| |
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. |
|
... 13 posts hidden. Click here to view all posts....
|
| |
Krill
Registered: Apr 2002
Posts: 2845 |
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: 1714 |
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: 2845 |
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: 1714 |
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: 1378 |
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: 634 |
(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: 2845 |
Let's not let this degrade to Code Golf, shall we. |
| |
Raistlin
Registered: Mar 2007
Posts: 562 |
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: 2845 |
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: 1378 |
(RLE discussion continued at On the relative pros and cons of various RLE schemes) |
| Previous - 1 | 2 | 3 - Next |
