4 ms·

Heatshrink: Data compression library for embedded/real-time systems

67 points by zdw 5y ago

jtchang 5y ago
I wonder how this compares to xz or lzo. Is the main draw the fact that it runs in really low memory?
- wolf550e 5y ago
  I think it's like LZO or LZ4 but with tiny window, so the compression is not great.
  - deleted 5y ago
    [deleted]
- MobiusHorizons 5y ago
  There is a blog post linked at the bottom of the readme that has some more interesting numbers. https://spin.atomicobject.com/2013/03/14/heatshrink-embedded-data-compression/ https://spin.atomicobject.com/2013/03/14/heatshrink-embedded...
- lifthrasiir 5y ago
  The linked blog post [1] contains a benchmark against the Canterbury Corpus [2]. It is hard to test against other compressors because of its very low memory requirement, but LZO1X-1(11) (`lzo1x -11` in LZBench [3]) comes close as both LZO1X-1(11) and HS 13,4 targets 8 KB of work memory. The result (higher is better): HS 13,4 LZO1X-1(11) sample 54.90% 38.02% alice29.txt 50.51% 34.00% asyoulik.txt 57.63% 49.38% cp.html 64.68% 56.97% fields.c 56.87% 51.03% grammar.lsp 71.65% 64.12% kennedy.xls 56.53% 40.33% lcet10.txt 48.57% 29.41% plrabn12.txt 77.74% 82.91% ptt5 47.76% 40.64% xargs.1 64.10% 54.90% total (note: doesn't include `sum`) It does seem to have a good compression compared with LZO1X. I think this is mostly because LZO1X has a requirement that literals should be aligned at byte boundary for the performance but Heatshrink doesn't. [1] https://spin.atomicobject.com/2013/03/14/heatshrink-embedded-data-compression/ https://spin.atomicobject.com/2013/03/14/heatshrink-embedded... [2] https://corpus.canterbury.ac.nz/ https://corpus.canterbury.ac.nz/ [3] https://morotti.github.io/lzbench-web/ https://morotti.github.io/lzbench-web/
eurg 5y ago
Once did a prototype that had to work with a really memory poor device. Compression and speed is meh, but still worth it (small serial interfaces are no racing dogs either). Also very simple to understand and port and play around with, and to compare with other algorithms. More or less took this project as an excuse to learn some compression basics. Can recommend
- malux85 5y ago
  I’m curious about embedded and constrained environments, do you mind telling us a bit more? What was the project? What hardware was involved? What tooling and OS’s did you use? What were the most challenging technical problems? Really just curious :)
  - roland35 5y ago
    Not the OP, but check out devices like Microchip's PIC (8 bits) or AVR (8 bits), or ARM Cortex M0 or Cortex M3/4 devices. On cheaper devices you can get down to a few kB of RAM and Flash memory, so you need to be mindful of what you use! When working with embedded devices like that, the main thing is you can't just easily import libraries or use many layers of abstraction (limited stack depth too). So generally everything is done at a low level.
  - eurg 5y ago
    > What were the most challenging technical problems? While technically the customer asked for the solution to problem A, they wanted us to solve problem B, but we failed to invoke our inner patio11, and as a result delivered what they said instead of what they meant. A frustrating lesson for me. At that point in my career I should have known better already. ETA: sibling comment about Cortex-M0 is spot on. You really start counting bytes. Some kiB of RAM sound a lot, but when you have to juggle several tasks, and don't have to option to write from scratch but instead reuse existing old code you've lying around, stuff gets dirty pretty quickly. Other team member was doing the hard work, I was just providing tooling for them.
    - BenjiWiebe 5y ago
unwind 5y ago
This seems really nice, very ambitious to do it as a "public" state machine that you sink data into and poll compressed bytes out. I can imagine that makes it really nice if you're trying to decompress something in a real-time environment, to cap the execution time. Cool. Another related algorithm is LZJB, which I've successfully used in embedded environments in production. I have a pure Python implementation [1] that can be useful for "offline" tool development, i.e. when building images for consumption by some embedded target, just thought I'd mention that. [1]: https://github.com/unwind/python-lzjb https://github.com/unwind/python-lzjb
vbezhenar 5y ago
What would be a good approach to compress not just a steam of arbitrary bytes, but a stream of 4-byte numbers which are similar to each other (like some sensor output)?
- nitrogen 5y ago
  You could start by encoding the deltas using variable length encoding, so a 0 delta could be as little as 1 bit. But anything off-the-shelf should be able to compress this type of data well.
- formerly_proven 5y ago
  Look into time-series compression. Delta-encoding, mentioned by sibling, is a very old but effective technique also known as differential PCM. You can also delta-encode delta-encoded values, which works especially well for values whose delta is constant (classic example: timestamped data). The advantage of these over general purpose compressors is that they require basically no resources to implement. TFA is "low memory usage (as low as 50 bytes)", but delta encoding needs just one register.
rurban 5y ago
I used tiny lz4 variants in one of my embedded projects, but using delta decoding of known default values is much better beforehand. Will look at that encoder also
huntik17 5y ago
I ported a tool 'detools' which generates binary patches and compresses them using heatshrink to ESP32 and got some great results! Use case: Compressed Delta OTA Updates for ESP32 ESP32 port: https://github.com/ESP32-Musings/esp32_compressed_delta_ota_update https://github.com/ESP32-Musings/esp32_compressed_delta_ota_... detools: https://github.com/eerimoq/detools https://github.com/eerimoq/detools
beeforpork 5y ago
> #define NO_BITS ((uint16_t)-1) Haha! :-)

