lzw.c

#include <book.h>
#define CODE_MAX 65534
#define DICT (1 << 17)
#define LZWEOF 256
struct { int32_t parent;  int16_t c, code; } dict[DICT];
void encode(FILE * in, FILE * out) {
    int nc = LZWEOF + 1, c, sc, i;
    COPY(dict[i].code, -1, DICT);
    if ((sc = fgetc(in)) == EOF) sc = LZWEOF;
    while ((c = fgetc(in)) != EOF) {
        for (i = (((c * 0xDF3703BFU) >> 8) ^ sc) % DICT;
            dict[i].code != -1 && (dict[i].parent != sc || dict[i].c != c);
            i++, i %= DICT);
        if (dict[i].code != -1) sc = dict[i].code; else {
            if (nc <= CODE_MAX)
                dict[i].code = nc++, dict[i].parent = sc, dict[i].c = c;
            fputc(sc >> 8, out);  fputc(sc, out);  sc = c;
        }
    }
    fputc(sc >> 8, out);  fputc(sc, out);  fputc(1, out);  fputc(0, out);
}
void decode(FILE * in, FILE * out) {
    #define READ2(var) \
        var = fgetc(in) << 8, var |= fgetc(in); \
        if (var == LZWEOF || feof(in)) return;
    static char stack[DICT];
    int next = LZWEOF + 1, new, old, code, n, c, tmp;
    READ2(old);
    for (fputc(c = old, out);; old = new) {
        READ2(new);  n = DICT - 1;
        if (new >= next) stack[n--] = c, code = old; else code = new;
        for (; code > 255; code = dict[code].parent) stack[n--] = dict[code].c;
        stack[n--] = c = code;  fwrite(stack + n + 1, 1, DICT - n - 1, out);
        if (next <= CODE_MAX) dict[next].parent = old, dict[next].c = c, next++;
    }
}