Описание алгоритма BZIP2

Потребовалась мне для одного проекта реализация распаковщика BZIP2. Как оказалось, описание этого формата фактически отсутствует. Особенно в русском переводе. Единственное, что мне помогало в работе — очень куцее описание в английской Википедии и исходники.

BZIP2 появился в середине 90х годов и сейчас является вторым по популярности алгоритмом для "стандартной" компрессии после Deflate. Разумеется, оба эти алгоритма очень сильно проигрывают сложным и мощным вроде методов из архиваторов RAR, 7z или UHARC, но они полностью открыты и требуют относительно небольших ресурсов для работы. BZIP2 заметно мощнее Deflate, но при этом медленнее и требует больше памяти. Двойка в названии появилась благодаря патентным войнам: первая версия использовала арифметическое кодирование, на которое было зарегистрировано сразу несколько ставших тогда модными жульнических патентов. Поэтому автор предпочел использовать общедоступное кодирование Хаффмена.

Как это принято в *nix-мире, алгоритм работает с одним потоком. Сжать сразу несколько файлов нельзя, но их можно сначала упаковать в один архивный файл. Обычно для этого используется TAR. Но при этом сжимаемый файл алгоритмом все равно разбивается на блоки, так как BWT требует блок байтов для сортировки. LZ-алгоритмы (Deflate) и PPM-алгоритмы (RAR) обычно работают с отдельными байтами (вернее, их нерегулярными цепочками). Вообще, все компрессоры классифицируются по использованию в них "ведущего" алгоритма LZ / BWT / PPM. Обычно степень сжатия также идет в таком порядке. То есть, BWT почти всегда жмут лучше, чем LZ, но хуже, чем PPM. Хотя, на стыках бывают и пересечения. Например, BWT-архиватор SBC часто жмет лучше, чем RAR. Но его развитие остановилось, а RAR продолжают улучшать.

Прежде чем погружаться в данное описание, вам следует изучить некоторые составные части этого алгоритма. Многое можно понять и в процессе данной статьи, но она будет гораздо понятнее, если вы уже знакомы со следующими вещами:

RLE (Run-Length Encoding)

Кодирование повторяющихся символов. Например, цепочку из десяти символов aaaaaaaaaa явно можно сохранить как-то компактнее. RLE находит такие цепочки и заменяет их на пары (a, 10). А вот как потом кодируются эти пары — есть десятки способов.

BWT (Burrows-Wheeler transform)

Сортировка Барроуза-Уиллера. Это самый важный алгоритм в цепочке BZIP2. Суть его в следующем: берется блок байтов и записывается как строка в таблицу. Затем мы поворачиваем этот блок на один байт (последний байт пишем перед первым) и записываем в следующую строку. Так повторяем, пока не получим квадратную таблицу из всех возможных поворотов первоначального блока. Строки этой таблицы мы сортируем и записываем в вывод получившийся последний столбец таблицы.

MTF (Move To Front)

Кодирование повторяющихся и расположенных близко одинаковых символов маленькими числами. Сначала составляется список всех возможных символов. Затем вместо каждого следующего входного символа мы выводим его позицию в списке, а в списке перемещаем его в самое начало.

Код Хаффмана

Префиксный код, который кодирует символы в зависимости от частоты появления (вероятности). При этом более вероятные символы кодируются более короткими кодами. Символы подбираются так, чтобы по префиксам их всегда можно было отличить друг от друга. Это уже непосредственный метод «сжатия». Все предыдущие методы лишь подготавливали для него данные.

CRC32 (Cyclic redundancy check)

Циклический избыточный код. Функция, высчитывающая 32-битное число для последовательности байтов. Используется для проверки целостности данных. Функция подобрана так, чтобы при небольшом изменении данных (в результате ошибки передачи) получалось по возможности несовпадающее число.

Формат файла

Современный поток BZIP2 выглядит так:

В начале файла почти всегда стоит "BZh9" и меняться может только цифра в конце. Она означает максимальный размер блоков, на которые нарезается файл. 1 означает 100'000, а 9 — 900'000. Разумеется, почти всегда там будет стоять 9: при большом блоке сжатие обычно лучше. Но скорость при этом ниже. 9 блоков по 100'000 байт обрабатываются гораздо быстрее, чем один на 900'000. Размер блока — единственный параметр упаковщика, больше пользователь ничего выбрать не может.

Данные записываются побитово, так что после первых десяти символов (4 байта из заголовка файла и 6 байт метки начала первого блока) все остальные магические числа могут быть сдвинуты на любое количество бит и просто поиском по байтам их не найти. Данные блоков идут друг за другом без выравнивания. После общего CRC32 могут остаться неиспользованные биты в последнем байте. Их просто обнуляют.

Для каждого блока вычисляется сумма CRC32 его исходных байтов (до прохода RLE4). В BZIP2 для ускорения расчетов используется подготовленная заранее таблица пересчетов CRC32. Для каждого следующего байта текущая сумма сдвигается на байт влево и производится операция XOR с константой из таблицы. Адрес вычисляется операцией XOR  первого байта суммы с добавляемым байтом.

Когда все байты блока учтены в сумме, она "финализируется" - просто инвертируется. Это число потом будет записано в данных блока.

Общий CRC32 набирается из сумм CRC32 отдельных блоков путем поворота на 1 бит влево и операции XOR с CRC32 очередного блока.

Нарезка блоков

