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