LZW 压缩，解压算法实现。

压缩算法:

#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

#define X(shift) (1 << (shift))
static int test_mask[32] = {
    X(0x00), X(0x01), X(0x02), X(0x03), X(0x04), X(0x05), X(0x06), X(0x07),
    X(0x08), X(0x09), X(0x0a), X(0x0b), X(0x0c), X(0x0d), X(0x0e), X(0x0f),
    X(0x10), X(0x11), X(0x12), X(0x13), X(0x14), X(0x15), X(0x16), X(0x17),
    X(0x18), X(0x19), X(0x1a), X(0x1b), X(0x1c), X(0x1d), X(0x1e), X(0x1f),
};

struct lzwc_ctx {
    size_t lc_bpp;
    size_t lc_bitcnt;
    size_t lc_dicode;
    size_t lc_testbl[4096 * 256 / sizeof(size_t) / 8];
    size_t lc_dictbl[4096 * 256];

    size_t lc_outcnt;
    char lc_outbuff[8192 + 4];

    size_t lc_outbit_cnt;
    uint32_t lc_outbit_buff;
};

inline void lzwc_restart(struct lzwc_ctx * ctxp)
{
    ctxp->lc_dicode = (1 << ctxp->lc_bpp) + 2;
    ctxp->lc_bitcnt = (ctxp->lc_bpp + 1);
    if (ctxp->lc_dicode >= (1 << ctxp->lc_bitcnt))
        ctxp->lc_bitcnt++;
    memset(ctxp->lc_testbl, 0, sizeof(ctxp-> lc_testbl));
}

inline void lzwc_init(struct lzwc_ctx * ctxp, int bpp)
{
    memset(ctxp, 0, sizeof(struct lzwc_ctx));
    ctxp->lc_bpp = bpp;
    lzwc_restart(ctxp);
}

inline int lzwc_find(struct lzwc_ctx * ctxp, int prefix, int code)
{
    int key = (prefix << 8) | code;
    assert (code < (1 << ctxp->lc_bpp));
    if (ctxp->lc_testbl[key >> 5] &
            test_mask[key & 0x1F]) 
        return ctxp->lc_dictbl[key];
    return -1;
}

inline int lzwc_update(struct lzwc_ctx * ctxp, int prefix, int code)
{
    int key = (prefix << 8) | code;
    ctxp->lc_testbl[key >> 5] |= test_mask[key & 0x1F];
    ctxp->lc_dictbl[key] = ctxp->lc_dicode++;
    return ctxp->lc_dicode;
}

void lzwc_output(struct lzwc_ctx * ctxp, size_t code, FILE *fp)
{
    size_t mask = (1 << ctxp->lc_bitcnt) - 1;

    ctxp->lc_outbit_buff |= ((code & mask) << ctxp->lc_outbit_cnt);
    ctxp->lc_outbit_cnt += ctxp->lc_bitcnt;

    while (ctxp->lc_outbit_cnt >= 8) {
        char outch = (ctxp->lc_outbit_buff & 0xFF);
        ctxp->lc_outbuff[ctxp->lc_outcnt++] = outch;
        ctxp->lc_outbit_buff >>= 8;
        ctxp->lc_outbit_cnt -= 8;
    }
    if (ctxp->lc_outcnt >= 8192) {
        fwrite(ctxp->lc_outbuff, 1, ctxp->lc_outcnt, fp);
        ctxp->lc_outcnt = 0;
    }
    if (mask < ctxp->lc_dicode) {
        ++ctxp->lc_bitcnt;
    }
}

void lzwc_clear(struct lzwc_ctx * ctxp, FILE * fp)
{
    int clear = (1 << ctxp->lc_bpp);
    lzwc_output(ctxp, clear, fp);
}

void lzwc_finish(struct lzwc_ctx * ctxp, size_t code, FILE *fp)
{
    int fin_code = (1 << ctxp->lc_bpp) + 1;
    lzwc_output(ctxp, code, fp);
    lzwc_output(ctxp, fin_code, fp);
    lzwc_output(ctxp, 0, fp);
    fwrite(ctxp->lc_outbuff, 1, ctxp->lc_outcnt, fp);
    ctxp->lc_outcnt = 0;
}

