/* inffast.c -- fast decoding | |
* Copyright (C) 1995-2008, 2010 Mark Adler | |
* For conditions of distribution and use, see copyright notice in zlib.h | |
*/ | |
#include "zutil.h" | |
#include "inftrees.h" | |
#include "inflate.h" | |
#include "inffast.h" | |
#ifndef ASMINF | |
/* Allow machine dependent optimization for post-increment or pre-increment. | |
Based on testing to date, | |
Pre-increment preferred for: | |
- PowerPC G3 (Adler) | |
- MIPS R5000 (Randers-Pehrson) | |
Post-increment preferred for: | |
- none | |
No measurable difference: | |
- Pentium III (Anderson) | |
- M68060 (Nikl) | |
*/ | |
#ifdef POSTINC | |
# define OFF 0 | |
# define PUP(a) *(a)++ | |
#else | |
# define OFF 1 | |
# define PUP(a) *++(a) | |
#endif | |
/* | |
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. | |
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 */ | |
{ | |
struct inflate_state FAR *state; | |
unsigned char FAR *in; /* local strm->next_in */ | |
unsigned char FAR *last; /* while in < last, enough input available */ | |
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 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 - OFF; | |
last = in + (strm->avail_in - 5); | |
out = strm->next_out - OFF; | |
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)(PUP(in)) << bits; | |
bits += 8; | |
hold += (unsigned long)(PUP(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)); | |
PUP(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)(PUP(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)(PUP(in)) << bits; | |
bits += 8; | |
hold += (unsigned long)(PUP(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)(PUP(in)) << bits; | |
bits += 8; | |
if (bits < op) { | |
hold += (unsigned long)(PUP(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 { | |
PUP(out) = 0; | |
} while (--len); | |
continue; | |
} | |
len -= op - whave; | |
do { | |
PUP(out) = 0; | |
} while (--op > whave); | |
if (op == 0) { | |
from = out - dist; | |
do { | |
PUP(out) = PUP(from); | |
} while (--len); | |
continue; | |
} | |
#endif | |
} | |
from = window - OFF; | |
if (wnext == 0) { /* very common case */ | |
from += wsize - op; | |
if (op < len) { /* some from window */ | |
len -= op; | |
do { | |
PUP(out) = PUP(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 { | |
PUP(out) = PUP(from); | |
} while (--op); | |
from = window - OFF; | |
if (wnext < len) { /* some from start of window */ | |
op = wnext; | |
len -= op; | |
do { | |
PUP(out) = PUP(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 { | |
PUP(out) = PUP(from); | |
} while (--op); | |
from = out - dist; /* rest from output */ | |
} | |
} | |
while (len > 2) { | |
PUP(out) = PUP(from); | |
PUP(out) = PUP(from); | |
PUP(out) = PUP(from); | |
len -= 3; | |
} | |
if (len) { | |
PUP(out) = PUP(from); | |
if (len > 1) | |
PUP(out) = PUP(from); | |
} | |
} | |
else { | |
from = out - dist; /* copy direct from output */ | |
do { /* minimum length is three */ | |
PUP(out) = PUP(from); | |
PUP(out) = PUP(from); | |
PUP(out) = PUP(from); | |
len -= 3; | |
} while (len > 2); | |
if (len) { | |
PUP(out) = PUP(from); | |
if (len > 1) | |
PUP(out) = PUP(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; | |
} | |
else if (op & 32) { /* end-of-block */ | |
Tracevv((stderr, "inflate: end of block\n")); | |
state->mode = TYPE; | |
break; | |
} | |
else { | |
strm->msg = (char *)"invalid literal/length code"; | |
state->mode = BAD; | |
break; | |
} | |
} 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 + OFF; | |
strm->next_out = out + OFF; | |
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 */ |