1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/ossrv/compressionlibs/ziplib/test/oldezlib/EZLib/inftrees.cpp Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,456 @@
1.4 +/* inftrees.c -- generate Huffman trees for efficient decoding
1.5 + * Copyright (C) 1995-2002 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.4 Copyright 1995-2002 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(
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 +/* Given a list of code lengths and a maximum table size, make a set of
1.108 + tables to decode that set of codes. Return Z_OK on success, Z_BUF_ERROR
1.109 + if the given code set is incomplete (the tables are still built in this
1.110 + case), or Z_DATA_ERROR if the input is invalid. */
1.111 +{
1.112 + // Line to stop compiler warning about unused mandatory global variable
1.113 + char __z=inflate_copyright[0]; __z=__z;
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_DATA_ERROR; /* overflow of MANY */
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(
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 + int r;
1.306 + uInt hn = 0; /* hufts used in space */
1.307 + uIntf *v; /* work area for huft_build */
1.308 +
1.309 + if ((v = (uIntf*)ZALLOC(z, 19, sizeof(uInt))) == Z_NULL)
1.310 + return Z_MEM_ERROR;
1.311 + r = huft_build(c, 19, 19, (uIntf*)Z_NULL, (uIntf*)Z_NULL,
1.312 + tb, bb, hp, &hn, v);
1.313 + if (r == Z_DATA_ERROR)
1.314 + z->msg = (char*)"oversubscribed dynamic bit lengths tree";
1.315 + else if (r == Z_BUF_ERROR || *bb == 0)
1.316 + {
1.317 + z->msg = (char*)"incomplete dynamic bit lengths tree";
1.318 + r = Z_DATA_ERROR;
1.319 + }
1.320 + ZFREE(z, v);
1.321 + return r;
1.322 +}
1.323 +
1.324 +
1.325 +int inflate_trees_dynamic(
1.326 +uInt nl, /* number of literal/length codes */
1.327 +uInt nd, /* number of distance codes */
1.328 +uIntf *c, /* that many (total) code lengths */
1.329 +uIntf *bl, /* literal desired/actual bit depth */
1.330 +uIntf *bd, /* distance desired/actual bit depth */
1.331 +inflate_huft * FAR *tl, /* literal/length tree result */
1.332 +inflate_huft * FAR *td, /* distance tree result */
1.333 +inflate_huft *hp, /* space for trees */
1.334 +z_streamp z) /* for messages */
1.335 +{
1.336 + int r;
1.337 + uInt hn = 0; /* hufts used in space */
1.338 + uIntf *v; /* work area for huft_build */
1.339 +
1.340 + /* allocate work area */
1.341 + if ((v = (uIntf*)ZALLOC(z, 288, sizeof(uInt))) == Z_NULL)
1.342 + return Z_MEM_ERROR;
1.343 +
1.344 + /* build literal/length tree */
1.345 + r = huft_build(c, nl, 257, cplens, cplext, tl, bl, hp, &hn, v);
1.346 + if (r != Z_OK || *bl == 0)
1.347 + {
1.348 + if (r == Z_DATA_ERROR)
1.349 + z->msg = (char*)"oversubscribed literal/length tree";
1.350 + else if (r != Z_MEM_ERROR)
1.351 + {
1.352 + z->msg = (char*)"incomplete literal/length tree";
1.353 + r = Z_DATA_ERROR;
1.354 + }
1.355 + ZFREE(z, v);
1.356 + return r;
1.357 + }
1.358 +
1.359 + /* build distance tree */
1.360 + r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, hp, &hn, v);
1.361 + if (r != Z_OK || (*bd == 0 && nl > 257))
1.362 + {
1.363 + if (r == Z_DATA_ERROR)
1.364 + z->msg = (char*)"oversubscribed distance tree";
1.365 + else if (r == Z_BUF_ERROR) {
1.366 +#ifdef PKZIP_BUG_WORKAROUND
1.367 + r = Z_OK;
1.368 + }
1.369 +#else
1.370 + z->msg = (char*)"incomplete distance tree";
1.371 + r = Z_DATA_ERROR;
1.372 + }
1.373 + else if (r != Z_MEM_ERROR)
1.374 + {
1.375 + z->msg = (char*)"empty distance tree with lengths";
1.376 + r = Z_DATA_ERROR;
1.377 + }
1.378 + ZFREE(z, v);
1.379 + return r;
1.380 +#endif
1.381 + }
1.382 +
1.383 + /* done */
1.384 + ZFREE(z, v);
1.385 + return Z_OK;
1.386 +}
1.387 +
1.388 +
1.389 +/* build fixed tables only once--keep them here */
1.390 +#ifdef BUILDFIXED
1.391 +local int fixed_built = 0;
1.392 +#define FIXEDH 544 /* number of hufts used by fixed tables */
1.393 +local inflate_huft fixed_mem[FIXEDH];
1.394 +local uInt fixed_bl;
1.395 +local uInt fixed_bd;
1.396 +local inflate_huft *fixed_tl;
1.397 +local inflate_huft *fixed_td;
1.398 +#else
1.399 +#include "inffixed.h"
1.400 +#endif
1.401 +
1.402 +
1.403 +int inflate_trees_fixed(
1.404 +uIntf *bl, /* literal desired/actual bit depth */
1.405 +uIntf *bd, /* distance desired/actual bit depth */
1.406 +const inflate_huft * FAR *tl, /* literal/length tree result */
1.407 +const inflate_huft * FAR *td, /* distance tree result */
1.408 +z_streamp /*z*/) /* for memory allocation */
1.409 +{
1.410 +#ifdef BUILDFIXED
1.411 + /* build fixed tables if not already */
1.412 + if (!fixed_built)
1.413 + {
1.414 + int k; /* temporary variable */
1.415 + uInt f = 0; /* number of hufts used in fixed_mem */
1.416 + uIntf *c; /* length list for huft_build */
1.417 + uIntf *v; /* work area for huft_build */
1.418 +
1.419 + /* allocate memory */
1.420 + if ((c = (uIntf*)ZALLOC(z, 288, sizeof(uInt))) == Z_NULL)
1.421 + return Z_MEM_ERROR;
1.422 + if ((v = (uIntf*)ZALLOC(z, 288, sizeof(uInt))) == Z_NULL)
1.423 + {
1.424 + ZFREE(z, c);
1.425 + return Z_MEM_ERROR;
1.426 + }
1.427 +
1.428 + /* literal table */
1.429 + for (k = 0; k < 144; k++)
1.430 + c[k] = 8;
1.431 + for (; k < 256; k++)
1.432 + c[k] = 9;
1.433 + for (; k < 280; k++)
1.434 + c[k] = 7;
1.435 + for (; k < 288; k++)
1.436 + c[k] = 8;
1.437 + fixed_bl = 9;
1.438 + huft_build(c, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl,
1.439 + fixed_mem, &f, v);
1.440 +
1.441 + /* distance table */
1.442 + for (k = 0; k < 30; k++)
1.443 + c[k] = 5;
1.444 + fixed_bd = 5;
1.445 + huft_build(c, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd,
1.446 + fixed_mem, &f, v);
1.447 +
1.448 + /* done */
1.449 + ZFREE(z, v);
1.450 + ZFREE(z, c);
1.451 + fixed_built = 1;
1.452 + }
1.453 +#endif
1.454 + *bl = fixed_bl;
1.455 + *bd = fixed_bd;
1.456 + *tl = fixed_tl;
1.457 + *td = fixed_td;
1.458 + return Z_OK;
1.459 +}