# The inflate core (linflate) & zero-copy decode output
<!-- nornir:class: reasoning -->
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/linflate/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](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)
| file | role |
|------|------|
| `linflate/src/bitreader.rs` | 64-bit shift register, **branchless refill** (4 insns, `bits \|= 56`), ≥56 bits after refill — one refill per symbol |
| `linflate/src/tables.rs` | packed-u32 Huffman entries, 11-bit litlen first-level table (~no subtable hits on real streams), thread-local table pool |
| `linflate/src/fixed.rs` | pre-built static fixed-Huffman tables |
| `linflate/src/copy.rs` | const-generic `<N>` SIMD match copy (LLVM emits `vmovdqu`), short-distance tiling |
| `linflate/src/fastloop.rs` | the hot loop — preload-before-copy, 3-literal unroll, `#[cold]` slow paths |
| `linflate/src/lib.rs` | API: `inflate_into`, `inflate_segment[_with_prefix[_limited]]`, `inflate_to_vec`, `OVERWRITE_HEADROOM` |
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:
```text
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
| surface | what |
|---------|------|
| `linflate::inflate_to_vec(data, expected)` | convenience, pre-sized exact when `expected` is known |
| `linflate::inflate_into / inflate_segment*` | zero-copy, caller-owned output |
| `ljar::chunk::{decode_chunk, decode_chunk_into}` | parallel chunk decode (owned / zero-copy) |
| `cargo bench -p ljar` | criterion: `inflate`, `table_build`, `flush_scan`, `vs_miniz`, `chunk_into` (B6 A/B) |
| `nornir bench run znippy` → `linflate_guava` / `linflate_scala` | **the scorecard**: linflate vs miniz_oxide single-stream decode (paired `*_mbs` + `speedup_x`, README-rendered) |
## 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.