Сергей Холодилов (fat_crocodile) wrote,
Сергей Холодилов
fat_crocodile

Category:

Пример: DEFLATE

Теория и обзор это здорово, но интересно же посмотреть, как устроен настоящий архиватор. DEFLATE это самая известная в мире реализация идеи LZ77+Huffman. Это zlib, gzip, он же внутри PNG, его использует SSL и http тоже обычно жмётся им же, и ещё много где. В общем, популярная штука.

Кажется, название формата-и-алгоритма правильно писать всеми большими буквами, но мне очень не понравилось, как это выглядит в тексте, поэтому дальше маленькими -- deflate.

Напоминаю общую идея алгоритмов этого класса: данные проходят через LZ77, потом результат кодируется Хаффманом. Формат, в котором сохраняются сжатые данные, и некоторые части рекомендуемого алгоритма, описаны в RFC 1951.

Код для декодирования (нормального) и кодирования (несколько урезанного) я, конечно, написал, но его получилось немного много для поста, так что в этот раз без примеров кода, извините. Может быть придумаю куда его выложить, приведу в порядок и выложу. Когда-нибудь.

Первый этап, LZ77

Максимальное смещение -- 215, максимальная длина совпадения -- 258 байт.
На выходе последовательность из литералов и пар <длина, смещение>, смещения считаются не от начала окна, а от текущего символа. Совпадения короче трёх символов не рассматриваются. Изначально в окне нет ничего и генерируемое смещение не должно выходить за пределы данных.

Это была обязательная часть. Рекомендательная начинается словами (это раздел 4, "Compression algorithm details"):

... since many variations of LZ77 are patented, it is strongly recommended that the implementor of a compressor follow the general algorithm presented here, which is known not to be patented per se. The material in this section is not part of the definition of the specification per se, and a compressor need not follow it in order to be compliant.

Подчеркнул последнее предложение я. И дальше описывается следующее:
  • При сжатии для поиска совпадений используется хеш-таблица, содержащая списки вхождений.

  • Аргумент хеш-функции -- следующие три символа.

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

  • Слишком старые вхождения специально не удаляются, просто игнорируются.

  • Вместо этого контролируется длина списка, если он стал слишком длинным, конец обрубается (чтобы поиск не превращался в линейный; вероятно имеется ввиду, что граница, по которой обрубается и граница, при пересечении которой обрубается -- это две разные границы).

  • Предлагается использовать "lazy matching". Найдя совпадение длины N, попробовать найти совпадение большей длины, начинающееся со следующего символа. Если получается, то вместо исходного совпадения на выходе литерал для текущего символа и более длинное найдённое. Если N уже и так неплохое, и нам не критично важна степень сжатия, эту логику можно отключать.

  • Если прежде всего важна скорость, хеш-таблица обновляется только тогда, когда найдено короткое совпадение или его не удалось найти совсем.

Когда обновляется хеш-таблица в обычной ситуации не написано: то ли на каждом шаге, то ли на каждый символ (насколько я понял, zlib в стандартном режиме обновляет на каждый символ).
Но в общем всё довольно просто и понятно.

Второй этап, бинарщина

Биты, байты
Многобайтные числа сохраняются в формате little endian, т.е. сначала младший байт, потом следующий по старшинству и т.д. Реально встречаются только двубайтные.

Битовые коды записываются в байты от младшего бита байта к старшему. При этом коды Хаффмана записываются от первого бита кода к последнему. Т.е., если у нас есть такая кодовая таблица:
a --> 11001 
b --> 111010
то строка ab кодируется так:
01234567 01234567
11001111 010-----
Это выглядит естественным потому что я расположил биты в порядке от младших к старшим. Если записать байт так, как записывают обычно, смотрится уже гораздо менее естественно. Если считать, что код Хаффмана это число и соответственно "первый бит" это "старший разряд", становится ещё менее естественно. Поэтому в этом месте для понимания логики так считать не надо: здесь коды это не числа, а битовые строки, и старших-младших у них нет, есть первые и последние.

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

Блоки
На бинарном уровне закодированный текст представляет из себя последовательность блоков, размер блока ограничен только тем, что размер соответствующих ему несжатых данных не должен быть больше 65 535 байт. Для LZ77 они прозрачны, он может обращаться к истории через границы блоков.

