Mercurial > flash_v2

comparison packages/services/compress/zlib/current/src/inftrees.c @ 1651:91a37e2314f4

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Upgrade to zlib-1.2.1
author gthomas
date Mon, 24 May 2004 19:33:34 +0000
parents c92d7972c02c
children
comparison
equal deleted inserted replaced
1650:0e6a7d89dd0e 1651:91a37e2314f4
1 /* inftrees.c -- generate Huffman trees for efficient decoding 1 /* inftrees.c -- generate Huffman trees for efficient decoding
2 * Copyright (C) 1995-2002 Mark Adler 2 * Copyright (C) 1995-2003 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h 3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */ 4 */
5 5
6 #include "zutil.h" 6 #include "zutil.h"
7 #include "inftrees.h" 7 #include "inftrees.h"
8 8
9 #if !defined(BUILDFIXED) && !defined(STDC) 9 #define MAXBITS 15
10 # define BUILDFIXED /* non ANSI compilers may not accept inffixed.h */
11 #endif
12 10
13 const char inflate_copyright[] = 11 const char inflate_copyright[] =
14 " inflate 1.1.4 Copyright 1995-2002 Mark Adler "; 12 " inflate 1.2.1 Copyright 1995-2003 Mark Adler ";
15 /* 13 /*
16 If you use the zlib library in a product, an acknowledgment is welcome 14 If you use the zlib library in a product, an acknowledgment is welcome
17 in the documentation of your product. If for some reason you cannot 15 in the documentation of your product. If for some reason you cannot
18 include such an acknowledgment, I would appreciate that you keep this 16 include such an acknowledgment, I would appreciate that you keep this
19 copyright string in the executable of your product. 17 copyright string in the executable of your product.
20 */ 18 */
21 struct internal_state {int dummy;}; /* for buggy compilers */ 19
22 20 /*
23 /* simplify the use of the inflate_huft type with some defines */ 21 Build a set of tables to decode the provided canonical Huffman code.
24 #define exop word.what.Exop 22 The code lengths are lens[0..codes-1]. The result starts at *table,
25 #define bits word.what.Bits 23 whose indices are 0..2^bits-1. work is a writable array of at least
26 24 lens shorts, which is used as a work area. type is the type of code
27 25 to be generated, CODES, LENS, or DISTS. On return, zero is success,
28 local int huft_build OF(( 26 -1 is an invalid code, and +1 means that ENOUGH isn't enough. table
29 uIntf *, /* code lengths in bits */ 27 on return points to the next available entry's address. bits is the
30 uInt, /* number of codes */ 28 requested root table index bits, and on return it is the actual root
31 uInt, /* number of "simple" codes */ 29 table index bits. It will differ if the request is greater than the
32 const uIntf *, /* list of base values for non-simple codes */ 30 longest code or if it is less than the shortest code.
33 const uIntf *, /* list of extra bits for non-simple codes */ 31 */
34 inflate_huft * FAR*,/* result: starting table */ 32 int inflate_table(type, lens, codes, table, bits, work)
35 uIntf *, /* maximum lookup bits (returns actual) */ 33 codetype type;
36 inflate_huft *, /* space for trees */ 34 unsigned short FAR *lens;
37 uInt *, /* hufts used in space */ 35 unsigned codes;
38 uIntf * )); /* space for values */ 36 code FAR * FAR *table;
39 37 unsigned FAR *bits;
40 /* Tables for deflate from PKZIP's appnote.txt. */ 38 unsigned short FAR *work;
41 local const uInt cplens[31] = { /* Copy lengths for literal codes 257..285 */ 39 {
40 unsigned len; /* a code's length in bits */
41 unsigned sym; /* index of code symbols */
42 unsigned min, max; /* minimum and maximum code lengths */
43 unsigned root; /* number of index bits for root table */
44 unsigned curr; /* number of index bits for current table */
45 unsigned drop; /* code bits to drop for sub-table */
46 int left; /* number of prefix codes available */
47 unsigned used; /* code entries in table used */
48 unsigned huff; /* Huffman code */
49 unsigned incr; /* for incrementing code, index */
50 unsigned fill; /* index for replicating entries */
51 unsigned low; /* low bits for current root entry */
52 unsigned mask; /* mask for low root bits */
53 code this; /* table entry for duplication */
54 code FAR *next; /* next available space in table */
55 const unsigned short FAR *base; /* base value table to use */
56 const unsigned short FAR *extra; /* extra bits table to use */
57 int end; /* use base and extra for symbol > end */
58 unsigned short count[MAXBITS+1]; /* number of codes of each length */
59 unsigned short offs[MAXBITS+1]; /* offsets in table for each length */
60 static const unsigned short lbase[31] = { /* Length codes 257..285 base */
42 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 61 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
43 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; 62 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
44 /* see note #13 above about 258 */ 63 static const unsigned short lext[31] = { /* Length codes 257..285 extra */
45 local const uInt cplext[31] = { /* Extra bits for literal codes 257..285 */ 64 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18,
46 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 65 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 76, 66};
47 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 112, 112}; /* 112==invalid */ 66 static const unsigned short dbase[32] = { /* Distance codes 0..29 base */
48 local const uInt cpdist[30] = { /* Copy offsets for distance codes 0..29 */
49 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 67 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
50 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 68 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
51 8193, 12289, 16385, 24577}; 69 8193, 12289, 16385, 24577, 0, 0};
52 local const uInt cpdext[30] = { /* Extra bits for distance codes */ 70 static const unsigned short dext[32] = { /* Distance codes 0..29 extra */
53 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 71 16, 16, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22,
54 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 72 23, 23, 24, 24, 25, 25, 26, 26, 27, 27,
55 12, 12, 13, 13}; 73 28, 28, 29, 29, 64, 64};
56 74
57 /* 75 /*
58 Huffman code decoding is performed using a multi-level table lookup. 76 Process a set of code lengths to create a canonical Huffman code. The
59 The fastest way to decode is to simply build a lookup table whose 77 code lengths are lens[0..codes-1]. Each length corresponds to the
60 size is determined by the longest code. However, the time it takes 78 symbols 0..codes-1. The Huffman code is generated by first sorting the
61 to build this table can also be a factor if the data being decoded 79 symbols by length from short to long, and retaining the symbol order
62 is not very long. The most common codes are necessarily the 80 for codes with equal lengths. Then the code starts with all zero bits
63 shortest codes, so those codes dominate the decoding time, and hence 81 for the first code of the shortest length, and the codes are integer
64 the speed. The idea is you can have a shorter table that decodes the 82 increments for the same length, and zeros are appended as the length
65 shorter, more probable codes, and then point to subsidiary tables for 83 increases. For the deflate format, these bits are stored backwards
66 the longer codes. The time it costs to decode the longer codes is 84 from their more natural integer increment ordering, and so when the
67 then traded against the time it takes to make longer tables. 85 decoding tables are built in the large loop below, the integer codes
68 86 are incremented backwards.
69 This results of this trade are in the variables lbits and dbits 87
70 below. lbits is the number of bits the first level table for literal/ 88 This routine assumes, but does not check, that all of the entries in
71 length codes can decode in one step, and dbits is the same thing for 89 lens[] are in the range 0..MAXBITS. The caller must assure this.
72 the distance codes. Subsequent tables are also less than or equal to 90 1..MAXBITS is interpreted as that code length. zero means that that
73 those sizes. These values may be adjusted either when all of the 91 symbol does not occur in this code.
74 codes are shorter than that, in which case the longest code length in 92
75 bits is used, or when the shortest code is *longer* than the requested 93 The codes are sorted by computing a count of codes for each length,
76 table size, in which case the length of the shortest code in bits is 94 creating from that a table of starting indices for each length in the
77 used. 95 sorted table, and then entering the symbols in order in the sorted
78 96 table. The sorted table is work[], with that space being provided by
79 There are two different values for the two tables, since they code a 97 the caller.
80 different number of possibilities each. The literal/length table 98
81 codes 286 possible values, or in a flat code, a little over eight 99 The length counts are used for other purposes as well, i.e. finding
82 bits. The distance table codes 30 possible values, or a little less 100 the minimum and maximum length codes, determining if there are any
83 than five bits, flat. The optimum values for speed end up being 101 codes at all, checking for a valid set of lengths, and looking ahead
84 about one bit more than those, so lbits is 8+1 and dbits is 5+1. 102 at length counts to determine sub-table sizes when building the
85 The optimum values may differ though from machine to machine, and 103 decoding tables.
86 possibly even between compilers. Your mileage may vary. 104 */
87 */ 105
88 106 /* accumulate lengths for codes (assumes lens[] all in 0..MAXBITS) */
89 107 for (len = 0; len <= MAXBITS; len++)
90 /* If BMAX needs to be larger than 16, then h and x[] should be uLong. */ 108 count[len] = 0;
91 #define BMAX 15 /* maximum bit length of any code */ 109 for (sym = 0; sym < codes; sym++)
92 110 count[lens[sym]]++;
93 local int huft_build(b, n, s, d, e, t, m, hp, hn, v) 111
94 uIntf *b; /* code lengths in bits (all assumed <= BMAX) */ 112 /* bound code lengths, force root to be within code lengths */
95 uInt n; /* number of codes (assumed <= 288) */ 113 root = *bits;
96 uInt s; /* number of simple-valued codes (0..s-1) */ 114 for (max = MAXBITS; max >= 1; max--)
97 const uIntf *d; /* list of base values for non-simple codes */ 115 if (count[max] != 0) break;
98 const uIntf *e; /* list of extra bits for non-simple codes */ 116 if (root > max) root = max;
99 inflate_huft * FAR *t; /* result: starting table */ 117 if (max == 0) return -1; /* no codes! */
100 uIntf *m; /* maximum lookup bits, returns actual */ 118 for (min = 1; min <= MAXBITS; min++)
101 inflate_huft *hp; /* space for trees */ 119 if (count[min] != 0) break;
102 uInt *hn; /* hufts used in space */ 120 if (root < min) root = min;
103 uIntf *v; /* working area: values in order of bit length */ 121
104 /* Given a list of code lengths and a maximum table size, make a set of 122 /* check for an over-subscribed or incomplete set of lengths */
105 tables to decode that set of codes. Return Z_OK on success, Z_BUF_ERROR 123 left = 1;
106 if the given code set is incomplete (the tables are still built in this 124 for (len = 1; len <= MAXBITS; len++) {
107 case), or Z_DATA_ERROR if the input is invalid. */ 125 left <<= 1;
108 { 126 left -= count[len];
109 127 if (left < 0) return -1; /* over-subscribed */
110 uInt a; /* counter for codes of length k */ 128 }
111 uInt c[BMAX+1]; /* bit length count table */ 129 if (left > 0 && (type == CODES || (codes - count[0] != 1)))
112 uInt f; /* i repeats in table every f entries */ 130 return -1; /* incomplete set */
113 int g; /* maximum code length */ 131
114 int h; /* table level */ 132 /* generate offsets into symbol table for each length for sorting */
115 register uInt i; /* counter, current code */ 133 offs[1] = 0;
116 register uInt j; /* counter */ 134 for (len = 1; len < MAXBITS; len++)
117 register int k; /* number of bits in current code */ 135 offs[len + 1] = offs[len] + count[len];
118 int l; /* bits per table (returned in m) */ 136
119 uInt mask; /* (1 << w) - 1, to avoid cc -O bug on HP */ 137 /* sort symbols by length, by symbol order within each length */
120 register uIntf *p; /* pointer into c[], b[], or v[] */ 138 for (sym = 0; sym < codes; sym++)
121 inflate_huft *q; /* points to current table */ 139 if (lens[sym] != 0) work[offs[lens[sym]]++] = (unsigned short)sym;
122 struct inflate_huft_s r; /* table entry for structure assignment */ 140
123 inflate_huft *u[BMAX]; /* table stack */ 141 /*
124 register int w; /* bits before this table == (l * h) */ 142 Create and fill in decoding tables. In this loop, the table being
125 uInt x[BMAX+1]; /* bit offsets, then code stack */ 143 filled is at next and has curr index bits. The code being used is huff
126 uIntf *xp; /* pointer into x */ 144 with length len. That code is converted to an index by dropping drop
127 int y; /* number of dummy codes added */ 145 bits off of the bottom. For codes where len is less than drop + curr,
128 uInt z; /* number of entries in current table */ 146 those top drop + curr - len bits are incremented through all values to
129 147 fill the table with replicated entries.
130 148
131 /* Generate counts for each bit length */ 149 root is the number of index bits for the root table. When len exceeds
132 p = c; 150 root, sub-tables are created pointed to by the root entry with an index
133 #define C0 *p++ = 0; 151 of the low root bits of huff. This is saved in low to check for when a
134 #define C2 C0 C0 C0 C0 152 new sub-table should be started. drop is zero when the root table is
135 #define C4 C2 C2 C2 C2 153 being filled, and drop is root when sub-tables are being filled.
136 C4 /* clear c[]--assume BMAX+1 is 16 */ 154
137 p = b; i = n; 155 When a new sub-table is needed, it is necessary to look ahead in the
138 do { 156 code lengths to determine what size sub-table is needed. The length
139 c[*p++]++; /* assume all entries <= BMAX */ 157 counts are used for this, and so count[] is decremented as codes are
140 } while (--i); 158 entered in the tables.
141 if (c[0] == n) /* null input--all zero length codes */ 159
142 { 160 used keeps track of how many table entries have been allocated from the
143 *t = (inflate_huft *)Z_NULL; 161 provided *table space. It is checked when a LENS table is being made
144 *m = 0; 162 against the space in *table, ENOUGH, minus the maximum space needed by
145 return Z_OK; 163 the worst case distance code, MAXD. This should never happen, but the
146 } 164 sufficiency of ENOUGH has not been proven exhaustively, hence the check.
147 165 This assumes that when type == LENS, bits == 9.
148 166
149 /* Find minimum and maximum length, bound *m by those */ 167 sym increments through all symbols, and the loop terminates when
150 l = *m; 168 all codes of length max, i.e. all codes, have been processed. This
151 for (j = 1; j <= BMAX; j++) 169 routine permits incomplete codes, so another loop after this one fills
152 if (c[j]) 170 in the rest of the decoding tables with invalid code markers.
153 break; 171 */
154 k = j; /* minimum code length */ 172
155 if ((uInt)l < j) 173 /* set up for code type */
156 l = j; 174 switch (type) {
157 for (i = BMAX; i; i--) 175 case CODES:
158 if (c[i]) 176 base = extra = work; /* dummy value--not used */
159 break; 177 end = 19;
160 g = i; /* maximum code length */ 178 break;
161 if ((uInt)l > i) 179 case LENS:
162 l = i; 180 base = lbase;
163 *m = l; 181 base -= 257;
164 182 extra = lext;
165 183 extra -= 257;
166 /* Adjust last length count to fill out codes, if needed */ 184 end = 256;
167 for (y = 1 << j; j < i; j++, y <<= 1) 185 break;
168 if ((y -= c[j]) < 0) 186 default: /* DISTS */
169 return Z_DATA_ERROR; 187 base = dbase;
170 if ((y -= c[i]) < 0) 188 extra = dext;
171 return Z_DATA_ERROR; 189 end = -1;
172 c[i] += y; 190 }
173 191
174 192 /* initialize state for loop */
175 /* Generate starting offsets into the value table for each length */ 193 huff = 0; /* starting code */
176 x[1] = j = 0; 194 sym = 0; /* starting code symbol */
177 p = c + 1; xp = x + 2; 195 len = min; /* starting code length */
178 while (--i) { /* note that i == g from above */ 196 next = *table; /* current table to fill in */
179 *xp++ = (j += *p++); 197 curr = root; /* current table index bits */
180 } 198 drop = 0; /* current bits to drop from code for index */
181 199 low = (unsigned)(-1); /* trigger new sub-table when len > root */
182 200 used = 1U << root; /* use root table entries */
183 /* Make a table of values in order of bit lengths */ 201 mask = used - 1; /* mask for comparing low */
184 p = b; i = 0; 202
185 do { 203 /* check available table space */
186 if ((j = *p++) != 0) 204 if (type == LENS && used >= ENOUGH - MAXD)
187 v[x[j]++] = i; 205 return 1;
188 } while (++i < n); 206
189 n = x[g]; /* set n to length of v */ 207 /* process all codes and make table entries */
190 208 for (;;) {
191 209 /* create table entry */
192 /* Generate the Huffman codes and for each, make the table entries */ 210 this.bits = (unsigned char)(len - drop);
193 x[0] = i = 0; /* first Huffman code is zero */ 211 if ((int)(work[sym]) < end) {
194 p = v; /* grab values in bit order */ 212 this.op = (unsigned char)0;
195 h = -1; /* no tables yet--level -1 */ 213 this.val = work[sym];
196 w = -l; /* bits decoded == (l * h) */ 214 }
197 u[0] = (inflate_huft *)Z_NULL; /* just to keep compilers happy */ 215 else if ((int)(work[sym]) > end) {
198 q = (inflate_huft *)Z_NULL; /* ditto */ 216 this.op = (unsigned char)(extra[work[sym]]);
199 z = 0; /* ditto */ 217 this.val = base[work[sym]];
200 218 }
201 /* go through the bit lengths (k already is bits in shortest code) */ 219 else {
202 for (; k <= g; k++) 220 this.op = (unsigned char)(32 + 64); /* end of block */
203 { 221 this.val = 0;
204 a = c[k]; 222 }
205 while (a--) 223
206 { 224 /* replicate for those indices with low len bits equal to huff */
207 /* here i is the Huffman code of length k bits for value *p */ 225 incr = 1U << (len - drop);
208 /* make tables up to required level */ 226 fill = 1U << curr;
209 while (k > w + l) 227 do {
210 { 228 fill -= incr;
211 h++; 229 next[(huff >> drop) + fill] = this;
212 w += l; /* previous table always l bits */ 230 } while (fill != 0);
213 231
214 /* compute minimum size table less than or equal to l bits */ 232 /* backwards increment the len-bit code huff */
215 z = g - w; 233 incr = 1U << (len - 1);
216 z = z > (uInt)l ? l : z; /* table size upper limit */ 234 while (huff & incr)
217 if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */ 235 incr >>= 1;
218 { /* too few codes for k-w bit table */ 236 if (incr != 0) {
219 f -= a + 1; /* deduct codes from patterns left */ 237 huff &= incr - 1;
220 xp = c + k; 238 huff += incr;
221 if (j < z) 239 }
222 while (++j < z) /* try smaller tables up to z bits */ 240 else
223 { 241 huff = 0;
224 if ((f <<= 1) <= *++xp) 242
225 break; /* enough codes to use up j bits */ 243 /* go to next symbol, update count, len */
226 f -= *xp; /* else deduct codes from patterns */ 244 sym++;
245 if (--(count[len]) == 0) {
246 if (len == max) break;
247 len = lens[work[sym]];
248 }
249
250 /* create new sub-table if needed */
251 if (len > root && (huff & mask) != low) {
252 /* if first time, transition to sub-tables */
253 if (drop == 0)
254 drop = root;
255
256 /* increment past last table */
257 next += 1U << curr;
258
259 /* determine length of next table */
260 curr = len - drop;
261 left = (int)(1 << curr);
262 while (curr + drop < max) {
263 left -= count[curr + drop];
264 if (left <= 0) break;
265 curr++;
266 left <<= 1;
227 } 267 }
228 } 268
229 z = 1 << j; /* table entries for j-bit table */ 269 /* check for enough space */
230 270 used += 1U << curr;
231 /* allocate new table */ 271 if (type == LENS && used >= ENOUGH - MAXD)
232 if (*hn + z > MANY) /* (note: doesn't matter for fixed) */ 272 return 1;
233 return Z_DATA_ERROR; /* overflow of MANY */ 273
234 u[h] = q = hp + *hn; 274 /* point entry in root table to sub-table */
235 *hn += z; 275 low = huff & mask;
236 276 (*table)[low].op = (unsigned char)curr;
237 /* connect to last table, if there is one */ 277 (*table)[low].bits = (unsigned char)root;
238 if (h) 278 (*table)[low].val = (unsigned short)(next - *table);
239 { 279 }
240 x[h] = i; /* save pattern for backing up */ 280 }
241 r.bits = (Byte)l; /* bits to dump before this table */ 281
242 r.exop = (Byte)j; /* bits in this table */ 282 /*
243 j = i >> (w - l); 283 Fill in rest of table for incomplete codes. This loop is similar to the
244 r.base = (uInt)(q - u[h-1] - j); /* offset to this table */ 284 loop above in incrementing huff for table indices. It is assumed that
245 u[h-1][j] = r; /* connect to last table */ 285 len is equal to curr + drop, so there is no loop needed to increment
286 through high index bits. When the current sub-table is filled, the loop
287 drops back to the root table to fill in any remaining entries there.
288 */
289 this.op = (unsigned char)64; /* invalid code marker */
290 this.bits = (unsigned char)(len - drop);
291 this.val = (unsigned short)0;
292 while (huff != 0) {
293 /* when done with sub-table, drop back to root table */
294 if (drop != 0 && (huff & mask) != low) {
295 drop = 0;
296 len = root;
297 next = *table;
298 curr = root;
299 this.bits = (unsigned char)len;
300 }
301
302 /* put invalid code marker in table */
303 next[huff >> drop] = this;
304
305 /* backwards increment the len-bit code huff */
306 incr = 1U << (len - 1);
307 while (huff & incr)
308 incr >>= 1;
309 if (incr != 0) {
310 huff &= incr - 1;
311 huff += incr;
246 } 312 }
247 else 313 else
248 *t = q; /* first table is returned result */ 314 huff = 0;
249 }
250
251 /* set up table entry in r */
252 r.bits = (Byte)(k - w);
253 if (p >= v + n)
254 r.exop = 128 + 64; /* out of values--invalid code */
255 else if (*p < s)
256 {
257 r.exop = (Byte)(*p < 256 ? 0 : 32 + 64); /* 256 is end-of-block */
258 r.base = *p++; /* simple code is just the value */
259 }
260 else
261 {
262 r.exop = (Byte)(e[*p - s] + 16 + 64);/* non-simple--look up in lists */
263 r.base = d[*p++ - s];
264 }
265
266 /* fill code-like entries with r */
267 f = 1 << (k - w);
268 for (j = i >> w; j < z; j += f)
269 q[j] = r;
270
271 /* backwards increment the k-bit code i */
272 for (j = 1 << (k - 1); i & j; j >>= 1)
273 i ^= j;
274 i ^= j;
275
276 /* backup over finished tables */
277 mask = (1 << w) - 1; /* needed on HP, cc -O bug */
278 while ((i & mask) != x[h])
279 {
280 h--; /* don't need to update q */
281 w -= l;
282 mask = (1 << w) - 1;
283 }
284 } 315 }
285 } 316
286 317 /* set return parameters */
287 318 *table += used;
288 /* Return Z_BUF_ERROR if we were given an incomplete table */ 319 *bits = root;
289 return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK; 320 return 0;
290 } 321 }
291
292
293 int inflate_trees_bits(c, bb, tb, hp, z)
294 uIntf *c; /* 19 code lengths */
295 uIntf *bb; /* bits tree desired/actual depth */
296 inflate_huft * FAR *tb; /* bits tree result */
297 inflate_huft *hp; /* space for trees */
298 z_streamp z; /* for messages */
299 {
300 int r;
301 uInt hn = 0; /* hufts used in space */
302 uIntf *v; /* work area for huft_build */
303
304 if ((v = (uIntf*)ZALLOC(z, 19, sizeof(uInt))) == Z_NULL)
305 return Z_MEM_ERROR;
306 r = huft_build(c, 19, 19, (uIntf*)Z_NULL, (uIntf*)Z_NULL,
307 tb, bb, hp, &hn, v);
308 if (r == Z_DATA_ERROR)
309 z->msg = (char*)"oversubscribed dynamic bit lengths tree";
310 else if (r == Z_BUF_ERROR || *bb == 0)
311 {
312 z->msg = (char*)"incomplete dynamic bit lengths tree";
313 r = Z_DATA_ERROR;
314 }
315 ZFREE(z, v);
316 return r;
317 }
318
319
320 int inflate_trees_dynamic(nl, nd, c, bl, bd, tl, td, hp, z)
321 uInt nl; /* number of literal/length codes */
322 uInt nd; /* number of distance codes */
323 uIntf *c; /* that many (total) code lengths */
324 uIntf *bl; /* literal desired/actual bit depth */
325 uIntf *bd; /* distance desired/actual bit depth */
326 inflate_huft * FAR *tl; /* literal/length tree result */
327 inflate_huft * FAR *td; /* distance tree result */
328 inflate_huft *hp; /* space for trees */
329 z_streamp z; /* for messages */
330 {
331 int r;
332 uInt hn = 0; /* hufts used in space */
333 uIntf *v; /* work area for huft_build */
334
335 /* allocate work area */
336 if ((v = (uIntf*)ZALLOC(z, 288, sizeof(uInt))) == Z_NULL)
337 return Z_MEM_ERROR;
338
339 /* build literal/length tree */
340 r = huft_build(c, nl, 257, cplens, cplext, tl, bl, hp, &hn, v);
341 if (r != Z_OK || *bl == 0)
342 {
343 if (r == Z_DATA_ERROR)
344 z->msg = (char*)"oversubscribed literal/length tree";
345 else if (r != Z_MEM_ERROR)
346 {
347 z->msg = (char*)"incomplete literal/length tree";
348 r = Z_DATA_ERROR;
349 }
350 ZFREE(z, v);
351 return r;
352 }
353
354 /* build distance tree */
355 r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, hp, &hn, v);
356 if (r != Z_OK || (*bd == 0 && nl > 257))
357 {
358 if (r == Z_DATA_ERROR)
359 z->msg = (char*)"oversubscribed distance tree";
360 else if (r == Z_BUF_ERROR) {
361 #ifdef PKZIP_BUG_WORKAROUND
362 r = Z_OK;
363 }
364 #else
365 z->msg = (char*)"incomplete distance tree";
366 r = Z_DATA_ERROR;
367 }
368 else if (r != Z_MEM_ERROR)
369 {
370 z->msg = (char*)"empty distance tree with lengths";
371 r = Z_DATA_ERROR;
372 }
373 ZFREE(z, v);
374 return r;
375 #endif
376 }
377
378 /* done */
379 ZFREE(z, v);
380 return Z_OK;
381 }
382
383
384 /* build fixed tables only once--keep them here */
385 #ifdef BUILDFIXED
386 local int fixed_built = 0;
387 #define FIXEDH 544 /* number of hufts used by fixed tables */
388 local inflate_huft fixed_mem[FIXEDH];
389 local uInt fixed_bl;
390 local uInt fixed_bd;
391 local inflate_huft *fixed_tl;
392 local inflate_huft *fixed_td;
393 #else
394 #include "inffixed.h"
395 #endif
396
397
398 int inflate_trees_fixed(bl, bd, tl, td, z)
399 uIntf *bl; /* literal desired/actual bit depth */
400 uIntf *bd; /* distance desired/actual bit depth */
401 inflate_huft * FAR *tl; /* literal/length tree result */
402 inflate_huft * FAR *td; /* distance tree result */
403 z_streamp z; /* for memory allocation */
404 {
405 #ifdef BUILDFIXED
406 /* build fixed tables if not already */
407 if (!fixed_built)
408 {
409 int k; /* temporary variable */
410 uInt f = 0; /* number of hufts used in fixed_mem */
411 uIntf *c; /* length list for huft_build */
412 uIntf *v; /* work area for huft_build */
413
414 /* allocate memory */
415 if ((c = (uIntf*)ZALLOC(z, 288, sizeof(uInt))) == Z_NULL)
416 return Z_MEM_ERROR;
417 if ((v = (uIntf*)ZALLOC(z, 288, sizeof(uInt))) == Z_NULL)
418 {
419 ZFREE(z, c);
420 return Z_MEM_ERROR;
421 }
422
423 /* literal table */
424 for (k = 0; k < 144; k++)
425 c[k] = 8;
426 for (; k < 256; k++)
427 c[k] = 9;
428 for (; k < 280; k++)
429 c[k] = 7;
430 for (; k < 288; k++)
431 c[k] = 8;
432 fixed_bl = 9;
433 huft_build(c, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl,
434 fixed_mem, &f, v);
435
436 /* distance table */
437 for (k = 0; k < 30; k++)
438 c[k] = 5;
439 fixed_bd = 5;
440 huft_build(c, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd,
441 fixed_mem, &f, v);
442
443 /* done */
444 ZFREE(z, v);
445 ZFREE(z, c);
446 fixed_built = 1;
447 }
448 #endif
449 *bl = fixed_bl;
450 *bd = fixed_bd;
451 *tl = fixed_tl;
452 *td = fixed_td;
453 return Z_OK;
454 }