1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/ossrv/compressionlibs/ziplib/test/oldezlib/Zlib/infblock.c Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,383 @@
1.4 +/* infblock.c -- interpret and process block types to last block
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 "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(inflate_blocks_statef *s, z_streamp z, uLongf *c)
1.72 +{
1.73 + if (c != Z_NULL)
1.74 + *c = s->check;
1.75 + if (s->mode == BTREE || s->mode == DTREE)
1.76 + ZFREE(z, s->sub.trees.blens);
1.77 + if (s->mode == CODES)
1.78 + inflate_codes_free(s->sub.decode.codes, z);
1.79 + s->mode = TYPE;
1.80 + s->bitk = 0;
1.81 + s->bitb = 0;
1.82 + s->read = s->write = s->window;
1.83 + if (s->checkfn != Z_NULL)
1.84 + z->adler = s->check = (*s->checkfn)(0L, (const Bytef *)Z_NULL, 0);
1.85 + Tracev((stderr, "inflate: blocks reset\n"));
1.86 +}
1.87 +
1.88 +
1.89 +inflate_blocks_statef *inflate_blocks_new(z_streamp z, check_func c, uInt w)
1.90 +{
1.91 + inflate_blocks_statef *s;
1.92 +
1.93 + if ((s = (inflate_blocks_statef *)ZALLOC
1.94 + (z,1,sizeof(struct inflate_blocks_state))) == Z_NULL)
1.95 + return s;
1.96 + if ((s->hufts =
1.97 + (inflate_huft *)ZALLOC(z, sizeof(inflate_huft), MANY)) == Z_NULL)
1.98 + {
1.99 + ZFREE(z, s);
1.100 + return Z_NULL;
1.101 + }
1.102 + if ((s->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL)
1.103 + {
1.104 + ZFREE(z, s->hufts);
1.105 + ZFREE(z, s);
1.106 + return Z_NULL;
1.107 + }
1.108 + s->end = s->window + w;
1.109 + s->checkfn = c;
1.110 + s->mode = TYPE;
1.111 + Tracev((stderr, "inflate: blocks allocated\n"));
1.112 + inflate_blocks_reset(s, z, Z_NULL);
1.113 + return s;
1.114 +}
1.115 +
1.116 +
1.117 +int inflate_blocks(inflate_blocks_statef *s, z_streamp z, int r)
1.118 +{
1.119 + uInt t; /* temporary storage */
1.120 + uLong b; /* bit buffer */
1.121 + uInt k; /* bits in bit buffer */
1.122 + Bytef *p; /* input data pointer */
1.123 + uInt n; /* bytes available there */
1.124 + Bytef *q; /* output window write pointer */
1.125 + uInt m; /* bytes to end of window or read pointer */
1.126 +
1.127 + /* copy input/output information to locals (UPDATE macro restores) */
1.128 + LOAD
1.129 +
1.130 + /* process input based on current state */
1.131 + while (1) switch (s->mode)
1.132 + {
1.133 + case TYPE:
1.134 + NEEDBITS(3)
1.135 + t = (uInt)b & 7;
1.136 + s->last = t & 1;
1.137 + switch (t >> 1)
1.138 + {
1.139 + case 0: /* stored */
1.140 + Tracev((stderr, "inflate: stored block%s\n",
1.141 + s->last ? " (last)" : ""));
1.142 + DUMPBITS(3)
1.143 + t = k & 7; /* go to byte boundary */
1.144 + DUMPBITS(t)
1.145 + s->mode = LENS; /* get length of stored block */
1.146 + break;
1.147 + case 1: /* fixed */
1.148 + Tracev((stderr, "inflate: fixed codes block%s\n",
1.149 + s->last ? " (last)" : ""));
1.150 + {
1.151 + uInt bl, bd;
1.152 + inflate_huft *tl, *td;
1.153 +
1.154 + inflate_trees_fixed(&bl, &bd, &tl, &td, z);
1.155 + s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z);
1.156 + if (s->sub.decode.codes == Z_NULL)
1.157 + {
1.158 + r = Z_MEM_ERROR;
1.159 + LEAVE
1.160 + }
1.161 + }
1.162 + DUMPBITS(3)
1.163 + s->mode = CODES;
1.164 + break;
1.165 + case 2: /* dynamic */
1.166 + Tracev((stderr, "inflate: dynamic codes block%s\n",
1.167 + s->last ? " (last)" : ""));
1.168 + DUMPBITS(3)
1.169 + s->mode = TABLE;
1.170 + break;
1.171 + case 3: /* illegal */
1.172 + DUMPBITS(3)
1.173 + s->mode = BAD;
1.174 + z->msg = (char*)"invalid block type";
1.175 + r = Z_DATA_ERROR;
1.176 + LEAVE
1.177 + }
1.178 + break;
1.179 + case LENS:
1.180 + NEEDBITS(32)
1.181 + if ((((~b) >> 16) & 0xffff) != (b & 0xffff))
1.182 + {
1.183 + s->mode = BAD;
1.184 + z->msg = (char*)"invalid stored block lengths";
1.185 + r = Z_DATA_ERROR;
1.186 + LEAVE
1.187 + }
1.188 + s->sub.left = (uInt)b & 0xffff;
1.189 + b = k = 0; /* dump bits */
1.190 + Tracev((stderr, "inflate: stored length %u\n", s->sub.left));
1.191 + s->mode = s->sub.left ? STORED : (s->last ? DRY : TYPE);
1.192 + break;
1.193 + case STORED:
1.194 + if (n == 0)
1.195 + LEAVE
1.196 + NEEDOUT
1.197 + t = s->sub.left;
1.198 + if (t > n) t = n;
1.199 + if (t > m) t = m;
1.200 + zmemcpy(q, p, t);
1.201 + p += t; n -= t;
1.202 + q += t; m -= t;
1.203 + if ((s->sub.left -= t) != 0)
1.204 + break;
1.205 + Tracev((stderr, "inflate: stored end, %lu total out\n",
1.206 + z->total_out + (q >= s->read ? q - s->read :
1.207 + (s->end - s->read) + (q - s->window))));
1.208 + s->mode = s->last ? DRY : TYPE;
1.209 + break;
1.210 + case TABLE:
1.211 + NEEDBITS(14)
1.212 + s->sub.trees.table = t = (uInt)b & 0x3fff;
1.213 +#ifndef PKZIP_BUG_WORKAROUND
1.214 + if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29)
1.215 + {
1.216 + s->mode = BAD;
1.217 + z->msg = (char*)"too many length or distance symbols";
1.218 + r = Z_DATA_ERROR;
1.219 + LEAVE
1.220 + }
1.221 +#endif
1.222 + t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f);
1.223 + if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL)
1.224 + {
1.225 + r = Z_MEM_ERROR;
1.226 + LEAVE
1.227 + }
1.228 + DUMPBITS(14)
1.229 + s->sub.trees.index = 0;
1.230 + Tracev((stderr, "inflate: table sizes ok\n"));
1.231 + s->mode = BTREE;
1.232 + case BTREE:
1.233 + while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10))
1.234 + {
1.235 + NEEDBITS(3)
1.236 + s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7;
1.237 + DUMPBITS(3)
1.238 + }
1.239 + while (s->sub.trees.index < 19)
1.240 + s->sub.trees.blens[border[s->sub.trees.index++]] = 0;
1.241 + s->sub.trees.bb = 7;
1.242 + t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb,
1.243 + &s->sub.trees.tb, s->hufts, z);
1.244 + if (t != Z_OK)
1.245 + {
1.246 + ZFREE(z, s->sub.trees.blens);
1.247 + r = t;
1.248 + if (r == Z_DATA_ERROR)
1.249 + s->mode = BAD;
1.250 + LEAVE
1.251 + }
1.252 + s->sub.trees.index = 0;
1.253 + Tracev((stderr, "inflate: bits tree ok\n"));
1.254 + s->mode = DTREE;
1.255 + case DTREE:
1.256 + while (t = s->sub.trees.table,
1.257 + s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f))
1.258 + {
1.259 + inflate_huft *h;
1.260 + uInt i, j, c;
1.261 +
1.262 + t = s->sub.trees.bb;
1.263 + NEEDBITS(t)
1.264 + h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]);
1.265 + t = h->bits;
1.266 + c = h->base;
1.267 + if (c < 16)
1.268 + {
1.269 + DUMPBITS(t)
1.270 + s->sub.trees.blens[s->sub.trees.index++] = c;
1.271 + }
1.272 + else /* c == 16..18 */
1.273 + {
1.274 + i = c == 18 ? 7 : c - 14;
1.275 + j = c == 18 ? 11 : 3;
1.276 + NEEDBITS(t + i)
1.277 + DUMPBITS(t)
1.278 + j += (uInt)b & inflate_mask[i];
1.279 + DUMPBITS(i)
1.280 + i = s->sub.trees.index;
1.281 + t = s->sub.trees.table;
1.282 + if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) ||
1.283 + (c == 16 && i < 1))
1.284 + {
1.285 + ZFREE(z, s->sub.trees.blens);
1.286 + s->mode = BAD;
1.287 + z->msg = (char*)"invalid bit length repeat";
1.288 + r = Z_DATA_ERROR;
1.289 + LEAVE
1.290 + }
1.291 + c = c == 16 ? s->sub.trees.blens[i - 1] : 0;
1.292 + do {
1.293 + s->sub.trees.blens[i++] = c;
1.294 + } while (--j);
1.295 + s->sub.trees.index = i;
1.296 + }
1.297 + }
1.298 + s->sub.trees.tb = Z_NULL;
1.299 + {
1.300 + uInt bl, bd;
1.301 + inflate_huft *tl, *td;
1.302 + inflate_codes_statef *c;
1.303 +
1.304 + bl = 9; /* must be <= 9 for lookahead assumptions */
1.305 + bd = 6; /* must be <= 9 for lookahead assumptions */
1.306 + t = s->sub.trees.table;
1.307 + t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f),
1.308 + s->sub.trees.blens, &bl, &bd, &tl, &td,
1.309 + s->hufts, z);
1.310 + ZFREE(z, s->sub.trees.blens);
1.311 + if (t != Z_OK)
1.312 + {
1.313 + if (t == (uInt)Z_DATA_ERROR)
1.314 + s->mode = BAD;
1.315 + r = t;
1.316 + LEAVE
1.317 + }
1.318 + Tracev((stderr, "inflate: trees ok\n"));
1.319 + if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL)
1.320 + {
1.321 + r = Z_MEM_ERROR;
1.322 + LEAVE
1.323 + }
1.324 + s->sub.decode.codes = c;
1.325 + }
1.326 + s->mode = CODES;
1.327 + case CODES:
1.328 + UPDATE
1.329 + if ((r = inflate_codes(s, z, r)) != Z_STREAM_END)
1.330 + return inflate_flush(s, z, r);
1.331 + r = Z_OK;
1.332 + inflate_codes_free(s->sub.decode.codes, z);
1.333 + LOAD
1.334 + Tracev((stderr, "inflate: codes end, %lu total out\n",
1.335 + z->total_out + (q >= s->read ? q - s->read :
1.336 + (s->end - s->read) + (q - s->window))));
1.337 + if (!s->last)
1.338 + {
1.339 + s->mode = TYPE;
1.340 + break;
1.341 + }
1.342 + s->mode = DRY;
1.343 + case DRY:
1.344 + FLUSH
1.345 + if (s->read != s->write)
1.346 + LEAVE
1.347 + s->mode = DONE;
1.348 + case DONE:
1.349 + r = Z_STREAM_END;
1.350 + LEAVE
1.351 + case BAD:
1.352 + r = Z_DATA_ERROR;
1.353 + LEAVE
1.354 + default:
1.355 + r = Z_STREAM_ERROR;
1.356 + LEAVE
1.357 + }
1.358 +}
1.359 +
1.360 +
1.361 +int inflate_blocks_free(inflate_blocks_statef *s, z_streamp z)
1.362 +{
1.363 + inflate_blocks_reset(s, z, Z_NULL);
1.364 + ZFREE(z, s->window);
1.365 + ZFREE(z, s->hufts);
1.366 + ZFREE(z, s);
1.367 + Tracev((stderr, "inflate: blocks freed\n"));
1.368 + return Z_OK;
1.369 +}
1.370 +
1.371 +
1.372 +void inflate_set_dictionary(inflate_blocks_statef *s, const Bytef *d, uInt n)
1.373 +{
1.374 + zmemcpy(s->window, d, n);
1.375 + s->read = s->write = s->window + n;
1.376 +}
1.377 +
1.378 +
1.379 +/* Returns true if inflate is currently at the end of a block generated
1.380 + * by Z_SYNC_FLUSH or Z_FULL_FLUSH.
1.381 + * IN assertion: s != Z_NULL
1.382 + */
1.383 +int inflate_blocks_sync_point(inflate_blocks_statef *s)
1.384 +{
1.385 + return s->mode == LENS;
1.386 +}