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