Вам когда-нибудь было интересно, как устроены 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 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 7 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