199767f8919635c4928607450d9e0abb932109ceToomas Soome/* inffast.c -- fast decoding
199767f8919635c4928607450d9e0abb932109ceToomas Soome * Copyright (C) 1995-2008, 2010, 2013 Mark Adler
199767f8919635c4928607450d9e0abb932109ceToomas Soome * For conditions of distribution and use, see copyright notice in zlib.h
199767f8919635c4928607450d9e0abb932109ceToomas Soome/* Allow machine dependent optimization for post-increment or pre-increment.
199767f8919635c4928607450d9e0abb932109ceToomas Soome Based on testing to date,
199767f8919635c4928607450d9e0abb932109ceToomas Soome Pre-increment preferred for:
199767f8919635c4928607450d9e0abb932109ceToomas Soome - PowerPC G3 (Adler)
199767f8919635c4928607450d9e0abb932109ceToomas Soome - MIPS R5000 (Randers-Pehrson)
199767f8919635c4928607450d9e0abb932109ceToomas Soome Post-increment preferred for:
199767f8919635c4928607450d9e0abb932109ceToomas Soome No measurable difference:
199767f8919635c4928607450d9e0abb932109ceToomas Soome - Pentium III (Anderson)
199767f8919635c4928607450d9e0abb932109ceToomas Soome - M68060 (Nikl)
199767f8919635c4928607450d9e0abb932109ceToomas Soome Decode literal, length, and distance codes and write out the resulting
199767f8919635c4928607450d9e0abb932109ceToomas Soome literal and match bytes until either not enough input or output is
199767f8919635c4928607450d9e0abb932109ceToomas Soome available, an end-of-block is encountered, or a data error is encountered.
199767f8919635c4928607450d9e0abb932109ceToomas Soome When large enough input and output buffers are supplied to inflate(), for
199767f8919635c4928607450d9e0abb932109ceToomas Soome example, a 16K input buffer and a 64K output buffer, more than 95% of the
199767f8919635c4928607450d9e0abb932109ceToomas Soome inflate execution time is spent in this routine.
199767f8919635c4928607450d9e0abb932109ceToomas Soome Entry assumptions:
199767f8919635c4928607450d9e0abb932109ceToomas Soome state->mode == LEN
199767f8919635c4928607450d9e0abb932109ceToomas Soome strm->avail_in >= 6
199767f8919635c4928607450d9e0abb932109ceToomas Soome strm->avail_out >= 258
199767f8919635c4928607450d9e0abb932109ceToomas Soome start >= strm->avail_out
199767f8919635c4928607450d9e0abb932109ceToomas Soome state->bits < 8
199767f8919635c4928607450d9e0abb932109ceToomas Soome On return, state->mode is one of:
199767f8919635c4928607450d9e0abb932109ceToomas Soome LEN -- ran out of enough output space or enough available input
199767f8919635c4928607450d9e0abb932109ceToomas Soome TYPE -- reached end of block code, inflate() to interpret next block
199767f8919635c4928607450d9e0abb932109ceToomas Soome BAD -- error in block data
199767f8919635c4928607450d9e0abb932109ceToomas Soome - The maximum input bits used by a length/distance pair is 15 bits for the
199767f8919635c4928607450d9e0abb932109ceToomas Soome length code, 5 bits for the length extra, 15 bits for the distance code,
199767f8919635c4928607450d9e0abb932109ceToomas Soome and 13 bits for the distance extra. This totals 48 bits, or six bytes.
199767f8919635c4928607450d9e0abb932109ceToomas Soome Therefore if strm->avail_in >= 6, then there is enough input to avoid
199767f8919635c4928607450d9e0abb932109ceToomas Soome checking for available input while decoding.
199767f8919635c4928607450d9e0abb932109ceToomas Soome - The maximum bytes that a single length/distance pair can output is 258
199767f8919635c4928607450d9e0abb932109ceToomas Soome bytes, which is the maximum length that can be coded. inflate_fast()
199767f8919635c4928607450d9e0abb932109ceToomas Soome requires strm->avail_out >= 258 for each loop to avoid checking for
199767f8919635c4928607450d9e0abb932109ceToomas Soome output space.
199767f8919635c4928607450d9e0abb932109ceToomas Soomeunsigned start; /* inflate()'s starting value for strm->avail_out */
199767f8919635c4928607450d9e0abb932109ceToomas Soome z_const unsigned char FAR *in; /* local strm->next_in */
199767f8919635c4928607450d9e0abb932109ceToomas Soome z_const unsigned char FAR *last; /* have enough input while in < last */
199767f8919635c4928607450d9e0abb932109ceToomas Soome unsigned char FAR *out; /* local strm->next_out */
199767f8919635c4928607450d9e0abb932109ceToomas Soome unsigned char FAR *beg; /* inflate()'s initial strm->next_out */
199767f8919635c4928607450d9e0abb932109ceToomas Soome unsigned char FAR *end; /* while out < end, enough space available */
199767f8919635c4928607450d9e0abb932109ceToomas Soome unsigned dmax; /* maximum distance from zlib header */
199767f8919635c4928607450d9e0abb932109ceToomas Soome unsigned wsize; /* window size or zero if not using window */
199767f8919635c4928607450d9e0abb932109ceToomas Soome unsigned whave; /* valid bytes in the window */
199767f8919635c4928607450d9e0abb932109ceToomas Soome unsigned char FAR *window; /* allocated sliding window, if wsize != 0 */
199767f8919635c4928607450d9e0abb932109ceToomas Soome code const FAR *lcode; /* local strm->lencode */
199767f8919635c4928607450d9e0abb932109ceToomas Soome code const FAR *dcode; /* local strm->distcode */
199767f8919635c4928607450d9e0abb932109ceToomas Soome unsigned lmask; /* mask for first level of length codes */
199767f8919635c4928607450d9e0abb932109ceToomas Soome unsigned dmask; /* mask for first level of distance codes */
199767f8919635c4928607450d9e0abb932109ceToomas Soome unsigned op; /* code bits, operation, extra bits, or */
199767f8919635c4928607450d9e0abb932109ceToomas Soome /* window position, window bytes to copy */
199767f8919635c4928607450d9e0abb932109ceToomas Soome unsigned char FAR *from; /* where to copy match from */
199767f8919635c4928607450d9e0abb932109ceToomas Soome /* copy state to local variables */
199767f8919635c4928607450d9e0abb932109ceToomas Soome state = (struct inflate_state FAR *)strm->state;
199767f8919635c4928607450d9e0abb932109ceToomas Soome /* decode literals and length/distances until end-of-block or not enough
199767f8919635c4928607450d9e0abb932109ceToomas Soome input data or output space */
199767f8919635c4928607450d9e0abb932109ceToomas Soome Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?
199767f8919635c4928607450d9e0abb932109ceToomas Soome "inflate: literal '%c'\n" :
199767f8919635c4928607450d9e0abb932109ceToomas Soome Tracevv((stderr, "inflate: length %u\n", len));
199767f8919635c4928607450d9e0abb932109ceToomas Soome strm->msg = (char *)"invalid distance too far back";
199767f8919635c4928607450d9e0abb932109ceToomas Soome Tracevv((stderr, "inflate: distance %u\n", dist));
199767f8919635c4928607450d9e0abb932109ceToomas Soome op = (unsigned)(out - beg); /* max distance in output */
199767f8919635c4928607450d9e0abb932109ceToomas Soome (char *)"invalid distance too far back";
199767f8919635c4928607450d9e0abb932109ceToomas Soome#ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
199767f8919635c4928607450d9e0abb932109ceToomas Soome } while (--len);
199767f8919635c4928607450d9e0abb932109ceToomas Soome } while (--len);
199767f8919635c4928607450d9e0abb932109ceToomas Soome } while (--op);
199767f8919635c4928607450d9e0abb932109ceToomas Soome else if (wnext < op) { /* wrap around window */
199767f8919635c4928607450d9e0abb932109ceToomas Soome } while (--op);
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (wnext < len) { /* some from start of window */
199767f8919635c4928607450d9e0abb932109ceToomas Soome } while (--op);
199767f8919635c4928607450d9e0abb932109ceToomas Soome else { /* contiguous in window */
199767f8919635c4928607450d9e0abb932109ceToomas Soome } while (--op);
199767f8919635c4928607450d9e0abb932109ceToomas Soome from = out - dist; /* copy direct from output */
199767f8919635c4928607450d9e0abb932109ceToomas Soome do { /* minimum length is three */
199767f8919635c4928607450d9e0abb932109ceToomas Soome else if ((op & 64) == 0) { /* 2nd level distance code */
199767f8919635c4928607450d9e0abb932109ceToomas Soome here = dcode[here.val + (hold & ((1U << op) - 1))];
199767f8919635c4928607450d9e0abb932109ceToomas Soome else if ((op & 64) == 0) { /* 2nd level length code */
199767f8919635c4928607450d9e0abb932109ceToomas Soome here = lcode[here.val + (hold & ((1U << op) - 1))];
199767f8919635c4928607450d9e0abb932109ceToomas Soome strm->msg = (char *)"invalid literal/length code";
199767f8919635c4928607450d9e0abb932109ceToomas Soome /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
199767f8919635c4928607450d9e0abb932109ceToomas Soome /* update state and return */
199767f8919635c4928607450d9e0abb932109ceToomas Soome strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
199767f8919635c4928607450d9e0abb932109ceToomas Soome inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
199767f8919635c4928607450d9e0abb932109ceToomas Soome - Using bit fields for code structure
199767f8919635c4928607450d9e0abb932109ceToomas Soome - Different op definition to avoid & for extra bits (do & for table bits)
199767f8919635c4928607450d9e0abb932109ceToomas Soome - Three separate decoding do-loops for direct, window, and wnext == 0
199767f8919635c4928607450d9e0abb932109ceToomas Soome - Special case for distance > 1 copies to do overlapped load and store copy
199767f8919635c4928607450d9e0abb932109ceToomas Soome - Explicit branch predictions (based on measured branch probabilities)
199767f8919635c4928607450d9e0abb932109ceToomas Soome - Deferring match copy and interspersed it with decoding subsequent codes
199767f8919635c4928607450d9e0abb932109ceToomas Soome - Swapping literal/length else
199767f8919635c4928607450d9e0abb932109ceToomas Soome - Swapping window/direct else
199767f8919635c4928607450d9e0abb932109ceToomas Soome - Larger unrolled copy loops (three is about right)
199767f8919635c4928607450d9e0abb932109ceToomas Soome - Moving len -= 3 statement into middle of loop
199767f8919635c4928607450d9e0abb932109ceToomas Soome#endif /* !ASMINF */