[Перевод] Распаковываем архив gzip вручную

Уровень сложности Средний Время на прочтение 5 мин Количество просмотров 4.3K Блог компании RUVDS.com Алгоритмы *Сжатие данных *Clojure * Туториал Перевод Автор оригинала: Thomas Tayac

В этой небольшой статье мы создадим архив 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. Также хорошо эта тема раскрыта на странице Википедии, посвящённой традиционным кодам Хаффмана.

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

Значение литерала	Битов	Код
0 — 143	8	от 00110000 до 10111111
144 — 255	9	от 110010000 до 111111111
256 — 279	7	от 0000000 до 0010111
280 — 287	8	от 11000000 до 11000111

Чтобы декодировать коды Хаффмана, нам потребуется прочитывать вплоть до 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-канале 🚀

Теги:

• ruvds_перевод
• gzip
• архивирование данных
• clojure
• deflate
• коды хаффмана

Хабы:

• Блог компании RUVDS.com
• Алгоритмы
• Сжатие данных
• Clojure

Источник