| |
ChristopherJam
Registered: Aug 2004
Posts: 1380 |
On the relative pros and cons of various RLE schemes
So over in Native crunch/decrunch code. I just suggested encoding
abbcdddeffffg as
abb{0}cdd{1}eff{2}g
Raistlin kindly liked the idea, Krill quite sensibly didn't want us to hijack the post and suggested a new post for the new topic. so... Have at it! |
|
| |
ChristopherJam
Registered: Aug 2004
Posts: 1380 |
(oh, addendum - whenever the count maxes out, there's no literal following, just another count - which could be zero. This also makes it quite easy to play with different count widths, (eg nybbles or bitpairs) without going down the huffman or arbitrary precision integer routes) |
| |
Krill
Registered: Apr 2002
Posts: 2852 |
As RLE isn't very crunchy to begin with, i'd suggest to focus on other things affecting performance,
such as whether the scheme allows for stream encoding (entire input not known beforehand) for a local optimum within this scheme,
whether or not it's a bit- rather than bytestream,
and how big a 6502 decompressor would be. |
| |
ChristopherJam
Registered: Aug 2004
Posts: 1380 |
I must admit, I came up with the scheme above partly because I got most of the way through implementing a cruncher for the usual escape byte based scheme and thought there must be a simpler way - so if anything I was (vaguely) optimising for code complexity - which presumably maps to code size to some extent. |
| |
tlr
Registered: Sep 2003
Posts: 1721 |
Quoting ChristopherJamSo over in Native crunch/decrunch code. I just suggested encoding
abbcdddeffffg as
abb{0}cdd{1}eff{2}g
Isn't this going to be expensive for certain inputs containing lots of byte pairs? |
| |
ChristopherJam
Registered: Aug 2004
Posts: 1380 |
That depends how expensive your encoding for a zero additional repeat counts is. But sure, every compression scheme is vulnerable to certain inputs getting bigger instead of smaller, otherwise you could just keep recrunching to get arbitrarily small outputs. |
| |
tlr
Registered: Sep 2003
Posts: 1721 |
but here you'll be vulnerable to something not too uncommon. I think for a run count represented with a regular byte, the escape code method is going to be smaller than both this and the lit/run chunk with count method for almost all normal c64 input. |
| |
CyberBrain
Administrator
Posts: 392 |
Quote: So over in Native crunch/decrunch code. I just suggested encoding
abbcdddeffffg as
abb{0}cdd{1}eff{2}g
Raistlin kindly liked the idea, Krill quite sensibly didn't want us to hijack the post and suggested a new post for the new topic. so... Have at it!
That looks like the encoding scheme from the codebase64 article? (https://codebase64.org/doku.php?id=base:rle_pack_unpack)
Yes, that way of encoding it, wastes one byte for each 2-byte repeat (starts saving bytes for 4-byte repeats and longer), so could be bad if there are too many of those in the input data
(I actually used that one in my latest demo to get room for more pics in memory, and this ultra simple RLE-based packing, together with delta-encoding, worked surprisingly (to me) well - it saved multiple $100s of bytes off some pics (they did have large background areas, but still), so the 2-repeats doesn't have to be a problem)
It could be interesting to hear about the other ways of representing the bytes of RLE-encoding, which are used on the C64.
For example, what is this "the usual escape byte based scheme" you guys have mentioned in this and the other thread? And the counter representation? |
| |
tlr
Registered: Sep 2003
Posts: 1721 |
Quoting CyberBrainIt could be interesting to hear about the other ways of representing the bytes of RLE-encoding, which are used on the C64.
For example, what is this "the usual escape byte based scheme" you guys have mentioned in this and the other thread? And the counter representation?
escape byte (typical example):
<byte> - emit byte
<esc> <count> <byte> - emit count * byte
<esc> $00 - emit 'esc' byte the esc byte is selected as the least used byte in the data (with some optimizations possible).
lit/run chunk (typical example):
$01-$7f, 1-127 * <byte> - emit 1-127 literal bytes
$81-$ff, <byte> - emit 1-127 * byte
$00 - end of stream |
| |
Krill
Registered: Apr 2002
Posts: 2852 |
Quoting tlrbut here you'll be vulnerable to something not too uncommon. I think for a run count represented with a regular byte, the escape code method is going to be smaller than both this and the lit/run chunk with count method for almost all normal c64 input. As RLE isn't that crunchy anyways, performance should be the main regard (where crunchiness plays a rather weak role, but it still has some impact).
Some test corpus wouldn't hurt, ofc. Maybe the good old Bitfire benchmark files? |
| |
CyberBrain
Administrator
Posts: 392 |
<Post edited by CyberBrain on 22/4-2024 23:52>
Cool, thank you, tlr!
Ah, ok, i can see how the "Escape byte" representation doesn't have to waste anything for 2-byte repeats (but requires an extra pass over the input data to find the least used byte when packing).
If understand the "lit/run chunk" representation correctly, it looks like it wastes a byte on each literal-chunk (so at least 2 bytes per 256 packed bytes, as far as i can tell). Looks like this could struggle a bit if there are many short repeats mixed in between non-repeating data. Edit: No, it couldn't - fake news.
Those are the 3 standard representations on C64? |
... 26 posts hidden. Click here to view all posts....
|
| Previous - 1 | 2 | 3 | 4 - Next |
