1

I'm looking for a library (or algorithm) with public description and reference source code (in any language with a mainstream compiler targeting 32bit embedded CPUs like Cortex-M0), doing lossless data compression, with (from most to least critical)

  1. A well-defined stream interface supporting synchronous flushing (meaning that decompression of the flushed compressed stream yields the full input stream at time of flush). In this respect, zlib is fine, and Java's DeflaterOutputStream is ideal.
  2. Decompression compatible with an embedded context. Make that max 10kB RAM for data, 30kB code, and no worse than 10 times slower than deflate. Constraining compression for compatibility with the decompression resources is OK. Compression resources are secondary.
  3. State-of-the-art compression ratio including for text payloads like JSON, XML of small size between flushes (0.2 to 20kB). The aforementioned deflate and friends start to show their age here. I have the vague impression ANS-class algorithms have an edge.
  4. Robust decompression code. The last thing I want is that some crafted compressed stream cause unspecified behavior, or worst a vulnerability. Zlib's changelog shows that's not easy. Well-handled exceptions on invalid compressed input are OK.

Suggestions?

Note: the question was originaly asked on SO, and migration here strongly asked.

2

Seems like zlib suits your requirements. The real kicker here is your 10 KB RAM for decompression. That will limit your look back for decompression, which will limit your compression ratio. Modern compression methods, such as xz, rely on a look back of many megabytes in order to achieve their compression ratios.

You can request an 8 KB sliding window (look back) for zlib's deflate, in which case the decompressor will only need 8 KB, plus some small tables, to decompress.

You can use puff, which is in the zlib contrib directory, for a very small footprint decompressor. puff takes about 2.3 times as long to decompress as zlib's inflate, and is about 6KB of code, optimized for speed. Optimized for space, it is 4KB of code, with the speed factor going up to 2.6.

Even zlib's inflate code, at about 24KB, meets your requirement.

You can also look into zstd, which uses ANS. I haven't checked to see if you can specify a window size that small, nor if there is a small footprint decompressor available. There wouldn't be a dramatic increase in compression over zlib, since it wouldn't be allowed to use a larger window.

1
  • zlib was my first choice, and while your recommendation may be a little biased, it's also excellently informed! I had missed puff, it seems a perfect fit for 2, and it's conciseness allows a review towards 4. Your remarks that my small RAM severely limits what I can hope for 3 is also excellent. It damps my hopes of better compression thru ANS or other, all before I spent any time on that! – fgrieu May 28 at 5:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.