add libflate
diff --git a/src/libflate/deflate.c b/src/libflate/deflate.c
new file mode 100644
index 0000000..3a55af3
--- /dev/null
+++ b/src/libflate/deflate.c
@@ -0,0 +1,1359 @@
+#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=%ld 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;
+ 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;
+ }
+ }
+}
