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