Блок начинается с трёхбитного заголовка: xyz
x -- признак последнего блока
zy -- тип блока (обратите внимание, что z старший, т.к. двубитное поле не код Хаффмана):
      00 -- блок без компрессии
      01 -- сжатие с предопределёнными кодами Хаффмана (fixed Huffman codes)
      10 -- сжатие с кодами Хаффмана, специально построенными для этого блока с учётом частотности данных (dynamic Huffman codes)
      11 -- зарезервировано
Блок начинается сразу же после предыдущего, начало блока не обязательно совпадает с границей байта.

Блоки без компрессии (тип 00)
Самые простые. После заголовка идёт:
0-7 битов  -- выравнивание на границу байта
два байта  -- поле LEN
два байта  -- поле NLEN
LEN байтов -- данные, не сжатые, даже никакого LZ77; но использовать этот блок для ссылок LZ77 (наверное?) может
Поле NLEN должно быть равно дополнению LEN до единицы (когда такое пишут, имеют ввиду единицу разряда, следующего за самым большим из представленных), т.е. фактически это два младших байта -LEN. Зачем оно нужно не очень понятно.

Блоки с предопределённым кодом (тип 01)
Вот тут надо вспомнить, что используемый вариант LZ77 выплёвывает либо литералы, либо пары (длина, смещение), где длина не больше чем 258. И нужно как-то уметь отличить, что идёт дальше: символ или пара.

Поэтому кодируемый Хаффманом алфавит объединяет в себе символы, признак конца блока и длины. В результате все получают разные коды и различимы. Немного точнее, алфавит следующий:
0-255    -- символы
256      -- признак конца блока
257-264  -- длины, 3-10
265-268  -- пары длин, от 11,12 до 17,18. Следующий бит позволяет выбрать число из пары
269-272  -- четвёрки длин, от 19-22 до 31-34. Следующие два бита позволяют выбрать
273-276  -- восьмёрки длин, от 35-42 до 59-66. Следующие три бита позволяют...
277-280  -- наборы по шестнадцать длин, от 67-82 до 115-130. Следующие четыре бита...
281-284  -- наборы по тридцать две длины, от 131-162 до 227-257. Следующие пять...
285      -- длина 258
Тот же приём с дополнительными битами используется для кодирования смещений. Таблица:
0-3   -- 1-4, смещения 0 не бывает, значит код ему не нужен
4,5   -- пары 5,6 и 7,8; 1 дополнительный бит
6,7   -- четвёрки 9-12 и 13-16; 2 бита
8,9   -- восьмёрки 17-24 и 25-32; 3 бита
10,11 -- 33-48 и 49-64; 4 бита
12,13 -- 65-96 и 97-128; 5 битов
14,15 -- 129-192 и 193-256; 6 битов
16,17 -- 257-384 и 385-512; 7 битов
18,19 -- 513-768 и 769-1024; 8 битов
20,21 -- 1025-1536 и 1537-2048; 9 битов
22,23 -- 2049-3072 и 3073-4096; 10 битов
24,25 -- 4097-6144 и 6145-8192; 11 битов
26,27 -- 8193-12288 и 12289-16384; 12 битов
28,29 -- 16285-24576 и 24577-32768; 13 битов
Немного подробнее о том, как кодируются дополнительные биты. Пусть в кодовой таблице символов-и-длин есть запись:

278 <--> 0010110

Код 278 соответствует диапазону длин 83-98, четыре дополнительных бита. Тогда
01234567 01234567
---00101 100000--    -- это 83
---00101 101000--    -- это 84 (= 83 + 1)
---00101 101010--    -- а это 88 (= 83 + 5)
---00101 101111--    -- 98 (= 83 + 15)
Обратите внимание, что числа записаны от младших битов к старшим. Со смещениями точно так же.

Всё написанное про алфавиты верно как для блоков с предопределённым кодом Хаффмана, так и для блоков с построенным кодом. А собственно сам предопределённый код выглядит так:

Символы и длины:
  0-143  -- 8 бит, от 00110000 до 10111111
144-255  -- 9 бит, от 110010000 до 111111111
256-279  -- 7 бит, от 0000000 до 0010111
280-287  -- 8 бит, от 11000000 до 11000111
коды 286 и 287 лишние, встречаться не должны

Смешения кодируются соответствующим пятибитным числом, от 00000 до 11111; и опять два лишних кода, для 30 и 31.

Блоки с построенным кодом (тип 10)
Отличаются от блоков с предопределённым кодом только собственно кодом Хаффмана, который, поскольку он не известен заранее, нужно сохранить в самом блоке. Но перед этим его нужно правильным образом построить.

