lib/zlib/inftrees.c

2 /* inftrees.c -- generate Huffman trees for efficient decoding
4  * For conditions of distribution and use, see copyright notice in zlib.h
16   in the documentation of your product. If for some reason you cannot
44     unsigned root;              /* number of index bits for root table */
45     unsigned curr;              /* number of index bits for current table */
46     unsigned drop;              /* code bits to drop for sub-table */
50     unsigned incr;              /* for incrementing code, index */
51     unsigned fill;              /* index for replicating entries */
52     unsigned low;               /* low bits for current root entry */
53     unsigned mask;              /* mask for low root bits */
54     code here;                  /* table entry for duplication */
58     unsigned match;             /* use base and extra for symbol >= match */
60     unsigned short offs[MAXBITS+1];     /* offsets in table for each length */
81        for codes with equal lengths.  Then the code starts with all zero bits
82        for the first code of the shortest length, and the codes are integer
83        increments for the same length, and zeros are appended as the length
84        increases.  For the deflate format, these bits are stored backwards
94        The codes are sorted by computing a count of codes for each length,
95        creating from that a table of starting indices for each length in the
100        The length counts are used for other purposes as well, i.e. finding
102        codes at all, checking for a valid set of lengths, and looking ahead
107     /* accumulate lengths for codes (assumes lens[] all in 0..MAXBITS) */
108     for (len = 0; len <= MAXBITS; len++)
110     for (sym = 0; sym < codes; sym++)
115     for (max = MAXBITS; max >= 1; max--)
125         return 0;     /* no symbols, but wait for decoding to report error */
127     for (min = 1; min < max; min++)
131     /* check for an over-subscribed or incomplete set of lengths */
133     for (len = 1; len <= MAXBITS; len++) {
141     /* generate offsets into symbol table for each length for sorting */
143     for (len = 1; len < MAXBITS; len++)
147     for (sym = 0; sym < codes; sym++)
154        bits off of the bottom.  For codes where len is less than drop + curr,
158        root is the number of index bits for the root table.  When len exceeds
160        of the low root bits of huff.  This is saved in low to check for when a
166        counts are used for this, and so count[] is decremented as codes are
170        provided *table space.  It is checked for LENS and DIST tables against
173        for more information.
181     /* set up for code type */
198     /* initialize state for loop */
204     drop = 0;                   /* current bits to drop from code for index */
207     mask = used - 1;            /* mask for comparing low */
215     for (;;) {
231         /* replicate for those indices with low len bits equal to huff */
277             /* check for enough space */