Table of Contents
概述
GIF（Graphics Interchange Format–图片交换格式）是一种位图图像格式，最初发布于 1987 年，1989 年出了一个扩展版本。89 版兼容 87 版，所以解码器可以在不支持 89 版本的情况下显示图片。
GIF 基于 8 位颜色表显示图片，但这并不意味着一副 GIF 图片最多只能有 256 色。因为每一帧图片可以有自己的局部颜色表。
GIF 数据使用小端序和 lzw 压缩存储。
GIF 文件的结构和解析，中英文都有相关资料。最准确的当然是 89a 标准（https://www.w3.org/Graphics/GIF/spec-gif89a.txt）和 wiki（https://en.wikipedia.org/wiki/GIF）。
本文章根据已有文章和解码器的实现总结而来。
前置
小端序
字节存储顺序主要分为大端序（Big-endian）和小端序（Little-endian），表现如下：
- Big-endian：高位字节存入低地址，低位字节存入高地址
- Little-endian：低位字节存入低地址，高位字节存入高地址
比如 12345678 存入内存：
| 存储顺序\内存顺序 | 1000h | 1001h | 1002h | 1003h |
| 大端序 | 12 | 34 | 56 | 78 |
| 小端序 | 78 | 56 | 34 | 12 |
LZW 压缩
关于 lzw 压缩，之前有写过一篇文章：《LZW压缩编解码》。GIF 使用了该算法的变体：变长 LZW 压缩。比如：一开始字典编码长度 8 位，最多 256 个 code。当出现新的 code，字典容量不够的时候，位宽 +1，变成 9 位。以此类推。于是，最终写入的数据就是不定长度的，不能按字节取数据，而是按位取。
按位存取数据
JavaScript 提供了 ArrayBuffer，但最小单位是字节，比如 Uint8Array。按位取数据需要自己实现。
比如：
/**
* getBits
* @param num 1 byte
* @param bitIdx bit index(from right to left)
* @param length required bits length
*/
export function getBits(num: number, bitIdx: number, length: number): number {
return (num >> bitIdx) & ((1 << length) - 1)
}
/**
* setBits
* @param targetNum 1 byte
* @param bitIdx bit index (from right to left)
* @param length required bits length
* @param sourceNum
* @returns
*/
export function setBits(targetNum: number, bitIdx: number, length: number, sourceNum: number): number {
return ((((1 << length) - 1) & sourceNum) << bitIdx) | targetNum
}
一个字节 8 位，从右往左，根据索引（bitIdx），按长度（length）写入。
文件结构
GIF 文件主要分为三块：文件头、GIF 数据流、文件尾。
- 文件头：包含签名（GIF）和版本号（87a 或者 89a）
- 数据流：分为各个块。逻辑屏幕描述符、全局颜色表、扩展块（0x21 标识，其后跟着扩展类型标识，扩展块最后一个字节为 0，标识着块的结束）、图片描述符（0x2C 标识，描述内容后是局部颜色表和图片数据）
- 文件结尾
一个 GIF 文件可以视为由多个数据块组成（以下表格翻译自 gif 89a 标准）：
| 块名称 | 是否必须 | 标识 | 是否扩展 | 版本 |
| 文件头 | 必须（1） | / | 否 | / |
| 逻辑屏幕描述符 | 必须（1） | / | 否 | 87a(89a) |
| 全局颜色表 | 可选（1） | / | 否 | 87a |
| 应用程序扩展 | 可选（*） | 0xFF(255) | 是 | 89a |
| 注释扩展 | 可选（*） | 0xFE(254) | 是 | 89a |
| 图形控制扩展 | 可选（*） | 0xF9(249) | 是 | 89a |
| 图片描述符 | 可选（*） | 0x2C(044) | 否 | 87a(89a) |
| 局部颜色表 | 可选（*） | / | 否 | 87a |
| 纯文本扩展 | 可选（*） | 0x01(001) | 是 | 89a |
| 结束标志 | 必须（1） | 0x3B(059) | 否 | 87a |
| 说明： | （1）–如果存在，最多一个 | |||
| （*）–存在 0 个或多个 |
文件头（Header）
7 6 5 4 3 2 1 0 Field Name Type +---------------+ 0 | 'G' | Signature 3 Bytes +- -+ 1 | 'I' | +- -+ 2 | 'F' | +---------------+ 3 | '8' | Version 3 Bytes +- -+ 4 | '7/9' | +- -+ 5 | 'a' | +---------------+
GIF 文件头固定为 6 个字节，位于文件的开头。前三个字节是签名“GIF”，后三位是版本——“87a” 或者 “89a”。
逻辑屏幕描述符（Logical Screen Descriptor）
7 6 5 4 3 2 1 0 Field Name Type
+---------------+
0 | | Logical Screen Width Unsigned
+- -+
1 | |
+---------------+
2 | | Logical Screen Height Unsigned
+- -+
3 | |
+---------------+
4 | | | | | <Packed Fields> See below
+---------------+
5 | | Background Color Index Byte
+---------------+
6 | | Pixel Aspect Ratio Byte
+---------------+
<Packed Fields> = Global Color Table Flag 1 Bit
Color Resolution 3 Bits
Sort Flag 1 Bit
Size of Global Color Table 3 Bits
逻辑屏幕描述符共 7 个字节，必须跟在文件头后面。即文件的第 7~13（含）字节。
第一、二字节为图像像素宽度。比如 0F 00，根据小端序读取，即为 15。
第三、四字节为图像像素高度。
第五个字节（图中下标 4）是压缩字节，包含了四个字段。从左到右分别为全局颜色表标识（Global Color Table Flag）、颜色解析度（Color Resolution）、排序标识（Sort Flag）、全局颜色表大小（Size of Global Color Table）。
- 全局颜色表标识。一位。0：没有全局颜色表，1：有。
- 颜色解析度。三位。原始图像中 rgb 每个主色的位数 – 1，即读出来的数字 + 1 为原图像主色位数。比如读数 7，说明原图 rgb 每个 8 位，即原图为真彩色。这个字段可以忽略，原图全按真彩色处理。
- 排序标识。一位。用来表示颜色表里的颜色是否按照频率降序。0：未排序，1：排序。这个字段用来辅助解码。可以忽略。
- 全局颜色表大小。三位。2^(value + 1) 即为颜色表大小——颜色数量。因此，GIF 颜色表最多 256 色。颜色表
第六个字节为背景色索引。即帧图片没有覆盖的地方用指定的颜色填充。因为帧图片可以小于 GIF 图像大小。
第七个字节为原图宽高比。在解码过程中我忽略了这个值。
全局颜色表（Global Color Table）
如果逻辑屏幕描述符表示有全局颜色表，则 LSD 后面必须紧跟着全局颜色表（GCT）。GCT 字节数为 GCT 大小 * 3——因为每个颜色有 RGB 三色通道。[n + 1, n + 2, n + 3] 为第一个颜色，以此类推。当某帧图片没有局部颜色表的时候会使用全局颜色表。
应用程序扩展（Application Extension）
7 6 5 4 3 2 1 0 Field Name Type
+---------------+
0 | | Extension Introducer Byte
+---------------+
1 | | Extension Label Byte
+---------------+
+---------------+
0 | | Block Size Byte
+---------------+
1 | |
+- -+
2 | |
+- -+
3 | | Application Identifier 8 Bytes
+- -+
4 | |
+- -+
5 | |
+- -+
6 | |
+- -+
7 | |
+- -+
8 | |
+---------------+
9 | |
+- -+
10 | | Appl. Authentication Code 3 Bytes
+- -+
11 | |
+---------------+
+===============+
| |
| | Application Data Data Sub-blocks
| |
| |
+===============+
+---------------+
0 | | Block Terminator Byte
+---------------+
应用程序扩展标识为 0xFF。当文件字节流遇到 0x21 0xFF 的时候即为应用程序扩展。接下来的一个字节表示后续内容的大小，固定为 11。前八个字节表示应用名称，后三个是鉴权码。现在一般为“NETSCAPE2.0”。接下来是应用数据，对于 NETSCAPE 块，第一个字节为子块大小（含自身），第二个字节为子块索引，第三个为 GIF 动画重复次数。
如果不关心循环次数，可以直接跳过应用程序扩展。
注释扩展（Comment Extension）
7 6 5 4 3 2 1 0 Field Name Type
+---------------+
0 | | Extension Introducer Byte
+---------------+
1 | | Comment Label Byte
+---------------+
+===============+
| |
N | | Comment Data Data Sub-blocks
| |
+===============+
+---------------+
0 | | Block Terminator Byte
+---------------+
注释扩展标识为 0xFE。当文件字节流遇到 0x21 0xFE 的时候即为注释扩展。注释数据由一系列子块组成，子块最大 255 字节，最小 1 字节。子块第一个字节为子块大小（不包含自身），其后为数据。
该扩展可跳过。
图形控制扩展（Graphic Control Extension）
7 6 5 4 3 2 1 0 Field Name Type
+---------------+
0 | | Extension Introducer Byte
+---------------+
1 | | Graphic Control Label Byte
+---------------+
+---------------+
0 | | Block Size Byte
+---------------+
1 | | | | | <Packed Fields> See below
+---------------+
2 | | Delay Time Unsigned
+- -+
3 | |
+---------------+
4 | | Transparent Color Index Byte
+---------------+
+---------------+
0 | | Block Terminator Byte
+---------------+
<Packed Fields> = Reserved 3 Bits
Disposal Method 3 Bits
User Input Flag 1 Bit
Transparent Color Flag 1 Bit
图形控制扩展（GCE）标识为 0xF9。当文件字节流遇到 0x21 0xF9 的时候即为 GCE。扩展数据里第一个字节表明块数据字节数（不含自身），固定为 4。
第二个字节是压缩字节，包含四个字段。
- 保留字段：三位。
- 处置方式：三位。表示当前帧绘制之后，下一帧绘制之前，如何处置当前帧。
- 0：不指定处置方式。可以理解为保留画面，下一帧直接叠加在当前画面上。
- 1：保留当前帧。下一帧直接叠加在当前画面上。
- 2：当前帧绘制区域恢复背景色。
- 3：抛弃当前帧。
- 4-7：未定义。
- 用户输入标志。一位。行为由应用定义。比如，开启此功能时——数值为 1，用户鼠标点击，则立即绘制下一帧。此标志可忽略。
- 透明色标识。一位。设为 1 时，说明有透明色索引。
第三四个字节是帧延迟时间。即当前帧与下一帧之间的时间，单位是 1/100 秒。如果为 0，大概是立即绘制下一帧（标准里没有说 0 该如何处理）。
第五个字节是背景色索引。当图像数据里遇到此值时，该像素为透明像素。
图形控制扩展后面一般是图像描述符或者纯文本扩展。但不排除两者之间出现注释扩展的可能。
图像描述符（Image Descriptor）
7 6 5 4 3 2 1 0 Field Name Type
+---------------+
0 | | Image Separator Byte
+---------------+
1 | | Image Left Position Unsigned
+- -+
2 | |
+---------------+
3 | | Image Top Position Unsigned
+- -+
4 | |
+---------------+
5 | | Image Width Unsigned
+- -+
6 | |
+---------------+
7 | | Image Height Unsigned
+- -+
8 | |
+---------------+
9 | | | | | | <Packed Fields> See below
+---------------+
<Packed Fields> = Local Color Table Flag 1 Bit
Interlace Flag 1 Bit
Sort Flag 1 Bit
Reserved 2 Bits
Size of Local Color Table 3 Bits
一副图像由图片描述符、可选的局部颜色表、图像数据组成。
图像描述符标识是 0x2C。注意，这里没有扩展标识 0x21。
第二、三字节是图像在逻辑屏幕宽度左边开始位置。即左边距。
第四、五字节是图像在逻辑屏幕高度上边开始位置。即右边距。
第六、七字节是图像宽度。
第八、九字节是图像高度。
第十个字节是压缩字节，包含五个字段。
- 局部颜色表标识。一位。如果为 1，说明存在局部颜色表。
- 交错标识。一位。如果为 1，说明图像采用隔行扫描排列。即图像数据并非按照原图按行存储，而是分为四轮扫描，每次存储特定的行。
- 第一轮：每八行取值，起始行索引 0。
- 第二轮：每八行取值，起始行索引 4。
- 第三轮：每四行取值，起始行索引 2。
- 第四轮：每两行取值，起始行索引 1。
- 排序标识。同全局颜色表。
- 保留位。两位。
- 局部颜色表大小。同全局颜色表。
局部颜色表（Local Color Table）
同全局颜色表。
图像数据（Table Based Image Data）
7 6 5 4 3 2 1 0 Field Name Type
+---------------+
| | LZW Minimum Code Size Byte
+---------------+
+===============+
| |
/ / Image Data Data Sub-blocks
| |
+===============+
+---------------+
|0 0 0 0 0 0 0 0| Block Terminator
+---------------+
第一个字节为变成 lzw 编码最短编码长度。
接下来是数据块。数据块由一些列子块组成。子块第一个字节表示子块大小（不包含自身），接下来是子块数据。因为只有一个字节表示大小，所以子块最大 256 个字节。
GIF 数据块的 lzw 压缩有一些规则：
- 最短编码长度为 2-8。即使只有两种颜色，lzw minimum code size 也要为 2。因为颜色表最多 256 种颜色，所以 lzw minimum code size 最大为 8。
- 字符串表（string table）（或者字典表）里，[0, 2^(lzw minimum code size) – 1] 为初始表项。表项值 2^(lzw minimum code size) 为清除标识，即 clear code，缩写 CC。解码时遇到 CC 需要重置 string table，编码长度回到 lzw minimum code size。表项值 2^(lzw minimum code size) + 1 为结束标识，即 end of information，缩写 EOI。遇到该值，停止解码。
- lzw 取值最小位长是 lzw minimum code size + 1，最大位长是 12。当位长 12 时，如果 string table 满了，不再增加位长，而是重置字符串表。编码时需要注意输出 CC 标识，避免解码时溢出。
- 编码时，先输出 code，再判断字符串表的大小是否达到了最大容量（比如 4096）达到了，则继续输出 CC 标识，重置字符串表等。没有达到最大容量，则判断是否达到了当前位的最大容量。达到了则位长加 1，然后添加新表项。否则，直接添加新表项。
纯文本扩展（Plain Text Extension）
7 6 5 4 3 2 1 0 Field Name Type
+---------------+
0 | | Extension Introducer Byte
+---------------+
1 | | Plain Text Label Byte
+---------------+
+---------------+
0 | | Block Size Byte
+---------------+
1 | | Text Grid Left Position Unsigned
+- -+
2 | |
+---------------+
3 | | Text Grid Top Position Unsigned
+- -+
4 | |
+---------------+
5 | | Text Grid Width Unsigned
+- -+
6 | |
+---------------+
7 | | Text Grid Height Unsigned
+- -+
8 | |
+---------------+
9 | | Character Cell Width Byte
+---------------+
10 | | Character Cell Height Byte
+---------------+
11 | | Text Foreground Color Index Byte
+---------------+
12 | | Text Background Color Index Byte
+---------------+
+===============+
| |
N | | Plain Text Data Data Sub-blocks
| |
+===============+
+---------------+
0 | | Block Terminator Byte
+---------------+
纯文本扩展（PTE）扩展标识是 0x01，即文件流碰到 0x21 0x01 的时候即为纯文本扩展。
文本内容为 7 位 ASCII 码，使用等宽字体，使用格子排版，每个字符在一个小格子里。
扩展标识后的第一个字节表示块大小，固定为 12（不含自身）。
前八个字节和图像描述符含义相同。后四个字节分别代表字符小格子宽度、高度，文字颜色、背景色。
数据由一系列子块组成，子块最大 255 字节，最小 1 字节。子块第一个字节为子块大小（不包含自身），其后为数据。
文件结束标识（Trailer）
文件结束标识一个字节，固定为 0x3B。
GIF 文件的结构基本如此。按照上面的介绍，结合标准文档差不多就可以写出编/解码器了。解码器容易一些，编码则涉及到颜色采样问题。因为我们现在用的 JPG 和 PNG 等图片都是真彩色，具备 16,777,216 色的表现能力，怎么将其压缩到 256 色就成了一个问题。