xref: /openbsd-src/lib/libz/inffast.c (revision 4480ad49db70b6d2b90da94cc0d4755aace8a632)
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