Hello HN!

I'd like to share the project I've been working on for the last couple of months.

On microcontrollers with only a few kilobytes of memory (both Flash and SRAM) heatshrink [1] and tamp [2] are the current meta when it comes to decompression of static assets. They are small, configurable, and produce good compression ratio.

However, when random-access workflows are concerned (like extracting a single parameter from a configuration file), both compressors require the exact same window to be allocated. This means that, to decompress a small (4-32 bytes) chunk, memory consumption stays the same as when decompression the entire payload.

blaris is a Windowless LZSS algorithm, meaning that it is LZSS but does not allocate a window. This allows it to reach the same compression ratio (and sometimes even better) as heatshrink and tamp, while keeping memory usage extremely minimal (around 100 bytes of SRAM).

Typical LZ77/LZSS works by copying a byte from the window buffer when resolving a match. Windowless version works by resolving this match using the compressed payload itself - following the chain of matches until it finds a literal run token.

To facilitate this, tokens are split into 3 streams:

1. controls (1 byte per value) - encode either literal run length (1 to 16) or 240 different pairs (match_len, match_distance_log2).

2. literals (1 byte per value) - raw literals.

3. distance bits (bit-packed) - contains bit-packed match offsets.

Because controls are 1 byte and determine the size of the token, we can traverse all 3 streams in both directions, which enables the windowless LZSS!

There are additional optimizations used to speed this up:

1. checkpoints contain decoder state at each 2^SPREAD_LOG positions, which enables the decoder to jump to the closest checkpoint in constant time.

2. matches' offsets can be forced to align to a power of two, increasing the match range paying the price of unaligned matches.

3. optimal parser on compression side comes up with the best possible representation of the input.

4. chain-flattening can significantly reduce average number of match to match hops while sacrificing just 1-2% of the compression ratio.

When decompressing small slices (4-32 bytes), blaris significantly outperforms both heatshrink and tamp (500x for 1B reads). For bigger slices, since its decompression time depends linearly on the data, blaris performs worse, but it isn't really made for that.

And the best part, it is extremely lightweight in terms of memory. When compiled for RV32IMC architecture, it takes only 548-784 bytes of Flash memory, while using just 104-112B of SRAM regardless of the file size. For comparison, heatshrink is 1300-1464 bytes of Flash and uses 206-16594 bytes of SRAM depending on the window size, and tamp is 2238-3238 bytes of Flash while also using 520-16672 bytes of SRAM.

[1] https://github.com/atomicobject/heatshrink

[2] https://github.com/BrianPugh/tamp

Comments URL: https://news.ycombinator.com/item?id=50499357

Points: 1

# Comments: 0