Вам когда-нибудь было интересно, как устроены gif-ки? В данной статье попробуем разобраться с внутренним строением GIF-формата и методом сжатия LZW.

Структура GIF


Файл в формате GIF состоит из фиксированной области в начале файла, за которой располагается переменное число блоков, и заканчивается файл завершителем изображения.



Основные характеристики формата GIF:

  • Изображение в формате GIF хранится построчно, поддерживается только формат с индексированной палитрой цветов;
  • Поддерживается 256-цветовая палитра;
  • Этот формат позволяет хранить несколько изображений в одном файле;
  • GIF поддерживает анимационные изображения;

    Такие изображения представляют собой последовательность из нескольких статичных кадров, а также информацию о том, сколько времени каждый кадр должен быть показан на экране. Анимацию можно сделать цикличной, тогда вслед за последним кадром начнётся воспроизведение первого кадра и т. д.
  • Поддерживает «прозрачность»;

    Один из цветов в палитре может быть объявлен «прозрачным». В этом случае в программах, которые поддерживают прозрачность GIF (например, большинство современных браузеров) сквозь пиксели, окрашенные «прозрачным» цветом, будет виден фон. GIF анимация может использовать прозрачность для того чтобы не сохранять очередной кадр целиком, а только изменения относительно предыдущего.
  • Используется универсальный алгоритм сжатия без потерь LZW.

Пример разбора


Рассмотрим разбор дампа анимированного GIF-изображения размера 4х4 пикселя, состоящего из двух кадров. А вот и сами кадры, увеличенные в десятки раз.



Исходное изображение

Заголовок




В начале каждого файла GIF находится заголовок. Состоит он из текста «GIF87a» или «GIF89a», в зависимости от версии. В формате GIF87a переменная область содержит исключительно описания изображения, а в формате GIF89a она может включать еще и блоки расширений.

Логический дескриптор экрана




[04 00] [04 00] – ширина и высота виртуального экрана в пикселях
[А2] –
     (1) — флаг M использования глобальной таблицы цветов. Если 1, то в файле присутствует глобальная таблица цветов.
     (010) = 2 — флаг CR. Число бит разрешения цвета = CR + 1.
     (0) – флаг S (флаг сортировки). Если 1, то цвета в глобальной карте цветов отсортированы в порядке убывающей важности.
     (010) = 2 — флаг PIXEL. Размер общей таблицы цветов. Число записей в глобальной таблице цветов: 2^(N+1).
[00] – Индекс цвета фона.
[00] – Соотношение сторон. По умолчанию — 1:1.

Глобальная таблица цветов




[0A B2 5D] —
[C8 A6 2D] —
[F3 ED 63] —  
[BA 60 A5] —
[00 80 C8] —  
[F1 60 22] —  
[00 00 00] —  
[FF FF FF] —   

После глобальной таблицы цветов располагается переменная часть GIF. Файл содержит последовательность блоков, которые иденцифицируются 1-байтовым кодом в начале блока.

Коды блоков:
    0x21 – Расширение
    0x2С – Блок изображения
    0x3B – Завершение файла GIF

Блок расширения




Коды расширения:
    0x1 – расширение простого текста
    0xF9 – расширение управления графикой
    0xFE – расширение комментария
    0xFF – расширение программы



[FF] — код расширения. В нашем случае имеем расширение программы.
[0B] — размер последующего блока в байтах.
[4E 45 54 53 43 41 50 45] — (NETSCAPE) идентификатор приложения, которому принадлежит это расширение.
[32 2E 30] — (2.0) код приложения. С его помощью приложение проверяет, действительно ли это расширение принадлежит ему.
[03] — размер последующего блока в байтах.
[01] — фиксированное значение.
[00 00] — значение 0..65535. Беззнаковое целое в формате little-endian. Определяет, сколько раз должен повторяться цикл.
            Для 0 – бесконечно.
[00] — конец блока.



[F9] — код расширения (расширение управления графикой).
[04] — размер последующего блока в байтах.
[04] —
    (000) – зарезервировано. Рекомендуется заполнять нулями.
    (001) — метод обработки. Определяет, что делать после отображения.
                0 – к картинке не будет применяться никакой обработки
                1 – картинка останется без изменений
                2 – картинка затрется фоном
                3 – восстановится изображение под картинкой
                4-7 – не определены
    (0) – флаг ввода пользователя. Если 1, то для продолжения обработки изображения требуется реакция пользователя.
    (0) – флаг цвета прозрачности. Указывает, будет ли какой-нибудь цвет использоваться как прозрачный.
[32 00] – время задержки в анимации. = 50/100 секунды = 0,5 с
[00] – индекс цвета прозрачности.
[00] — конец блока.

Блок изображения






