...с этого места Alone Coder пересел за
пентагон и продолжил набирать статьи на
нём. Несмотря на сопротивляющуюся клавиа-
туру, это оказалось удобнее :)
Формат RAR 2.x.
Мне очень понравился этот формат с точки
зрения быстроты распаковщика, соотнесённой
с качеством сжатия, поэтому я решил вам о
нём рассказать.
Для начала приведу фирменную техническую
информацию,чтобы было немного понятно, что
и где в файле лежит :)
--------- begin of techinfo.txt ----------
Техническая информация по RAR версии 2.70
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ОПИСЫВАЕМЫЙ ФОРМАТ АРХИВА ДЕЙСТВИТЕЛЕН
ТОЛЬКО ДЛЯ RAR ВЕРСИИ 1.50 И СТАРШЕ
==========================================
Формат архивного файла RAR
==========================================
Файл архива состоит из блоков разной дли-
ны. Порядок следования этих блоков может
меняться, но первым блоком всегда должен
быть блок-маркер, за которым следует блок
заголовка архива.
Каждый блок начинается со следующих полей:
HEAD_CRC 2 байта CRC всего блока
или его части
HEAD_TYPE 1 байт Тип блока
HEAD_FLAGS 2 байта Флаги блока
HEAD_SIZE 2 байта Размер блока
ADD_SIZE 4 байта Необязательное
поле:добавление
к размеру блока
Поле ADD_SIZE присутствует, только если
(HEAD_FLAGS & 0x8000) != 0
Общий размер блока указан в поле HEAD_SIZE
- если (HEAD_FLAGS & 0x8000) == 0,- или
HEAD_SIZE+ADD_SIZE,если есть поле ADD_SIZE
- при этом (HEAD_FLAGS & 0x8000) != 0.
Во всех блоках следующие биты в HEAD_FLAGS
имеют одинаковое значение:
0x4000 - если установлен, то старые версии
RAR будут игнорировать этот блок
и удалять его при изменении архи-
ва;
если не установлен, то блок копи-
руется в новый архивный файл при
изменении архива;
0x8000 - если установлен, то присутствует
поле ADD_SIZE,
и размер полного блока составляет
HEAD_SIZE+ADD_SIZE.
Заявленные типы блоков:
HEAD_TYPE=0x72 блок-маркер
HEAD_TYPE=0x73 заголовок архива
HEAD_TYPE=0x74 заголовок файла
HEAD_TYPE=0x75 заголовок комментария
HEAD_TYPE=0x76 электронная подпись
старого типа
HEAD_TYPE=0x77 субблок
HEAD_TYPE=0x78 информация для
восстановления
HEAD_TYPE=0x79 электронная подпись
Блок комментария используется только внут-
ри других блоков.
Обработка архива происходит следующим об-
разом:
1. Читается и проверяется блок-маркер
2. Читается заголовок архива
3. Читаются или пропускаются HEAD_SIZE-ра-
змер(MAIN_HEAD) байт
4. Если обнаружен конец архива, то обрабо-
тка архива прекращается, иначе читаются 7
байт в полях:
HEAD_CRC,HEAD_TYPE,HEAD_FLAGS,HEAD_SIZE.
5. Проверяется HEAD_TYPE.
Если HEAD_TYPE==0x74
прочитать заголовок файла (первые 7 байт
уже прочитаны)
прочитать или пропустить HEAD_SIZE-раз-
мер(FILE_HEAD) байт
прочитать или пропустить FILE_SIZE байт
иначе
прочитать соответствующий блок HEAD_TYPE:
прочитать HEAD_SIZE-7 байт
если (HEAD_FLAGS & 0x8000)
прочитать ADD_SIZE байт
6. Перейти к шагу 4.
==========================================
Форматы блоков
==========================================
Блок-маркер (MARK_HEAD)
~~~~~~~~~~~~~~~~~~~~~~~
HEAD_CRC Всегда 0x6152
2 байта
HEAD_TYPE Тип заголовка: 0x72
1 байт
HEAD_FLAGS Всегда 0x1a21
2 байта
HEAD_SIZE Размер блока = 0x0007
2 байта
Блок-маркер в действительности считается
фиксированной последовательностью байт:
0x52 0x61 0x72 0x21 0x1a 0x07 0x00
(прим.AlCo: удачно подобран CRC!!! Выходит
любопытная последовательность: "Rar!",Esc,
Bell и Nul, удобная и для визуального опо-
знавания, и для проверки канала передачи
данных на вшивость.)
(прим. Shaitan: собственно разработ-
чик, Евгений Рошал, даного формата перво-
начально и добивался визуального определе-
ни архива. Примерно такая же история и с
другими форматами архивов, и вообще, нали-
чие неповторимой и визуальной сигнатуры в
разного рода файлах уже стало правилом хо-
рошего тона)
Заголовок архива (MAIN_HEAD)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
HEAD_CRC CRC полей от HEAD_TYPE до
2 байта RESERVED2
HEAD_TYPE Тип заголовка: 0x73
1 байт
HEAD_FLAGS Битовые флаги:
2 байта
0x01 - Атрибут тома (том
многотомного архива)
0x02 - Есть архивный коммен-
тарий
0x04 - Атрибут блокировки
архива
0x08 - Атрибут непрерывного
(solid) архива
0x10 - Не используется
0x20 - Есть информация об
авторе или электронная
подпись (AV)
остальные биты в HEAD_FLAGS зарезерви-
рованы для внутреннего использования.
HEAD_SIZE Общий размер архивного
2 байта заголовка,включая архивные
комментарии
RESERVED1 Зарезервировано
2 байта
RESERVED2 Зарезервировано
4 байта
Блок комментария
присутствует, если (HEAD_FLAGS & 0x02)!=0
Заголовок файла (файл в архиве)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
HEAD_CRC CRC полей от HEAD_TYPE до
2 байта FILEATTR и имени файла
HEAD_TYPE Тип заголовка: 0x74
1 байт
HEAD_FLAGS Битовые флаги:
2 байта
0x01 - файл продолжается из
предыдущего тома
0x02 - файл продолжается в
следующем томе
0x04 - файл зашифрован паролем
0x08 - есть комментарий файла
0x10 - используется информация
из предыдущих файлов
(флаг непрерывности)
(для RAR 2.0 и выше)
биты 7 6 5 (для RAR 2.0 и выше)
0 0 0 - размер словаря 64 Кб
0 0 1 - размер словаря 128 Кб
0 1 0 - размер словаря 256 Кб
0 1 1 - размер словаря 512 Кб
1 0 0 - размер словаря 1024Кб
1 0 1 - зарезервировано
1 1 0 - зарезервировано
1 1 1 - file is directory
0x100 - есть поля
HIGH_PACK_SIZE и
HIGH_UNP_SIZE. Эти поля
используются только для
архивирования очень бо-
льших файлов (больше 2
Гб), для меньших файлов
эти поля отсутствуют.
0x8000 - этот бит всегда устано-
влен,так как общий раз-
мер блока HEAD_SIZE +
+ PACK_SIZE (и плюс
HIGH_PACK_SIZE, если
установлен бит 0x100)
HEAD_SIZE Полный размер заголовка
2 байта файла, включая имя файла и
комментарии
PACK_SIZE Размер файла в архиве
4 байта (сжатый)
UNP_SIZE Размер исходного файла
4 байта (несжатый)
HOST_OS Использованная при архивиро-
1 байт вании операционная система:
0 - MS-DOS
1 - OS/2
2 - Win32
3 - Unix
4 - Mac OS
5 - BeOS
FILE_CRC CRC файла
4 байта
FTIME Дата и время в стандартном
4 байта формате MS-DOS
UNP_VER Версия RAR,необходимая для
1 байт извлечения файла
METHOD Метод сжатия
1 байт
NAME_SIZE Размер имени файла
2 байта
ATTR Атрибуты файла
4 байта
HIGH_PACK_SIZE Старшие 4 байта 64-битного
4 байта размера сжатого файла.
Необязательное значение,
которое присутствует,
только если бит 0x100 в
HEAD_FLAGS установлен.
HIGH_UNP_SIZE Старшие 4 байта 64-битного
4 байта размера несжатого файла.
Необязательное значение,
которое присутствует,
только если бит 0x100 в
HEAD_FLAGS установлен.
FILE_NAME Имя файла - строка
размером NAME_SIZE байт
Блок комментария
присутствует, если (HEAD_FLAGS & 0x08)!=0
Блок комментария
~~~~~~~~~~~~~~~~
HEAD_CRC CRC полей от HEAD_TYPE до
2 байта COMM_CRC
HEAD_TYPE Тип заголовка: 0x75
1 байт
HEAD_FLAGS Битовые флаги
2 байта
HEAD_SIZE Размер заголовка коммента-
2 байта рия + размер комментария
UNP_SIZE Размер несжатого коммента-
2 байта рия
UNP_VER Версия RAR,необходимая для
1 байт извлечения комментария
METHOD Метод сжатия
1 байт
COMM_CRC CRC комментария
2 байта
COMMENT Текст комментария
Блок дополнительной информации
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
HEAD_CRC CRC блока
2 байта
HEAD_TYPE Тип заголовка: 0x76
1 байт
HEAD_FLAGS Битовые флаги
2 байта
HEAD_SIZE Общий размер блока
2 байта
INFO Прочие данные
Субблок
~~~~~~~
Объект в архиве (блок или заголовок) может
сопровождаться субблоком. Субблок зависит
от основного объекта. Субблок может быть
удален или перемещен в новой версии архива
при его обновлении.
Субблок содержит следующие поля:
HEAD_CRC CRC блока
2 байта
HEAD_TYPE Тип заголовка: 0x77
1 байт
HEAD_FLAGS Битовые флаги
2 байта (HEAD_FLAGS & 0x8000)==1,
так как полный размер
блока составляет
HEAD_SIZE + DATA_SIZE
HEAD_SIZE Общий размер блока
2 байта
DATA_SIZE Общий размер данных
4 байта
SUB_TYPE Тип субблока
2 байта
RESERVED Должно быть 0
1 байт
Другие поля Другие поля в зависимости
от типа субблока
Субблок расширенных атрибутов OS/2
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
HEAD_CRC CRC блока
2 байта
HEAD_TYPE Тип заголовка: 0x77
1 байт
HEAD_FLAGS Битовые флаги
2 байта (HEAD_FLAGS & 0x8000)==1,
так как полный
размер блока составляет
HEAD_SIZE + DATA_SIZE
HEAD_SIZE Общий размер блока
2 байта
DATA_SIZE Общий размер данных
4 байта (сжатый размер расширенных
атрибутов)
SUB_TYPE 0x100
2 байта
RESERVED Должно быть 0
1 байт
UNP_SIZE Размер несжатых
4 байта расширенных атрибутов
UNP_VER Версия RAR,необходимая для
1 байт извлечения расширенных
атрибутов
METHOD Метод сжатия
1 байт
EA_CRC CRC расширенных атрибутов
4 байта
==========================================
Примечания
==========================================
1. Для обработки SFX-архива нужно пропус-
тить модуль SFX, для чего в архиве осуще-
ствляется поиск блока-маркера.В самом SFX
модуле отсутствует последовательность ба-
йтов блока-маркера
(0x52 0x61 0x72 0x21 0x1a 0x07 0x00).
2. CRC вычисляется с помощью стандартного
полинома 0xEDB88320. В случае,если размер
CRC меньше 4 байт, то используются только
младшие байты.
3. Кодирование метода сжатия:
0x30 - сохранение (без сжатия)
0x31 - скоростное сжатие
0x32 - быстрое сжатие
0x33 - нормальное сжатие
0x34 - хорошее сжатие
0x35 - максимальное сжатие
4. Номер версии RAR,необходимой для извле-
чения, кодируется как 10 * старший номер
версии + младший номер версии.
---------- end of techinfo.txt -----------
Дальше пошла отсебятина:
Внутренний формат RAR.
Используется сжатие типа LZ, заключающееся
в копировании некоторых кусков из уже рас-
пакованной части файла под курсор. Ниже
употребляется терминология:
"длина ссылки" (puts) - длина копируемого
куска;
"смещение" (disp) - смещение от курсора до
начала копируемого куска.
Для уменьшения избыточности LZ кодирования
используются деревья Хаффмана глубиной до
15 бит, в количестве 4 штуки. Эти деревья
носят названия: BD, LD, DD и RD. Первое
применяется для распаковки остальных трёх.
BD содержит 19 возможных символов;
LD содержит 298 возможных символов;
DD содержит 48 возможных символов;
RD содержит 28 возможных символов.
Ниже используется термин:
"ярус" (Row) - совокупность символов в де-
реве, имеющих одинаковую битовую длину.
Любой упакованный блок,если он не является
вторым и далее в solid архиве, начинается
с блока под названием "упакованные дере-
вья".
Упакованные деревья:
1 бит - "multimedia block" flag ( 0, если
не multimedia: ниже рассматривается только
такой вариант)
1 бит - очистить старый массив длин нулями
( 1 - не надо)
19x4 бит - дерево BD. Указаны длины в би-
тах для всех 19 символов (символы расписа-
ны ниже). Алгоритм генерации дерева,исходя
из информации о длинах, довольно хитрый, и
здесь я его приводить не буду. Скажу толь-
ко, что более короткие символы располагаю-
тся в дереве левее (т.е. начинаются скорее
с нуля, чем с единицы), нежели более длин-
ные.
После того, как вышеизложенная информация
прочитана, начинается работа с большой та-
блицей длин под названием RT_Table, кото-
рая имеет размер 374=298+48+28 байт. В ней
последовательно содержатся длины (0..15)
всех символов деревьев LD, DD и RD.
Итак, устанавливаем указатель i на первый
байт таблицы RT_Table и читаем символы из
файла, пользуясь деревом BD:
0..15 - прибавить это число к текущей яче-
йке таблицы RT_Table и перейти к следующей
ячейке.
tab[i]=(tab[i]+num)&15;i++
16 - скопировать предыдущую ячейку N+3 ра-
за, где N (2 бита) хранится в файле сразу
после символа 16.
tab[i]=tab[i-1];i++ и т.д.
17 - поместить в Z+3 ячеек,начиная с теку-
щей,число 0. Где Z (3 бита) хранится сразу
после символа 17.
tab[i]=0;i++ и т.д.
18 - поместить в Z+11 ячеек, начиная с те-
кущей,число 0. Где Z (7 бит) хранится сра-
зу после символа 18.
tab[i]=0;i++ и т.д.
Заполнение RT_Table заканчивается, когда
обработаны все её 374 ячейки.
Таким образом, мы получили из файла струк-
туры всех деревьев. Переводим деревья в
удобный для нас формат (в моём распаковщи-
ке это таблица чисел "LowRowCode", таблица
чисел "RowAdr-(LowRowCode>>Row)" и таблица
"номер листа дерева->символ", где RowAdr -
адрес первого символа в ярусе,а LowRowCode
- код,соответствующий самому левому элеме-
нту яруса) и переходим к считыванию упако-
ванных данных.
Упакованные данные:
Как выше уже упоминалось, до самих данных
в файле лежат деревья. По тому же условию,
что требуется для наличия деревьев в нача-
ле файла (то есть,"блок не является вторым
или далее файлом solid архива"), следует
(или не следует иначе) обнулить таблицу
предыдущих смещений. Дело в том,что распа-
ковщик всегда хранит 4 предыдущих реализо-
ванных смещения. Эти смещения - 20-битные
числа (максимальная ссылка назад = 1 Мб).
Впрочем, я не уверен, что обнулять их так
уж необходимо, но кто знает, что на уме у
упаковщика?
Читаем из файла токен, пользуясь деревом
LD:
0..255 - просто символ. Помещаем его в вы-
ходной поток.
256 - повтор предыдущего смещения и преды-
дущёй длины ссылки. Реализуем эту ссылку.
257..260 - берём одно из предыдущих 4 сме-
щений ( 257 =самое новое, 258 =позапрошлое
и т.д.). Читаем токен, пользуясь деревом
RD. Этот токен указывает номер строки в
таблице midBIT. Из неё берётся длина ссыл-
ки и количество битов,которые нужно сейчас
дополнительно дочитать из файла,чтобы при-
бавить их к этой длине ссылки.
Потом длина ещё немного корректируется:
если disp>=257, инкрементируем длину;
если disp>=32768, снова инкрементируем
длину;
если disp>=#40000, ещё раз инкрементируем
длину.
Уфффф. Реализуем ссылку.
261..268 - если вычесть 261, получим номер
строки в таблице litBIT. Из неё берётся
смещение и число битов, которые нужно до-
читать из файла для коррекции этого смеще-
ния. Длина ссылки считается равной 2. Реа-
лизуем ссылку.
269 - считываем новые деревья (формат см.
выше). Ничего в самом распаковщике не ини-
циализируется! Меняются только деревья!
270..297 - вычитаем 270, получаем № строки
в midBIT, достаём оттуда длину ссылки и
число бит её коррекции.
Инкрементируем длину.
Читаем токен, пользуясь деревом DD. Он за-
даёт номер строки в таблице bigBIT - берём
оттуда смещение и число битов для его кор-
рекции.
Если disp>=32768, инкрементируем длину;
если disp>=#40000, ещё раз инкрементируем
длину.
Реализуем ссылку.
Распаковка заканчивается, когда извлечено
столько байт распакованного файла, сколько
указано в заголовке этого файла.
Всё! :) В следующий раз я расскажу вам про
мультимедийную компрессию и шифрование,
если, конечно, сам разберусь :)
