Line | Count | Source (jump to first uncovered line) |
1 | | /* inftrees.c -- generate Huffman trees for efficient decoding |
2 | | * Copyright (C) 1995-2022 Mark Adler |
3 | | * For conditions of distribution and use, see copyright notice in zlib.h |
4 | | */ |
5 | | |
6 | | #include "zutil.h" |
7 | | #include "inftrees.h" |
8 | | |
9 | 0 | #define MAXBITS 15 |
10 | | |
11 | | const char inflate_copyright[] = |
12 | | " inflate 1.2.13 Copyright 1995-2022 Mark Adler "; |
13 | | /* |
14 | | If you use the zlib library in a product, an acknowledgment is welcome |
15 | | in the documentation of your product. If for some reason you cannot |
16 | | include such an acknowledgment, I would appreciate that you keep this |
17 | | copyright string in the executable of your product. |
18 | | */ |
19 | | |
20 | | /* |
21 | | Build a set of tables to decode the provided canonical Huffman code. |
22 | | The code lengths are lens[0..codes-1]. The result starts at *table, |
23 | | whose indices are 0..2^bits-1. work is a writable array of at least |
24 | | lens shorts, which is used as a work area. type is the type of code |
25 | | to be generated, CODES, LENS, or DISTS. On return, zero is success, |
26 | | -1 is an invalid code, and +1 means that ENOUGH isn't enough. table |
27 | | on return points to the next available entry's address. bits is the |
28 | | requested root table index bits, and on return it is the actual root |
29 | | table index bits. It will differ if the request is greater than the |
30 | | longest code or if it is less than the shortest code. |
31 | | */ |
32 | | int ZLIB_INTERNAL inflate_table(type, lens, codes, table, bits, work) |
33 | | codetype type; |
34 | | unsigned short FAR *lens; |
35 | | unsigned codes; |
36 | | code FAR * FAR *table; |
37 | | unsigned FAR *bits; |
38 | | unsigned short FAR *work; |
39 | 0 | { |
40 | 0 | unsigned len; /* a code's length in bits */ |
41 | 0 | unsigned sym; /* index of code symbols */ |
42 | 0 | unsigned min, max; /* minimum and maximum code lengths */ |
43 | 0 | unsigned root; /* number of index bits for root table */ |
44 | 0 | unsigned curr; /* number of index bits for current table */ |
45 | 0 | unsigned drop; /* code bits to drop for sub-table */ |
46 | 0 | int left; /* number of prefix codes available */ |
47 | 0 | unsigned used; /* code entries in table used */ |
48 | 0 | unsigned huff; /* Huffman code */ |
49 | 0 | unsigned incr; /* for incrementing code, index */ |
50 | 0 | unsigned fill; /* index for replicating entries */ |
51 | 0 | unsigned low; /* low bits for current root entry */ |
52 | 0 | unsigned mask; /* mask for low root bits */ |
53 | 0 | code here; /* table entry for duplication */ |
54 | 0 | code FAR *next; /* next available space in table */ |
55 | 0 | const unsigned short FAR *base; /* base value table to use */ |
56 | 0 | const unsigned short FAR *extra; /* extra bits table to use */ |
57 | 0 | unsigned match; /* use base and extra for symbol >= match */ |
58 | 0 | unsigned short count[MAXBITS+1]; /* number of codes of each length */ |
59 | 0 | unsigned short offs[MAXBITS+1]; /* offsets in table for each length */ |
60 | 0 | static const unsigned short lbase[31] = { /* Length codes 257..285 base */ |
61 | 0 | 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, |
62 | 0 | 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; |
63 | 0 | static const unsigned short lext[31] = { /* Length codes 257..285 extra */ |
64 | 0 | 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18, |
65 | 0 | 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 194, 65}; |
66 | 0 | static const unsigned short dbase[32] = { /* Distance codes 0..29 base */ |
67 | 0 | 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, |
68 | 0 | 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, |
69 | 0 | 8193, 12289, 16385, 24577, 0, 0}; |
70 | 0 | static const unsigned short dext[32] = { /* Distance codes 0..29 extra */ |
71 | 0 | 16, 16, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22, |
72 | 0 | 23, 23, 24, 24, 25, 25, 26, 26, 27, 27, |
73 | 0 | 28, 28, 29, 29, 64, 64}; |
74 | | |
75 | | /* |
76 | | Process a set of code lengths to create a canonical Huffman code. The |
77 | | code lengths are lens[0..codes-1]. Each length corresponds to the |
78 | | symbols 0..codes-1. The Huffman code is generated by first sorting the |
79 | | symbols by length from short to long, and retaining the symbol order |
80 | | for codes with equal lengths. Then the code starts with all zero bits |
81 | | for the first code of the shortest length, and the codes are integer |
82 | | increments for the same length, and zeros are appended as the length |
83 | | increases. For the deflate format, these bits are stored backwards |
84 | | from their more natural integer increment ordering, and so when the |
85 | | decoding tables are built in the large loop below, the integer codes |
86 | | are incremented backwards. |
87 | | |
88 | | This routine assumes, but does not check, that all of the entries in |
89 | | lens[] are in the range 0..MAXBITS. The caller must assure this. |
90 | | 1..MAXBITS is interpreted as that code length. zero means that that |
91 | | symbol does not occur in this code. |
92 | | |
93 | | The codes are sorted by computing a count of codes for each length, |
94 | | creating from that a table of starting indices for each length in the |
95 | | sorted table, and then entering the symbols in order in the sorted |
96 | | table. The sorted table is work[], with that space being provided by |
97 | | the caller. |
98 | | |
99 | | The length counts are used for other purposes as well, i.e. finding |
100 | | the minimum and maximum length codes, determining if there are any |
101 | | codes at all, checking for a valid set of lengths, and looking ahead |
102 | | at length counts to determine sub-table sizes when building the |
103 | | decoding tables. |
104 | | */ |
105 | | |
106 | | /* accumulate lengths for codes (assumes lens[] all in 0..MAXBITS) */ |
107 | 0 | for (len = 0; len <= MAXBITS; len++) |
108 | 0 | count[len] = 0; |
109 | 0 | for (sym = 0; sym < codes; sym++) |
110 | 0 | count[lens[sym]]++; |
111 | | |
112 | | /* bound code lengths, force root to be within code lengths */ |
113 | 0 | root = *bits; |
114 | 0 | for (max = MAXBITS; max >= 1; max--) |
115 | 0 | if (count[max] != 0) break; |
116 | 0 | if (root > max) root = max; |
117 | 0 | if (max == 0) { /* no symbols to code at all */ |
118 | 0 | here.op = (unsigned char)64; /* invalid code marker */ |
119 | 0 | here.bits = (unsigned char)1; |
120 | 0 | here.val = (unsigned short)0; |
121 | 0 | *(*table)++ = here; /* make a table to force an error */ |
122 | 0 | *(*table)++ = here; |
123 | 0 | *bits = 1; |
124 | 0 | return 0; /* no symbols, but wait for decoding to report error */ |
125 | 0 | } |
126 | 0 | for (min = 1; min < max; min++) |
127 | 0 | if (count[min] != 0) break; |
128 | 0 | if (root < min) root = min; |
129 | | |
130 | | /* check for an over-subscribed or incomplete set of lengths */ |
131 | 0 | left = 1; |
132 | 0 | for (len = 1; len <= MAXBITS; len++) { |
133 | 0 | left <<= 1; |
134 | 0 | left -= count[len]; |
135 | 0 | if (left < 0) return -1; /* over-subscribed */ |
136 | 0 | } |
137 | 0 | if (left > 0 && (type == CODES || max != 1)) |
138 | 0 | return -1; /* incomplete set */ |
139 | | |
140 | | /* generate offsets into symbol table for each length for sorting */ |
141 | 0 | offs[1] = 0; |
142 | 0 | for (len = 1; len < MAXBITS; len++) |
143 | 0 | offs[len + 1] = offs[len] + count[len]; |
144 | | |
145 | | /* sort symbols by length, by symbol order within each length */ |
146 | 0 | for (sym = 0; sym < codes; sym++) |
147 | 0 | if (lens[sym] != 0) work[offs[lens[sym]]++] = (unsigned short)sym; |
148 | | |
149 | | /* |
150 | | Create and fill in decoding tables. In this loop, the table being |
151 | | filled is at next and has curr index bits. The code being used is huff |
152 | | with length len. That code is converted to an index by dropping drop |
153 | | bits off of the bottom. For codes where len is less than drop + curr, |
154 | | those top drop + curr - len bits are incremented through all values to |
155 | | fill the table with replicated entries. |
156 | | |
157 | | root is the number of index bits for the root table. When len exceeds |
158 | | root, sub-tables are created pointed to by the root entry with an index |
159 | | of the low root bits of huff. This is saved in low to check for when a |
160 | | new sub-table should be started. drop is zero when the root table is |
161 | | being filled, and drop is root when sub-tables are being filled. |
162 | | |
163 | | When a new sub-table is needed, it is necessary to look ahead in the |
164 | | code lengths to determine what size sub-table is needed. The length |
165 | | counts are used for this, and so count[] is decremented as codes are |
166 | | entered in the tables. |
167 | | |
168 | | used keeps track of how many table entries have been allocated from the |
169 | | provided *table space. It is checked for LENS and DIST tables against |
170 | | the constants ENOUGH_LENS and ENOUGH_DISTS to guard against changes in |
171 | | the initial root table size constants. See the comments in inftrees.h |
172 | | for more information. |
173 | | |
174 | | sym increments through all symbols, and the loop terminates when |
175 | | all codes of length max, i.e. all codes, have been processed. This |
176 | | routine permits incomplete codes, so another loop after this one fills |
177 | | in the rest of the decoding tables with invalid code markers. |
178 | | */ |
179 | | |
180 | | /* set up for code type */ |
181 | 0 | switch (type) { |
182 | 0 | case CODES: |
183 | 0 | base = extra = work; /* dummy value--not used */ |
184 | 0 | match = 20; |
185 | 0 | break; |
186 | 0 | case LENS: |
187 | 0 | base = lbase; |
188 | 0 | extra = lext; |
189 | 0 | match = 257; |
190 | 0 | break; |
191 | 0 | default: /* DISTS */ |
192 | 0 | base = dbase; |
193 | 0 | extra = dext; |
194 | 0 | match = 0; |
195 | 0 | } |
196 | | |
197 | | /* initialize state for loop */ |
198 | 0 | huff = 0; /* starting code */ |
199 | 0 | sym = 0; /* starting code symbol */ |
200 | 0 | len = min; /* starting code length */ |
201 | 0 | next = *table; /* current table to fill in */ |
202 | 0 | curr = root; /* current table index bits */ |
203 | 0 | drop = 0; /* current bits to drop from code for index */ |
204 | 0 | low = (unsigned)(-1); /* trigger new sub-table when len > root */ |
205 | 0 | used = 1U << root; /* use root table entries */ |
206 | 0 | mask = used - 1; /* mask for comparing low */ |
207 | | |
208 | | /* check available table space */ |
209 | 0 | if ((type == LENS && used > ENOUGH_LENS) || |
210 | 0 | (type == DISTS && used > ENOUGH_DISTS)) |
211 | 0 | return 1; |
212 | | |
213 | | /* process all codes and make table entries */ |
214 | 0 | for (;;) { |
215 | | /* create table entry */ |
216 | 0 | here.bits = (unsigned char)(len - drop); |
217 | 0 | if (work[sym] + 1U < match) { |
218 | 0 | here.op = (unsigned char)0; |
219 | 0 | here.val = work[sym]; |
220 | 0 | } |
221 | 0 | else if (work[sym] >= match) { |
222 | 0 | here.op = (unsigned char)(extra[work[sym] - match]); |
223 | 0 | here.val = base[work[sym] - match]; |
224 | 0 | } |
225 | 0 | else { |
226 | 0 | here.op = (unsigned char)(32 + 64); /* end of block */ |
227 | 0 | here.val = 0; |
228 | 0 | } |
229 | | |
230 | | /* replicate for those indices with low len bits equal to huff */ |
231 | 0 | incr = 1U << (len - drop); |
232 | 0 | fill = 1U << curr; |
233 | 0 | min = fill; /* save offset to next table */ |
234 | 0 | do { |
235 | 0 | fill -= incr; |
236 | 0 | next[(huff >> drop) + fill] = here; |
237 | 0 | } while (fill != 0); |
238 | | |
239 | | /* backwards increment the len-bit code huff */ |
240 | 0 | incr = 1U << (len - 1); |
241 | 0 | while (huff & incr) |
242 | 0 | incr >>= 1; |
243 | 0 | if (incr != 0) { |
244 | 0 | huff &= incr - 1; |
245 | 0 | huff += incr; |
246 | 0 | } |
247 | 0 | else |
248 | 0 | huff = 0; |
249 | | |
250 | | /* go to next symbol, update count, len */ |
251 | 0 | sym++; |
252 | 0 | if (--(count[len]) == 0) { |
253 | 0 | if (len == max) break; |
254 | 0 | len = lens[work[sym]]; |
255 | 0 | } |
256 | | |
257 | | /* create new sub-table if needed */ |
258 | 0 | if (len > root && (huff & mask) != low) { |
259 | | /* if first time, transition to sub-tables */ |
260 | 0 | if (drop == 0) |
261 | 0 | drop = root; |
262 | | |
263 | | /* increment past last table */ |
264 | 0 | next += min; /* here min is 1 << curr */ |
265 | | |
266 | | /* determine length of next table */ |
267 | 0 | curr = len - drop; |
268 | 0 | left = (int)(1 << curr); |
269 | 0 | while (curr + drop < max) { |
270 | 0 | left -= count[curr + drop]; |
271 | 0 | if (left <= 0) break; |
272 | 0 | curr++; |
273 | 0 | left <<= 1; |
274 | 0 | } |
275 | | |
276 | | /* check for enough space */ |
277 | 0 | used += 1U << curr; |
278 | 0 | if ((type == LENS && used > ENOUGH_LENS) || |
279 | 0 | (type == DISTS && used > ENOUGH_DISTS)) |
280 | 0 | return 1; |
281 | | |
282 | | /* point entry in root table to sub-table */ |
283 | 0 | low = huff & mask; |
284 | 0 | (*table)[low].op = (unsigned char)curr; |
285 | 0 | (*table)[low].bits = (unsigned char)root; |
286 | 0 | (*table)[low].val = (unsigned short)(next - *table); |
287 | 0 | } |
288 | 0 | } |
289 | | |
290 | | /* fill in remaining table entry if code is incomplete (guaranteed to have |
291 | | at most one remaining entry, since if the code is incomplete, the |
292 | | maximum code length that was allowed to get this far is one bit) */ |
293 | 0 | if (huff != 0) { |
294 | 0 | here.op = (unsigned char)64; /* invalid code marker */ |
295 | 0 | here.bits = (unsigned char)(len - drop); |
296 | 0 | here.val = (unsigned short)0; |
297 | 0 | next[huff] = here; |
298 | 0 | } |
299 | | |
300 | | /* set return parameters */ |
301 | 0 | *table += used; |
302 | 0 | *bits = root; |
303 | 0 | return 0; |
304 | 0 | } |