logoalt Hacker News

seb3773 • last Thursday at 7:11 PM • 0 replies • view on HN

I built LZ0, an asymmetric LZ compressor targeting environments where decompression resources are tightly constrained (bootloaders, microcontrollers, embedded asset loading) or where decoder simplicity matters most. I've always admired micro-decoders like Einar Saukas' ZX0—zero dynamic allocation, no scratch RAM, and small enough to fit into a handful of instructions. The catch with traditional optimal parsers is that they often scale in O(N^2), taking tens of seconds or minutes once files exceed a few hundred kilobytes. I wrote LZ0 to keep that same decoder footprint while compressing multi-megabyte files in milliseconds.

Where it sits (Ratio vs. Speed): - Compression density: beats LZ4/Snappy, staying within 1–3% of zlib/Deflate and exhaustive ZX0. - Decompression speed: 200–350 MB/s for portable C, 250–700 MB/s for compact ASM, and 520–1,330 MB/s for vector ASM. That's up to 10x faster than Deflate while requiring zero heap memory or state tables. - Compression throughput: ~1.3–1.6 s on typical 1 MB inputs.

How the encoder avoids the O(N^2) wall (H2C8 pipeline): - Multi-tier match finding: dual-level hash chains for local matches paired with an O(N) SA-IS suffix array for deep, long-range matches. - Sparse DP parsing: instead of evaluating every edge in the graph, it groups Elias gamma bit costs into mathematical plateaus to skip redundant searches.

The repo ships with three 0-alloc decoder implementations: 1. Portable C (`lz0dec_min.c`): ~75 lines of freestanding C with zero libc dependencies. 2. Compact ASM: hand-written x86-64 and ARM64 routines (~1.3 KiB of machine code), with zero state or lookup tables. 3. High-throughput "FAST" ASM: dual-engine vector path (SSE2 on x86-64, NEON on ARM64) using branch-free Elias gamma decoding and segment-window refills.

All decoders enforce strict bounds checks and have been validated against 240,000+ guard-page and fuzzing tests to ensure corrupt streams never trigger out-of-bounds reads or crashes.

Bitstream specification: https://github.com/seb3773/lz0/blob/main/docs/LZ0_FORMAT.md Benchmarks: https://github.com/seb3773/lz0/blob/main/docs/BENCHMARKS.md

I'd appreciate any feedback on the bitstream layout, the decoder tradeoffs, or edge cases I might have missed.