Lines Matching +full:16 +full:- +full:bits
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
18 on return points to the next available entry's address. bits is the
19 requested root table index bits, and on return it is the actual root
20 table index bits. It will differ if the request is greater than the
24 code **table, unsigned *bits, unsigned short *work) in zlib_inflate_table() argument
26 unsigned len; /* a code's length in bits */ in zlib_inflate_table()
29 unsigned root; /* number of index bits for root table */ in zlib_inflate_table()
30 unsigned curr; /* number of index bits for current table */ in zlib_inflate_table()
31 unsigned drop; /* code bits to drop for sub-table */ in zlib_inflate_table()
37 unsigned low; /* low bits for current root entry */ in zlib_inflate_table()
38 unsigned mask; /* mask for low root bits */ in zlib_inflate_table()
42 const unsigned short *extra; /* extra bits table to use */ in zlib_inflate_table()
50 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18, in zlib_inflate_table()
51 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 201, 196}; in zlib_inflate_table()
57 16, 16, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22, 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()
66 for codes with equal lengths. Then the code starts with all zero bits in zlib_inflate_table()
69 increases. For the deflate format, these bits are stored backwards in zlib_inflate_table()
88 at length counts to determine sub-table sizes when building the in zlib_inflate_table()
99 root = *bits; in zlib_inflate_table()
100 for (max = MAXBITS; max >= 1; max--) in zlib_inflate_table()
105 this.bits = (unsigned char)1; in zlib_inflate_table()
109 *bits = 1; in zlib_inflate_table()
116 /* check for an over-subscribed or incomplete set of lengths */ 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()
137 filled is at next and has curr index bits. The code being used is huff 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()
145 of the low root bits of huff. This is saved in low to check for when a 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()
159 This assumes that when type == LENS, bits == 9. 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()
191 curr = root; /* current table index bits */ in zlib_inflate_table()
192 drop = 0; /* current bits to drop from code for index */ 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()
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()
240 if (--(count[len]) == 0) { in zlib_inflate_table()
245 /* create new sub-table if needed */ in zlib_inflate_table()
247 /* if first time, transition to sub-tables */ 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()
272 (*table)[low].bits = (unsigned char)root; in zlib_inflate_table()
273 (*table)[low].val = (unsigned short)(next - *table); 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()
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()
313 *bits = root; in zlib_inflate_table()