nordisk/znippy

The inflate core (linflate) & zero-copy decode output

How znippy decodes DEFLATE — the custom SIMD inflate core and the candidate-offset output model built on top of it. Source: znippy-zoomies/linflate/ (the core; full low-level design in its DESIGN.md), znippy-zoomies/ljar/src/chunk.rs (decode_chunk_into) and znippy-zoomies/ljar/src/bin/ljar.rs (the pipelined binary).

What it is

linflate is a pure-Rust, full-buffer, SIMD-optimized DEFLATE decompressor — the shared decode engine under ljar (JAR), lgz (gzip) and lzip-parallel (ZIP). It follows libdeflate's full-buffer model (no streaming window — the parallel pipelines always hold complete segments in memory) with zlib-ng's branchless tricks. One decode core, three container front-ends.

It grew out of ljar::inflate and was extracted into its own crate; the embedded ljar copy was deleted 2026-06-09 (it had diverged and still carried the refill_slow corruption bug fixed in linflate — see Gotchas). ljar::inflate remains as a re-export of linflate for path compatibility.

Laws (locked — see plan.md)

• Zero-copy in: every decoder takes a borrowed &[u8]; input is never copied into the decoder.
• Caller owns the output: inflate_into(&mut [u8]) / inflate_segment — no per-call allocation in the core. Output buffers must include linflate::OVERWRITE_HEADROOM (SIMD copies may scribble past the written end; regions are sized so neighbours are never harmed).
• Parallel split is always possible via candidate offsets + forward seek (see Output model below) — never a per-segment allocation, never a barrier.

Architecture (the core)

Hot working set ≈ 13 KB — fits L1-D. inflate_segment decodes a slice that need not end on BFINAL=1, which is what makes mid-stream parallel segments (split at Z_FULL_FLUSH boundaries by deflate_scan) independently decodable.

The output model — candidate offsets + forward seek (B6)

Segment output sizes are unknown before decoding, so naive parallel decode allocates one Vec per segment and concatenates. znippy never does that. Instead, both decode paths lay out one pre-allocated buffer:

caps:   [cap_0        ][cap_1        ][cap_2        ]   candidate regions
decode:  ███████        █████          █████████        (parallel, in place)
compact: ███████████████████████                        forward-seek, leftward
         └ true cumulative offsets; set_len(total)

• Each segment gets a candidate offset = prefix sum of generous caps (exact when the output size is known — e.g. a whole entry whose uncompressed size the ZIP central directory states — else sized from the entry's real compressed/uncompressed ratio).
• All segments decode in parallel, in place at their candidate offsets — zero per-segment allocation.
• Forward-seek compaction: walk segments in order, move each down to the true cumulative offset. actual ≤ cap guarantees every move is leftward, so nothing un-moved is ever clobbered.
• A segment that outgrows its cap spills to an owned Vec (rare) and the chunk falls back to a sequential rebuild — never corrupts.
• Buffers recycle through a pool (writer → main), so steady state allocates nothing.

Two implementations of the same model:

1. ljar::chunk::decode_chunk_into — library, rayon fork-join per chunk.
2. ljar binary — the model woven into the no-barrier 5-thread pipeline (Reader → Main → N workers → Collector → Writer): workers inflate_segment straight into their region via raw pointer, the collector compacts when the chunk's last segment lands, the writer returns the buffer to the pool.

Measured (A/B, law 6): 163 840-entry / 10 GB corpus, best-of-5 wall — 7.12 s → 6.70 s and variance 7.1–11.3 s → 6.7–7.4 s (allocator churn eliminated; output byte-identical).

Surfaces

Gotchas

• OVERWRITE_HEADROOM is part of the API contract. Undersized output = OutputOverflow, not UB — but candidate regions must include it so SIMD scribble never crosses into a neighbour.
• refill_slow invariant (fixed 2026-06-09): the slow refill must loop bits < 56, not ≤ 56 — entering with exactly 56 bits pushed the count to 64, and the next fast refill's << bits masked to << 0 on x86 in release: 8 raw bytes OR'd over the whole register, silent tail corruption. Regression test: refill_slow_at_56_bits_keeps_invariant.
• Don't fork the core. The deleted ljar/src/inflate/ copy is the cautionary tale: it diverged and kept the corruption bug while the fix landed in linflate. One core, re-exports for compatibility.