6502 Compressors / Decompressors

[Negative Charge]

Hi all,

I've been porting a number of decompression routines to BeebAsm format and thought I'd share the links here. I haven't really performed any analysis at this time as to best performing (some are clearly a lot faster than others) or which compress best. My main goal is to find a decompressor that allows sequential byte access to a stream similar to Exomizer but with less overhead. Huffmunch does this but the uncompressed source is limited to 64Kb and it's slow. I think some of the others can be adapted with some work - ZX02 looks the most interesting.

Hopefully these may be of some interest/use for others - each has a sample pre-built .ssd that decompresses the same Mode 5 picture to screen:

• Exomizer 3.1.1 https://github.com/NegativeCharge/Exomi ... ebAsm-Port
• Dali https://github.com/NegativeCharge/Dali- ... ebAsm-Port
• Shrinkler https://github.com/NegativeCharge/Shrin ... ebAsm-Port
• TSCrunch https://github.com/NegativeCharge/TSCru ... compressor
• apultra https://github.com/NegativeCharge/apult ... compressor
• Huffmunch https://github.com/NegativeCharge/Huffm ... compressor
• LZSA2 https://github.com/NegativeCharge/LZSA2 ... compressor
• ZX02 https://github.com/NegativeCharge/ZX02- ... compressor
• ZX0 https://github.com/NegativeCharge/ZX0-6 ... Acorn-Port
• Tricky’s Compressor https://github.com/NegativeCharge/Trick ... compressor
• c64f https://github.com/NegativeCharge/c64f- ... ebAsm-Port
• Packbits https://github.com/NegativeCharge/PackB ... ebAsm-Port
• ZX7 https://github.com/NegativeCharge/ZX7-6 ... ebAsm-Port
• ZX5 https://github.com/NegativeCharge/ZX5-6 ... ebAsm-Port
• LZ4 https://github.com/NegativeCharge/LZ4-6 ... ebAsm-Port

Code: Select all

Compressor	Size	Speed		ZP Data		Decomp Size
-------------------------------------------------------------------
Exomiser	6688    Medium		18		513
Huffmunch	7320	Medium		14		330
TSCrunch	7632	Very Fast	7		248
Dali		6950	Fast		6		264
Shrinkler	6685	Slow		19-27		468
LZSA2		7213	Fast		1		253
ZX02		6816	Fast		10		138
ZX0		6918	Fast		4		223
apultra		7061	Fast		9		252
Tricky		8438 	Fast 	 	5		72
c64f		6860 	Fast 		11		267
Packbits	8600	Fast		6		110
ZX7		6861	Fast		12		162
ZX5		6712	Fast		14		262
LZ4		7569	Fast		0		144

If you have other recommendations or know of streaming decompression algorithms I can implement I'd be very interested.

[tricky]

There is a thread on various ones and I think kieranhj posted a link to a nice graph, but I don't remember them mentioning streaming.
Mine can stream in pages, but the source is from memory and the compression not great, by it is small and reasonably fast.

[0xC0DE]

I've been porting a number of decompression routines to BeebAsm format and thought I'd share the links here.

Thank you!

[julie_m]

This is really meant for decompressing text, and includes some more stuff besides that -- basically, most of the lifting and shifting for text adventures -- but is linked in case someone finds it useful:

https://github.com/JulieMontoya/AdveBuilder

This only includes decompression code for the 6502, as it's meant for authoring games on the emulation host, so counting frequencies, building up the symbol tree and the actual compression were intended all to be done on that side; but I recently started wondering about using my existing decompression code from AdveBuilder for some documentation for BCP, which (having already started it as a multi-part build on the Beeb before I discovered BeebAsm) I always wanted to be fully buildable on the target. So I had a stab at porting the compression stuff over to the 6502, have working code (and it's not as slow as I was afraid it would be, which is nice; I tried a programming trick I always regarded as a bit dirty, but it seems to have paid off) and just need to write some notes, if anyone is interested.

[SteveF]

I've been porting a number of decompression routines to BeebAsm format and thought I'd share the links here.

