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