GIF LZW 압축 된 스트림의 인코딩 오류

Question

연습용으로 다양한 형식의 SDL_Surfaces를 내보내는 C 라이브러리를 작성 중이며 지금까지 BMP, TGA 및 PCX 형식을 사용했습니다. 이제는 GIF 형식으로 작업하고 있으며 작동하는 데 아주 가깝다고 생각합니다. 내 구현은 수정 된 버전 this one입니다.

현재 문제는 GIF LZW 압축 이미지 데이터 하위 블록을 작성하는 것입니다. 첫 번째 하위 블록에서 위치 208까지 모든 것이 부드럽게 진행됩니다. 원본 파일의 3 바이트는 (위치 207부터 시작) : "B8 29 B2"(16 진수), "B8 41 B2"입니다. 그 후에 바이트는 다시 까지 "동기화"됩니다. 압축 된 스트림을 더 내려 보면 비슷한 차이점을 발견 할 수 있습니다. 아마도 이 첫 번째 오류로 인해 발생했습니다. 내 파일도 원래 파일보다 짧습니다.

lxw_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); 

UPDATE가 :) : 좀 더 많은 테스트를 수행하고, 비트 패킹 알고리즘을 구현했습니다 그 아키 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? 

} 

사전에

4 메가 ​​바이트 메모리는 많은 (특히 표준이 개발되었을 때, 올해 1987에 비해), 그러나 아마 보다 복잡한 해시 테이블을 작성하는 것이 정당합니다. 기본 단위는 짧을 수 있습니다. 테이블에 코드 + 1을 쓰면 (그리고 테이블 [a] .next [b] -1로 읽으면) 0으로 초기화 할 수 있습니다.

테이블 지우기를 최적화 할 수 있습니다. 4MB의 메모리가 예약되었지만 사용 된 4KB 미만의 항목이 있습니다.

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;