В рамках очередной лабораторной работы мы с коллегами столкнулись с задачей разбора шестнадцатеричного дампа файла PNG. По стандарту RFC 2083 формат PNG хранит пиксельные данные, сжатые алгоритмом Deflate. Поэтому при разборе дампа нам потребовалось распаковывать сжатые данные алгоритмом Inflate.
Разбор проводим на следующем изображении размера 4х4 пиксела:
Сжатые при помощи 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
