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