# Prior work

- **The format and its checks are libbzip2's** (Julian Seward, bzip2 1.0.8, `decompress.c`). mibz2 follows its decoding rules and makes each of its checks, 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 in Rust, not a port of libbzip2's code. The tests use libbzip2 itself (the `bzip2` crate's bundled 1.0.8) as the oracle.
- **Interleaving several traversals of one BWT inversion** on one thread, so that out-of-order execution keeps their loads in flight, is Kärkkäinen, Kempa and Puglisi's idea: "Slashing the Time for BWT Inversion", DCC 2012, pp. 99–108.

  - They also use a super-alphabet (an LF² table: two characters a dependent lookup) and "Precopy" for repetitive data. Neither is used here: both were built in mibz2 and lost ([why](<https://lmmx.github.io/mibz2/concepts/couriers/#cheaper-steps>)).
  - What is particular here is only how the traversals are found in an existing bzip2 file, which carries no metadata for them: the random starts, the flagged starts that end each segment, and the joining in order.
- **libsais** (Ilya Grebnov), 2.12's cyclic inverse BWT, "as used by bzip2": its `RUN_LANES` store, 16 equal last-column bytes linked at once, is in mibz2's T-vector build. Its chain decode's shared-offset passes are mibz2's walk since 0.1.5 ([\#37](<https://github.com/lmmx/mibz2/pull/37>)).
- **Block-parallel decoding** is lbzip2's (Mikołaj Izdebski) and pbzip2's approach.
- **pbz2** (Soof Golan) arrived independently at a segmented, multi-chain walk too; the bake-off that found it is in the [journals](<https://lmmx.github.io/mibz2/background/journals/index.md>).