5 typedef struct Chain Chain;
6 typedef struct Chains Chains;
7 typedef struct Dyncode Dyncode;
8 typedef struct Huff Huff;
9 typedef struct LZblock LZblock;
10 typedef struct LZstate LZstate;
15 * deflate format paramaters
17 DeflateUnc = 0, /* uncompressed block */
18 DeflateFix = 1, /* fixed huffman codes */
19 DeflateDyn = 2, /* dynamic huffman codes */
21 DeflateEob = 256, /* end of block code in lit/len book */
22 DeflateMaxBlock = 64*1024-1, /* maximum size of uncompressed block */
24 DeflateMaxExp = 10, /* maximum expansion for a block */
26 LenStart = 257, /* start of length codes in litlen */
27 Nlitlen = 288, /* number of litlen codes */
28 Noff = 30, /* number of offset codes */
29 Nclen = 19, /* number of codelen codes */
32 MinMatch = 3, /* shortest match possible */
33 MaxMatch = 258, /* longest match possible */
36 * huffman code paramaters
39 MaxHuffBits = 16, /* max bits in a huffman code */
40 ChainMem = 2 * (MaxHuffBits - 1) * MaxHuffBits,
43 * coding of the lz parse
46 LenShift = 4, /* leaves enough space for MinMatchMaxOff */
47 MaxLitRun = LenFlag - 1,
50 * internal lz paramaters
52 DeflateOut = 4096, /* output buffer size */
53 BlockSize = 8192, /* attempted input read quanta */
54 DeflateBlock = DeflateMaxBlock & ~(BlockSize - 1),
55 MinMatchMaxOff = 4096, /* max profitable offset for small match;
56 * assumes 8 bits for len, 5+10 for offset
57 * DONT CHANGE WITHOUT CHANGING LZPARSE CONSTANTS
59 HistSlop = 512, /* must be at lead MaxMatch */
61 HistSize = HistBlock + HistSlop,
64 HashSize = 1<<HashLog,
66 MaxOffCode = 256, /* biggest offset looked up in direct table */
74 * knuth vol. 3 multiplicative hashing
75 * each byte x chosen according to rules
76 * 1/4 < x < 3/10, 1/3 x < < 3/7, 4/7 < x < 2/3, 7/10 < x < 3/4
77 * with reasonable spread between the bytes & their complements
79 * the 3 byte value appears to be as almost good as the 4 byte value,
80 * and might be faster on some machines
83 #define hashit(c) ((u32int)((c) * 0x6b43a9) >> (24 - HashLog))
85 #define hashit(c) ((u32int)(((c) & 0xffffff) * 0x6b43a9b5) >> (32 - HashLog))
88 * lempel-ziv style compression state
93 ulong pos; /* current location in history buffer */
94 ulong avail; /* data available after pos */
96 ushort hash[HashSize]; /* hash chains */
98 int now; /* pos in hash chains */
99 int dot; /* dawn of time in history */
100 int prevlen; /* lazy matching state */
102 int maxcheck; /* compressor tuning */
104 uchar obuf[DeflateOut];
105 uchar *out; /* current position in the output buffer */
107 ulong bits; /* bit shift register */
109 int rbad; /* got an error reading the buffer */
110 int wbad; /* got an error writing the buffer */
111 int (*w)(void*, void*, int);
114 ulong totr; /* total input size */
115 ulong totw; /* total output size */
121 ushort parse[DeflateMaxBlock / 2 + 1];
122 int lastv; /* value being constucted for parse */
123 ulong litlencount[Nlitlen];
124 ulong offcount[Noff];
125 ushort *eparse; /* limit for parse table */
126 int bytes; /* consumed from the input */
127 int excost; /* cost of encoding extra len & off bits */
135 short bits; /* length of the code */
136 ushort encode; /* the code */
140 * encoding of dynamic huffman trees
149 uchar codes[Nlitlen+Noff];
150 uchar codeaux[Nlitlen+Noff];
153 static int deflateb(LZstate *lz, LZblock *lzb, void *rr, int (*r)(void*, void*, int));
154 static int lzcomp(LZstate*, LZblock*, uchar*, ushort*, int finish);
155 static void wrblock(LZstate*, int, ushort*, ushort*, Huff*, Huff*);
156 static int bitcost(Huff*, ulong*, int);
157 static int huffcodes(Dyncode*, Huff*, Huff*);
158 static void wrdyncode(LZstate*, Dyncode*);
159 static void lzput(LZstate*, ulong bits, int nbits);
160 static void lzflushbits(LZstate*);
161 static void lzflush(LZstate *lz);
162 static void lzwrite(LZstate *lz, void *buf, int n);
164 static int hufftabinit(Huff*, int, ulong*, int);
165 static int mkgzprecode(Huff*, ulong *, int, int);
167 static int mkprecode(Huff*, ulong *, int, int, ulong*);
168 static void nextchain(Chains*, int);
169 static void leafsort(ulong*, ushort*, int, int);
171 /* conversion from len to code word */
172 static int lencode[MaxMatch];
175 * conversion from off to code word
176 * off <= MaxOffCode ? offcode[off] : bigoffcode[off >> 7]
178 static int offcode[MaxOffCode];
179 static int bigoffcode[256];
181 /* litlen code words LenStart-285 extra bits */
182 static int litlenbase[Nlitlen-LenStart];
183 static int litlenextra[Nlitlen-LenStart] =
186 /* 260 */ 0, 0, 0, 0, 0, 1, 1, 1, 1, 2,
187 /* 270 */ 2, 2, 2, 3, 3, 3, 3, 4, 4, 4,
188 /* 280 */ 4, 5, 5, 5, 5, 0, 0, 0
191 /* offset code word extra bits */
192 static int offbase[Noff];
193 static int offextra[] =
195 0, 0, 0, 0, 1, 1, 2, 2, 3, 3,
196 4, 4, 5, 5, 6, 6, 7, 7, 8, 8,
197 9, 9, 10, 10, 11, 11, 12, 12, 13, 13,
201 /* order code lengths */
202 static int clenorder[Nclen] =
204 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
207 /* static huffman tables */
208 static Huff litlentab[Nlitlen];
209 static Huff offtab[Noff];
210 static Huff hofftab[Noff];
212 /* bit reversal for brain dead endian swap in huffman codes */
213 static uchar revtab[256];
215 static ulong nmatches;
220 ulong bitcount[MaxHuffBits];
223 /* byte reverse table */
227 revtab[i] |= 0x80 >> j;
229 /* static Litlen bit lengths */
231 litlentab[i].bits = 8;
232 for(i=144; i<256; i++)
233 litlentab[i].bits = 9;
234 for(i=256; i<280; i++)
235 litlentab[i].bits = 7;
236 for(i=280; i<Nlitlen; i++)
237 litlentab[i].bits = 8;
239 memset(bitcount, 0, sizeof(bitcount));
240 bitcount[8] += 144 - 0;
241 bitcount[9] += 256 - 144;
242 bitcount[7] += 280 - 256;
243 bitcount[8] += Nlitlen - 280;
245 if(!hufftabinit(litlentab, Nlitlen, bitcount, 9))
246 return FlateInternal;
248 /* static offset bit lengths */
249 for(i = 0; i < Noff; i++)
252 memset(bitcount, 0, sizeof(bitcount));
255 if(!hufftabinit(offtab, Noff, bitcount, 5))
256 return FlateInternal;
260 if(!mkgzprecode(hofftab, bitcount, 2, MaxHuffBits))
261 return FlateInternal;
263 /* conversion tables for lens & offs to codes */
265 for(i = LenStart; i < 286; i++){
266 n = ci + (1 << litlenextra[i - LenStart]);
267 litlenbase[i - LenStart] = ci;
271 /* patch up special case for len MaxMatch */
272 lencode[MaxMatch-MinMatch] = 285;
273 litlenbase[285-LenStart] = MaxMatch-MinMatch;
276 for(i = 0; i < 16; i++){
277 n = ci + (1 << offextra[i]);
285 n = ci + (1 << (offextra[i] - 7));
286 offbase[i] = ci << 7;
294 deflatereset(LZstate *lz, int level, int debug)
296 memset(lz->nexts, 0, sizeof lz->nexts);
297 memset(lz->hash, 0, sizeof lz->hash);
303 lz->eout = &lz->obuf[DeflateOut];
304 lz->prevlen = MinMatch - 1;
306 lz->now = MaxOff + 1;
310 lz->maxcheck = (1 << level);
311 lz->maxcheck -= lz->maxcheck >> 2;
314 else if(lz->maxcheck > 1024)
321 deflate(void *wr, int (*w)(void*, void*, int), void *rr, int (*r)(void*, void*, int), int level, int debug)
327 lz = malloc(sizeof *lz + sizeof *lzb);
330 lzb = (LZblock*)&lz[1];
332 deflatereset(lz, level, debug);
339 while(!lz->eof || lz->avail){
340 ok = deflateb(lz, lzb, rr, r);
344 if(ok == FlateOk && lz->rbad)
346 if(ok == FlateOk && lz->wbad)
347 ok = FlateOutputFail;
353 deflateb(LZstate *lz, LZblock *lzb, void *rr, int (*r)(void*, void*, int))
355 Dyncode dyncode, hdyncode;
356 Huff dlitlentab[Nlitlen], dofftab[Noff], hlitlentab[Nlitlen];
357 ulong litcount[Nlitlen];
358 long nunc, ndyn, nfix, nhuff;
361 int i, n, m, mm, nslop;
363 memset(lzb->litlencount, 0, sizeof lzb->litlencount);
364 memset(lzb->offcount, 0, sizeof lzb->offcount);
365 lzb->litlencount[DeflateEob]++;
368 lzb->eparse = lzb->parse;
372 slop = &lz->hist[lz->pos];
374 while(n < DeflateBlock && (!lz->eof || lz->avail)){
376 * fill the buffer as much as possible,
377 * while leaving room for MaxOff history behind lz->pos,
378 * and not reading more than we can handle.
380 * make sure we read at least HistSlop bytes.
383 ep = lz->pos + lz->avail;
386 m = HistBlock - MaxOff - lz->avail;
387 if(m > HistBlock - n)
389 if(m > (HistBlock + HistSlop) - ep)
390 m = (HistBlock + HistSlop) - ep;
391 if(m & ~(BlockSize - 1))
392 m &= ~(BlockSize - 1);
395 * be nice to the caller: stop reads that are too small.
396 * can only get here when we've already filled the buffer some
399 if(!m || !lzb->bytes)
400 return FlateInternal;
404 mm = (*r)(rr, &lz->hist[ep], m);
407 * wrap data to end if we're read it from the beginning
408 * this way, we don't have to wrap searches.
410 * wrap reads past the end to the beginning.
411 * this way, we can guarantee minimum size reads.
414 memmove(&lz->hist[ep + HistBlock], &lz->hist[ep], HistSlop - ep);
415 else if(ep + mm > HistBlock)
416 memmove(&lz->hist[0], &lz->hist[HistBlock], ep + mm - HistBlock);
427 ep = lz->pos + lz->avail;
430 if(lzb->bytes + ep - lz->pos > DeflateMaxBlock)
431 ep = lz->pos + DeflateMaxBlock - lzb->bytes;
432 m = lzcomp(lz, lzb, &lz->hist[ep], lzb->eparse, lz->eof);
434 lz->pos = (lz->pos + m) & (HistBlock - 1);
438 *lzb->eparse++ = lzb->lastv;
439 if(lzb->eparse > lzb->parse + nelem(lzb->parse))
440 return FlateInternal;
443 if(!mkgzprecode(dlitlentab, lzb->litlencount, Nlitlen, MaxHuffBits)
444 || !mkgzprecode(dofftab, lzb->offcount, Noff, MaxHuffBits))
445 return FlateInternal;
447 ndyn = huffcodes(&dyncode, dlitlentab, dofftab);
449 return FlateInternal;
450 ndyn += bitcost(dlitlentab, lzb->litlencount, Nlitlen)
451 + bitcost(dofftab, lzb->offcount, Noff)
454 memset(litcount, 0, sizeof litcount);
457 if(nslop > &lz->hist[HistSize] - slop)
458 nslop = &lz->hist[HistSize] - slop;
460 for(i = 0; i < nslop; i++)
462 hslop = &lz->hist[HistSlop - nslop];
464 litcount[hslop[i]]++;
465 litcount[DeflateEob]++;
467 if(!mkgzprecode(hlitlentab, litcount, Nlitlen, MaxHuffBits))
468 return FlateInternal;
469 nhuff = huffcodes(&hdyncode, hlitlentab, hofftab);
471 return FlateInternal;
472 nhuff += bitcost(hlitlentab, litcount, Nlitlen);
474 nfix = bitcost(litlentab, lzb->litlencount, Nlitlen)
475 + bitcost(offtab, lzb->offcount, Noff)
478 lzput(lz, lz->eof && !lz->avail, 1);
481 fprint(2, "block: bytes=%lud entries=%ld extra bits=%d\n\tuncompressed=%lud fixed=%lud dynamic=%lud huffman=%lud\n",
482 nunc, lzb->eparse - lzb->parse, lzb->excost, (nunc + 4) * 8, nfix, ndyn, nhuff);
483 fprint(2, "\tnlit=%lud matches=%lud eof=%d\n", nlits, nmatches, lz->eof && !lz->avail);
486 if((nunc + 4) * 8 < ndyn && (nunc + 4) * 8 < nfix && (nunc + 4) * 8 < nhuff){
487 lzput(lz, DeflateUnc, 2);
490 lzput(lz, nunc & 0xff, 8);
491 lzput(lz, (nunc >> 8) & 0xff, 8);
492 lzput(lz, ~nunc & 0xff, 8);
493 lzput(lz, (~nunc >> 8) & 0xff, 8);
496 lzwrite(lz, slop, nslop);
497 lzwrite(lz, &lz->hist[HistSlop], nunc - nslop);
498 }else if(ndyn < nfix && ndyn < nhuff){
499 lzput(lz, DeflateDyn, 2);
501 wrdyncode(lz, &dyncode);
502 wrblock(lz, slop - lz->hist, lzb->parse, lzb->eparse, dlitlentab, dofftab);
503 lzput(lz, dlitlentab[DeflateEob].encode, dlitlentab[DeflateEob].bits);
504 }else if(nhuff < nfix){
505 lzput(lz, DeflateDyn, 2);
507 wrdyncode(lz, &hdyncode);
510 for(i = nunc; i > MaxLitRun; i -= MaxLitRun)
511 lzb->parse[m++] = MaxLitRun;
514 wrblock(lz, slop - lz->hist, lzb->parse, lzb->parse + m, hlitlentab, hofftab);
515 lzput(lz, hlitlentab[DeflateEob].encode, hlitlentab[DeflateEob].bits);
517 lzput(lz, DeflateFix, 2);
519 wrblock(lz, slop - lz->hist, lzb->parse, lzb->eparse, litlentab, offtab);
520 lzput(lz, litlentab[DeflateEob].encode, litlentab[DeflateEob].bits);
523 if(lz->eof && !lz->avail){
531 lzwrite(LZstate *lz, void *buf, int n)
536 nw = (*lz->w)(lz->wr, buf, n);
548 lzwrite(lz, lz->obuf, lz->out - lz->obuf);
553 lzput(LZstate *lz, ulong bits, int nbits)
555 bits = (bits << lz->nbits) | lz->bits;
556 for(nbits += lz->nbits; nbits >= 8; nbits -= 8){
558 if(lz->out == lz->eout)
567 lzflushbits(LZstate *lz)
570 lzput(lz, 0, 8 - (lz->nbits & 7));
574 * write out a block of n samples,
575 * given lz encoding and counts for huffman tables
578 wrblock(LZstate *out, int litoff, ushort *soff, ushort *eoff, Huff *litlentab, Huff *offtab)
581 int i, run, offset, lit, len, c;
584 for(off = soff; off < eoff; ){
586 run = offset & MaxLitRun;
588 for(i = 0; i < run; i++){
589 lit = out->hist[litoff & (HistBlock - 1)];
591 fprint(2, "\tlit %.2ux %c\n", lit, lit);
593 if(!(offset & LenFlag))
595 len = offset >> LenShift;
597 }else if(offset & LenFlag){
598 len = offset >> LenShift;
604 litoff += len + MinMatch;
605 fprint(2, "\t<%d, %d>\n", offset + 1, len + MinMatch);
609 for(off = soff; off < eoff; ){
611 run = offset & MaxLitRun;
613 for(i = 0; i < run; i++){
614 lit = out->hist[litoff & (HistBlock - 1)];
616 lzput(out, litlentab[lit].encode, litlentab[lit].bits);
618 if(!(offset & LenFlag))
620 len = offset >> LenShift;
622 }else if(offset & LenFlag){
623 len = offset >> LenShift;
629 litoff += len + MinMatch;
631 lzput(out, litlentab[c].encode, litlentab[c].bits);
634 lzput(out, len - litlenbase[c], litlenextra[c]);
636 if(offset < MaxOffCode)
639 c = bigoffcode[offset >> 7];
640 lzput(out, offtab[c].encode, offtab[c].bits);
642 lzput(out, offset - offbase[c], offextra[c]);
647 * look for the longest, closest string which matches
648 * the next prefix. the clever part here is looking for
649 * a string 1 longer than the previous best match.
651 * follows the recommendation of limiting number of chains
652 * which are checked. this appears to be the best heuristic.
655 lzmatch(int now, int then, uchar *p, uchar *es, ushort *nexts, uchar *hist, int runlen, int check, int *m)
667 for(; check-- > 0; then = nexts[then & (MaxOff-1)]){
668 off = (ushort)(now - then);
669 if(off <= last || off > MaxOff)
672 t = hist + (((p - hist) - off) & (HistBlock-1));
681 * we have a new best match.
682 * extend it to it's maximum length
693 if(s == es || runlen > ml)
702 lzcomp(LZstate *lz, LZblock *lzb, uchar *ep, ushort *parse, int finish)
704 ulong cont, excost, *litlencount, *offcount;
705 uchar *p, *q, *s, *es;
706 ushort *nexts, *hash;
707 int v, i, h, runlen, n, now, then, m, prevlen, prevoff, maxdefer;
709 litlencount = lzb->litlencount;
710 offcount = lzb->offcount;
715 p = &lz->hist[lz->pos];
716 if(lz->prevlen != MinMatch - 1)
720 * hash in the links for any hanging link positions,
721 * and calculate the hash for the current position.
727 for(i = 0; i < n - 1; i++){
728 m = now - ((MinMatch-1) - i);
731 s = lz->hist + (((p - lz->hist) - (now - m)) & (HistBlock-1));
733 cont = (s[0] << 16) | (s[1] << 8) | s[2];
736 for(then = hash[h]; ; then = nexts[then & (MaxOff-1)]){
737 v = (ushort)(now - then);
738 if(v <= prevoff || v >= (MinMatch-1) - i)
742 if(then == (ushort)m)
744 nexts[m & (MaxOff-1)] = hash[h];
747 for(i = 0; i < n; i++)
748 cont = (cont << 8) | p[i];
751 * now must point to the index in the nexts array
752 * corresponding to p's position in the history
754 prevlen = lz->prevlen;
755 prevoff = lz->prevoff;
756 maxdefer = lz->maxcheck >> 2;
762 if(!finish || p >= ep)
768 runlen = lzmatch(now, hash[h], p, es, nexts, lz->hist, prevlen, lz->maxcheck, &m);
771 * back out of small matches too far in the past
773 if(runlen == MinMatch && m >= MinMatchMaxOff){
774 runlen = MinMatch - 1;
779 * record the encoding and increment counts for huffman trees
780 * if we get a match, defer selecting it until we check for
781 * a longer match at the next position.
783 if(prevlen >= runlen && prevlen != MinMatch - 1){
785 * old match at least as good; use that one
787 n = prevlen - MinMatch;
789 *parse++ = v | LenFlag | (n << LenShift);
792 *parse++ = prevoff << LenShift;
797 excost += litlenextra[n - LenStart];
799 if(prevoff < MaxOffCode)
800 n = offcode[prevoff];
802 n = bigoffcode[prevoff >> 7];
804 excost += offextra[n];
806 runlen = prevlen - 1;
807 prevlen = MinMatch - 1;
809 }else if(runlen == MinMatch - 1){
811 * no match; just put out the literal
813 if(++v == MaxLitRun){
821 if(prevlen != MinMatch - 1){
823 * longer match now. output previous literal,
824 * update current match, and try again
826 if(++v == MaxLitRun){
830 litlencount[p[-1]]++;
836 if(runlen < maxdefer){
840 n = runlen - MinMatch;
842 *parse++ = v | LenFlag | (n << LenShift);
845 *parse++ = prevoff << LenShift;
850 excost += litlenextra[n - LenStart];
852 if(prevoff < MaxOffCode)
853 n = offcode[prevoff];
855 n = bigoffcode[prevoff >> 7];
857 excost += offextra[n];
859 prevlen = MinMatch - 1;
865 * update the hash for the newly matched data
866 * this is constructed so the link for the old
867 * match in this position must be at the end of a chain,
868 * and will expire when this match is added, ie it will
869 * never be examined by the match loop.
870 * add to the hash chain only if we have the real hash data.
872 for(q = p + runlen; p != q; p++){
873 if(p + MinMatch <= ep){
875 nexts[now & (MaxOff-1)] = hash[h];
877 if(p + MinMatch < ep)
878 cont = (cont << 8) | p[MinMatch];
885 * we can just store away the lazy state and
886 * pick it up next time. the last block will have finish set
887 * so we won't have any pending matches
888 * however, we need to correct for how much we've encoded
890 if(prevlen != MinMatch - 1)
893 lzb->excost += excost;
898 lz->prevlen = prevlen;
899 lz->prevoff = prevoff;
901 return p - &lz->hist[lz->pos];
905 * make up the dynamic code tables, and return the number of bits
906 * needed to transmit them.
909 huffcodes(Dyncode *dc, Huff *littab, Huff *offtab)
912 uchar *codes, *codeaux;
913 ulong codecount[Nclen], excost;
914 int i, n, m, v, c, nlit, noff, ncode, nclen;
916 codetab = dc->codetab;
918 codeaux = dc->codeaux;
921 * trim the sizes of the tables
923 for(nlit = Nlitlen; nlit > 257 && littab[nlit-1].bits == 0; nlit--)
925 for(noff = Noff; noff > 1 && offtab[noff-1].bits == 0; noff--)
929 * make the code-length code
931 for(i = 0; i < nlit; i++)
932 codes[i] = littab[i].bits;
933 for(i = 0; i < noff; i++)
934 codes[i + nlit] = offtab[i].bits;
937 * run-length compress the code-length code
942 for(i = 0; i < ncode; ){
945 while(n < ncode && v == codes[n])
955 codeaux[c++] = m - 11;
961 codeaux[c++] = n - 3;
973 codeaux[c++] = m - 3;
980 memset(codecount, 0, sizeof codecount);
981 for(i = 0; i < c; i++)
982 codecount[codes[i]]++;
983 if(!mkgzprecode(codetab, codecount, Nclen, 8))
986 for(nclen = Nclen; nclen > 4 && codetab[clenorder[nclen-1]].bits == 0; nclen--)
994 return 5 + 5 + 4 + nclen * 3 + bitcost(codetab, codecount, Nclen) + excost;
998 wrdyncode(LZstate *out, Dyncode *dc)
1001 uchar *codes, *codeaux;
1005 * write out header, then code length code lengths,
1008 lzput(out, dc->nlit-257, 5);
1009 lzput(out, dc->noff-1, 5);
1010 lzput(out, dc->nclen-4, 4);
1012 codetab = dc->codetab;
1013 for(i = 0; i < dc->nclen; i++)
1014 lzput(out, codetab[clenorder[i]].bits, 3);
1017 codeaux = dc->codeaux;
1019 for(i = 0; i < c; i++){
1021 lzput(out, codetab[v].encode, codetab[v].bits);
1024 lzput(out, codeaux[i], 2);
1026 lzput(out, codeaux[i], 3);
1028 lzput(out, codeaux[i], 7);
1034 bitcost(Huff *tab, ulong *count, int n)
1040 for(i = 0; i < n; i++)
1041 tot += count[i] * tab[i].bits;
1046 mkgzprecode(Huff *tab, ulong *count, int n, int maxbits)
1048 ulong bitcount[MaxHuffBits];
1051 nbits = mkprecode(tab, count, n, maxbits, bitcount);
1052 for(i = 0; i < n; i++){
1053 if(tab[i].bits == -1)
1055 else if(tab[i].bits == 0){
1056 if(nbits != 0 || bitcount[0] != 1)
1064 if(bitcount[0] != 0)
1066 return hufftabinit(tab, n, bitcount, nbits);
1070 hufftabinit(Huff *tab, int n, ulong *bitcount, int nbits)
1072 ulong code, nc[MaxHuffBits];
1076 for(bits = 1; bits <= nbits; bits++){
1077 code = (code + bitcount[bits-1]) << 1;
1081 for(i = 0; i < n; i++){
1084 code = nc[bits]++ << (16 - bits);
1087 tab[i].encode = revtab[code >> 8] | (revtab[code & 0xff] << 8);
1095 * this should be in a library
1099 ulong count; /* occurances of everything in the chain */
1100 ushort leaf; /* leaves to the left of chain, or leaf value */
1101 char col; /* ref count for collecting unused chains */
1102 char gen; /* need to generate chains for next lower level */
1103 Chain *up; /* Chain up in the lists */
1108 Chain *lists[(MaxHuffBits - 1) * 2];
1109 ulong leafcount[MaxLeaf]; /* sorted list of leaf counts */
1110 ushort leafmap[MaxLeaf]; /* map to actual leaf number */
1111 int nleaf; /* number of leaves */
1112 Chain chains[ChainMem];
1120 * fast, low space overhead algorithm for max depth huffman type codes
1122 * J. Katajainen, A. Moffat and A. Turpin, "A fast and space-economical
1123 * algorithm for length-limited coding," Proc. Intl. Symp. on Algorithms
1124 * and Computation, Cairns, Australia, Dec. 1995, Lecture Notes in Computer
1125 * Science, Vol 1004, J. Staples, P. Eades, N. Katoh, and A. Moffat, eds.,
1126 * pp 12-21, Springer Verlag, New York, 1995.
1129 mkprecode(Huff *tab, ulong *count, int n, int maxbits, ulong *bitcount)
1135 memset(&cs, 0, sizeof cs);
1138 * set up the sorted list of leaves
1141 for(i = 0; i < n; i++){
1145 cs.leafcount[m] = count[i];
1152 tab[cs.leafmap[0]].bits = 0;
1159 leafsort(cs.leafcount, cs.leafmap, 0, m);
1161 for(i = 0; i < m; i++)
1162 cs.leafcount[i] = count[cs.leafmap[i]];
1167 cs.free = &cs.chains[2];
1168 cs.echains = &cs.chains[ChainMem];
1172 * initialize chains for each list
1175 c->count = cs.leafcount[0];
1180 cs.chains[1] = cs.chains[0];
1181 cs.chains[1].leaf = 2;
1182 cs.chains[1].count = cs.leafcount[1];
1183 for(i = 0; i < maxbits-1; i++){
1184 cs.lists[i * 2] = &cs.chains[0];
1185 cs.lists[i * 2 + 1] = &cs.chains[1];
1188 cs.nlists = 2 * (maxbits - 1);
1190 for(i = 2; i < m; i++)
1191 nextchain(&cs, cs.nlists - 2);
1194 bitcount[0] = cs.nleaf;
1195 for(c = cs.lists[cs.nlists - 1]; c != nil; c = c->up){
1197 bitcount[bits++] -= m;
1201 for(i = bits; i >= 0; i--)
1202 for(em = m + bitcount[i]; m < em; m++)
1203 tab[cs.leafmap[m]].bits = i;
1209 * calculate the next chain on the list
1210 * we can always toss out the old chain
1213 nextchain(Chains *cs, int list)
1218 oc = cs->lists[list + 1];
1219 cs->lists[list] = oc;
1224 * make sure we have all chains needed to make sumc
1225 * note it is possible to generate only one of these,
1226 * use twice that value for sumc, and then generate
1227 * the second if that preliminary sumc would be chosen.
1228 * however, this appears to be slower on current tests
1231 nextchain(cs, list - 2);
1232 nextchain(cs, list - 2);
1237 * pick up the chain we're going to add;
1238 * collect unused chains no free ones are left
1240 for(c = cs->free; ; c++){
1241 if(c >= cs->echains){
1243 for(i = 0; i < cs->nlists; i++)
1244 for(c = cs->lists[i]; c != nil; c = c->up)
1248 if(c->col != cs->col)
1253 * pick the cheapest of
1254 * 1) the next package from the previous list
1259 if(list > 0 && cs->lists[list-1] != nil)
1260 sumc = cs->lists[list-2]->count + cs->lists[list-1]->count;
1261 if(sumc != 0 && (nleaf >= cs->nleaf || cs->leafcount[nleaf] > sumc)){
1264 c->up = cs->lists[list-1];
1266 }else if(nleaf >= cs->nleaf){
1267 cs->lists[list + 1] = nil;
1270 c->leaf = nleaf + 1;
1271 c->count = cs->leafcount[nleaf];
1277 cs->lists[list + 1] = c;
1282 pivot(ulong *c, int a, int n)
1287 pi = a + j; /* 1/6 */
1289 pj = pi + j; /* 1/2 */
1290 pk = pj + j; /* 5/6 */
1308 leafsort(ulong *leafcount, ushort *leafmap, int a, int n)
1315 pi = pivot(leafcount, a, n);
1320 leafcount[pi] = leafcount[a];
1323 leafmap[pi] = leafmap[a];
1331 while(pi < pn && (leafcount[pi] < leafcount[a] || leafcount[pi] == leafcount[a] && leafmap[pi] > leafmap[a]));
1334 while(pj > a && (leafcount[pj] > leafcount[a] || leafcount[pj] == leafcount[a] && leafmap[pj] < leafmap[a]));
1338 leafcount[pi] = leafcount[pj];
1341 leafmap[pi] = leafmap[pj];
1345 leafcount[a] = leafcount[pj];
1348 leafmap[a] = leafmap[pj];
1354 leafsort(leafcount, leafmap, a, j);
1357 leafsort(leafcount, leafmap, a + (j+1), n);