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

  • Tutorial
В прошлый раз мы разобрались как устроен 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. Цветовое разрешение. Количество цветов равно 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 и изначально именно по столько битов будем читать.

Краткое описание алгоритма:
  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
  • +105
  • 10,5k
  • 9
Поделиться публикацией
Комментарии 9
    0
    Как-то нужно было портировать код по получению размера изображения с Perl на С++. Секции для JPG и PNG были маленькие и легко портировались. Под GIF же было около 5 условий — и все они обрабатывались по-разному. Не подскажете, почему такая несправедливость? Судя по статье всё должно было быть намного проще…
      +2
      Реальный размер изображения находится в секции Image Descriptor (2C), расположение которого еще нужно найти, пропустив доп. секции. Возможно поэтому.
        +1
        Потому что в PNG в секциях есть данные об их размерах и что где лежит, а в GIF секции, так сказать, «плавающие» — получить доступ к данным можно только прочитав все секции до картинки по очереди.
          +1
          Картинка уж очень похожа на инвайт на хабр.
            0
            На Ассемблере есть библиотека для декодирования GIF

            ;LOADGIF.ASM v1.0 — Optimized GIF Loader for EGA and VGA Video Modes
            ;By Rich Geldreich, Jr.
            ;Last Modified August 20, 1993
            ;Assembled with TASM v2.0

            Помню, в 1999 году написал на основе этой библиотеки программу для DOS для просмотра анимированных GIF и даже для работы с ними — создание, распаковки и т.п. (-: вот было время то!

            Сейчас на javascript уже делают распаковщики mp3.

            
            hallo:
             db 'PLAYGIF { ..имя [имяXXXX[.расширение] | @файл_список] } [ключик][Y|N]',13,10
             db 'где: имя - GIF-картинка,может быть полный путь',13,10
             db ' имяXXXX - специальный формат файла с цифрами (girl0,vgf90,lk1000,35)',13,10
             db 9,'   Учитываются последние цифры.Первые нули нельзя',13,10
             db '   @файл - файл,в котором содержатся имена,разделенные Space,Enter,Tab',13,10
             db ' ключики - задают команды,что делать:',13,10
             db '      /E - разделить анимированный GIF на несколько: ИМЯ.gif имяXXXX',13,10
             db 9,'   при этом XXXX задает первый файл,затем будет автоувеличение',13,10
             db 9,'   на единицу',13,10
             db 9,'   /E@, /E@F - еще сделать файл список <ИМЯ.sld>',13,10
             db '      /C - сделать анимированный GIF: имяXXXX имяXXXX; имя.gif @список;',13,10
             db 9,'   имя.gif имяXXXX1-имяXXXX2 -> в первом случае объединит',13,10
             db 9,'   начиная с 1 и по 2 и получится имя.gif; будет брать имена',13,10
             db 9,'   из списка и получится имя.gif; В 3 случае все ясно и так',13,10
             db '      /B - показывает информацию о анимированном GIF: имя.gif',13,10
             db '      /@ - сделать файл_список из всех GIF в текущем каталоге: имя',13,10
             db 9,'   /@F - полный путь в именах',13,10
             db 'Ключи могут быть и в конце,и в начале.[Y|N] - перезапись разрешена,запрещена',13,10
             db 'Пример: farsy.gif a0.gif /e; new.gif g1-g10 /c; beleave.gif w0 /ey; l /@',36
            
              +1
              Продолжение о формате PNG последует?
                +1
                Ага, он следующий на очереди. Постараюсь не тянуть :)
                +1
                Вот ещё хорошая статья с картинками Краткое описание формата GIF.

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                Самое читаемое