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

в 10:02, , рубрики: Deflate, Hamming code, PNG, Алгоритмы, сжатие данных

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

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

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

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

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

1 байт 1 байт 4 байта
CMF FLG DICTID
4 бита 4 бита 2 бита 1 бит 5 бит
CINFO СМ FLEVEL FDICT FCHECK

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

  • 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, высчитанная по несжатым данным по алгоритму Adler-32.

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

78 DA 0111 1000 11 0 11010
Window size = 32K Compression method = Deflate Compression level = fastest Dictionary is used = false Check bits

Из заголовка выясняем, что словарь не используется (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 — значение зарезервировано.

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

Распакованное значение Количество битов Коды base
0 — 143 8 От 00110000 до 10111111 00110000
144 — 255 9 От 110010000 до 111111111 110010000
256 — 279 7 От 0000000 до 0010111 0000000
280 — 287 8 От 11000000 до 11000111 11000000

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

Коды Доп. биты Расстояние Коды Доп. биты Расстояние Коды Доп. биты Расстояние
0 0 1 10 4 33 — 48 20 9 1025 — 1536
1 0 2 11 4 49 — 64 21 9 1537 2048
2 0 3 12 5 65 — 96 22 10 2049 — 3072
3 0 4 13 5 97 — 128 23 10 3073 — 4096
4 1 5, 6 14 6 129 — 192 24 11 4097 — 6144
5 1 7, 8 15 6 193 — 256 25 11 6145 — 8192
6 2 9 — 12 16 7 257 — 384 26 12 8193 — 12288
7 2 13 — 16 17 7 385 — 512 27 12 12289 — 16384
8 3 17 — 24 18 8 513 — 768 28 13 16385 — 24576
9 3 25 — 32 19 8 769 — 1024 29 13 24577 — 32768

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

Коды Доп. Биты Длина Коды Доп. Биты Длина Коды Доп. Биты Длина
257 0 3 267 1 15, 16 277 4 67 — 82
258 0 4 268 1 17, 18 278 4 83 — 98
259 0 5 269 2 19 — 22 279 4 99 — 114
260 0 6 270 2 23 — 26 280 4 115 — 130
261 0 7 271 2 27 — 30 281 5 131 — 162
262 0 8 272 2 31 — 34 282 5 163 — 194
263 0 9 273 3 35 — 42 283 5 195 — 226
264 0 10 274 3 43 — 50 284 5 227 — 257
265 1 11, 12 275 3 51 — 58 285 0 258
266 1 13, 14 276 3 59 — 66      

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

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

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. В конечном счете, когда распаковщик считывает очередное фиксированное значение, равное нулю, он завершает свою работу.

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

01100011 FINAL CHUNK, FIXED HUFFMAN
11111000 48 — 48 + 0 = 0 — FILTER: NONE
00111111 511 — 400 + 144 = 255
10010011 409 — 400 + 144 = 153
11100001 48 — 48 + 0 = 0
00111111 511 — 400 + 144 = 255
00000011 48 — 48 + 0 = 0
11000011 48 — 48 + 0 = 0
11001100 409 — 400 + 144 = 153
11111111 511 — 400 + 144 = 255
00100000 2 — 0 + 256 = 258 LENGTH=4
00011010 5 DISTANCE=7+1=8
11001000 1 — 0 + 256 = 257 LENGTH=3
00000000 6 DISTANCE=9+0=9
00100001 1 — 0 + 256 = 257 LENGTH=3, 2 DISTANCE=3
00100100 9 — 0 + 256 = 265 LENGTH=11+0=11
00001110 7 DISTANCE=13+0=13
01011000 3 — 0 + 256 = 259 LENGTH=5
00010010 9 DISTANCE=25+4=29
10000101 10 — 0 + 256 = 266 LENGTH=13+0=13
00110011 7 DISTANCE=13+0=13
11010011 409 — 400 + 144 = 153
11111000 99 — 48 + 0 = 51
00111111 511 — 400 + 144 = 255
00000011 48 — 48 + 0 = 0
00110010 9 — 0 + 256 = 265 LENGTH=11+1=12
00000111 7 DISTANCE=13+0=13
01000100 2 — 0 + 256 = 258 LENGTH=4
00000011 5 DISTANCE=7+1=8
00000000 0 — 0 + 256 = 256 END
10101010 ADLER
00000101 ADLER
00100011 ADLER
01110111 ADLER
0
255 153 0 255
0 0 153 255
255 153 0 255
255 0 0 255
0
0 0 153 255
255 153 0 255
255 0 0 255
255 153 0 255
0
255 153 0 255
255 0 0 255
255 153 0 255
0 153 51 255
0
255 0 0 255
255 153 0 255
0 153 51 255
255 153 0 255

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

Исходное изображение

Автор: thezebrazzz

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js