Memory-efficient decompression for embedded computers

Discuss all aspects of programming here. From 8-bit through to modern architectures.
User avatar
davidb
Posts: 1825
Joined: Sun Nov 11, 2007 10:11 pm
Contact:

Memory-efficient decompression for embedded computers

Postby davidb » Tue Oct 03, 2017 4:04 pm

I stumbled upon this article while looking at other things: Memory-efficient decompression for embedded computers. It's probably quite a lot like the existing schemes used by members here - all LZ-based if I remember correctly - but it performs well enough to be a candidate for someone to write a 6502 decompression routine for it.

User avatar
kieranhj
Posts: 481
Joined: Sat Sep 19, 2015 10:11 pm
Location: Farnham, Surrey, UK

Re: Memory-efficient decompression for embedded computers

Postby kieranhj » Wed Oct 04, 2017 8:26 am

Interesting. Thank for the find! I've relied heavily on Exomiser for high compression ratios previously but the decompression is very expensive and typically requires 1K or more of scratch RAM at higher rates. Would be interesting to run some comparisons with this scheme (and the others like Tricky's mentioned previously.)

Phantasm
Posts: 14
Joined: Thu Jan 19, 2017 9:56 pm

Re: Memory-efficient decompression for embedded computers

Postby Phantasm » Wed Oct 04, 2017 4:25 pm

I have attached some stuff I wrote earlier this year when doing a tape 2 disc conversion project for the Electron.

It is a lzss compressor in C# (source code included) with a 6502 uncompressor with BBC basic source code included.

The source code includes a test project that compares several slightly different implementations of lzss and the one i decided to go for in the end uses a byte to store 8 flags for the next 8 runs of data to indicate whether they are an uncoded character or a repeat of some already uncompressed data. When encoding a repeat run it uses 1 byte for the offset and 1 byte for the length. Repeat runs are only encoded where more than 2 characters are matched giving a maximum compressed run of 258 characters.

The following files are included in the archive:

LzssPackUnpack.exe - windows command line compress/decompress tool (needs .net framework)
screen.raw - a sample file used to test (a saved mode 5 screen)
test.pak - the compressed version of the above screen.raw file
unpackscr.bas - the decompression assembly code
test.sdd - the sample test files and the unpacker on a dfs disc

You can see from the included source that the unpack code uses some addresses in the &70-&79 range to store the addresses of the source, destination and end of the compressed data.

When uncompressing you can either uncompress to a different memory area or over the original data - if you decompress over the original data you should put the compressed data at the very end of the buffer area so that it doesnt get overwritten during the decompress

eg.

uncompressed data area: &5800 - &7fff
compressed data size: &800

compressed data should be loaded at &7800 - &7fff

the compressed data is all stored in bytes rather than a packed stream of bits so its pretty quick to decompress although it wont win any awards for its compression ratios it is also highly memory efficient

Hope this stuff is useful to someone

Darren
Attachments
lzss beeb.zip
some beeb lzss compression/decompression stuff
(36.54 KiB) Downloaded 4 times

User avatar
kieranhj
Posts: 481
Joined: Sat Sep 19, 2015 10:11 pm
Location: Farnham, Surrey, UK

Re: Memory-efficient decompression for embedded computers

Postby kieranhj » Wed Oct 04, 2017 6:50 pm

Thank you for adding that to the list Darren and with such comprehensive source.

When I get chance I would like to do some comparisons of the various general purpose compression schemes available for the Beeb.

There was some discussion on this topic on the old RetroSoftware forums: http://www.retrosoftware.co.uk/forum/viewtopic.php?f=73&t=999

User avatar
tricky
Posts: 1811
Joined: Tue Jun 21, 2011 8:25 am
Contact:

Re: Memory-efficient decompression for embedded computers

Postby tricky » Wed Oct 04, 2017 9:30 pm

Phantasm, when I was doing mine, I found that rather than having 1+7+8 bits, other ratios were better, but I like your idea of having 8 flags together and then whole bytes for size and offset.


Return to “programming”

Who is online

Users browsing this forum: No registered users and 3 guests