В прошлый раз мы разобрались как устроен JPEG (Декодирование JPEG для чайников). Вполне логично, что следующим форматом стал GIF. Кстати, он гораздо проще. Его, в отличии от JPEG, можно декодировать имея только ручку с бумажкой. Сначала, продолжая традицию, я захотел закодировать в GIF favicon Гугла, но потом решил, что лучше расписать процесс декодирования всего файла на маленьком изображении. Без всяких «а дальше по аналогии...». Пришлось долго экспериментировать, и картинка получилась неказистой, зато вполне наглядной для изучения.
Итак, мы будем ковырять вот эту картинку
. Видите? :) Тогда она же, увеличенная в 10 раз:
Внутренности в hex-редакторе:
Тут может быть и GIF89a. Эти форматы различаются опциональными дополнительными секциями, которые мы не будем рассматривать, они описаны в спецификации.
Следом расположена секция
Изображение расположено в некотором logical screen и может быть сдвинуто относительно верхнего левого угла этого экрана. У всех просмотренных мною файлов размеры картинки и экрана совпадали.
Следом расположена секция
Читаем 12 байт, и формируем такую табличку:
Следом байт
Далее в файле могут быть дополнительные секции (ниже я написал как их определить), но у нас их нет, и мы почти подошли к закодированным данным, и нас отделяют от них
Для сжатия используется алгоритм Лемпеля — Зива — Велча. Ниже опишу его работу в двух словах.
Алгоритм LZW требует это проинициализированный словарь. У нас 4 цвета в таблице, поэтому добавляем 4 значения (они будут являтся индексами цветов):
0: {0} (черный)
1: {1} (белый)
2: {2} (красный)
3: {3} (в нашем примере не используется)
Для gif версии LZW в конец добавляются еще 2 управляющих кода (значения можно не добавлять, просто зарезервировать место):
4: {clear}
5: {end}
Продолжим. Следующие 7 байт:
[84] 10000100
[62] 01100010
[18] 00011000
[2A] 00101010
[10] 00010000
[5D] 01011101
[00] 00000000
Это коды, просто записанные подряд друг за другом. Но справа налево! Просто отсчитываем нужное количество бит справа и берем это число. А если байт закончился, то к уже частично полученному значению спереди дописываем число (с оставшимся количеством битов) из второго байта. На практике будет понятнее.
Мы узнали, что минимальная длина кода LZW в битах равна 2. Но нужно прибавлять еще 1, т.е. 3. Это означает, что текущий размер кода равен 3 и изначально именно по столько битов будем читать.
Краткое описание алгоритма:
Словарь достиг предела для 3-х битных кодов. Текущий размер кода увеличиваем на 1.
Словарь достиг предела для 4-х битных кодов. Текущий размер кода увеличиваем на 1 (длина кода увеличивается максимум до 12! При достижении словарем размера 4096 длина кода остается равной 12, и добавлять в словарь ничего не нужно. Обычно следом идет код clear)
Выпишем полученные индексы слева направо, сверху вниз (учитывая размер картинки 4x4)
Картинка уже угадывается! Уже понятно, что осталось посмотреть какой цвет скрывается за каждым индексом и вывести на экран. А у нас осталось еще 2 байта:
Между секцией Image Descriptor и LZW encoded image data могут располагаться еще несколько секций. Там есть информация об анимации, комментарий, какие-то данные приложений, и т.п. Они определяются по маркеру [21][XX]. Описание см. в спецификации. Я описал только самый минимум, но обработка дополнительных секций не представляет проблем, к тому же большинство можно смело пропускать.
Aлгоритм_Лемпеля_—_Зива_—_Велча
Graphics Interchange Format
GIF89a specification
Итак, мы будем ковырять вот эту картинку
. Видите? :) Тогда она же, увеличенная в 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. Цветовое разрешение. Количество цветов равно 2n+1, в нашем случае 4. (0) = 0. Цвета не отсортированы. (001) = 1. Размер таблицы цветов. Занимает 3*2n+1 байт. У нас 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 и изначально именно по столько битов будем читать.
Краткое описание алгоритма:
- Читаем очередной код.
- В словаре, под номером равным коду, берем список индексов. Это готовые индексы цветов.
- В словарь добавляется список индексов, взятый из словаря на предыдущем этапе с добавленным первым индексом взятый из словаря на текущем этапе.
(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
