[Из песочницы] GIF изнутри12.01.2016 13:18

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

d4997d2275b141e0bebbe826eb796c26.png

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

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

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

  • Поддерживает «прозрачность»;

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

  • Используется универсальный алгоритм сжатия без потерь LZW.


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

be147e8a3c1d4d38a61feb2faa1c4fa3.PNG3a3319ace4d548c1b0a7e25fbaf0c886.png

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

Заголовок


f2c2690926d84d59ac39ae01d8c315e2.png

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

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


0f0cb5226f1b4fc198a7b74dd96fd65e.png

[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.

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


fc5db554d45b422cb86e9b87a43abb41.png

[0A B2 5D] — 0a7721cffdcb4002b877162badc55af8
[C8 A6 2D] — 4c12b3c231e54c88849e3cd709c91b3b
[F3 ED 63] —  d69b8f2f326449e08017c6d514bd3817
[BA 60 A5] — 45307b6b4b5745ab96db0f9f7fe493f8
[00 80 C8] —  44e0eacb364f4fe0aafebab8d666008f
[F1 60 22] —  22c38b0823bc4af1aa9f4fbf529508ff
[00 00 00] —  718a9f43ca6d4f5db37fbe42da9bc438
[FF FF FF] —   90a8f3dddadc485dac301654fbc7d5a2

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

Коды блоков:
    0×21 — Расширение
    0×2С — Блок изображения
    0×3B — Завершение файла GIF

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


b2b846575a9c4b3a83bfdffe3f36176b

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

aa2853bd574a498bb7d0355dcce437f5.png

[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] — конец блока.

ea69d7049dcb4517a090b7bb5b0f1194.png

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

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


f013919de2984dd08c26ef37d16a8688

4e8d38ca6b9548c7a3a2ae5a73cda59e.png

[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


be147e8a3c1d4d38a61feb2faa1c4fa3.PNG

Словарь/Code Table

44bf77f800fd4d198083e00d69a20f9f

Словарь инициализирован по количеству цветов и кодами {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 00 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 02 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 22 2 2 4 4 4 4 5 5 5 5 #13 — 2 2 #8 #0 #10 #0 #2
12 Read 0 0 0 0 222 2 4 4 4 4 5 5 5 5   #8 #0 #10 #0 #2
13 Found 0 0 0 0 22 2 2 4 4 4 4 5 5 5 5   #8 #0 #10 #0 #2
14 Read 0 0 0 0 22 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 55 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.

ea7729eef8284622993464fa94e9a3a6

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

Кадр 2


3a3319ace4d548c1b0a7e25fbaf0c886.png

Словарь/Code Table

9c68af24dfbf4f929070dc17a5b331b0

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 17   #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.

5547dbba6cb64f5187d64ca992aa8340

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


4f903495eecf42fc9bcedd42e16d0252.png

Заключение


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

e237560d17e2402381e999d3c62cd0bb.jpg

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


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

Авторы: kolyadkodarya blueberry24 anna_shunko

© Habrahabr.ru