1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/ossrv/compressionlibs/ziplib/test/oldezlib/EZLib/infblock.cpp Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,404 @@
1.4 +/* infblock.c -- interpret and process block types to last block
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 "infblock.h"
1.11 +#include "inftrees.h"
1.12 +#include "infcodes.h"
1.13 +#include "infutil.h"
1.14 +
1.15 +struct inflate_codes_state {int dummy;}; /* for buggy compilers */
1.16 +
1.17 +/* simplify the use of the inflate_huft type with some defines */
1.18 +#define exop word.what.Exop
1.19 +#define bits word.what.Bits
1.20 +
1.21 +/* Table for deflate from PKZIP's appnote.txt. */
1.22 +local const uInt border[] = { /* Order of the bit length code lengths */
1.23 + 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
1.24 +
1.25 +/*
1.26 + Notes beyond the 1.93a appnote.txt:
1.27 +
1.28 + 1. Distance pointers never point before the beginning of the output
1.29 + stream.
1.30 + 2. Distance pointers can point back across blocks, up to 32k away.
1.31 + 3. There is an implied maximum of 7 bits for the bit length table and
1.32 + 15 bits for the actual data.
1.33 + 4. If only one code exists, then it is encoded using one bit. (Zero
1.34 + would be more efficient, but perhaps a little confusing.) If two
1.35 + codes exist, they are coded using one bit each (0 and 1).
1.36 + 5. There is no way of sending zero distance codes--a dummy must be
1.37 + sent if there are none. (History: a pre 2.0 version of PKZIP would
1.38 + store blocks with no distance codes, but this was discovered to be
1.39 + too harsh a criterion.) Valid only for 1.93a. 2.04c does allow
1.40 + zero distance codes, which is sent as one code of zero bits in
1.41 + length.
1.42 + 6. There are up to 286 literal/length codes. Code 256 represents the
1.43 + end-of-block. Note however that the static length tree defines
1.44 + 288 codes just to fill out the Huffman codes. Codes 286 and 287
1.45 + cannot be used though, since there is no length base or extra bits
1.46 + defined for them. Similarily, there are up to 30 distance codes.
1.47 + However, static trees define 32 codes (all 5 bits) to fill out the
1.48 + Huffman codes, but the last two had better not show up in the data.
1.49 + 7. Unzip can check dynamic Huffman blocks for complete code sets.
1.50 + The exception is that a single code would not be complete (see #4).
1.51 + 8. The five bits following the block type is really the number of
1.52 + literal codes sent minus 257.
1.53 + 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
1.54 + (1+6+6). Therefore, to output three times the length, you output
1.55 + three codes (1+1+1), whereas to output four times the same length,
1.56 + you only need two codes (1+3). Hmm.
1.57 + 10. In the tree reconstruction algorithm, Code = Code + Increment
1.58 + only if BitLength(i) is not zero. (Pretty obvious.)
1.59 + 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19)
1.60 + 12. Note: length code 284 can represent 227-258, but length code 285
1.61 + really is 258. The last length deserves its own, short code
1.62 + since it gets used a lot in very redundant files. The length
1.63 + 258 is special since 258 - 3 (the min match length) is 255.
1.64 + 13. The literal/length and distance code bit lengths are read as a
1.65 + single stream of lengths. It is possible (and advantageous) for
1.66 + a repeat code (16, 17, or 18) to go across the boundary between
1.67 + the two sets of lengths.
1.68 + */
1.69 +
1.70 +
1.71 +void inflate_blocks_reset(
1.72 +inflate_blocks_statef *s,
1.73 +z_streamp z,
1.74 +uLongf *c)
1.75 +{
1.76 + if (c != Z_NULL)
1.77 + *c = s->check;
1.78 + if (s->mode == BTREE || s->mode == DTREE)
1.79 + ZFREE(z, s->sub.trees.blens);
1.80 + if (s->mode == CODES)
1.81 + inflate_codes_free(s->sub.decode.codes, z);
1.82 + s->mode = TYPE;
1.83 + s->bitk = 0;
1.84 + s->bitb = 0;
1.85 + s->read = s->write = s->window;
1.86 + if (s->checkfn != Z_NULL)
1.87 + z->adler = s->check = (*s->checkfn)(0L, (const Bytef *)Z_NULL, 0);
1.88 + Tracev((stderr, "inflate: blocks reset\n"));
1.89 +}
1.90 +
1.91 +
1.92 +inflate_blocks_statef *inflate_blocks_new(
1.93 +z_streamp z,
1.94 +check_func c,
1.95 +uInt w)
1.96 +{
1.97 + inflate_blocks_statef *s;
1.98 +
1.99 + if ((s = (inflate_blocks_statef *)ZALLOC
1.100 + (z,1,sizeof(struct inflate_blocks_state))) == Z_NULL)
1.101 + return s;
1.102 + if ((s->hufts =
1.103 + (inflate_huft *)ZALLOC(z, sizeof(inflate_huft), MANY)) == Z_NULL)
1.104 + {
1.105 + ZFREE(z, s);
1.106 + return Z_NULL;
1.107 + }
1.108 + if ((s->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL)
1.109 + {
1.110 + ZFREE(z, s->hufts);
1.111 + ZFREE(z, s);
1.112 + return Z_NULL;
1.113 + }
1.114 + s->end = s->window + w;
1.115 + s->checkfn = c;
1.116 + s->mode = TYPE;
1.117 + Tracev((stderr, "inflate: blocks allocated\n"));
1.118 + inflate_blocks_reset(s, z, Z_NULL);
1.119 + return s;
1.120 +}
1.121 +
1.122 +
1.123 +int inflate_blocks(
1.124 +inflate_blocks_statef *s,
1.125 +z_streamp z,
1.126 +int r)
1.127 +{
1.128 + uInt t; /* temporary storage */
1.129 + uLong b; /* bit buffer */
1.130 + uInt k; /* bits in bit buffer */
1.131 + Bytef *p; /* input data pointer */
1.132 + uInt n; /* bytes available there */
1.133 + Bytef *q; /* output window write pointer */
1.134 + uInt m; /* bytes to end of window or read pointer */
1.135 +
1.136 + /* copy input/output information to locals (UPDATE macro restores) */
1.137 + LOAD
1.138 +
1.139 + /* process input based on current state */
1.140 + for (;;) switch (s->mode)
1.141 + {
1.142 + case TYPE:
1.143 + NEEDBITS(3)
1.144 + t = (uInt)b & 7;
1.145 + s->last = t & 1;
1.146 + switch (t >> 1)
1.147 + {
1.148 + case 0: /* stored */
1.149 + Tracev((stderr, "inflate: stored block%s\n",
1.150 + s->last ? " (last)" : ""));
1.151 + DUMPBITS(3)
1.152 + t = k & 7; /* go to byte boundary */
1.153 + DUMPBITS(t)
1.154 + s->mode = LENS; /* get length of stored block */
1.155 + break;
1.156 + case 1: /* fixed */
1.157 + Tracev((stderr, "inflate: fixed codes block%s\n",
1.158 + s->last ? " (last)" : ""));
1.159 + {
1.160 + uInt bl, bd;
1.161 + const inflate_huft *tl, *td;
1.162 +
1.163 + inflate_trees_fixed(&bl, &bd, &tl, &td, z);
1.164 + s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z);
1.165 + if (s->sub.decode.codes == Z_NULL)
1.166 + {
1.167 + r = Z_MEM_ERROR;
1.168 + LEAVE
1.169 + }
1.170 + }
1.171 + DUMPBITS(3)
1.172 + s->mode = CODES;
1.173 + break;
1.174 + case 2: /* dynamic */
1.175 + Tracev((stderr, "inflate: dynamic codes block%s\n",
1.176 + s->last ? " (last)" : ""));
1.177 + DUMPBITS(3)
1.178 + s->mode = TABLE;
1.179 + break;
1.180 + case 3: /* illegal */
1.181 + DUMPBITS(3)
1.182 + s->mode = BAD;
1.183 + z->msg = (char*)"invalid block type";
1.184 + r = Z_DATA_ERROR;
1.185 + LEAVE
1.186 + }
1.187 + break;
1.188 + case LENS:
1.189 + NEEDBITS(32)
1.190 + if ((((~b) >> 16) & 0xffff) != (b & 0xffff))
1.191 + {
1.192 + s->mode = BAD;
1.193 + z->msg = (char*)"invalid stored block lengths";
1.194 + r = Z_DATA_ERROR;
1.195 + LEAVE
1.196 + }
1.197 + s->sub.left = (uInt)b & 0xffff;
1.198 + b = k = 0; /* dump bits */
1.199 + Tracev((stderr, "inflate: stored length %u\n", s->sub.left));
1.200 + s->mode = s->sub.left ? STORED : (s->last ? DRY : TYPE);
1.201 + break;
1.202 + case STORED:
1.203 + if (n == 0)
1.204 + LEAVE
1.205 + NEEDOUT
1.206 + t = s->sub.left;
1.207 + if (t > n) t = n;
1.208 + if (t > m) t = m;
1.209 + zmemcpy(q, p, t);
1.210 + p += t; n -= t;
1.211 + q += t; m -= t;
1.212 + if ((s->sub.left -= t) != 0)
1.213 + break;
1.214 + Tracev((stderr, "inflate: stored end, %lu total out\n",
1.215 + z->total_out + (q >= s->read ? q - s->read :
1.216 + (s->end - s->read) + (q - s->window))));
1.217 + s->mode = s->last ? DRY : TYPE;
1.218 + break;
1.219 + case TABLE:
1.220 + NEEDBITS(14)
1.221 + s->sub.trees.table = t = (uInt)b & 0x3fff;
1.222 +#ifndef PKZIP_BUG_WORKAROUND
1.223 + if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29)
1.224 + {
1.225 + s->mode = BAD;
1.226 + z->msg = (char*)"too many length or distance symbols";
1.227 + r = Z_DATA_ERROR;
1.228 + LEAVE
1.229 + }
1.230 +#endif
1.231 + t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f);
1.232 + if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL)
1.233 + {
1.234 + r = Z_MEM_ERROR;
1.235 + LEAVE
1.236 + }
1.237 + DUMPBITS(14)
1.238 + s->sub.trees.index = 0;
1.239 + Tracev((stderr, "inflate: table sizes ok\n"));
1.240 + s->mode = BTREE;
1.241 + case BTREE:
1.242 + while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10))
1.243 + {
1.244 + NEEDBITS(3)
1.245 + s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7;
1.246 + DUMPBITS(3)
1.247 + }
1.248 + while (s->sub.trees.index < 19)
1.249 + s->sub.trees.blens[border[s->sub.trees.index++]] = 0;
1.250 + s->sub.trees.bb = 7;
1.251 + t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb,
1.252 + &s->sub.trees.tb, s->hufts, z);
1.253 + if (t != Z_OK)
1.254 + {
1.255 + r = t;
1.256 + if (r == Z_DATA_ERROR)
1.257 + {
1.258 + ZFREE(z, s->sub.trees.blens);
1.259 + s->mode = BAD;
1.260 + }
1.261 + LEAVE
1.262 + }
1.263 + s->sub.trees.index = 0;
1.264 + Tracev((stderr, "inflate: bits tree ok\n"));
1.265 + s->mode = DTREE;
1.266 + case DTREE:
1.267 + while (t = s->sub.trees.table,
1.268 + s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f))
1.269 + {
1.270 + inflate_huft *h;
1.271 + uInt i, j, c;
1.272 +
1.273 + t = s->sub.trees.bb;
1.274 + NEEDBITS(t)
1.275 + h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]);
1.276 + t = h->bits;
1.277 + c = h->base;
1.278 + if (c < 16)
1.279 + {
1.280 + DUMPBITS(t)
1.281 + s->sub.trees.blens[s->sub.trees.index++] = c;
1.282 + }
1.283 + else /* c == 16..18 */
1.284 + {
1.285 + i = c == 18 ? 7 : c - 14;
1.286 + j = c == 18 ? 11 : 3;
1.287 + NEEDBITS(t + i)
1.288 + DUMPBITS(t)
1.289 + j += (uInt)b & inflate_mask[i];
1.290 + DUMPBITS(i)
1.291 + i = s->sub.trees.index;
1.292 + t = s->sub.trees.table;
1.293 + if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) ||
1.294 + (c == 16 && i < 1))
1.295 + {
1.296 + ZFREE(z, s->sub.trees.blens);
1.297 + s->mode = BAD;
1.298 + z->msg = (char*)"invalid bit length repeat";
1.299 + r = Z_DATA_ERROR;
1.300 + LEAVE
1.301 + }
1.302 + c = c == 16 ? s->sub.trees.blens[i - 1] : 0;
1.303 + do {
1.304 + s->sub.trees.blens[i++] = c;
1.305 + } while (--j);
1.306 + s->sub.trees.index = i;
1.307 + }
1.308 + }
1.309 + s->sub.trees.tb = Z_NULL;
1.310 + {
1.311 + uInt bl, bd;
1.312 + inflate_huft *tl, *td;
1.313 + inflate_codes_statef *c;
1.314 +
1.315 + bl = 9; /* must be <= 9 for lookahead assumptions */
1.316 + bd = 6; /* must be <= 9 for lookahead assumptions */
1.317 + t = s->sub.trees.table;
1.318 + t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f),
1.319 + s->sub.trees.blens, &bl, &bd, &tl, &td,
1.320 + s->hufts, z);
1.321 +
1.322 + if (t != Z_OK)
1.323 + {
1.324 + if (t == (uInt)Z_DATA_ERROR)
1.325 + {
1.326 + ZFREE(z, s->sub.trees.blens);
1.327 + s->mode = BAD;
1.328 + }
1.329 + r = t;
1.330 + LEAVE
1.331 + }
1.332 + Tracev((stderr, "inflate: trees ok\n"));
1.333 + if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL)
1.334 + {
1.335 + r = Z_MEM_ERROR;
1.336 + LEAVE
1.337 + }
1.338 + s->sub.decode.codes = c;
1.339 + }
1.340 + ZFREE(z, s->sub.trees.blens);
1.341 + s->mode = CODES;
1.342 + case CODES:
1.343 + UPDATE
1.344 + if ((r = inflate_codes(s, z, r)) != Z_STREAM_END)
1.345 + return inflate_flush(s, z, r);
1.346 + r = Z_OK;
1.347 + inflate_codes_free(s->sub.decode.codes, z);
1.348 + LOAD
1.349 + Tracev((stderr, "inflate: codes end, %lu total out\n",
1.350 + z->total_out + (q >= s->read ? q - s->read :
1.351 + (s->end - s->read) + (q - s->window))));
1.352 + if (!s->last)
1.353 + {
1.354 + s->mode = TYPE;
1.355 + break;
1.356 + }
1.357 + s->mode = DRY;
1.358 + case DRY:
1.359 + FLUSH
1.360 + if (s->read != s->write)
1.361 + LEAVE
1.362 + s->mode = DONE;
1.363 + case DONE:
1.364 + r = Z_STREAM_END;
1.365 + LEAVE
1.366 + case BAD:
1.367 + r = Z_DATA_ERROR;
1.368 + LEAVE
1.369 + default:
1.370 + r = Z_STREAM_ERROR;
1.371 + LEAVE
1.372 + }
1.373 +}
1.374 +
1.375 +
1.376 +int inflate_blocks_free(
1.377 +inflate_blocks_statef *s,
1.378 +z_streamp z)
1.379 +{
1.380 + inflate_blocks_reset(s, z, Z_NULL);
1.381 + ZFREE(z, s->window);
1.382 + ZFREE(z, s->hufts);
1.383 + ZFREE(z, s);
1.384 + Tracev((stderr, "inflate: blocks freed\n"));
1.385 + return Z_OK;
1.386 +}
1.387 +
1.388 +
1.389 +void inflate_set_dictionary(
1.390 +inflate_blocks_statef *s,
1.391 +const Bytef *d,
1.392 +uInt n)
1.393 +{
1.394 + zmemcpy(s->window, d, n);
1.395 + s->read = s->write = s->window + n;
1.396 +}
1.397 +
1.398 +
1.399 +/* Returns true if inflate is currently at the end of a block generated
1.400 + * by Z_SYNC_FLUSH or Z_FULL_FLUSH.
1.401 + * IN assertion: s != Z_NULL
1.402 + */
1.403 +int inflate_blocks_sync_point(
1.404 +inflate_blocks_statef *s)
1.405 +{
1.406 + return s->mode == LENS;
1.407 +}