deniz.in

Markets

Weather

Loading weather

· via Hacker News – Front Page (native)

LZ0: an open-source lossless format with a zero-allocation, ~150-line C decoder

LZ0, a new open-source lossless compression format shown on Hacker News, puts the hard work in the encoder so its C decoder needs no heap allocation and fits in roughly 150 lines.

LZ0: an open-source lossless format with a zero-allocation, ~150-line C decoder

A format designed backwards from the decoder

A project called LZ0, surfaced on the Hacker News front page on 21 November via a Show HN post, is a new open-source lossless compression format with a reference C implementation. Its organising idea, according to the GitHub README, is deliberate asymmetry: the compressor is allowed to be sophisticated and computationally expensive so that the decompressor can be as tiny and simple as possible.

The payoff is a decoder the README describes as roughly 150 lines of C. It performs no dynamic memory allocation, keeps only a few pieces of state — a write position in the output buffer, the most recent match offset (initialised to 1), and a small bit-reader — and works entirely inside buffers supplied by the caller. It processes explicit LZ tokens at hundreds of megabytes per second. LZ0 targets small-to-medium binary blobs and structured data, typically a few hundred kilobytes to a few megabytes, and the README points to bootloaders, microcontrollers, retro hardware and kernel space as natural homes for such a compact decoder.

A token grammar with four operations

The decoder understands just four operations:

  • LiteralRun: copy a run of uncompressed bytes straight from the stream.
  • MatchLast: copy L bytes from the previously used offset.
  • MatchNew: read a new offset, remember it, then copy L bytes from that distance.
  • EOF: end the stream cleanly.

Matches are copied byte by byte, so when a match length exceeds its offset the earlier bytes repeat — an offset of 1 with a length of 8 expands a single byte into an 8-byte run. The README cautions that a standard non-overlapping memcpy is incorrect here.

The raw bitstream carries no magic bytes, header or length metadata. Bits are packed most-significant-bit first, and literal byte payloads plus the low 8 bits of each offset sit in the stream as unaligned raw bytes. Lengths use Elias gamma variable-length integers, while offsets are split into a high part coded with an inverted Elias gamma code and an 8-bit remainder written as a raw byte; the decoder reconstructs the offset as msb times 256 minus that byte. New-offset matches with lengths from 2 to 8 are packed into three fixed bits, with an escape prefix plus a further Elias code for longer runs. Even the stream's first decision bit is omitted, since every stream must begin with a literal run. For storage on disk, the CLI wraps the payload in an 8-byte container header: a four-byte magic string, LZ01, followed by the uncompressed size as a little-endian 32-bit integer.

Positioning between ZX0 and UPKR

The README situates LZ0 in a niche between two existing designs. ZX0 set the benchmark for minimal-decoder LZ compression, pairing a byte-by-byte overlapping-copy decoder with an optimal dynamic-programming parser — but its exhaustive search can take several minutes once inputs exceed about 1 MiB. LZ0 keeps ZX0's decoder simplicity and Elias-based integer coding while replacing the encoder with a faster architecture: hash chains combined with an O(N) SA-IS suffix array and a sparse dynamic-programming parser. The result, per the README, is comparable compression ratios achieved in seconds on 5 MiB inputs instead of minutes.

UPKR takes the opposite trade-off. It couples LZ matching with adaptive rANS/rABS entropy coding to reach higher ratios, but its decoder must maintain probability distributions and update entropy state on every token. LZ0 skips adaptive entropy coding entirely, accepting slightly worse ratios in exchange for a decoder that touches only raw bits, which the README argues minimises branch mispredictions and per-token overhead.

A further design choice is format independence: the bitstream describes only reconstruction instructions, so the encoder can evolve — better search, smarter pruning, new heuristics — without breaking or complicating already-deployed decoders.

Why it matters

Most compression work optimises ratio or throughput on general-purpose hardware. LZ0 instead optimises for the cases where the decompressor itself is the constraint: no heap available, minimal code size, and a routine small enough to audit line by line. That matters for firmware, boot paths and embedded targets, where a ~150-line, zero-allocation decoder is a small bug and security surface and behaves predictably under memory pressure. The encoder-side flexibility also means compression quality can improve over time without touching decoders already shipped in devices. The project is explicitly labelled experimental, and real-world uptake will depend on tooling and independent benchmarks — but as a documented exercise in decoder-first, asymmetric compression design, LZ0 is a clear and interesting data point.

  • #compression
  • #open-source
  • #c
  • #embedded-systems
  • #algorithms

Related posts