Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
4349 | Serge | 1 | /* inftrees.c -- generate Huffman trees for efficient decoding |
2 | * Copyright (C) 1995-2002 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 | #if !defined(BUILDFIXED) && !defined(STDC) |
||
10 | # define BUILDFIXED /* non ANSI compilers may not accept inffixed.h */ |
||
11 | #endif |
||
12 | |||
13 | |||
14 | #if 0 |
||
15 | local const char inflate_copyright[] = |
||
16 | " inflate 1.1.4 Copyright 1995-2002 Mark Adler "; |
||
17 | #endif |
||
18 | /* |
||
19 | If you use the zlib library in a product, an acknowledgment is welcome |
||
20 | in the documentation of your product. If for some reason you cannot |
||
21 | include such an acknowledgment, I would appreciate that you keep this |
||
22 | copyright string in the executable of your product. |
||
23 | */ |
||
24 | |||
25 | /* simplify the use of the inflate_huft type with some defines */ |
||
26 | #define exop word.what.Exop |
||
27 | #define bits word.what.Bits |
||
28 | |||
29 | |||
30 | local int huft_build OF(( |
||
31 | uIntf *, /* code lengths in bits */ |
||
32 | uInt, /* number of codes */ |
||
33 | uInt, /* number of "simple" codes */ |
||
34 | const uIntf *, /* list of base values for non-simple codes */ |
||
35 | const uIntf *, /* list of extra bits for non-simple codes */ |
||
36 | inflate_huft * FAR*,/* result: starting table */ |
||
37 | uIntf *, /* maximum lookup bits (returns actual) */ |
||
38 | inflate_huft *, /* space for trees */ |
||
39 | uInt *, /* hufts used in space */ |
||
40 | uIntf * )); /* space for values */ |
||
41 | |||
42 | /* Tables for deflate from PKZIP's appnote.txt. */ |
||
43 | local const uInt cplens[31] = { /* Copy lengths for literal codes 257..285 */ |
||
44 | 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, |
||
45 | 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; |
||
46 | /* see note #13 above about 258 */ |
||
47 | local const uInt cplext[31] = { /* Extra bits for literal codes 257..285 */ |
||
48 | 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, |
||
49 | 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 112, 112}; /* 112==invalid */ |
||
50 | local const uInt cpdist[30] = { /* Copy offsets for distance codes 0..29 */ |
||
51 | 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, |
||
52 | 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, |
||
53 | 8193, 12289, 16385, 24577}; |
||
54 | local const uInt cpdext[30] = { /* Extra bits for distance codes */ |
||
55 | 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, |
||
56 | 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, |
||
57 | 12, 12, 13, 13}; |
||
58 | |||
59 | /* |
||
60 | Huffman code decoding is performed using a multi-level table lookup. |
||
61 | The fastest way to decode is to simply build a lookup table whose |
||
62 | size is determined by the longest code. However, the time it takes |
||
63 | to build this table can also be a factor if the data being decoded |
||
64 | is not very long. The most common codes are necessarily the |
||
65 | shortest codes, so those codes dominate the decoding time, and hence |
||
66 | the speed. The idea is you can have a shorter table that decodes the |
||
67 | shorter, more probable codes, and then point to subsidiary tables for |
||
68 | the longer codes. The time it costs to decode the longer codes is |
||
69 | then traded against the time it takes to make longer tables. |
||
70 | |||
71 | This results of this trade are in the variables lbits and dbits |
||
72 | below. lbits is the number of bits the first level table for literal/ |
||
73 | length codes can decode in one step, and dbits is the same thing for |
||
74 | the distance codes. Subsequent tables are also less than or equal to |
||
75 | those sizes. These values may be adjusted either when all of the |
||
76 | codes are shorter than that, in which case the longest code length in |
||
77 | bits is used, or when the shortest code is *longer* than the requested |
||
78 | table size, in which case the length of the shortest code in bits is |
||
79 | used. |
||
80 | |||
81 | There are two different values for the two tables, since they code a |
||
82 | different number of possibilities each. The literal/length table |
||
83 | codes 286 possible values, or in a flat code, a little over eight |
||
84 | bits. The distance table codes 30 possible values, or a little less |
||
85 | than five bits, flat. The optimum values for speed end up being |
||
86 | about one bit more than those, so lbits is 8+1 and dbits is 5+1. |
||
87 | The optimum values may differ though from machine to machine, and |
||
88 | possibly even between compilers. Your mileage may vary. |
||
89 | */ |
||
90 | |||
91 | |||
92 | /* If BMAX needs to be larger than 16, then h and x[] should be uLong. */ |
||
93 | #define BMAX 15 /* maximum bit length of any code */ |
||
94 | |||
95 | local int huft_build( /* b, n, s, d, e, t, m, hp, hn, v) */ |
||
96 | uIntf *b, /* code lengths in bits (all assumed <= BMAX) */ |
||
97 | uInt n, /* number of codes (assumed <= 288) */ |
||
98 | uInt s, /* number of simple-valued codes (0..s-1) */ |
||
99 | const uIntf *d, /* list of base values for non-simple codes */ |
||
100 | const uIntf *e, /* list of extra bits for non-simple codes */ |
||
101 | inflate_huft * FAR *t, /* result: starting table */ |
||
102 | uIntf *m, /* maximum lookup bits, returns actual */ |
||
103 | inflate_huft *hp, /* space for trees */ |
||
104 | uInt *hn, /* hufts used in space */ |
||
105 | uIntf *v /* working area: values in order of bit length */ |
||
106 | /* Given a list of code lengths and a maximum table size, make a set of |
||
107 | tables to decode that set of codes. Return Z_OK on success, Z_BUF_ERROR |
||
108 | if the given code set is incomplete (the tables are still built in this |
||
109 | case), or Z_DATA_ERROR if the input is invalid. */ |
||
110 | ) |
||
111 | { |
||
112 | |||
113 | uInt a; /* counter for codes of length k */ |
||
114 | uInt c[BMAX+1]; /* bit length count table */ |
||
115 | uInt f; /* i repeats in table every f entries */ |
||
116 | int g; /* maximum code length */ |
||
117 | int h; /* table level */ |
||
118 | register uInt i; /* counter, current code */ |
||
119 | register uInt j; /* counter */ |
||
120 | register int k; /* number of bits in current code */ |
||
121 | int l; /* bits per table (returned in m) */ |
||
122 | uInt mask; /* (1 << w) - 1, to avoid cc -O bug on HP */ |
||
123 | register uIntf *p; /* pointer into c[], b[], or v[] */ |
||
124 | inflate_huft *q; /* points to current table */ |
||
125 | struct inflate_huft_s r; /* table entry for structure assignment */ |
||
126 | inflate_huft *u[BMAX]; /* table stack */ |
||
127 | register int w; /* bits before this table == (l * h) */ |
||
128 | uInt x[BMAX+1]; /* bit offsets, then code stack */ |
||
129 | uIntf *xp; /* pointer into x */ |
||
130 | int y; /* number of dummy codes added */ |
||
131 | uInt z; /* number of entries in current table */ |
||
132 | |||
133 | |||
134 | /* Make compiler happy */ |
||
135 | r.base = 0; |
||
136 | |||
137 | /* Generate counts for each bit length */ |
||
138 | p = c; |
||
139 | #define C0 *p++ = 0; |
||
140 | #define C2 C0 C0 C0 C0 |
||
141 | #define C4 C2 C2 C2 C2 |
||
142 | C4 /* clear c[]--assume BMAX+1 is 16 */ |
||
143 | p = b; i = n; |
||
144 | do { |
||
145 | c[*p++]++; /* assume all entries <= BMAX */ |
||
146 | } while (--i); |
||
147 | if (c[0] == n) /* null input--all zero length codes */ |
||
148 | { |
||
149 | *t = (inflate_huft *)Z_NULL; |
||
150 | *m = 0; |
||
151 | return Z_OK; |
||
152 | } |
||
153 | |||
154 | |||
155 | /* Find minimum and maximum length, bound *m by those */ |
||
156 | l = *m; |
||
157 | for (j = 1; j <= BMAX; j++) |
||
158 | if (c[j]) |
||
159 | break; |
||
160 | k = j; /* minimum code length */ |
||
161 | if ((uInt)l < j) |
||
162 | l = j; |
||
163 | for (i = BMAX; i; i--) |
||
164 | if (c[i]) |
||
165 | break; |
||
166 | g = i; /* maximum code length */ |
||
167 | if ((uInt)l > i) |
||
168 | l = i; |
||
169 | *m = l; |
||
170 | |||
171 | |||
172 | /* Adjust last length count to fill out codes, if needed */ |
||
173 | for (y = 1 << j; j < i; j++, y <<= 1) |
||
174 | if ((y -= c[j]) < 0) |
||
175 | return Z_DATA_ERROR; |
||
176 | if ((y -= c[i]) < 0) |
||
177 | return Z_DATA_ERROR; |
||
178 | c[i] += y; |
||
179 | |||
180 | |||
181 | /* Generate starting offsets into the value table for each length */ |
||
182 | x[1] = j = 0; |
||
183 | p = c + 1; xp = x + 2; |
||
184 | while (--i) { /* note that i == g from above */ |
||
185 | *xp++ = (j += *p++); |
||
186 | } |
||
187 | |||
188 | |||
189 | /* Make a table of values in order of bit lengths */ |
||
190 | p = b; i = 0; |
||
191 | do { |
||
192 | if ((j = *p++) != 0) |
||
193 | v[x[j]++] = i; |
||
194 | } while (++i < n); |
||
195 | n = x[g]; /* set n to length of v */ |
||
196 | |||
197 | |||
198 | /* Generate the Huffman codes and for each, make the table entries */ |
||
199 | x[0] = i = 0; /* first Huffman code is zero */ |
||
200 | p = v; /* grab values in bit order */ |
||
201 | h = -1; /* no tables yet--level -1 */ |
||
202 | w = -l; /* bits decoded == (l * h) */ |
||
203 | u[0] = (inflate_huft *)Z_NULL; /* just to keep compilers happy */ |
||
204 | q = (inflate_huft *)Z_NULL; /* ditto */ |
||
205 | z = 0; /* ditto */ |
||
206 | |||
207 | /* go through the bit lengths (k already is bits in shortest code) */ |
||
208 | for (; k <= g; k++) |
||
209 | { |
||
210 | a = c[k]; |
||
211 | while (a--) |
||
212 | { |
||
213 | /* here i is the Huffman code of length k bits for value *p */ |
||
214 | /* make tables up to required level */ |
||
215 | while (k > w + l) |
||
216 | { |
||
217 | h++; |
||
218 | w += l; /* previous table always l bits */ |
||
219 | |||
220 | /* compute minimum size table less than or equal to l bits */ |
||
221 | z = g - w; |
||
222 | z = z > (uInt)l ? (uInt)l : z; /* table size upper limit */ |
||
223 | if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */ |
||
224 | { /* too few codes for k-w bit table */ |
||
225 | f -= a + 1; /* deduct codes from patterns left */ |
||
226 | xp = c + k; |
||
227 | if (j < z) |
||
228 | while (++j < z) /* try smaller tables up to z bits */ |
||
229 | { |
||
230 | if ((f <<= 1) <= *++xp) |
||
231 | break; /* enough codes to use up j bits */ |
||
232 | f -= *xp; /* else deduct codes from patterns */ |
||
233 | } |
||
234 | } |
||
235 | z = 1 << j; /* table entries for j-bit table */ |
||
236 | |||
237 | /* allocate new table */ |
||
238 | if (*hn + z > MANY) /* (note: doesn't matter for fixed) */ |
||
239 | return Z_DATA_ERROR; /* overflow of MANY */ |
||
240 | u[h] = q = hp + *hn; |
||
241 | *hn += z; |
||
242 | |||
243 | /* connect to last table, if there is one */ |
||
244 | if (h) |
||
245 | { |
||
246 | x[h] = i; /* save pattern for backing up */ |
||
247 | r.bits = (Byte)l; /* bits to dump before this table */ |
||
248 | r.exop = (Byte)j; /* bits in this table */ |
||
249 | j = i >> (w - l); |
||
250 | r.base = (uInt)(q - u[h-1] - j); /* offset to this table */ |
||
251 | u[h-1][j] = r; /* connect to last table */ |
||
252 | } |
||
253 | else |
||
254 | *t = q; /* first table is returned result */ |
||
255 | } |
||
256 | |||
257 | /* set up table entry in r */ |
||
258 | r.bits = (Byte)(k - w); |
||
259 | if (p >= v + n) |
||
260 | r.exop = 128 + 64; /* out of values--invalid code */ |
||
261 | else if (*p < s) |
||
262 | { |
||
263 | r.exop = (Byte)(*p < 256 ? 0 : 32 + 64); /* 256 is end-of-block */ |
||
264 | r.base = *p++; /* simple code is just the value */ |
||
265 | } |
||
266 | else |
||
267 | { |
||
268 | r.exop = (Byte)(e[*p - s] + 16 + 64);/* non-simple--look up in lists */ |
||
269 | r.base = d[*p++ - s]; |
||
270 | } |
||
271 | |||
272 | /* fill code-like entries with r */ |
||
273 | f = 1 << (k - w); |
||
274 | for (j = i >> w; j < z; j += f) |
||
275 | q[j] = r; |
||
276 | |||
277 | /* backwards increment the k-bit code i */ |
||
278 | for (j = 1 << (k - 1); i & j; j >>= 1) |
||
279 | i ^= j; |
||
280 | i ^= j; |
||
281 | |||
282 | /* backup over finished tables */ |
||
283 | mask = (1 << w) - 1; /* needed on HP, cc -O bug */ |
||
284 | while ((i & mask) != x[h]) |
||
285 | { |
||
286 | h--; /* don't need to update q */ |
||
287 | w -= l; |
||
288 | mask = (1 << w) - 1; |
||
289 | } |
||
290 | } |
||
291 | } |
||
292 | |||
293 | |||
294 | /* Return Z_BUF_ERROR if we were given an incomplete table */ |
||
295 | return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK; |
||
296 | } |
||
297 | |||
298 | |||
299 | local int inflate_trees_bits( /* c, bb, tb, hp, z) */ |
||
300 | uIntf *c, /* 19 code lengths */ |
||
301 | uIntf *bb, /* bits tree desired/actual depth */ |
||
302 | inflate_huft * FAR *tb, /* bits tree result */ |
||
303 | inflate_huft *hp, /* space for trees */ |
||
304 | z_streamp z /* for messages */ |
||
305 | ) |
||
306 | { |
||
307 | int r; |
||
308 | uInt hn = 0; /* hufts used in space */ |
||
309 | uIntf *v; /* work area for huft_build */ |
||
310 | |||
311 | if ((v = (uIntf*)ZALLOC(z, 19, sizeof(uInt))) == Z_NULL) |
||
312 | return Z_MEM_ERROR; |
||
313 | r = huft_build(c, 19, 19, (uIntf*)Z_NULL, (uIntf*)Z_NULL, |
||
314 | tb, bb, hp, &hn, v); |
||
315 | if (r == Z_DATA_ERROR) |
||
316 | z->msg = (char*)"oversubscribed dynamic bit lengths tree"; |
||
317 | else if (r == Z_BUF_ERROR || *bb == 0) |
||
318 | { |
||
319 | z->msg = (char*)"incomplete dynamic bit lengths tree"; |
||
320 | r = Z_DATA_ERROR; |
||
321 | } |
||
322 | ZFREE(z, v); |
||
323 | return r; |
||
324 | } |
||
325 | |||
326 | |||
327 | local int inflate_trees_dynamic( /* nl, nd, c, bl, bd, tl, td, hp, z) */ |
||
328 | uInt nl, /* number of literal/length codes */ |
||
329 | uInt nd, /* number of distance codes */ |
||
330 | uIntf *c, /* that many (total) code lengths */ |
||
331 | uIntf *bl, /* literal desired/actual bit depth */ |
||
332 | uIntf *bd, /* distance desired/actual bit depth */ |
||
333 | inflate_huft * FAR *tl, /* literal/length tree result */ |
||
334 | inflate_huft * FAR *td, /* distance tree result */ |
||
335 | inflate_huft *hp, /* space for trees */ |
||
336 | z_streamp z /* for messages */ |
||
337 | ) |
||
338 | { |
||
339 | int r; |
||
340 | uInt hn = 0; /* hufts used in space */ |
||
341 | uIntf *v; /* work area for huft_build */ |
||
342 | |||
343 | /* allocate work area */ |
||
344 | if ((v = (uIntf*)ZALLOC(z, 288, sizeof(uInt))) == Z_NULL) |
||
345 | return Z_MEM_ERROR; |
||
346 | |||
347 | /* build literal/length tree */ |
||
348 | r = huft_build(c, nl, 257, cplens, cplext, tl, bl, hp, &hn, v); |
||
349 | if (r != Z_OK || *bl == 0) |
||
350 | { |
||
351 | if (r == Z_DATA_ERROR) |
||
352 | z->msg = (char*)"oversubscribed literal/length tree"; |
||
353 | else if (r != Z_MEM_ERROR) |
||
354 | { |
||
355 | z->msg = (char*)"incomplete literal/length tree"; |
||
356 | r = Z_DATA_ERROR; |
||
357 | } |
||
358 | ZFREE(z, v); |
||
359 | return r; |
||
360 | } |
||
361 | |||
362 | /* build distance tree */ |
||
363 | r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, hp, &hn, v); |
||
364 | if (r != Z_OK || (*bd == 0 && nl > 257)) |
||
365 | { |
||
366 | if (r == Z_DATA_ERROR) |
||
367 | z->msg = (char*)"oversubscribed distance tree"; |
||
368 | else if (r == Z_BUF_ERROR) { |
||
369 | #if 0 |
||
370 | { |
||
371 | #endif |
||
372 | #ifdef PKZIP_BUG_WORKAROUND |
||
373 | r = Z_OK; |
||
374 | } |
||
375 | #else |
||
376 | z->msg = (char*)"incomplete distance tree"; |
||
377 | r = Z_DATA_ERROR; |
||
378 | } |
||
379 | else if (r != Z_MEM_ERROR) |
||
380 | { |
||
381 | z->msg = (char*)"empty distance tree with lengths"; |
||
382 | r = Z_DATA_ERROR; |
||
383 | } |
||
384 | ZFREE(z, v); |
||
385 | return r; |
||
386 | #endif |
||
387 | } |
||
388 | |||
389 | /* done */ |
||
390 | ZFREE(z, v); |
||
391 | return Z_OK; |
||
392 | } |
||
393 | |||
394 | |||
395 | /* build fixed tables only once--keep them here */ |
||
396 | #ifdef BUILDFIXED |
||
397 | local int fixed_built = 0; |
||
398 | #define FIXEDH 544 /* number of hufts used by fixed tables */ |
||
399 | local inflate_huft fixed_mem[FIXEDH]; |
||
400 | local uInt fixed_bl; |
||
401 | local uInt fixed_bd; |
||
402 | local inflate_huft *fixed_tl; |
||
403 | local inflate_huft *fixed_td; |
||
404 | #else |
||
405 | #include "inffixed.h" |
||
406 | #endif |
||
407 | |||
408 | |||
409 | local int inflate_trees_fixed( /* bl, bd, tl, td, z) */ |
||
410 | uIntf *bl, /* literal desired/actual bit depth */ |
||
411 | uIntf *bd, /* distance desired/actual bit depth */ |
||
412 | const inflate_huft * FAR *tl, /* literal/length tree result */ |
||
413 | const inflate_huft * FAR *td, /* distance tree result */ |
||
414 | z_streamp z /* for memory allocation */ |
||
415 | ) |
||
416 | { |
||
417 | #ifdef BUILDFIXED |
||
418 | /* build fixed tables if not already */ |
||
419 | if (!fixed_built) |
||
420 | { |
||
421 | int k; /* temporary variable */ |
||
422 | uInt f = 0; /* number of hufts used in fixed_mem */ |
||
423 | uIntf *c; /* length list for huft_build */ |
||
424 | uIntf *v; /* work area for huft_build */ |
||
425 | |||
426 | /* allocate memory */ |
||
427 | if ((c = (uIntf*)ZALLOC(z, 288, sizeof(uInt))) == Z_NULL) |
||
428 | return Z_MEM_ERROR; |
||
429 | if ((v = (uIntf*)ZALLOC(z, 288, sizeof(uInt))) == Z_NULL) |
||
430 | { |
||
431 | ZFREE(z, c); |
||
432 | return Z_MEM_ERROR; |
||
433 | } |
||
434 | |||
435 | /* literal table */ |
||
436 | for (k = 0; k < 144; k++) |
||
437 | c[k] = 8; |
||
438 | for (; k < 256; k++) |
||
439 | c[k] = 9; |
||
440 | for (; k < 280; k++) |
||
441 | c[k] = 7; |
||
442 | for (; k < 288; k++) |
||
443 | c[k] = 8; |
||
444 | fixed_bl = 9; |
||
445 | huft_build(c, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl, |
||
446 | fixed_mem, &f, v); |
||
447 | |||
448 | /* distance table */ |
||
449 | for (k = 0; k < 30; k++) |
||
450 | c[k] = 5; |
||
451 | fixed_bd = 5; |
||
452 | huft_build(c, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd, |
||
453 | fixed_mem, &f, v); |
||
454 | |||
455 | /* done */ |
||
456 | ZFREE(z, v); |
||
457 | ZFREE(z, c); |
||
458 | fixed_built = 1; |
||
459 | } |
||
460 | #else |
||
461 | FT_UNUSED(z); |
||
462 | #endif |
||
463 | *bl = fixed_bl; |
||
464 | *bd = fixed_bd; |
||
465 | *tl = fixed_tl; |
||
466 | *td = fixed_td; |
||
467 | return Z_OK; |
||
468 | }>>>>>><>><>><>>><>>>><>=>=><=>>>><>=>>>>=><=>>><>>=>=>><>=>=> |