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