This page follows Joe Tsai’s
bzip2
format description and bzip2’s own source (decompress.c,
compress.c, bzlib_private.h and CHANGES from
sourceware.org), read
2026-11-12.
A block holds up to 100,000 × level bytes of data, sorted and coded on its own, so any block can be decoded without the others. It starts at any bit: nothing inside a block is aligned to a byte. Bits are read from the most significant bit of each byte down, and a field of several bits is read most significant bit first. The fields below follow one another with no gaps. How the data was transformed before it was coded is on the compression stages page; the stream around the blocks is on the streams page.
Block header
| Bits | Field | Meaning |
|---|---|---|
| 48 | Block magic | 31 41 59 26 53 59: the first digits of π in binary-coded decimal. It tells a block from the end of the stream, whose magic is 17 72 45 38 50 90. |
| 32 | Block CRC | The CRC of the bytes this block decompresses to (see CRCs). |
| 1 | Randomised | 1: the block was randomised before sorting, which bzip2 before 0.9.5 did to very repetitive data. bzip2 has not written it since, and still reads it. |
| 24 | Origin pointer | The row of the sorted rotations that holds the original block: where the inverse Burrows–Wheeler transform starts. It must be less than the number of bytes in the sorted block. |
Symbol map
Which of the 256 byte values the block holds, in two levels, so that a block of text needs few bits for it:
| Bits | Field | Meaning |
|---|---|---|
| 16 | Rows in use | Bit i (counting from the most significant, 0 to 15) is set when any byte from i × 16 to i × 16 + 15 is in use. |
| 16 for each row in use | Row | For each set bit above, in order: bit j set means the byte i × 16 + j is in use. |
The bytes in use, in ascending order, make the starting move-to-front list, and their number n sets the size of the symbol alphabet. At least one byte must be in use. A byte may be marked in use and never appear; decoders accept that.
Table and selector counts
| Bits | Field | Meaning |
|---|---|---|
| 3 | Tables | The number of Huffman tables, 2 to 6. A table that no selector names is allowed. |
| 15 | Selectors | The number of selectors, 1 to 32,767: one for each group of 50 symbols. |
bzip2’s own compressor picks the number of tables from the number of symbols it has to code: 2 below 200, 3 below 600, 4 below 1,200, 5 below 2,400 and 6 from there on. Other compressors may choose differently.
Selectors
Each selector names the table that codes the next 50 symbols. The selectors are sent
through a move-to-front list of the tables, which starts as 0, 1, 2 … in order: each
selector is its table’s position in that list, written in unary as that many 1 bits
and a 0 (0, 10, 110 … up to five 1 bits), and
the table then moves to the front of the list. A position that is not less than the
number of tables is an error.
A block of 900,000 bytes needs at most 18,002 selectors (900,000 ÷ 50, and two more). bzip2 1.0.8 reads a larger count but keeps only the first 18,002 selectors; bzip2 1.0.7 added a range check on the count for CVE-2019-12900 and refused such files, and 1.0.8 relaxed it again. Selectors left over after the end of block are ignored, but running out of selectors before the end of block is an error.
Code lengths
Then each table in turn, as the code length of every symbol of the alphabet (n + 2 symbols, see below):
| Bits | Field | Meaning |
|---|---|---|
| 5 | Starting length | The current length, before the first symbol. |
| 2 each, repeated | 10 or 11 | 10 makes the current length one longer, 11 one shorter. |
| 1 | 0 | The current length is this symbol’s length; go on to the next symbol. |
The current length must stay from 1 to 20 whenever it is checked, which is before
each step: a starting length of 0, or a step to 0 or 21, is an error. Steps need not
be the fewest possible (10 11 10 0 means the same as 10 0),
though bzip2 never writes more than it needs. bzip2’s own compressor keeps its codes to
17 bits.
Huffman codes
The codes follow from the lengths alone, as in Deflate: shorter codes come first, and codes of the same length go in symbol order. Starting from 0 at the shortest length, each symbol of that length takes the next value; moving to the next length doubles the value. Codes are read most significant bit first, a bit at a time, until they match.
A proper set of lengths is complete: the sum of 2−length over all symbols is exactly 1. bzip2 does not check this. Its decoder builds limit and base tables from the lengths and reads whatever bit patterns those tables accept; a pattern that leads to no symbol, or a code longer than 20 bits, is an error. Some other compressors have written incomplete tables, so a decoder that must read every file bzip2 reads has to build its tables the same way.
Symbols
With n bytes in use, the alphabet has n + 2 symbols:
| Symbol | Name | Meaning |
|---|---|---|
| 0 | RUNA | A digit worth 1 × w in a run of the byte at the front of the move-to-front list |
| 1 | RUNB | A digit worth 2 × w in such a run |
| 2 to n | Move-to-front position | Symbol s is the byte at position s − 1 of the list, which then moves to the front |
| n + 1 | End of block | The last symbol of the block |
The weight w starts at 1 for the first digit of a run and doubles with each digit, so a run’s length is written in bijective base 2, lowest digit first (table of runs). Position 0 of the list never appears as a symbol of its own: it is always part of a run.
Symbols are read in groups of 50, each group with the table its selector names, until the end-of-block symbol. The block ends straight after that symbol’s last bit, and the next block or the end of the stream follows at the very next bit.
What bzip2 turns down
bzip2 1.0.8 stops with a data error, and the explorer does too, when a block has:
- an origin pointer greater than 100,000 × level + 10, or not less than the number of bytes the symbols make;
- no bytes in use in its symbol map;
- fewer than 2 or more than 6 tables, or no selectors;
- a selector that names a table past the last;
- a code length outside 1 to 20;
- a Huffman code longer than 20 bits, or one that leads to no symbol;
- more groups of 50 symbols than selectors;
- a run of more than 21 RUNA and RUNB digits (the 22nd would have a weight of 221);
- more bytes than 100,000 × level in the sorted block;
- four equal bytes at the end of the block with no count byte after them (see RLE1);
- a CRC that does not match the data.
Example
The six bytes banana, compressed by bzip2 1.0.8 at level 9, make a file of
39 bytes with one block, which starts at bit 32, straight after the
BZh9 header:
| Bit | Bits | Field | Value |
|---|---|---|---|
| 32 | 48 | Block magic | 31 41 59 26 53 59 |
| 80 | 32 | Block CRC | EFB6EC01 |
| 112 | 1 | Randomised | 0 |
| 113 | 24 | Origin pointer | 3 |
| 137 | 16 | Rows in use | 0000001000000000: row 6 only (bytes 60 to 6F) |
| 153 | 16 | Row 6 | 0110000000000010: a, b and n, so n = 3 and there are 5 symbols |
| 169 | 3 | Tables | 2 |
| 172 | 15 | Selectors | 1 |
| 187 | 2 | Selector 0 | 10: position 1 of the list 0, 1, so table 1 (the second) |
| 189 | 12 | Table 0 | 00011 0 0 110 0 0: start 3; lengths 3, 3, 2, 2, 2 (not used) |
| 201 | 18 | Table 1 | 00011 0 0 0 11110 10100: start 3; lengths 3, 3, 3, 1, 3, so the codes are 100, 101, 110, 0, 111 |
| 219 | 12 | Symbols | 0 100 0 0 101 111: 3, RUNA, 3, 3, RUNB, end of block |
| 231 | End of stream | the end-of-stream magic follows |
Decoding the symbols with the list a b n: 3 is position 2, n
(list n a b); RUNA is a run of one more n; 3 is
b (list b n a); 3 is a (list
a b n); RUNB is a run of two more a. The sorted block is
nnbaaa, and the inverse transform from row 3 gives
banana (worked through on the
compression stages page).
In the explorer
Drop a .bz2 file on this site: every block is in the structure tree, with
each field above as a node, and Show opens the block’s fields, symbol map, selectors,
code lengths as sent with the codes they make, every symbol with its bits and meaning,
the Burrows–Wheeler step and the RLE1 runs.