ref: c11957a7915d355d80ff7e6a21721ba05441ca29
dir: /libflate/deflate.c/
#include <u.h> #include <libc.h> #include <flate.h> typedef struct Chain Chain; typedef struct Chains Chains; typedef struct Dyncode Dyncode; typedef struct Huff Huff; typedef struct LZblock LZblock; typedef struct LZstate LZstate; enum { /* * deflate format paramaters */ DeflateUnc = 0, /* uncompressed block */ DeflateFix = 1, /* fixed huffman codes */ DeflateDyn = 2, /* dynamic huffman codes */ DeflateEob = 256, /* end of block code in lit/len book */ DeflateMaxBlock = 64*1024-1, /* maximum size of uncompressed block */ DeflateMaxExp = 10, /* maximum expansion for a block */ LenStart = 257, /* start of length codes in litlen */ Nlitlen = 288, /* number of litlen codes */ Noff = 30, /* number of offset codes */ Nclen = 19, /* number of codelen codes */ MaxOff = 32*1024, MinMatch = 3, /* shortest match possible */ MaxMatch = 258, /* longest match possible */ /* * huffman code paramaters */ MaxLeaf = Nlitlen, MaxHuffBits = 16, /* max bits in a huffman code */ ChainMem = 2 * (MaxHuffBits - 1) * MaxHuffBits, /* * coding of the lz parse */ LenFlag = 1 << 3, LenShift = 4, /* leaves enough space for MinMatchMaxOff */ MaxLitRun = LenFlag - 1, /* * internal lz paramaters */ DeflateOut = 4096, /* output buffer size */ BlockSize = 8192, /* attempted input read quanta */ DeflateBlock = DeflateMaxBlock & ~(BlockSize - 1), MinMatchMaxOff = 4096, /* max profitable offset for small match; * assumes 8 bits for len, 5+10 for offset * DONT CHANGE WITHOUT CHANGING LZPARSE CONSTANTS */ HistSlop = 512, /* must be at lead MaxMatch */ HistBlock = 64*1024, HistSize = HistBlock + HistSlop, HashLog = 13, HashSize = 1<<HashLog, MaxOffCode = 256, /* biggest offset looked up in direct table */ EstLitBits = 8, EstLenBits = 4, EstOffBits = 5, }; /* * knuth vol. 3 multiplicative hashing * each byte x chosen according to rules * 1/4 < x < 3/10, 1/3 x < < 3/7, 4/7 < x < 2/3, 7/10 < x < 3/4 * with reasonable spread between the bytes & their complements * * the 3 byte value appears to be as almost good as the 4 byte value, * and might be faster on some machines */ /* #define hashit(c) (((ulong)(c) * 0x6b43a9) >> (24 - HashLog)) */ #define hashit(c) ((((ulong)(c) & 0xffffff) * 0x6b43a9b5) >> (32 - HashLog)) /* * lempel-ziv style compression state */ struct LZstate { uchar hist[HistSize]; ulong pos; /* current location in history buffer */ ulong avail; /* data available after pos */ int eof; ushort hash[HashSize]; /* hash chains */ ushort nexts[MaxOff]; int now; /* pos in hash chains */ int dot; /* dawn of time in history */ int prevlen; /* lazy matching state */ int prevoff; int maxcheck; /* compressor tuning */ uchar obuf[DeflateOut]; uchar *out; /* current position in the output buffer */ uchar *eout; ulong bits; /* bit shift register */ int nbits; int rbad; /* got an error reading the buffer */ int wbad; /* got an error writing the buffer */ int (*w)(void*, void*, int); void *wr; ulong totr; /* total input size */ ulong totw; /* total output size */ int debug; }; struct LZblock { ushort parse[DeflateMaxBlock / 2 + 1]; int lastv; /* value being constucted for parse */ ulong litlencount[Nlitlen]; ulong offcount[Noff]; ushort *eparse; /* limit for parse table */ int bytes; /* consumed from the input */ int excost; /* cost of encoding extra len & off bits */ }; /* * huffman code table */ struct Huff { short bits; /* length of the code */ ushort encode; /* the code */ }; /* * encoding of dynamic huffman trees */ struct Dyncode { int nlit; int noff; int nclen; int ncode; Huff codetab[Nclen]; uchar codes[Nlitlen+Noff]; uchar codeaux[Nlitlen+Noff]; }; static int deflateb(LZstate *lz, LZblock *lzb, void *rr, int (*r)(void*, void*, int)); static int lzcomp(LZstate*, LZblock*, uchar*, ushort*, int finish); static void wrblock(LZstate*, int, ushort*, ushort*, Huff*, Huff*); static int bitcost(Huff*, ulong*, int); static int huffcodes(Dyncode*, Huff*, Huff*); static void wrdyncode(LZstate*, Dyncode*); static void lzput(LZstate*, ulong bits, int nbits); static void lzflushbits(LZstate*); static void lzflush(LZstate *lz); static void lzwrite(LZstate *lz, void *buf, int n); static int hufftabinit(Huff*, int, ulong*, int); static int mkgzprecode(Huff*, ulong *, int, int); static int mkprecode(Huff*, ulong *, int, int, ulong*); static void nextchain(Chains*, int); static void leafsort(ulong*, ushort*, int, int); /* conversion from len to code word */ static int lencode[MaxMatch]; /* * conversion from off to code word * off <= MaxOffCode ? offcode[off] : bigoffcode[off >> 7] */ static int offcode[MaxOffCode]; static int bigoffcode[256]; /* litlen code words LenStart-285 extra bits */ static int litlenbase[Nlitlen-LenStart]; static int litlenextra[Nlitlen-LenStart] = { /* 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 }; /* offset code word extra bits */ static int offbase[Noff]; static int offextra[] = { 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, }; /* 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 }; /* static huffman tables */ static Huff litlentab[Nlitlen]; static Huff offtab[Noff]; static Huff hofftab[Noff]; /* bit reversal for brain dead endian swap in huffman codes */ static uchar revtab[256]; static ulong nlits; static ulong nmatches; int deflateinit(void) { ulong bitcount[MaxHuffBits]; int i, j, ci, n; /* byte reverse table */ for(i=0; i<256; i++) for(j=0; j<8; j++) if(i & (1<<j)) revtab[i] |= 0x80 >> j; /* static Litlen bit lengths */ for(i=0; i<144; i++) litlentab[i].bits = 8; for(i=144; i<256; i++) litlentab[i].bits = 9; for(i=256; i<280; i++) litlentab[i].bits = 7; for(i=280; i<Nlitlen; i++) litlentab[i].bits = 8; memset(bitcount, 0, sizeof(bitcount)); bitcount[8] += 144 - 0; bitcount[9] += 256 - 144; bitcount[7] += 280 - 256; bitcount[8] += Nlitlen - 280; if(!hufftabinit(litlentab, Nlitlen, bitcount, 9)) return FlateInternal; /* static offset bit lengths */ for(i = 0; i < Noff; i++) offtab[i].bits = 5; memset(bitcount, 0, sizeof(bitcount)); bitcount[5] = Noff; if(!hufftabinit(offtab, Noff, bitcount, 5)) return FlateInternal; bitcount[0] = 0; bitcount[1] = 0; if(!mkgzprecode(hofftab, bitcount, 2, MaxHuffBits)) return FlateInternal; /* conversion tables for lens & offs to codes */ ci = 0; for(i = LenStart; i < 286; i++){ n = ci + (1 << litlenextra[i - LenStart]); litlenbase[i - LenStart] = ci; for(; ci < n; ci++) lencode[ci] = i; } /* patch up special case for len MaxMatch */ lencode[MaxMatch-MinMatch] = 285; litlenbase[285-LenStart] = MaxMatch-MinMatch; ci = 0; for(i = 0; i < 16; i++){ n = ci + (1 << offextra[i]); offbase[i] = ci; for(; ci < n; ci++) offcode[ci] = i; } ci = ci >> 7; for(; i < 30; i++){ n = ci + (1 << (offextra[i] - 7)); offbase[i] = ci << 7; for(; ci < n; ci++) bigoffcode[ci] = i; } return FlateOk; } static void deflatereset(LZstate *lz, int level, int debug) { memset(lz->nexts, 0, sizeof lz->nexts); memset(lz->hash, 0, sizeof lz->hash); lz->totr = 0; lz->totw = 0; lz->pos = 0; lz->avail = 0; lz->out = lz->obuf; lz->eout = &lz->obuf[DeflateOut]; lz->prevlen = MinMatch - 1; lz->prevoff = 0; lz->now = MaxOff + 1; lz->dot = lz->now; lz->bits = 0; lz->nbits = 0; lz->maxcheck = (1 << level); lz->maxcheck -= lz->maxcheck >> 2; if(lz->maxcheck < 2) lz->maxcheck = 2; else if(lz->maxcheck > 1024) lz->maxcheck = 1024; lz->debug = debug; } int deflate(void *wr, int (*w)(void*, void*, int), void *rr, int (*r)(void*, void*, int), int level, int debug) { LZstate *lz; LZblock *lzb; int ok; lz = malloc(sizeof *lz + sizeof *lzb); if(lz == nil) return FlateNoMem; lzb = (LZblock*)&lz[1]; deflatereset(lz, level, debug); lz->w = w; lz->wr = wr; lz->wbad = 0; lz->rbad = 0; lz->eof = 0; ok = FlateOk; while(!lz->eof || lz->avail){ ok = deflateb(lz, lzb, rr, r); if(ok != FlateOk) break; } if(ok == FlateOk && lz->rbad) ok = FlateInputFail; if(ok == FlateOk && lz->wbad) ok = FlateOutputFail; free(lz); return ok; } static int deflateb(LZstate *lz, LZblock *lzb, void *rr, int (*r)(void*, void*, int)) { Dyncode dyncode, hdyncode; Huff dlitlentab[Nlitlen], dofftab[Noff], hlitlentab[Nlitlen]; ulong litcount[Nlitlen]; long nunc, ndyn, nfix, nhuff; uchar *slop, *hslop; ulong ep; int i, n, m, mm, nslop; memset(lzb->litlencount, 0, sizeof lzb->litlencount); memset(lzb->offcount, 0, sizeof lzb->offcount); lzb->litlencount[DeflateEob]++; lzb->bytes = 0; lzb->eparse = lzb->parse; lzb->lastv = 0; lzb->excost = 0; slop = &lz->hist[lz->pos]; n = lz->avail; while(n < DeflateBlock && (!lz->eof || lz->avail)){ /* * fill the buffer as much as possible, * while leaving room for MaxOff history behind lz->pos, * and not reading more than we can handle. * * make sure we read at least HistSlop bytes. */ if(!lz->eof){ ep = lz->pos + lz->avail; if(ep >= HistBlock) ep -= HistBlock; m = HistBlock - MaxOff - lz->avail; if(m > HistBlock - n) m = HistBlock - n; if(m > (HistBlock + HistSlop) - ep) m = (HistBlock + HistSlop) - ep; if(m & ~(BlockSize - 1)) m &= ~(BlockSize - 1); /* * be nice to the caller: stop reads that are too small. * can only get here when we've already filled the buffer some */ if(m < HistSlop){ if(!m || !lzb->bytes) return FlateInternal; break; } mm = (*r)(rr, &lz->hist[ep], m); if(mm > 0){ /* * wrap data to end if we're read it from the beginning * this way, we don't have to wrap searches. * * wrap reads past the end to the beginning. * this way, we can guarantee minimum size reads. */ if(ep < HistSlop) memmove(&lz->hist[ep + HistBlock], &lz->hist[ep], HistSlop - ep); else if(ep + mm > HistBlock) memmove(&lz->hist[0], &lz->hist[HistBlock], ep + mm - HistBlock); lz->totr += mm; n += mm; lz->avail += mm; }else{ if(mm < 0) lz->rbad = 1; lz->eof = 1; } } ep = lz->pos + lz->avail; if(ep > HistSize) ep = HistSize; if(lzb->bytes + ep - lz->pos > DeflateMaxBlock) ep = lz->pos + DeflateMaxBlock - lzb->bytes; m = lzcomp(lz, lzb, &lz->hist[ep], lzb->eparse, lz->eof); lzb->bytes += m; lz->pos = (lz->pos + m) & (HistBlock - 1); lz->avail -= m; } if(lzb->lastv) *lzb->eparse++ = lzb->lastv; if(lzb->eparse > lzb->parse + nelem(lzb->parse)) return FlateInternal; nunc = lzb->bytes; if(!mkgzprecode(dlitlentab, lzb->litlencount, Nlitlen, MaxHuffBits) || !mkgzprecode(dofftab, lzb->offcount, Noff, MaxHuffBits)) return FlateInternal; ndyn = huffcodes(&dyncode, dlitlentab, dofftab); if(ndyn < 0) return FlateInternal; ndyn += bitcost(dlitlentab, lzb->litlencount, Nlitlen) + bitcost(dofftab, lzb->offcount, Noff) + lzb->excost; memset(litcount, 0, sizeof litcount); nslop = nunc; if(nslop > &lz->hist[HistSize] - slop) nslop = &lz->hist[HistSize] - slop; for(i = 0; i < nslop; i++) litcount[slop[i]]++; hslop = &lz->hist[HistSlop - nslop]; for(; i < nunc; i++) litcount[hslop[i]]++; litcount[DeflateEob]++; if(!mkgzprecode(hlitlentab, litcount, Nlitlen, MaxHuffBits)) return FlateInternal; nhuff = huffcodes(&hdyncode, hlitlentab, hofftab); if(nhuff < 0) return FlateInternal; nhuff += bitcost(hlitlentab, litcount, Nlitlen); nfix = bitcost(litlentab, lzb->litlencount, Nlitlen) + bitcost(offtab, lzb->offcount, Noff) + lzb->excost; lzput(lz, lz->eof && !lz->avail, 1); if(lz->debug){ fprint(2, "block: bytes=%lud entries=%zd extra bits=%d\n\tuncompressed=%lud fixed=%lud dynamic=%lud huffman=%lud\n", nunc, lzb->eparse - lzb->parse, lzb->excost, (nunc + 4) * 8, nfix, ndyn, nhuff); fprint(2, "\tnlit=%lud matches=%lud eof=%d\n", nlits, nmatches, lz->eof && !lz->avail); } if((nunc + 4) * 8 < ndyn && (nunc + 4) * 8 < nfix && (nunc + 4) * 8 < nhuff){ lzput(lz, DeflateUnc, 2); lzflushbits(lz); lzput(lz, nunc & 0xff, 8); lzput(lz, (nunc >> 8) & 0xff, 8); lzput(lz, ~nunc & 0xff, 8); lzput(lz, (~nunc >> 8) & 0xff, 8); lzflush(lz); lzwrite(lz, slop, nslop); lzwrite(lz, &lz->hist[HistSlop], nunc - nslop); }else if(ndyn < nfix && ndyn < nhuff){ lzput(lz, DeflateDyn, 2); wrdyncode(lz, &dyncode); wrblock(lz, slop - lz->hist, lzb->parse, lzb->eparse, dlitlentab, dofftab); lzput(lz, dlitlentab[DeflateEob].encode, dlitlentab[DeflateEob].bits); }else if(nhuff < nfix){ lzput(lz, DeflateDyn, 2); wrdyncode(lz, &hdyncode); m = 0; for(i = nunc; i > MaxLitRun; i -= MaxLitRun) lzb->parse[m++] = MaxLitRun; lzb->parse[m++] = i; wrblock(lz, slop - lz->hist, lzb->parse, lzb->parse + m, hlitlentab, hofftab); lzput(lz, hlitlentab[DeflateEob].encode, hlitlentab[DeflateEob].bits); }else{ lzput(lz, DeflateFix, 2); wrblock(lz, slop - lz->hist, lzb->parse, lzb->eparse, litlentab, offtab); lzput(lz, litlentab[DeflateEob].encode, litlentab[DeflateEob].bits); } if(lz->eof && !lz->avail){ lzflushbits(lz); lzflush(lz); } return FlateOk; } static void lzwrite(LZstate *lz, void *buf, int n) { int nw; if(n && lz->w){ nw = (*lz->w)(lz->wr, buf, n); if(nw != n){ lz->w = nil; lz->wbad = 1; }else lz->totw += n; } } static void lzflush(LZstate *lz) { lzwrite(lz, lz->obuf, lz->out - lz->obuf); lz->out = lz->obuf; } static void lzput(LZstate *lz, ulong bits, int nbits) { bits = (bits << lz->nbits) | lz->bits; for(nbits += lz->nbits; nbits >= 8; nbits -= 8){ *lz->out++ = bits; if(lz->out == lz->eout) lzflush(lz); bits >>= 8; } lz->bits = bits; lz->nbits = nbits; } static void lzflushbits(LZstate *lz) { if(lz->nbits) lzput(lz, 0, 8 - (lz->nbits & 7)); } /* * write out a block of n samples, * given lz encoding and counts for huffman tables */ static void wrblock(LZstate *out, int litoff, ushort *soff, ushort *eoff, Huff *litlentab, Huff *offtab) { ushort *off; int i, run, offset, lit, len, c; if(out->debug > 2){ for(off = soff; off < eoff; ){ offset = *off++; run = offset & MaxLitRun; if(run){ for(i = 0; i < run; i++){ lit = out->hist[litoff & (HistBlock - 1)]; litoff++; fprint(2, "\tlit %.2ux %c\n", lit, lit); } if(!(offset & LenFlag)) continue; len = offset >> LenShift; offset = *off++; }else if(offset & LenFlag){ len = offset >> LenShift; offset = *off++; }else{ len = 0; offset >>= LenShift; } litoff += len + MinMatch; fprint(2, "\t<%d, %d>\n", offset + 1, len + MinMatch); } } for(off = soff; off < eoff; ){ offset = *off++; run = offset & MaxLitRun; if(run){ for(i = 0; i < run; i++){ lit = out->hist[litoff & (HistBlock - 1)]; litoff++; lzput(out, litlentab[lit].encode, litlentab[lit].bits); } if(!(offset & LenFlag)) continue; len = offset >> LenShift; offset = *off++; }else if(offset & LenFlag){ len = offset >> LenShift; offset = *off++; }else{ len = 0; offset >>= LenShift; } litoff += len + MinMatch; c = lencode[len]; lzput(out, litlentab[c].encode, litlentab[c].bits); c -= LenStart; if(litlenextra[c]) lzput(out, len - litlenbase[c], litlenextra[c]); if(offset < MaxOffCode) c = offcode[offset]; else c = bigoffcode[offset >> 7]; lzput(out, offtab[c].encode, offtab[c].bits); if(offextra[c]) lzput(out, offset - offbase[c], offextra[c]); } } /* * look for the longest, closest string which matches * the next prefix. the clever part here is looking for * a string 1 longer than the previous best match. * * follows the recommendation of limiting number of chains * which are checked. this appears to be the best heuristic. */ static int lzmatch(int now, int then, uchar *p, uchar *es, ushort *nexts, uchar *hist, int runlen, int check, int *m) { uchar *s, *t; int ml, off, last; ml = check; if(runlen >= 8) check >>= 2; *m = 0; if(p + runlen >= es) return runlen; last = 0; for(; check-- > 0; then = nexts[then & (MaxOff-1)]){ off = (ushort)(now - then); if(off <= last || off > MaxOff) break; s = p + runlen; t = hist + (((p - hist) - off) & (HistBlock-1)); t += runlen; for(; s >= p; s--){ if(*s != *t) goto matchloop; t--; } /* * we have a new best match. * extend it to it's maximum length */ t += runlen + 2; s += runlen + 2; for(; s < es; s++){ if(*s != *t) break; t++; } runlen = s - p; *m = off - 1; if(s == es || runlen > ml) break; matchloop:; last = off; } return runlen; } static int lzcomp(LZstate *lz, LZblock *lzb, uchar *ep, ushort *parse, int finish) { ulong cont, excost, *litlencount, *offcount; uchar *p, *q, *s, *es; ushort *nexts, *hash; int v, i, h, runlen, n, now, then, m, prevlen, prevoff, maxdefer; litlencount = lzb->litlencount; offcount = lzb->offcount; nexts = lz->nexts; hash = lz->hash; now = lz->now; p = &lz->hist[lz->pos]; if(lz->prevlen != MinMatch - 1) p++; /* * hash in the links for any hanging link positions, * and calculate the hash for the current position. */ n = MinMatch; if(n > ep - p) n = ep - p; cont = 0; for(i = 0; i < n - 1; i++){ m = now - ((MinMatch-1) - i); if(m < lz->dot) continue; s = lz->hist + (((p - lz->hist) - (now - m)) & (HistBlock-1)); cont = (s[0] << 16) | (s[1] << 8) | s[2]; h = hashit(cont); prevoff = 0; for(then = hash[h]; ; then = nexts[then & (MaxOff-1)]){ v = (ushort)(now - then); if(v <= prevoff || v >= (MinMatch-1) - i) break; prevoff = v; } if(then == (ushort)m) continue; nexts[m & (MaxOff-1)] = hash[h]; hash[h] = m; } for(i = 0; i < n; i++) cont = (cont << 8) | p[i]; /* * now must point to the index in the nexts array * corresponding to p's position in the history */ prevlen = lz->prevlen; prevoff = lz->prevoff; maxdefer = lz->maxcheck >> 2; excost = 0; v = lzb->lastv; for(;;){ es = p + MaxMatch; if(es > ep){ if(!finish || p >= ep) break; es = ep; } h = hashit(cont); runlen = lzmatch(now, hash[h], p, es, nexts, lz->hist, prevlen, lz->maxcheck, &m); /* * back out of small matches too far in the past */ if(runlen == MinMatch && m >= MinMatchMaxOff){ runlen = MinMatch - 1; m = 0; } /* * record the encoding and increment counts for huffman trees * if we get a match, defer selecting it until we check for * a longer match at the next position. */ if(prevlen >= runlen && prevlen != MinMatch - 1){ /* * old match at least as good; use that one */ n = prevlen - MinMatch; if(v || n){ *parse++ = v | LenFlag | (n << LenShift); *parse++ = prevoff; }else *parse++ = prevoff << LenShift; v = 0; n = lencode[n]; litlencount[n]++; excost += litlenextra[n - LenStart]; if(prevoff < MaxOffCode) n = offcode[prevoff]; else n = bigoffcode[prevoff >> 7]; offcount[n]++; excost += offextra[n]; runlen = prevlen - 1; prevlen = MinMatch - 1; nmatches++; }else if(runlen == MinMatch - 1){ /* * no match; just put out the literal */ if(++v == MaxLitRun){ *parse++ = v; v = 0; } litlencount[*p]++; nlits++; runlen = 1; }else{ if(prevlen != MinMatch - 1){ /* * longer match now. output previous literal, * update current match, and try again */ if(++v == MaxLitRun){ *parse++ = v; v = 0; } litlencount[p[-1]]++; nlits++; } prevoff = m; if(runlen < maxdefer){ prevlen = runlen; runlen = 1; }else{ n = runlen - MinMatch; if(v || n){ *parse++ = v | LenFlag | (n << LenShift); *parse++ = prevoff; }else *parse++ = prevoff << LenShift; v = 0; n = lencode[n]; litlencount[n]++; excost += litlenextra[n - LenStart]; if(prevoff < MaxOffCode) n = offcode[prevoff]; else n = bigoffcode[prevoff >> 7]; offcount[n]++; excost += offextra[n]; prevlen = MinMatch - 1; nmatches++; } } /* * update the hash for the newly matched data * this is constructed so the link for the old * match in this position must be at the end of a chain, * and will expire when this match is added, ie it will * never be examined by the match loop. * add to the hash chain only if we have the real hash data. */ for(q = p + runlen; p != q; p++){ if(p + MinMatch <= ep){ h = hashit(cont); nexts[now & (MaxOff-1)] = hash[h]; hash[h] = now; if(p + MinMatch < ep) cont = (cont << 8) | p[MinMatch]; } now++; } } /* * we can just store away the lazy state and * pick it up next time. the last block will have finish set * so we won't have any pending matches * however, we need to correct for how much we've encoded */ if(prevlen != MinMatch - 1) p--; lzb->excost += excost; lzb->eparse = parse; lzb->lastv = v; lz->now = now; lz->prevlen = prevlen; lz->prevoff = prevoff; return p - &lz->hist[lz->pos]; } /* * make up the dynamic code tables, and return the number of bits * needed to transmit them. */ static int huffcodes(Dyncode *dc, Huff *littab, Huff *offtab) { Huff *codetab; uchar *codes, *codeaux; ulong codecount[Nclen], excost; int i, n, m, v, c, nlit, noff, ncode, nclen; codetab = dc->codetab; codes = dc->codes; codeaux = dc->codeaux; /* * trim the sizes of the tables */ for(nlit = Nlitlen; nlit > 257 && littab[nlit-1].bits == 0; nlit--) ; for(noff = Noff; noff > 1 && offtab[noff-1].bits == 0; noff--) ; /* * make the code-length code */ for(i = 0; i < nlit; i++) codes[i] = littab[i].bits; for(i = 0; i < noff; i++) codes[i + nlit] = offtab[i].bits; /* * run-length compress the code-length code */ excost = 0; c = 0; ncode = nlit+noff; for(i = 0; i < ncode; ){ n = i + 1; v = codes[i]; while(n < ncode && v == codes[n]) n++; n -= i; i += n; if(v == 0){ while(n >= 11){ m = n; if(m > 138) m = 138; codes[c] = 18; codeaux[c++] = m - 11; n -= m; excost += 7; } if(n >= 3){ codes[c] = 17; codeaux[c++] = n - 3; n = 0; excost += 3; } } while(n--){ codes[c++] = v; while(n >= 3){ m = n; if(m > 6) m = 6; codes[c] = 16; codeaux[c++] = m - 3; n -= m; excost += 3; } } } memset(codecount, 0, sizeof codecount); for(i = 0; i < c; i++) codecount[codes[i]]++; if(!mkgzprecode(codetab, codecount, Nclen, 8)) return -1; for(nclen = Nclen; nclen > 4 && codetab[clenorder[nclen-1]].bits == 0; nclen--) ; dc->nlit = nlit; dc->noff = noff; dc->nclen = nclen; dc->ncode = c; return 5 + 5 + 4 + nclen * 3 + bitcost(codetab, codecount, Nclen) + excost; } static void wrdyncode(LZstate *out, Dyncode *dc) { Huff *codetab; uchar *codes, *codeaux; int i, v, c; /* * write out header, then code length code lengths, * and code lengths */ lzput(out, dc->nlit-257, 5); lzput(out, dc->noff-1, 5); lzput(out, dc->nclen-4, 4); codetab = dc->codetab; for(i = 0; i < dc->nclen; i++) lzput(out, codetab[clenorder[i]].bits, 3); codes = dc->codes; codeaux = dc->codeaux; c = dc->ncode; for(i = 0; i < c; i++){ v = codes[i]; lzput(out, codetab[v].encode, codetab[v].bits); if(v >= 16){ if(v == 16) lzput(out, codeaux[i], 2); else if(v == 17) lzput(out, codeaux[i], 3); else /* v == 18 */ lzput(out, codeaux[i], 7); } } } static int bitcost(Huff *tab, ulong *count, int n) { ulong tot; int i; tot = 0; for(i = 0; i < n; i++) tot += count[i] * tab[i].bits; return tot; } static int mkgzprecode(Huff *tab, ulong *count, int n, int maxbits) { ulong bitcount[MaxHuffBits]; int i, nbits; nbits = mkprecode(tab, count, n, maxbits, bitcount); for(i = 0; i < n; i++){ if(tab[i].bits == -1) tab[i].bits = 0; else if(tab[i].bits == 0){ if(nbits != 0 || bitcount[0] != 1) return 0; bitcount[1] = 1; bitcount[0] = 0; nbits = 1; tab[i].bits = 1; } } if(bitcount[0] != 0) return 0; if(nbits == 0){ bitcount[1] = 1; nbits = 1; tab[0].bits = 1; } return hufftabinit(tab, n, bitcount, nbits); } static int hufftabinit(Huff *tab, int n, ulong *bitcount, int nbits) { ulong code, nc[MaxHuffBits]; int i, bits; code = 0; for(bits = 1; bits <= nbits; bits++){ code = (code + bitcount[bits-1]) << 1; nc[bits] = code; } for(i = 0; i < n; i++){ bits = tab[i].bits; if(bits){ code = nc[bits]++ << (16 - bits); if(code & ~0xffff) return 0; tab[i].encode = revtab[code >> 8] | (revtab[code & 0xff] << 8); } } return 1; } /* * this should be in a library */ struct Chain { ulong count; /* occurances of everything in the chain */ ushort leaf; /* leaves to the left of chain, or leaf value */ char col; /* ref count for collecting unused chains */ char gen; /* need to generate chains for next lower level */ Chain *up; /* Chain up in the lists */ }; struct Chains { Chain *lists[(MaxHuffBits - 1) * 2]; ulong leafcount[MaxLeaf]; /* sorted list of leaf counts */ ushort leafmap[MaxLeaf]; /* map to actual leaf number */ int nleaf; /* number of leaves */ Chain chains[ChainMem]; Chain *echains; Chain *free; char col; int nlists; }; /* * fast, low space overhead algorithm for max depth huffman type codes * * J. Katajainen, A. Moffat and A. Turpin, "A fast and space-economical * algorithm for length-limited coding," Proc. Intl. Symp. on Algorithms * and Computation, Cairns, Australia, Dec. 1995, Lecture Notes in Computer * Science, Vol 1004, J. Staples, P. Eades, N. Katoh, and A. Moffat, eds., * pp 12-21, Springer Verlag, New York, 1995. */ static int mkprecode(Huff *tab, ulong *count, int n, int maxbits, ulong *bitcount) { Chains cs; Chain *c; int i, m, em, bits; /* * set up the sorted list of leaves */ m = 0; for(i = 0; i < n; i++){ tab[i].bits = -1; tab[i].encode = 0; if(count[i] != 0){ cs.leafcount[m] = count[i]; cs.leafmap[m] = i; m++; } } if(m < 2){ if(m != 0){ tab[cs.leafmap[0]].bits = 0; bitcount[0] = 1; }else bitcount[0] = 0; return 0; } cs.nleaf = m; leafsort(cs.leafcount, cs.leafmap, 0, m); for(i = 0; i < m; i++) cs.leafcount[i] = count[cs.leafmap[i]]; /* * set up free list */ cs.free = &cs.chains[2]; cs.echains = &cs.chains[ChainMem]; cs.col = 1; /* * initialize chains for each list */ c = &cs.chains[0]; c->count = cs.leafcount[0]; c->leaf = 1; c->col = cs.col; c->up = nil; c->gen = 0; cs.chains[1] = cs.chains[0]; cs.chains[1].leaf = 2; cs.chains[1].count = cs.leafcount[1]; for(i = 0; i < maxbits-1; i++){ cs.lists[i * 2] = &cs.chains[0]; cs.lists[i * 2 + 1] = &cs.chains[1]; } cs.nlists = 2 * (maxbits - 1); m = 2 * m - 2; for(i = 2; i < m; i++) nextchain(&cs, cs.nlists - 2); bits = 0; bitcount[0] = cs.nleaf; for(c = cs.lists[cs.nlists - 1]; c != nil; c = c->up){ m = c->leaf; bitcount[bits++] -= m; bitcount[bits] = m; } m = 0; for(i = bits; i >= 0; i--) for(em = m + bitcount[i]; m < em; m++) tab[cs.leafmap[m]].bits = i; return bits; } /* * calculate the next chain on the list * we can always toss out the old chain */ static void nextchain(Chains *cs, int list) { Chain *c, *oc; int i, nleaf, sumc; oc = cs->lists[list + 1]; cs->lists[list] = oc; if(oc == nil) return; /* * make sure we have all chains needed to make sumc * note it is possible to generate only one of these, * use twice that value for sumc, and then generate * the second if that preliminary sumc would be chosen. * however, this appears to be slower on current tests */ if(oc->gen){ nextchain(cs, list - 2); nextchain(cs, list - 2); oc->gen = 0; } /* * pick up the chain we're going to add; * collect unused chains no free ones are left */ for(c = cs->free; ; c++){ if(c >= cs->echains){ cs->col++; for(i = 0; i < cs->nlists; i++) for(c = cs->lists[i]; c != nil; c = c->up) c->col = cs->col; c = cs->chains; } if(c->col != cs->col) break; } /* * pick the cheapest of * 1) the next package from the previous list * 2) the next leaf */ nleaf = oc->leaf; sumc = 0; if(list > 0 && cs->lists[list-1] != nil) sumc = cs->lists[list-2]->count + cs->lists[list-1]->count; if(sumc != 0 && (nleaf >= cs->nleaf || cs->leafcount[nleaf] > sumc)){ c->count = sumc; c->leaf = oc->leaf; c->up = cs->lists[list-1]; c->gen = 1; }else if(nleaf >= cs->nleaf){ cs->lists[list + 1] = nil; return; }else{ c->leaf = nleaf + 1; c->count = cs->leafcount[nleaf]; c->up = oc->up; c->gen = 0; } cs->free = c + 1; cs->lists[list + 1] = c; c->col = cs->col; } static int pivot(ulong *c, int a, int n) { int j, pi, pj, pk; j = n/6; pi = a + j; /* 1/6 */ j += j; pj = pi + j; /* 1/2 */ pk = pj + j; /* 5/6 */ if(c[pi] < c[pj]){ if(c[pi] < c[pk]){ if(c[pj] < c[pk]) return pj; return pk; } return pi; } if(c[pj] < c[pk]){ if(c[pi] < c[pk]) return pi; return pk; } return pj; } static void leafsort(ulong *leafcount, ushort *leafmap, int a, int n) { ulong t; int j, pi, pj, pn; while(n > 1){ if(n > 10){ pi = pivot(leafcount, a, n); }else pi = a + (n>>1); t = leafcount[pi]; leafcount[pi] = leafcount[a]; leafcount[a] = t; t = leafmap[pi]; leafmap[pi] = leafmap[a]; leafmap[a] = t; pi = a; pn = a + n; pj = pn; for(;;){ do pi++; while(pi < pn && (leafcount[pi] < leafcount[a] || leafcount[pi] == leafcount[a] && leafmap[pi] > leafmap[a])); do pj--; while(pj > a && (leafcount[pj] > leafcount[a] || leafcount[pj] == leafcount[a] && leafmap[pj] < leafmap[a])); if(pj < pi) break; t = leafcount[pi]; leafcount[pi] = leafcount[pj]; leafcount[pj] = t; t = leafmap[pi]; leafmap[pi] = leafmap[pj]; leafmap[pj] = t; } t = leafcount[a]; leafcount[a] = leafcount[pj]; leafcount[pj] = t; t = leafmap[a]; leafmap[a] = leafmap[pj]; leafmap[pj] = t; j = pj - a; n = n-j-1; if(j >= n){ leafsort(leafcount, leafmap, a, j); a += j+1; }else{ leafsort(leafcount, leafmap, a + (j+1), n); n = j; } } }