Heatshrink: An Embedded Data Compression Library | Hacker News Reader

Heatshrink: An Embedded Data Compression Library

spin.atomicobject.com

Thanks. This is the first library I've seen where compression can be done on the micro. I was looking for something like this to compress recorded data so it would take less time to transfer. Since then I've increased my transfer speeds and I'm not sure I still want to bother with the compression. I worry it'll make it a lot harder to debug and missing blocks of data could become a huge problem.

However, I am putting images in my code space. I was thinking about RLEing them, but I'll see if this works better.

For what it's worth, you can put only the compressor or decompressor on the micro. I'm still working on the documentation.

IME, it works particularly well on bitmapped images and sparse sensor data. Also, it can be faster to incrementally read and unpack compressed data from slow storage (such as flash memory) than to read the whole uncompressed data set. I'm decompressing from flash memory directly into video RAM.

Also, if your window size is greater than 2^8 and you can afford an extra 2 x window_size bytes, the optional indexing greatly increases the compression speed over normal LZSS; the typical linear scan for every byte really hurts as the window gets larger. The index construction is O(N) in the window size for both time and space, which should be doable on many systems.

It doesn't change the fundamental algorithm, just speeds up the compression's pattern detection.

An alternative is LZJB, used in ZFS and CDDL licensed: http://en.wikipedia.org/wiki/LZJB

The code is less than 100 lines for both compressor and decompressor, and it compresses fairly well considering the code size.

It looks like that compresses/decompresses the data in one blocking step, unless I'm missing something. It doesn't handle if (say) the last bit of input ends in the middle of a byte. Does it pad up every compression step output, or do it just assume the whole data set will be resident in memory at once?

heatshrink can suspend and resume, working in small increments. That's particularly important in embedded and hard real-time systems -- they typically can't block for long. Microcontrollers rarely have enough memory to store all the compressed and decompressed data at once.

Most of the work went into co-routining LZSS in little memory, not LZSS itself. LZSS is pretty simple.

I did run across that while doing research for my embedded project and forgot to mention it. (It was one I skipped due to blocking for too long. It's a good implementation otherwise.) I added it to the article.

Yes, it does its work in one go so it doesn't play well with hard realtime and variable sized/large work units (unless you've got an OS that handles task swapping as needed, of course).

We selected it for our embedded devices based on its small code size and suitable license, and since we use it mostly to compress log data with lots of repetitions it works very well.

If you've got an RTOS with pre-emptive threading, you can do blocking (de)compression safely...but then you need extra memory for another thread stack.

It's a good implementation if that isn't an issue, but then there's a couple tiny LZSS/LZW/etc. implementations available.

Reply on news.ycombinator.com