|
Inferno
#04
22 июня 2003 |
|
Sofтинка - Формат RAR 2.x. Техническая информация.
...с этого места 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, ещё раз инкрементируем длину. Реализуем ссылку. Распаковка заканчивается, когда извлечено столько байт распакованного файла, сколько указано в заголовке этого файла. Всё! :) В следующий раз я расскажу вам про мультимедийную компрессию и шифрование, если, конечно, сам разберусь :)
Другие статьи номера:
Похожие статьи:
В этот день... 21 ноября