c - GIF LZW 压缩流中的编码错误

Question

我正在编写一个 C 库来将 SDL_Surfaces 导出为各种格式作为练习，到目前为止，我已经搞定了 BMP、TGA 和 PCX 格式。现在我正在制作 GIF格式，我觉得我已经非常接近让它发挥作用了。我的实现是this one的修改版本.

我当前的问题是编写GIF LZW压缩图像数据子 block 。一切都很顺利，直到第一个子 block 中的位置208。原始文件中的三个字节是(从位置207开始):十六进制的“B8 29 B2”，我的是“B8 41 B2”。之后，字节“同步”起来再次。在压缩流的更深处，我可能会发现类似的差异由第一个错误引起。我的文件也比原始文件短。

我应该注意，我将 lzw_entry 结构的类型从 uint16_t 更改为 int 以允许-1 表示“空”条目，因为 0 是有效条目。这并没有真正带来什么不同但在压缩流中。原始实现使用未初始化的数据来标记一个空条目。

我认为我错误地读取了字典值，这就是为什么我在位置 208 处得到了比预期更多的代码。否则，我的位打包不正确。

我添加了压缩代码的精简版本。可能是什么问题？还有，我怎样才能要么让我的“字典”数据结构更好，要么让比特流写入更快？

最后，我也知道我可以在这里或那里优化一些代码:)

static Uint8 bit_count = 0;
static Uint8 block_pos = 0;

int LZW_PackBits(SDL_RWops *dst, Uint8 *block, int code, Uint8 bits) {
    Uint8 out = 0;

    while (out != bits) {
        if (bit_count == 8) {
            bit_count = 0;

            if (block_pos == 254) { // Thus 254 * 8 + 8 == 2040 -> 2040 / 8 = 255 -> buffer full
                ++block_pos;
                SDL_RWwrite(dst, &block_pos, 1, 1);
                SDL_RWwrite(dst, &block[0], 1, block_pos);
                memset(block, 0, block_pos);
                block_pos = 0;
            } else
                ++block_pos;
        }

        block[block_pos] |= (code >> out & 0x1) << bit_count;
        ++bit_count; ++out;
    }

    return 1;
}

#define LZW_MAX_BITS      12
#define LZW_START_BITS    9
#define LZW_CLEAR_CODE    256
#define LZW_END_CODE      257
#define LZW_ALPHABET_SIZE 256

typedef struct {
    int next[LZW_ALPHABET_SIZE]; // int so that -1 is allowed
} lzw_entry;

int table_size       = 1 << LZW_MAX_BITS; // 2^12 = 4096
lzw_entry *lzw_table = (lzw_entry*)malloc(sizeof(lzw_entry) * table_size);

for (i = 0; i < table_size; ++i)
    memset(&lzw_table[i].next[0], -1, sizeof(int) * LZW_ALPHABET_SIZE);

Uint8 block[255];
memset(&block[0], 0, 255);
Uint16 next_entry = LZW_END_CODE + 1;
Uint8  out_len    = LZW_START_BITS;
Uint8  next_byte  = 0;
int    input      = 0;
int    nc         = 0;

LZW_PackBits(dst, block, clear_code, out_len);

Uint8 *pos = ... // Start of image data
Uint8 *end = ... // End of image data
input = *pos++;

while (pos < end) {
    next_byte = *pos++;
    nc = lzw_table[input].next[next_byte];

    if (nc >= 0) {
        input = nc;
        continue;
    } else {
        LZW_PackBits(dst, block, input, out_len);
        nc    = lzw_table[input].next[next_byte] = next_entry++;
        input = next_byte;
    }

    if (next_entry == (1 << out_len)) { // Next code requires more bits
        ++out_len;

        if (out_len > LZW_MAX_BITS) {
            // Reset table
            LZW_PackBits(dst, block, clear_code, out_len - 1);
            out_len = LZW_START_BITS;
            next_entry = LZW_END_CODE + 1;

            for (i = 0; i < table_size; ++i)
                memset(&lzw_table[i].next[0], -1, sizeof(int) * LZW_ALPHABET_SIZE);
        }
    }
}

// Write remaining stuff including current code (not shown)
LZW_PackBits(dst, block, end_code, out_len);
++block_pos;
SDL_RWwrite(dst, &block[0], 1, block_pos);
SDL_RWwrite(dst, &zero_byte, 1, 1);

const Uint8 trailer = 0x3b; // ';'
SDL_RWwrite(dst, &trailer, 1, 1);

更新:我做了更多测试，并实现了 Aki Suihkonen 建议的位打包算法。它没有产生明显的差异，这告诉我，我在 lzw_table 结构中以某种方式错误地查找/存储代码，并且错误位于主循环中。

Answer 1

这不是问题的原因，但是有必要时不时地写一下字符255吗？
SDL_RWwrite(dst, &block_pos, 1, 1);

第一个指针如何使位写入更快:

void bitpacker(int what, int howmany)
{
   static unsigned int bit_reservoir=0;
   static int bits_left = 0;
   static unsigned char *my_block = start_of_block;

   bit_reservoir|=what<<bits_left;   // you can optionally mask: (what & ((1<<howmany)-1))
   bits_left+=howmany;
   while (bits_left >= 8) {
       *myblock++ = bit_reservoir;
       bits_left-=8;
       bit_reservoir>>=8;            // EDIT: added, even though it's so obvious :)
       if (myblock==end_of_block) { my_block=start_of_block;  
           write(my_block,1,block_size, outputfile);
       }
   }
   // and while we are here, why not reserve a few kilobytes at least for myblock?

}

字典的 4MB 内存是很多(特别是与 1987 年标准制定时相比)，但可能不足以证明编写更复杂的哈希表是合理的。但基本单元可能会很短。如果您只需将 code+1 写入表(并将其读取为 table[a].next[b] -1)，您也可以将其初始化为零。

桌面清理可以优化。保留了 4MB 内存，但使用的条目少于 4k。

 int *clear_table[MAX_CODES];
 ...
 {
     // memorize the address that is changed...
     int *tmp = clear_table[next_entry] = &lzw_table[input].next[next_byte];
     nc    = *tmp = next_entry++;
 }
 if (need_to_clear) { for (int i=258;i<MAX_CODE;i++) *(clear_table[i]) = 0;