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