What would be a good (de)compression routine for this scenario

Question

I need a FAST decompression routine optimized for restricted resource environment like embedded systems on binary (hex data) that has following characteristics:

1. Data is 8bit (byte) oriented (data bus is 8 bits wide).
2. Byte values do NOT range uniformly from 0 - 0xFF, but have a poisson distribution (bell curve) in each DataSet.
3. Dataset is fixed in advanced (to be burnt into Flash) and each set is rarely > 1 - 2MB

Compression can take as much as time required, but decompression of a byte should take 23uS in the worst case scenario with minimal memory footprint as it will be done on a restricted resource environment like an embedded system (3Mhz - 12Mhz core, 2k byte RAM).

What would be a good decompression routine?

The basic Run-length encoding seems too wasteful - I can immediately see that adding a header setion to the compressed data to put to use unused byte values to represent oft repeated patterns would give phenomenal performance!

With me who only invested a few minutes, surely there must already exist much better algorithms from people who love this stuff?

I would like to have some "ready to go" examples to try out on a PC so that I can compare the performance vis-a-vis a basic RLE.

Answer 1

The two solutions I use when performance is the only concern:

• LZO Has a GPL License.
• liblzf Has a BSD License.
• miniLZO.tar.gz This is LZO, just repacked in to a 'minified' version that is better suited to embedded development.

Both are extremely fast when decompressing. I've found that LZO will create slightly smaller compressed data than liblzf in most cases. You'll need to do your own benchmarks for speeds, but I consider them to be "essentially equal". Both are light-years faster than zlib, though neither compresses as well (as you would expect).

LZO, in particular miniLZO, and liblzf are both excellent for embedded targets.