Как это устроено: структура изображений в формате PNG. Разбираем на примере
Привет! В этой статье я познакомлю вас с устройством изображений в формате PNG, а так же с механизмом работы алгоритма Deflate. Мы на примере рассмотрим все аспекты этой темы. Надеюсь, вам будет интересно.
Дисклеймер
Данный материал не призван быть максимально объективным и академически верным. Автор статьи (в дальнейшем — я и другие личные местоимения первого лица) мог упускать некоторые моменты, а некоторые рассматривать лишь с одной стороны. Статья была рождена на свет исключительно из спортивного интереса, а также желания лучше понимать то, с чем я работаю каждый день. Если ты, дорогой читатель, не согласен со мной или считаешь, что я забыл дописать что-то очень важное, то, пожалуйста, напиши об этом в комментариях. Этим сотрудничеством мы сможем добиться ликвидации пробелов в знаниях и, быть может, сделать мир чуточку лучше.
Тем не менее, данная статья поможет начинающим примерно понять внутреннее устройство PNG (о котором и идёт речь), что создаст основу для дальнейшего развития.
В разделе «материалы» я оставил ссылки на полезные статьи и спецификации PNG и zlib, которые помогли мне понять всё то, о чём я написал (и даже больше). Иногда я прямо указываю на них, о чём пишу в виде «ссылка #{номер ссылки}».
Пример изображения
Внутреннее устройство PNG мы будем разбирать на примере маленького изображения 2 x 2 пикселя. Ссылку на него я оставлю в разделе «материалы» в нижней части страницы.
Вот так выглядит увеличенная копия изображения:
Долой длинные вступления. Начинаем!
Структура PNG
Не буду грузить читателя описанием формата, историей его появления и прочими вещами, которые никаким образом не относятся к теме статьи, а сразу же без всяких прелюдий перейду к рассмотрению структуры.
Любой файл PNG начинается со следующей последовательности байтов (в шестнадцатеричном представлении):
Это так называемая подпись PNG (PNG file signature). 50 4E 47 — как раз и соответствуют символам P N и G из таблицы ASCII. Наличие данной строки указывает программе-декодеру, что она имеет дело с классическим изображением формата PNG, которое состоит из последовательности чанков (об этом ниже), первый из которых — это IHDR, а последний — IEND. Отчасти именно эта подпись позволяет большинству программ преспокойно прочитать изображение PNG, даже если у него в качестве расширения указан, скажем, JPEG.
PNG имеет удивительно логичную и лаконичную структуру, что позволяет без лишних затруднений читать, изменять и создавать изображения в этом формате. Как я уже выше упомянул, в основе структуры любого PNG-изображения лежит последовательность чанков (от англ. «chunk» — кусок, ломоть; я буду использовать именно это слово, вместо соблазнительного «блок», так как это позволит избежать путаницы), которые следуют друг за другом.
Каждый чанк состоит из следующих обязательных частей:
1. Length — информация о длине чанка. Нужна для того, чтобы декодер знал, когда заканчивается тот или иной чанк. Записывается при помощи 4 байт.
2. Chunk type — тип чанка. У каждого из них есть своё собственное предназначение, поэтому программа интерпретирует их по-разному. 4 байта.
3. Chunk data — непосредственно данные, которые содержит чанк. Длина зависит от того, что было указано в поле Length. Может быть пустым.
4. CRC — контрольная сумма Length и Chunk type, высчитанная при помощи алгоритма CRC-32. 4 байта.
Все чанки можно разделить на обязательные (critical) и вспомогательные (ancillary). Самые догадливые уже всё поняли, но я, всё же, опишу несколькими словами их различия. Обязательные чанки должны присутствовать в любом PNG-изображении, а вспомогательные — нет (вот это новость!). Отсутствие обязательного чанка вызовет ошибку, а вот отсутствие вспомогательного, даже если на него ссылается какой-нибудь другой чанк, декодер проигнорирует.
Названия обязательных чанков всегда начинаются с прописной буквы, а вспомогательных — со строчной (например IDAT — обязательный, а вот tIME — нет).
К обязательным чанкам относятся:
IHDR — содержит сведения об изображении: ширина, высота, глубина цвета и другие.
PLTE — содержит перечень цветов, используемых в изображении. Является обязательным, но в некоторых случаях может отсутствовать. Об этом немного позже.
IDAT — чанк, содержащий непосредственно данные изображения.
IEND — чанк, указывающий программе-декодеру на окончание файла. Данных не содержит.
Перечень вспомогательных чанков можно найти в документации PNG (ссылка #1), а обязательные мы разберем немного подробнее:
IHDR
Это самый первый из обязательных чанков. Важно запомнить, что он должен располагаться в самом начале документа. Состоит из 13 байт:
4 байта — ширина изображения
4 байта — высота изображения
1 байт — глубина цвета (bit depth)
1 байт — цветовая модель (color type)
1 байт — метод сжатия
1 байт — метод фильтрации
1 байт — метод чересстрочной развертки
Наиболее важными для нас являются 9 и 10 байты. Давайте рассмотрим их чуть подробнее.
Color type
Используемая цветовая модель. Может принимать следующие значения:
-
010 (0002) — grayscale
Самое первое и самое простое значение. Каждый одноканальный пиксель кодируется 1, 2, 4, 8 или 16-битовым целым числом, которое выражает уровень яркости белого цвета. -
210 (0102) — RGB/TrueColor
Три канала: красный, зеленый и синий. Каждый из каналов (для одного пикселя) кодируется 8 или 16-битным числом. -
310 (0112) — индексированные значения
Содержит индексы каналов, которые находятся в чанке PLTE. Количество битов: 1, 2, 4 или 8. -
410 (1002) — grayscale и альфа-канал: для каждого пикселя указывается прозрачность
2 канала: оттенок серого и альфа-канал. Каждый канал кодируется 8 или 16 битами. -
610 (1102) — RGBA
То же самое, что и RGB, только с добавлением альфа-канала, который отвечает за степень прозрачности.
В виде таблицы:
| Bits per pixel | ||||||
|---|---|---|---|---|---|---|
| Color option | Channels | BIts per channel | ||||
| 1 | 2 | 4 | 8 | 16 | ||
| Grayscale | 1 | 1 | 2 | 4 | 8 | 16 |
| RGB | 3 | 24 | 48 | |||
| Indexed | 1 | 1 | 2 | 4 | 8 | |
| Grayscale and alpha | 2 | 16 | 32 | |||
| RGBA | 4 | 32 | 64 | |||
Глубина цвета
Цветовая глубина — значение, представляющее собой количество битов, которое необходимо для кодирования одного канала. Например, если у нас color type равен RGB, а глубина цвета — 8 бит, то количество битов, необходимое для кодирования 1 пикселя будет равняться 24.
То, что я написал выше, очень важно запомнить или записать, так как эта информация обязательно пригодится нам при расшифровке чанка IDAT.
В нашем случае чанк IHDR является следующей строкой (в шестнадцатеричном представлении):
Теперь нам совершенно не составит труда всё это расшифровать:
Ширина изображения — 2 пикселя.
Высота изображения — 2 пикселя.
Глубина цвета — 16 пикселей на канал.
Color type — 2.
Сжатие, фильтрация и чересстрочная развертка — по нулям.
Что же это означает? Color type равняется 2, значит используется цветовая модель RGB, т.е. комбинация красного, зелёного и синего каналов. Глубина цвета равняется 16, а значит каждый из этих каналов закодирован парой байтов. Отсюда также несложно понять, что для кодирования одного пикселя изображения используется 48 бит или 6 байт. Идём дальше.
PLTE
Считается обязательным чанком, но фактически является таковым только для color type 3. PLTE содержит от 1 до 256 трёхбайтовых цветов:
1 байт — красный (от 0 до 255)
1 байт — зелёный (от 0 до 255)
1 байт — синий (от 0 до 255)
Подробно на нём останавливаться я не собираюсь, так как на практике color type 3 встречается очень редко. Самые любознательные смогут найти исчерпывающую информацию в спецификации PNG (ссылка #1).
IDAT
Наконец-то мы добрались до содержимого нашего изображения. Чанк IDAT начинается с 4 байтов — 49 44 41 54, которые, собственно, и декодируется в «IDAT». Согласно спецификации PNG, содержимое IDAT сжато методом Deflate и упаковано в формат zlib. В общем случае чанк состоит из следующих обязательных частей:
- Zlib header, содержащий информацию о методе, степени сжатия и некоторую служебную информацию.
- Последовательность блоков со сжатой информацией, следующих друг за другом.
- Последовательность битов, представляющих собой контрольную сумму несжатых данных, сгенерированную при помощи алгоритма Adler-32
Давайте немного подробнее.
Zlib header
Спецификация RFC 1950 говорит нам, что zlib header должен состоять из двух байтов. Первый байт – это Compression Method and Flags (CMF), который в свою очередь содержит:
- Первые 4 бита (от младшего к старшему) — Compression Method (CM). Если CM равен 8, то это означает, что используется алгоритм Deflate (о котором я подробнее расскажу чуть дальше).
-
Последние 4 бита – Compression Info (CINFO). Этот параметр отвечает за размер окна (речь о так называемом «скользящем окне», которое используется в алгоритме Deflate (подробнее об этом я напишу в соответствующем пункте) и находится следующим образом:
\(C=\log _{ 2 }{ W } -8,\)
где W — размер окна, C — CINFO.
Например, если CINFO равен 7, то
\(W={ 2 }^{ 7+8 },\)
что равняется 35768 байтам или 32 килобайтам.
Второй байт — Flags (FLG), содержит:
- Compression Level (FLEVEL) – степень сжатия.
- Preset Dictionary (FDICT) – Если он равен 1, то за байтом FLG должен идти словарь. Если я правильно понял, то это просто последовательность несжатых байтов, которая необходима для кодирования/декодирования содержимого. Словарь полезно использовать при небольших размерах файла.
- Check bits for CMF and FLG (FCHECK) – число, которое дополняет CMF * 256 + FLG до такого значения, чтобы оно было кратно 31.
Схематично Zlib header можно изобразить так:
| CMF | FLG | DICT (IF FDICT === 1) | |||
|---|---|---|---|---|---|
| CINFO | CM | FLEVEL | FDICT | FCHECK | |
| 0111 | 1000 | 11 | 0 | 11010 | |
В нашем случае: 78 DA или в двоичном представлении 0111100011011010:
CMF:
- CM – 1000, что в десятичной равно 8. Согласно спецификации RFC 1950 – это Deflate.
- CINFO – 0111, в десятичной — 7. Мы можем сразу же найти размер окна:
\(7+8=15;\)
\(\log _{ 2 }{ x } =15;\)
\(x={ 2 }^{ 15 }\) — размер окна равен 32 килобайта.
FLG:
- FLEVEL — 112 или 310. (RFC 1950) – compressor used maximum compression, slowest algorithm – максимальное сжатие.
- FDICT – 0 – словарь не используется.
- FCHECK – 110102 или 2610
Проверим. Для удобства переведём всё это в десятичную систему:
FLG — FCHECK: \({ 11000000 }_{ 2 }={ 192 }_{ 10 }\)
Считаем:
\(\dfrac { 30912 }{ 31 } =997,161290…\) — не кратно 31
Ближайшее целое число такое, что \(x\times 31\ge(120\times 256+192)\), это 998.
Значит \(998\times 31-30912=26\)
Получилось 26. Это и есть наш FCHECK. Всё правильно.
Изучаем сжатые данные
Это самый скучный и однообразный процесс. Внутри этих блоков мы ожидаем увидеть последовательность строк, каждая из которых начинается со значения FILTER — фильтра (речь о фильтрации, используемой при сжатии для увеличения его эффективности). FILTER может принимать значения от 0 до 4, которые носят названия «None», «Sub», «Up», «Average», «Paeth». Для чего это нужно? При больших размерах файла фильтрация может помочь сократить занимаемое изображением пространство. Например, фильтр «Sub» означает, что нужно сложить значение текущего пикселя со значениями предыдущих пикселей в строке. Вот так выглядит формула для декомпрессии с использованием «Sub»:
где Raw(x) — искомое значение, Raw(x-bpp) — сумма значений уже декодированных байтов в строке, Sub(x) — отфильтрованное значение текущего пикселя.
Подробнее про фильтрации можно почитать в спецификации PNG (ссылка #1).
Считываем блоки, помня про спецификацию RFC 1950, которая гласит, что блок начинается с трёхбитного заголовка:
1 бит – BFINAL. Устанавливается в 1, если данный блок последний.
2 бита – BTYPE. Содержит информацию о типе сжатия:
- 00 – без сжатия
- 01 – сжатие с фиксированными кодами Хаффмана
- 10 – сжатие с динамическими кодами Хаффмана
- 11 – зарезервированное значение. Установка его вызовет ошибку.
Внимательность: каждый байт рассматривается в виде последовательности битов, идущих от младшего к старшему. Например, байт 11100001 мы прочитаем как 10000111.
В работе будем использовать таблицу фиксированных кодов Хаффмана (для фиксированных значиний, разумеется), таблицу смещений и таблицу длин. Давайте их и рассмотрим.
Таблица фиксированных кодов Хаффмана
Как мы будем её использовать? Очень просто, на самом деле. Сначала берём первые 7 битов (минимальное значение, см. таблицу), после этого смотрим на префикс нашей получившейся последовательности. Префиксом называется подстрока, начинающаяся с 1 символа. Таблица кодов Хаффмана построена таким образом, чтобы по ней можно было однозначно декодировать наше значение, так как ни один из кодов не является подстрокой для другого кода. Это позволит нам по префиксу восстановить правильное значение. Для тех, кто не очень понял, объясню на примере:
Допустим, у нас есть последовательность 110011000011001. Берём первые 7 битов — 1100110. Теперь смотрим в таблицу и в третьем столбце находим такой промежуток, чтобы наша последовательность при соответствии старших битов однозначно попадала в него. Начнём с первой строки — промежуток равен [00110000, 10111111], смотрим:
Нижними подчёркиваниями я обозначил любые значения, ибо они нам в данный момент безразличны.
Как видим, наше значение не попадает в первый промежуток. Идём дальше:
А вот тут уже интереснее. Значение действительно попадает в промежуток. Теперь смотрим во второй столбец и видим, что необходимое количество битов — 9. Значит берём еще два бита, после чего наша измученная последовательность выглядит так: 110011000.
Теперь, чтобы восстановить исходное значение, нужно воспользоваться следующей формулой:
V — искомое значение, D — наша последовательность, B — нижнее значение из 3 столбца таблицы, L — нижнее значение из 1 столбца таблицы.
А вот и сама таблица (ссылка #3):
| Таблица фиксированных кодов Хаффмана | |||
|---|---|---|---|
| Коды символов | Длина | Диапазон | |
| 0-143 | 8 | от 00110000 до 10111111 | |
| 144-255 | 9 | от 110010000 до 111111111 | |
| 256-279 | 7 | от 0000000 до 0010111 | |
| 280-287 | 8 | от 11000000 до 11000111 | |
Код 256 — признак конца блока, символы 286 и 287 лишние.
Таблицы длин и обратных смещений
Тут тоже нет ничего сложного. Если код, который мы высчитали по предыдущей таблице попадает в промежуток от 257 до 285 (то есть, 3 и 4 случаи, исключая код 256, 286 и 287), то наше итоговое значение будет высчитываться по длине и обратному смещению. Но что же это? А это и есть результат работы Deflate. Название таблицы говорит само за себя. Когда мы натыкаемся на подобную команду, нужно отступить назад на количество битов, равное обратному смещению и взять количество битов, равное длине.
Таблица длин (ссылка #4):
| Таблица длин | ||
|---|---|---|
| Коды | Доп. биты | Диапазон длин |
| 257-264 | 0 | 3-10 |
| 265-268 | 1 | 11-12, 17-18 |
| 269-272 | 2 | 19-22, 31-34 |
| 273-276 | 3 | 35-42, 59-66 |
| 277-280 | 4 | 67-82, 115-130 |
| 281-284 | 5 | 131-162, 227-257 |
Код 285 обозначает длину 258
Внимательность: пара замечаний по таблице. Я так понимаю, она была сгруппирована по доп. битам и сделано это лишь с целью экономии места. Поэтому немного объясню. Первая колонка содержит диапазоны кодов, а вторая — соответствующие им диапазоны длин. То есть, например, коду 265 соответствуют длины 11-12, 266 — 12-13, 267 — 13-14, ну и так далее со всеми остальными. Дополнительные биты нужны для того, чтобы в этом диапазоне длин выбрать нужное значение. Если, например, у нас длины равны 12-13 и есть 1 дополнительный бит, то 0 будет указывать на 12, а 1 — на 13. Думаю, логика примерно ясна.
Таблица обратных смещений:
| Таблица смещений | ||
|---|---|---|
| Коды | Доп. биты | Диапазон смещений |
| 0-3 | 0 | 1-4 |
| 4,5 | 1 | 5-6, 7-8 |
| 6,7 | 2 | 9-12, 13-16 |
| 8,9 | 3 | 17-24, 25-32 |
| 10,11 | 4 | 33-48, 49-64 |
| 12,13 | 5 | 65-96, 97-128 |
| 14,15 | 6 | 129-192, 193-256 |
| 16,17 | 7 | 257-384, 385-512 |
| 18,19 | 8 | 513-768, 769-1024 |
| 20,21 | 9 | 1025-1536, 1537-2048 |
| 22,23 | 10 | 2049-3072, 3073-4096 |
| 24,25 | 11 | 4097-6144, 6145-8192 |
| 26,27 | 12 | 8193-12288, 12289-16384 |
| 28,29 | 13 | 16285-24576, 24577-32768 |
Логика здесь точно такая же. После того, как мы нашли значение длины, считываем еще 5 битов (от младшего к старшему, естественно), переводим в десятичное представление для удобства. Этот код находим в таблице, используем дополнительные биты при необходимости и находим обратное смещение. Поехали дальше, начнём разбирать наш код.
Приступаем
Для удобства переведём всю последовательность в двоичный код (можно написать программу для этого, можно сделать вручную, а можно воспользоваться калькулятором, которых в Интернете полно; лично я предпочитаю первый вариант). Итак, у нас получается код (не забывайте про нули, их здесь может и не быть, но каждый байт обязательно является двоичным восьмибитным числом):
Выглядит эффектно, правда? На самом деле, тут всё просто. Начинаем:
1. Считываем первые 3 бита, заголовок первого блока.
| 0 | 10 | 00110
BFINAL — 0 — блок не последний.
BTYPE — 10 — используются фиксированные коды Хаффмана.
2. На этом этапе нужно брать минимум 7 битов, определять префикс. Далее уже переводить в число, либо считать смещения и длины. Что же мы стоим? Вперёд!
2.1 Берём первые 7 битов: |00110 00| 011010
0011000 — префикс попадает в первую категорию, а значит число должно иметь длину 8 бит. Берем еще один — 00110000.
По формуле находим значение:
\(F=0\)
Первое число равно 0. FILTER:NONE. Идём дальше. Берем еще 7 битов: |11010 10|00|1101 — 2-й промежуток, 9 бит. Находим значение:
Таким же образом проделываем всю остальную работу. Мы помним, что для кодирования 1 пикселя в нашем случае используется 6 байтов. Считаем их всех, а потом ненадолго остановимся:
\({ R }_{ 2 }=421-400+144=165\)
\({ G }_{ 1 }=80-48+0=32\)
\({ G }_{ 2 }=80-48+0=32\)
\({ B }_{ 1 }=160-48+0=112\)
\({ B }_{ 2 }=160-48+0=112\)
Самые смышлёные тут опять же вспомнят, что в данном изображении используется цветовая модель RGB с глубиной цвета 16 бит. Каждый их трёх каналов закодирован двумя байтами. Чтобы получить 16-битное значение мы должны просто конкатенировать два байта. Далее, если мы захотим преобразовать их в 8-битный аналог, то я предлагаю решить следующую пропорцию. Можно, конечно же, просто отбросить второй байт, но тогда есть небольшая вероятность того, что полученное значение будет искажено. Поехали:
\({ 168 }_{ 10 }={ 10101000 }_{ 2 },\)
\({ 165 }_{ 10 }=10100101_{ 2 },\)
\({ 1111111111111111 }_{ 2 }={ 65535 }_{ 10 }\) — конкатенация 255 и 255,
\({ 1010100010100101 }_{ 2 }={ 43173 }_{ 10 }\)
Отсюда x:
\(\dfrac { 65535 }{ 43173 } =\dfrac { 255 }{ x },\)
\(65535\times x=255\times 43173,\)
\(x=\dfrac { 255\times 43173 }{ 65535 },\)
\(x=\left\lceil 167,9 \right\rceil =168\)
Символами \(\lceil\) \(\rceil\) обозначают потолок, то есть округление до целого в большую сторону.
Получилось, что R в нашем случае равен 168. Если мы проделаем то же самое с G и B-каналами, то получим, что цвет нашего первого пикселя в RGB-представлении равен (168, 32, 112). Теперь посмотрим на скриншот:
Мы движемся в верном направлении. А это значит, что нет смысла останавливаться! Второй пиксель декодируем так:
… : 111 111111|11 1111111 | 1 11111111 | 11111111 1 | 1111111 11 |111111 111 | 00110
Путём несложных вычислений получаем наш код: RGB(255, 255, 255) — белый цвет. Всё верно. На этом строка заканчивается, так как её ширина составляет всего 2 пикселя. Приступаем ко второй (и последней) строке:
\(F=48-48+0=0\)
FILTER:NONE
Значение попадает в третий промежуток, давайте разбираться. По формуле получим следующий код:
Заглянем в таблицу длин и получим значения:
1. Длина — 6
2. Доп. биты — 0
Теперь считываем следующие 5 битов, которые являются обратным смещением: \(00101=5\)
По таблице:
1. Доп.биты — 1
2. Расстояние 7,8
Следующий бит скажет скорректирует смещение. Он равен 0, значит фактическое смещение равняется 7.
А вот тут самое интересное. Наш «курсор» находится сразу же после байта со значением FILTER (который равен 0). Вернёмся на 7 байтов назад (обратное смещение) и скопируем 6 байтов (это как раз байты последнего пикселя первой строки):
Вот и всё. Ничего тут страшного нет. Цвет первого пикселя второй строки — RGB(255, 255, 255), что правда. Ух, надо идти вперёд! Я буду краток:
\({ 01000 }_{ 2 }={ 8 }_{ 10 }\)
1. Доп. биты — 3
2. Длина — 17-24
Смещение = \(17+2=19\)
Получаем:
Цвет — RGB(168, 32, 112). В принципе, может показаться, что это всё. Но на самом деле, нет. Считываем дальше:
\(0-0+256=256\)
256 — признак конца блока. Мы закончили.
Итак, что у нас получилось? Две строки по два пикселя. Первый имеет цвет RGB(168, 32, 112), второй RGB(255, 255, 255), третий и четвёртый — RGB(255, 255, 255) и RGB(168, 32, 112) соответственно. Если вы вспомните изображение, то поймете, что это недалеко от правды. Значит, мы всё делаем правильно, что внушает надежду на светлое будущее.
Тем не менее, далее следует блок, который имеет нулевую длину. Честно признаюсь, я не до конца осознал целесообразность его нахождения здесь. Продолжим.
Судя по всему, начало нового блока? Ладно. Сжатия нет, блок последний.
Здесь самый простой вариант — без сжатия. В этом случае после заголовка идёт выравнивание на границу байта (то есть мы должны взять оставшееся количество битов в этом байте). Потом два байта — LEN и еще 2 — NLEN.
LEN — длина несжатых данных, NLEN — дополнение LEN до единицы.
11111111 11111111 — NLEN
Как мы видим, всё действительно так. Единственное, что LEN = 0, т.е. данных нет. Зачем это сделано — непонятно.
Ну и наконец, в самом конце чанка IDAT следует четырёхбайтовая хеш-сумма несжатых данных, высчитанная по алгоритму Adler-32. В нашем случае, хеш-сумма в двоичном представлении выглядит так:
Adler-32
Подробную информацию о том, как работает Adler-32 можно найти по ссылке #5. А мы пока возьмем последовательность расшифрованных байтов и захешируем её.
Последовательность (в десятичном представлении):
Я набросал на PHP простенький код:
$array = explode(' ', $uncompressed);
$start_1 = 1;
$start_2 = 0;
foreach($array as $num)
{
$temp_1 = $start_1 + trim($num);
$temp_2 = $start_2 + $temp_1;
$start_1 = $temp_1;
$start_2 = $temp_2;
}
$hash = sprintf("%016b", $temp_2 % 65521) . sprintf("%016b", $temp_1 % 65521);
Переменная $hash после выполнения кода содержит строку:
Найдите 10 отличий. Хеш-суммы совпадают, а поэтому с полной уверенностью заявляю, что мы сделали всё верно! Со следующего байта уже начинается чанк IEND, с IDAT же мы наконец-то закончили.
Стоит признать, что это было довольно просто. В пункте про алгоритм Deflate мы также рассмотрим декодирование строки (да, для примера возьмем обычную строку) с динамическими кодами Хаффмана.
IEND
Обязательный чанк, который должен следовать после всех остальных. Символизирует окончание PNG-документа и не содержит какой-либо информации.
Deflate
Чтобы сильно не утомлять моего читателя, который к этому моменту мог уже слегка подустать, расскажу лишь то, что встречалось выше. Данные в PNG хранятся в формате zlib и представляют собой последовательность блоков, сжатых при помощи Deflate. Deflate — это алгоритм сжатия, комбинирующий LZ77 и метод Хаффмана. Если очень коротко, то несжатая последовательность обрабатывается при помощи LZ77, после чего получившиеся коды упаковываются при помощи алгоритма Хаффмана.
LZ77
Сам алгоритм довольно сложный, поэтому объясню его принцип, что называется, «на пальцах». LZ77 — это алгоритм сжатия без потерь, основанный на принципе «скользящего окна» (помните я писал про размер окна?), призванный заменять последовательности, встречающиеся чаще одного раза, на ссылки, указывающие на самые ранних из них. Что я имею в виду? Программа поочерёдно считывает последовательность битов, держа «в голове» (то есть в буфере) информацию об уже прочитанных битах. Когда программа натыкается на последовательность, которая уже содержится в буфере, то она полностью заменяется ссылкой, которая представляет собой сведения о смещении и длине последовательности. Смещение может быть как прямым (то есть начинаться от начала окна, либо от произвольной точки), так и обратным (отсчитываться смещение будет в обратном порядке относительно обрабатываемого бита). На самом деле, я не особо уверен в существовании прямого смещения, так как на практике не встречал, но в разных документах я видел упоминания о нём. Проще говоря, программа-интерпретатор получает указания отступить на n шагов назад и взять m байтов. Размер окна — это и есть размер нашего буфера, то есть расстояние от первого бита, который программа еще помнит, до первого бита, который программа уже помнит. Во время кодирования, программа без проблем может заменять комбинации, которые пока еще лежат за пределами окна.
Алгоритм Хаффмана
Еще один алгоритм сжатия без потерь, заменяющий все символы входящей последовательности на специальные коды таким образом, что самые часто встречающие символы образуют самые короткие коды. Алгоритм пробегается по строке, подсчитывая частоту вхождения каждого символа, потом выстраивается очередь с приоритетом, где самыми первыми встраиваются элементы с наименьшей частотой. После чего выстраивается бинарное дерево, в котором каждый символ является концевой вершиной. В конце концов каждый символ получает свой код исходя из того, насколько далеко он располагается относительно корня. Есть смысл объяснять подробнее?
Ладно, уговорили. Допустим, у нас есть строка: «Hello, World!». Поехали:
1. Сначала выстраиваем список «Символ — частота»:
H - 1 e - 1 l - 3 o - 2 , - 1 W - 1 r - 1 d - 1 ! - 1
2. Сортируем его по частоте и создаем очередь. Приоритетом является частота. При этом, элементы с самым низким приоритетом выстраиваются в самом начале:
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 3 | | H | e | , | W | r | d | ! | o | l |
3. Теперь создаем бинарное дерево. Алгоритм такой: Берем первые два элемента и формируем из них мини-дерево, где листьями будут наши элементы. В таблицу записываем сумму приоритетов, помещая его в нужное место:
| 1 | 1 | 1 | 1 | 1 | 2 | 2 | 3 |
| , | W | r | d | ! | o | / \ | l |
H e
Таким же образом делаем со всеми остальными. В итоге получается такое дерево:
| 11 |
/ \
/\ / \
l /\ /\ /\
o /\ , w r w
H e
Общий приоритет — 11. Теперь присвоим коды. Каждая левая ветка — 0, правая — 1. В итоге получается что-то вроде этого:
l - 00 o - 010 H - 0110 e - 0111 , - 100 w - 101 r - 110 d - 111
Теперь нужно заменить нашу последовательность полученными кодами и выстроить таблицу, чтобы интерпретатор мог без проблем её декодировать. В принципе, это всё.
Ближе к теме
Я уже выше писал, но напомню еще раз. Данные состоят из блоков, следующих друг за другом последовательно. Каждый из них содержит заголовок, состоящий из 3 битов (RFC 1950):
1 бит – BFINAL. Устанавливается в 1, если данный блок последний.
2 бита – BTYPE. Содержит информацию о типе сжатия:
- 00 – без сжатия
- 01 – сжатие с фиксированными кодами Хаффмана
- 10 – сжатие с динамическими кодами Хаффмана
- 11 – зарезервированное значение. Установка его вызовет ошибку.
«Без сжатия» означает, что данные представлены в нетронутом виде. Мы рассмотрели работу с подобными данными в подпункте IDAT пункта «структура PNG».
«Сжатие с фиксированными кодами Хаффмана» — данные сжаты с помощью уже заранее предопределенных кодов. Этот способ мы тоже рассмотрели.
«Cжатие с динамическими кодами Хаффмана» — в данном случае, сжатая последовательность состоит из кодов, создаваемых «на лету». Коды и их значения хранятся непосредственно в блоке. Давайте рассмотрим немного подробнее.
Для урока я взял простую последовательность, которая не включает в себя длины и смещения. Тем не менее, работать с подобными данными мы уже умеем, так как это было рассмотрено выше, а метод сжатия значения не имеет, ибо всё происходит точно так же. Также уточню, что строка ниже не содержит заголовка zlib и контрольной суммы. Мы рассматриваем только Deflate.
Пример Deflate с динамическими кодами Хаффмана
Предположим, у нас есть следующая последовательность:
В двоичном представлении:
Считываем по байтам, биты от младшего к старшему. Первые 3 байта — заголовок:
101 — последний блок, динамический Хаффман. Да, информация о типе сжатия берется справа-налево, если мы идём от младшего к старшему. Дальше идут следующие значения:
HLIT — 5 бит, которое равно: количество_длин_и_символов минус 257. В нашем случае, 0, значит количество длин и символов — 257.
HDIST — 5 бит, которое равно: количество_смещений минус 1. В нашем случае 0, значит количество смещений — 1.
HCLEN — 4 бита, которое равно: количество_длин_и_команд минус 4. В нашем случае 11. Значит количество команд и длин — 15.
Давайте ненадолго остановимся и рассмотрим всё это. Блок с динамическими кодами состоит из следующих частей (исключая заголовок и описание длин):
1. Сначала следуют трёхбитовые длины команд и кодов, которых FCLEN + 4. Длины нам помогут декодировать наши значения.
Дело в том, что у каждого кода и команды есть длина (0110 — 4, 111 — 3). Знание длин команд и кодов даёт нам возможность узнать сами коды, нигде их не записывая. Как это работает? Допустим, у нас есть 5 кодов, которые имеют длины соответственно 2, 3, 4, 4, 4. Если при кодировании использовались канонические коды, то мы без проблем их восстановим. Начинаем с наименьшей длины, присваиваем ей код 00. а дальше увеличиваем их в пределах своей длины, дописывая 0, если длина меняется:
Длина - код 2 - 00 3 - 010 4 - 0110 4 - 0111 4 - 1000
Еще раз, если не очень понятно. Если у нас одна длина, то увеличиваем значение на 1. Если длина меняется — увеличиваем на единицу и дописываем 0. Таким образом мы избавляемся от префиксов, то есть мы уверены, что ни один из кодов не является подстрокой для другого. А это позволяет интерпретатору однозначно декодировать значения. Удобно, правда?
Внимательность: в первой части мы получаем лишь длины, которые в последствии пригодятся при декодировании. Мы получаем длины тем же способом, что я описал выше.
Коды и команды следуют в следующем порядке: 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15.
Здесь:
0-15 — длины непосредственно кодов.
16 — длина команды, которая говорит интерпретатору повторить предыдущее значение n раз. Следующие 2 бита как раз являются этим n.
17 — повторить значение 0 n раз. 3 бита являются значением n.
18 — повторить значение 0 n раз. 8 битов являются значением n.
2. Далее идёт последовательность из HLIT + 257 команд и значений закодированных символов, которые можно найти, исходя из их позиции в потоке данных (на примере я объясню этот момент). В предыдущем блоке мы получили их длины. Теперь же мы сможем сопоставить распакованное значение и длину кода, которым оно закодировано. Используя приведённый выше алгоритм, зная длины кодов и их значения, мы без проблем найдем сами коды.
3. Последним идёт блок со сжатыми данными. На этом этапе мы уже знаем коды и их значения (или длины и смещения). Поэтому без проблем можем декодировать строку.
Если у вас каша в голове, то не переживайте, сейчас на примере мы всё разберём. Поехали!
Итак, берём HCLEN + 4 (15) трёхбитовых значений:
|16 | 17 | 18 | 0 | 8 | 7 | 9 | 6 | 10 | 5 | 11 | 4 | 12 | 3 | 13 | 2 | |000 | 011 | 011 | 010 | 000 | 000 | 000 | 000 | 000 | 000 | 000 | 011 | 000 | 011 | 000 | 010 |
Отбросим все значение, где длина равна 0 и переведём в десятичную систему:
0 - 2 2 - 2 3 - 3 4 - 3 17 - 3 18 - 3
Теперь восстанавливаем коды длин:
0 - 00 2 - 01 3 - 100 4 - 101 17 - 110 18 - 111
Затем у нас следуют 257 длин и команд. Здесь мы и применяем наши длины символов и команд. Давайте я покажу как найти значение.
Допустим, возьмём первый код. Благодаря тому, что у нас отсутствуют префиксы, мы можем правильно определить коды. Первый код в нашем потоке — это 111. Смотрим выше и понимаем, что 111 соответствует 18. Смотрим еще выше и вспоминаем, что 18 это команда. Нам требуется еще 7 битов, возьмем же их — 0100000 (32). Это значит, что нам нужно повторить значение 0 32 раза. Самый первый символ имеет позицию 0. Если мы «передвинемся» по нашей последовательности на 32 бита вправо (включая 0), то окажемся на 31 бите. Это всё.
Дальше берём следующую порцию битов — 101. 101 соответствует длине 4. Запоминаем этот код и делаем еще один шаг — 32. Это значит, что первые код с длиной, равной 4, имеет значение 32. Возможно, это не совсем корректное объяснение, но так проще всего понять. Всё остальное делаем точно так же:
длина/команда - значение/повторения. Если 0 - просто делаем еще один шаг. | 18 | 32 | 4 - 32 | 4 - 33 | 18 - 10 | 4 - 44 | 18 - 27 | 4 - 72 | 18 - 14 | 4 - 87 | 18 - 12 | 4 - 100 | 4 - 101 | | 111 | 0100000 | 101 | 101 | 111 0001010 | 101 | 111 0011011 | 101 | 111 0001110 | 101 | 111 0001100 | 101 | 101 | | 17 - 6 | 2 - 108 | 0 | 0 | 3 - 111 | 0 | 0 | 4 - 114 | 18 - 138 | 0 | 0 | 0 | 256 | 0 | 110 110 | 01 | 00 | 00 | 100 | 00 | 00 | 101 | 111 1111111 | 00 | 00 | 00 | 101 | 00 |
Восстанавливаем коды и значения. Всё последовательно.
Полученное на данном шаге значение - код - соотв. символ из таблицы ASCII 108 - 00 - l 111 - 010 - o 32 - 0110 - пробел 33 - 0111 - ! 44 - 1000 - , 72 - 1001 - H 87 - 1010 - W 100 - 1011 - d 101 - 1100 - e 114 - 1101 - r 256 - 1111 - EOB (конец блока)
Теперь сжатые данные:
| H | e | l | l | o | , | | W | o | r | l | d | ! | EOB | | 1001 | 1100 | 00 | 00 | 010 | 1000 | 0110 | 1010 | 010 | 1101 | 00 | 1011 | 0111 | 1111 |
Ну вот, собственно, и всё!
Материалы
#1 — Спецификация PNG
#2 — RFC 1950
#3 — Замечательная статья на Хабре, которая очень помогла мне разобраться с Deflate в PNG
#4 — Еще одна полезная статья о Deflate
#5 — Adler-32
#6 — Изображение