| |
ChristopherJam
Registered: Aug 2004
Posts: 1397 |
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! |
|
... 38 posts hidden. Click here to view all posts....
|
| |
Bansai
Registered: Feb 2023
Posts: 40 |
Quoting Martin PiperIf I recall, reversing BWT encoded data needs a few sorts for each stored string. Which makes it quite expensive? Creating the BWT data also needs a sort, but I don't care about that so much. https://marknelson.us/posts/1996/09/01/bwt.html
...BWT is off topic from RLE, but Nelson breaks compression and decompression up into phases that can be piped, so it's easy to move them around, omit them entirely, etc., to see what they do.
His "The Data Compression Book" was a decent reference at the time it was published: https://marknelson.us/pages/tdcb.html. It's a good intro text for those who want to understand various forms of data compression. |
| |
Starfox
Registered: Jul 2014
Posts: 42 |
I found some links in my notes. Take them as they are.
It's mostly BWT though:
https://www.baeldung.com/cs/bwt-rle-compression-algorithm-for-s..
https://www.fileformat.info/mirror/egff/ch09_03.htm
https://www.youtube.com/watch?v=4n7NPk5lwbI
I had some other pdf's/videos with some other methods. If only I could find them... (same youtube channel)
Here's one "FM index": https://www.youtube.com/watch?v=kvVGj5V65io (It's also based on BWT).
I can't find a description of a scheme to encode the number of bytes in a row, I read, where you stored the number of equal bytes in bit representation so it could be any number. I'll put the link if I find it.
Think it is this Unary coding/elias in this video, where he explains it:
https://www.youtube.com/watch?v=3jKLjmV1bL8
ok last link about text transforms before encoding:
https://www.youtube.com/watch?v=Q2pinaj3i9Y
p.s sorry for messy post :) |
| |
ChristopherJam
Registered: Aug 2004
Posts: 1397 |
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: 1065 |
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: 241 |
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: 1750 |
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: 241 |
@tlr thanks! |
| |
Martin Piper
Registered: Nov 2007
Posts: 659 |
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: 1750 |
Quote: Some freezers did this for the colour RAM.
You mean just packed nybbles? |
| |
Fungus
Registered: Sep 2002
Posts: 648 |
That's what he means, and its a very very common technique. |
| Previous - 1 | 2 | 3 | 4 | 5 - Next |