[00 00] [00 00] — номер строки и столбца. Определяет координаты верхнего левого угла логического экрана. (0, 0).
[04 00] [04 00] — ширина и высота изображения в пикселях.
[00] —
    (0) – флаг использования локальной таблицы цветов
    (0) – флаг чересстрочной развертки. Указывает, в каком порядке считываются пиксели изображения.
                0 – по строкам слева направо, сверху вниз
                1 – порядок:0-я. 8-я, 16-я…, 4-я, 12-я, 24-я…
    (0) – флаг сортировки локальной таблицы цветов. Если 1, то цвета в локальной карте цветов отсортированы в порядке убывающей важности.
    (00) – зарезервированы.
    (000) – флаг PIXEL. Размер локальной таблицы цветов, если есть.

[03] — минимальный размер кода в LZW.
[08] — размер последующего блока в байтах.
[08 0A D2 42 90 94 59 12] — блок данных, сжатых алгоритмом LZW. Представлены в виде последовательности кодов, имеющих длину [мин. размер кода] + 1
[00] — окончание потока данных.

Разбор алгоритма LZW

Кадр 1




Словарь/Code Table



Словарь инициализирован по количеству цветов и кодами {clear} и {end}. Берем код с длиной текущего размера, получаем его значение из словаря. Если значение есть в словаре, то получаем готовый индекс цвета для текущего пикселя и добавляем в словарь следующее значение: полученное предыдущее + первое из текущего. Если в словаре еще нет такого значения, то добавляем по этому индексу полученное предыдущее + первое из предыдущего. Первый код должен соответствовать значению {clear}, последний — {end}.

Решим обратную задачу. Возьмем исходные данные изображения и закодируем их с использованием алгоритма LZW. Под исходными данными понимаем последовательность индексов цветов из словаря, соответствующих каждому из пикселей. Пискели рассматриваем сверху вниз, слева направо.

Step Action Index Stream New Code Table Row Code Stream
1 Init 0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5   #8
2 Read 0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5   #8
3 Not found 0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5 #10 – 0 0 #8 #0
4 Read 0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5   #8 #0
5 Found 0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5   #8 #0 
6 Read 0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5   #8 #0  
7 Not found 0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5 #11 – 0 0 0 #8 #0 #10 
8 Read 0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5   #8 #0 #10 
9 Not found 0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5 #12 – 0 2 #8 #0 #10 #0
10 Read 0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5   #8 #0 #10 #0
11 Not found 0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5 #13 – 2 2 #8 #0 #10 #0 #2
12 Read 0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5   #8 #0 #10 #0 #2
13 Found 0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5   #8 #0 #10 #0 #2
14 Read 0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5   #8 #0 #10 #0 #2
15 Not found 0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5 #14 – 2 2 2 #8 #0 #10 #0 #2 #13
16 Read 0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5   #8 #0 #10 #0 #2 #13
17 Not found 0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5 #15 – 2 4 #8 #0 #10 #0 #2 #13 #2
18 Read 0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5   #8 #0 #10 #0 #2 #13 #2
19 Not found 0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5 #16 – 4 4 #8 #0 #10 #0 #2 #13 #2 #4
20 Read 0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5   #8 #0 #10 #0 #2 #13 #2 #4
21 Found 0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5   #8 #0 #10 #0 #2 #13 #2 #4
22 Read 0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5   #8 #0 #10 #0 #2 #13 #2 #4
23 Not found 0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5 #17 – 4 4 4 #8 #0 #10 #0 #2 #13 #2 #4 #16
24 Read 0 0 0 0 2 2 2 2 4 4 4 5 5 5 5   #8 #0 #10 #0 #2 #13 #2 #4 #16
25 Not found 0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5 #18 – 4 5 #8 #0 #10 #0 #2 #13 #2 #4 #16 #4
26 Read 0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5   #8 #0 #10 #0 #2 #13 #2 #4 #16 #4
27 Not found 0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5
#19 – 5 5 #8 #0 #10 #0 #2 #13 #2 #4 #16 #4 #5
28 Read 0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5   #8 #0 #10 #0 #2 #13 #2 #4 #16 #4 #5
29 Found 0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5   #8 #0 #10 #0 #2 #13 #2 #4 #16 #4 #5
30 Read 0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5   #8 #0 #10 #0 #2 #13 #2 #4 #16 #4 #5
31 Not found 0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5 #20 –5 5 5 #8 #0 #10 #0 #2 #13 #2 #4 #16 #4 #5 #19
32 Read 0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5   #8 #0 #10 #0 #2 #13 #2 #4 #16 #4 #5 #19 #5 #9

Теперь сравним результат кодирования со сжатыми данными, хранящимися в дампе. Формат GIF в данном блоке хранит многобайтовые целые числа с младшим байтом на первом месте (прямой порядок байтов).

[08 0A D2 42 90 94 59 12] — блок данных, сжатых алгоритмом LZW.



Аналогично поступаем со вторым кадром.

Кадр 2




Словарь/Code Table



