diff options
Diffstat (limited to 'filter/lzwd.c')
| -rw-r--r-- | filter/lzwd.c | 263 |
1 files changed, 263 insertions, 0 deletions
diff --git a/filter/lzwd.c b/filter/lzwd.c new file mode 100644 index 00000000..1ab47357 --- /dev/null +++ b/filter/lzwd.c @@ -0,0 +1,263 @@ +#include <fitz.h> + +/* TODO: error checking */ + +#define noDEBUG 1 + +#ifdef DEBUG +#define DPRINT(...) fprintf(stderr, __VA_ARGS__) +#else +#define DPRINT(...) +#endif + +enum +{ + MINBITS = 9, + MAXBITS = 12, + NUMCODES = (1 << MAXBITS), + LZW_CLEAR = 256, + LZW_EOD = 257, + LZW_FIRST = 258, +}; + +typedef struct lzw_code_s lzw_code; + +struct lzw_code_s +{ + int prev; /* prev code (in string) */ + unsigned short length; /* string len, including this token */ + unsigned char value; /* data value */ + unsigned char firstchar; /* first token of string */ +}; + +typedef struct fz_lzwd_s fz_lzwd; + +struct fz_lzwd_s +{ + fz_filter super; + + int earlychange; + + unsigned int word; /* bits loaded from data */ + int bidx; + + int resume; /* resume output of code from needout */ + int codebits; /* num bits/code */ + int code; /* current code */ + int oldcode; /* previously recognized code */ + int nextcode; /* next free entry */ + lzw_code table[NUMCODES]; +}; + +fz_error * +fz_newlzwd(fz_filter **fp, fz_obj *params) +{ + int i; + + FZ_NEWFILTER(fz_lzwd, lzw, lzwd); + + lzw->earlychange = 0; + + if (params) { + fz_obj *obj; + obj = fz_dictgets(params, "EarlyChange"); + if (obj) lzw->earlychange = fz_toint(obj) != 0; + } + + lzw->bidx = 32; + lzw->word = 0; + + for (i = 0; i < 256; i++) { + lzw->table[i].value = i; + lzw->table[i].firstchar = i; + lzw->table[i].length = 1; + lzw->table[i].prev = -1; + } + + for (i = LZW_FIRST; i < NUMCODES; i++) { + lzw->table[i].value = 0; + lzw->table[i].firstchar = 0; + lzw->table[i].length = 0; + lzw->table[i].prev = -1; + } + + lzw->codebits = MINBITS; + lzw->code = -1; + lzw->nextcode = LZW_FIRST; + lzw->oldcode = -1; + lzw->resume = 0; + + return nil; +} + +void +fz_freelzwd(fz_filter *filter) +{ + fz_free(filter); +} + +static inline void eatbits(fz_lzwd *lzw, int nbits) +{ + lzw->word <<= nbits; + lzw->bidx += nbits; +} + +static inline fz_error * fillbits(fz_lzwd *lzw, fz_buffer *in) +{ + while (lzw->bidx >= 8) + { + if (in->rp + 1 > in->wp) + return fz_ioneedin; + lzw->bidx -= 8; + lzw->word |= *in->rp << lzw->bidx; + in->rp ++; + } + return nil; +} + +fz_error * +fz_processlzwd(fz_filter *filter, fz_buffer *in, fz_buffer *out) +{ + fz_lzwd *lzw = (fz_lzwd*)filter; + unsigned char *s; + int len; + + if (lzw->resume) { + lzw->resume = 0; + goto output; + } + + while (1) + { + if (fillbits(lzw, in)) { + DPRINT("FILL[eof=%d] bidx=%d word=%08x\n", in->eof, lzw->bidx, lzw->word); + if (in->eof) { + if (lzw->bidx > 32 - lzw->codebits) { + out->eof = 1; + return fz_iodone; + } + } + else { + return fz_ioneedin; + } + } + + lzw->code = lzw->word >> (32 - lzw->codebits); + + DPRINT("CODE[%d]: %03x (%d)\n", lzw->codebits, lzw->code, lzw->code); + + if (lzw->code == LZW_EOD) + { + DPRINT("-> LZW_EOD\n"); + + eatbits(lzw, lzw->codebits); + out->eof = 1; + return fz_iodone; + } + + if (lzw->code == LZW_CLEAR) + { + DPRINT("-> LZW_CLEAR\n"); + + int oldcodebits = lzw->codebits; + + lzw->codebits = MINBITS; + lzw->nextcode = LZW_FIRST; + + lzw->code = lzw->word >> (32 - oldcodebits - MINBITS) & ((1 << MINBITS) - 1); + + DPRINT("CODE[%d]: %03x (%d) [after CLEAR]\n", lzw->codebits, lzw->code, lzw->code); + + if (lzw->code == LZW_EOD) { + DPRINT("-> LZW_EOD\n"); + + eatbits(lzw, oldcodebits + MINBITS); + out->eof = 1; + return fz_iodone; + } + + DPRINT("-> %d\n", lzw->code); + + if (out->wp + 1 > out->ep) + return fz_ioneedout; + + *out->wp++ = lzw->code; + + lzw->oldcode = lzw->code; + + eatbits(lzw, oldcodebits + MINBITS); + + continue; + } + + eatbits(lzw, lzw->codebits); + + /* if stream starts without a clear code, oldcode is undefined... */ + if (lzw->oldcode == -1) { + lzw->oldcode = lzw->code; + goto output; + } + + /* add new entry to the code table */ + lzw->table[lzw->nextcode].prev = lzw->oldcode; + lzw->table[lzw->nextcode].firstchar = lzw->table[lzw->oldcode].firstchar; + lzw->table[lzw->nextcode].length = lzw->table[lzw->oldcode].length + 1; + if (lzw->code < lzw->nextcode) + lzw->table[lzw->nextcode].value = lzw->table[lzw->code].firstchar; + else + lzw->table[lzw->nextcode].value = lzw->table[lzw->nextcode].firstchar; + + DPRINT("NEW[%d] prev=%d, f=%d, l=%d, v=%d\n", + lzw->nextcode, + lzw->table[lzw->nextcode].prev, + lzw->table[lzw->nextcode].firstchar, + lzw->table[lzw->nextcode].length, + lzw->table[lzw->nextcode].value); + + lzw->nextcode ++; + + if (lzw->nextcode >= (1 << lzw->codebits) - lzw->earlychange - 1) + { + lzw->codebits ++; + if (lzw->codebits > MAXBITS) + lzw->codebits = MAXBITS; /* FIXME */ + } + + lzw->oldcode = lzw->code; + +output: + /* code maps to a string, copy to output (in reverse...) */ + if (lzw->code > 255) + { + if (out->wp + lzw->table[lzw->code].length > out->ep) { + lzw->resume = 1; + return fz_ioneedout; + } + + len = lzw->table[lzw->code].length; + s = out->wp + len; + + DPRINT("OUT code=%d len=%d\n", lzw->code, len); + do { + DPRINT("-> %d\n", lzw->table[lzw->code].value); + *(--s) = lzw->table[lzw->code].value; + lzw->code = lzw->table[lzw->code].prev; + } while (lzw->code >= 0 && s > out->wp); + out->wp += len; + } + + /* ... or just a single character */ + else + { + if (out->wp + 1 > out->ep) { + lzw->resume = 1; + return fz_ioneedout; + } + + DPRINT("OUT code=%d\n-> %d\n", lzw->code, lzw->code); + + *out->wp++ = lzw->code; + } + } +} + |