5128eecc9f 2011-02-23 kinaba: /* inffast.c -- process literals and length/distance pairs fast 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: struct inflate_codes_state {int dummy;}; /* for buggy compilers */ 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: /* macros for bit input with no checking and for returning unused bytes */ 5128eecc9f 2011-02-23 kinaba: #define GRABBITS(j) {while(k<(j)){b|=((uLong)NEXTBYTE)<<k;k+=8;}} 5128eecc9f 2011-02-23 kinaba: #define UNGRAB {c=z->avail_in-n;c=(k>>3)<c?k>>3:c;n+=c;p-=c;k-=c<<3;} 5128eecc9f 2011-02-23 kinaba: 5128eecc9f 2011-02-23 kinaba: /* Called with number of bytes left to write in window at least 258 5128eecc9f 2011-02-23 kinaba: (the maximum string length) and number of input bytes available 5128eecc9f 2011-02-23 kinaba: at least ten. The ten bytes are six bytes for the longest length/ 5128eecc9f 2011-02-23 kinaba: distance pair plus four bytes for overloading the bit buffer. */ 5128eecc9f 2011-02-23 kinaba: 5128eecc9f 2011-02-23 kinaba: int inflate_fast(bl, bd, tl, td, s, 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: inflate_blocks_statef *s; 5128eecc9f 2011-02-23 kinaba: z_streamp z; 5128eecc9f 2011-02-23 kinaba: { 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: uInt ml; /* mask for literal/length tree */ 5128eecc9f 2011-02-23 kinaba: uInt md; /* mask for distance tree */ 5128eecc9f 2011-02-23 kinaba: uInt c; /* bytes to copy */ 5128eecc9f 2011-02-23 kinaba: uInt d; /* distance back to copy from */ 5128eecc9f 2011-02-23 kinaba: Bytef *r; /* copy source pointer */ 5128eecc9f 2011-02-23 kinaba: 5128eecc9f 2011-02-23 kinaba: /* load input, output, bit values */ 5128eecc9f 2011-02-23 kinaba: LOAD 5128eecc9f 2011-02-23 kinaba: 5128eecc9f 2011-02-23 kinaba: /* initialize masks */ 5128eecc9f 2011-02-23 kinaba: ml = inflate_mask[bl]; 5128eecc9f 2011-02-23 kinaba: md = inflate_mask[bd]; 5128eecc9f 2011-02-23 kinaba: 5128eecc9f 2011-02-23 kinaba: /* do until not enough input or output space for fast loop */ 5128eecc9f 2011-02-23 kinaba: do { /* assume called with m >= 258 && n >= 10 */ 5128eecc9f 2011-02-23 kinaba: /* get literal/length code */ 5128eecc9f 2011-02-23 kinaba: GRABBITS(20) /* max bits for literal/length code */ 5128eecc9f 2011-02-23 kinaba: if ((e = (t = tl + ((uInt)b & ml))->exop) == 0) 5128eecc9f 2011-02-23 kinaba: { 5128eecc9f 2011-02-23 kinaba: DUMPBITS(t->bits) 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: *q++ = (Byte)t->base; 5128eecc9f 2011-02-23 kinaba: m--; 5128eecc9f 2011-02-23 kinaba: continue; 5128eecc9f 2011-02-23 kinaba: } 5128eecc9f 2011-02-23 kinaba: do { 5128eecc9f 2011-02-23 kinaba: DUMPBITS(t->bits) 5128eecc9f 2011-02-23 kinaba: if (e & 16) 5128eecc9f 2011-02-23 kinaba: { 5128eecc9f 2011-02-23 kinaba: /* get extra bits for length */ 5128eecc9f 2011-02-23 kinaba: e &= 15; 5128eecc9f 2011-02-23 kinaba: c = t->base + ((uInt)b & inflate_mask[e]); 5128eecc9f 2011-02-23 kinaba: DUMPBITS(e) 5128eecc9f 2011-02-23 kinaba: Tracevv((stderr, "inflate: * length %u\n", c)); 5128eecc9f 2011-02-23 kinaba: 5128eecc9f 2011-02-23 kinaba: /* decode distance base of block to copy */ 5128eecc9f 2011-02-23 kinaba: GRABBITS(15); /* max bits for distance code */ 5128eecc9f 2011-02-23 kinaba: e = (t = td + ((uInt)b & md))->exop; 5128eecc9f 2011-02-23 kinaba: do { 5128eecc9f 2011-02-23 kinaba: DUMPBITS(t->bits) 5128eecc9f 2011-02-23 kinaba: if (e & 16) 5128eecc9f 2011-02-23 kinaba: { 5128eecc9f 2011-02-23 kinaba: /* get extra bits to add to distance base */ 5128eecc9f 2011-02-23 kinaba: e &= 15; 5128eecc9f 2011-02-23 kinaba: GRABBITS(e) /* get extra bits (up to 13) */ 5128eecc9f 2011-02-23 kinaba: d = t->base + ((uInt)b & inflate_mask[e]); 5128eecc9f 2011-02-23 kinaba: DUMPBITS(e) 5128eecc9f 2011-02-23 kinaba: Tracevv((stderr, "inflate: * distance %u\n", d)); 5128eecc9f 2011-02-23 kinaba: 5128eecc9f 2011-02-23 kinaba: /* do the copy */ 5128eecc9f 2011-02-23 kinaba: m -= c; 5128eecc9f 2011-02-23 kinaba: if ((uInt)(q - s->window) >= d) /* offset before dest */ 5128eecc9f 2011-02-23 kinaba: { /* just copy */ 5128eecc9f 2011-02-23 kinaba: r = q - d; 5128eecc9f 2011-02-23 kinaba: *q++ = *r++; c--; /* minimum count is three, */ 5128eecc9f 2011-02-23 kinaba: *q++ = *r++; c--; /* so unroll loop a little */ 5128eecc9f 2011-02-23 kinaba: } 5128eecc9f 2011-02-23 kinaba: else /* else offset after destination */ 5128eecc9f 2011-02-23 kinaba: { 5128eecc9f 2011-02-23 kinaba: e = d - (uInt)(q - s->window); /* bytes from offset to end */ 5128eecc9f 2011-02-23 kinaba: r = s->end - e; /* pointer to offset */ 5128eecc9f 2011-02-23 kinaba: if (c > e) /* if source crosses, */ 5128eecc9f 2011-02-23 kinaba: { 5128eecc9f 2011-02-23 kinaba: c -= e; /* copy to end of window */ 5128eecc9f 2011-02-23 kinaba: do { 5128eecc9f 2011-02-23 kinaba: *q++ = *r++; 5128eecc9f 2011-02-23 kinaba: } while (--e); 5128eecc9f 2011-02-23 kinaba: r = s->window; /* copy rest from start of window */ 5128eecc9f 2011-02-23 kinaba: } 5128eecc9f 2011-02-23 kinaba: } 5128eecc9f 2011-02-23 kinaba: do { /* copy all or what's left */ 5128eecc9f 2011-02-23 kinaba: *q++ = *r++; 5128eecc9f 2011-02-23 kinaba: } while (--c); 5128eecc9f 2011-02-23 kinaba: break; 5128eecc9f 2011-02-23 kinaba: } 5128eecc9f 2011-02-23 kinaba: else if ((e & 64) == 0) 5128eecc9f 2011-02-23 kinaba: { 5128eecc9f 2011-02-23 kinaba: t += t->base; 5128eecc9f 2011-02-23 kinaba: e = (t += ((uInt)b & inflate_mask[e]))->exop; 5128eecc9f 2011-02-23 kinaba: } 5128eecc9f 2011-02-23 kinaba: else 5128eecc9f 2011-02-23 kinaba: { 5128eecc9f 2011-02-23 kinaba: z->msg = (char*)"invalid distance code"; 5128eecc9f 2011-02-23 kinaba: UNGRAB 5128eecc9f 2011-02-23 kinaba: UPDATE 5128eecc9f 2011-02-23 kinaba: return Z_DATA_ERROR; 5128eecc9f 2011-02-23 kinaba: } 5128eecc9f 2011-02-23 kinaba: } while (1); 5128eecc9f 2011-02-23 kinaba: break; 5128eecc9f 2011-02-23 kinaba: } 5128eecc9f 2011-02-23 kinaba: if ((e & 64) == 0) 5128eecc9f 2011-02-23 kinaba: { 5128eecc9f 2011-02-23 kinaba: t += t->base; 5128eecc9f 2011-02-23 kinaba: if ((e = (t += ((uInt)b & inflate_mask[e]))->exop) == 0) 5128eecc9f 2011-02-23 kinaba: { 5128eecc9f 2011-02-23 kinaba: DUMPBITS(t->bits) 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: *q++ = (Byte)t->base; 5128eecc9f 2011-02-23 kinaba: m--; 5128eecc9f 2011-02-23 kinaba: break; 5128eecc9f 2011-02-23 kinaba: } 5128eecc9f 2011-02-23 kinaba: } 5128eecc9f 2011-02-23 kinaba: else if (e & 32) 5128eecc9f 2011-02-23 kinaba: { 5128eecc9f 2011-02-23 kinaba: Tracevv((stderr, "inflate: * end of block\n")); 5128eecc9f 2011-02-23 kinaba: UNGRAB 5128eecc9f 2011-02-23 kinaba: UPDATE 5128eecc9f 2011-02-23 kinaba: return Z_STREAM_END; 5128eecc9f 2011-02-23 kinaba: } 5128eecc9f 2011-02-23 kinaba: else 5128eecc9f 2011-02-23 kinaba: { 5128eecc9f 2011-02-23 kinaba: z->msg = (char*)"invalid literal/length code"; 5128eecc9f 2011-02-23 kinaba: UNGRAB 5128eecc9f 2011-02-23 kinaba: UPDATE 5128eecc9f 2011-02-23 kinaba: return Z_DATA_ERROR; 5128eecc9f 2011-02-23 kinaba: } 5128eecc9f 2011-02-23 kinaba: } while (1); 5128eecc9f 2011-02-23 kinaba: } while (m >= 258 && n >= 10); 5128eecc9f 2011-02-23 kinaba: 5128eecc9f 2011-02-23 kinaba: /* not enough input or output--restore pointers and return */ 5128eecc9f 2011-02-23 kinaba: UNGRAB 5128eecc9f 2011-02-23 kinaba: UPDATE 5128eecc9f 2011-02-23 kinaba: return Z_OK; 5128eecc9f 2011-02-23 kinaba: }