Encoding error in GIF LZW compressed stream

[NordCoder]

I'm writing a C library to export SDL_Surfaces to various image formats as an exercise. Now I'm working on the GIF format and I feel I'm very close to getting it working, but I've been at this for a while with no luck. I've already re-read all the specs, wiki entries, various other internet articles on the subject and tried to debug it in all sorts of ways.

My implementation is a modified version of this one.
The specs I've been using are here. Appendix F contains all the details of how the LZW compressed byte stream is created.

My current problem is writing the GIF LZW compressed image data sub-blocks. I've tried different files to see if that had anything to do with it. Everything goes smooth until some position (usually in the first sub-block) where the byte is incorrect compared to the original file. Sometimes the stream 'syncs' up again (but then becomes a mess later on) and sometimes it doesn't. I changed the way I pack bits into the compressed LZW byte-stream (in LZW_PackBits) to a more efficient one, but since it didn't result in a change in the file, I think my error(s) lie somewhere in the dictionary reading/creation (or the error is still present in the bit-packing).

I realize this question strongly resembles a "fix my code for me" question, but I have tried so many things with no luck, and I really need some help or suggestions. I'll be happy to explain anything if necessary since I assume few people have actually worked with the GIF version of LZW.

The code has been stripped of debugging stuff and all the code that writes the headers, color tables etc.

#include "SDL_iw.h"
#include <string.h>
#include <stdlib.h>
#include <math.h>

#define LZW_START_BITS     9
#define LZW_MAX_BITS       12
#define LZW_ALPHABET_SIZE  256
#define LZW_CLEAR_CODE     256
#define LZW_END_CODE       257
#define LZW_FLUSH          1 << LZW_MAX_BITS // Invalid code signals to flush the LZW byte buffer
#define BUFFER_SIZE        255

typedef struct {
    Uint16 next[LZW_ALPHABET_SIZE];
} lzw_entry;

static Uint8 *buffer = NULL;

/* Packs an LZW codepoint of 'bits' length into a buffer as an LZW byte stream */
int LZW_PackBits(SDL_RWops *dst, Uint16 codepoint, Uint8 bits) {
    static Uint32 bit_count     = 0;
    static Uint32 byte_count    = 0;
    static Uint32 bit_reservoir = 0;

    if (codepoint == LZW_FLUSH && byte_count > 0) {
        SDL_RWwrite(dst, &byte_count, 1, 1);
        SDL_RWwrite(dst, buffer, 1, byte_count);
        memset(buffer, byte_count, byte_count);
        byte_count = 0;
    } else {
        if (bits < LZW_START_BITS || bits > LZW_MAX_BITS) {
            IW_SetError("Bit length %d out of bounds in LZW_PackBits", bits);
            return 0;
        }

        bit_reservoir |= codepoint << bit_count;
        bit_count += bits;

        while (bit_count >= 8) {
            buffer[byte_count] = bit_reservoir;
            ++byte_count;
            bit_count -= 8;
            bit_reservoir >>= 8;

            if (byte_count == 255) {
                SDL_RWwrite(dst, &byte_count, 1, 1);
                SDL_RWwrite(dst, buffer, 1, byte_count);
                memset(buffer, 0, byte_count);
                byte_count = 0;
            }
        }
    }

    return 1;
}

int IW_WriteGIF_RW(SDL_Surface *surface, SDL_RWops *dst, int freedst) {
    // Header, color table etc. are written here...

    const Uint8  bpp        = 8;
    const Uint16 clear_code = LZW_CLEAR_CODE;
    const Uint16 end_code   = LZW_END_CODE;
    const Uint8  zero_byte  = 0;

    SDL_RWwrite(dst, &bpp, 1, 1);
    int table_size       = LZW_FLUSH;
    lzw_entry *lzw_table = (lzw_entry*)malloc(sizeof(lzw_entry) * table_size);

    if (!lzw_table) {
        IW_SetError("Out of memory: Failed to allocate LZW table\n");
        goto done;
    }

    for (i = 0; i < table_size; ++i) // i declared earlier...
        memset(&lzw_table[i].next[0], 0, sizeof(Uint16) * LZW_ALPHABET_SIZE);

    buffer = (Uint8*)malloc(BUFFER_SIZE);
    if (!buffer) {
        IW_SetError("Out of memory: Failed to allocate byte buffer\n");
        goto done;
    }

    memset(buffer, 0, BUFFER_SIZE);
    Uint16 next_code = LZW_END_CODE + 1;
    Uint8  out_len   = LZW_START_BITS;
    Uint8  next_byte = 0;
    Uint16 input     = 0;
    Uint16 nc        = 0;

    // Output a clear code
    LZW_PackBits(dst, clear_code, out_len);

    if (SDL_MUSTLOCK(surface))
        SDL_LockSurface(surface);

    Uint8 *pos = (Uint8*)surface->pixels;
    Uint8 *end = (Uint8*)(surface->pixels + surface->pitch * surface->h);
    input = *pos++;

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

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

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

                if (out_len > LZW_MAX_BITS) {
                    LZW_PackBits(dst, clear_code, out_len - 1);
                    out_len   = LZW_START_BITS;
                    next_code = LZW_END_CODE + 1;

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

    if (SDL_MUSTLOCK(surface))
        SDL_UnlockSurface(surface);

    // Pack remaining data and end-of-data marker
    LZW_PackBits(dst, input, out_len);
    LZW_PackBits(dst, end_code, out_len);
    LZW_PackBits(dst, LZW_FLUSH, 0);
    SDL_RWwrite(dst, &zero_byte, 1, 1);

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

    done:
    free(buffer);
    free(lzw_table);

    if (freedst)
        SDL_RWclose(dst);

    return 1;
}

[rubberman]

How was the data compressed? Did you write your own LZW compression tool? From what you are saying, it sounds like the string dictionary is out-of-whack, or that you are accessing it incorrectly. Sorry, but I don't have the cycles right now to analyze your code in regards to that last comment.

[NordCoder]

Hi rubberman,

Thanks for the response. I'm compressing the data myself. The bulk of it happens in lines 101-126 (using the function LZW_PackBits). I'm pretty sure that's the issue, but I can't prove or disprove it.

Yeah, I realize there's a lot of code, but I've run out of ideas.

Basically, the GIF LZW algorithm allows for 4096 (2^12 or 1 << 12) codes. I have a table of size 4096 of lzw_entry structs (line 68 and 14-16). In each one, there's an array of 256 Uint16's. Let's say I encounter the sequence 0, 0, 0... and I'm looking at the first two bytes: lzw_table[0][0] == 0, so the sequence has not yet been seen. Thus we store the first available code (258 according to the specs) as lzw_table[0][0] = 258 and write code 0. When I look at the next two I discover that lzw_table[0][0] == 258, but since I have not yet seen lzw_table[258][0] (corresponds to the sequence 0, 0, 0), I write code 258. Thus the data is being compressed.

I hope that helps :) As a note, most space/speed efficient implementations I've seen use a hashtable usually with some kind of open addressing, but I really want to solve this problem before I move on to writing a hashtable in C...