gif图片介绍和LZW算法说明
GIF图片介绍和LZW算法说明
1. GIF格式
GIF图像的文件格式如下：
重点字段介绍：
逻辑屏幕标志符：包含了逻辑屏幕的长宽，是否包含全局颜色列表，背景色等。
全局颜色列表：包含了图片中使用的所有颜色，而图片的数据使用全局颜色列表中的索引代替。
图像块：gif的数据是由数据块组成，每个数据块的长度最大为255
2. LZW算法
全称为“串表压缩算法”，LZW代表了研发该算法的三个人（坑爹啊，还以为是英文缩写）。属于字典编码的一种，最大的优点在于压缩后的数据不需要额外携带字典就可以解压。GIF采用LZW算法进行编码的。
2.1 首先介绍几个相关术语：
数据流：需要进行编码的数据串，GIF中指像素的颜色值。LZW编码时的输入
编码流：数据流编码的结果。LZW编码时的输出
编译表：编码时候的字典表，是动态建立的。
字符：数据流中最基本的单位，GIF中一个像素的颜色在颜色列表中的序号。
字符串：由连续字符组成的，前缀和后缀一起代表了字符串
前缀：也是字符串，但可以为空。具体解释见下文
后缀：也是字符串，一个字符就是后缀，可以为空。具体解释见下文
2.2 编码流程
首先举一个简单的例子，有一个数据流为：abcbabbac
我们为了和数据流的字符进行区别，我们采用1,2,3这样的数字进行编码。数据流中可能出现的字符为，a~z，所以我们初始化编译表，用1~26，代表a~z单个字符。所以对于其它的字符串只能从27进行编码。初始化前缀为空，后缀也为空，编码流为空，编译表为1~26和a~z的对应。
1.2.1 从数据流取字符a作为后缀，前缀为空，字符串为a，在编译表中存在，为1，字符串变前缀。前缀：a；后缀：空；字符串：a；编码流：空；编译表：单个字符的对应（后面不再显示）
1.2.2 取字符b作为后缀，字符串为：ab，编译表中不存在，定义ab为27，前缀输出，后缀变前缀。前缀：b；后缀：空；字符串：b；编码流：1；编译表：27=ab
1.2.3 取字符c作为后缀，字符串为：bc，编译表不存在，定义bc为28，前缀输出，后缀变前缀。前缀：c；后缀：空；字符串：c；编码流：1-2；编译表：27=ab 28=bc
1.2.4 取字符b作为后缀，字符串为：cb，编译表不存在，定义cb为29，前缀输出，后缀变前缀。前缀：b；后缀：空；字符串：b；编码流：1-2-3；编译表：27=ab 28=bc 29=cb
1.2.5 取字符a作为后缀，字符串为：ba，编译表不存在，定义ba为30，前缀输出，后缀变前缀。前缀：a；后缀：空；字符串：a；编码流：1-2-3-2；编译表：27=ab 28=bc 29=cb 30=ba
1.2.6 取字符b作为后缀，字符串为：ab，编译表存在，为27，字符串变前缀。前缀：ab；后缀：空；字符串：ab；编码流：1-2-3-2；编译表：27=ab 28=bc 29=cb 30=ba
1.2.7 取字符b作为后缀，字符串为：abb，编译表不存在，定义abb为31，前缀输出，后缀变前缀。前缀：b；后缀：空；字符串：b；编码流：1-2-3-2-27；编译表：27=ab 28=bc 29=cb 30=ba 31=abb
1.2.8 取字符a作为后缀，字符串为：ba，编译表存在，为30，字符串变前缀。前缀：ba；后缀：空；字符串：ba；编码流：1-2-3-2-27；编译表：27=ab 28=bc 29=cb 30=ba 31=abb
1.2.9 取字符c作为后缀，字符串为：bac，编译表不存在，定义bac为32，前缀输出，后缀变前缀。前缀：c；后缀：空；字符串：c；编码流：1-2-3-2-27-30；编译表：27=ab 28=bc 29=cb 30=ba 31=abb 32=bac
1.2.10 输入流没有字符，将前缀c输出，最终编码流为：1-2-3-2-27-30-3
能够看到原来的9个字符被压缩成7个字符。
GIF是基于颜色列表的图片结构，GIF的数据对应的是每个点的颜色在颜色列表的索引，LZW编码是对该索引进行的编码。在GIF格式的图片中，对LZW做了一些改变：
1. 首先定义编码长度，gif中最大编码长度为12位，能表示的最大数字为4096，因此，编译表中序号不能超过4096.
2. gif最大支持256色，因此gif编码长度为9~12位。采用变长编码，到1023，再编码就改为10位，以此类推。
3. gif定义了clear code，清除标记为原始数据长度+1，比如gif最大值为255，那么清除标记为256. 当一个编译的时候，如果编译表达到了最大值，比如4096，就要插入一个clear code，即可以清空编译表，重新开始编译。
4. gif定义了结束标记end，end为清除标记+1， gif中为257，当gif的一张图片编码数据结束后插入end，表示图片结束。
GIF图片编码举例：
输入流：10 21 22 26 10 21 22 10 26
编译表：1~255，256(clear code)，257（end）
| 输入 | 前缀 | 后缀 | 字符串 | 编译表 | 输出 |
| 10 | 10 | ( ，10) | |||
| 21 | 10 | 21 | (10, 21) | 258=(10, 21) | 10 |
| 22 | 21 | 22 | (21, 22) | 259=(21, 22) | 21 |
| 26 | 22 | 26 | (22, 26) | 260=(22, 26) | 22 |
| 10 | 26 | 10 | (26, 10) | 261=(26, 10) | 26 |
| 21 | 10 | 21 | (10, 21) | ||
| 22 | 258 | 22 | (258, 22) | 262=(258, 22) | 258 |
| 10 | 22 | 10 | (22. 10) | 263=(22, 10) | 22 |
| 26 | 10 | 26 | (10, 26) | 264=(10, 26) | 10 |
最后的输出流为：10 21 22 26 258 22 10 26
具体流程图为：
1.2 解码流程
对于1.1中第一个例子，压缩后的编码为1-2-3-2-27-30-3。初始化后的编码表为1~26对应a~z。
1.2.1 读入值1，编译表中存在，输出a，输入做前缀，字符串为a，也在编译表中，前缀为a
1.2.2 读入值2，编译表中存在，输出b，，将b作为后缀，字符串为ab，不在编译表中，定义27=ab，输入做前缀，前缀为b
1.2.3 读入值3，编译表中存在，输出c，将c作为后缀，字符串为bc，不在编译表中，定义28=bc，输入做前缀，前缀为c
1.2.4 读入值2，编译表中存在，输出b，将b作为后缀，字符串为cb，不在编译表中，定义29=cb，输入做前缀，前缀为b
1.2.5 读入值27，编译表中存在，输出ab，将a作为后缀，字符串为ba，不在编译表中，定义30=ba，输入做前缀，前缀为ab
1.2.6 读入值30，编译表中存在，输出ba，将b作为后缀，字符串为abb，在编译表中，输入做前缀为ba
1.2.7 读入值3，编译表中存在，输出c，将c作为后缀，字符串为bac，不在编译表中，定义32=bac，前缀为c
解码后的输出为：abcbabbac
上述第二个例子同理，不再赘述。
如果读入值30后，编译表中不存在，则将上次输入的值+该值的第一个字符输出，将该输出定义为30
流程图为：
3. GraphicsMagic
在使用中发现GM对于有些gif文件无法解析
3.1 bug分析
GM解析gif图片的部分代码：
for (x=0; x < (long) image->columns; )
{
if (top_stack == pixel_stack)
{
if (bits < code_size)
{
/*
Load bytes until there is enough bits for a code.
*/
if (count == 0)
{
/*
Read a new data block.
*/
count=ReadBlobBlock(image,packet);
if (count == 0)
break;
c=packet;
}
datum+=(unsigned long) (*c) << bits;
bits+=8;
c++;
count--;
continue;
}
/*
Get the next code.
*/
code=(long) (datum & code_mask);
datum>>=code_size;
bits-=code_size;
/*
Interpret the code
*/
if (code > available)
{
status=MagickFail;
break;
}
if (code == end_of_information)
break;
if (code == clear)
{
/*
Reset decoder.
*/
code_size=data_size+1;
code_mask=(1 << code_size)-1;
available=clear+2;
old_code=NullCode;
continue;
}
if (old_code == NullCode)
{
*top_stack++=suffix[code];
old_code=code;
first=(unsigned char) code;
continue;
}
in_code=code;
if (code >= available)
{
*top_stack++=first;
code=old_code;
}
while (code >= clear)
{
if ((top_stack-pixel_stack) >= MaxStackSize)
{
status=MagickFail;
break;
}
*top_stack++=suffix[code];
code=prefix[code];
}
if (status == MagickFail)
break;
first=suffix[code];
/*
Add a new string to the string table,
*/
if (available >= MaxStackSize)
{
(void) LogMagickEvent(CoderEvent,GetMagickModule(),
"Excessive LZW string data "
"(string table overflow)");
status=MagickFail;
break;
}
*top_stack++=first;
prefix[available]=(short) old_code;
suffix[available]=first;
available++;
if (((available & code_mask) == 0) && (available < MaxStackSize))
{
code_size++;
code_mask+=available;
}
old_code=in_code;
}
/*
Pop a pixel off the pixel stack.
*/
top_stack--;
index=(*top_stack);
VerifyColormapIndex(image,index);
indexes[x]=index;
*q=image->colormap[index];
q->opacity=(Quantum)
(index == opacity ? TransparentOpacity : OpaqueOpacity);
x++;
q++;
}
结果发现对于有些gif文件，使用gm进行解析会出错，通过debug发现错误信息为：
Excessive LZW string data (string table overflow)
可知当available>4096时会出现该错误。原因是对于有些gif文件没有严格遵守gif格式，导致解码表超过4096。
3.2 解决方案
将上述红色的代码改为：
if (available < MaxStackSize)
{
prefix[available]=(short) old_code;
suffix[available]=first;
available++;
if (available >= code_mask + 1 && code_size < 12U)
{
code_size++;
}
}
将蓝色的代码去掉。
这样对于超出解码表的像素不再进行解析。