Expand description
A Rust port of the Heatshrink compression library for embedded/real-time systems.
§How it works
Heatshrink is based on LZSS.
It recognizes repeated byte sequences in data and encodes them as backreferences to the original sequence.
A backreference consists of an index and length. The index is a negative offset from the current position in the data that can go as far back as 2^window.
The length can be any value in the inclusive range [1, 2^lookahead].
While a backreference of length 1 or 2 could technically be constructed, it would waste space (sizeof(index) + sizeof(length) > sizeof(single byte)).
Instead, Heatshrink encodes these smaller sequences of data as literals; the raw data is emitted.
To indicate whether data is a backreference or literal, the encoder includes a 1-bit identifer flag: 0 for a backreference, 1 for a literal.
§Encoder
The encoder buffers up incoming data internally to try and generate backreferences in the available window of data. The search for backreferences is the most computationally intensive operation. There is an indexing optimization that speeds it up, but it uses more memory.
§Decoder
The decoder immediately yields literals as they are received and maintains a circular buffer of the last 2^window bytes for handling backreferences.
There aren’t really any computationally intensive operations performed.
§Raw Format
encoded_data = [entry]*
entry = [tag_bit][tag_data]
if tag_bit == [0] then tag_data = [index][len] (backreference)
if tag_bit == [1] then tag_data = [byte] (literal)
index = window-bits number
len = lookahead-bits number
byte = 8-bit number§Credits
Scott Vokes is the author of the original C library. His blog post goes into more detail on the origins and performance.