5128eecc9f 2011-02-23 kinaba: /* infcodes.c -- process literals and length/distance pairs 5128eecc9f 2011-02-23 kinaba: * Copyright (C) 1995-1998 Mark Adler 5128eecc9f 2011-02-23 kinaba: * For conditions of distribution and use, see copyright notice in zlib.h 5128eecc9f 2011-02-23 kinaba: */ 5128eecc9f 2011-02-23 kinaba: 5128eecc9f 2011-02-23 kinaba: #include "zutil.h" 5128eecc9f 2011-02-23 kinaba: #include "inftrees.h" 5128eecc9f 2011-02-23 kinaba: #include "infblock.h" 5128eecc9f 2011-02-23 kinaba: #include "infcodes.h" 5128eecc9f 2011-02-23 kinaba: #include "infutil.h" 5128eecc9f 2011-02-23 kinaba: #include "inffast.h" 5128eecc9f 2011-02-23 kinaba: 5128eecc9f 2011-02-23 kinaba: /* simplify the use of the inflate_huft type with some defines */ 5128eecc9f 2011-02-23 kinaba: #define exop word.what.Exop 5128eecc9f 2011-02-23 kinaba: #define bits word.what.Bits 5128eecc9f 2011-02-23 kinaba: 5128eecc9f 2011-02-23 kinaba: typedef enum { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */ 5128eecc9f 2011-02-23 kinaba: START, /* x: set up for LEN */ 5128eecc9f 2011-02-23 kinaba: LEN, /* i: get length/literal/eob next */ 5128eecc9f 2011-02-23 kinaba: LENEXT, /* i: getting length extra (have base) */ 5128eecc9f 2011-02-23 kinaba: DIST, /* i: get distance next */ 5128eecc9f 2011-02-23 kinaba: DISTEXT, /* i: getting distance extra */ 5128eecc9f 2011-02-23 kinaba: COPY, /* o: copying bytes in window, waiting for space */ 5128eecc9f 2011-02-23 kinaba: LIT, /* o: got literal, waiting for output space */ 5128eecc9f 2011-02-23 kinaba: WASH, /* o: got eob, possibly still output waiting */ 5128eecc9f 2011-02-23 kinaba: END, /* x: got eob and all data flushed */ 5128eecc9f 2011-02-23 kinaba: BADCODE} /* x: got error */ 5128eecc9f 2011-02-23 kinaba: inflate_codes_mode; 5128eecc9f 2011-02-23 kinaba: 5128eecc9f 2011-02-23 kinaba: /* inflate codes private state */ 5128eecc9f 2011-02-23 kinaba: struct inflate_codes_state { 5128eecc9f 2011-02-23 kinaba: 5128eecc9f 2011-02-23 kinaba: /* mode */ 5128eecc9f 2011-02-23 kinaba: inflate_codes_mode mode; /* current inflate_codes mode */ 5128eecc9f 2011-02-23 kinaba: 5128eecc9f 2011-02-23 kinaba: /* mode dependent information */ 5128eecc9f 2011-02-23 kinaba: uInt len; 5128eecc9f 2011-02-23 kinaba: union { 5128eecc9f 2011-02-23 kinaba: struct { 5128eecc9f 2011-02-23 kinaba: inflate_huft *tree; /* pointer into tree */ 5128eecc9f 2011-02-23 kinaba: uInt need; /* bits needed */ 5128eecc9f 2011-02-23 kinaba: } code; /* if LEN or DIST, where in tree */ 5128eecc9f 2011-02-23 kinaba: uInt lit; /* if LIT, literal */ 5128eecc9f 2011-02-23 kinaba: struct { 5128eecc9f 2011-02-23 kinaba: uInt get; /* bits to get for extra */ 5128eecc9f 2011-02-23 kinaba: uInt dist; /* distance back to copy from */ 5128eecc9f 2011-02-23 kinaba: } copy; /* if EXT or COPY, where and how much */ 5128eecc9f 2011-02-23 kinaba: } sub; /* submode */ 5128eecc9f 2011-02-23 kinaba: 5128eecc9f 2011-02-23 kinaba: /* mode independent information */ 5128eecc9f 2011-02-23 kinaba: Byte lbits; /* ltree bits decoded per branch */ 5128eecc9f 2011-02-23 kinaba: Byte dbits; /* dtree bits decoder per branch */ 5128eecc9f 2011-02-23 kinaba: inflate_huft *ltree; /* literal/length/eob tree */ 5128eecc9f 2011-02-23 kinaba: inflate_huft *dtree; /* distance tree */ 5128eecc9f 2011-02-23 kinaba: 5128eecc9f 2011-02-23 kinaba: }; 5128eecc9f 2011-02-23 kinaba: 5128eecc9f 2011-02-23 kinaba: 5128eecc9f 2011-02-23 kinaba: inflate_codes_statef *inflate_codes_new(bl, bd, tl, td, z) 5128eecc9f 2011-02-23 kinaba: uInt bl, bd; 5128eecc9f 2011-02-23 kinaba: inflate_huft *tl; 5128eecc9f 2011-02-23 kinaba: inflate_huft *td; /* need separate declaration for Borland C++ */ 5128eecc9f 2011-02-23 kinaba: z_streamp z; 5128eecc9f 2011-02-23 kinaba: { 5128eecc9f 2011-02-23 kinaba: inflate_codes_statef *c; 5128eecc9f 2011-02-23 kinaba: 5128eecc9f 2011-02-23 kinaba: if ((c = (inflate_codes_statef *) 5128eecc9f 2011-02-23 kinaba: ZALLOC(z,1,sizeof(struct inflate_codes_state))) != Z_NULL) 5128eecc9f 2011-02-23 kinaba: { 5128eecc9f 2011-02-23 kinaba: c->mode = START; 5128eecc9f 2011-02-23 kinaba: c->lbits = (Byte)bl; 5128eecc9f 2011-02-23 kinaba: c->dbits = (Byte)bd; 5128eecc9f 2011-02-23 kinaba: c->ltree = tl; 5128eecc9f 2011-02-23 kinaba: c->dtree = td; 5128eecc9f 2011-02-23 kinaba: Tracev((stderr, "inflate: codes new\n")); 5128eecc9f 2011-02-23 kinaba: } 5128eecc9f 2011-02-23 kinaba: return c; 5128eecc9f 2011-02-23 kinaba: } 5128eecc9f 2011-02-23 kinaba: 5128eecc9f 2011-02-23 kinaba: 5128eecc9f 2011-02-23 kinaba: int inflate_codes(s, z, r) 5128eecc9f 2011-02-23 kinaba: inflate_blocks_statef *s; 5128eecc9f 2011-02-23 kinaba: z_streamp z; 5128eecc9f 2011-02-23 kinaba: int r; 5128eecc9f 2011-02-23 kinaba: { 5128eecc9f 2011-02-23 kinaba: uInt j; /* temporary storage */ 5128eecc9f 2011-02-23 kinaba: inflate_huft *t; /* temporary pointer */ 5128eecc9f 2011-02-23 kinaba: uInt e; /* extra bits or operation */ 5128eecc9f 2011-02-23 kinaba: uLong b; /* bit buffer */ 5128eecc9f 2011-02-23 kinaba: uInt k; /* bits in bit buffer */ 5128eecc9f 2011-02-23 kinaba: Bytef *p; /* input data pointer */ 5128eecc9f 2011-02-23 kinaba: uInt n; /* bytes available there */ 5128eecc9f 2011-02-23 kinaba: Bytef *q; /* output window write pointer */ 5128eecc9f 2011-02-23 kinaba: uInt m; /* bytes to end of window or read pointer */ 5128eecc9f 2011-02-23 kinaba: Bytef *f; /* pointer to copy strings from */ 5128eecc9f 2011-02-23 kinaba: inflate_codes_statef *c = s->sub.decode.codes; /* codes state */ 5128eecc9f 2011-02-23 kinaba: 5128eecc9f 2011-02-23 kinaba: /* copy input/output information to locals (UPDATE macro restores) */ 5128eecc9f 2011-02-23 kinaba: LOAD 5128eecc9f 2011-02-23 kinaba: 5128eecc9f 2011-02-23 kinaba: /* process input and output based on current state */ 5128eecc9f 2011-02-23 kinaba: while (1) switch (c->mode) 5128eecc9f 2011-02-23 kinaba: { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */ 5128eecc9f 2011-02-23 kinaba: case START: /* x: set up for LEN */ 5128eecc9f 2011-02-23 kinaba: #ifndef SLOW 5128eecc9f 2011-02-23 kinaba: if (m >= 258 && n >= 10) 5128eecc9f 2011-02-23 kinaba: { 5128eecc9f 2011-02-23 kinaba: UPDATE 5128eecc9f 2011-02-23 kinaba: r = inflate_fast(c->lbits, c->dbits, c->ltree, c->dtree, s, z); 5128eecc9f 2011-02-23 kinaba: LOAD 5128eecc9f 2011-02-23 kinaba: if (r != Z_OK) 5128eecc9f 2011-02-23 kinaba: { 5128eecc9f 2011-02-23 kinaba: c->mode = r == Z_STREAM_END ? WASH : BADCODE; 5128eecc9f 2011-02-23 kinaba: break; 5128eecc9f 2011-02-23 kinaba: } 5128eecc9f 2011-02-23 kinaba: } 5128eecc9f 2011-02-23 kinaba: #endif /* !SLOW */ 5128eecc9f 2011-02-23 kinaba: c->sub.code.need = c->lbits; 5128eecc9f 2011-02-23 kinaba: c->sub.code.tree = c->ltree; 5128eecc9f 2011-02-23 kinaba: c->mode = LEN; 5128eecc9f 2011-02-23 kinaba: case LEN: /* i: get length/literal/eob next */ 5128eecc9f 2011-02-23 kinaba: j = c->sub.code.need; 5128eecc9f 2011-02-23 kinaba: NEEDBITS(j) 5128eecc9f 2011-02-23 kinaba: t = c->sub.code.tree + ((uInt)b & inflate_mask[j]); 5128eecc9f 2011-02-23 kinaba: DUMPBITS(t->bits) 5128eecc9f 2011-02-23 kinaba: e = (uInt)(t->exop); 5128eecc9f 2011-02-23 kinaba: if (e == 0) /* literal */ 5128eecc9f 2011-02-23 kinaba: { 5128eecc9f 2011-02-23 kinaba: c->sub.lit = t->base; 5128eecc9f 2011-02-23 kinaba: Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ? 5128eecc9f 2011-02-23 kinaba: "inflate: literal '%c'\n" : 5128eecc9f 2011-02-23 kinaba: "inflate: literal 0x%02x\n", t->base)); 5128eecc9f 2011-02-23 kinaba: c->mode = LIT; 5128eecc9f 2011-02-23 kinaba: break; 5128eecc9f 2011-02-23 kinaba: } 5128eecc9f 2011-02-23 kinaba: if (e & 16) /* length */ 5128eecc9f 2011-02-23 kinaba: { 5128eecc9f 2011-02-23 kinaba: c->sub.copy.get = e & 15; 5128eecc9f 2011-02-23 kinaba: c->len = t->base; 5128eecc9f 2011-02-23 kinaba: c->mode = LENEXT; 5128eecc9f 2011-02-23 kinaba: break; 5128eecc9f 2011-02-23 kinaba: } 5128eecc9f 2011-02-23 kinaba: if ((e & 64) == 0) /* next table */ 5128eecc9f 2011-02-23 kinaba: { 5128eecc9f 2011-02-23 kinaba: c->sub.code.need = e; 5128eecc9f 2011-02-23 kinaba: c->sub.code.tree = t + t->base; 5128eecc9f 2011-02-23 kinaba: break; 5128eecc9f 2011-02-23 kinaba: } 5128eecc9f 2011-02-23 kinaba: if (e & 32) /* end of block */ 5128eecc9f 2011-02-23 kinaba: { 5128eecc9f 2011-02-23 kinaba: Tracevv((stderr, "inflate: end of block\n")); 5128eecc9f 2011-02-23 kinaba: c->mode = WASH; 5128eecc9f 2011-02-23 kinaba: break; 5128eecc9f 2011-02-23 kinaba: } 5128eecc9f 2011-02-23 kinaba: c->mode = BADCODE; /* invalid code */ 5128eecc9f 2011-02-23 kinaba: z->msg = (char*)"invalid literal/length code"; 5128eecc9f 2011-02-23 kinaba: r = Z_DATA_ERROR; 5128eecc9f 2011-02-23 kinaba: LEAVE 5128eecc9f 2011-02-23 kinaba: case LENEXT: /* i: getting length extra (have base) */ 5128eecc9f 2011-02-23 kinaba: j = c->sub.copy.get; 5128eecc9f 2011-02-23 kinaba: NEEDBITS(j) 5128eecc9f 2011-02-23 kinaba: c->len += (uInt)b & inflate_mask[j]; 5128eecc9f 2011-02-23 kinaba: DUMPBITS(j) 5128eecc9f 2011-02-23 kinaba: c->sub.code.need = c->dbits; 5128eecc9f 2011-02-23 kinaba: c->sub.code.tree = c->dtree; 5128eecc9f 2011-02-23 kinaba: Tracevv((stderr, "inflate: length %u\n", c->len)); 5128eecc9f 2011-02-23 kinaba: c->mode = DIST; 5128eecc9f 2011-02-23 kinaba: case DIST: /* i: get distance next */ 5128eecc9f 2011-02-23 kinaba: j = c->sub.code.need; 5128eecc9f 2011-02-23 kinaba: NEEDBITS(j) 5128eecc9f 2011-02-23 kinaba: t = c->sub.code.tree + ((uInt)b & inflate_mask[j]); 5128eecc9f 2011-02-23 kinaba: DUMPBITS(t->bits) 5128eecc9f 2011-02-23 kinaba: e = (uInt)(t->exop); 5128eecc9f 2011-02-23 kinaba: if (e & 16) /* distance */ 5128eecc9f 2011-02-23 kinaba: { 5128eecc9f 2011-02-23 kinaba: c->sub.copy.get = e & 15; 5128eecc9f 2011-02-23 kinaba: c->sub.copy.dist = t->base; 5128eecc9f 2011-02-23 kinaba: c->mode = DISTEXT; 5128eecc9f 2011-02-23 kinaba: break; 5128eecc9f 2011-02-23 kinaba: } 5128eecc9f 2011-02-23 kinaba: if ((e & 64) == 0) /* next table */ 5128eecc9f 2011-02-23 kinaba: { 5128eecc9f 2011-02-23 kinaba: c->sub.code.need = e; 5128eecc9f 2011-02-23 kinaba: c->sub.code.tree = t + t->base; 5128eecc9f 2011-02-23 kinaba: break; 5128eecc9f 2011-02-23 kinaba: } 5128eecc9f 2011-02-23 kinaba: c->mode = BADCODE; /* invalid code */ 5128eecc9f 2011-02-23 kinaba: z->msg = (char*)"invalid distance code"; 5128eecc9f 2011-02-23 kinaba: r = Z_DATA_ERROR; 5128eecc9f 2011-02-23 kinaba: LEAVE 5128eecc9f 2011-02-23 kinaba: case DISTEXT: /* i: getting distance extra */ 5128eecc9f 2011-02-23 kinaba: j = c->sub.copy.get; 5128eecc9f 2011-02-23 kinaba: NEEDBITS(j) 5128eecc9f 2011-02-23 kinaba: c->sub.copy.dist += (uInt)b & inflate_mask[j]; 5128eecc9f 2011-02-23 kinaba: DUMPBITS(j) 5128eecc9f 2011-02-23 kinaba: Tracevv((stderr, "inflate: distance %u\n", c->sub.copy.dist)); 5128eecc9f 2011-02-23 kinaba: c->mode = COPY; 5128eecc9f 2011-02-23 kinaba: case COPY: /* o: copying bytes in window, waiting for space */ 5128eecc9f 2011-02-23 kinaba: #ifndef __TURBOC__ /* Turbo C bug for following expression */ 5128eecc9f 2011-02-23 kinaba: f = (uInt)(q - s->window) < c->sub.copy.dist ? 5128eecc9f 2011-02-23 kinaba: s->end - (c->sub.copy.dist - (q - s->window)) : 5128eecc9f 2011-02-23 kinaba: q - c->sub.copy.dist; 5128eecc9f 2011-02-23 kinaba: #else 5128eecc9f 2011-02-23 kinaba: f = q - c->sub.copy.dist; 5128eecc9f 2011-02-23 kinaba: if ((uInt)(q - s->window) < c->sub.copy.dist) 5128eecc9f 2011-02-23 kinaba: f = s->end - (c->sub.copy.dist - (uInt)(q - s->window)); 5128eecc9f 2011-02-23 kinaba: #endif 5128eecc9f 2011-02-23 kinaba: while (c->len) 5128eecc9f 2011-02-23 kinaba: { 5128eecc9f 2011-02-23 kinaba: NEEDOUT 5128eecc9f 2011-02-23 kinaba: OUTBYTE(*f++) 5128eecc9f 2011-02-23 kinaba: if (f == s->end) 5128eecc9f 2011-02-23 kinaba: f = s->window; 5128eecc9f 2011-02-23 kinaba: c->len--; 5128eecc9f 2011-02-23 kinaba: } 5128eecc9f 2011-02-23 kinaba: c->mode = START; 5128eecc9f 2011-02-23 kinaba: break; 5128eecc9f 2011-02-23 kinaba: case LIT: /* o: got literal, waiting for output space */ 5128eecc9f 2011-02-23 kinaba: NEEDOUT 5128eecc9f 2011-02-23 kinaba: OUTBYTE(c->sub.lit) 5128eecc9f 2011-02-23 kinaba: c->mode = START; 5128eecc9f 2011-02-23 kinaba: break; 5128eecc9f 2011-02-23 kinaba: case WASH: /* o: got eob, possibly more output */ 5128eecc9f 2011-02-23 kinaba: if (k > 7) /* return unused byte, if any */ 5128eecc9f 2011-02-23 kinaba: { 5128eecc9f 2011-02-23 kinaba: Assert(k < 16, "inflate_codes grabbed too many bytes") 5128eecc9f 2011-02-23 kinaba: k -= 8; 5128eecc9f 2011-02-23 kinaba: n++; 5128eecc9f 2011-02-23 kinaba: p--; /* can always return one */ 5128eecc9f 2011-02-23 kinaba: } 5128eecc9f 2011-02-23 kinaba: FLUSH 5128eecc9f 2011-02-23 kinaba: if (s->read != s->write) 5128eecc9f 2011-02-23 kinaba: LEAVE 5128eecc9f 2011-02-23 kinaba: c->mode = END; 5128eecc9f 2011-02-23 kinaba: case END: 5128eecc9f 2011-02-23 kinaba: r = Z_STREAM_END; 5128eecc9f 2011-02-23 kinaba: LEAVE 5128eecc9f 2011-02-23 kinaba: case BADCODE: /* x: got error */ 5128eecc9f 2011-02-23 kinaba: r = Z_DATA_ERROR; 5128eecc9f 2011-02-23 kinaba: LEAVE 5128eecc9f 2011-02-23 kinaba: default: 5128eecc9f 2011-02-23 kinaba: r = Z_STREAM_ERROR; 5128eecc9f 2011-02-23 kinaba: LEAVE 5128eecc9f 2011-02-23 kinaba: } 5128eecc9f 2011-02-23 kinaba: #ifdef NEED_DUMMY_RETURN 5128eecc9f 2011-02-23 kinaba: return Z_STREAM_ERROR; /* Some dumb compilers complain without this */ 5128eecc9f 2011-02-23 kinaba: #endif 5128eecc9f 2011-02-23 kinaba: } 5128eecc9f 2011-02-23 kinaba: 5128eecc9f 2011-02-23 kinaba: 5128eecc9f 2011-02-23 kinaba: void inflate_codes_free(c, z) 5128eecc9f 2011-02-23 kinaba: inflate_codes_statef *c; 5128eecc9f 2011-02-23 kinaba: z_streamp z; 5128eecc9f 2011-02-23 kinaba: { 5128eecc9f 2011-02-23 kinaba: ZFREE(z, c); 5128eecc9f 2011-02-23 kinaba: Tracev((stderr, "inflate: codes free\n")); 5128eecc9f 2011-02-23 kinaba: }