Декодирование GIF

В прошлый раз мы разобрались как устроен JPEG (Декодирование JPEG для чайников). Вполне логично, что следующим форматом стал GIF. Кстати, он гораздо проще. Его, в отличии от JPEG, можно декодировать имея только ручку с бумажкой. Сначала, продолжая традицию, я захотел закодировать в GIF favicon Гугла, но потом решил, что лучше расписать процесс декодирования всего файла на маленьком изображении. Без всяких «а дальше по аналогии...». Пришлось долго экспериментировать, и картинка получилась неказистой, зато вполне наглядной для изучения.

Итак, мы будем ковырять вот эту картинку . Видите? :) Тогда она же, увеличенная в 10 раз:


Внутренности в hex-редакторе:

Заголовок

[47 49 46 38 37 61] GIF87a.
Тут может быть и GIF89a. Эти форматы различаются опциональными дополнительными секциями, которые мы не будем рассматривать, они описаны в спецификации.

Следом расположена секция

Logical Screen Descriptor

Изображение расположено в некотором logical screen и может быть сдвинуто относительно верхнего левого угла этого экрана. У всех просмотренных мною файлов размеры картинки и экрана совпадали.

[04 00] [04 00] = 4x4 (размеры logical screen)
[91] = 10010001b
  (1)   = 1. Используется глобальная таблица цветов.
  (001) = 1. Цветовое разрешение. Количество цветов равно 2ⁿ⁺¹, в нашем случае 4.
  (0)   = 0. Цвета не отсортированы.
  (001) = 1. Размер таблицы цветов. Занимает 3*2ⁿ⁺¹ байт. У нас 12.
[00] = 0. Индекс цвета фона. Для прозрачности.
[00] = 0. Соотношение сторон. (У подавляющего большинства изображений этот байт 0, т.е. 1:1. В противном случае см. спецификацию)

Следом расположена секция

Global Color Table

Читаем 12 байт, и формируем такую табличку:
 R  G  B
[04 02 04] — почти черный (это кодировщик так решил)
[FC FE FC] — почти белый
[FC 02 04] — почти красный
[00 00 00] — в нашем примере не используется.

Следом байт [2C], а это значит, что началась секция

Image Descriptor [2C]

[00 00] [00 00] = (0, 0). Координаты верхнего левого угла в logical screen
[04 00] [04 00] = 4x4. Размеры изображения
[00] = 00000000.
  (0)   = 0. Локальная таблица цветов не используется.
  (0)   = 0. Интерлейс не используется (если 1, то меняется порядок строк, см Spec. Appendix E)
  (0)   = 0. Локальная таблица цветов не отсортирована.
  (00)  = 0. Зарезервировано
  (000) = 0. цветовое разрешение локальной таблицы цветов.

Далее в файле могут быть дополнительные секции (ниже я написал как их определить), но у нас их нет, и мы почти подошли к закодированным данным, и нас отделяют от них

Еще 2 байта

Для сжатия используется алгоритм Лемпеля — Зива — Велча. Ниже опишу его работу в двух словах.

[02] Минимальная длина кода LZW в битах (+1).
[07] Длина секции с данными. Вы спросите: «Как! Тут же всего один байт, то есть максимальная длина 255?». Верно, но таких секций неограниченное число. Если файл еще не закончился, то после окончания секции опять встретится байт с длиной следующей секции. Код может оказаться разрезанным этим байтом. Нужно запоминать его, чтобы вычислить расположение следующего.

LZW encoded image data.

Алгоритм LZW требует это проинициализированный словарь. У нас 4 цвета в таблице, поэтому добавляем 4 значения (они будут являтся индексами цветов):
0: {0} (черный)
1: {1} (белый)
2: {2} (красный)
3: {3} (в нашем примере не используется)

Для gif версии LZW в конец добавляются еще 2 управляющих кода (значения можно не добавлять, просто зарезервировать место):
4: {clear}
5: {end}

Продолжим. Следующие 7 байт: [84 62 18 2A 10 5D 00]. Нужно перевести их в двоичное представление

[84] 10000100
[62] 01100010
[18] 00011000
[2A] 00101010
[10] 00010000
[5D] 01011101
[00] 00000000

Это коды, просто записанные подряд друг за другом. Но справа налево! Просто отсчитываем нужное количество бит справа и берем это число. А если байт закончился, то к уже частично полученному значению спереди дописываем число (с оставшимся количеством битов) из второго байта. На практике будет понятнее.
Мы узнали, что минимальная длина кода LZW в битах равна 2. Но нужно прибавлять еще 1, т.е. 3. Это означает, что текущий размер кода равен 3 и изначально именно по столько битов будем читать.

Краткое описание алгоритма:

1. Читаем очередной код.
2. В словаре, под номером равным коду, берем список индексов. Это готовые индексы цветов.
3. В словарь добавляется список индексов, взятый из словаря на предыдущем этапе с добавленным первым индексом взятый из словаря на текущем этапе.

(100) 4. В словаре под номером 4 расположен код clear. Значит инициализируем словарь, текущий размер кода устанавливаем равным 3 (в нашем примере конечно же). В файлах побольше этот код встречаться часто.
(000) 0. В словаре под номером 0 находится {0}, это уже готовый индекс цвета (левого верхнего угла). В словарь ничего не добавляем.
(010) 2. В словаре под номером 2 находится {2}. Добавляем {0}+{2} = {0,2} с номером 6 (далее я буду использовать запись покороче: 2:{2}, +6:{0,2})
(001) 1. В словаре под номером 1 находится {1}. Добавляем {2}+{1} = {2,1} с номером 7 (+7:{2,1})

Словарь достиг предела для 3-х битных кодов. Текущий размер кода увеличиваем на 1.
(0110) 6: {0,2}   +8: {1,0}
(1000) 8: {1,0}   +9: {0,2,1}
(0001) 1: {1}     +10:{1,0,1}
(1010) 10:{1,0,1} +11:{1,1}
(0010) 2: {2}     +12:{1,0,1,2}
(0000) 0: {0}     +13:{2,0}
(0001) 1: {1}     +14:{0,1}
(1101) 13:{2,0}   +15:{1,2}

Словарь достиг предела для 4-х битных кодов. Текущий размер кода увеличиваем на 1 (длина кода увеличивается максимум до 12! При достижении словарем размера 4096 длина кода остается равной 12, и добавлять в словарь ничего не нужно. Обычно следом идет код clear)
(00101) 5:{end} конец

Выпишем полученные индексы слева направо, сверху вниз (учитывая размер картинки 4x4)
0210
2101
1012
0120

Картинка уже угадывается! Уже понятно, что осталось посмотреть какой цвет скрывается за каждым индексом и вывести на экран. А у нас осталось еще 2 байта:
[00] еще один конец.
[3B] точно-точно конец :)

Extensions

Между секцией Image Descriptor и LZW encoded image data могут располагаться еще несколько секций. Там есть информация об анимации, комментарий, какие-то данные приложений, и т.п. Они определяются по маркеру [21][XX]. Описание см. в спецификации. Я описал только самый минимум, но обработка дополнительных секций не представляет проблем, к тому же большинство можно смело пропускать.

Полезные ссылки

Aлгоритм_Лемпеля_—_Зива_—_Велча
Graphics Interchange Format
GIF89a specification