| Geant4 Cross Reference |
1 /* inftrees.c -- generate Huffman trees for ef 1
2 * Copyright (C) 1995-2022 Mark Adler
3 * For conditions of distribution and use, see
4 */
5
6 #include "zutil.h"
7 #include "inftrees.h"
8
9 #define MAXBITS 15
10
11 const char inflate_copyright[] =
12 " inflate 1.2.13 Copyright 1995-2022 Mark A
13 /*
14 If you use the zlib library in a product, an
15 in the documentation of your product. If for
16 include such an acknowledgment, I would appr
17 copyright string in the executable of your p
18 */
19
20 /*
21 Build a set of tables to decode the provide
22 The code lengths are lens[0..codes-1]. The
23 whose indices are 0..2^bits-1. work is a w
24 lens shorts, which is used as a work area.
25 to be generated, CODES, LENS, or DISTS. On
26 -1 is an invalid code, and +1 means that EN
27 on return points to the next available entr
28 requested root table index bits, and on ret
29 table index bits. It will differ if the re
30 longest code or if it is less than the shor
31 */
32 int ZLIB_INTERNAL inflate_table(type, lens, co
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 {
40 unsigned len; /* a code's le
41 unsigned sym; /* index of co
42 unsigned min, max; /* minimum and
43 unsigned root; /* number of i
44 unsigned curr; /* number of i
45 unsigned drop; /* code bits t
46 int left; /* number of p
47 unsigned used; /* code entrie
48 unsigned huff; /* Huffman cod
49 unsigned incr; /* for increme
50 unsigned fill; /* index for r
51 unsigned low; /* low bits fo
52 unsigned mask; /* mask for lo
53 code here; /* table entry
54 code FAR *next; /* next availa
55 const unsigned short FAR *base; /* bas
56 const unsigned short FAR *extra; /* ext
57 unsigned match; /* use base an
58 unsigned short count[MAXBITS+1]; /* num
59 unsigned short offs[MAXBITS+1]; /* off
60 static const unsigned short lbase[31] = {
61 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 1
62 35, 43, 51, 59, 67, 83, 99, 115, 131,
63 static const unsigned short lext[31] = { /
64 16, 16, 16, 16, 16, 16, 16, 16, 17, 17
65 19, 19, 19, 19, 20, 20, 20, 20, 21, 21
66 static const unsigned short dbase[32] = {
67 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 4
68 257, 385, 513, 769, 1025, 1537, 2049,
69 8193, 12289, 16385, 24577, 0, 0};
70 static const unsigned short dext[32] = { /
71 16, 16, 16, 16, 17, 17, 18, 18, 19, 19
72 23, 23, 24, 24, 25, 25, 26, 26, 27, 27
73 28, 28, 29, 29, 64, 64};
74
75 /*
76 Process a set of code lengths to create
77 code lengths are lens[0..codes-1]. Eac
78 symbols 0..codes-1. The Huffman code i
79 symbols by length from short to long, a
80 for codes with equal lengths. Then the
81 for the first code of the shortest leng
82 increments for the same length, and zer
83 increases. For the deflate format, the
84 from their more natural integer increme
85 decoding tables are built in the large
86 are incremented backwards.
87
88 This routine assumes, but does not chec
89 lens[] are in the range 0..MAXBITS. Th
90 1..MAXBITS is interpreted as that code
91 symbol does not occur in this code.
92
93 The codes are sorted by computing a cou
94 creating from that a table of starting
95 sorted table, and then entering the sym
96 table. The sorted table is work[], wit
97 the caller.
98
99 The length counts are used for other pu
100 the minimum and maximum length codes, d
101 codes at all, checking for a valid set
102 at length counts to determine sub-table
103 decoding tables.
104 */
105
106 /* accumulate lengths for codes (assumes l
107 for (len = 0; len <= MAXBITS; len++)
108 count[len] = 0;
109 for (sym = 0; sym < codes; sym++)
110 count[lens[sym]]++;
111
112 /* bound code lengths, force root to be wi
113 root = *bits;
114 for (max = MAXBITS; max >= 1; max--)
115 if (count[max] != 0) break;
116 if (root > max) root = max;
117 if (max == 0) { /* no
118 here.op = (unsigned char)64; /* inv
119 here.bits = (unsigned char)1;
120 here.val = (unsigned short)0;
121 *(*table)++ = here; /* mak
122 *(*table)++ = here;
123 *bits = 1;
124 return 0; /* no symbols, but wait
125 }
126 for (min = 1; min < max; min++)
127 if (count[min] != 0) break;
128 if (root < min) root = min;
129
130 /* check for an over-subscribed or incompl
131 left = 1;
132 for (len = 1; len <= MAXBITS; len++) {
133 left <<= 1;
134 left -= count[len];
135 if (left < 0) return -1; /* ove
136 }
137 if (left > 0 && (type == CODES || max != 1
138 return -1; /* inc
139
140 /* generate offsets into symbol table for
141 offs[1] = 0;
142 for (len = 1; len < MAXBITS; len++)
143 offs[len + 1] = offs[len] + count[len]
144
145 /* sort symbols by length, by symbol order
146 for (sym = 0; sym < codes; sym++)
147 if (lens[sym] != 0) work[offs[lens[sym
148
149 /*
150 Create and fill in decoding tables. In
151 filled is at next and has curr index bi
152 with length len. That code is converte
153 bits off of the bottom. For codes wher
154 those top drop + curr - len bits are in
155 fill the table with replicated entries.
156
157 root is the number of index bits for th
158 root, sub-tables are created pointed to
159 of the low root bits of huff. This is
160 new sub-table should be started. drop
161 being filled, and drop is root when sub
162
163 When a new sub-table is needed, it is n
164 code lengths to determine what size sub
165 counts are used for this, and so count[
166 entered in the tables.
167
168 used keeps track of how many table entr
169 provided *table space. It is checked f
170 the constants ENOUGH_LENS and ENOUGH_DI
171 the initial root table size constants.
172 for more information.
173
174 sym increments through all symbols, and
175 all codes of length max, i.e. all codes
176 routine permits incomplete codes, so an
177 in the rest of the decoding tables with
178 */
179
180 /* set up for code type */
181 switch (type) {
182 case CODES:
183 base = extra = work; /* dummy value
184 match = 20;
185 break;
186 case LENS:
187 base = lbase;
188 extra = lext;
189 match = 257;
190 break;
191 default: /* DISTS */
192 base = dbase;
193 extra = dext;
194 match = 0;
195 }
196
197 /* initialize state for loop */
198 huff = 0; /* starting co
199 sym = 0; /* starting co
200 len = min; /* starting co
201 next = *table; /* current tab
202 curr = root; /* current tab
203 drop = 0; /* current bit
204 low = (unsigned)(-1); /* trigger new
205 used = 1U << root; /* use root ta
206 mask = used - 1; /* mask for co
207
208 /* check available table space */
209 if ((type == LENS && used > ENOUGH_LENS) |
210 (type == DISTS && used > ENOUGH_DISTS)
211 return 1;
212
213 /* process all codes and make table entrie
214 for (;;) {
215 /* create table entry */
216 here.bits = (unsigned char)(len - drop
217 if (work[sym] + 1U < match) {
218 here.op = (unsigned char)0;
219 here.val = work[sym];
220 }
221 else if (work[sym] >= match) {
222 here.op = (unsigned char)(extra[wo
223 here.val = base[work[sym] - match]
224 }
225 else {
226 here.op = (unsigned char)(32 + 64)
227 here.val = 0;
228 }
229
230 /* replicate for those indices with lo
231 incr = 1U << (len - drop);
232 fill = 1U << curr;
233 min = fill; /* save of
234 do {
235 fill -= incr;
236 next[(huff >> drop) + fill] = here
237 } while (fill != 0);
238
239 /* backwards increment the len-bit cod
240 incr = 1U << (len - 1);
241 while (huff & incr)
242 incr >>= 1;
243 if (incr != 0) {
244 huff &= incr - 1;
245 huff += incr;
246 }
247 else
248 huff = 0;
249
250 /* go to next symbol, update count, le
251 sym++;
252 if (--(count[len]) == 0) {
253 if (len == max) break;
254 len = lens[work[sym]];
255 }
256
257 /* create new sub-table if needed */
258 if (len > root && (huff & mask) != low
259 /* if first time, transition to su
260 if (drop == 0)
261 drop = root;
262
263 /* increment past last table */
264 next += min; /* here mi
265
266 /* determine length of next table
267 curr = len - drop;
268 left = (int)(1 << curr);
269 while (curr + drop < max) {
270 left -= count[curr + drop];
271 if (left <= 0) break;
272 curr++;
273 left <<= 1;
274 }
275
276 /* check for enough space */
277 used += 1U << curr;
278 if ((type == LENS && used > ENOUGH
279 (type == DISTS && used > ENOUG
280 return 1;
281
282 /* point entry in root table to su
283 low = huff & mask;
284 (*table)[low].op = (unsigned char)
285 (*table)[low].bits = (unsigned cha
286 (*table)[low].val = (unsigned shor
287 }
288 }
289
290 /* fill in remaining table entry if code i
291 at most one remaining entry, since if t
292 maximum code length that was allowed to
293 if (huff != 0) {
294 here.op = (unsigned char)64;
295 here.bits = (unsigned char)(len - drop
296 here.val = (unsigned short)0;
297 next[huff] = here;
298 }
299
300 /* set return parameters */
301 *table += used;
302 *bits = root;
303 return 0;
304 }
305