ref: 41e27b2d10c6a60c49931332e8677438736a1e36
dir: /os/boot/libflate/inflate.c/
#include "lib9.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; }