Here's yet another piece of simple data compression code:

simple_lz

Cart File | Forum Post |

	More cartridges by luchak

More Cartridges [View All]

 

simple_lz

by luchak

Cart #simple_lz-0 | 2023-04-09 | Code ▽ | Embed ▽ | License: CC4-BY-NC-SA

4

I wrote this for a (hopefully) upcoming player cart for RP-8 songs, in order to be able to pack as much RP-8 song data as possible into the spritesheet/map/sfx/music area of the cart. The compression technique is basically LZSS, with a couple of small changes / enhancements:

• The code supports strings longer than 32kB - it will break them into 32kB blocks for compression and reassemble those blocks after decompression.
• Literals are move-to-front encoded.
• Match offsets, match lengths, and MTF literals are encoded using Elias gamma coding. The lowest N bits (N is a separately tunable parameter for offsets and literals, N is fixed to 0 for lengths) are encoded as usual, the remaining high-order bits are Elias gamma encoded.

The code works correctly on every string I've tested it on (so far) ... but I am less certain about whether there are efficiency bugs or not. The maximum supported match length is 1027.

If you would like to use this code, I suggest the following process:

1. Find some test data, and copy it into this cart.
2. Play around with different values of OFFB and MTFB to see which produce the smallest files. Generally, smaller values of OFFB will be better for smaller amounts of compressed data, larger values will be better for larger amounts of compressed data. 3 seems to be a good value for MTFB for most strings I have tried, but maybe you will find a case where a different value is better.
3. Modify this cart to save out your compressed data in whatever way makes sense to you.
4. Copy the functions pf_make_r, pf_decompress_block, and decompress into whatever cart needs to read the compressed data. You may want to substitute the various constants at the top of this cart with their literal tuned values at this time to save tokens. If you do this, the decompression code will probably clock in at a little over 250 tokens. I'm sure it's possible to make it much shorter.

At some point I may play around with having the compressor try out different OFFB and MTFB values on its own, or have it do some form of optimal LZ parsing. Basically, experimenting with different ways to trade slower compression times for slightly better compression ratios. Or perhaps I should just write a Pico-8 decompressor for upkr.

And here's a 0-clause BSD license for this code so you can go ahead and use it without worrying about the CC attribution or share-alike provisions if you want:

Permission to use, copy, modify, and/or distribute this software for
any purpose with or without fee is hereby granted.

THE SOFTWARE IS PROVIDED “AS IS” AND THE AUTHOR DISCLAIMS ALL
WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES
OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE
FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY
DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN
AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

Sorry, but I’m not a coder