- PVSM.RU - https://www.pvsm.ru -

GIF изнутри

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

Структура GIF

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

GIF изнутри - 2

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

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

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

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

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

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

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

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

GIF изнутри - 3 GIF изнутри - 4

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

Заголовок

GIF изнутри - 5

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

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

GIF изнутри - 6

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

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

GIF изнутри - 7

[0A B2 5D] — GIF изнутри - 8
[C8 A6 2D] — GIF изнутри - 9
[F3 ED 63] — &nbspGIF изнутри - 10
[BA 60 A5] — GIF изнутри - 11
[00 80 C8] — &nbspGIF изнутри - 12
[F1 60 22] — &nbspGIF изнутри - 13
[00 00 00] — &nbspGIF изнутри - 14
[FF FF FF] — &nbsp&nbspGIF изнутри - 15

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

Коды блоков:
&nbsp&nbsp&nbsp&nbsp0x21 – Расширение
&nbsp&nbsp&nbsp&nbsp0x2С – Блок изображения
&nbsp&nbsp&nbsp&nbsp0x3B – Завершение файла GIF

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

GIF изнутри - 16

Коды расширения:
&nbsp&nbsp&nbsp&nbsp0x1 – расширение простого текста
&nbsp&nbsp&nbsp&nbsp0xF9 – расширение управления графикой
&nbsp&nbsp&nbsp&nbsp0xFE – расширение комментария
&nbsp&nbsp&nbsp&nbsp0xFF – расширение программы

GIF изнутри - 17

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

GIF изнутри - 18

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

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

GIF изнутри - 19

GIF изнутри - 20

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

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

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

Кадр 1

GIF изнутри - 21

Словарь/Code Table

GIF изнутри - 22

Словарь инициализирован по количеству цветов и кодами {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.

GIF изнутри - 23

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

Кадр 2

GIF изнутри - 24

Словарь/Code Table

GIF изнутри - 25

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 изнутри - 26

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

GIF изнутри - 27

Заключение

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

GIF изнутри - 28

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

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

Авторы: kolyadkodarya [6] blueberry24 [7] anna_shunko [8]

Автор: anna_shunko

Источник [9]

Сайт-источник PVSM.RU: https://www.pvsm.ru

Путь до страницы источника: https://www.pvsm.ru/dekodirovanie/108699

Ссылки в тексте:

[1] GIF: https://ru.wikipedia.org/wiki/GIF

[2] LZW: https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch

[3] Исходное изображение: https://habrastorage.org/files/5df/86a/3d1/5df86a3d138046d3a29a3a7bac2c2e80.gif

[4] www.w3.org/Graphics/GIF/spec-gif89a.txt: http://www.w3.org/Graphics/GIF/spec-gif89a.txt

[5] home.onego.ru/~chiezo/gif.htm: http://home.onego.ru/~chiezo/gif.htm

[6] kolyadkodarya: http://habrahabr.ru/users/kolyadkodarya/

[7] blueberry24: http://habrahabr.ru/users/blueberry24/

[8] anna_shunko: http://habrahabr.ru/users/anna_shunko/

[9] Источник: http://habrahabr.ru/post/274917/