lbunzip2 — reasoning
Class:
reasoning· Function:lbunzip2. Why bzip2 is the easy member of the family and why the shape is what it is. Shipped shape inlbunzip2-design.md.
Why bzip2 saturates where gzip cannot
bzip2's format hands us the independence gzip's does not. Every bzip2 block is a self-contained BWT unit: it starts at the 48-bit magic, carries its own Huffman tables, its own MTF state, its own CRC — nothing crosses a block boundary. So a 1 GB .bz2 is ~1000+ genuinely independent decode units, and the per-block work (inverse-BWT is the expensive part) dwarfs everything else. There is no LZ77 window threading the whole stream the way DEFLATE has, so no full-flush trickery is needed and no serial fallback exists. bzip2 is the format the gatling shape was made for.
The only non-embarrassingly-parallel cost is finding the blocks — the magic sits at an arbitrary bit offset, so you must bit-scan. That scan is cheap (a 64-bit sliding window, ~32 bytes/cycle) and is itself fanned across cores (split_boundaries_parallel, lbzip2/src/block_scan.rs:279), with a 73-bit quick_verify_block header check to reject coincidental magic patterns without a full decode. So even the "serial prefix" is parallel.
Why streaming instead of scan-whole-then-decode
The CLI reads 8 MB chunks and streams segments through run_ordered_sink rather than mmapping the whole file and decoding every block at once. Reason: bounded memory. A 1 GB .bz2 expands to ~10 GB; holding it all resident is a peak-RSS wound. The permit-bounded ordered sink keeps only cap decoded segments alive at any instant, so resident memory is O(cap × segment) regardless of file size, while the producer's I/O overlaps the workers' decode. The in-memory ParallelBz2Read variant exists for the cases where you do have the bytes and want the whole thing — see lbzip2-readers-reasoning.md.
Why the CRC check is fatal, not lenient
decode_segment_checked exits non-zero on a per-block CRC-32 mismatch (lbunzip2.rs:270). A decompressor that silently emits truncated output on corruption is a security hole (the finding that motivated it): downstream consumers would treat a tampered stream as valid. bzip2's per-block CRC is authoritative and cheap, so we honor it hard.
Why we still lose to C lbzip2 (honest)
The README caption reads straight: we crush serial bzip2 ~10×, but the mature C lbzip2 still edges us on raw bzip2 throughput. The gap is in the inner block decode (hand-tuned C inverse-BWT / MTF), not in the parallel structure — our fan-out is already near-flat. That is a codec-microoptimization gap, recorded honestly rather than hidden. Numbers land in the README.md mashup on the heavy-bench wave.