Thanks for doing this, it will make it a lot easier for people to choose an optimal decompressor for their needs in future!

There is a thread on various ones and I think kieranhj posted a link to a nice graph, but I don't remember them mentioning streaming.

FWIW the LZSA github page has a graph which shows some (I don't think all) of these compressors. The performance is based on the ZX Spectrum so is probably only vaguely indicative of 6502 performance, but the actual compression ratio should presumably be the same.

[ChrisB]

I will certainly be investigating some of these. A quick table from the example disks of the code size (data+code) and my perceived decompression speed and the number of ZP bytes that they use.

Code: Select all

Compressor	Size	Speed		ZP Data
Huffmunch	7320	Medium		14
TSCrunch	7632	Very Fast	7
Dali		6950	Fast		6
Shrinkler	6685	Slow		19-27
LZSA2		7213	Fast		1
ZX02		6816	Fast		10
ZX0		6918	Fast		4
apultura	7061	Fast		9

[Negative Charge]

There is a thread on various ones and I think kieranhj posted a link to a nice graph, but I don't remember them mentioning streaming.
Mine can stream in pages, but the source is from memory and the compression not great, by it is small and reasonably fast.

Thanks Tricky! I’ve added your compressor to the list - it’s fast but doesn’t compress the sample image as well as the others. Compressed file size is 8,438 bytes.

[tricky]

Thank you for taking the time to try it.

Yes, I wrote it to compress my games so that they fit in a 16k ROM and as I'm usually using a screen that is 16k, but can be less and sometimes include a status area, or three entire screen in the case of pacman, it usually only needs to compress 17 or 18k into about 15.5k plus the ROM header and decompressor. The same file when not loaded as a ROM works as an exe so, my priorities were small, fast and then compression.

I also have a tiny steaming text one that is used for my menu system that does a much better on that data, but probably not as well as compressors that target text. It uses a page of memory as a dictionary and a handful of byes as a stack but that could be 128 byes worst case. Again, the goal was to get a few thousand strings totalling about 50k into the beeb along with the menu program and be able to jump to and page and display 23 of them with a tiny amount of meets data for each.

[Negative Charge]

I will certainly be investigating some of these.

Thanks! I’ve added your table to the first post and added two more compressors.

[tricky]

Does the size include the code, any decompression buffers or tables/dictionaries built while decompressing I'm sure I remember some needing quite a bit of space in addition to the size of the decompressor code?

[Negative Charge]

Does the size include the code, any decompression buffers or tables/dictionaries built while decompressing I'm sure I remember some needing quite a bit of space in addition to the size of the decompressor code?

Very good point. I’ll add the decompressor sizes to the table too.

[VectorEyes]

Hi Negative Charge,

Love your stuff! Thanks for doing this, it’s a really useful piece of research.

I’ve leaned heavily on Exomizer3 in previous demos so I’d be very interested in any compressors that offer substantially better compression ratios (which seems unlikely, it seems that Exo3 is pretty good) or compression similar to Exo3 but with faster decrunch. Frankly, I’m not too fussed about decrunch speed — the benefits of having a “background decruncher” system — but if a faster one with equal compression ratio was available it would be silly not to use it!

Could I make two suggestions? It would be great to be able to directly compare all of the compressors against Exo3. Would adding Exo3’s results to the table be easy? Also, I believe that just compressing one image may not cover how the compressors deal with different types of input. For instance, 65(C)02 code may compress differently, as may music streams, data tables, other images, or binary blobs containing mixtures of the above. A few more test files of various kinds might identify the strengths and weaknesses of the various compressors (although I appreciate that doing all that would be a lot of effort!)

[TobyLobster]

Great work Negative Charge, I'm sure I will be making use of these results in future.

[Negative Charge]

Could I make two suggestions? It would be great to be able to directly compare all of the compressors against Exo3. Would adding Exo3’s results to the table be easy? Also, I believe that just compressing one image may not cover how the compressors deal with different types of input. For instance, 65(C)02 code may compress differently, as may music streams, data tables, other images, or binary blobs containing mixtures of the above. A few more test files of various kinds might identify the strengths and weaknesses of the various compressors (although I appreciate that doing all that would be a lot of effort!)

Hi VectorEyes,

Thanks! I’ve also heavily relied on Exo2 and Exo3 in the past. I started this to try and find a faster decompressor as I’m looking to compress large amounts of SN76489 register data to playback at speeds much greater than 50Hz (1kHz or preferably 2kHz if possible). Exo soon shows its limitations here. However, it’s great for streaming and can work across multiple SWRAM banks.

I’ll add Exo3 soon - the size of the decompression buffers are also something to consider here. Not sure I’ll have the time or patience to do a thorough test with different payloads, but made these available for others to improve and test as they wish. I may at least try some large music data payloads though.

[Negative Charge]

To follow up on this topic, I've finally managed lo get an LZSS-based streaming music player working. It's based on the Atari SAP music player, but modified for raw SN76489 register writes - due to the initial code using 9 byte streams for the Atari POKEY registers (and needing 11 byte streams for the SN76489) I've compressed the four volume nybbles into 2 bytes at the end of each frame. I believe music data will compress better with 11 bytes streams, but for now it works with my less than optimal player.

I'll post the code to GitHub once I've made more progress, but attached is a sample. This music track compresses to 13,528 bytes from 103,680 bytes (13528 / 103680 = 13.05%) so a very decent compression ratio. The player needs 9*256 bytes of buffer for a look back window, but the player itself is a lot faster than using Exomizer - you can see the raster time used per frame in the demo:

LZSSPlayer.ssd

(17.25 KiB) Downloaded 12 times

You can try it via VirtualBeeb here: https://negativecharge.github.io/virtua ... Player.ssd

I'm looking into whether something similar is achievable with ZX0 or ZX02.

[FYI - The code this is based on comes from https://github.com/dmsc/lzss-sap]

[davidb]

This music track compresses to 13,528 bytes from 103,680 bytes (13528 / 103680 = 13.05%) so a very decent compression ratio.

Can you post a link to the original data, please? It would be interesting to try various algorithms on it.

[Negative Charge]

This music track compresses to 13,528 bytes from 103,680 bytes (13528 / 103680 = 13.05%) so a very decent compression ratio.

Can you post a link to the original data, please? It would be interesting to try various algorithms on it.

Here you go:

output.zip

(16.64 KiB) Downloaded 25 times

[davidb]

Looking at the size of the zip archive, it seems difficult to improve on the compression ratio you've achieved with your compressor.

I tried my simple stream compressor and couldn't get below around 60K.

[VectorEyes]

What is the exact nature of the input data before compression? I'm curious because my current music-compression-and-playback solution which is based on a modified version of SimonM's 'VGC' format -- https://github.com/simondotm/vgm-packer -- seems to compress at equivalent or slightly better ratios (Simon's page suggests 9 - 11 % of original file size) and only needs 8x256byte buffers for playback. It's essentially 3 streams of 16-bit data and 5 streams of 8-bit, each one run-length-encoded and then LZ4 compressed. It would be interesting to convert your test file to VGM format and see how well it compressed under that scheme. It looks like the SAP format is 9 streams but not run-length encoded, so a bit different.

In any case it seems that both seems achieve approximately the same packing ratio. It seems that around 10% is the typical ballpark for SN music compression, unless anyone comes up with something radically different!

[Negative Charge]

What is the exact nature of the input data before compression?

That would have been useful information for me to add! The format is per frame:

[Tone 0 Latch/Data][Tone 0 Data] [Tone 1 Latch/Data][Tone 1 Data] [Tone 2 Latch/Data][Tone 2 Data][Noise Latch/Data][Vol 0|Vol 1][Vol 2|Vol 3]

So 9 bytes. I think the combining of volume data nybbles into bytes may be hurting the compression.

I’ll output to VGM and compare with Simon’s compressor later - that’s my usual playback engine, but I’m looking if there’s anything faster for decompression as I have music data for playback at 882Hz and higher (I’ve some really nice sounding 2kHz tracks which simulate the AY envelopes quite well, but all attempts to play them back have resulted in stuttered slowed down playback.

[Negative Charge]

It would be interesting to convert your test file to VGM format and see how well it compressed under that scheme.

vgc-compressed.zip

(13.37 KiB) Downloaded 10 times

For this track the compressed file size is 7587 bytes - so much better than my LZSS compression. However, this format can't be directly fed to the SN76489 so not necessarily a good comparison. My goal is lowest decompression time rather than maximum compression.

[VectorEyes]

For this track the compressed file size is 7587 bytes - so much better than my LZSS compression. However, this format can't be directly fed to the SN76489 so not necessarily a good comparison. My goal is lowest decompression time rather than maximum compression.

Thanks very much! Out of curiosity I fed it into my hacked-around VGC compressor / player and got a result of 7548 bytes (slightly better than standard VGC). I think if I'm reading this right, your LZSS player is taking the bytes and sending them straight to the SN76489, 11x per 'update', with literally no 'byte decoding' required? Whereas the VGC player has to do masking and other decoding before it sends the data to the SN, but the RLE encoding means that it can just not bother to send bytes if they don't need to be updated, which presumably saves a few cycles. My version interleaves the 8 LZ-compressed streams, making it 'streamable' (there's only one 'read pointer' into the source data) which also saves a little bit of CPU time because there's less context to set up when LZ-decoding each byte.

I wonder how we could precisely quantify the CPU time spent by the various playback schemes, and how 'bumpy' they are, ie how much variance in CPU cycles spent there is frame-to-frame. Perhaps hacking one of the emulators to record CPU cycles spent inside the 'music update' function each frame would be the way to go. You could then start to get clever and make the compressor defer register updates by one frame if a frame is particularly heavy for CPU decoding, etc.

Anyway this is all getting rather a long way away from the thread's original purpose of exploring 6502 compressors / decompressors in general! Time to move to a 'music compression' thread perhaps?

[Negative Charge]

If anyone is interested in the LZSS music player, I'm developing the code here: https://github.com/NegativeCharge/BBC-M ... ZSS-Player

My 6502 isn't great, but it's working so far. A few basic tests shows this still probably isn't fast enough for 1 kHz playback, but it's a nice lightweight alternative that has pretty good compression.

[BlondMM]

Hi all,

I've been porting a number of decompression routines to BeebAsm format and thought I'd share the links here. I haven't really performed any analysis at this time as to best performing (some are clearly a lot faster than others) or which compress best. My main goal is to find a decompressor that allows sequential byte access to a stream similar to Exomizer but with less overhead. Huffmunch does this but the uncompressed source is limited to 64Kb and it's slow. I think some of the others can be adapted with some work - ZX02 looks the most interesting.

Hopefully these may be of some interest/use for others - each has a sample pre-built .ssd that decompresses the same Mode 5 picture to screen:

If you have other recommendations or know of streaming decompression algorithms I can implement I'd be very interested.

In an attempt to write my own fast decompressor someday, I gathered also a couple of interesting finds last year:

FastLZ - https://ariya.github.io/FastLZ/
LZO - http://www.oberhumer.com/opensource/lzo/
pucrunch - https://github.com/mist64/pucrunch/
- http://a1bert.kapsi.fi/Dev/pucrunch/

[Negative Charge]

In an attempt to write my own fast decompressor someday, I gathered also a couple of interesting finds last year:

FastLZ - https://ariya.github.io/FastLZ/
LZO - http://www.oberhumer.com/opensource/lzo/
pucrunch - https://github.com/mist64/pucrunch/
- http://a1bert.kapsi.fi/Dev/pucrunch/

Thanks! If you are aware of 6502 versions of the first two I’d gladly take a look at porting them to beebasm. For pucrunch there’s already a version for the Beeb here: http://www.retrosoftware.co.uk/wiki/ind ... _Pu_Crunch

When I find some time I’ll look at creating a similar comparison for pucrunch.