| /* infblock.c -- interpret and process block types to last block |
| * Copyright (C) 1995-2002 Mark Adler |
| * For conditions of distribution and use, see copyright notice in zlib.h |
| */ |
| |
| #include "zutil.h" |
| #include "infblock.h" |
| #include "inftrees.h" |
| #include "infcodes.h" |
| #include "infutil.h" |
| |
| |
| /* simplify the use of the inflate_huft type with some defines */ |
| #define exop word.what.Exop |
| #define bits word.what.Bits |
| |
| /* Table for deflate from PKZIP's appnote.txt. */ |
| local const uInt border[] = { /* Order of the bit length code lengths */ |
| 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; |
| |
| /* |
| Notes beyond the 1.93a appnote.txt: |
| |
| 1. Distance pointers never point before the beginning of the output |
| stream. |
| 2. Distance pointers can point back across blocks, up to 32k away. |
| 3. There is an implied maximum of 7 bits for the bit length table and |
| 15 bits for the actual data. |
| 4. If only one code exists, then it is encoded using one bit. (Zero |
| would be more efficient, but perhaps a little confusing.) If two |
| codes exist, they are coded using one bit each (0 and 1). |
| 5. There is no way of sending zero distance codes--a dummy must be |
| sent if there are none. (History: a pre 2.0 version of PKZIP would |
| store blocks with no distance codes, but this was discovered to be |
| too harsh a criterion.) Valid only for 1.93a. 2.04c does allow |
| zero distance codes, which is sent as one code of zero bits in |
| length. |
| 6. There are up to 286 literal/length codes. Code 256 represents the |
| end-of-block. Note however that the static length tree defines |
| 288 codes just to fill out the Huffman codes. Codes 286 and 287 |
| cannot be used though, since there is no length base or extra bits |
| defined for them. Similarily, there are up to 30 distance codes. |
| However, static trees define 32 codes (all 5 bits) to fill out the |
| Huffman codes, but the last two had better not show up in the data. |
| 7. Unzip can check dynamic Huffman blocks for complete code sets. |
| The exception is that a single code would not be complete (see #4). |
| 8. The five bits following the block type is really the number of |
| literal codes sent minus 257. |
| 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits |
| (1+6+6). Therefore, to output three times the length, you output |
| three codes (1+1+1), whereas to output four times the same length, |
| you only need two codes (1+3). Hmm. |
| 10. In the tree reconstruction algorithm, Code = Code + Increment |
| only if BitLength(i) is not zero. (Pretty obvious.) |
| 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19) |
| 12. Note: length code 284 can represent 227-258, but length code 285 |
| really is 258. The last length deserves its own, short code |
| since it gets used a lot in very redundant files. The length |
| 258 is special since 258 - 3 (the min match length) is 255. |
| 13. The literal/length and distance code bit lengths are read as a |
| single stream of lengths. It is possible (and advantageous) for |
| a repeat code (16, 17, or 18) to go across the boundary between |
| the two sets of lengths. |
| */ |
| |
| |
| local void inflate_blocks_reset( /* s, z, c) */ |
| inflate_blocks_statef *s, |
| z_streamp z, |
| uLongf *c ) |
| { |
| if (c != Z_NULL) |
| *c = s->check; |
| if (s->mode == BTREE || s->mode == DTREE) |
| ZFREE(z, s->sub.trees.blens); |
| if (s->mode == CODES) |
| inflate_codes_free(s->sub.decode.codes, z); |
| s->mode = TYPE; |
| s->bitk = 0; |
| s->bitb = 0; |
| s->read = s->write = s->window; |
| if (s->checkfn != Z_NULL) |
| z->adler = s->check = (*s->checkfn)(0L, (const Bytef *)Z_NULL, 0); |
| Tracev((stderr, "inflate: blocks reset\n")); |
| } |
| |
| |
| local inflate_blocks_statef *inflate_blocks_new( /* z, c, w) */ |
| z_streamp z, |
| check_func c, |
| uInt w ) |
| { |
| inflate_blocks_statef *s; |
| |
| if ((s = (inflate_blocks_statef *)ZALLOC |
| (z,1,sizeof(struct inflate_blocks_state))) == Z_NULL) |
| return s; |
| if ((s->hufts = |
| (inflate_huft *)ZALLOC(z, sizeof(inflate_huft), MANY)) == Z_NULL) |
| { |
| ZFREE(z, s); |
| return Z_NULL; |
| } |
| if ((s->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL) |
| { |
| ZFREE(z, s->hufts); |
| ZFREE(z, s); |
| return Z_NULL; |
| } |
| s->end = s->window + w; |
| s->checkfn = c; |
| s->mode = TYPE; |
| Tracev((stderr, "inflate: blocks allocated\n")); |
| inflate_blocks_reset(s, z, Z_NULL); |
| return s; |
| } |
| |
| |
| local int inflate_blocks( /* s, z, r) */ |
| inflate_blocks_statef *s, |
| z_streamp z, |
| int r ) |
| { |
| uInt t; /* temporary storage */ |
| uLong b; /* bit buffer */ |
| uInt k; /* bits in bit buffer */ |
| Bytef *p; /* input data pointer */ |
| uInt n; /* bytes available there */ |
| Bytef *q; /* output window write pointer */ |
| uInt m; /* bytes to end of window or read pointer */ |
| |
| /* copy input/output information to locals (UPDATE macro restores) */ |
| LOAD |
| |
| /* process input based on current state */ |
| while (1) switch (s->mode) |
| { |
| case TYPE: |
| NEEDBITS(3) |
| t = (uInt)b & 7; |
| s->last = t & 1; |
| switch (t >> 1) |
| { |
| case 0: /* stored */ |
| Tracev((stderr, "inflate: stored block%s\n", |
| s->last ? " (last)" : "")); |
| DUMPBITS(3) |
| t = k & 7; /* go to byte boundary */ |
| DUMPBITS(t) |
| s->mode = LENS; /* get length of stored block */ |
| break; |
| case 1: /* fixed */ |
| Tracev((stderr, "inflate: fixed codes block%s\n", |
| s->last ? " (last)" : "")); |
| { |
| uInt bl, bd; |
| inflate_huft *tl, *td; |
| |
| inflate_trees_fixed(&bl, &bd, (const inflate_huft**)&tl, |
| (const inflate_huft**)&td, z); |
| s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z); |
| if (s->sub.decode.codes == Z_NULL) |
| { |
| r = Z_MEM_ERROR; |
| LEAVE |
| } |
| } |
| DUMPBITS(3) |
| s->mode = CODES; |
| break; |
| case 2: /* dynamic */ |
| Tracev((stderr, "inflate: dynamic codes block%s\n", |
| s->last ? " (last)" : "")); |
| DUMPBITS(3) |
| s->mode = TABLE; |
| break; |
| case 3: /* illegal */ |
| DUMPBITS(3) |
| s->mode = BAD; |
| z->msg = (char*)"invalid block type"; |
| r = Z_DATA_ERROR; |
| LEAVE |
| } |
| break; |
| case LENS: |
| NEEDBITS(32) |
| if ((((~b) >> 16) & 0xffff) != (b & 0xffff)) |
| { |
| s->mode = BAD; |
| z->msg = (char*)"invalid stored block lengths"; |
| r = Z_DATA_ERROR; |
| LEAVE |
| } |
| s->sub.left = (uInt)b & 0xffff; |
| b = k = 0; /* dump bits */ |
| Tracev((stderr, "inflate: stored length %u\n", s->sub.left)); |
| s->mode = s->sub.left ? STORED : (s->last ? DRY : TYPE); |
| break; |
| case STORED: |
| if (n == 0) |
| LEAVE |
| NEEDOUT |
| t = s->sub.left; |
| if (t > n) t = n; |
| if (t > m) t = m; |
| zmemcpy(q, p, t); |
| p += t; n -= t; |
| q += t; m -= t; |
| if ((s->sub.left -= t) != 0) |
| break; |
| Tracev((stderr, "inflate: stored end, %lu total out\n", |
| z->total_out + (q >= s->read ? q - s->read : |
| (s->end - s->read) + (q - s->window)))); |
| s->mode = s->last ? DRY : TYPE; |
| break; |
| case TABLE: |
| NEEDBITS(14) |
| s->sub.trees.table = t = (uInt)b & 0x3fff; |
| #ifndef PKZIP_BUG_WORKAROUND |
| if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29) |
| { |
| s->mode = BAD; |
| z->msg = (char*)"too many length or distance symbols"; |
| r = Z_DATA_ERROR; |
| LEAVE |
| } |
| #endif |
| t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f); |
| if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL) |
| { |
| r = Z_MEM_ERROR; |
| LEAVE |
| } |
| DUMPBITS(14) |
| s->sub.trees.index = 0; |
| Tracev((stderr, "inflate: table sizes ok\n")); |
| s->mode = BTREE; |
| case BTREE: |
| while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10)) |
| { |
| NEEDBITS(3) |
| s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7; |
| DUMPBITS(3) |
| } |
| while (s->sub.trees.index < 19) |
| s->sub.trees.blens[border[s->sub.trees.index++]] = 0; |
| s->sub.trees.bb = 7; |
| t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb, |
| &s->sub.trees.tb, s->hufts, z); |
| if (t != Z_OK) |
| { |
| r = t; |
| if (r == Z_DATA_ERROR) |
| { |
| ZFREE(z, s->sub.trees.blens); |
| s->mode = BAD; |
| } |
| LEAVE |
| } |
| s->sub.trees.index = 0; |
| Tracev((stderr, "inflate: bits tree ok\n")); |
| s->mode = DTREE; |
| case DTREE: |
| while (t = s->sub.trees.table, |
| s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f)) |
| { |
| inflate_huft *h; |
| uInt i, j, c; |
| |
| t = s->sub.trees.bb; |
| NEEDBITS(t) |
| h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]); |
| t = h->bits; |
| c = h->base; |
| if (c < 16) |
| { |
| DUMPBITS(t) |
| s->sub.trees.blens[s->sub.trees.index++] = c; |
| } |
| else /* c == 16..18 */ |
| { |
| i = c == 18 ? 7 : c - 14; |
| j = c == 18 ? 11 : 3; |
| NEEDBITS(t + i) |
| DUMPBITS(t) |
| j += (uInt)b & inflate_mask[i]; |
| DUMPBITS(i) |
| i = s->sub.trees.index; |
| t = s->sub.trees.table; |
| if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) || |
| (c == 16 && i < 1)) |
| { |
| ZFREE(z, s->sub.trees.blens); |
| s->mode = BAD; |
| z->msg = (char*)"invalid bit length repeat"; |
| r = Z_DATA_ERROR; |
| LEAVE |
| } |
| c = c == 16 ? s->sub.trees.blens[i - 1] : 0; |
| do { |
| s->sub.trees.blens[i++] = c; |
| } while (--j); |
| s->sub.trees.index = i; |
| } |
| } |
| s->sub.trees.tb = Z_NULL; |
| { |
| uInt bl, bd; |
| inflate_huft *tl, *td; |
| inflate_codes_statef *c; |
| |
| bl = 9; /* must be <= 9 for lookahead assumptions */ |
| bd = 6; /* must be <= 9 for lookahead assumptions */ |
| t = s->sub.trees.table; |
| t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f), |
| s->sub.trees.blens, &bl, &bd, &tl, &td, |
| s->hufts, z); |
| if (t != Z_OK) |
| { |
| if (t == (uInt)Z_DATA_ERROR) |
| { |
| ZFREE(z, s->sub.trees.blens); |
| s->mode = BAD; |
| } |
| r = t; |
| LEAVE |
| } |
| Tracev((stderr, "inflate: trees ok\n")); |
| if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL) |
| { |
| r = Z_MEM_ERROR; |
| LEAVE |
| } |
| s->sub.decode.codes = c; |
| } |
| ZFREE(z, s->sub.trees.blens); |
| s->mode = CODES; |
| case CODES: |
| UPDATE |
| if ((r = inflate_codes(s, z, r)) != Z_STREAM_END) |
| return inflate_flush(s, z, r); |
| r = Z_OK; |
| inflate_codes_free(s->sub.decode.codes, z); |
| LOAD |
| Tracev((stderr, "inflate: codes end, %lu total out\n", |
| z->total_out + (q >= s->read ? q - s->read : |
| (s->end - s->read) + (q - s->window)))); |
| if (!s->last) |
| { |
| s->mode = TYPE; |
| break; |
| } |
| s->mode = DRY; |
| case DRY: |
| FLUSH |
| if (s->read != s->write) |
| LEAVE |
| s->mode = DONE; |
| case DONE: |
| r = Z_STREAM_END; |
| LEAVE |
| case BAD: |
| r = Z_DATA_ERROR; |
| LEAVE |
| default: |
| r = Z_STREAM_ERROR; |
| LEAVE |
| } |
| #ifdef NEED_DUMMY_RETURN |
| return 0; |
| #endif |
| } |
| |
| |
| local int inflate_blocks_free( /* s, z) */ |
| inflate_blocks_statef *s, |
| z_streamp z ) |
| { |
| inflate_blocks_reset(s, z, Z_NULL); |
| ZFREE(z, s->window); |
| ZFREE(z, s->hufts); |
| ZFREE(z, s); |
| Tracev((stderr, "inflate: blocks freed\n")); |
| return Z_OK; |
| } |
| |
| |