libbzip2-rs: moving bzip2 to safe Rust, one byte at a time

The library you already trust, in a language it wasn’t written in

You depend on bzip2 somewhere. It’s in your package manager, your kernel’s initramfs tooling, half the scientific data formats you’ve ever tar’d. It is thirty years of Julian Seward’s C, and it is load-bearing — which is exactly why “just rewrite it in Rust” is a scarier sentence than it sounds.

The memory-safety mandate is real and it is correct: C’s undefined behavior is a liability, and moving critical codecs to a memory-safe language removes a whole class of exploit. But there are two ways a port can go wrong, and both look fine at first:

1. It transliterates. You run the C through a mechanical converter and get Rust that is technically Rust and spiritually C — *mut u8 everywhere, unsafe blocks wrapping pointer arithmetic, a libc dependency. It compiles. It is not safer.
2. It drifts. You rewrite it idiomatically, it passes your round-trip test on a few files, you ship it — and six months later someone feeds it a low-memory-mode stream and gets a byte wrong on decompress. The bug was there on day one; your test corpus just never hit the path.

The interesting work is avoiding both at once: idiomatic, unsafe-free Rust that is provably the same program. This is a study of one such port — libbzip2-rs — and of where the real difficulty lives.

What “drop-in” has to mean

A drop-in replacement that produces even one different byte is not a drop-in replacement; it is a fork with a marketing problem. So the bar is unforgiving and it is the only bar worth holding: byte-for-byte identical output to the C reference, everywhere you can observe it from the outside.

That is a claim you should never be asked to take on faith, so the repo ships the way to check it. make check runs a differential: the same inputs go through both the original bzip2 1.0.8 and the Rust port, and every byte of every output is compared.

$ make check
PASS: Rust port byte-identical to bzip2 1.0.8 over 265 commands
      (compress + decompress, small=0 and small=1, valid + malformed streams; 0 unsafe)

The corpus is not “a few files.” It is designed to hit the paths that actually diverge:

Dimension	Why it’s in the corpus
Compress and decompress	A port can round-trip correctly while producing a different compressed stream. Both directions are checked against C.
small=0 and small=1	bzip2 has two entirely different decompress implementations — a fast one and a low-memory one. The second is where drift hides.
Every block-size (-1 … -9)	Block size changes the sort and the Huffman tables; the humps live at the boundaries.
Valid and malformed streams	Rejecting bad input the same way C does is half the spec, and the half everyone skips.
Empty, single-byte, highly-repetitive	Run-length and BWT edge cases — the inputs that break naive implementations.

265 commands is not a large number. It is a sufficient number, chosen so each one exercises a path the others don’t — and because it’s public and re-runnable, it’s a floor you can raise. More on that at the end.

The interesting part: inverting the Burrows–Wheeler transform

bzip2’s heart is the Burrows–Wheeler transform. Compression sorts rotations of the block so similar contexts cluster; decompression has to invert that sort exactly. Get the inverse wrong by one index and you don’t get “slightly wrong output” — you get garbage from that point forward, because every subsequent symbol is chained off the last.

Here is the shape of the inverse in C (from decompress.c, simplified):

/* Reconstruct the original block by walking the transform vector.
   tt[] holds, in its high 24 bits, the index of the next symbol;
   the low 8 bits carry the byte itself. One walk = one output block. */
tPos = tt[tPos] >> 8;
for (i = 0; i < nblock; i++) {
    UChar b = (UChar)(tt[tPos] & 0xff);
    tPos    = tt[tPos] >> 8;
    emit(b);
}

The idiomatic Rust is recognizably the same walk, but the indexing is checked and the buffer is owned rather than pointed at:

// tt: Vec<u32> — high 24 bits = next index, low 8 = the byte.
let mut t_pos = tt[t_pos as usize] >> 8;
for _ in 0..nblock {
    let b = (tt[t_pos as usize] & 0xff) as u8;
    t_pos = tt[t_pos as usize] >> 8;
    out.push(b);
}

Nothing surprising — in fast mode. The trap is small=1.

The low-memory path is a second implementation, not a flag

When you pass -s (or the library’s small decompress), bzip2 doesn’t just use less memory with the same code — it runs a different inverse-BWT that trades roughly half the RAM for more arithmetic, reconstructing the cumulative-frequency table (cftab) and computing indices on the fly instead of storing the full tt[] links. It is its own code path with its own opportunities to be subtly wrong.

This is the single most useful thing a byte-level differential buys you: the fast path (small=0) can pass every test you’d think to write by hand, while the low-memory path drops a bit on a specific class of block — and you would never know, because your round-trip test defaulted to small=0. The corpus runs both modes over the same inputs and diffs them independently. The place a hand-review would sign off is exactly the place the harness refuses to.

That’s the pattern worth internalizing: the bug is never where the happy path is. It’s in the second implementation of the same thing, behind a flag most tests don’t set.

Malformed input is half the spec

A decompressor’s contract is not “decode valid streams.” It is “decode valid streams and reject invalid ones, predictably.” bzip2 has a well-known history here — the selector run-length reading in getAndMoveToFrontDecode is the site of the long-since-fixed CVE-2019-12900, where a stream declaring more selectors than the table can hold walked off the end of an array.

Reading the selector table looks like this in C:

