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, ещё раз инкрементируем 
длину. 
Реализуем ссылку. 

Распаковка  заканчивается, когда извлечено
столько байт распакованного файла, сколько
указано в заголовке этого файла.

Всё! :) В следующий раз я расскажу вам про 
мультимедийную  компрессию  и  шифрование, 
если, конечно, сам разберусь :) 





Другие статьи номера:

События - Об окончании первой части виртуального музыкального пати The Compo.

Sofтинка - Об операционных системах для спектрума ChAOS и ZXVGS.

Inferno - Авторы журнала.

Pentagon - Инструкция по активации незадействованной (нулевой) банки пзу в компьютере Пентагон.

Pentagon - Инструкция по переделке Пентагона-128 для выхода по Reset'у в 0-ю банку ПЗУ 27512.

Gameland - Прохождение игры Черный Ворон: Неизвестные Отгрузки. Диск 1.

Gameland - Прохождение игры Черный Ворон: Неизвестные Отгрузки. Диск 2.

Sofтинка - Описание графической оболочки для дисковой системы TR-DOS - ChAOS.

Inferno - Об оболочке.

Sofтинка - Редактор двухэкранной графики DouBleScreen Editor v0.4.

Sofтинка - Операционная система ZXVGS. Состав версий, софт.

Inferno - Вступление от редакторов.

Железо - Итоги освоения кодеров RGB - PAL/NTSC, на конец 2002 года.

Gameland - Об играх King's Bounty 3, Чёрный Ворон: Неизвестные Отгрузки.

Others - Об анкетировании.

For Coderz - Макросы под ассемблер Alasm v4.4x.

Математика - Фрактал Мандельброта.

Sofтинка - Музыкальный редактор Pro Tracker v3.71. Особенности программы.

Sofтинка - Формат RAR 2.x. Техническая информация.

Others - Зарегистрированные пользователи ZXVGS и CPM22QED.

Sofтинка - Типы файлов, определённые в ОС ZXVGS.

Sofтинка - Функции операционной системы ZXVGS.

Sofтинка - Внешний вид операционной системы ZXVGS.

Sofтинка - IDEDOS - доступ к жёстким дискам в ОС ZXVGS.

Sofтинка - Описание операционной системы ZXVGS.

Sofтинка - MEMDISK - файловая система для хранения файлов в областях памяти.

Sofтинка - Релизы ОС ZXVGS и их различия.

Sofтинка - Резидентные Расширения Системы (RSX) в ZXVGS.

Sofтинка - Список версий новой операционной системы для спектрума ZXVGS.

Железо - Расширенная клавиатура для sinclair-совместимых персональных компьютеров.

For Coderz - Алгоритм нахождения целой части квадратного корня.

События - Номинанты виртуального музыкального пати The Compo.


Темы: Игры, Программное обеспечение, Пресса, Аппаратное обеспечение, Сеть, Демосцена, Люди, Программирование

Похожие статьи:
Sofтинка - Формат RAR 2.x. Техническая информация.

В этот день...   19 июля