-/* inffast.c -- process literals and length/distance pairs fast
- * Copyright (C) 1995 Mark Adler
- * For conditions of distribution and use, see copyright notice in zlib.h
+/* inffast.c -- fast decoding
+ * Copyright (C) 1995-2017 Mark Adler
+ * For conditions of distribution and use, see copyright notice in zlib.h
*/
#include "zutil.h"
#include "inftrees.h"
-#include "infutil.h"
+#include "inflate.h"
#include "inffast.h"
-struct inflate_codes_state {int dummy;}; /* for buggy compilers */
+#ifdef ASMINF
+# pragma message("Assembler code may have bugs -- use at your own risk")
+#else
-/* simplify the use of the inflate_huft type with some defines */
-#define base more.Base
-#define next more.Next
-#define exop word.what.Exop
-#define bits word.what.Bits
+/*
+ Decode literal, length, and distance codes and write out the resulting
+ literal and match bytes until either not enough input or output is
+ available, an end-of-block is encountered, or a data error is encountered.
+ When large enough input and output buffers are supplied to inflate(), for
+ example, a 16K input buffer and a 64K output buffer, more than 95% of the
+ inflate execution time is spent in this routine.
-/* macros for bit input with no checking and for returning unused bytes */
-#ifdef DEBUG
-# undef NEXTBYTE
-# define NEXTBYTE (n--?0:fprintf(stderr,"inffast underrun\n"),*p++)
-#endif
-#define GRABBITS(j) {while(k<(j)){b|=((uLong)NEXTBYTE)<<k;k+=8;}}
-#define UNGRAB {n+=(c=k>>3);p-=c;k&=7;}
-
-/* Called with number of bytes left to write in window at least 258
- (the maximum string length) and number of input bytes available
- at least ten. The ten bytes are six bytes for the longest length/
- distance pair plus four bytes for overloading the bit buffer. */
-
-int inflate_fast(bl, bd, tl, td, s, z)
-uInt bl, bd;
-inflate_huft *tl, *td;
-struct inflate_blocks_state *s;
-z_stream *z;
+ Entry assumptions:
+
+ state->mode == LEN
+ strm->avail_in >= 6
+ strm->avail_out >= 258
+ start >= strm->avail_out
+ state->bits < 8
+
+ On return, state->mode is one of:
+
+ LEN -- ran out of enough output space or enough available input
+ TYPE -- reached end of block code, inflate() to interpret next block
+ BAD -- error in block data
+
+ Notes:
+
+ - The maximum input bits used by a length/distance pair is 15 bits for the
+ length code, 5 bits for the length extra, 15 bits for the distance code,
+ and 13 bits for the distance extra. This totals 48 bits, or six bytes.
+ Therefore if strm->avail_in >= 6, then there is enough input to avoid
+ checking for available input while decoding.
+
+ - The maximum bytes that a single length/distance pair can output is 258
+ bytes, which is the maximum length that can be coded. inflate_fast()
+ requires strm->avail_out >= 258 for each loop to avoid checking for
+ output space.
+ */
+void ZLIB_INTERNAL inflate_fast(strm, start)
+z_streamp strm;
+unsigned start; /* inflate()'s starting value for strm->avail_out */
{
- inflate_huft *t; /* temporary pointer */
- int e; /* extra bits or operation */
- uLong b; /* bit buffer */
- uInt k; /* bits in bit buffer */
- Byte *p; /* input data pointer */
- uInt n; /* bytes available there */
- Byte *q; /* output window write pointer */
- uInt m; /* bytes to end of window or read pointer */
- uInt ml; /* mask for literal/length tree */
- uInt md; /* mask for distance tree */
- uInt c; /* bytes to copy */
- uInt d; /* distance back to copy from */
- Byte *r; /* copy source pointer */
-
- /* load input, output, bit values */
- LOAD
-
- /* initialize masks in registers */
- ml = inflate_mask[bl];
- md = inflate_mask[bd];
-
- /* do until not enough input or output space for fast loop */
- do { /* assume called with m >= 258 && n >= 10 */
- /* get literal/length code */
- GRABBITS(20) /* max bits for literal/length code */
- if ((e = (t = tl + ((uInt)b & ml))->exop) < 0)
- do {
- if (e == -128)
- {
- z->msg = "invalid literal/length code";
- UNGRAB
- UPDATE
- return Z_DATA_ERROR;
+ struct inflate_state FAR *state;
+ z_const unsigned char FAR *in; /* local strm->next_in */
+ z_const unsigned char FAR *last; /* have enough input while in < last */
+ unsigned char FAR *out; /* local strm->next_out */
+ unsigned char FAR *beg; /* inflate()'s initial strm->next_out */
+ unsigned char FAR *end; /* while out < end, enough space available */
+#ifdef INFLATE_STRICT
+ unsigned dmax; /* maximum distance from zlib header */
+#endif
+ unsigned wsize; /* window size or zero if not using window */
+ unsigned whave; /* valid bytes in the window */
+ unsigned wnext; /* window write index */
+ unsigned char FAR *window; /* allocated sliding window, if wsize != 0 */
+ unsigned long hold; /* local strm->hold */
+ unsigned bits; /* local strm->bits */
+ code const FAR *lcode; /* local strm->lencode */
+ code const FAR *dcode; /* local strm->distcode */
+ unsigned lmask; /* mask for first level of length codes */
+ unsigned dmask; /* mask for first level of distance codes */
+ code const *here; /* retrieved table entry */
+ unsigned op; /* code bits, operation, extra bits, or */
+ /* window position, window bytes to copy */
+ unsigned len; /* match length, unused bytes */
+ unsigned dist; /* match distance */
+ unsigned char FAR *from; /* where to copy match from */
+
+ /* copy state to local variables */
+ state = (struct inflate_state FAR *)strm->state;
+ in = strm->next_in;
+ last = in + (strm->avail_in - 5);
+ out = strm->next_out;
+ beg = out - (start - strm->avail_out);
+ end = out + (strm->avail_out - 257);
+#ifdef INFLATE_STRICT
+ dmax = state->dmax;
+#endif
+ wsize = state->wsize;
+ whave = state->whave;
+ wnext = state->wnext;
+ window = state->window;
+ hold = state->hold;
+ bits = state->bits;
+ lcode = state->lencode;
+ dcode = state->distcode;
+ lmask = (1U << state->lenbits) - 1;
+ dmask = (1U << state->distbits) - 1;
+
+ /* decode literals and length/distances until end-of-block or not enough
+ input data or output space */
+ do {
+ if (bits < 15) {
+ hold += (unsigned long)(*in++) << bits;
+ bits += 8;
+ hold += (unsigned long)(*in++) << bits;
+ bits += 8;
+ }
+ here = lcode + (hold & lmask);
+ dolen:
+ op = (unsigned)(here->bits);
+ hold >>= op;
+ bits -= op;
+ op = (unsigned)(here->op);
+ if (op == 0) { /* literal */
+ Tracevv((stderr, here->val >= 0x20 && here->val < 0x7f ?
+ "inflate: literal '%c'\n" :
+ "inflate: literal 0x%02x\n", here->val));
+ *out++ = (unsigned char)(here->val);
+ }
+ else if (op & 16) { /* length base */
+ len = (unsigned)(here->val);
+ op &= 15; /* number of extra bits */
+ if (op) {
+ if (bits < op) {
+ hold += (unsigned long)(*in++) << bits;
+ bits += 8;
+ }
+ len += (unsigned)hold & ((1U << op) - 1);
+ hold >>= op;
+ bits -= op;
+ }
+ Tracevv((stderr, "inflate: length %u\n", len));
+ if (bits < 15) {
+ hold += (unsigned long)(*in++) << bits;
+ bits += 8;
+ hold += (unsigned long)(*in++) << bits;
+ bits += 8;
+ }
+ here = dcode + (hold & dmask);
+ dodist:
+ op = (unsigned)(here->bits);
+ hold >>= op;
+ bits -= op;
+ op = (unsigned)(here->op);
+ if (op & 16) { /* distance base */
+ dist = (unsigned)(here->val);
+ op &= 15; /* number of extra bits */
+ if (bits < op) {
+ hold += (unsigned long)(*in++) << bits;
+ bits += 8;
+ if (bits < op) {
+ hold += (unsigned long)(*in++) << bits;
+ bits += 8;
+ }
+ }
+ dist += (unsigned)hold & ((1U << op) - 1);
+#ifdef INFLATE_STRICT
+ if (dist > dmax) {
+ strm->msg = (char *)"invalid distance too far back";
+ state->mode = BAD;
+ break;
+ }
+#endif
+ hold >>= op;
+ bits -= op;
+ Tracevv((stderr, "inflate: distance %u\n", dist));
+ op = (unsigned)(out - beg); /* max distance in output */
+ if (dist > op) { /* see if copy from window */
+ op = dist - op; /* distance back in window */
+ if (op > whave) {
+ if (state->sane) {
+ strm->msg =
+ (char *)"invalid distance too far back";
+ state->mode = BAD;
+ break;
+ }
+#ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
+ if (len <= op - whave) {
+ do {
+ *out++ = 0;
+ } while (--len);
+ continue;
+ }
+ len -= op - whave;
+ do {
+ *out++ = 0;
+ } while (--op > whave);
+ if (op == 0) {
+ from = out - dist;
+ do {
+ *out++ = *from++;
+ } while (--len);
+ continue;
+ }
+#endif
+ }
+ from = window;
+ if (wnext == 0) { /* very common case */
+ from += wsize - op;
+ if (op < len) { /* some from window */
+ len -= op;
+ do {
+ *out++ = *from++;
+ } while (--op);
+ from = out - dist; /* rest from output */
+ }
+ }
+ else if (wnext < op) { /* wrap around window */
+ from += wsize + wnext - op;
+ op -= wnext;
+ if (op < len) { /* some from end of window */
+ len -= op;
+ do {
+ *out++ = *from++;
+ } while (--op);
+ from = window;
+ if (wnext < len) { /* some from start of window */
+ op = wnext;
+ len -= op;
+ do {
+ *out++ = *from++;
+ } while (--op);
+ from = out - dist; /* rest from output */
+ }
+ }
+ }
+ else { /* contiguous in window */
+ from += wnext - op;
+ if (op < len) { /* some from window */
+ len -= op;
+ do {
+ *out++ = *from++;
+ } while (--op);
+ from = out - dist; /* rest from output */
+ }
+ }
+ while (len > 2) {
+ *out++ = *from++;
+ *out++ = *from++;
+ *out++ = *from++;
+ len -= 3;
+ }
+ if (len) {
+ *out++ = *from++;
+ if (len > 1)
+ *out++ = *from++;
+ }
+ }
+ else {
+ from = out - dist; /* copy direct from output */
+ do { /* minimum length is three */
+ *out++ = *from++;
+ *out++ = *from++;
+ *out++ = *from++;
+ len -= 3;
+ } while (len > 2);
+ if (len) {
+ *out++ = *from++;
+ if (len > 1)
+ *out++ = *from++;
+ }
+ }
+ }
+ else if ((op & 64) == 0) { /* 2nd level distance code */
+ here = dcode + here->val + (hold & ((1U << op) - 1));
+ goto dodist;
+ }
+ else {
+ strm->msg = (char *)"invalid distance code";
+ state->mode = BAD;
+ break;
+ }
+ }
+ else if ((op & 64) == 0) { /* 2nd level length code */
+ here = lcode + here->val + (hold & ((1U << op) - 1));
+ goto dolen;
}
- DUMPBITS(t->bits)
- e = -e;
- if (e & 64) /* end of block */
- {
- Tracevv((stderr, "inflate: * end of block\n"));
- UNGRAB
- UPDATE
- return Z_STREAM_END;
+ else if (op & 32) { /* end-of-block */
+ Tracevv((stderr, "inflate: end of block\n"));
+ state->mode = TYPE;
+ break;
}
- } while ((e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop) < 0);
- DUMPBITS(t->bits)
-
- /* process literal or length (end of block already trapped) */
- if (e & 16) /* then it's a literal */
- {
- Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
- "inflate: * literal '%c'\n" :
- "inflate: * literal 0x%02x\n", t->base));
- *q++ = (Byte)t->base;
- m--;
- }
- else /* it's a length */
- {
- /* get length of block to copy (already have extra bits) */
- c = t->base + ((uInt)b & inflate_mask[e]);
- DUMPBITS(e);
- Tracevv((stderr, "inflate: * length %u\n", c));
-
- /* decode distance base of block to copy */
- GRABBITS(15); /* max bits for distance code */
- if ((e = (t = td + ((uInt)b & md))->exop) < 0)
- do {
- if (e == -128)
- {
- z->msg = "invalid distance code";
- UNGRAB
- UPDATE
- return Z_DATA_ERROR;
- }
- DUMPBITS(t->bits)
- e = -e;
- } while ((e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop) < 0);
- DUMPBITS(t->bits)
-
- /* get extra bits to add to distance base */
- GRABBITS((uInt)e) /* get extra bits (up to 13) */
- d = t->base + ((uInt)b & inflate_mask[e]);
- DUMPBITS(e)
- Tracevv((stderr, "inflate: * distance %u\n", d));
-
- /* do the copy */
- m -= c;
- if ((uInt)(q - s->window) >= d) /* if offset before destination, */
- { /* just copy */
- r = q - d;
- *q++ = *r++; c--; /* minimum count is three, */
- *q++ = *r++; c--; /* so unroll loop a little */
- do {
- *q++ = *r++;
- } while (--c);
- }
- else /* else offset after destination */
- {
- e = d - (q - s->window); /* bytes from offset to end */
- r = s->end - e; /* pointer to offset */
- if (c > (uInt)e) /* if source crosses, */
- {
- c -= e; /* copy to end of window */
- do {
- *q++ = *r++;
- } while (--e);
- r = s->window; /* copy rest from start of window */
+ else {
+ strm->msg = (char *)"invalid literal/length code";
+ state->mode = BAD;
+ break;
}
- do { /* copy all or what's left */
- *q++ = *r++;
- } while (--c);
- }
- }
- } while (m >= 258 && n >= 10);
-
- /* not enough input or output--restore pointers and return */
- UNGRAB
- UPDATE
- return Z_OK;
+ } while (in < last && out < end);
+
+ /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
+ len = bits >> 3;
+ in -= len;
+ bits -= len << 3;
+ hold &= (1U << bits) - 1;
+
+ /* update state and return */
+ strm->next_in = in;
+ strm->next_out = out;
+ strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
+ strm->avail_out = (unsigned)(out < end ?
+ 257 + (end - out) : 257 - (out - end));
+ state->hold = hold;
+ state->bits = bits;
+ return;
}
+
+/*
+ inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
+ - Using bit fields for code structure
+ - Different op definition to avoid & for extra bits (do & for table bits)
+ - Three separate decoding do-loops for direct, window, and wnext == 0
+ - Special case for distance > 1 copies to do overlapped load and store copy
+ - Explicit branch predictions (based on measured branch probabilities)
+ - Deferring match copy and interspersed it with decoding subsequent codes
+ - Swapping literal/length else
+ - Swapping window/direct else
+ - Larger unrolled copy loops (three is about right)
+ - Moving len -= 3 statement into middle of loop
+ */
+
+#endif /* !ASMINF */
projects / zlib.git / blobdiff