1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/ossrv/compressionlibs/ziplib/test/oldezlib/Zlib/inftrees.c Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,460 @@
1.4 +/* inftrees.c -- generate Huffman trees for efficient decoding
1.5 + * Copyright (C) 1995-1998 Mark Adler
1.6 + * For conditions of distribution and use, see copyright notice in zlib.h
1.7 + */
1.8 +
1.9 +#include "zutil.h"
1.10 +#include "inftrees.h"
1.11 +
1.12 +#if !defined(BUILDFIXED) && !defined(STDC)
1.13 +# define BUILDFIXED /* non ANSI compilers may not accept inffixed.h */
1.14 +#endif
1.15 +
1.16 +const char inflate_copyright[] =
1.17 + " inflate 1.1.3 Copyright 1995-1998 Mark Adler ";
1.18 +/*
1.19 + If you use the zlib library in a product, an acknowledgment is welcome
1.20 + in the documentation of your product. If for some reason you cannot
1.21 + include such an acknowledgment, I would appreciate that you keep this
1.22 + copyright string in the executable of your product.
1.23 + */
1.24 +struct internal_state {int dummy;}; /* for buggy compilers */
1.25 +
1.26 +/* simplify the use of the inflate_huft type with some defines */
1.27 +#define exop word.what.Exop
1.28 +#define bits word.what.Bits
1.29 +
1.30 +
1.31 +local int huft_build OF((
1.32 + uIntf *, /* code lengths in bits */
1.33 + uInt, /* number of codes */
1.34 + uInt, /* number of "simple" codes */
1.35 + const uIntf *, /* list of base values for non-simple codes */
1.36 + const uIntf *, /* list of extra bits for non-simple codes */
1.37 + inflate_huft * FAR*,/* result: starting table */
1.38 + uIntf *, /* maximum lookup bits (returns actual) */
1.39 + inflate_huft *, /* space for trees */
1.40 + uInt *, /* hufts used in space */
1.41 + uIntf * )); /* space for values */
1.42 +
1.43 +/* Tables for deflate from PKZIP's appnote.txt. */
1.44 +local const uInt cplens[31] = { /* Copy lengths for literal codes 257..285 */
1.45 + 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
1.46 + 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
1.47 + /* see note #13 above about 258 */
1.48 +local const uInt cplext[31] = { /* Extra bits for literal codes 257..285 */
1.49 + 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
1.50 + 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 112, 112}; /* 112==invalid */
1.51 +local const uInt cpdist[30] = { /* Copy offsets for distance codes 0..29 */
1.52 + 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
1.53 + 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
1.54 + 8193, 12289, 16385, 24577};
1.55 +local const uInt cpdext[30] = { /* Extra bits for distance codes */
1.56 + 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
1.57 + 7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
1.58 + 12, 12, 13, 13};
1.59 +
1.60 +/*
1.61 + Huffman code decoding is performed using a multi-level table lookup.
1.62 + The fastest way to decode is to simply build a lookup table whose
1.63 + size is determined by the longest code. However, the time it takes
1.64 + to build this table can also be a factor if the data being decoded
1.65 + is not very long. The most common codes are necessarily the
1.66 + shortest codes, so those codes dominate the decoding time, and hence
1.67 + the speed. The idea is you can have a shorter table that decodes the
1.68 + shorter, more probable codes, and then point to subsidiary tables for
1.69 + the longer codes. The time it costs to decode the longer codes is
1.70 + then traded against the time it takes to make longer tables.
1.71 +
1.72 + This results of this trade are in the variables lbits and dbits
1.73 + below. lbits is the number of bits the first level table for literal/
1.74 + length codes can decode in one step, and dbits is the same thing for
1.75 + the distance codes. Subsequent tables are also less than or equal to
1.76 + those sizes. These values may be adjusted either when all of the
1.77 + codes are shorter than that, in which case the longest code length in
1.78 + bits is used, or when the shortest code is *longer* than the requested
1.79 + table size, in which case the length of the shortest code in bits is
1.80 + used.
1.81 +
1.82 + There are two different values for the two tables, since they code a
1.83 + different number of possibilities each. The literal/length table
1.84 + codes 286 possible values, or in a flat code, a little over eight
1.85 + bits. The distance table codes 30 possible values, or a little less
1.86 + than five bits, flat. The optimum values for speed end up being
1.87 + about one bit more than those, so lbits is 8+1 and dbits is 5+1.
1.88 + The optimum values may differ though from machine to machine, and
1.89 + possibly even between compilers. Your mileage may vary.
1.90 + */
1.91 +
1.92 +
1.93 +/* If BMAX needs to be larger than 16, then h and x[] should be uLong. */
1.94 +#define BMAX 15 /* maximum bit length of any code */
1.95 +
1.96 +local int huft_build(uIntf *b, uInt n, uInt s, const uIntf *d, const uIntf *e, inflate_huft * FAR *t, uIntf *m, inflate_huft *hp, uInt *hn, uIntf *v)
1.97 +/* uIntf *b; code lengths in bits (all assumed <= BMAX) */
1.98 +/* uInt n; number of codes (assumed <= 288) */
1.99 +/* uInt s; number of simple-valued codes (0..s-1) */
1.100 +/* const uIntf *d; list of base values for non-simple codes */
1.101 +/* const uIntf *e; list of extra bits for non-simple codes */
1.102 +/* inflate_huft * FAR *t; result: starting table */
1.103 +/* uIntf *m; maximum lookup bits, returns actual */
1.104 +/* inflate_huft *hp; space for trees */
1.105 +/* uInt *hn; hufts used in space */
1.106 +/* uIntf *v; working area: values in order of bit length */
1.107 +
1.108 +/* Given a list of code lengths and a maximum table size, make a set of
1.109 + tables to decode that set of codes. Return Z_OK on success, Z_BUF_ERROR
1.110 + if the given code set is incomplete (the tables are still built in this
1.111 + case), Z_DATA_ERROR if the input is invalid (an over-subscribed set of
1.112 + lengths), or Z_MEM_ERROR if not enough memory. */
1.113 +{
1.114 +
1.115 + uInt a; /* counter for codes of length k */
1.116 + uInt c[BMAX+1]; /* bit length count table */
1.117 + uInt f; /* i repeats in table every f entries */
1.118 + int g; /* maximum code length */
1.119 + int h; /* table level */
1.120 + register uInt i; /* counter, current code */
1.121 + register uInt j; /* counter */
1.122 + register int k; /* number of bits in current code */
1.123 + int l; /* bits per table (returned in m) */
1.124 + uInt mask; /* (1 << w) - 1, to avoid cc -O bug on HP */
1.125 + register uIntf *p; /* pointer into c[], b[], or v[] */
1.126 + inflate_huft *q; /* points to current table */
1.127 + struct inflate_huft_s r; /* table entry for structure assignment */
1.128 + inflate_huft *u[BMAX]; /* table stack */
1.129 + register int w; /* bits before this table == (l * h) */
1.130 + uInt x[BMAX+1]; /* bit offsets, then code stack */
1.131 + uIntf *xp; /* pointer into x */
1.132 + int y; /* number of dummy codes added */
1.133 + uInt z; /* number of entries in current table */
1.134 +
1.135 +
1.136 + /* Generate counts for each bit length */
1.137 + p = c;
1.138 +#define C0 *p++ = 0;
1.139 +#define C2 C0 C0 C0 C0
1.140 +#define C4 C2 C2 C2 C2
1.141 + C4 /* clear c[]--assume BMAX+1 is 16 */
1.142 + p = b; i = n;
1.143 + do {
1.144 + c[*p++]++; /* assume all entries <= BMAX */
1.145 + } while (--i);
1.146 + if (c[0] == n) /* null input--all zero length codes */
1.147 + {
1.148 + *t = (inflate_huft *)Z_NULL;
1.149 + *m = 0;
1.150 + return Z_OK;
1.151 + }
1.152 +
1.153 +
1.154 + /* Find minimum and maximum length, bound *m by those */
1.155 + l = *m;
1.156 + for (j = 1; j <= BMAX; j++)
1.157 + if (c[j])
1.158 + break;
1.159 + k = j; /* minimum code length */
1.160 + if ((uInt)l < j)
1.161 + l = j;
1.162 + for (i = BMAX; i; i--)
1.163 + if (c[i])
1.164 + break;
1.165 + g = i; /* maximum code length */
1.166 + if ((uInt)l > i)
1.167 + l = i;
1.168 + *m = l;
1.169 +
1.170 +
1.171 + /* Adjust last length count to fill out codes, if needed */
1.172 + for (y = 1 << j; j < i; j++, y <<= 1)
1.173 + if ((y -= c[j]) < 0)
1.174 + return Z_DATA_ERROR;
1.175 + if ((y -= c[i]) < 0)
1.176 + return Z_DATA_ERROR;
1.177 + c[i] += y;
1.178 +
1.179 +
1.180 + /* Generate starting offsets into the value table for each length */
1.181 + x[1] = j = 0;
1.182 + p = c + 1; xp = x + 2;
1.183 + while (--i) { /* note that i == g from above */
1.184 + *xp++ = (j += *p++);
1.185 + }
1.186 +
1.187 +
1.188 + /* Make a table of values in order of bit lengths */
1.189 + p = b; i = 0;
1.190 + do {
1.191 + if ((j = *p++) != 0)
1.192 + v[x[j]++] = i;
1.193 + } while (++i < n);
1.194 + n = x[g]; /* set n to length of v */
1.195 +
1.196 +
1.197 + /* Generate the Huffman codes and for each, make the table entries */
1.198 + x[0] = i = 0; /* first Huffman code is zero */
1.199 + p = v; /* grab values in bit order */
1.200 + h = -1; /* no tables yet--level -1 */
1.201 + w = -l; /* bits decoded == (l * h) */
1.202 + u[0] = (inflate_huft *)Z_NULL; /* just to keep compilers happy */
1.203 + q = (inflate_huft *)Z_NULL; /* ditto */
1.204 + z = 0; /* ditto */
1.205 +
1.206 + /* go through the bit lengths (k already is bits in shortest code) */
1.207 + for (; k <= g; k++)
1.208 + {
1.209 + a = c[k];
1.210 + while (a--)
1.211 + {
1.212 + /* here i is the Huffman code of length k bits for value *p */
1.213 + /* make tables up to required level */
1.214 + while (k > w + l)
1.215 + {
1.216 + h++;
1.217 + w += l; /* previous table always l bits */
1.218 +
1.219 + /* compute minimum size table less than or equal to l bits */
1.220 + z = g - w;
1.221 + z = z > (uInt)l ? l : z; /* table size upper limit */
1.222 + if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */
1.223 + { /* too few codes for k-w bit table */
1.224 + f -= a + 1; /* deduct codes from patterns left */
1.225 + xp = c + k;
1.226 + if (j < z)
1.227 + while (++j < z) /* try smaller tables up to z bits */
1.228 + {
1.229 + if ((f <<= 1) <= *++xp)
1.230 + break; /* enough codes to use up j bits */
1.231 + f -= *xp; /* else deduct codes from patterns */
1.232 + }
1.233 + }
1.234 + z = 1 << j; /* table entries for j-bit table */
1.235 +
1.236 + /* allocate new table */
1.237 + if (*hn + z > MANY) /* (note: doesn't matter for fixed) */
1.238 + return Z_MEM_ERROR; /* not enough memory */
1.239 + u[h] = q = hp + *hn;
1.240 + *hn += z;
1.241 +
1.242 + /* connect to last table, if there is one */
1.243 + if (h)
1.244 + {
1.245 + x[h] = i; /* save pattern for backing up */
1.246 + r.bits = (Byte)l; /* bits to dump before this table */
1.247 + r.exop = (Byte)j; /* bits in this table */
1.248 + j = i >> (w - l);
1.249 + r.base = (uInt)(q - u[h-1] - j); /* offset to this table */
1.250 + u[h-1][j] = r; /* connect to last table */
1.251 + }
1.252 + else
1.253 + *t = q; /* first table is returned result */
1.254 + }
1.255 +
1.256 + /* set up table entry in r */
1.257 + r.bits = (Byte)(k - w);
1.258 + if (p >= v + n)
1.259 + r.exop = 128 + 64; /* out of values--invalid code */
1.260 + else if (*p < s)
1.261 + {
1.262 + r.exop = (Byte)(*p < 256 ? 0 : 32 + 64); /* 256 is end-of-block */
1.263 + r.base = *p++; /* simple code is just the value */
1.264 + }
1.265 + else
1.266 + {
1.267 + r.exop = (Byte)(e[*p - s] + 16 + 64);/* non-simple--look up in lists */
1.268 + r.base = d[*p++ - s];
1.269 + }
1.270 +
1.271 + /* fill code-like entries with r */
1.272 + f = 1 << (k - w);
1.273 + for (j = i >> w; j < z; j += f)
1.274 + q[j] = r;
1.275 +
1.276 + /* backwards increment the k-bit code i */
1.277 + for (j = 1 << (k - 1); i & j; j >>= 1)
1.278 + i ^= j;
1.279 + i ^= j;
1.280 +
1.281 + /* backup over finished tables */
1.282 + mask = (1 << w) - 1; /* needed on HP, cc -O bug */
1.283 + while ((i & mask) != x[h])
1.284 + {
1.285 + h--; /* don't need to update q */
1.286 + w -= l;
1.287 + mask = (1 << w) - 1;
1.288 + }
1.289 + }
1.290 + }
1.291 +
1.292 +
1.293 + /* Return Z_BUF_ERROR if we were given an incomplete table */
1.294 + return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK;
1.295 +}
1.296 +
1.297 +
1.298 +int inflate_trees_bits(uIntf *c, uIntf *bb, inflate_huft * FAR *tb, inflate_huft *hp, z_streamp z)
1.299 +/* uIntf *c; 19 code lengths */
1.300 +/* uIntf *bb; bits tree desired/actual depth */
1.301 +/* inflate_huft * FAR *tb; bits tree result */
1.302 +/* inflate_huft *hp; space for trees */
1.303 +/* z_streamp z; for messages */
1.304 +
1.305 +
1.306 +{
1.307 + int r;
1.308 + uInt hn = 0; /* hufts used in space */
1.309 + uIntf *v; /* work area for huft_build */
1.310 +
1.311 + if ((v = (uIntf*)ZALLOC(z, 19, sizeof(uInt))) == Z_NULL)
1.312 + return Z_MEM_ERROR;
1.313 + r = huft_build(c, 19, 19, (uIntf*)Z_NULL, (uIntf*)Z_NULL,
1.314 + tb, bb, hp, &hn, v);
1.315 + if (r == Z_DATA_ERROR)
1.316 + z->msg = (char*)"oversubscribed dynamic bit lengths tree";
1.317 + else if (r == Z_BUF_ERROR || *bb == 0)
1.318 + {
1.319 + z->msg = (char*)"incomplete dynamic bit lengths tree";
1.320 + r = Z_DATA_ERROR;
1.321 + }
1.322 + ZFREE(z, v);
1.323 + return r;
1.324 +}
1.325 +
1.326 +
1.327 +int inflate_trees_dynamic(uInt nl, uInt nd, uIntf *c, uIntf *bl, uIntf *bd, inflate_huft * FAR *tl, inflate_huft * FAR *td, inflate_huft *hp, z_streamp z)
1.328 +/* uInt nl; number of literal/length codes */
1.329 +/* uInt nd; number of distance codes */
1.330 +/* uIntf *c; that many (total) code lengths */
1.331 +/* uIntf *bl; literal desired/actual bit depth */
1.332 +/* uIntf *bd; distance desired/actual bit depth */
1.333 +/* inflate_huft * FAR *tl; literal/length tree result */
1.334 +/* inflate_huft * FAR *td; distance tree result */
1.335 +/* inflate_huft *hp; space for trees */
1.336 +/* z_streamp z; for messages */
1.337 +
1.338 +
1.339 +{
1.340 + int r;
1.341 + uInt hn = 0; /* hufts used in space */
1.342 + uIntf *v; /* work area for huft_build */
1.343 +
1.344 + /* allocate work area */
1.345 + if ((v = (uIntf*)ZALLOC(z, 288, sizeof(uInt))) == Z_NULL)
1.346 + return Z_MEM_ERROR;
1.347 +
1.348 + /* build literal/length tree */
1.349 + r = huft_build(c, nl, 257, cplens, cplext, tl, bl, hp, &hn, v);
1.350 + if (r != Z_OK || *bl == 0)
1.351 + {
1.352 + if (r == Z_DATA_ERROR)
1.353 + z->msg = (char*)"oversubscribed literal/length tree";
1.354 + else if (r != Z_MEM_ERROR)
1.355 + {
1.356 + z->msg = (char*)"incomplete literal/length tree";
1.357 + r = Z_DATA_ERROR;
1.358 + }
1.359 + ZFREE(z, v);
1.360 + return r;
1.361 + }
1.362 +
1.363 + /* build distance tree */
1.364 + r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, hp, &hn, v);
1.365 + if (r != Z_OK || (*bd == 0 && nl > 257))
1.366 + {
1.367 + if (r == Z_DATA_ERROR)
1.368 + z->msg = (char*)"oversubscribed distance tree";
1.369 + else if (r == Z_BUF_ERROR) {
1.370 +#ifdef PKZIP_BUG_WORKAROUND
1.371 + r = Z_OK;
1.372 + }
1.373 +#else
1.374 + z->msg = (char*)"incomplete distance tree";
1.375 + r = Z_DATA_ERROR;
1.376 + }
1.377 + else if (r != Z_MEM_ERROR)
1.378 + {
1.379 + z->msg = (char*)"empty distance tree with lengths";
1.380 + r = Z_DATA_ERROR;
1.381 + }
1.382 + ZFREE(z, v);
1.383 + return r;
1.384 +#endif
1.385 + }
1.386 +
1.387 + /* done */
1.388 + ZFREE(z, v);
1.389 + return Z_OK;
1.390 +}
1.391 +
1.392 +
1.393 +/* build fixed tables only once--keep them here */
1.394 +#ifdef BUILDFIXED
1.395 +local int fixed_built = 0;
1.396 +#define FIXEDH 544 /* number of hufts used by fixed tables */
1.397 +local inflate_huft fixed_mem[FIXEDH];
1.398 +local uInt fixed_bl;
1.399 +local uInt fixed_bd;
1.400 +local inflate_huft *fixed_tl;
1.401 +local inflate_huft *fixed_td;
1.402 +#else
1.403 +#include "inffixed.h"
1.404 +#endif
1.405 +
1.406 +int inflate_trees_fixed(uIntf *bl, uIntf *bd, inflate_huft * FAR *tl, inflate_huft * FAR *td, z_streamp z)
1.407 +/* uIntf *bl; literal desired/actual bit depth */
1.408 +/* uIntf *bd; distance desired/actual bit depth */
1.409 +/* inflate_huft * FAR *tl; literal/length tree result */
1.410 +/* inflate_huft * FAR *td; distance tree result */
1.411 +/* z_streamp z; for memory allocation */
1.412 +{
1.413 +#ifdef BUILDFIXED
1.414 + /* build fixed tables if not already */
1.415 + if (!fixed_built)
1.416 + {
1.417 + int k; /* temporary variable */
1.418 + uInt f = 0; /* number of hufts used in fixed_mem */
1.419 + uIntf *c; /* length list for huft_build */
1.420 + uIntf *v; /* work area for huft_build */
1.421 +
1.422 + /* allocate memory */
1.423 + if ((c = (uIntf*)ZALLOC(z, 288, sizeof(uInt))) == Z_NULL)
1.424 + return Z_MEM_ERROR;
1.425 + if ((v = (uIntf*)ZALLOC(z, 288, sizeof(uInt))) == Z_NULL)
1.426 + {
1.427 + ZFREE(z, c);
1.428 + return Z_MEM_ERROR;
1.429 + }
1.430 +
1.431 + /* literal table */
1.432 + for (k = 0; k < 144; k++)
1.433 + c[k] = 8;
1.434 + for (; k < 256; k++)
1.435 + c[k] = 9;
1.436 + for (; k < 280; k++)
1.437 + c[k] = 7;
1.438 + for (; k < 288; k++)
1.439 + c[k] = 8;
1.440 + fixed_bl = 9;
1.441 + huft_build(c, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl,
1.442 + fixed_mem, &f, v);
1.443 +
1.444 + /* distance table */
1.445 + for (k = 0; k < 30; k++)
1.446 + c[k] = 5;
1.447 + fixed_bd = 5;
1.448 + huft_build(c, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd,
1.449 + fixed_mem, &f, v);
1.450 +
1.451 + /* done */
1.452 + ZFREE(z, v);
1.453 + ZFREE(z, c);
1.454 + fixed_built = 1;
1.455 + }
1.456 +#endif
1.457 + *bl = fixed_bl;
1.458 + *bd = fixed_bd;
1.459 + *tl = fixed_tl;
1.460 + *td = fixed_td;
1.461 + z->data_type = z->data_type; /* Here to prevent TOOLS2 warning about z being unused. */
1.462 + return Z_OK;
1.463 +}