Распаковка данных, сжатых алгоритмом Deflate с фиксированными кодами Хаффмана на примере формата PNG

В рамках очередной лабораторной работы мы с коллегами столкнулись с задачей разбора шестнадцатеричного дампа файла PNG ^[1]. По стандарту RFC 2083 ^[2] формат PNG хранит пиксельные данные, сжатые алгоритмом Deflate ^[3]. Поэтому при разборе дампа нам потребовалось распаковывать сжатые данные алгоритмом Inflate.

Разбор проводим на следующем изображении размера 4х4 пиксела:

Сжатые при помощи Deflate стандарта RFC 1951 ^[4] потоки данных хранятся в PNG в формате zlib ^[5] стандарта RFC 1950 ^[6], мы и будем пользоваться этим стандартом при разборе. Заголовок zlib определяет настройки Deflate. Он имеет следующую структуру:

Подробнее о полях:

• CMF (Compression method and flags). Этот байт разделен на 2 ячейки по 4 бита в каждой: CM (Compression method), CINFO (Compression info).
• CM (Compression method). Данное поле определяет метод сжатия, используемого в файле. CM = 8 обозначает, что используется Deflate с размером окна до 32 килобайт.
• CINFO (Compression info). Когда CM = 8, CINFO — это логарифм с основанием 2, задающий значение размера окна минус 8 (CINFO = 7, задает размер окна, равный 32 килобайтам).
• FLG (Flags). Этот байт разделен на части следующим образом: FCHECK, FDICT, FLEVEL.
• FCHECK (check bits for CMF and FLG). Рассмотрим значение выражения sum = (CMF * 256 + FLG) как шестнадцатибитное целое число без знака. Данное поле дополняет FLG так, чтобы значение sum было кратно 31.
• FDICT (Preset dictionary). Если данный флаг установлен, то описатель словаря DICT следует сразу за байтом FLG. Распаковщик может использовать значение данного поля для определения словаря, который использовался при сжатии.
• FLEVEL (Compression level). Это поле используется особыми алгоритмами сжатия. Deflate (CM = 8): 0 — наиболее быстрое сжатие, 1- быстрое сжатие, 2 — сжатие по умолчанию, 3 — максимальное сжатие (наиболее медленно). Значение данного поля не учитывается при распаковке. Используется для того, чтобы указать, имеет ли смысл, дополнительное сжатие.

После DICT (если установлен FDICT) идет поток сжатых данных, длина которого для PNG зависит от поля CHUNK_LENGTH структуры IDAT. В конце порции zlib идет контрольная сумма ADLER-32 ^[7], высчитанная по несжатым данным по алгоритму Adler-32.

В нашем случае заголовок zlib имеет следующий вид:

Из заголовка выясняем, что словарь не используется (FDICT = 0).

Сжатые данные для нашей картинки:

63 F8 3F 93 E1 3F 03 C3 CC FF 20 1A C8 00 22 24 0E 58 12 85 33 D3 F8 3F 03 32 07 44 03 00 AA 05 23 77

Биты далее считываются непрерывно по байтам. В байте идем от последнего бита к первому (например, в потоке данных последовательно идут 2 байта: 63 F8 (0b01100011 0b11111000), тогда должны получить следующую последовательность битов: 1100011000011111).

Первым битом в считываемой последовательности идет флаг BFINAL, указывающий, является ли данная порция данных последней. Следующие 2 бита BTYPE указывают тип сжатия: 00 — без сжатия, 01 — сжатие с фиксированными кодами Хаффмана, 10 — сжатие с динамическими кодами Хаффмана, 11 — значение зарезервировано.

Таблица для фиксированных кодов Хаффмана:

Таблица смещений:

Таблица длин:

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

Данные, которые мы считываем должны быть переведены в фиксированные значения. Ниже представлена формула перевода:

lit value = data — base + left bound, где
lit value — фиксированные значение,
base — столбец из таблицы 1,
left bound — левое число из столбца распакованных значений из таблицы 1.

При считывании данных, мы можем однозначно определить, к какому промежутку фиксированных значений из таблицы 1 оно соответствует благодаря тому, что префиксы каждого промежутка различны.

К примеру, выберем из нашей последовательности 2 байта F8 и 3F. Последовательность бит, которая получилась 0001111111111100. Пусть текущая позиция считывания 4, считываем далее 7 бит (минимальная количество битов), получаем префикс 1111111, который соответствует промежутку 2. Из этого получается, что длина считываемого кода равна 9.

0b111111111 = 0d511

Используя формулу, приведенную выше, получим, что число, которое было закодировано равно 255 = 511 — 400 (0b110010000) + 144.

Рассмотрим случай, когда у нас вместо фиксированного значения поток данных содержит информацию о длине и обратном смещении, т.е. считываемое значение попадает в 3-ий промежуток. В нашем варианте это будет подпоследовательность:

20 1A C8 ( 00000100 01011000 00010011).

Считываем первые 7 бит (0b0000010), которые попадают в промежуток 3. По формуле переводим в число. Это будет число 257 = 1 — 0 + 256. Далее используем таблицу 3. Код 257 означает, что количество дополнительных битов, которое необходимо считать равно 0. А длина по третьему столбцу равна 3. Если дополнительные биты есть, то они считываются в обратном порядке. Эти биты определяют число, которое мы прибавляем к длине.

Далее считываем 5 бит (0b00101 = 0d5), которые определяют обратное смещение. В нашем случае это число 5. Из таблицы 2 понятно, что нам надо считать 1 дополнительный бит. Считываем его в обратном порядке. Получилось 1 (0d1). Прибавляем это число к минимальному расстоянию из столбца 3. И из этого следует, что наше обратное смещение равно 7 + 1 = 8.

Что же это означает? Например, мы считали 9 значений: 0 255 153 0 255 0 0 153 255. Обратное расстояние показывает, на сколько значений нам надо сместиться в этом потоке назад, т.е. мы будем на втором значении — 255. Длина, которая у нас равна 3, показывает, что нам надо взять 3 значения в из потока данных, начиная со значения, на котором мы стоим, т.е. 255 153 0. Если длина больше, чем смещение, то мы возвращаемся на начальную позицию и считываем заново в исходном порядке до тех пор, пока не считаем количество значений, равное длине. Допустим, у нас получилась длина 7, а обратное смещение равно 2. Мы смещаемся на 2 значения, т.е. наша позиция на предпоследнем числе — 153. Последовательность которая получилась равна 153 255 153 255 153 255 153. В конечном счете, когда распаковщик считывает очередное фиксированное значение, равное нулю, он завершает свою работу.

Полный разбор дампа:

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

Исходное изображение ^[8]

Автор: thezebrazzz

Источник ^[9]