185c48e79Shenning /* inffast.c -- fast decoding
236f395ceStb * Copyright (C) 1995-2017 Mark Adler
32af503bcStholo * For conditions of distribution and use, see copyright notice in zlib.h
42af503bcStholo */
52af503bcStholo
62af503bcStholo #include "zutil.h"
72af503bcStholo #include "inftrees.h"
885c48e79Shenning #include "inflate.h"
92af503bcStholo #include "inffast.h"
102af503bcStholo
1136f395ceStb #ifdef ASMINF
1236f395ceStb # pragma message("Assembler code may have bugs -- use at your own risk")
1385c48e79Shenning #else
142af503bcStholo
1585c48e79Shenning /*
1685c48e79Shenning Decode literal, length, and distance codes and write out the resulting
1785c48e79Shenning literal and match bytes until either not enough input or output is
1885c48e79Shenning available, an end-of-block is encountered, or a data error is encountered.
1985c48e79Shenning When large enough input and output buffers are supplied to inflate(), for
2085c48e79Shenning example, a 16K input buffer and a 64K output buffer, more than 95% of the
2185c48e79Shenning inflate execution time is spent in this routine.
222af503bcStholo
2385c48e79Shenning Entry assumptions:
242af503bcStholo
2585c48e79Shenning state->mode == LEN
2685c48e79Shenning strm->avail_in >= 6
2785c48e79Shenning strm->avail_out >= 258
2885c48e79Shenning start >= strm->avail_out
2985c48e79Shenning state->bits < 8
3085c48e79Shenning
3185c48e79Shenning On return, state->mode is one of:
3285c48e79Shenning
3385c48e79Shenning LEN -- ran out of enough output space or enough available input
3485c48e79Shenning TYPE -- reached end of block code, inflate() to interpret next block
3585c48e79Shenning BAD -- error in block data
3685c48e79Shenning
3785c48e79Shenning Notes:
3885c48e79Shenning
3985c48e79Shenning - The maximum input bits used by a length/distance pair is 15 bits for the
4085c48e79Shenning length code, 5 bits for the length extra, 15 bits for the distance code,
4185c48e79Shenning and 13 bits for the distance extra. This totals 48 bits, or six bytes.
4285c48e79Shenning Therefore if strm->avail_in >= 6, then there is enough input to avoid
4385c48e79Shenning checking for available input while decoding.
4485c48e79Shenning
4585c48e79Shenning - The maximum bytes that a single length/distance pair can output is 258
4685c48e79Shenning bytes, which is the maximum length that can be coded. inflate_fast()
4785c48e79Shenning requires strm->avail_out >= 258 for each loop to avoid checking for
4885c48e79Shenning output space.
4985c48e79Shenning */
inflate_fast(z_streamp strm,unsigned start)50a04ea15dStb void ZLIB_INTERNAL inflate_fast(z_streamp strm, unsigned start) {
5185c48e79Shenning struct inflate_state FAR *state;
52efa1b761Sjca z_const unsigned char FAR *in; /* local strm->next_in */
5336f395ceStb z_const unsigned char FAR *last; /* have enough input while in < last */
5485c48e79Shenning unsigned char FAR *out; /* local strm->next_out */
5585c48e79Shenning unsigned char FAR *beg; /* inflate()'s initial strm->next_out */
5685c48e79Shenning unsigned char FAR *end; /* while out < end, enough space available */
57d76b9bfaSmillert #ifdef INFLATE_STRICT
58d76b9bfaSmillert unsigned dmax; /* maximum distance from zlib header */
59d76b9bfaSmillert #endif
6085c48e79Shenning unsigned wsize; /* window size or zero if not using window */
6185c48e79Shenning unsigned whave; /* valid bytes in the window */
6236f395ceStb unsigned wnext; /* window write index */
6385c48e79Shenning unsigned char FAR *window; /* allocated sliding window, if wsize != 0 */
6485c48e79Shenning unsigned long hold; /* local strm->hold */
6585c48e79Shenning unsigned bits; /* local strm->bits */
6685c48e79Shenning code const FAR *lcode; /* local strm->lencode */
6785c48e79Shenning code const FAR *dcode; /* local strm->distcode */
6885c48e79Shenning unsigned lmask; /* mask for first level of length codes */
6985c48e79Shenning unsigned dmask; /* mask for first level of distance codes */
70703d4924Stb code const *here; /* retrieved table entry */
7185c48e79Shenning unsigned op; /* code bits, operation, extra bits, or */
7285c48e79Shenning /* window position, window bytes to copy */
7385c48e79Shenning unsigned len; /* match length, unused bytes */
7485c48e79Shenning unsigned dist; /* match distance */
7585c48e79Shenning unsigned char FAR *from; /* where to copy match from */
762af503bcStholo
7785c48e79Shenning /* copy state to local variables */
7885c48e79Shenning state = (struct inflate_state FAR *)strm->state;
7936f395ceStb in = strm->next_in;
8085c48e79Shenning last = in + (strm->avail_in - 5);
8136f395ceStb out = strm->next_out;
8285c48e79Shenning beg = out - (start - strm->avail_out);
8385c48e79Shenning end = out + (strm->avail_out - 257);
84d76b9bfaSmillert #ifdef INFLATE_STRICT
85d76b9bfaSmillert dmax = state->dmax;
86d76b9bfaSmillert #endif
8785c48e79Shenning wsize = state->wsize;
8885c48e79Shenning whave = state->whave;
8936f395ceStb wnext = state->wnext;
9085c48e79Shenning window = state->window;
9185c48e79Shenning hold = state->hold;
9285c48e79Shenning bits = state->bits;
9385c48e79Shenning lcode = state->lencode;
9485c48e79Shenning dcode = state->distcode;
9585c48e79Shenning lmask = (1U << state->lenbits) - 1;
9685c48e79Shenning dmask = (1U << state->distbits) - 1;
972af503bcStholo
9885c48e79Shenning /* decode literals and length/distances until end-of-block or not enough
9985c48e79Shenning input data or output space */
10085c48e79Shenning do {
10185c48e79Shenning if (bits < 15) {
10236f395ceStb hold += (unsigned long)(*in++) << bits;
10385c48e79Shenning bits += 8;
10436f395ceStb hold += (unsigned long)(*in++) << bits;
10585c48e79Shenning bits += 8;
1062af503bcStholo }
107703d4924Stb here = lcode + (hold & lmask);
10885c48e79Shenning dolen:
109703d4924Stb op = (unsigned)(here->bits);
11085c48e79Shenning hold >>= op;
11185c48e79Shenning bits -= op;
112703d4924Stb op = (unsigned)(here->op);
11385c48e79Shenning if (op == 0) { /* literal */
114703d4924Stb Tracevv((stderr, here->val >= 0x20 && here->val < 0x7f ?
11585c48e79Shenning "inflate: literal '%c'\n" :
116703d4924Stb "inflate: literal 0x%02x\n", here->val));
117703d4924Stb *out++ = (unsigned char)(here->val);
1181a167136Smillert }
11985c48e79Shenning else if (op & 16) { /* length base */
120703d4924Stb len = (unsigned)(here->val);
12185c48e79Shenning op &= 15; /* number of extra bits */
12285c48e79Shenning if (op) {
12385c48e79Shenning if (bits < op) {
12436f395ceStb hold += (unsigned long)(*in++) << bits;
12585c48e79Shenning bits += 8;
12685c48e79Shenning }
12785c48e79Shenning len += (unsigned)hold & ((1U << op) - 1);
12885c48e79Shenning hold >>= op;
12985c48e79Shenning bits -= op;
13085c48e79Shenning }
13185c48e79Shenning Tracevv((stderr, "inflate: length %u\n", len));
13285c48e79Shenning if (bits < 15) {
13336f395ceStb hold += (unsigned long)(*in++) << bits;
13485c48e79Shenning bits += 8;
13536f395ceStb hold += (unsigned long)(*in++) << bits;
13685c48e79Shenning bits += 8;
13785c48e79Shenning }
138703d4924Stb here = dcode + (hold & dmask);
13985c48e79Shenning dodist:
140703d4924Stb op = (unsigned)(here->bits);
14185c48e79Shenning hold >>= op;
14285c48e79Shenning bits -= op;
143703d4924Stb op = (unsigned)(here->op);
14485c48e79Shenning if (op & 16) { /* distance base */
145703d4924Stb dist = (unsigned)(here->val);
14685c48e79Shenning op &= 15; /* number of extra bits */
14785c48e79Shenning if (bits < op) {
14836f395ceStb hold += (unsigned long)(*in++) << bits;
14985c48e79Shenning bits += 8;
15085c48e79Shenning if (bits < op) {
15136f395ceStb hold += (unsigned long)(*in++) << bits;
15285c48e79Shenning bits += 8;
1531a167136Smillert }
1541a167136Smillert }
15585c48e79Shenning dist += (unsigned)hold & ((1U << op) - 1);
156d76b9bfaSmillert #ifdef INFLATE_STRICT
157d76b9bfaSmillert if (dist > dmax) {
158*4480ad49Stb strm->msg = (z_const char *)"invalid distance too far back";
159d76b9bfaSmillert state->mode = BAD;
160d76b9bfaSmillert break;
161d76b9bfaSmillert }
162d76b9bfaSmillert #endif
16385c48e79Shenning hold >>= op;
16485c48e79Shenning bits -= op;
16585c48e79Shenning Tracevv((stderr, "inflate: distance %u\n", dist));
16685c48e79Shenning op = (unsigned)(out - beg); /* max distance in output */
16785c48e79Shenning if (dist > op) { /* see if copy from window */
16885c48e79Shenning op = dist - op; /* distance back in window */
16985c48e79Shenning if (op > whave) {
17036f395ceStb if (state->sane) {
171193acacbSmillert #ifdef SMALL
172*4480ad49Stb strm->msg = (z_const char *)"error";
173193acacbSmillert #else
17436f395ceStb strm->msg =
175*4480ad49Stb (z_const char *)"invalid distance too far back";
176193acacbSmillert #endif
17785c48e79Shenning state->mode = BAD;
1782af503bcStholo break;
1792af503bcStholo }
18036f395ceStb #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
18136f395ceStb if (len <= op - whave) {
18236f395ceStb do {
18336f395ceStb *out++ = 0;
18436f395ceStb } while (--len);
18536f395ceStb continue;
18636f395ceStb }
18736f395ceStb len -= op - whave;
18836f395ceStb do {
18936f395ceStb *out++ = 0;
19036f395ceStb } while (--op > whave);
19136f395ceStb if (op == 0) {
19236f395ceStb from = out - dist;
19336f395ceStb do {
19436f395ceStb *out++ = *from++;
19536f395ceStb } while (--len);
19636f395ceStb continue;
19736f395ceStb }
19836f395ceStb #endif
19936f395ceStb }
20036f395ceStb from = window;
20136f395ceStb if (wnext == 0) { /* very common case */
20285c48e79Shenning from += wsize - op;
20385c48e79Shenning if (op < len) { /* some from window */
20485c48e79Shenning len -= op;
20585c48e79Shenning do {
20636f395ceStb *out++ = *from++;
20785c48e79Shenning } while (--op);
20885c48e79Shenning from = out - dist; /* rest from output */
20915ce0796Smillert }
2102af503bcStholo }
21136f395ceStb else if (wnext < op) { /* wrap around window */
21236f395ceStb from += wsize + wnext - op;
21336f395ceStb op -= wnext;
21485c48e79Shenning if (op < len) { /* some from end of window */
21585c48e79Shenning len -= op;
21685c48e79Shenning do {
21736f395ceStb *out++ = *from++;
21885c48e79Shenning } while (--op);
21936f395ceStb from = window;
22036f395ceStb if (wnext < len) { /* some from start of window */
22136f395ceStb op = wnext;
22285c48e79Shenning len -= op;
22385c48e79Shenning do {
22436f395ceStb *out++ = *from++;
22585c48e79Shenning } while (--op);
22685c48e79Shenning from = out - dist; /* rest from output */
2272af503bcStholo }
22885c48e79Shenning }
22985c48e79Shenning }
23085c48e79Shenning else { /* contiguous in window */
23136f395ceStb from += wnext - op;
23285c48e79Shenning if (op < len) { /* some from window */
23385c48e79Shenning len -= op;
23485c48e79Shenning do {
23536f395ceStb *out++ = *from++;
23685c48e79Shenning } while (--op);
23785c48e79Shenning from = out - dist; /* rest from output */
23885c48e79Shenning }
23985c48e79Shenning }
24085c48e79Shenning while (len > 2) {
24136f395ceStb *out++ = *from++;
24236f395ceStb *out++ = *from++;
24336f395ceStb *out++ = *from++;
24485c48e79Shenning len -= 3;
24585c48e79Shenning }
24685c48e79Shenning if (len) {
24736f395ceStb *out++ = *from++;
24885c48e79Shenning if (len > 1)
24936f395ceStb *out++ = *from++;
25085c48e79Shenning }
25185c48e79Shenning }
25285c48e79Shenning else {
25385c48e79Shenning from = out - dist; /* copy direct from output */
25485c48e79Shenning do { /* minimum length is three */
25536f395ceStb *out++ = *from++;
25636f395ceStb *out++ = *from++;
25736f395ceStb *out++ = *from++;
25885c48e79Shenning len -= 3;
25985c48e79Shenning } while (len > 2);
26085c48e79Shenning if (len) {
26136f395ceStb *out++ = *from++;
26285c48e79Shenning if (len > 1)
26336f395ceStb *out++ = *from++;
26485c48e79Shenning }
26585c48e79Shenning }
26685c48e79Shenning }
26785c48e79Shenning else if ((op & 64) == 0) { /* 2nd level distance code */
268703d4924Stb here = dcode + here->val + (hold & ((1U << op) - 1));
26985c48e79Shenning goto dodist;
27085c48e79Shenning }
27185c48e79Shenning else {
272193acacbSmillert #ifdef SMALL
273*4480ad49Stb strm->msg = (z_const char *)"error";
274193acacbSmillert #else
275*4480ad49Stb strm->msg = (z_const char *)"invalid distance code";
276193acacbSmillert #endif
27785c48e79Shenning state->mode = BAD;
2782af503bcStholo break;
2792af503bcStholo }
2802af503bcStholo }
28185c48e79Shenning else if ((op & 64) == 0) { /* 2nd level length code */
282703d4924Stb here = lcode + here->val + (hold & ((1U << op) - 1));
28385c48e79Shenning goto dolen;
2842af503bcStholo }
28585c48e79Shenning else if (op & 32) { /* end-of-block */
28685c48e79Shenning Tracevv((stderr, "inflate: end of block\n"));
28785c48e79Shenning state->mode = TYPE;
28885c48e79Shenning break;
2892af503bcStholo }
29085c48e79Shenning else {
291193acacbSmillert #ifdef SMALL
292*4480ad49Stb strm->msg = (z_const char *)"error";
293193acacbSmillert #else
294*4480ad49Stb strm->msg = (z_const char *)"invalid literal/length code";
295193acacbSmillert #endif
29685c48e79Shenning state->mode = BAD;
29785c48e79Shenning break;
29885c48e79Shenning }
29985c48e79Shenning } while (in < last && out < end);
3002af503bcStholo
30185c48e79Shenning /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
30285c48e79Shenning len = bits >> 3;
30385c48e79Shenning in -= len;
30485c48e79Shenning bits -= len << 3;
30585c48e79Shenning hold &= (1U << bits) - 1;
30685c48e79Shenning
30785c48e79Shenning /* update state and return */
30836f395ceStb strm->next_in = in;
30936f395ceStb strm->next_out = out;
31085c48e79Shenning strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
31185c48e79Shenning strm->avail_out = (unsigned)(out < end ?
31285c48e79Shenning 257 + (end - out) : 257 - (out - end));
31385c48e79Shenning state->hold = hold;
31485c48e79Shenning state->bits = bits;
31585c48e79Shenning return;
3162af503bcStholo }
31785c48e79Shenning
31885c48e79Shenning /*
31985c48e79Shenning inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
32085c48e79Shenning - Using bit fields for code structure
32185c48e79Shenning - Different op definition to avoid & for extra bits (do & for table bits)
32236f395ceStb - Three separate decoding do-loops for direct, window, and wnext == 0
32385c48e79Shenning - Special case for distance > 1 copies to do overlapped load and store copy
32485c48e79Shenning - Explicit branch predictions (based on measured branch probabilities)
32585c48e79Shenning - Deferring match copy and interspersed it with decoding subsequent codes
32685c48e79Shenning - Swapping literal/length else
32785c48e79Shenning - Swapping window/direct else
32885c48e79Shenning - Larger unrolled copy loops (three is about right)
32985c48e79Shenning - Moving len -= 3 statement into middle of loop
33085c48e79Shenning */
33185c48e79Shenning
33285c48e79Shenning #endif /* !ASMINF */
333