nSelectors = getBits(15);
for (i = 0; i < nSelectors; i++) {
    j = 0;
    while (getBit()) j++;      /* unary MTF value */
    selectorMtf[i] = j;        /* <-- i, j both need bounds the format doesn't guarantee */
}

In #![forbid(unsafe_code)] Rust, the same logic cannot become a memory-safety bug. An index past the end of a Vec is a bounds check and a clean panic-or-error, not a write into adjacent memory:

let n_selectors = get_bits(15)?;
for i in 0..n_selectors {
    let mut j = 0u32;
    while get_bit()? { j += 1; }
    // selector_mtf[i] — indexing is checked; an out-of-range i can't corrupt anything.
    *selector_mtf.get_mut(i).ok_or(BzError::DataError)? = j;
}

The point of the study is not “Rust prevents the CVE” — that’s table stakes for any safe language. The point is that the differential asserts something stronger: the port rejects the same malformed inputs the C rejects, and accepts the same valid ones. Safety that changed the accept/reject boundary would be a different program. The malformed half of the corpus exists to nail that boundary in place.

The safety is enforced by the compiler, not promised in a README

The crate root carries #![forbid(unsafe_code)]. This is not a style choice; it is a compile error waiting for anyone — including a future maintainer, including a well-meaning optimization — who tries to reach for a raw pointer. The guarantee is checked by rustc on every build, not asserted in prose.

That guarantee has a price, and honesty about the price is the whole point of a study. To satisfy forbid(unsafe), this port owns its buffers — Vec<u8>, Vec<u32> — rather than viewing the caller’s memory through aliased pointers the way the C does. For the codec that is completely fine: it round-trips byte-identically, and it’s genuinely idiomatic Rust.

But “owns its buffers” is a design decision, not a free lunch, and it’s precisely the decision the rest of this series interrogates. A C caller that hands bzip2 a buffer and expects the library to work through that allocation, with that aliasing, is relying on a memory-layout contract this port quietly relaxes. It looks like bzip2 in every way you can test from the outside — and whether “looks identical from the outside” is the same as “is the drop-in you’d actually ask for” is the thread the next studies pull. This one earns the safe, byte-identical baseline. Naming what it traded to get there is how you read the ones that follow.

Grunt work vs. craft

Here is the thesis, stated plainly. Everything above splits cleanly into two kinds of work.

The grunt work is mechanical, exhausting, and unbounded: generate a corpus that hits every mode and every edge; run both implementations over all of it; diff every byte; when a byte differs, bisect the path down to the one function and the one line where the bit was lost. It is not hard in the sense of requiring insight. It is hard in the sense that it is enormous, and it is the exact work that burns out the senior engineers you can least afford to lose — the ones who could be doing something better.

The craft is the part that actually wants a human: the ownership model (what borrows, what owns, what the API hands back), the idiom, the shape of the public interface, and the performance fine-tuning near the hot loops. Judgment work. Taste work.

The argument this whole project makes is that you should automate the grunt work so the grunt work stops taxing the talent. The machine grinds the equivalence proof over 265 commands and localizes the divergence; the engineer reviews the ownership decisions and tunes the idiom. You get memory safety without the maintenance tax of a team now owning a pile of code in a language its veterans don’t write — because the tedious, mechanical majority of the port didn’t come out of their week.

That is a claim about where effort should go, not a claim that the machine has taste. It doesn’t. The corpus does the grinding; a person still has to decide what “right” means.

Honest limits

A study without a limits section is a brochure. Here is what this port is not:

• Byte-identical is over the tested envelope, not a proof. 265 commands is a strong, re-runnable floor — it is not a formal verification. A metamorphic or property-based extension is the honest next rung, and the corpus is structured to grow toward it.
• Performance is near-C, not “faster than C.” The goal here was equivalence and safety, not a speed claim. Owning buffers and checked indexing have a cost; where it lands relative to C is its own study, not this one.
• It relaxes the allocation/aliasing contract. As above — it owns memory instead of honoring the caller’s. Correct for a codec, a real question for a true drop-in, and the subject of what comes next.
• The corpus is finite by construction. That’s a feature, not a hedge: it’s finite so that you can re-run it, and public so that you can extend it. A floor you can raise beats a ceiling you have to trust.

For allies, and for critics

If you build compression tooling, the most useful thing you can do with this is try to break it. Clone it, run make check, then throw your own inputs at the differential — your weird streams, your corrupted archives, your pathological block sizes. If you find an input where the Rust port and C disagree by a single byte, that is the most valuable bug report you could send, and the harness is built to make it reproducible.

And if you want the reference standard for what a Rust bzip2 looks like when careful humans build it end to end, read the Trifecta Tech Foundation’s libbzip2-rs. This port is laid out module-for-module against it on purpose — so you can put decompress.rs next to decompress.rs next to the original decompress.c and see three answers to the same question side by side. Their work is the target this points toward, not competes with.

The next study takes the uncomfortable step: what happens when “byte-identical from the outside” and “honors the caller’s contract” stop being the same thing — and the bug turns out to be coming from inside the house.

---

Diff it, run it, break it: github.com/Kaizen-3C/libbzip2-rs. Found a divergence, or want a codec studied this way? contact@kaizen-3c.dev.