Compact decompression library for embedded use

Question

We're currently creating a device for a customer that will get a block of data (like, say, 5-10KB) from a PC application. This is a bit simplified, so assume that the data must be passed and uncompressed a lot, not just once a year. The communication channel is really, really slow, so we'd like to compress the data beforehand, pass to the device and let it uncompress the data to its internal flash. The device itself, however, runs on a micro controller that is not really fast and does not have a lot of memory. It has enough flash memory to store the result, and can uncompress the data block as it is received, but it may not have enough RAM to store the entire compressed or uncompressed (or even both!) data blocks. And of course, it doesn't have an operating system or other luxury.

This means we need a sufficiently fast uncompression algorithm that does not use a lot of memory. The compression can be slow and ugly, since we're doing it on the PC side. C or .NET code preferred though for compression, to make things easier. The uncompression code should be in C, since it's unlikely that someone has an ASM optimized version for our controller.

We found LZO, which would be almost perfect for us, but it has a so-called "free" license (GPL) by default, which makes it totally unusable for our customer. The author says that commercial licenses are available on request, but unfortunately he's currently unreachable (for non-technical reasons, like the news on his site say).

I found a few other libraries, including the puff.c from zlib, and we're still investigating, but I thought I'd ask for your experience:

Which compression algorithm and/or library do you recommend for embedded purposes, given that the decompression device has really limited resources and source code and a commercial license are required?

Answer 1

You might want to check out one of these which are not GPL and are fairly compact implementations:

• fastlz - MIT license, fairly simple code
• lzjb - sun CDDL, used in zfs for compression, simple and very short
• liblzf - BSD-style license, small, fast
• lzfx - BSD-style, based on liblzf, small, fast

Those algorithms are all based on the original algorithm of Lempel–Ziv–Welch (They have all LZ in common) https://en.wikipedia.org/wiki/Lempel–Ziv–Welch

Answer 2

I have used LZSS. I used code from Haruhiko Okumura as base. It uses the last portion of uncompressed data(2K) as dictionary. This code can be modified to not require a temporary ring buffer if you have no memory. The licensing is not clear from his site but some versions was released with a "Use, distribute, and modify this program freely" line included and the code is used by commercial vendors.

Here is an implementation based on the same code that forms part of the Allegro game library. Allegro licensing is giftware or zlib.

Another option could be the lzfx lib that implement LZF. I have not used it yet but it seems nice. Also uses previous results so it has low memory requirements and is released under a BSD Licence.