| |
ChristopherJam
Registered: Aug 2004
Posts: 1423 |
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! |
|
... 40 posts hidden. Click here to view all posts....
|
| |
ChristopherJam
Registered: Aug 2004
Posts: 1423 |
Cheers for the links, Starfox!
This is getting a bit off topic (ironic given that this page was created to shift all the RLE talk away from another discussion) but yeah, I've been looking at FM-Index and BWT for implementing a native cruncher that doesn't require an REU just to get compression time down to something workable. There's been a lot of interesting research the past 20 years!
Have you done any work on implementing BWT in a c64 context? |
| |
Burglar
Registered: Dec 2004
Posts: 1137 |
Quoting enthusiJust to add an alternative which is a bit special but cute:
Maniac Mansion and ZMK use some RLE depacker that resides in ZP and encodes most-common bytes, which I felt works rather well for graphics. I wrote something about that here:
https://www.pagetable.com/?p=603
A byte of < $40 = count of raw bytes following
$3f to < $80 represents the length of the run of the byte to follow (+$3f of course).
$7f to < $a0 is the number of runs of most common byte 1,
$9f to < $c0 and $bf to <$e0 and $df-$ff for common byte 2, 3 and 4 respectively. that is interesting indeed, also lovely article, even Ron Gilbert himself replied :)
not having looked at the unpacker, i'm assuming lotsa CMPs, so possibly custom ranges could generate great results for various inputs. |
| |
ws
Registered: Apr 2012
Posts: 251 |
Hej,
i know, thin ice here, please excuse, but this is a real question.
ABSTRACT:
So if you have a longer sequence of bytes like
04 0f 02 0a 08 09 01 02 06 05 (->low nibbles)
or
80 c0 90 10 20 a0 f0 70 d0 b0 (->high nibbles)
where you could compress by just saying
crunch mode identifier byte $f1 for combining the low nibbles,
number of "stacked bytes" (10) $0a,
followed by cojoined nibbles, resulting in:
f1 0a 4f 2a 89 12 65
or
crunch mode identifier byte $f2 for combining the high nibbles,
number of "stacked bytes" (10) $0a
followed by cojoined nibbles, resulting in
f2 0a 8c 91 2a f7 dc
QUESTION:
is there a name for this compression method?
would there be a more efficient simple way to compress these (usually very random) numbers (preferrably to implement as a cruncher on a c64)?
my initial thought stems from the practice of crunching a petscii color map by 50% like this.
thanks in advance for helpful answers, and really sorry, i had no clue how to search for this certain usecase. |
| |
tlr
Registered: Sep 2003
Posts: 1807 |
Quoting wsQUESTION:
is there a name for this compression method?
shift + or?
Quoting wswould there be a more efficient simple way to compress these (usually very random) numbers (preferrably to implement as a cruncher on a c64)?
If the numbers are indeed random, then your suggested method should be the most effective. |
| |
ws
Registered: Apr 2012
Posts: 251 |
@tlr thanks! |
| |
Martin Piper
Registered: Nov 2007
Posts: 739 |
Quote: Hej,
i know, thin ice here, please excuse, but this is a real question.
ABSTRACT:
So if you have a longer sequence of bytes like
04 0f 02 0a 08 09 01 02 06 05 (->low nibbles)
or
80 c0 90 10 20 a0 f0 70 d0 b0 (->high nibbles)
where you could compress by just saying
crunch mode identifier byte $f1 for combining the low nibbles,
number of "stacked bytes" (10) $0a,
followed by cojoined nibbles, resulting in:
f1 0a 4f 2a 89 12 65
or
crunch mode identifier byte $f2 for combining the high nibbles,
number of "stacked bytes" (10) $0a
followed by cojoined nibbles, resulting in
f2 0a 8c 91 2a f7 dc
QUESTION:
is there a name for this compression method?
would there be a more efficient simple way to compress these (usually very random) numbers (preferrably to implement as a cruncher on a c64)?
my initial thought stems from the practice of crunching a petscii color map by 50% like this.
thanks in advance for helpful answers, and really sorry, i had no clue how to search for this certain usecase.
Some freezers did this for the colour RAM. |
| |
tlr
Registered: Sep 2003
Posts: 1807 |
Quote: Some freezers did this for the colour RAM.
You mean just packed nybbles? |
| |
Fungus
Registered: Sep 2002
Posts: 746 |
That's what he means, and its a very very common technique. |
| Previous - 1 | 2 | 3 | 4 | 5 - Next |
