需要帮助解压缩GIF光栅数据

Question

我有一个10x10的gif，由4种颜色组成，白色，红色，蓝色，黑色。我已经解析了

下面的gif数据

4749 4638 3961                      <-- header
0a00 0a00 9100 00                   <-- lsd (pb 91 = 1001 0001) nColors = 4, bytes = 12
ffffff ff0000 0000ff 000000         <-- global color table
                                    #0  FF FF FF
                                    #1  FF 00 00
                                    #2  00 00 FF
                                    #3  00 00 00
21f9 04(00) (0000) (00)00           <-- graphics control extension 
                                    (00) = pb (000 reserved 000 disposal method 0 user input flag 0 transparent color flag) 
                                    (0000) = delay time                     
                                    (00) = transparent color index
2c 0000 0000 0a00 0a00 00           <-- image descriptor
02 16                               <-- (image data - 02 = lzw min code size, 0x16 size of image (bytes))
8c2d 9987 2a1c dc33 a002 75ec 95fa a8de 608c 0491 4c01 00   <-- image block
3b  

我们有上面的图像数据(标记为image block)我试图解压缩它，这样我就能得到原始图像。我的理解是，从左到右读取字节，从右到左读取位，从lzwmincodesize + 1开始(2 + 1位=每次3位)。

这是我要遵循的解压缩算法

Initialize code table
let CODE be the first code in the code stream
output {CODE} to index stream
<LOOP POINT>
let CODE be the next code in the code stream
is CODE in the code table?
Yes:
    output {CODE} to index stream
    let K be the first index in {CODE}
    add {CODE-1}+K to the code table
No:
    let K be the first index of {CODE-1}
    output {CODE-1}+K to index stream
    add {CODE-1}+K to code table
return to LOOP POINT

我正在逐步完成解压缩算法，这是我到目前为止得到的结果…(从前3个字节码开始)

Global Color Table
000 FF FF FF
001 FF 00 00
010 00 00 FF
011 00 00 00
100 CLEAR
101 End of Data
 3  2   1   6  5   4      8   7    
10|001|100  0|010|110|1  100|110|01
last        current     output      cindex      exists      dictionary      value
            100                     4                                       CLEAR
100         001         001         1           y                           RED
001         110         001 001     6           n           +001 001        RED RED
001 001     110         001 001     6           y           +001 001 001    RED RED
001 001     010         010         2           y           +001 001 010    BLUE
010         010         010         2           y           +010 010        BLUE
010         110         001 001     6           y           +010 001 001    RED RED
001 001     100                     4                                       CLEAR
100         111         111         7 ???? <--- (what do I do here)?

我应该得到5个红色值，然后是前10个像素的5个蓝色值，但正如你所看到的，它解码了5个红色，然后2个蓝色，然后2个红色。有人能指出我哪里做错了吗?

谢谢

Answer 1

您的错误来自忽略了代码大小的增加。以下是代码，"nextcode"值和当前代码大小:

Code read from bitstream:    100, 001, 110, 110, 0010, 1001
internal 'Next' code value:  110, 110, 110, 111, 1000, 1001
current code size:             3,   3,   3,   3,    4,    4

解码循环中缺少的逻辑是，您需要维护一个"nextcode"变量，该变量告诉您在表中插入代码的位置以及何时增加代码大小。它从值"clearcode + 2"开始，并在从比特流读取每个代码后增加(在第一个非CC值之后)。逻辑基本上是这样的:

clear_dictionary:
clearcode = 1<<codestart;
codesize = codestart+1;
nextcode = clearcode + 2;
nextlimit = 1<<(codesize+1);
oldcode = -1;
mainloop:
while (!done)
{
code = getCode();
if (code == clearcode)
   goto clear_dictionary;
if (oldcode == -1)
{
   write_code_to_output(code);
}
else
{
   <LZW logic>
   nextcode++;
   if (nextcode >= nextlimit)
   {
      nextlimit <<= 1;
      codesize++;
   }
}
oldcode = code;
} // while !done