1 /* inftrees.c -- generate Huffman trees for efficient decoding
2  * Copyright (C) 1995-2005 Mark Adler
13    The code lengths are lens[0..codes-1].  The result starts at *table,
14    whose indices are 0..2^bits-1.  work is a writable array of at least
17    -1 is an invalid code, and +1 means that ENOUGH isn't enough.  table
26     unsigned len;               /* a code's length in bits */  in zlib_inflate_table()  local
28     unsigned min, max;          /* minimum and maximum code lengths */  in zlib_inflate_table()  local
31     unsigned drop;              /* code bits to drop for sub-table */  in zlib_inflate_table()
63        code lengths are lens[0..codes-1].  Each length corresponds to the  in zlib_inflate_table()
64        symbols 0..codes-1.  The Huffman code is generated by first sorting the  in zlib_inflate_table()
88        at length counts to determine sub-table sizes when building the  in zlib_inflate_table()
93     for (len = 0; len <= MAXBITS; len++)  in zlib_inflate_table()
94         count[len] = 0;  in zlib_inflate_table()
100     for (max = MAXBITS; max >= 1; max--)  in zlib_inflate_table()
112     for (min = 1; min < MAXBITS; min++)  in zlib_inflate_table()
113         if (count[min] != 0) break;  in zlib_inflate_table()
114     if (root < min) root = min;  in zlib_inflate_table()
116     /* check for an over-subscribed or incomplete set of lengths */  in zlib_inflate_table()
118     for (len = 1; len <= MAXBITS; len++) {  in zlib_inflate_table()
120         left -= count[len];  in zlib_inflate_table()
121         if (left < 0) return -1;        /* over-subscribed */  in zlib_inflate_table()
124         return -1;                      /* incomplete set */  in zlib_inflate_table()
128     for (len = 1; len < MAXBITS; len++)  in zlib_inflate_table()
129         offs[len + 1] = offs[len] + count[len];  in zlib_inflate_table()
138        with length len.  That code is converted to an index by dropping drop  in zlib_inflate_table()
139        bits off of the bottom.  For codes where len is less than drop + curr,  in zlib_inflate_table()
140        those top drop + curr - len bits are incremented through all values to  in zlib_inflate_table()
143        root is the number of index bits for the root table.  When len exceeds  in zlib_inflate_table()
144        root, sub-tables are created pointed to by the root entry with an index  in zlib_inflate_table()
146        new sub-table should be started.  drop is zero when the root table is  in zlib_inflate_table()
147        being filled, and drop is root when sub-tables are being filled.  in zlib_inflate_table()
149        When a new sub-table is needed, it is necessary to look ahead in the  in zlib_inflate_table()
150        code lengths to determine what size sub-table is needed.  The length  in zlib_inflate_table()
170         base = extra = work;    /* dummy value--not used */  in zlib_inflate_table()
175         base -= 257;  in zlib_inflate_table()
177         extra -= 257;  in zlib_inflate_table()
183         end = -1;  in zlib_inflate_table()
189     len = min;                  /* starting code length */  in zlib_inflate_table()
193     low = (unsigned)(-1);       /* trigger new sub-table when len > root */  in zlib_inflate_table()
195     mask = used - 1;            /* mask for comparing low */  in zlib_inflate_table()
198     if (type == LENS && used >= ENOUGH - MAXD)  in zlib_inflate_table()
204         this.bits = (unsigned char)(len - drop);  in zlib_inflate_table()
218         /* replicate for those indices with low len bits equal to huff */  in zlib_inflate_table()
219         incr = 1U << (len - drop);  in zlib_inflate_table()
221         min = fill;                 /* save offset to next table */  in zlib_inflate_table()
223             fill -= incr;  in zlib_inflate_table()
227         /* backwards increment the len-bit code huff */  in zlib_inflate_table()
228         incr = 1U << (len - 1);  in zlib_inflate_table()
232             huff &= incr - 1;  in zlib_inflate_table()
238         /* go to next symbol, update count, len */  in zlib_inflate_table()
240         if (--(count[len]) == 0) {  in zlib_inflate_table()
241             if (len == max) break;  in zlib_inflate_table()
242             len = lens[work[sym]];  in zlib_inflate_table()
245         /* create new sub-table if needed */  in zlib_inflate_table()
246         if (len > root && (huff & mask) != low) {  in zlib_inflate_table()
247             /* if first time, transition to sub-tables */  in zlib_inflate_table()
252             next += min;            /* here min is 1 << curr */  in zlib_inflate_table()
255             curr = len - drop;  in zlib_inflate_table()
258                 left -= count[curr + drop];  in zlib_inflate_table()
266             if (type == LENS && used >= ENOUGH - MAXD)  in zlib_inflate_table()
269             /* point entry in root table to sub-table */  in zlib_inflate_table()
273             (*table)[low].val = (unsigned short)(next - *table);  in zlib_inflate_table()
280        len is equal to curr + drop, so there is no loop needed to increment  in zlib_inflate_table()
281        through high index bits.  When the current sub-table is filled, the loop  in zlib_inflate_table()
285     this.bits = (unsigned char)(len - drop);  in zlib_inflate_table()
288         /* when done with sub-table, drop back to root table */  in zlib_inflate_table()
291             len = root;  in zlib_inflate_table()
293             this.bits = (unsigned char)len;  in zlib_inflate_table()
299         /* backwards increment the len-bit code huff */  in zlib_inflate_table()
300         incr = 1U << (len - 1);  in zlib_inflate_table()
304             huff &= incr - 1;  in zlib_inflate_table()