67 points by zdw 5y ago

jtchang 5y ago

I wonder how this compares to xz or lzo. Is the main draw the fact that it runs in really low memory?

wolf550e 5y ago
I think it's like LZO or LZ4 but with tiny window, so the compression is not great.
- deleted 5y ago
  [deleted]
MobiusHorizons 5y ago
There is a blog post linked at the bottom of the readme that has some more interesting numbers. https://spin.atomicobject.com/2013/03/14/heatshrink-embedded-data-compression/ https://spin.atomicobject.com/2013/03/14/heatshrink-embedded...
lifthrasiir 5y ago
The linked blog post [1] contains a benchmark against the Canterbury Corpus [2]. It is hard to test against other compressors because of its very low memory requirement, but LZO1X-1(11) (`lzo1x -11` in LZBench [3]) comes close as both LZO1X-1(11) and HS 13,4 targets 8 KB of work memory. The result (higher is better): HS 13,4 LZO1X-1(11) sample 54.90% 38.02% alice29.txt 50.51% 34.00% asyoulik.txt 57.63% 49.38% cp.html 64.68% 56.97% fields.c 56.87% 51.03% grammar.lsp 71.65% 64.12% kennedy.xls 56.53% 40.33% lcet10.txt 48.57% 29.41% plrabn12.txt 77.74% 82.91% ptt5 47.76% 40.64% xargs.1 64.10% 54.90% total (note: doesn't include `sum`) It does seem to have a good compression compared with LZO1X. I think this is mostly because LZO1X has a requirement that literals should be aligned at byte boundary for the performance but Heatshrink doesn't. [1] https://spin.atomicobject.com/2013/03/14/heatshrink-embedded-data-compression/ https://spin.atomicobject.com/2013/03/14/heatshrink-embedded... [2] https://corpus.canterbury.ac.nz/ https://corpus.canterbury.ac.nz/ [3] https://morotti.github.io/lzbench-web/ https://morotti.github.io/lzbench-web/

eurg 5y ago

Once did a prototype that had to work with a really memory poor device. Compression and speed is meh, but still worth it (small serial interfaces are no racing dogs either). Also very simple to understand and port and play around with, and to compare with other algorithms. More or less took this project as an excuse to learn some compression basics. Can recommend

malux85 5y ago
I’m curious about embedded and constrained environments, do you mind telling us a bit more? What was the project? What hardware was involved? What tooling and OS’s did you use? What were the most challenging technical problems? Really just curious :)
- roland35 5y ago
  Not the OP, but check out devices like Microchip's PIC (8 bits) or AVR (8 bits), or ARM Cortex M0 or Cortex M3/4 devices. On cheaper devices you can get down to a few kB of RAM and Flash memory, so you need to be mindful of what you use! When working with embedded devices like that, the main thing is you can't just easily import libraries or use many layers of abstraction (limited stack depth too). So generally everything is done at a low level.
- eurg 5y ago
  > What were the most challenging technical problems? While technically the customer asked for the solution to problem A, they wanted us to solve problem B, but we failed to invoke our inner patio11, and as a result delivered what they said instead of what they meant. A frustrating lesson for me. At that point in my career I should have known better already. ETA: sibling comment about Cortex-M0 is spot on. You really start counting bytes. Some kiB of RAM sound a lot, but when you have to juggle several tasks, and don't have to option to write from scratch but instead reuse existing old code you've lying around, stuff gets dirty pretty quickly. Other team member was doing the hard work, I was just providing tooling for them.
  - BenjiWiebe 5y ago

unwind 5y ago

This seems really nice, very ambitious to do it as a "public" state machine that you sink data into and poll compressed bytes out. I can imagine that makes it really nice if you're trying to decompress something in a real-time environment, to cap the execution time. Cool. Another related algorithm is LZJB, which I've successfully used in embedded environments in production. I have a pure Python implementation [1] that can be useful for "offline" tool development, i.e. when building images for consumption by some embedded target, just thought I'd mention that. [1]: https://github.com/unwind/python-lzjb https://github.com/unwind/python-lzjb

vbezhenar 5y ago

What would be a good approach to compress not just a steam of arbitrary bytes, but a stream of 4-byte numbers which are similar to each other (like some sensor output)?

nitrogen 5y ago
You could start by encoding the deltas using variable length encoding, so a 0 delta could be as little as 1 bit. But anything off-the-shelf should be able to compress this type of data well.
formerly_proven 5y ago
Look into time-series compression. Delta-encoding, mentioned by sibling, is a very old but effective technique also known as differential PCM. You can also delta-encode delta-encoded values, which works especially well for values whose delta is constant (classic example: timestamped data). The advantage of these over general purpose compressors is that they require basically no resources to implement. TFA is "low memory usage (as low as 50 bytes)", but delta encoding needs just one register.

rurban 5y ago

I used tiny lz4 variants in one of my embedded projects, but using delta decoding of known default values is much better beforehand. Will look at that encoder also

huntik17 5y ago

I ported a tool 'detools' which generates binary patches and compresses them using heatshrink to ESP32 and got some great results! Use case: Compressed Delta OTA Updates for ESP32 ESP32 port: https://github.com/ESP32-Musings/esp32_compressed_delta_ota_update https://github.com/ESP32-Musings/esp32_compressed_delta_ota_... detools: https://github.com/eerimoq/detools https://github.com/eerimoq/detools

beeforpork 5y ago

> #define NO_BITS ((uint16_t)-1) Haha! :-)