int main(int argc, char *argv[])
{
    int prefix = -1;
    int i, j, count;
    uint8_t buffer[8192];

    struct lzwc_ctx * ctxp = NULL;
    ctxp = (struct lzwc_ctx *) malloc( sizeof(struct lzwc_ctx) );
    assert (ctxp != NULL);
    lzwc_init(ctxp, 8);

    FILE *fout = fopen("output.lzw", "wb");
    lzwc_clear(ctxp, fout);

    for (i = 1; i < argc; i++) {
        FILE *fp = fopen(argv[i], "rb");

        if (fp == NULL)
            continue;

        while ( !feof(fp) ) {
            count = fread(buffer, 1, sizeof(buffer), fp);
            for (j = 0; j < count; j++) {
                int code = buffer[j];
                if (prefix == -1) {
                    prefix = code;
                    continue;
                }
                int prefix1 = lzwc_find(ctxp, prefix, code);
                if (prefix1 != -1) {
                    assert(prefix1 <= ctxp->lc_dicode);
                    prefix = prefix1;
                    continue;
                }
                lzwc_output(ctxp, prefix, fout);
                if (lzwc_update(ctxp, prefix, code) < 4096) {
                    prefix = code;
                    continue;
                }
                lzwc_clear(ctxp, fout);
                prefix = code;
                lzwc_restart(ctxp);
            }
        }
        fclose(fp);
    }
    lzwc_finish(ctxp, prefix, fout);
    free(ctxp);
    fclose(fout);
    return 0;
}

解压算法:

#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <assert.h>

static size_t old = 0;
static size_t cmax = 0;
static size_t cclear = 256;

static size_t bitmask = 0;
static size_t bitsize = 9;

static char * dictp[4096];
static size_t dictl[4096];

static char output[1024*1024*3*3];
static char * outptr = output;

int lzw_init()
{
    int i;
    cclear = 256;
    static char color[256];
    for (i=0; i<cclear; i++){
        dictp[i] = color+i;
        dictl[i] = 1;
        color[i] = i;
    }
    old = 0;
    bitsize = 9;
    outptr = output;
    bitmask = (1<<bitsize)-1;
    cmax = cclear+1;
    return cmax;
}

int lzw_code(size_t code)
{
    if (code > 4096){
        printf("%x %x %x %d %x\n", code, cmax, bitmask, bitsize, old);
    }
    assert(code <= 4096);
    if (code > cmax){
        printf("%d %d\n", cmax, code);
    }
    assert(code <= cmax);
    char *oldptr = outptr;
    if (code < cmax){
        size_t dl = dictl[code];
        memcpy(outptr, dictp[code], dl);
        dictl[cmax] = dictl[old]+1;
        char *p = outptr-dictl[old];
        //assert(!memcmp(p, dictp[old], dictl[old]));
        dictp[cmax] = p;
        outptr += dl;
    }else{
        size_t dl = dictl[old];
        memcpy(outptr, dictp[old], dl);
        outptr[dl] = *outptr;
        dictp[cmax] = outptr;
        dictl[cmax] = dl+1;
        outptr += (dl+1);
    }

#if 0
    printf("------------------------\n");
    while (oldptr<outptr)
        printf("%02x ", 0xff&*oldptr++);
    printf("\n");
#endif
    old = code;
    return ++cmax;
}

int main(int argc, char *argv[])
{
    int i, j, count;
    uint8_t buffer[8192];

    int outbit_cnt = 0;
    uint32_t outbit_buff = 0;

    FILE *fout = fopen("output.orig", "wb");

    lzw_init();
    for (i=1; i<argc; i++){
        FILE *fp = fopen(argv[i], "rb");

        if (fp == NULL){
            continue;
        }

        while (!feof(fp)){
            count = fread(buffer, 1, sizeof(buffer), fp);
            for (j=0; j<count; j++){
                outbit_buff |= (buffer[j]<<outbit_cnt);
                outbit_cnt += 8;

                while (outbit_cnt >= bitsize){
                    size_t code = bitmask&outbit_buff;
                    outbit_buff >>= bitsize;
                    outbit_cnt -= bitsize;

                    if (code == cclear){
                        fwrite(output, outptr-output, 1, fout);
                        lzw_init();
                        continue;
                    }
                    if (code == cclear+1){
                        printf("end stream!\n");
                        fwrite(output, outptr-output, 1, fout);
                        outptr = output;
                        break;
                    }
                    if (lzw_code(code) > bitmask){
                        if (bitsize < 12){
                            bitmask = bitmask*2+1;
                            bitsize++;
                        }
                    }
                }
            }
        }
        fclose(fp);
    }
    fwrite(output, outptr-output, 1, fout);
    outptr = output;
    fclose(fout);
    return 0;
}