diff options
author | rsc <devnull@localhost> | 2003-11-23 18:19:18 +0000 |
---|---|---|
committer | rsc <devnull@localhost> | 2003-11-23 18:19:18 +0000 |
commit | b6afd33e2f23953f00c6fac6b5d45946a9113654 (patch) | |
tree | 300478ec8ac939d1b7aa0c1b987367a49a4e47ce /src/libflate/inflate.c | |
parent | 8a708fb239f4272ac7e4f16f437093c56b2cab39 (diff) | |
download | plan9port-b6afd33e2f23953f00c6fac6b5d45946a9113654.tar.gz plan9port-b6afd33e2f23953f00c6fac6b5d45946a9113654.tar.bz2 plan9port-b6afd33e2f23953f00c6fac6b5d45946a9113654.zip |
add libflate
Diffstat (limited to 'src/libflate/inflate.c')
-rw-r--r-- | src/libflate/inflate.c | 693 |
1 files changed, 693 insertions, 0 deletions
diff --git a/src/libflate/inflate.c b/src/libflate/inflate.c new file mode 100644 index 00000000..f979084c --- /dev/null +++ b/src/libflate/inflate.c @@ -0,0 +1,693 @@ +#include <u.h> +#include <libc.h> +#include <flate.h> + +enum { + HistorySize= 32*1024, + BufSize= 4*1024, + MaxHuffBits= 17, /* maximum bits in a encoded code */ + Nlitlen= 288, /* number of litlen codes */ + Noff= 32, /* number of offset codes */ + Nclen= 19, /* number of codelen codes */ + LenShift= 10, /* code = len<<LenShift|code */ + LitlenBits= 7, /* number of bits in litlen decode table */ + OffBits= 6, /* number of bits in offset decode table */ + ClenBits= 6, /* number of bits in code len decode table */ + MaxFlatBits= LitlenBits, + MaxLeaf= Nlitlen +}; + +typedef struct Input Input; +typedef struct History History; +typedef struct Huff Huff; + +struct Input +{ + int error; /* first error encountered, or FlateOk */ + void *wr; + int (*w)(void*, void*, int); + void *getr; + int (*get)(void*); + ulong sreg; + int nbits; +}; + +struct History +{ + uchar his[HistorySize]; + uchar *cp; /* current pointer in history */ + int full; /* his has been filled up at least once */ +}; + +struct Huff +{ + int maxbits; /* max bits for any code */ + int minbits; /* min bits to get before looking in flat */ + int flatmask; /* bits used in "flat" fast decoding table */ + ulong flat[1<<MaxFlatBits]; + ulong maxcode[MaxHuffBits]; + ulong last[MaxHuffBits]; + ulong decode[MaxLeaf]; +}; + +/* litlen code words 257-285 extra bits */ +static int litlenextra[Nlitlen-257] = +{ +/* 257 */ 0, 0, 0, +/* 260 */ 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, +/* 270 */ 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, +/* 280 */ 4, 5, 5, 5, 5, 0, 0, 0 +}; + +static int litlenbase[Nlitlen-257]; + +/* offset code word extra bits */ +static int offextra[Noff] = +{ + 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, + 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, + 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, + 0, 0, +}; +static int offbase[Noff]; + +/* order code lengths */ +static int clenorder[Nclen] = +{ + 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 +}; + +/* for static huffman tables */ +static Huff litlentab; +static Huff offtab; +static uchar revtab[256]; + +static int uncblock(Input *in, History*); +static int fixedblock(Input *in, History*); +static int dynamicblock(Input *in, History*); +static int sregfill(Input *in, int n); +static int sregunget(Input *in); +static int decode(Input*, History*, Huff*, Huff*); +static int hufftab(Huff*, char*, int, int); +static int hdecsym(Input *in, Huff *h, int b); + +int +inflateinit(void) +{ + char *len; + int i, j, base; + + /* byte reverse table */ + for(i=0; i<256; i++) + for(j=0; j<8; j++) + if(i & (1<<j)) + revtab[i] |= 0x80 >> j; + + for(i=257,base=3; i<Nlitlen; i++) { + litlenbase[i-257] = base; + base += 1<<litlenextra[i-257]; + } + /* strange table entry in spec... */ + litlenbase[285-257]--; + + for(i=0,base=1; i<Noff; i++) { + offbase[i] = base; + base += 1<<offextra[i]; + } + + len = malloc(MaxLeaf); + if(len == nil) + return FlateNoMem; + + /* static Litlen bit lengths */ + for(i=0; i<144; i++) + len[i] = 8; + for(i=144; i<256; i++) + len[i] = 9; + for(i=256; i<280; i++) + len[i] = 7; + for(i=280; i<Nlitlen; i++) + len[i] = 8; + + if(!hufftab(&litlentab, len, Nlitlen, MaxFlatBits)) + return FlateInternal; + + /* static Offset bit lengths */ + for(i=0; i<Noff; i++) + len[i] = 5; + + if(!hufftab(&offtab, len, Noff, MaxFlatBits)) + return FlateInternal; + free(len); + + return FlateOk; +} + +int +inflate(void *wr, int (*w)(void*, void*, int), void *getr, int (*get)(void*)) +{ + History *his; + Input in; + int final, type; + + his = malloc(sizeof(History)); + if(his == nil) + return FlateNoMem; + his->cp = his->his; + his->full = 0; + in.getr = getr; + in.get = get; + in.wr = wr; + in.w = w; + in.nbits = 0; + in.sreg = 0; + in.error = FlateOk; + + do { + if(!sregfill(&in, 3)) + goto bad; + final = in.sreg & 0x1; + type = (in.sreg>>1) & 0x3; + in.sreg >>= 3; + in.nbits -= 3; + switch(type) { + default: + in.error = FlateCorrupted; + goto bad; + case 0: + /* uncompressed */ + if(!uncblock(&in, his)) + goto bad; + break; + case 1: + /* fixed huffman */ + if(!fixedblock(&in, his)) + goto bad; + break; + case 2: + /* dynamic huffman */ + if(!dynamicblock(&in, his)) + goto bad; + break; + } + } while(!final); + + if(his->cp != his->his && (*w)(wr, his->his, his->cp - his->his) != his->cp - his->his) { + in.error = FlateOutputFail; + goto bad; + } + + if(!sregunget(&in)) + goto bad; + + free(his); + if(in.error != FlateOk) + return FlateInternal; + return FlateOk; + +bad: + free(his); + if(in.error == FlateOk) + return FlateInternal; + return in.error; +} + +static int +uncblock(Input *in, History *his) +{ + int len, nlen, c; + uchar *hs, *hp, *he; + + if(!sregunget(in)) + return 0; + len = (*in->get)(in->getr); + len |= (*in->get)(in->getr)<<8; + nlen = (*in->get)(in->getr); + nlen |= (*in->get)(in->getr)<<8; + if(len != (~nlen&0xffff)) { + in->error = FlateCorrupted; + return 0; + } + + hp = his->cp; + hs = his->his; + he = hs + HistorySize; + + while(len > 0) { + c = (*in->get)(in->getr); + if(c < 0) + return 0; + *hp++ = c; + if(hp == he) { + his->full = 1; + if((*in->w)(in->wr, hs, HistorySize) != HistorySize) { + in->error = FlateOutputFail; + return 0; + } + hp = hs; + } + len--; + } + + his->cp = hp; + + return 1; +} + +static int +fixedblock(Input *in, History *his) +{ + return decode(in, his, &litlentab, &offtab); +} + +static int +dynamicblock(Input *in, History *his) +{ + Huff *lentab, *offtab; + char *len; + int i, j, n, c, nlit, ndist, nclen, res, nb; + + if(!sregfill(in, 14)) + return 0; + nlit = (in->sreg&0x1f) + 257; + ndist = ((in->sreg>>5) & 0x1f) + 1; + nclen = ((in->sreg>>10) & 0xf) + 4; + in->sreg >>= 14; + in->nbits -= 14; + + if(nlit > Nlitlen || ndist > Noff || nlit < 257) { + in->error = FlateCorrupted; + return 0; + } + + /* huff table header */ + len = malloc(Nlitlen+Noff); + lentab = malloc(sizeof(Huff)); + offtab = malloc(sizeof(Huff)); + if(len == nil || lentab == nil || offtab == nil){ + in->error = FlateNoMem; + goto bad; + } + for(i=0; i < Nclen; i++) + len[i] = 0; + for(i=0; i<nclen; i++) { + if(!sregfill(in, 3)) + goto bad; + len[clenorder[i]] = in->sreg & 0x7; + in->sreg >>= 3; + in->nbits -= 3; + } + + if(!hufftab(lentab, len, Nclen, ClenBits)){ + in->error = FlateCorrupted; + goto bad; + } + + n = nlit+ndist; + for(i=0; i<n;) { + nb = lentab->minbits; + for(;;){ + if(in->nbits<nb && !sregfill(in, nb)) + goto bad; + c = lentab->flat[in->sreg & lentab->flatmask]; + nb = c & 0xff; + if(nb > in->nbits){ + if(nb != 0xff) + continue; + c = hdecsym(in, lentab, c); + if(c < 0) + goto bad; + }else{ + c >>= 8; + in->sreg >>= nb; + in->nbits -= nb; + } + break; + } + + if(c < 16) { + j = 1; + } else if(c == 16) { + if(in->nbits<2 && !sregfill(in, 2)) + goto bad; + j = (in->sreg&0x3)+3; + in->sreg >>= 2; + in->nbits -= 2; + if(i == 0) { + in->error = FlateCorrupted; + goto bad; + } + c = len[i-1]; + } else if(c == 17) { + if(in->nbits<3 && !sregfill(in, 3)) + goto bad; + j = (in->sreg&0x7)+3; + in->sreg >>= 3; + in->nbits -= 3; + c = 0; + } else if(c == 18) { + if(in->nbits<7 && !sregfill(in, 7)) + goto bad; + j = (in->sreg&0x7f)+11; + in->sreg >>= 7; + in->nbits -= 7; + c = 0; + } else { + in->error = FlateCorrupted; + goto bad; + } + + if(i+j > n) { + in->error = FlateCorrupted; + goto bad; + } + + while(j) { + len[i] = c; + i++; + j--; + } + } + + if(!hufftab(lentab, len, nlit, LitlenBits) + || !hufftab(offtab, &len[nlit], ndist, OffBits)){ + in->error = FlateCorrupted; + goto bad; + } + + res = decode(in, his, lentab, offtab); + + free(len); + free(lentab); + free(offtab); + + return res; + +bad: + free(len); + free(lentab); + free(offtab); + return 0; +} + +static int +decode(Input *in, History *his, Huff *litlentab, Huff *offtab) +{ + int len, off; + uchar *hs, *hp, *hq, *he; + int c; + int nb; + + hs = his->his; + he = hs + HistorySize; + hp = his->cp; + + for(;;) { + nb = litlentab->minbits; + for(;;){ + if(in->nbits<nb && !sregfill(in, nb)) + return 0; + c = litlentab->flat[in->sreg & litlentab->flatmask]; + nb = c & 0xff; + if(nb > in->nbits){ + if(nb != 0xff) + continue; + c = hdecsym(in, litlentab, c); + if(c < 0) + return 0; + }else{ + c >>= 8; + in->sreg >>= nb; + in->nbits -= nb; + } + break; + } + + if(c < 256) { + /* literal */ + *hp++ = c; + if(hp == he) { + his->full = 1; + if((*in->w)(in->wr, hs, HistorySize) != HistorySize) { + in->error = FlateOutputFail; + return 0; + } + hp = hs; + } + continue; + } + + if(c == 256) + break; + + if(c > 285) { + in->error = FlateCorrupted; + return 0; + } + + c -= 257; + nb = litlenextra[c]; + if(in->nbits < nb && !sregfill(in, nb)) + return 0; + len = litlenbase[c] + (in->sreg & ((1<<nb)-1)); + in->sreg >>= nb; + in->nbits -= nb; + + /* get offset */ + nb = offtab->minbits; + for(;;){ + if(in->nbits<nb && !sregfill(in, nb)) + return 0; + c = offtab->flat[in->sreg & offtab->flatmask]; + nb = c & 0xff; + if(nb > in->nbits){ + if(nb != 0xff) + continue; + c = hdecsym(in, offtab, c); + if(c < 0) + return 0; + }else{ + c >>= 8; + in->sreg >>= nb; + in->nbits -= nb; + } + break; + } + + if(c > 29) { + in->error = FlateCorrupted; + return 0; + } + + nb = offextra[c]; + if(in->nbits < nb && !sregfill(in, nb)) + return 0; + + off = offbase[c] + (in->sreg & ((1<<nb)-1)); + in->sreg >>= nb; + in->nbits -= nb; + + hq = hp - off; + if(hq < hs) { + if(!his->full) { + in->error = FlateCorrupted; + return 0; + } + hq += HistorySize; + } + + /* slow but correct */ + while(len) { + *hp = *hq; + hq++; + hp++; + if(hq >= he) + hq = hs; + if(hp == he) { + his->full = 1; + if((*in->w)(in->wr, hs, HistorySize) != HistorySize) { + in->error = FlateOutputFail; + return 0; + } + hp = hs; + } + len--; + } + + } + + his->cp = hp; + + return 1; +} + +static int +revcode(int c, int b) +{ + /* shift encode up so it starts on bit 15 then reverse */ + c <<= (16-b); + c = revtab[c>>8] | (revtab[c&0xff]<<8); + return c; +} + +/* + * construct the huffman decoding arrays and a fast lookup table. + * the fast lookup is a table indexed by the next flatbits bits, + * which returns the symbol matched and the number of bits consumed, + * or the minimum number of bits needed and 0xff if more than flatbits + * bits are needed. + * + * flatbits can be longer than the smallest huffman code, + * because shorter codes are assigned smaller lexical prefixes. + * this means assuming zeros for the next few bits will give a + * conservative answer, in the sense that it will either give the + * correct answer, or return the minimum number of bits which + * are needed for an answer. + */ +static int +hufftab(Huff *h, char *hb, int maxleaf, int flatbits) +{ + ulong bitcount[MaxHuffBits]; + ulong c, fc, ec, mincode, code, nc[MaxHuffBits]; + int i, b, minbits, maxbits; + + for(i = 0; i < MaxHuffBits; i++) + bitcount[i] = 0; + maxbits = -1; + minbits = MaxHuffBits + 1; + for(i=0; i < maxleaf; i++){ + b = hb[i]; + if(b){ + bitcount[b]++; + if(b < minbits) + minbits = b; + if(b > maxbits) + maxbits = b; + } + } + + h->maxbits = maxbits; + if(maxbits <= 0){ + h->maxbits = 0; + h->minbits = 0; + h->flatmask = 0; + return 1; + } + code = 0; + c = 0; + for(b = 0; b <= maxbits; b++){ + h->last[b] = c; + c += bitcount[b]; + mincode = code << 1; + nc[b] = mincode; + code = mincode + bitcount[b]; + if(code > (1 << b)) + return 0; + h->maxcode[b] = code - 1; + h->last[b] += code - 1; + } + + if(flatbits > maxbits) + flatbits = maxbits; + h->flatmask = (1 << flatbits) - 1; + if(minbits > flatbits) + minbits = flatbits; + h->minbits = minbits; + + b = 1 << flatbits; + for(i = 0; i < b; i++) + h->flat[i] = ~0; + + /* + * initialize the flat table to include the minimum possible + * bit length for each code prefix + */ + for(b = maxbits; b > flatbits; b--){ + code = h->maxcode[b]; + if(code == -1) + break; + mincode = code + 1 - bitcount[b]; + mincode >>= b - flatbits; + code >>= b - flatbits; + for(; mincode <= code; mincode++) + h->flat[revcode(mincode, flatbits)] = (b << 8) | 0xff; + } + + for(i = 0; i < maxleaf; i++){ + b = hb[i]; + if(b <= 0) + continue; + c = nc[b]++; + if(b <= flatbits){ + code = (i << 8) | b; + ec = (c + 1) << (flatbits - b); + if(ec > (1<<flatbits)) + return 0; /* this is actually an internal error */ + for(fc = c << (flatbits - b); fc < ec; fc++) + h->flat[revcode(fc, flatbits)] = code; + } + if(b > minbits){ + c = h->last[b] - c; + if(c >= maxleaf) + return 0; + h->decode[c] = i; + } + } + return 1; +} + +static int +hdecsym(Input *in, Huff *h, int nb) +{ + long c; + + if((nb & 0xff) == 0xff) + nb = nb >> 8; + else + nb = nb & 0xff; + for(; nb <= h->maxbits; nb++){ + if(in->nbits<nb && !sregfill(in, nb)) + return -1; + c = revtab[in->sreg&0xff]<<8; + c |= revtab[(in->sreg>>8)&0xff]; + c >>= (16-nb); + if(c <= h->maxcode[nb]){ + in->sreg >>= nb; + in->nbits -= nb; + return h->decode[h->last[nb] - c]; + } + } + in->error = FlateCorrupted; + return -1; +} + +static int +sregfill(Input *in, int n) +{ + int c; + + while(n > in->nbits) { + c = (*in->get)(in->getr); + if(c < 0){ + in->error = FlateInputFail; + return 0; + } + in->sreg |= c<<in->nbits; + in->nbits += 8; + } + return 1; +} + +static int +sregunget(Input *in) +{ + if(in->nbits >= 8) { + in->error = FlateInternal; + return 0; + } + + /* throw other bits on the floor */ + in->nbits = 0; + in->sreg = 0; + return 1; +} |