aboutsummaryrefslogtreecommitdiff
path: root/inftrees.c
diff options
context:
space:
mode:
Diffstat (limited to 'inftrees.c')
-rw-r--r--inftrees.c160
1 files changed, 80 insertions, 80 deletions
diff --git a/inftrees.c b/inftrees.c
index ab0ed2c..9858927 100644
--- a/inftrees.c
+++ b/inftrees.c
@@ -16,37 +16,37 @@ struct internal_state {int dummy;}; /* for buggy compilers */
16 16
17 17
18local int huft_build __P(( 18local 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
28local voidp falloc __P(( 28local 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
33local void ffree __P(( 33local 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. */
38local uInt cplens[] = { /* Copy lengths for literal codes 257..285 */ 38local 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 */
42local uInt cplext[] = { /* Extra bits for literal codes 257..285 */ 42local 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 */
45local uInt cpdist[] = { /* Copy offsets for distance codes 0..29 */ 45local 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};
49local uInt cpdext[] = { /* Extra bits for distance codes */ 49local 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 */
100uInt *e; /* list of extra bits for non-simple codes */ 100uInt *e; /* list of extra bits for non-simple codes */
101inflate_huft **t; /* result: starting table */ 101inflate_huft **t; /* result: starting table */
102uInt *m; /* maximum lookup bits, returns actual */ 102uInt *m; /* maximum lookup bits, returns actual */
103z_stream *zs; /* for zalloc function */ 103z_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
296int inflate_trees_bits(c, bb, tb, z) 296int inflate_trees_bits(c, bb, tb, z)
297uInt *c; /* 19 code lengths */ 297uInt *c; /* 19 code lengths */
298uInt *bb; /* bits tree desired/actual depth */ 298uInt *bb; /* bits tree desired/actual depth */
299inflate_huft **tb; /* bits tree result */ 299inflate_huft **tb; /* bits tree result */
300z_stream *z; /* for zfree function */ 300z_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
317int inflate_trees_dynamic(nl, nd, c, bl, bd, tl, td, z) 317int inflate_trees_dynamic(nl, nd, c, bl, bd, tl, td, z)
318uInt nl; /* number of literal/length codes */ 318uInt nl; /* number of literal/length codes */
319uInt nd; /* number of distance codes */ 319uInt nd; /* number of distance codes */
320uInt *c; /* that many (total) code lengths */ 320uInt *c; /* that many (total) code lengths */
321uInt *bl; /* literal desired/actual bit depth */ 321uInt *bl; /* literal desired/actual bit depth */
322uInt *bd; /* distance desired/actual bit depth */ 322uInt *bd; /* distance desired/actual bit depth */
323inflate_huft **tl; /* literal/length tree result */ 323inflate_huft **tl; /* literal/length tree result */
324inflate_huft **td; /* distance tree result */ 324inflate_huft **td; /* distance tree result */
325z_stream *z; /* for zfree function */ 325z_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 */
368local int fixed_lock = 0; 368local int fixed_lock = 0;
369local int fixed_built = 0; 369local 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 */
371local uInt fixed_left = FIXEDH; 371local uInt fixed_left = FIXEDH;
372local inflate_huft fixed_mem[FIXEDH]; 372local inflate_huft fixed_mem[FIXEDH];
373local uInt fixed_bl; 373local uInt fixed_bl;
@@ -377,9 +377,9 @@ local inflate_huft *fixed_td;
377 377
378 378
379local voidp falloc(q, n, s) 379local voidp falloc(q, n, s)
380voidp q; /* opaque pointer (not used) */ 380voidp q; /* opaque pointer (not used) */
381uInt n; /* number of items */ 381uInt n; /* number of items */
382uInt s; /* size of item */ 382uInt 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
401int inflate_trees_fixed(bl, bd, tl, td) 401int inflate_trees_fixed(bl, bd, tl, td)
402uInt *bl; /* literal desired/actual bit depth */ 402uInt *bl; /* literal desired/actual bit depth */
403uInt *bd; /* distance desired/actual bit depth */ 403uInt *bd; /* distance desired/actual bit depth */
404inflate_huft **tl; /* literal/length tree result */ 404inflate_huft **tl; /* literal/length tree result */
405inflate_huft **td; /* distance tree result */ 405inflate_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
451int inflate_trees_free(t, z) 451int inflate_trees_free(t, z)
452inflate_huft *t; /* table to free */ 452inflate_huft *t; /* table to free */
453z_stream *z; /* for zfree function */ 453z_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. */