Во-первых, длина кодов не должна превышать 15 бит.
Во-вторых, применяется один из вариантов канонического кодирования. А именно:

  • [если воспринимать коды как числа, у которых первый бит кода это старший разряд, то] все коды одной длины должны быть последовательными значениями, упорядоченными так же, как символы, которые они кодируют

  • [если воспринимать коды как строки бит, то] коды меньшей длины лексикографически предшествуют кодам большей длины

Кстати, описанный выше фиксированный код построен в соответствии с этими правилами

Это позволяет восстановить коды, зная только длины. Например, если даны длины:
a --> 3
b --> 3
c --> 2
d --> 3
e --> 3 
f --> 4
g --> 4
h --> 4
i --> 4
То однозначно получаем:
c --> 00     -- начинать надо с нулей
a --> 010    -- минимальная строка, следующая за последним кодом предыдущей группы. Фактически это 
                ещё один код предыдущей группы, к которому в конец дописали нули.
b --> 011    -- +1, и т.п., в рамках группы буквы расположены по алфавиту
d --> 100
e --> 101
f --> 1100   -- следующая группа
g --> 1101   -- +1, и т.п.
h --> 1110
i --> 1111
А значит сохранять словарь можно в виде последовательности длин.

Кроме того, упорядоченная структура позволяет быстрее определять границы кода в потоке бит и быстрее декодировать. Идея примерно такая: по префиксу можно понять, к какой группе длин относится код, оставшаяся часть даёт номер в группе.

Сохранение длин это тоже отдельная история. Во-первых, они описываются следующим алфавитом команд:
0-15 -- длины от 0 до 15 соответственно; длина 0 означает, что символ не используется; кодов длиннее 15 не должно быть
16   -- повторить предыдущую длину от трёх до шести раз, следующие два бита уточняют, сколько именно раз (00 -- 3, 11 -- 6)
17   -- повторить длину 0 3-10 раз, следующие три бита уточняют
18   -- повторить длину 0 11-138 раз, следующие семь битов уточняют
Во-вторых, этот алфавит тоже закодирован Хаффманом!

Итак, сразу после заголовка в блоке с построенным кодом идёт:

  • HLIT -- 5 бит; [число, такое, что] количество-литералов-и-длин = HLIT + 257. Фактически HLIT это количество длин, так как первые 257 элементов, которые всегда присутствуют это символы и признак конца блока.

  • HDIST -- 5 бит; количество-смещений = HDIST + 1

  • HCLEN -- 4 бита; количество-команд-длин = HCLEN + 4

  • Дальше идёт (HCLEN+4) трёхбитовых длин, кодирующих алфавит команд для кодирования длин. При этом алфавит расположен в следующем порядке: 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15. Таким образом повышается вероятность, что он потребуется не весь. А вот при вычислении кодов порядок обычный.

  • И после этого при помощи полученных команд закодировано HLIT + HDIST + 258 длин. Закодировано именно непрерывным массивом, т.е. команда "повторить что-то сколько-то раз" может пересекать границы между литералами-длинами и смещениями.

  • Ну и наконец данные.

Понятно, что всё это не от хорошей жизни, а для сокращения непроизводительных расходов на заголовок.

Пример

Вот такие данные:

15 8d 51 0a c0 20 0c 43 ff 3d 45 ae 56 67 dd 8a 5d 0b d5 21 de 7e 0a f9 08 21 2f c9 4a 57 cb 12 05 5d ec de 82 18 c6 c3 28 4c 05 5e 61 72 3f 23 0d 6a 7c e2 ce c8 e1 8d 0d 73 77 3b c8 0a 94 29 36 e3 a8 ba 12 a9 62 f9 17 50 a9 9c b6 c3 e4 60 b8 e9 c2 24 19 e7 a1 7a ec 2d e9 78 fd 65 1b 07 a5 90 ce e9 07

15 это 00010101, а если с младших то 10101000. Первый установленный бит означает последний блок, следующие два бита сообщают, что это блок с построенным кодом Хаффмана. Начинаем разбирать. Везде дальше данные рассматриваются как поток бит, все байты младшими разрядами вперёд.
     HLIT  HDIST HCLEN
101|01000| 10110|001 1|...
то есть,

HLIT = 2, значит 259 символов-и-длин.
HDIST = 13, смещений 14
HCLEN = 12, команд 16