Step Action Index Stream New Code Table Row Code Stream
1 Init 3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7   #8
2 Read 3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7   #8
3 Not found 3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7 #10 – 3 6 #8 #3
4 Read 3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7   #8 #3
5 Not found 3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7 #11 – 6 1 #8 #3 #6
6 Read 3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7   #8 #3 #6
7 Not found 3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7 #12 – 1 7 #8 #3 #6 #1
8 Read 3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7   #8 #3 #6 #1
9 Not found 3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7 #13 – 7 3 #8 #3 #6 #1 #7
10 Read 3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7   #8 #3 #6 #1 #7
11 Found 3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7   #8 #3 #6 #1#7
12 Read 3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7   #8 #3 #6 #1#7
13 Not found 3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7 #14 – 3 6 1 #8 #3 #6 #1 #7 #10
14 Read 3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7   #8 #3 #6 #1 #7 #10
15 Found 3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7   #8 #3 #6 #1 #7 #10
16 Read 3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7   #8 #3 #6 #1 #7 #10
17 Not found 3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7 #15 – 1 7 3 #8 #3 #6 #1 #7 #10 #12
18 Read 3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7   #8 #3 #6 #1 #7 #10 #12
19 Found 3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7   #8 #3 #6 #1 #7 #10 #12
20 Read 3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7   #8 #3 #6 #1 #7 #10 #12
21 Found 3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7   #8 #3 #6 #1 #7 #10 #12
22 Read 3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7   #8 #3 #6 #1 #7 #10 #12
23 Not found 3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7 #16 – 3 6 1 7 #8 #3 #6 #1 #7 #10 #12 #14
24 Read 3 6 1 7 3 6 1 7 3 6 1 3 6 1 7   #8 #3 #6 #1 #7 #10 #12 #14
25 Found 3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7   #8 #3 #6 #1 #7 #10 #12 #14
26 Read 3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7   #8 #3 #6 #1 #7 #10 #12 #14
27 Not found 3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7 #17 – 7 3 6 #8 #3 #6 #1 #7 #10 #12 #14 #13
28 Read 3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7   #8 #3 #6 #1 #7 #10 #12 #14 #13
29 Found 3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7   #8 #3 #6 #1 #7 #10 #12 #14 #13
30 Read 3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7   #8 #3 #6 #1 #7 #10 #12 #14 #13
31 Not found 3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7 #18 – 6 1 7 #8 #3 #6 #1 #7 #10 #12 #14 #13 #11
32 Read 3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7   #8 #3 #6 #1 #7 #10 #12 #14 #13 #11 #7 #9

[38 16 A7 EC 6D 9D 04] — блок данных, сжатых алгоритмом LZW.



Блок завершения файла GIF




Заключение


На этом всё. Надеемся, эта статья была полезна для вас (ну или хотя бы интересна).



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


www.w3.org/Graphics/GIF/spec-gif89a.txt
home.onego.ru/~chiezo/gif.htm

Авторы: kolyadkodarya blueberry24 anna_shunko

Комментарии (16)


  1. romangoward
    12.01.2016 13:58
    +28

    Твоё лицо, когда в статье про gif нет ни одной gif :-}


    1. saboteur_kiev
      13.01.2016 10:46

      Блин, а я сперва подумал, что изображение в конце статьи это пример полноцветного gif, но нет — png ;(


  1. cruzo
    12.01.2016 14:41
    +6

    Эх, я так надеялся увидеть блок данных, который тормозит gif постоянно.


    1. gurux13
      12.01.2016 15:27
      +1

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


      1. merlin-vrn
        13.01.2016 09:42

        Парятся, парятся. Куча оптимизаторов это делают.


  1. gurux13
    12.01.2016 15:39
    +6

    Ну и гифка в статью о гифках (отсюда: хабр)
    image


    1. bolk
      13.01.2016 09:41

      Странно, что все именно эту гифку копируют. Вот вам более красивая:


      1. x128
        13.01.2016 14:38
        +2

        Можно и картинку из статьи заGIFить:

        image


  1. muxrim
    12.01.2016 19:40

    я NETSCAPE


    1. alcr
      13.01.2016 09:15

      Таки второе пришествие свершилось. Мёртвые восстали из могил.


  1. bolk
    13.01.2016 10:06

    Ещё GIF поддерживает цветовые профили: bolknote.ru/2012/08/29/~3728 И бывают ещё несжатые GIF (тут немного писал об этом: bolknote.ru/2012/08/11/~3712).


    1. merlin-vrn
      13.01.2016 11:46

      Ну, так в GIF можно ещё RLE, не только патентованый до недавнего времени LZW.


      1. bolk
        13.01.2016 11:56

        Ага. «Недавнего» :) 11 лет прошло. Только на территории России патент никто не получал, поэтому и соблюдать российский софт его был не обязан. :)


      1. bolk
        13.01.2016 12:55
        +1

        Кстати, никогда не слышал, что в ГИФе можно RLE. Есть где-то подтверждение этому? Я не нашёл этого в спецификации.


  1. sergiks
    19.01.2016 13:44
    +1

    ОБС, что в gif, как в контейнер, помимо изображения можно поместить ещё любые абстрактные данные без вреда для визуального отображения.


  1. uvelichitel
    19.01.2016 17:09
    +1

    Немного не о gif, но релевантно, небезызвестные suckless.org анонсировали свой растровый формат farbfeld. Кто нибудь пробовал в быту vs gif?