gif图片介绍和LZW算法说明

kaixiansheng

浏览: 13154 次

最近访客更多访客>>

paomian8

siemens800

clhero

IT小鑫

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

图片相关

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++;
		}
}

将蓝色的代码去掉。

这样对于超出解码表的像素不再进行解析。