# Bzip2

Bzip2 is a general purpose compression format, using Huffman codes, Run Length
Encoding, the Move To Front Transform and the Burrows Wheeler Transform. There
is no official specification, but Joe Tsai has written [comprehensive
documentation](https://github.com/dsnet/compress/raw/master/doc/bzip2-format.pdf)
of the wire format.

It is a block based format, which means that when decoding each block, the
whole compressed block has to be read before a single byte of the uncompressed
block can be written.

Like zlib (but unlike gzip), bzip2 just holds compressed bytes. It does not
hold additional metadata like the original file's name or modification time.


# Wire Format Worked Example

Let's compress "abraca". Bzip2 compresses poorly on such a short input file,
converting 6 uncompressed bytes to 0x2b = 43 compressed bytes. Nonetheless, the
"abraca" uncompressed text matches the example from the 1994 [BWT technical
report](http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-124.pdf) (by M.
Burrows and D. J. Wheeler) that introduced their eponymous Burrows Wheeler
Transform.

    $ hd abraca.txt
    00000000  61 62 72 61 63 61                                 |abraca|
    00000006
    $ hd abraca.txt.bz2
    00000000  42 5a 68 39 31 41 59 26  53 59 76 a7 09 95 00 00  |BZh91AY&SYv.....|
    00000010  00 81 80 38 00 10 00 20  00 21 9a 68 33 4d 30 91  |...8... .!.h3M0.|
    00000020  e2 ee 48 a7 0a 12 0e d4  e1 32 a0                 |..H......2.|
    0000002b

Here are the bits of those 43 bytes with various bitslices labeled from (a) to
(s). The bzip2 file format works in bits instead of bytes. It reads bits from
MSB (Most Significant Bit) to LSB (Least Significant Bit) order and does not
pad to byte boundaries (except at the end of the file).

    offset  xoffset ASCII   hex     binary          bitslice
    000000  0x0000  B       0x42    0b_0100_0010    aaaa_aaaa
    000001  0x0001  Z       0x5A    0b_0101_1010    aaaa_aaaa
    000002  0x0002  h       0x68    0b_0110_1000    bbbb_bbbb
    000003  0x0003  9       0x39    0b_0011_1001    cccc_cccc
    000004  0x0004  1       0x31    0b_0011_0001    dddd_dddd
    000005  0x0005  A       0x41    0b_0100_0001    dddd_dddd
    000006  0x0006  Y       0x59    0b_0101_1001    dddd_dddd
    000007  0x0007  &       0x26    0b_0010_0110    dddd_dddd
    000008  0x0008  S       0x53    0b_0101_0011    dddd_dddd
    000009  0x0009  Y       0x59    0b_0101_1001    dddd_dddd
    000010  0x000A  v       0x76    0b_0111_0110    eeee_eeee
    000011  0x000B  .       0xA7    0b_1010_0111    eeee_eeee
    000012  0x000C  .       0x09    0b_0000_1001    eeee_eeee
    000013  0x000D  .       0x95    0b_1001_0101    eeee_eeee
    000014  0x000E  .       0x00    0b_0000_0000    fggg_gggg
    000015  0x000F  .       0x00    0b_0000_0000    gggg_gggg
    000016  0x0010  .       0x00    0b_0000_0000    gggg_gggg
    000017  0x0011  .       0x81    0b_1000_0001    ghhh_hhhh    popcount(h) = 2
    000018  0x0012  .       0x80    0b_1000_0000    hhhh_hhhh
    000019  0x0013  8       0x38    0b_0011_1000    hiii_iiii    popcount(i) = 3
    000020  0x0014  .       0x00    0b_0000_0000    iiii_iiii
    000021  0x0015  .       0x10    0b_0001_0000    ijjj_jjjj    popcount(j) = 1
    000022  0x0016  .       0x00    0b_0000_0000    jjjj_jjjj
    000023  0x0017          0x20    0b_0010_0000    jkkk_llll
    000024  0x0018  .       0x00    0b_0000_0000    llll_llll
    000025  0x0019  !       0x21    0b_0010_0001    lllm_nnnn
    000026  0x001A  .       0x9A    0b_1001_1010    nnnn_nnnn
    000027  0x001B  h       0x68    0b_0110_1000    nnnn_nnno
    000028  0x001C  3       0x33    0b_0011_0011    oooo_oooo
    000029  0x001D  M       0x4D    0b_0100_1101    oooo_oooo
    000030  0x001E  0       0x30    0b_0011_0000    oopp_pppp
    000031  0x001F  .       0x91    0b_1001_0001    pppp_pppp
    000032  0x0020  .       0xE2    0b_1110_0010    pppq_qqqq
    000033  0x0021  .       0xEE    0b_1110_1110    qqqq_qqqq
    000034  0x0022  H       0x48    0b_0100_1000    qqqq_qqqq
    000035  0x0023  .       0xA7    0b_1010_0111    qqqq_qqqq
    000036  0x0024  .       0x0A    0b_0000_1010    qqqq_qqqq
    000037  0x0025  .       0x12    0b_0001_0010    qqqq_qqqq
    000038  0x0026  .       0x0E    0b_0000_1110    qqqr_rrrr
    000039  0x0027  .       0xD4    0b_1101_0100    rrrr_rrrr
    000040  0x0028  .       0xE1    0b_1110_0001    rrrr_rrrr
    000041  0x0029  2       0x32    0b_0011_0010    rrrr_rrrr
    000042  0x002A  .       0xA0    0b_1010_0000    rrrs_ssss

(a) A 16-bit magic number "BZ" meaning the start of the bzip2 file.

(b) The 'h' byte means Huffman compression. The original bzip (as in, without
the "2" in "bzip2") used a '0' byte here to indicate arithmetic codes instead
of Huffman codes, but arithmetic/bzip was not widely used because of patent
concerns. This package (and worked example) only considers Huffman/bzip2.

(c) The '9' byte means the uncompressed block size ranges up to 900000
(inclusive).

(d) A 48-bit magic number 0x314159265359 (a homage to π) means the start of a
block.

(e) A 32-bit checksum. Refer to section 2.2.3.1 "BlockHeader" of [Tsai's
document](https://github.com/dsnet/compress/raw/master/doc/bzip2-format.pdf)
which notes, "It is the same [CRC-32] checksum used in GZip (RFC 1952, section
8), but is slightly different due to the bit-packing differences noted in
section 2.1".

(f) A "block randomized" bit, deprecated and not used here.

(g) The 24-bit index of the original string in the sorted list of BWT
rotations. The [BWT technical
report](http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-124.pdf) calls this
number *I*. In this case, the value is 0x000001.

(h) A 16-bit bitmap of which byte values are present in the uncompressed text.
In this case, `0b_0000_0011_0000_0000` means that there are values in the 7th
and 8th rows (with 16 bytes per row). Its popcount (population count, the
number of set bits) is 2, which means there are 2 further 16-bit bitmaps
immediately following.

(i) The 16-bit bitmap for the 7th row in (h). `0b_0111_0000_0000_0000` means
that the `0x61`, `0x62` and `0x63` bytes (ASCII 'a', 'b' and 'c') are present.

(j) The 16-bit bitmap for the 8th row in (h). `0b_0010_0000_0000_0000` means
that the `0x72` byte (ASCII 'r') is present.

(k) The 3-bit number of Huffman codes. In this case, `0b_010 = 2`, the minimum
valid value.

(l) The 15-bit number of sections. Each section is 50 symbols. Each symbol
either produces one byte of uncompressed data (roughly speaking) or are one of
three special symbols: RUNA, RUNB (both Run Length Encoding related) or EOB
(End Of Block). The selected Huffman code can change at section boundaries.

(m) The array of unary encoded Huffman code selectors (one for each section).
In this case, an array of one element, [0]. Applying the MTFT (Move To Front
Transform) produces the same values: [0]. This part of `abraca.txt.bz2` isn't
very enlightening but there's a more interesting example in the "MTFT Reprised"
section below.

(n) The first Huffman code. More details below.

(o) The second Huffman code. For `abraca.txt.bz2`, the second Huffman code is
never referenced by the selectors in the (m) bitslice but, for the record, the
(o) bitslice is identical to the (n) bitslice and therefore produces the same
Huffman code.

(p) The bitstream to feed the Huffman codes. More details below.

(q) A 48-bit magic number 0x177245385090 (a homage to sqrt(π)) means no further
blocks.

(r) A 32-bit checksum. Refer to section 2.2.4 "StreamFooter" of [Tsai's
document](https://github.com/dsnet/compress/raw/master/doc/bzip2-format.pdf).

(s) Padding up to a byte boundary.


## Huffman Codes

The (h), (i) and (j) bitslices collectively state that there are 4 byte values
present in the uncompressed output: 'a', 'b', 'c' and 'r'. The relevant MTFT
uses 1 fewer symbols (m01, m02 and m03) than this count, since an m00 operation
(see below) is redundant with the RUNA and RUNB symbols. Adding the 3 special
symbols (RUNA, RUNB, EOB) means that each Huffman code covers 6 symbols.

Here's the (n) bitslice again:

    offset  xoffset ASCII   hex     binary          bitslice
    000025  0x0019  !       0x21    0b_0010_0001    lllm_nnnn
    000026  0x001A  .       0x9A    0b_1001_1010    nnnn_nnnn
    000027  0x001B  h       0x68    0b_0110_1000    nnnn_nnno

Its bits are "0001100110100110100". Adding spaces gives "00011 0 0 11 0 10 0 11
0 10 0", which represents the sequence [3+0, +0, -1+0, +1+0, -1+0, +1+0].
Adding up the deltas gives the code lengths [3, 3, 2, 3, 2, 3] and so the
[canonical Huffman code](https://en.wikipedia.org/wiki/Canonical_Huffman_code)
(with RUNA and RUNB before the mNN symbols and EOB after) is:

    code  length  symbol
    100   3       RUNA
    101   3       RUNB
    00    2       m01
    110   3       m02
    01    2       m03
    111   3       EOB

Here's the (p) bitslice again.

    offset  xoffset ASCII   hex     binary          bitslice
    000030  0x001E  0       0x30    0b_0011_0000    oopp_pppp
    000031  0x001F  .       0x91    0b_1001_0001    pppp_pppp
    000032  0x0020  .       0xE2    0b_1110_0010    pppq_qqqq

Its bits are "11000010010001111". Adding spaces, giving "110 00 01 00 100 01
111", makes it clearer that applying the Huffman code from the (n) bitslice to
the (p) bitslice produces the symbol sequence [m02, m01, m03, m01, RUNA, m03,
EOB].


## Move To Front Transform

MTFT operates on a byte array (let's call it the "order" buffer) that's
initialized with with the bytes-in-use in their natural order: ['a', 'b', 'c',
'r']. Each mNN symbol emits the N'th element (using 0-based indexing) and also
rearranges the order buffer: moving that element to the start and pushing the N
earlier symbols one to the right.

There is no explicit m00 symbol. Instead, a combination of RUNA and RUNB
symbols produce a number R meaning to repeat the 0th element R times (and leave
the order buffer unchanged). For the `abraca.txt.bz2` example, we have one RUNA
symbol but no RUNB symbols, which is effectively an m00 repeated once. Here's
the production:

    order  symbol  emission
    abcr   m02     c
    cabr   m01     a
    acbr   m03     r
    racb   m01     a
    arcb   RUNA    a
    arcb   m03     b
    barc   EOB

Tsai calls this RUNA / RUNB mechanism RLE2 (and goes into further detail on
their semantics) and calls a later Run Length Encoding mechanism RLE1. Later
when decoding, but when encoding, RLE1 occurs before RLE2.


## Burrows Wheeler Transform

Reading down the emission column gives "caraab", which the [BWT technical
report](http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-124.pdf) calls *L*,
the last column of the sorted list of permutations of the uncompressed text. We
can compute its histogram ('a' occurs 3 times, 'b', 'c' and 'r' all occur 1
time) in a first pass over *L*, and thus the cumulative counts:

    Byte  Cumulative
    a     0
    b     3
    c     4
    r     5

We then compute *T* in a second pass over *L*, by assigning an incrementing
value (relative to each cumulative count) to all the 'a' elements in *L*
(assigning 0, 1 and 2), all the 'b' elements (assigning 3), all the 'c'
elements (assinging 4) and all the 'r' elements (assigning 5).

    Index  L  T
    0      c  4
    1      a  0
    2      r  5
    3      a  1
    4      a  2
    5      b  3

Starting with the *I* value given in the (g) bitslice, which was 1, calculate
*I*, *T[I]*, *T[T[I]]*, *T[T[T[I]]]*, etc to give [1, 0, 4, 2, 5, 3]. Indexing
*L* with these values gives "acarba" and reversing that gives "abraca", the
uncompressed text.


## Alternative BWT Inversion

It's not in the BWT technical report, but instead of walking *I*, *T[I]*,
*T[T[I]]*, etc, an alternative but equivalent algorithm works on *U*, the
inverse of the *T* vector. For example *T[4] == 2* and so *U[2] == 4*.

    Index  L  T  F  U
    0      c  4  a  1
    1      a  0  a  3
    2      r  5  a  4
    3      a  1  b  5
    4      a  2  c  0
    5      b  3  r  2

Calculate *U[I]*, *U[U[I]]*, *U[U[U[I]]]*, etc to give [3, 5, 2, 4, 0, 1].
Indexing *L* with these values gives "abraca", the uncompressed text (without
being reversed).


## Final Run Length Encoding

It's not used in `abraca.txt.bz2` but after BWT inversion, there's a final Run
Length Encoding step (which Tsai calls RLE1), separate from the RUNA and RUNB
ops mentioned above. It's triggered by four consecutive identical bytes and
when decoding, converts strings like "AAAA\x03BBBB\x00CCCD" to
"AAAAAAABBBBCCCD".


# Another Example

Here's a larger file, 942 bytes uncompressed and 568 bytes bzip2-compressed.

    $ cat romeo.txt     | head
    Romeo and Juliet
    Excerpt from Act 2, Scene 2
    
    JULIET
    O Romeo, Romeo! wherefore art thou Romeo?
    Deny thy father and refuse thy name;
    Or, if thou wilt not, be but sworn my love,
    And I'll no longer be a Capulet.
    
    ROMEO
    $ hd  romeo.txt.bz2 | head
    00000000  42 5a 68 39 31 41 59 26  53 59 f8 7d 63 30 00 00  |BZh91AY&SY.}c0..|
    00000010  8c 5f 80 00 10 60 85 10  18 be 77 9e 8a 3f ef df  |._...`....w..?..|
    00000020  f0 40 02 30 e3 bb 00 22  9e a0 68 01 a1 a0 00 00  |.@.0..."..h.....|
    00000030  00 02 26 13 23 4d 21 20  6d 41 a0 d0 d0 d0 f2 80  |..&.#M! mA......|
    00000040  2a 9e f5 4f 50 f5 46 4c  23 13 09 89 82 60 4c 09  |*..OP.FL#....`L.|
    00000050  84 89 1a 9a 05 31 92 27  92 6c 88 68 7a 23 26 83  |.....1.'.l.hz#&.|
    00000060  4a b3 4b 3a 06 9b ec c7  19 bc 9a 88 60 6a 6b 42  |J.K:........`jkB|
    00000070  5a c6 8e ad c7 c3 8f a8  f0 91 d1 db e3 1b 25 b5  |Z.............%.|
    00000080  4e 06 cd f3 08 a9 af e8  82 2d 5b 54 fc 35 a9 0e  |N........-[T.5..|
    00000090  13 01 17 7b 4c 98 47 24  25 d9 bd aa cd 31 da ee  |...{L.G$%....1..|

Where `abraca.txt.bz2` had 3 + 1 = 4 possible uncompressed bytes ('a', 'b', 'c'
and 'r'), `romeo.txt.bz2` has 1 + 5 + 4 + 12 + 7 + 14 + 10 = 53. This is
represented in the wire format by the (h), (i) and (j) bitslices for
`abraca.txt.bz2` and the 8 equivalent bitslices in `romeo.txt.bz2` (where we
have repeatedly alternated the (i) and (j) bitslice labels).

    offset  xoffset ASCII   hex     binary          bitslice
    000017  0x0011  _       0x5F    0b_0101_1111    ghhh_hhhh    popcount(h) =  7
    000018  0x0012  .       0x80    0b_1000_0000    hhhh_hhhh
    000019  0x0013  .       0x00    0b_0000_0000    hiii_iiii    popcount(i) =  1
    000020  0x0014  .       0x10    0b_0001_0000    iiii_iiii
    000021  0x0015  `       0x60    0b_0110_0000    ijjj_jjjj    popcount(j) =  5
    000022  0x0016  .       0x85    0b_1000_0101    jjjj_jjjj
    000023  0x0017  .       0x10    0b_0001_0000    jiii_iiii    popcount(i) =  4
    000024  0x0018  .       0x18    0b_0001_1000    iiii_iiii
    000025  0x0019  .       0xBE    0b_1011_1110    ijjj_jjjj    popcount(j) = 12
    000026  0x001A  w       0x77    0b_0111_0111    jjjj_jjjj
    000027  0x001B  .       0x9E    0b_1001_1110    jiii_iiii    popcount(i) =  7
    000028  0x001C  .       0x8A    0b_1000_1010    iiii_iiii
    000029  0x001D  ?       0x3F    0b_0011_1111    ijjj_jjjj    popcount(j) = 14
    000030  0x001E  .       0xEF    0b_1110_1111    jjjj_jjjj
    000031  0x001F  .       0xDF    0b_1101_1111    jiii_iiii    popcount(i) = 10
    000032  0x0020  .       0xF0    0b_1111_0000    iiii_iiii
    000033  0x0021  @       0x40    0b_0100_0000    ikkk_llll

Similarly, where `abraca.txt.bz2` had 1 section (per the (l) bitslice), each
selecting from 2 possible Huffman codes (per the (k) bitslice), `romeo.txt.bz2`
has 17 sections, each selecting from 4 possible Huffman codes.

    offset  xoffset ASCII   hex     binary          bitslice
    000033  0x0021  @       0x40    0b_0100_0000    ikkk_llll
    000034  0x0022  .       0x02    0b_0000_0010    llll_llll
    000035  0x0023  0       0x30    0b_0011_0000    lllm_mmmm


## MTFT Reprised

Bzip2 uses the [Move To Front
Transform](https://en.wikipedia.org/wiki/Move-to-front_transform) in two
places:

1. for the selectors array encoded in the (m) bitslice and
2. for the conversion from the symbols (the Huffman code's output) to
   generating the *L* string.

Use 2 is discussed above but the Use 1 values for `abraca.txt.bz2` is not very
educational, since the (m) bitslice was literally only one bit long. For
`romeo.txt.bz2`, the equivalent (m) bitslice is 29 bits long and makes for a
more interesting example.

    offset  xoffset ASCII   hex     binary          bitslice
    000035  0x0023  0       0x30    0b_0011_0000    lllm_mmmm
    000036  0x0024  .       0xE3    0b_1110_0011    mmmm_mmmm
    000037  0x0025  .       0xBB    0b_1011_1011    mmmm_mmmm
    000038  0x0026  .       0x00    0b_0000_0000    mmmm_mmmm

The bits are "10000111000111011101100000000" which is the unary encoding of the
17-element selector array (before applying the MTFT): [1, 0, 0, 0, 3, 0, 0, 3,
3, 2, 0, 0, 0, 0, 0, 0, 0].

If we label the 4 Huffman codes to select from as w, x, y and z then the MTFT
converts those 17 elements to "xxxxzzzywzzzzzzzz", per the table below. As
before, each N value (pre-MTFT) emits the N'th element (using 0-based indexing)
and also rearranges the order buffer: moving that element to the start and
pushing the N earlier symbols one to the right.

    order  pre  post
    wxyz   1    x
    xwyz   0    x
    xwyz   0    x
    xwyz   0    x
    xwyz   3    z
    zxwy   0    z
    zxwy   0    z
    zxwy   3    y
    yzxw   3    w
    wyzx   2    z
    zwyx   0    z
    zwyx   0    z
    zwyx   0    z
    zwyx   0    z
    zwyx   0    z
    zwyx   0    z
    zwyx   0    z


# Even More Examples

Appendix A of [Tsai's
document](https://github.com/dsnet/compress/raw/master/doc/bzip2-format.pdf)
gives even more wire format worked examples, presented in great detail.