Дальше длины кодов команд:
     16  17   18   0   8    7   9    6  10   5   11   4  12    3  13    2 
...|000|101|0 01|010|000| 000|000|11 0|000|010|0 00|110|000| 110|000|10 1|...
ненулевые длины получаем:

0 -- 2
2 -- 5
3 -- 3
4 -- 3
5 -- 2
6 -- 3
17 -- 5
18 -- 4

Отсюда сразу коды:

0 -- 00
5 -- 01
3 -- 100
4 -- 101
6 -- 110
18 -- 1110
2 -- 11110
17 -- 11111

Дальше последовательность длин (зелёным отмечены команды, задающие длину более чем одному коду):
       17 10    5   18 21          3   18 64         4   5   6  5    4  5   6    6   4  0  5
...|11111|11 1|01|1110|0 101000|10 0|1110|101 0110|101|0 1|110|01|10 1|01|110|11 0|101|00|01|

  4   6    4   4  0  0    4  5  5    6  0  5  0   5   18 134        6   5  5  0  0    3    17 3      3  0
101|110|10 1|101|00|00| 101|01|01|1 10|00|01|00| 01|1110|11 01111|110| 01|01|00|00| 100|11111| 000|100|00|

  3  0   3      2   3    3
100|00|100| 11110|100| 100|...
Несложный подсчёт даёт следующие результаты:

Длины алфавита литералов-и-длин:
- 3 -- код 32 -- это символ пробела
- 4 -- коды 97, 101, 105, 108, 110, 111, 114 -- это 'a', 'e', 'i', 'l', 'n', 'o', 'r'
- 5 -- коды 10, 98, 100, 102, 107, 115, 116, 119, 121, 257, 258 -- это перевод строки, 'b', 'd', 'f', 'k', 's', 't', 'w', 'y', длины 3 и 4.
- 6 -- коды 99, 103, 104, 109, 117, 256 -- это 'c', 'g', 'h', 'm', 'u' и признак конца блока

Длины алфавита смещений:
- 2 -- код 11 -- диапазон 49-64
- 3 -- коды 2, 6, 8, 10, 12, 13 -- смещение 3, диапазоны 9-12, 17-24, 33-48, 65-96 и 97-128.

Отсюда сразу коды литералов-и-длин:

000 -- ' '
0010 -- a
0011 -- e
0100 -- i
0101 -- l
0110 -- n
0111 -- o
1000 -- r
10010 -- \n
10011 -- b
10100 -- d
10101 -- f
10110 -- k
10111 -- s
11000 -- t
11001 -- w
11010 -- y
11011 -- длина 3
11100 -- длина 4
111010 -- с
111011 -- g
111100 -- h
111101 -- m
111110 -- u
111111 -- EOB

И смещений

00 -- 49-64
010 -- 3
011 -- 9-12
100 -- 17-24
101 -- 33-48
110 -- 65-96
111 -- 97-128

И наконец можно разархивировать (зелёным длины, красным смещения):
    b      l    a     c      k      b      i    r     d     _    s     i     n    g           3  
...|10011| 0101|0010| 111010|10 110|10011| 0100|1000| 10100|000| 10111|010 0|0110|111 011|11011| 

3   _   i     n    _    t     h       e     _   d      e    a     d     _    o    f      _   n
010|000|01 00|0110|00 0|11000|11 1100|0011| 000|10100| 0011|0010| 10100|000| 0111|1010 1|000|0110| 

i    g       h       t     \n     t     a     k      e         4 17      s      e     _   b
0100|1110 11|111100| 11000|100 10|11000|0 010|10110| 0011|1110 0|100|011|1 0111|0011| 000|10011|

r    o     k     e     n    _    w          3 33        s     _    a    n     d     _    l    e
1000|0111| 10110|001 1|0110|000| 11001|110 11|101|110 1|10111|00 0|0010|011 0|10100|00 0|0101|001 1|..

   a    r         3 49       o     _   f      l    y
..|0010|100 0|11011|00| 1100|0111| 000|10101| 0101|1101 0|...
Дальше идут третья и четвертая строчки.

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

Чтоб два раза не вставать

В природе deflate встречается как составная часть различных форматов и протоколов. Самые простые, не вносящие каких-то дополнительных смыслов это zlib и gzip.

Я не смотрел исходники, только читал RFC и проверил на паре примеров что результат действительно на это похож.