Сначала файловый поток проходит через метод RLE4, который ищет в потоке последовательности одинаковых символов (но не короче 4 символов). Последовательности из двух или трех символов просто записываются как есть, а если их количество превышает 3, то первые 4 символа записываются, а следующие (до 255, но обычно только 251) заменяются одним байтом с их количеством. Скажем, если мы имеем последовательность из 10 символов 'a', то метод скопирует в вывод 'a' 'a' 'a' 'a' [6]. Самый неудачный вариант — последовательность из 4 символов: в этом случае кроме них будет записан еще и один нулевой байт. Данный метод предназначался для защиты метода BWT от длинных одинаковых последовательностей (он очень долго их сортирует), но кроме одинаковых байт гораздо чаще встречаются одинаковые последовательности из разных байтов. Поэтому помощь от данного метода очень невелика и автор метода считает его ошибкой. После записи каждого байта или сжатой последовательности метод проверяет длину набранного блока. Если она близка к желаемой (до размера блока осталось меньше 18 байт), блок отправляется на обработку, а последующие данные набираются в следующий блок. Поэтому блоки всегда чуть короче заказанной длины.

203032015156100288888888883030131 => 2030320151561002888863030131

Благодаря возможности сжатия, в блок на 900000 может попасть чуть меньше (<720k) или гораздо больше (>46M) байт исходного файла.

Формат блока

Сжатый блок может занимать любое количество бит и выравнивание между блоками не предусмотрено, поэтому все структуры могут начинаться с любого бита.

Краткое описание алгоритма сжатия блока

Отдельные шаги я рассмотрю в следующей статье, а сейчас просто коротко набросаем шаги алгоритма:

1. Сначала сортируем блок методом BWT и запоминаем индекс исходного блока
2. Затем перенумеровываем байты, сдвигая вниз значения байтов, если какие-то значения не появляются. То есть, если в блоке вообще не встречался байт 120, то все последующие байты будут сдвинуты вниз на один байт. Эту операцию можно провести и перед сортировкой: некоторые способы сортировки могут благодаря ей ускориться. Референсный алгоритм выполняет ее одновременно со следующим шагом.
3. Составляем RLE-MTF-последовательность. Отсортированный блок обычно содержит длиные цепочки одинаковых символов или последовательностей символов. Мы проходим по байтам и рассматриваем их как последовательность цепочек одинаковых символов. Каждую такую цепочку мы кодируем как символ и длина последовательности. Символ сначала пропускается через MTF, (он наверняка недавно появлялся, так работает BWT). А длину цепочки кодируют с помощью двух специальных символов: RUNA и RUNB. Это кодирование позволяет записать любую длину. Поскольку мы вводим новые символы в алфавит, их уже не спутаешь с байтами файла. Именно эту самую RLE-MTF-последовательность мы и будем дальше сжимать, сами байты нас уже не интересуют.
4. Составляем начальные таблицы Хаффмана. Каждые 50 элементов RLE-MTF-последовательности сжимаются по одной таблице. Это позволяет выбирать локально самый выгодный способ сжатия. Сначала решаем сколько таблиц будет: BZIP2 поддерживает от 2 до 6 таблиц. Их количество зависит от количества элементов RLE-MTF. Чаще всего именно 6 и создается. Меньшие количества выгодны только для коротких последовательностей, где запись самой таблицы не окупится оптимизацией кодирования. Начальные таблицы собираются по волшебному алгоритму, так что смысл его не обязательно понимать. В первую таблицу попадает сколько-то первых символов с хорошими вероятностями, а остальные с плохими; во вторую - следующие сколько-то символов.
5. Оптимизируем таблицы. Прикидываем длину каждого блока из 50 элементов, если его сжимать каждой таблицей и выбираем самую выгодную для него. Затем эта таблица обновляет свою статистику элементами блока и таблицы пересчитываются. В результате распределение по таблицам чуть-чуть приближается к локальному максимуму. Такая операция выполняется 4 раза. После 4 раза улучшения уже не очень значительны. Обычно лишь первые 3 шага очень серьезно различаются в результатах.
6. Вычисляем конкретные коды для таблиц (до этого мы работали только с длинами кодов).
7. Выводим карту использованных символов: сначала по биту для группы из 16 значений (16 бит), затем каждую группу, где есть хоть один использованый символ. Для большинства бинарных файлов таблица будет полностью заполнена и мы выведем 17 значений xFFFF. А вот текстовые файлы часто содержат небольшую часть всех возможных байтов и для них числа будут другие. Это нужно для сокращения таблиц Хаффмана: меньше используемых байтов, меньше символов в таблице.
8. Выводим селекторы (номер используемой таблицы) для каждого 50-символьного блока. Селекторы пропускаются через MTF и записываются в 1-арном виде: количество единиц равно номеру в MTF и ноль в конце. То есть 0 = 0, 1 = 10, 2 = 110 и т.д. В соседних блоках чаще всего используются одинаковые таблицы, так что большинство селекторов кодируются одним битом.
9. Выводим кодовые таблицы. На самом деле сохраняются только длины кодов, а по ним распаковщик может построить такую же таблицу. Коды внутри таблицы благодаря RLE-MTF обычно последовательно нарастают, так что явно выводится длина только первого кода, а для последующих идут инструкции по модификации:
   0 - Длина готова
   10 - Увеличить длину
   11 - Уменьшить длину
10. Выводим сами коды для символов: для каждого 50-символьного блока берем по его селектору соответствующую таблицу и записываем из нее соответствующие символам коды.