Crate mibz2 

A bzip2 decoder built for memory-level parallelism: block-parallel like lbzip2, and within a block, its inverse BWT walked as 12 interleaved chains, so a core keeps a dozen of the walk’s cache-missing loads in flight instead of one. Byte for byte libbzip2’s output, every block’s and stream’s CRC checked, on any x86-64 or aarch64 CPU: its SIMD kernels (AVX2, PCLMULQDQ) are chosen at run time, each with a portable scalar twin. No dependencies beyond std.

Use

use std::io::Read;
// a whole .bz2 in memory, on this thread, or on 4 threads
let data = std::fs::read("file.bz2")?;
let text = mibz2::decode(&data)?;
let same = mibz2::decode_parallel(&data, 4)?;
// any `Read`, as a `Read`: on this thread, or block-parallel
let mut out = Vec::new();
mibz2::BzReader::parallel(std::fs::File::open("file.bz2")?, 4).read_to_end(&mut out)?;
// the blocks without decoding them, then any range of whole blocks, on any thread
for span in mibz2::scan(&data) {
    let span = span?;
    let mut part = Vec::new();
    mibz2::decode_blocks(&data, span.start_bit, span.end_bit, span.level, mibz2::Kernels::detect(), &mut part)?;
}

• decode, decode_parallel: a whole .bz2 (its streams one after another);
• BzReader: a Read adaptor, sequential or parallel (BzReader::parallel);
• StreamDecoder: the push form (write compressed bytes from one thread, read decoded bytes from another), with an explicit thread count and in-flight bound;
• scan and decode_blocks: a .bz2’s block boundaries, then ranges of whole blocks decoded independently (a caller’s own parallelism);
• Error and ErrorKind: what is wrong with the input, and where (block, bit);
• Kernels: the SIMD kernels, detected or forced scalar;
• bwt::InverseBwt: the inverse-BWT kernel, swappable.

How a block is decoded

1. its header and Huffman-coded symbols (block), the one sequential part: a block’s end is known only once its symbols are read, so one thread reads them in order;
2. RUNA/RUNB and move-to-front (mtf; AVX2 for the move);
3. the T-vector, by a counting sort (bwt::build);
4. the inverse BWT’s walk, as 12 interleaved chains joined in order (bwt::walk_segments: the walk is bound by a load’s latency, not by bandwidth); phases 3 and 4 sit behind bwt::InverseBwt;
5. RLE1 undone (rle; AVX2) and the block’s CRC (crc; PCLMULQDQ), checked against the CRC the block stores.

In parallel, phases 2-5 run on worker threads, a block each (parallel), and the blocks come out in order. Each stream’s combined CRC is checked at its end.

Prior work

• The format and its checks are libbzip2’s (Julian Seward; bzip2 1.0.8, decompress.c): this decoder follows its decoding rules and makes every check it makes, in its terms (its Huffman decode tables are built as BZ2_hbCreateDecodeTables builds them), so a stream libbzip2 refuses is refused here too. It is a separate implementation, not a port of its code.
• Interleaved traversals of one BWT inversion on one thread are Kärkkäinen, Kempa and Puglisi’s: “Slashing the Time for BWT Inversion”, DCC 2012, pp. 99-108 (who add a two-characters-per-lookup table and “Precopy”, not used here). What is particular here is only finding the traversals in an existing bzip2 file, which carries no metadata for them: pseudo-random segment starts, a bitmap to stop each segment, and the segments joined in order.
• Block parallelism is lbzip2’s (Mikolaj Izdebski) and pbzip2’s idea.

Choices

The format is libbzip2 1.0.8’s, with these choices, each its own error:

• randomised blocks (written only by bzip2 0.9.0 and earlier) are refused;
• bytes after the last stream that do not begin another stream are an error (lbzip2 and bzip2 ignore them), so nothing after a stream is ever silently dropped;
• an oversubscribed Huffman code whose code points past the alphabet (where libbzip2 reads a stale table entry) is an error;
• a block whose compressed form passes 64 MiB is an error (a real block is at most about 4.2 MB; only a code-length table padded with no-op steps could be longer).

Re-exports

pub use parallel::StreamDecoder;

Modules

bits

