4 ms·

Heatshrink: An Embedded Data Compression Library

68 points by silentbicycle 14y ago

FigBug 14y ago
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.
- silentbicycle 14y ago
  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.
- silentbicycle 14y ago
  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.
m_eiman 14y ago
An alternative is LZJB, used in ZFS and CDDL licensed: http://en.wikipedia.org/wiki/LZJB 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.
- silentbicycle 14y ago
  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.
  - m_eiman 14y ago
    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.
    - silentbicycle 14y ago
      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.

68 points by silentbicycle 14y ago

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.

silentbicycle 14y ago
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.
silentbicycle 14y ago
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.

m_eiman 14y ago

An alternative is LZJB, used in ZFS and CDDL licensed: http://en.wikipedia.org/wiki/LZJB 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.

silentbicycle 14y ago
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.
- m_eiman 14y ago
  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.
  - silentbicycle 14y ago
    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.