В этой небольшой статье мы создадим архив gzip, после чего разберём его внутренние составляющие и просмотрим начинку. Избегая лишней сложности, в качестве содержимого для сжатия мы просто запишем в изначальный файл 8 символов a.

$ echo "aaaaaaaa" > test.out
$ xxd test.out
00000000: 6161 6161 6161 6161 0a     aaaaaaaa.

Файл получился размером 9 байт — 8 символов a плюс перевод каретки в конце.

Теперь архивируем его. Сделаем это командой gzip -1, поскольку так мы задействуем самый быстрый метод сжатия, который позволит нам лучше разобрать процесс.

$ gzip -1 test.out
$ xxd test.out.gz
00000000: 1f8b 0808 bf35 6a61 0403 7465 7374 2e6f  .....5ja..test.o
00000010: 7574 004b 4c84 002e 00b6 66d7 ad09 0000  ut.KL.....f.....
00000020: 00

Дисклеймер: эту статью я писал в целях обучения, так что мог допустить некоторые ошибки. Мне нравится заниматься низкоуровневым программированием, но моя основная деятельность сосредоточена на веб-разработке для Microsoft Teams.

▍ Информация gzip

Первые несколько байтов вполне понятны:

1. 1f8b — «магический», жёстко закодированный заголовок gzip.
2. 08 — означает метод сжатия DEFLATE.
3. 08(00001000) — бит 3 установлен, значит будет присутствовать имя файла.
4. bf35 6a61 — временна́я метка UTC Saturday, October 16, 2021 2:15:27 AM
5. 04 — использование самого быстрого алгоритма (для этого мы и сопроводили команду аргументом -1).
6. 03 — операционная система Unix (нужна для LF/CLRF).

Следующие несколько байтов описывают имя файла:

74 65 73 74 2e 6f 75 74 00
t  e  s  t  .  o  u  t  NUL

▍ Сжатые данные

Данные начинаются с байта 0х13 со значением 4b. Для их декодирования нужно будет рассматривать биты поочерёдно, так как при упаковке информации через DEFLATE они могут пересекать границу байта. Нередко встречаются коды длиной 5 или 9 бит.

$ xxd -s 19 -b test.out.gz
00000013: 01001011 01001100 10000100 00000000 00101110 00000000  KL....
00000019: 10110110 01100110 11010111 10101101 00001001 00000000  .f....
0000001f: 00000000 00000000

Разберём полученный вывод. К сожалению, xxd выводит байты по одному в порядке от старшего бита (MSB, most significant bit) к младшему (LSB, least significant bit). Но в gzip байты сжимаются с обратным порядком битов. Значит, нам придётся реверсировать строки байт за байтом. Вдобавок к этому, мы определим несколько вспомогательных функций, которые помогут нам в вычислениях.

(require [clojure.string :as str])

