Log inRegister an accountBrowse CSDbHelp & documentationFacts & StatisticsThe forumsAvailable RSS-feeds on CSDbSupport CSDb Commodore 64 Scene Database
You are not logged in - nap
CSDb User Forums


Forums > C64 Coding > On the relative pros and cons of various RLE schemes
2024-04-21 17:12
ChristopherJam

Registered: Aug 2004
Posts: 1382
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....
 
2024-05-29 20:13
Bansai

Registered: Feb 2023
Posts: 36
Quoting Martin Piper
If 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.
2024-05-30 20:15
Starfox

Registered: Jul 2014
Posts: 34
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 :)
2024-05-31 04:34
ChristopherJam

Registered: Aug 2004
Posts: 1382
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?
2024-05-31 20:41
Burglar

Registered: Dec 2004
Posts: 1051
Quoting enthusi
Just 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.
2024-06-07 19:32
ws

Registered: Apr 2012
Posts: 235
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.
2024-06-07 21:03
tlr

Registered: Sep 2003
Posts: 1730
Quoting ws
QUESTION:
is there a name for this compression method?

shift + or?

Quoting ws
would 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.
2024-06-07 21:16
ws

Registered: Apr 2012
Posts: 235
@tlr thanks!
2024-06-08 04:27
Martin Piper

Registered: Nov 2007
Posts: 647
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.
2024-06-08 18:38
tlr

Registered: Sep 2003
Posts: 1730
Quote: Some freezers did this for the colour RAM.

You mean just packed nybbles?
2024-06-08 19:36
Fungus

Registered: Sep 2002
Posts: 631
That's what he means, and its a very very common technique.
Previous - 1 | 2 | 3 | 4 | 5 - Next
RefreshSubscribe to this thread:

You need to be logged in to post in the forum.

Search the forum:
Search   for   in  
All times are CET.
Search CSDb
Advanced
Users Online
psenough
Guests online: 91
Top Demos
1 Next Level  (9.7)
2 13:37  (9.7)
3 Mojo  (9.7)
4 Coma Light 13  (9.7)
5 Edge of Disgrace  (9.7)
6 Aliens in Wonderland  (9.6)
7 Comaland 100%  (9.6)
8 Uncensored  (9.6)
9 No Bounds  (9.6)
10 Wonderland XIV  (9.6)
Top onefile Demos
1 Layers  (9.6)
2 Cubic Dream  (9.6)
3 Party Elk 2  (9.6)
4 Copper Booze  (9.6)
5 Rainbow Connection  (9.5)
6 It's More Fun to Com..  (9.5)
7 Dawnfall V1.1  (9.5)
8 Daah, Those Acid Pil..  (9.5)
9 Birth of a Flower  (9.5)
10 Quadrants  (9.5)
Top Groups
1 Nostalgia  (9.4)
2 Oxyron  (9.3)
3 Booze Design  (9.3)
4 Censor Design  (9.3)
5 SHAPE  (9.3)
Top Organizers
1 Burglar  (9.9)
2 Sixx  (9.8)
3 hedning  (9.7)
4 Irata  (9.7)
5 Tim  (9.7)

Home - Disclaimer
Copyright © No Name 2001-2024
Page generated in: 0.043 sec.