diff options
Diffstat (limited to 'inftrees.c')
-rw-r--r-- | inftrees.c | 160 |
1 files changed, 80 insertions, 80 deletions
@@ -16,37 +16,37 @@ struct internal_state {int dummy;}; /* for buggy compilers */ | |||
16 | 16 | ||
17 | 17 | ||
18 | local int huft_build __P(( | 18 | local int huft_build __P(( |
19 | uInt *, /* code lengths in bits */ | 19 | uInt *, /* code lengths in bits */ |
20 | uInt, /* number of codes */ | 20 | uInt, /* number of codes */ |
21 | uInt, /* number of "simple" codes */ | 21 | uInt, /* number of "simple" codes */ |
22 | uInt *, /* list of base values for non-simple codes */ | 22 | uInt *, /* list of base values for non-simple codes */ |
23 | uInt *, /* list of extra bits for non-simple codes */ | 23 | uInt *, /* list of extra bits for non-simple codes */ |
24 | inflate_huft **, /* result: starting table */ | 24 | inflate_huft **, /* result: starting table */ |
25 | uInt *, /* maximum lookup bits (returns actual) */ | 25 | uInt *, /* maximum lookup bits (returns actual) */ |
26 | z_stream *)); /* for zalloc function */ | 26 | z_stream *)); /* for zalloc function */ |
27 | 27 | ||
28 | local voidp falloc __P(( | 28 | local voidp falloc __P(( |
29 | voidp, /* opaque pointer (not used) */ | 29 | voidp, /* opaque pointer (not used) */ |
30 | uInt, /* number of items */ | 30 | uInt, /* number of items */ |
31 | uInt)); /* size of item */ | 31 | uInt)); /* size of item */ |
32 | 32 | ||
33 | local void ffree __P(( | 33 | local void ffree __P(( |
34 | voidp q, /* opaque pointer (not used) */ | 34 | voidp q, /* opaque pointer (not used) */ |
35 | voidp p)); /* what to free (not used) */ | 35 | voidp p)); /* what to free (not used) */ |
36 | 36 | ||
37 | /* Tables for deflate from PKZIP's appnote.txt. */ | 37 | /* Tables for deflate from PKZIP's appnote.txt. */ |
38 | local uInt cplens[] = { /* Copy lengths for literal codes 257..285 */ | 38 | local uInt cplens[] = { /* Copy lengths for literal codes 257..285 */ |
39 | 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, | 39 | 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, |
40 | 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; | 40 | 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; |
41 | /* actually lengths - 2; also see note #13 above about 258 */ | 41 | /* actually lengths - 2; also see note #13 above about 258 */ |
42 | local uInt cplext[] = { /* Extra bits for literal codes 257..285 */ | 42 | local uInt cplext[] = { /* Extra bits for literal codes 257..285 */ |
43 | 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, | 43 | 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, |
44 | 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 128, 128}; /* 128==invalid */ | 44 | 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 128, 128}; /* 128==invalid */ |
45 | local uInt cpdist[] = { /* Copy offsets for distance codes 0..29 */ | 45 | local uInt cpdist[] = { /* Copy offsets for distance codes 0..29 */ |
46 | 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, | 46 | 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, |
47 | 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, | 47 | 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, |
48 | 8193, 12289, 16385, 24577}; | 48 | 8193, 12289, 16385, 24577}; |
49 | local uInt cpdext[] = { /* Extra bits for distance codes */ | 49 | local uInt cpdext[] = { /* Extra bits for distance codes */ |
50 | 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, | 50 | 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, |
51 | 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, | 51 | 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, |
52 | 12, 12, 13, 13}; | 52 | 12, 12, 13, 13}; |
@@ -100,32 +100,32 @@ uInt *d; /* list of base values for non-simple codes */ | |||
100 | uInt *e; /* list of extra bits for non-simple codes */ | 100 | uInt *e; /* list of extra bits for non-simple codes */ |
101 | inflate_huft **t; /* result: starting table */ | 101 | inflate_huft **t; /* result: starting table */ |
102 | uInt *m; /* maximum lookup bits, returns actual */ | 102 | uInt *m; /* maximum lookup bits, returns actual */ |
103 | z_stream *zs; /* for zalloc function */ | 103 | z_stream *zs; /* for zalloc function */ |
104 | /* Given a list of code lengths and a maximum table size, make a set of | 104 | /* Given a list of code lengths and a maximum table size, make a set of |
105 | tables to decode that set of codes. Return Z_OK on success, Z_BUF_ERROR | 105 | tables to decode that set of codes. Return Z_OK on success, Z_BUF_ERROR |
106 | if the given code set is incomplete (the tables are still built in this | 106 | if the given code set is incomplete (the tables are still built in this |
107 | case), Z_DATA_ERROR if the input is invalid (all zero length codes or an | 107 | case), Z_DATA_ERROR if the input is invalid (all zero length codes or an |
108 | over-subscribed set of lengths), or Z_MEM_ERROR if not enough memory. */ | 108 | over-subscribed set of lengths), or Z_MEM_ERROR if not enough memory. */ |
109 | { | 109 | { |
110 | uInt a; /* counter for codes of length k */ | 110 | uInt a; /* counter for codes of length k */ |
111 | uInt c[BMAX+1]; /* bit length count table */ | 111 | uInt c[BMAX+1]; /* bit length count table */ |
112 | uInt f; /* i repeats in table every f entries */ | 112 | uInt f; /* i repeats in table every f entries */ |
113 | int g; /* maximum code length */ | 113 | int g; /* maximum code length */ |
114 | int h; /* table level */ | 114 | int h; /* table level */ |
115 | register uInt i; /* counter, current code */ | 115 | register uInt i; /* counter, current code */ |
116 | register uInt j; /* counter */ | 116 | register uInt j; /* counter */ |
117 | register int k; /* number of bits in current code */ | 117 | register int k; /* number of bits in current code */ |
118 | int l; /* bits per table (returned in m) */ | 118 | int l; /* bits per table (returned in m) */ |
119 | register uInt *p; /* pointer into c[], b[], or v[] */ | 119 | register uInt *p; /* pointer into c[], b[], or v[] */ |
120 | register inflate_huft *q; /* points to current table */ | 120 | register inflate_huft *q; /* points to current table */ |
121 | inflate_huft r; /* table entry for structure assignment */ | 121 | inflate_huft r; /* table entry for structure assignment */ |
122 | inflate_huft *u[BMAX]; /* table stack */ | 122 | inflate_huft *u[BMAX]; /* table stack */ |
123 | uInt v[N_MAX]; /* values in order of bit length */ | 123 | uInt v[N_MAX]; /* values in order of bit length */ |
124 | register int w; /* bits before this table == (l * h) */ | 124 | register int w; /* bits before this table == (l * h) */ |
125 | uInt x[BMAX+1]; /* bit offsets, then code stack */ | 125 | uInt x[BMAX+1]; /* bit offsets, then code stack */ |
126 | uInt *xp; /* pointer into x */ | 126 | uInt *xp; /* pointer into x */ |
127 | int y; /* number of dummy codes added */ | 127 | int y; /* number of dummy codes added */ |
128 | uInt z; /* number of entries in current table */ | 128 | uInt z; /* number of entries in current table */ |
129 | 129 | ||
130 | 130 | ||
131 | /* Generate counts for each bit length */ | 131 | /* Generate counts for each bit length */ |
@@ -133,7 +133,7 @@ z_stream *zs; /* for zalloc function */ | |||
133 | #define C0 *p++ = 0; | 133 | #define C0 *p++ = 0; |
134 | #define C2 C0 C0 C0 C0 | 134 | #define C2 C0 C0 C0 C0 |
135 | #define C4 C2 C2 C2 C2 | 135 | #define C4 C2 C2 C2 C2 |
136 | C4 /* clear c[]--assume BMAX+1 is 16 */ | 136 | C4 /* clear c[]--assume BMAX+1 is 16 */ |
137 | p = b; i = n; | 137 | p = b; i = n; |
138 | do { | 138 | do { |
139 | c[*p++]++; /* assume all entries <= BMAX */ | 139 | c[*p++]++; /* assume all entries <= BMAX */ |
@@ -193,8 +193,8 @@ z_stream *zs; /* for zalloc function */ | |||
193 | p = v; /* grab values in bit order */ | 193 | p = v; /* grab values in bit order */ |
194 | h = -1; /* no tables yet--level -1 */ | 194 | h = -1; /* no tables yet--level -1 */ |
195 | w = -l; /* bits decoded == (l * h) */ | 195 | w = -l; /* bits decoded == (l * h) */ |
196 | u[0] = (inflate_huft *)Z_NULL; /* just to keep compilers happy */ | 196 | u[0] = (inflate_huft *)Z_NULL; /* just to keep compilers happy */ |
197 | q = (inflate_huft *)Z_NULL; /* ditto */ | 197 | q = (inflate_huft *)Z_NULL; /* ditto */ |
198 | z = 0; /* ditto */ | 198 | z = 0; /* ditto */ |
199 | 199 | ||
200 | /* go through the bit lengths (k already is bits in shortest code) */ | 200 | /* go through the bit lengths (k already is bits in shortest code) */ |
@@ -217,25 +217,25 @@ z_stream *zs; /* for zalloc function */ | |||
217 | f -= a + 1; /* deduct codes from patterns left */ | 217 | f -= a + 1; /* deduct codes from patterns left */ |
218 | xp = c + k; | 218 | xp = c + k; |
219 | if (j < z) | 219 | if (j < z) |
220 | while (++j < z) /* try smaller tables up to z bits */ | 220 | while (++j < z) /* try smaller tables up to z bits */ |
221 | { | 221 | { |
222 | if ((f <<= 1) <= *++xp) | 222 | if ((f <<= 1) <= *++xp) |
223 | break; /* enough codes to use up j bits */ | 223 | break; /* enough codes to use up j bits */ |
224 | f -= *xp; /* else deduct codes from patterns */ | 224 | f -= *xp; /* else deduct codes from patterns */ |
225 | } | 225 | } |
226 | } | 226 | } |
227 | z = 1 << j; /* table entries for j-bit table */ | 227 | z = 1 << j; /* table entries for j-bit table */ |
228 | 228 | ||
229 | /* allocate and link in new table */ | 229 | /* allocate and link in new table */ |
230 | if ((q = (inflate_huft *)ZALLOC | 230 | if ((q = (inflate_huft *)ZALLOC |
231 | (zs,z + 1,sizeof(inflate_huft))) == Z_NULL) | 231 | (zs,z + 1,sizeof(inflate_huft))) == Z_NULL) |
232 | { | 232 | { |
233 | if (h) | 233 | if (h) |
234 | inflate_trees_free(u[0], zs); | 234 | inflate_trees_free(u[0], zs); |
235 | return Z_MEM_ERROR; /* not enough memory */ | 235 | return Z_MEM_ERROR; /* not enough memory */ |
236 | } | 236 | } |
237 | #ifdef DEBUG | 237 | #ifdef DEBUG |
238 | inflate_hufts += z + 1; | 238 | inflate_hufts += z + 1; |
239 | #endif | 239 | #endif |
240 | *t = q + 1; /* link to list for huft_free() */ | 240 | *t = q + 1; /* link to list for huft_free() */ |
241 | *(t = &(q->next)) = (inflate_huft *)Z_NULL; | 241 | *(t = &(q->next)) = (inflate_huft *)Z_NULL; |
@@ -245,8 +245,8 @@ z_stream *zs; /* for zalloc function */ | |||
245 | if (h) | 245 | if (h) |
246 | { | 246 | { |
247 | x[h] = i; /* save pattern for backing up */ | 247 | x[h] = i; /* save pattern for backing up */ |
248 | r.bits = (char)l; /* bits to dump before this table */ | 248 | r.bits = (Byte)l; /* bits to dump before this table */ |
249 | r.exop = -(char)j; /* bits in this table */ | 249 | r.exop = -(Char)j; /* bits in this table */ |
250 | r.next = q; /* pointer to this table */ | 250 | r.next = q; /* pointer to this table */ |
251 | j = i >> (w - l); /* (get around Turbo C bug) */ | 251 | j = i >> (w - l); /* (get around Turbo C bug) */ |
252 | u[h-1][j] = r; /* connect to last table */ | 252 | u[h-1][j] = r; /* connect to last table */ |
@@ -254,17 +254,17 @@ z_stream *zs; /* for zalloc function */ | |||
254 | } | 254 | } |
255 | 255 | ||
256 | /* set up table entry in r */ | 256 | /* set up table entry in r */ |
257 | r.bits = (char)(k - w); | 257 | r.bits = (Byte)(k - w); |
258 | if (p >= v + n) | 258 | if (p >= v + n) |
259 | r.exop = -128; /* out of values--invalid code */ | 259 | r.exop = (Char)(-128); /* out of values--invalid code */ |
260 | else if (*p < s) | 260 | else if (*p < s) |
261 | { | 261 | { |
262 | r.exop = (char)(*p < 256 ? 16 : -64); /* 256 is end-of-block code */ | 262 | r.exop = (Char)(*p < 256 ? 16 : -64); /* 256 is end-of-block code */ |
263 | r.base = *p++; /* simple code is just the value */ | 263 | r.base = *p++; /* simple code is just the value */ |
264 | } | 264 | } |
265 | else | 265 | else |
266 | { | 266 | { |
267 | r.exop = (char)e[*p - s]; /* non-simple--look up in lists */ | 267 | r.exop = (Char)e[*p - s]; /* non-simple--look up in lists */ |
268 | r.base = d[*p++ - s]; | 268 | r.base = d[*p++ - s]; |
269 | } | 269 | } |
270 | 270 | ||
@@ -294,10 +294,10 @@ z_stream *zs; /* for zalloc function */ | |||
294 | 294 | ||
295 | 295 | ||
296 | int inflate_trees_bits(c, bb, tb, z) | 296 | int inflate_trees_bits(c, bb, tb, z) |
297 | uInt *c; /* 19 code lengths */ | 297 | uInt *c; /* 19 code lengths */ |
298 | uInt *bb; /* bits tree desired/actual depth */ | 298 | uInt *bb; /* bits tree desired/actual depth */ |
299 | inflate_huft **tb; /* bits tree result */ | 299 | inflate_huft **tb; /* bits tree result */ |
300 | z_stream *z; /* for zfree function */ | 300 | z_stream *z; /* for zfree function */ |
301 | { | 301 | { |
302 | int r; | 302 | int r; |
303 | 303 | ||
@@ -315,14 +315,14 @@ z_stream *z; /* for zfree function */ | |||
315 | 315 | ||
316 | 316 | ||
317 | int inflate_trees_dynamic(nl, nd, c, bl, bd, tl, td, z) | 317 | int inflate_trees_dynamic(nl, nd, c, bl, bd, tl, td, z) |
318 | uInt nl; /* number of literal/length codes */ | 318 | uInt nl; /* number of literal/length codes */ |
319 | uInt nd; /* number of distance codes */ | 319 | uInt nd; /* number of distance codes */ |
320 | uInt *c; /* that many (total) code lengths */ | 320 | uInt *c; /* that many (total) code lengths */ |
321 | uInt *bl; /* literal desired/actual bit depth */ | 321 | uInt *bl; /* literal desired/actual bit depth */ |
322 | uInt *bd; /* distance desired/actual bit depth */ | 322 | uInt *bd; /* distance desired/actual bit depth */ |
323 | inflate_huft **tl; /* literal/length tree result */ | 323 | inflate_huft **tl; /* literal/length tree result */ |
324 | inflate_huft **td; /* distance tree result */ | 324 | inflate_huft **td; /* distance tree result */ |
325 | z_stream *z; /* for zfree function */ | 325 | z_stream *z; /* for zfree function */ |
326 | { | 326 | { |
327 | int r; | 327 | int r; |
328 | 328 | ||
@@ -367,7 +367,7 @@ z_stream *z; /* for zfree function */ | |||
367 | /* build fixed tables only once--keep them here */ | 367 | /* build fixed tables only once--keep them here */ |
368 | local int fixed_lock = 0; | 368 | local int fixed_lock = 0; |
369 | local int fixed_built = 0; | 369 | local int fixed_built = 0; |
370 | #define FIXEDH 530 /* number of hufts used by fixed tables */ | 370 | #define FIXEDH 530 /* number of hufts used by fixed tables */ |
371 | local uInt fixed_left = FIXEDH; | 371 | local uInt fixed_left = FIXEDH; |
372 | local inflate_huft fixed_mem[FIXEDH]; | 372 | local inflate_huft fixed_mem[FIXEDH]; |
373 | local uInt fixed_bl; | 373 | local uInt fixed_bl; |
@@ -377,9 +377,9 @@ local inflate_huft *fixed_td; | |||
377 | 377 | ||
378 | 378 | ||
379 | local voidp falloc(q, n, s) | 379 | local voidp falloc(q, n, s) |
380 | voidp q; /* opaque pointer (not used) */ | 380 | voidp q; /* opaque pointer (not used) */ |
381 | uInt n; /* number of items */ | 381 | uInt n; /* number of items */ |
382 | uInt s; /* size of item */ | 382 | uInt s; /* size of item */ |
383 | { | 383 | { |
384 | Assert(s == sizeof(inflate_huft) && n <= fixed_left, | 384 | Assert(s == sizeof(inflate_huft) && n <= fixed_left, |
385 | "inflate_trees falloc overflow"); | 385 | "inflate_trees falloc overflow"); |
@@ -399,19 +399,19 @@ voidp p; | |||
399 | 399 | ||
400 | 400 | ||
401 | int inflate_trees_fixed(bl, bd, tl, td) | 401 | int inflate_trees_fixed(bl, bd, tl, td) |
402 | uInt *bl; /* literal desired/actual bit depth */ | 402 | uInt *bl; /* literal desired/actual bit depth */ |
403 | uInt *bd; /* distance desired/actual bit depth */ | 403 | uInt *bd; /* distance desired/actual bit depth */ |
404 | inflate_huft **tl; /* literal/length tree result */ | 404 | inflate_huft **tl; /* literal/length tree result */ |
405 | inflate_huft **td; /* distance tree result */ | 405 | inflate_huft **td; /* distance tree result */ |
406 | { | 406 | { |
407 | /* build fixed tables if not built already--lock out other instances */ | 407 | /* build fixed tables if not built already--lock out other instances */ |
408 | while (++fixed_lock > 1) | 408 | while (++fixed_lock > 1) |
409 | fixed_lock--; | 409 | fixed_lock--; |
410 | if (!fixed_built) | 410 | if (!fixed_built) |
411 | { | 411 | { |
412 | int k; /* temporary variable */ | 412 | int k; /* temporary variable */ |
413 | unsigned c[288]; /* length list for huft_build */ | 413 | unsigned c[288]; /* length list for huft_build */ |
414 | z_stream z; /* for falloc function */ | 414 | z_stream z; /* for falloc function */ |
415 | 415 | ||
416 | /* set up fake z_stream for memory routines */ | 416 | /* set up fake z_stream for memory routines */ |
417 | z.zalloc = falloc; | 417 | z.zalloc = falloc; |
@@ -449,8 +449,8 @@ inflate_huft **td; /* distance tree result */ | |||
449 | 449 | ||
450 | 450 | ||
451 | int inflate_trees_free(t, z) | 451 | int inflate_trees_free(t, z) |
452 | inflate_huft *t; /* table to free */ | 452 | inflate_huft *t; /* table to free */ |
453 | z_stream *z; /* for zfree function */ | 453 | z_stream *z; /* for zfree function */ |
454 | /* Free the malloc'ed tables built by huft_build(), which makes a linked | 454 | /* Free the malloc'ed tables built by huft_build(), which makes a linked |
455 | list of the tables it made, with the links in a dummy first entry of | 455 | list of the tables it made, with the links in a dummy first entry of |
456 | each table. */ | 456 | each table. */ |