zlib
Формат zlib описан в RFC 1950, он задумывался как тонкая обёртка над каким угодно алгоритмом архивации, для начала -- над deflate. По факту, как был один единственный deflate, так и остался (20 лет прошло, кстати).

Опуская мелкие подробности, формат выглядит так:
  • первый байт 01111000 (0x78) -- младшие четыре бита это код алгоритма архивирования, 8 это deflate; старшие четыре бита это параметр, для deflate это (log2(размер окна) - 8). 7 означает стандартное окно размером 215.

  • второй байт xy0abcde (скорее всего 0x9c) -- старшие два бита xy это применявшийся уровень сжатия, от 00 (самый быстрый) до 11 (самый качественный); 10 -- режим "по умолчанию". Младшие пять бит abcde это контрольная сумма, они подобраны так, что число (первый-байт*256 + второй-байт) делится на 31.

  • дальше идут сжатые данные

  • и в конце 4 байта контрольной суммы, вычисленной от несжатых данных по алгоритму Adler-32.

То есть всего два лишних байта в начале и четыре в конце, остальное -- просто deflate.

gzip
RFC 1952; если глобально то смысл тот же что и у формата zlib -- обёртка над произвольным алгоритмом архивирования, специфицирован только deflate, только он в итоге и есть. Но обёртка более толстая, основное предназначение всё же архивировать файлы, а не поток данных (хотя может и поток).

Файл gzip состоит из последовательности блоков, которые просто идут друг за другом, без какой-либо дополнительной информации между ними или кроме них. Каждый блок:
  • Первые два байта 0x1f 0x8b -- признак того, что это gzip-файл

  • Третий байт -- код алгоритма архивации, для deflate это 8

  • Дальше байт флагов. В основном он определяет, какие дальше есть ещё поля.

    • бит 0 пропустим

    • бит 1 -- FHCRC -- присутствует ли дальше поле CRC16

    • бит 2 -- FEXTRA -- дополнительные поля

    • бит 3 -- FNAME -- имя файла

    • бит 4 -- FCOMMENT -- комментарий

    • остальные зарезервированы, должны быть 0

  • Четыре байта -- дата модификации архивируемого файла, в стандартном формате unix, little endian. Можно игнорировать.

  • Байт дополнительных флагов, специфичных для алгоритма архивации. Для deflate он позволяет выбрать между быстрым сжатием и хорошим: 2 -- быстрое, 4 -- хорошее.

  • Один байт -- операционная система. Задумывалось для конвертации переводов строк в текстовых файлах. Безопасное значение -- 255.

  • [если FEXTRA] два байта длины дополнительных полей и потом они сами

  • [если FNAME] ограниченная нулём строка с именем файла, кодировка LATIN-1 (это rfc 1996-го года)

  • [если FCOMMENT] ограниченная нулём строка с комментарием, кодировка LATIN-1

  • [если FHCRC] CRC16 от всего вышеперечисленного, вычисляемый как два младших байта от CRC32

  • наконец-то! сжатые данные

  • CRC32 от несжатых данных

  • Четыре байта -- размер несжатых данных по модулю 232

В минимальной комплектации остаётся десять дополнительных байт в начале и восемь в конце на каждый блок. Несколько блоков получается если подсунуть гзипу несколько файлов запуском вида: gzip -c file1 file2 > res.gz. Из необязательных полей мой домашний по умолчанию использует только имя файла, причём проблему кодировки решает utf8.
Tags: архиваторы, математика, программинг
Subscribe

  • A Starting Point

    Нашел сайт https://www.astartingpoint.com, на него можно полчаса-час потратить. Там есть список тем (economy, education, government,…

  • (no subject)

    Случайно с небольшой разницей во времени прочитал в вики сюжет двух американских молодежных ... комедий? Первая "Mean Girls" (…

  • (no subject)

    Из внезапного: мальчик, с которым я 3.5 года занимался математикой получил второй результат на всеросе (9-й класс). В такой формулировке это звучит…

  • Post a new comment

    Error

    default userpic
    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 13 comments

  • A Starting Point

    Нашел сайт https://www.astartingpoint.com, на него можно полчаса-час потратить. Там есть список тем (economy, education, government,…

  • (no subject)

    Случайно с небольшой разницей во времени прочитал в вики сюжет двух американских молодежных ... комедий? Первая "Mean Girls" (…

  • (no subject)

    Из внезапного: мальчик, с которым я 3.5 года занимался математикой получил второй результат на всеросе (9-й класс). В такой формулировке это звучит…