| |
Flavioweb
Registered: Nov 2011
Posts: 447 |
Native crunch/decrunch code.
Do you know if the source code of a native crunch/decrunch routine for C64 exists somewhere?
Not a complete utility with interface etc...
just the compression/decompression code. |
|
| |
tlr
Registered: Sep 2003
Posts: 1727 |
Are there any requirements on performance here? Compression and speed that is. |
| |
Flavioweb
Registered: Nov 2011
Posts: 447 |
No.
Preferably it should use little ram but I have some headroom to adapt. |
| |
Krill
Registered: Apr 2002
Posts: 2855 |
Quoting FlaviowebDo you know if the source code of a native crunch/decrunch routine for C64 exists somewhere?
Not a complete utility with interface etc...
just the compression/decompression code. Why would you want to crunch natively?
And if you really must, why do you need the source code?
Just pick apart any of the crunchers from the olden days. |
| |
Flavioweb
Registered: Nov 2011
Posts: 447 |
Quoting KrillWhy would you want to crunch natively?
And if you really must, why do you need the source code?
Just pick apart any of the crunchers from the olden days.
I have a program running, from $3000 to $FFFF that modifies itself.
I would like the user to be able to save a stand alone version.
I managed to get the working sources of Fast Cruncher 5.09 but as soon as I change a small thing I create a lot of problems.
I would like to avoid unnecessary waste of time by using existing code... if it exists somewhere.
that's all. |
| |
tlr
Registered: Sep 2003
Posts: 1727 |
Quote: No.
Preferably it should use little ram but I have some headroom to adapt.
Then I’d go for a simple RLE. |
| |
Krill
Registered: Apr 2002
Posts: 2855 |
Quoting tlrThen I’d go for a simple RLE. Indeed. Native LZ-style crunching would take hours like it did in the olden days.
RLE is not nearly as crunchy, but fast and might fit the bill, too. |
| |
Flavioweb
Registered: Nov 2011
Posts: 447 |
Thank you!
If you can provide me with something I hope to be able to use it properly. |
| |
Krill
Registered: Apr 2002
Posts: 2855 |
Quoting FlaviowebIf you can provide me with something I hope to be able to use it properly. https://codebase64.org/doku.php?id=base:rle_pack_unpack perhaps. |
| |
Raistlin
Registered: Mar 2007
Posts: 575 |
Quote: Quoting FlaviowebIf you can provide me with something I hope to be able to use it properly. https://codebase64.org/doku.php?id=base:rle_pack_unpack perhaps.
I’m not the person for this, but, that code on Codebase64 looks a bit long for just RLE pack/depack doesn’t it..? It seems like something that could be coded with a really tight loop… |
| |
tlr
Registered: Sep 2003
Posts: 1727 |
Quoting RaistlinI’m not the person for this, but, that code on Codebase64 looks a bit long for just RLE pack/depack doesn’t it..? It seems like something that could be coded with a really tight loop…
Also it's missing the requested executable binary generation. I have some RLE code here, but that is for streamed input from disk which may not be optimal for this usecase. |
| |
chatGPZ
Registered: Dec 2001
Posts: 11148 |
mmmh i remember some simple packer from the past... it loaded to $03xx-$0800 and was super easy to include in own programs (which many people did, i also used it for some "intromaker" stuff iirc). No idea how it was called though, maybe someone remembers... :) |
| |
Martin Piper
Registered: Nov 2007
Posts: 645 |
For simple RLE, it should be relatively simple to write two position independent routines. One to compress a block of memory to an address, and the other one to decompress data to an address.
The decompression especially could then be copied to anywhere and just pointed at the data to decompress. |
| |
Flavioweb
Registered: Nov 2011
Posts: 447 |
I have collected some ideas in the last few days and I think I have reached a good compromise (at least on a theoretical level).
The "pure" RLE compression didn't convince me very much because, in practice, it doubled the space required for the code to be compressed, but it works well for the data part.
In my specific case I know the location of both the code and the data so I can create an ad hoc compression routine that compresses the data and leaves the code unchanged.
To overcome the problems of lack of RAM, I can save the compression result directly on disk while it is being processed, preceded by the decompression code so as not to worry about creating the entire file in ram before saving it.
It should work. I hope. |
| |
Krill
Registered: Apr 2002
Posts: 2855 |
Quoting FlaviowebThe "pure" RLE compression didn't convince me very much because, in practice, it doubled the space required for the code to be compressed, but it works well for the data part. It seems like you've misunderstood how the algorithm/encoding works.
Actual RLE emits a counter/type byte to encode a run, with up to 128 bytes of repeating or literal bytes. (Ignore the inferior escape byte approach that was so popular on C-64.)
So, worst case would be one extra byte for every 128 input bytes. |
| |
tlr
Registered: Sep 2003
Posts: 1727 |
Quoting KrillActual RLE emits a counter/type byte to encode a run, with up to 128 bytes of repeating or literal bytes. (Ignore the inferior escape byte approach that was so popular on C-64.) Not sure I agree the escape byte approach is inferior, but it's more messy.
Though as you point out, some way to differentiate literals vs runs is required for RLE. There should be little or no expansion of uncompressible sections. |
| |
Krill
Registered: Apr 2002
Posts: 2855 |
Quoting tlrNot sure I agree the escape byte approach is inferior, but it's more messy. It's inferior in the way the decompressor needs to look at every input byte to decide what to do,
while the 1.7bits control byte approach allows for loops or nice Duff's devices that don't need to branch for every input byte, as the length of both types of run is known beforehand.
(It's a bit like C-strings vs Pascal-strings. =D) |
| |
tlr
Registered: Sep 2003
Posts: 1727 |
Quote: Quoting tlrNot sure I agree the escape byte approach is inferior, but it's more messy. It's inferior in the way the decompressor needs to look at every input byte to decide what to do,
while the 1.7bits control byte approach allows for loops or nice Duff's devices that don't need to branch for every input byte, as the length of both types of run is known beforehand.
(It's a bit like C-strings vs Pascal-strings. =D)
Yeah, but you have to count instead. In the RLE case it's also usually less efficient, although RLE is very inefficient to begin with. |
| |
ChristopherJam
Registered: Aug 2004
Posts: 1381 |
So far as RLE is concerned, alternately you can just output a count of "how many more repeats" after each adjacent pair of identical values, and potentially huffman encode the counts to make them smaller.
(eg abbcdddeffffg becomes abb{0}cdd{1}eff{2}g )
But anyway, I'm kind of tempted to push a simple MTF+uneven symbol size codec out the door - a quick draft crunches zorro from 54105 bytes to 45892, and would be fairly simple to implement in 6502. It's not as good a ratio as even tinycrunch (38962 bytes for the same test file), but it'd compress in a matter of seconds, and would outperform RLE unless you're crunching quite a bit of of empty space. Of interest? |
| |
Martin Piper
Registered: Nov 2007
Posts: 645 |
(number of literals)(output literals)(number of repeated bytes, repeat the previous byte)...
Since the number of repeats always follows a number of literals, there is no need for a control flag.
The "number of" can use some form of Elias gamma coding, for up to 16 bit values for the whole memory range, to keep things short. |
| |
Krill
Registered: Apr 2002
Posts: 2855 |
Let's not let this degrade to Code Golf, shall we. |
| |
Raistlin
Registered: Mar 2007
Posts: 575 |
Quote: Let's not let this degrade to Code Golf, shall we.
Why? I think the thread becomes more interesting that way… if “Code Golf” means what I think it means..? Or did you mean “Code Tennis”?
I like CJam’s idea, I never thought of doing RLE in that way and, annoyingly, it’s so damn obvious now that he’s suggested it. |
| |
Krill
Registered: Apr 2002
Posts: 2855 |
Quoting RaistlinWhy? I think the thread becomes more interesting that way… if “Code Golf” means what I think it means..? Or did you mean “Code Tennis”? No idea where the difference is, but i suggest another thread to discuss the relative pros and cons of various RLE schemes. =) |
| |
ChristopherJam
Registered: Aug 2004
Posts: 1381 |
(RLE discussion continued at On the relative pros and cons of various RLE schemes) |