An MSB-first bit reader over a byte slice. Past the slice’s end it reads zeros, and says it has (overran): the caller then either has more input to give it (and starts the item again) or the stream is truncated. So the decoder’s loops never index past the input, and an item cut short by the input’s end is never taken as whole.

block

A block’s header and its Huffman-coded symbols, read in order from the stream: the one part of the decode that must be sequential, since a block’s end is known only once its symbols are decoded. Every check libbzip2 1.0.8 makes here (decompress.c) is made the same way, in the same terms, so a stream libbzip2 refuses is refused here too.

bwt

Phases 3 and 4: the inverse BWT. The T-vector (lbzip2’s packing: a row’s byte in bits 0-7, the next row above) is built by a counting sort, then walked from the primary index. The walk is a chain of dependent loads through 3.6 MB, so it is bound by the load’s latency, not by bandwidth (docs/journal/2026-10-27-compute-frontier.md, section 2). walk_segments walks it as K chains at once (memory-level parallelism within one block) and joins them: exactly the plain walk’s output, in about half its time.

crc

CRC-32/BZIP2 (polynomial 0x04C11DB7, MSB first, initial value and final xor all ones), the block CRC bzip2 stores: sliced by 8 (portable), or by carry-less multiplication (PCLMULQDQ with SSE4.1, dispatched at run time, see Kernels).

mtf

Phase 2: RUNA/RUNB runs and move-to-front undone, into the BWT’s last column (ll) and its byte counts, with libbzip2’s checks: a run’s weight below 2^21, and the block no longer than its stream’s level allows. The scalar loop, or (AVX2) the move of an index below 32, nearly all of them, as one blend of the list and the list a byte on.

parallel

The block-parallel streaming decoder: compressed bytes written in (StreamDecoder::write, from any thread, blocking while the input queued is full), decoded bytes read out in order (StreamDecoder::read). Like lbzip2’s, its parallelism is across blocks:

rle

Phase 5’s RLE1 undone: 4 equal bytes, then a byte counting 0-255 more of them. Scalar, or (AVX2) the test for 4 equal bytes made at 32 positions at once, the stretches between runs copied whole.

stream

The sequential part of the decode: a .bz2’s streams read in order, each block’s header and symbols (block.rs), each stream’s header and end, its combined CRC checked. The input comes from a Source: a slice, or chunks arriving on a channel (parallel.rs), held only from the block being read on.

Structs

BlockSpan

A block of a .bz2, as scan finds it

BzReader

A .bz2 stream (or several, one after another) read from R, decoded.

Error

An error, and where: the block (counted from the input’s first, across its streams) and the bit of the input it starts at

Kernels

The SIMD kernels to use, detected once at run time (or forced to the scalar ones)

Range

What decode_blocks read: each block’s bit range and CRC, and where it stopped

Scan

Scratch

A worker’s buffers, kept from block to block (about 7 MB at the 900 kB block size)

Enums

ErrorKind

What is wrong with the input

Functions

combine

A stream’s combined CRC from its blocks’ CRCs, in order

decode

A whole .bz2 (its streams one after another) decoded on this thread, every block’s and stream’s CRC checked, with the fastest kernels this CPU has

decode_block

Phases 2-5 of a block whose symbols are read: its bytes appended to out, its CRC checked. Returns the CRC.

decode_blocks

The blocks of data from start_bit (a block header’s first bit) to end_bit (the next block’s first bit, or a stream end marker’s), in a stream of level (1-9), appended to out, each block’s CRC checked; a range that meets its stream’s end marker stops there. For a reader that finds block boundaries itself and decodes ranges of blocks in parallel (the sweep reader’s block-aligned segments, which today take lbzip2 -n1 each): it can combine the returned CRCs (combine) to check its stream’s.

decode_parallel

A whole .bz2 decoded on threads worker threads (at least 1), a block each, in order

decode_with

decode with the kernels k and the inverse-BWT kernel I (bwt::Segmented, the default; bwt::Plain, the plain walk, to test or time it against)

scan

The blocks of a .bz2 in memory, found by reading each block’s header and Huffman symbols (about a tenth of a decode’s work; no block is decoded further, so no block CRC is checked here, but each stream’s combined CRC is checked against its blocks’ stored CRCs). Each span can then be decoded by decode_blocks, on any thread.