.BZ2 File Format – Compression stages

RLE1: the first run-length coding

Before sorting, every run of 4 or more equal bytes is written as its first 4 bytes and a count byte: how many more copies follow, 0 to 255. So aaaaaaa becomes aaaa and the byte 3, and a run of exactly four still needs its count, 0. bzip2 cuts runs at 255 bytes, so it never writes a count over 251, but every decoder of bzip2 reads 252 to 255 as well, for runs of up to 259 bytes. A run does not continue from one block into the next.

When decoding, the count byte is the byte after any four equal bytes, whatever its value: after it the next byte starts afresh. A block that ends just after four equal bytes, with no count byte, is damaged, and bzip2 stops with a data error.

The stage exists to keep very long runs from slowing the sort; it makes little difference to the size.

The Burrows–Wheeler transform

The block is treated as a ring. All its rotations are sorted, comparing bytes as unsigned numbers and wrapping round at the end, and the transform is the last byte of each sorted rotation, in order. It keeps every byte of the block but groups bytes that are followed by similar text, which the next stages code well. Unlike the textbook transform there is no end-of-text marker; instead the block header stores the origin pointer, the row of the sorted rotations that is the original block. For banana:

The transform of banana is nnbaaa with origin pointer 3, which is what bzip2 1.0.8 writes (the example on the blocks page).

Undoing it. Sorting the last column gives the first column. The k-th c in the first column is the same byte of the ring as the k-th c in the last column, so each row p can be linked to the place in the last column of the byte that starts it. Counting how many bytes of each value the block holds is enough to build those links in one pass. Then, starting from the link of the origin row, output the byte of the last column at the current place and follow that place’s link, once for every byte of the block:

The link of row 3 is 2: output b, go to 5; output a, go to 1; n, 4; a, 0; n, 3; a. The result is banana.

Move-to-front

The list starts as the bytes in use, in ascending order, as the block’s symbol map gives them, afresh for every block. Each byte of the sorted block is written as its position in the list, and then moved to the front. A byte repeated at once is therefore position 0, and the sorted block, being full of repeats, becomes mostly zeros and small numbers. Decoding takes the byte at the position and moves it to the front in the same way.

RLE2: RUNA and RUNB

Every run of zeros from the move-to-front stage, of any length, is written as a number in bijective base 2 with the digits RUNA (1) and RUNB (2), lowest digit first: the i-th digit, counting from 0, is worth its value × 2ⁱ. Every length has exactly one spelling, and the run ends at the first symbol that is not RUNA or RUNB. Other positions p from 1 up are written as the symbol p + 1.

To write a run of n: while n > 0, write RUNA if n is odd and set n to (n − 1) ÷ 2, otherwise write RUNB and set n to (n − 2) ÷ 2. A block can hold at most 900,000 bytes, but bzip2 accepts runs of up to 21 digits, enough for any run.

Huffman coding

The symbols, ending with the end-of-block symbol, are cut into groups of 50. Each group is coded with one of 2 to 6 Huffman tables, named by that group’s selector, so a compressor can keep a table for each kind of stretch in the data. bzip2’s own compressor chooses the tables by refining them over four passes, but any choice of tables and selectors decodes. The tables are sent as code lengths, and the codes follow from the lengths (Huffman codes).

Randomised blocks

bzip2’s early block sorting could take a very long time on highly repetitive data. When sorting a block took too long, bzip2 before 0.9.5 flipped the lowest bit of some of its bytes, at gaps given by a fixed table, sorted it again, and set the block’s randomised bit. bzip2 0.9.5 added a fallback sort that needs no such help, and nothing since has written randomised blocks; decoders still read them.

A decoder undoes it after the inverse Burrows–Wheeler transform and before RLE1, byte by byte, count bytes included. It keeps a counter, which starts at 0, and a place in the table, which starts at 0. For each byte: if the counter is 0, it takes the next number from the table (after the 512th it goes back to the first); it then takes 1 off the counter, and if the counter is now 1 it flips the byte’s lowest bit. So the first bytes flipped are those at 617, 1,337 and 1,464 (counting from 0). The table, as bzip2’s source gives it (BZ2_rNums), sixteen numbers to a line:

619 720 127 481 931 816 813 233 566 247 985 724 205 454 863 491
741 242 949 214 733 859 335 708 621 574  73 654 730 472 419 436
278 496 867 210 399 680 480  51 878 465 811 169 869 675 611 697
867 561 862 687 507 283 482 129 807 591 733 623 150 238  59 379
684 877 625 169 643 105 170 607 520 932 727 476 693 425 174 647
 73 122 335 530 442 853 695 249 445 515 909 545 703 919 874 474
882 500 594 612 641 801 220 162 819 984 589 513 495 799 161 604
958 533 221 400 386 867 600 782 382 596 414 171 516 375 682 485
911 276  98 553 163 354 666 933 424 341 533 870 227 730 475 186
263 647 537 686 600 224 469  68 770 919 190 373 294 822 808 206
184 943 795 384 383 461 404 758 839 887 715  67 618 276 204 918
873 777 604 560 951 160 578 722  79 804  96 409 713 940 652 934
970 447 318 353 859 672 112 785 645 863 803 350 139  93 354  99
820 908 609 772 154 274 580 184  79 626 630 742 653 282 762 623
680  81 927 626 789 125 411 521 938 300 821  78 343 175 128 250
170 774 972 275 999 639 495  78 352 126 857 956 358 619 580 124
737 594 701 612 669 112 134 694 363 992 809 743 168 974 944 375
748  52 600 747 642 182 862  81 344 805 988 739 511 655 814 334
249 515 897 955 664 981 649 113 974 459 893 228 433 837 553 268
926 240 102 654 459  51 686 754 806 760 493 403 415 394 687 700
946 670 656 610 738 392 760 799 887 653 978 321 576 617 626 502
894 679 243 440 680 879 194 572 640 724 926  56 204 700 707 151
457 449 797 195 791 558 945 679 297  59  87 824 713 663 412 693
342 606 134 108 571 364 631 212 174 643 304 329 343  97 430 751
497 314 983 374 822 928 140 206  73 263 980 736 876 478 430 305
170 514 364 692 829  82 855 953 676 246 369 970 294 750 807 827
150 790 288 923 804 378 215 828 592 281 565 555 710  82 896 831
547 261 524 462 293 465 502  56 661 821 976 991 658 869 905 758
745 193 768 550 608 933 378 286 215 979 792 961  61 688 793 644
986 403 106 366 905 644 372 567 466 434 645 210 389 550 919 135
780 773 635 389 707 100 626 958 165 504 920 176 193 713 857 265
203  50 668 108 645 990 626 197 510 357 358 850 858 364 936 638

In the explorer

Show on a block lists every symbol with what it does to the move-to-front list and the runs, then the Burrows–Wheeler step: the sorted block as the symbols spell it, the origin pointer, the block after the inverse transform, and every RLE1 run with its count byte.