(defn reverse-str-bytewise [s] 
  (->> (str/replace s " " "") 
       (partition 8) 
       (map #(apply str %)) 
       (map str/reverse)))

(reverse-str-bytewise "01001011 01001100 10000100 00000000 00101110 00000000")
; ("11010010" "00110010" "00100001" "00000000" "01110100" "00000000")
; ^^^^^^ Этот поток битов мы будем анализировать ниже ^^^^^^

(defn str->bits [s] (->> s (str/reverse) (mapv #(if (= % \1) 1 0))))

(str->bits "110010")
; [0 1 0 0 1 1]

(defn bin->dec [s] 
  (->> s 
       (str->bits) 
       (reduce-kv (fn [acc, i, elem] 
                    (if (= elem 1) (+ acc (bit-shift-left 1 i)) acc)) 
                  0))

(bin->dec "10001")
; 17

Код выше написан на языке Clojure. Ничего страшного, если он вам непонятен. Это просто кое-какие вспомогательные функции.

▍ Декодирование блока

8bitswise: 11010010   00110010 00100001 00000000 01110100 00000000
separated: 1 10 10010001 10010001 0000100 00000 00111010 0000000 00

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

Далее нам нужно декодировать коды Хаффмана. Если вы не читали спецификацию алгоритма DEFLATE, то коды Хаффмана представляют просто множество общепринятых кодов размером от 7 до 9 бит. Это префиксные коды, что позволяет легко их разграничивать при побитовом считывании.

Если вы не до конца понимаете, о чём речь, то для начала лучше будет прочитать разделы 3.2.5 и 3.2.6 (статические коды Хаффмана) документации DEFLATE. Также хорошо эта тема раскрыта на странице Википедии, посвящённой традиционным кодам Хаффмана.

Ниже показана таблица этих кодов из документации:

Чтобы декодировать коды Хаффмана, нам потребуется прочитывать вплоть до 9 очередных битов. Мы будем считывать их по одному, пока не встретим префикс, позволяющий распознать отдельный символ. Этот процесс можно представить как прохождение вниз по ветвям дерева Хаффмана.

Примечание: декодеры Хаффмана обычно сразу считывают 9 бит, ищут их в таблице и «возвращают на место» те, которые не потребовались, не расходуя ценное процессорное время на побитовое чтение.

Наши следующие 9 бит представлены как 100100011 — здесь мы видим префикс 100, а значит это литерал между 0 и 143 размером всего 8 бит (1001 0001).

Напомню, что коды Хаффмана упаковываются в прямом порядке битов, но как целое число интерпретируются в обратном порядке. К чему это недоумение? ¯\(ツ)/¯ …

Декодирование даёт нам: val = (10010001 минус 00110000) = 145 — 48 = 97

97 — это код ASCII для a. Прекрасно!

Декодируя остальные биты, получаем:

1 10 10010001 10010001 0000100  00000       00111010    0000000    00
     97       97         260     0            58          256      -
     'a'      'a'    repeat 6x  1 behind    0x10 (LF)    HALT     <padding>
     LIT      LIT       LEN     DIST        LIT         

Это наши 8 символов а! Два литерала, за которыми идут 6 а, сопровождаемые переводом каретки.

repeat 6x 1 behind — это код длины + расстояния (LEN, DIST). Он сообщает декодеру о повторении символа, который был только что декодирован. В нашем случае это символ а.

Без лишней мороки мы закодировали 8 а и перевод каретки (изначально 72 бита) в 46 бит, включая 2 бита заполнения.

Но мне кажется, что gzip способен на большее. Он мог бы просто закодировать одну а, сопроводив её кодом 261, означающим 7-кратное повторение. Сначала я решил, что дело в выполнении gzip -1, но и выполнение стандартной gzip даёт тот же результат. Не могу понять, почему так. Может, кто-то из читателей объяснит причину.

▍ Завершение – контрольная сумма и размер

Мы подошли к завершению файла gzip. Дальше должен идти код CRC32. Обратившись к онлайн-инструменту crc32, мы видим, что несжатые 8 символов а с переводом каретки дадут ad d7 66 b6. Действительно, если ещё раз взглянуть на hex-поток:

$ xxd test.out.gz
00000000: 1f8b 0808 bf35 6a61 0403 7465 7374 2e6f  .....5ja..test.o
00000010: 7574 004b 4c84 002e 00b6 66d7 ad09 0000  ut.KL.....f.....
00000020: 00                    ^^^^^^^^^^
                                  Here!

Мы отчётливо увидим b6 66 d7 ad в порядке байтов от младшего к старшему. Это контрольная сумма CRC.

Следующие 4 байта 09 00 00 00 представляют 9 байтов в порядке от младшего к старшему. Получается, мы декодировали 9 байтов, которые соответствуют 9 байтам входного файла.

▍ Обобщение

Итак, вот вся структура файла:

gzip info: 1f8b 0808 bf35 6a61 0403 
filename: 7465 7374 2e6f 7574 00 
DEFLATE data: 4b 4c 84 00 2e 00
crc32: b6 66 d7 ad 
size: 09 00 00 00    

Конечно, это лишь вершина айсберга — основной потенциал алгоритма gzip заключается в динамических кодах Хаффмана. В дальнейшем я планирую написать вторую статью по этой теме, но она уже будет акцентироваться не на ручной реализации, а на объяснении принципа разворачивания таблиц Хаффмана. Я пробовал реализовывать динамические коды Хаффмана от руки, но через час моё терпение иссякло.

Если найдёте какие-то ошибки, можете сообщить о них на GitHub или отписать мне на почту thomastayac@gmail.com.

Скидки, итоги розыгрышей и новости о спутнике RUVDS — в нашем Telegram-канале ????