13 Comments

heatshrink: An Embedded Data Compression Library

DIY TiVo IR Blaster

In embedded systems, space is always tight. Adding pennies of extra storage can be enough to kill a budget (when multiplied by hundreds of thousands or even millions of units), so available space has to be used effectively.

For my current project, I need to fit a lot of data into 16 MB of flash: a backup of the firmware, 9 MB (!) of graphical assets (including bitmapped Chinese fonts with over 30,000 characters), and other configuration data for the unit. On top of this, I need space for a second version of everything during updates. There’s no way this could fit as-is.

While data compression has obvious benefits for embedded systems, I was surprised by the lack of suitable libraries. While there are well-known open-source libraries such as zlib, I found none that could work in my resource-constrained environment. Existing options were too large for my program ROM (zlib), GPL’d (lzo), required too much working memory (zlib, again), required an actual filesystem, or hijacked control flow by blocking and doing everything at once (lzjb).

heatshrink for Embedded Data Compression

I decided to write my own, heatshrink. It’s released under a BSD license, it can run in very small amounts of memory (under 50 bytes for practical decompression), and it can work in small increments while addressing the other needs of a hard real-time system. (For my project, it reduces the graphical assets from 9 MB to about 6.5 MB, so everything can fit.)

The Basics

I chose to base it on LZSS because it needs little working space beyond a cache of the last 2^N bytes of data (where N is configurable), and decompression is quite simple. The interface is also pretty simple: dump data in, keep turning the crank until no more data comes out, dump more in, repeat. Notify the encoder/decoder when the end of input is reached, and keep cranking until it’s finished. It can suspend on individual bit I/O boundaries as necessary, so by adjusting buffer sizes, work can be done in configurably-brief intervals.

Size Requirements

Its buffer size parameter allows an explicit trade-off between compression effectiveness and working memory. Beyond the space used for IO buffering (and it can work a single byte at a time, if necessary), its space requirements are modest:

Encoding:

16 + 2 * 2^N bytes, plus more for an optional search index (currently an additional 2 * 2^N bytes) to speed up encoding.

Decoding:

16 + 2^N bytes to decode, where N matches the setting used when encoding.

Results

It also compares reasonably to libraries such as zlib/gzip. For example, here are the results for the Canterbury Corpus, a set of documents used to compare effectiveness of compression algorithms.

gzip HS 13,4 HS 11,4 HS 8,4 HS 6,3 HS 5,3
Memory Used > 128 KB 8,208 B 2,064
B
272 B 80 B 48 B
Document
alice29.txt 64.2 % 54.90 % 48.02 % 26.50 % 5.82 % -2.79 %
asyoulik.txt 60.9 % 50.51 % 44.23 % 24.87 % 5.63 % -3.34 %
cp.html 67.6 % 57.63 % 52.03 % 35.67 % -2.26 % -4.68 %
fields.c 72.1 % 64.68 % 63.36 % 49.52 % 26.65 % 10.98 %
grammar.lsp 67.5 % 56.87 % 59.61 % 52.43 % 32.71 % 14.92 %
kennedy.xls 79.9 % 71.65 % 73.10 % 74.57 % 68.89 % 69.96 %
lcet10.txt 66.1 % 56.53 % 48.55 % 25.40 % 5.21 % -2.13 %
plrabn12.txt 59.5 % 48.57 % 41.37 % 21.65 % 6.00 % -5.61 %
ptt5 89.0 % 77.74 % 78.79 % 79.16 % 70.84 % 71.88 %
xargs.1 59.3 % 47.76 % 48.76 % 30.42 % 11.00 % 1.70 %
everything 73.8 % 64.40 % 61.91 % 53.23 % 41.27 % 37.71 %

“HS 11,4″ means heatshrink was run with a window size of 2^11 and a lookahead of 2^4 bits (command line arguments of “-w 11 -l 4″), and the percentages represent size reduction (more is better). HS 8,4 is a reasonable default for embedded systems. If more memory is available, a larger window size allows better compression, but even in a severely constrained environment, HS 5,3 is still effective on certain kinds of data (such as bitmapped images or sparse sensor data). The memory used to decompress does not include the decoder’s input buffer size, but that can be as small as 1 byte.

When compiled for an Arduino microcontroller by avr-gcc, the decoder only needs about 1 KB of program ROM space. (I’m working on getting it smaller, and this will vary from platform to platform. On my project’s hardware platform, it’s under 800 bytes.)

You can download heatshrink at our github page.