xref: /illumos-gate/usr/src/contrib/zlib/inffast.c (revision b8382935)
1 /* inffast.c -- fast decoding
2  * Copyright (C) 1995-2017 Mark Adler
3  * For conditions of distribution and use, see copyright notice in zlib.h
4  */
5 
6 #include "zutil.h"
7 #include "inftrees.h"
8 #include "inflate.h"
9 #include "inffast.h"
10 
11 #ifdef ASMINF
12 #  pragma message("Assembler code may have bugs -- use at your own risk")
13 #else
14 
15 /*
16    Decode literal, length, and distance codes and write out the resulting
17    literal and match bytes until either not enough input or output is
18    available, an end-of-block is encountered, or a data error is encountered.
19    When large enough input and output buffers are supplied to inflate(), for
20    example, a 16K input buffer and a 64K output buffer, more than 95% of the
21    inflate execution time is spent in this routine.
22 
23    Entry assumptions:
24 
25         state->mode == LEN
26         strm->avail_in >= 6
27         strm->avail_out >= 258
28         start >= strm->avail_out
29         state->bits < 8
30 
31    On return, state->mode is one of:
32 
33         LEN -- ran out of enough output space or enough available input
34         TYPE -- reached end of block code, inflate() to interpret next block
35         BAD -- error in block data
36 
37    Notes:
38 
39     - The maximum input bits used by a length/distance pair is 15 bits for the
40       length code, 5 bits for the length extra, 15 bits for the distance code,
41       and 13 bits for the distance extra.  This totals 48 bits, or six bytes.
42       Therefore if strm->avail_in >= 6, then there is enough input to avoid
43       checking for available input while decoding.
44 
45     - The maximum bytes that a single length/distance pair can output is 258
46       bytes, which is the maximum length that can be coded.  inflate_fast()
47       requires strm->avail_out >= 258 for each loop to avoid checking for
48       output space.
49  */
inflate_fast(z_streamp strm,unsigned start)50 void ZLIB_INTERNAL inflate_fast(z_streamp strm, unsigned start)
51 {
52     struct inflate_state FAR *state;
53     z_const unsigned char FAR *in;      /* local strm->next_in */
54     z_const unsigned char FAR *last;    /* have enough input while in < last */
55     unsigned char FAR *out;     /* local strm->next_out */
56     unsigned char FAR *beg;     /* inflate()'s initial strm->next_out */
57     unsigned char FAR *end;     /* while out < end, enough space available */
58 #ifdef INFLATE_STRICT
59     unsigned dmax;              /* maximum distance from zlib header */
60 #endif
61     unsigned wsize;             /* window size or zero if not using window */
62     unsigned whave;             /* valid bytes in the window */
63     unsigned wnext;             /* window write index */
64     unsigned char FAR *window;  /* allocated sliding window, if wsize != 0 */
65     unsigned long hold;         /* local strm->hold */
66     unsigned bits;              /* local strm->bits */
67     code const FAR *lcode;      /* local strm->lencode */
68     code const FAR *dcode;      /* local strm->distcode */
69     unsigned lmask;             /* mask for first level of length codes */
70     unsigned dmask;             /* mask for first level of distance codes */
71     code here;                  /* retrieved table entry */
72     unsigned op;                /* code bits, operation, extra bits, or */
73                                 /*  window position, window bytes to copy */
74     unsigned len;               /* match length, unused bytes */
75     unsigned dist;              /* match distance */
76     unsigned char FAR *from;    /* where to copy match from */
77 
78     /* copy state to local variables */
79     state = (struct inflate_state FAR *)strm->state;
80     in = strm->next_in;
81     last = in + (strm->avail_in - 5);
82     out = strm->next_out;
83     beg = out - (start - strm->avail_out);
84     end = out + (strm->avail_out - 257);
85 #ifdef INFLATE_STRICT
86     dmax = state->dmax;
87 #endif
88     wsize = state->wsize;
89     whave = state->whave;
90     wnext = state->wnext;
91     window = state->window;
92     hold = state->hold;
93     bits = state->bits;
94     lcode = state->lencode;
95     dcode = state->distcode;
96     lmask = (1U << state->lenbits) - 1;
97     dmask = (1U << state->distbits) - 1;
98 
99     /* decode literals and length/distances until end-of-block or not enough
100        input data or output space */
101     do {
102         if (bits < 15) {
103             hold += (unsigned long)(*in++) << bits;
104             bits += 8;
105             hold += (unsigned long)(*in++) << bits;
106             bits += 8;
107         }
108         here = lcode[hold & lmask];
109       dolen:
110         op = (unsigned)(here.bits);
111         hold >>= op;
112         bits -= op;
113         op = (unsigned)(here.op);
114         if (op == 0) {                          /* literal */
115             Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?
116                     "inflate:         literal '%c'\n" :
117                     "inflate:         literal 0x%02x\n", here.val));
118             *out++ = (unsigned char)(here.val);
119         }
120         else if (op & 16) {                     /* length base */
121             len = (unsigned)(here.val);
122             op &= 15;                           /* number of extra bits */
123             if (op) {
124                 if (bits < op) {
125                     hold += (unsigned long)(*in++) << bits;
126                     bits += 8;
127                 }
128                 len += (unsigned)hold & ((1U << op) - 1);
129                 hold >>= op;
130                 bits -= op;
131             }
132             Tracevv((stderr, "inflate:         length %u\n", len));
133             if (bits < 15) {
134                 hold += (unsigned long)(*in++) << bits;
135                 bits += 8;
136                 hold += (unsigned long)(*in++) << bits;
137                 bits += 8;
138             }
139             here = dcode[hold & dmask];
140           dodist:
141             op = (unsigned)(here.bits);
142             hold >>= op;
143             bits -= op;
144             op = (unsigned)(here.op);
145             if (op & 16) {                      /* distance base */
146                 dist = (unsigned)(here.val);
147                 op &= 15;                       /* number of extra bits */
148                 if (bits < op) {
149                     hold += (unsigned long)(*in++) << bits;
150                     bits += 8;
151                     if (bits < op) {
152                         hold += (unsigned long)(*in++) << bits;
153                         bits += 8;
154                     }
155                 }
156                 dist += (unsigned)hold & ((1U << op) - 1);
157 #ifdef INFLATE_STRICT
158                 if (dist > dmax) {
159                     strm->msg = (char *)"invalid distance too far back";
160                     state->mode = BAD;
161                     break;
162                 }
163 #endif
164                 hold >>= op;
165                 bits -= op;
166                 Tracevv((stderr, "inflate:         distance %u\n", dist));
167                 op = (unsigned)(out - beg);     /* max distance in output */
168                 if (dist > op) {                /* see if copy from window */
169                     op = dist - op;             /* distance back in window */
170                     if (op > whave) {
171                         if (state->sane) {
172                             strm->msg =
173                                 (char *)"invalid distance too far back";
174                             state->mode = BAD;
175                             break;
176                         }
177 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
178                         if (len <= op - whave) {
179                             do {
180                                 *out++ = 0;
181                             } while (--len);
182                             continue;
183                         }
184                         len -= op - whave;
185                         do {
186                             *out++ = 0;
187                         } while (--op > whave);
188                         if (op == 0) {
189                             from = out - dist;
190                             do {
191                                 *out++ = *from++;
192                             } while (--len);
193                             continue;
194                         }
195 #endif
196                     }
197                     from = window;
198                     if (wnext == 0) {           /* very common case */
199                         from += wsize - op;
200                         if (op < len) {         /* some from window */
201                             len -= op;
202                             do {
203                                 *out++ = *from++;
204                             } while (--op);
205                             from = out - dist;  /* rest from output */
206                         }
207                     }
208                     else if (wnext < op) {      /* wrap around window */
209                         from += wsize + wnext - op;
210                         op -= wnext;
211                         if (op < len) {         /* some from end of window */
212                             len -= op;
213                             do {
214                                 *out++ = *from++;
215                             } while (--op);
216                             from = window;
217                             if (wnext < len) {  /* some from start of window */
218                                 op = wnext;
219                                 len -= op;
220                                 do {
221                                     *out++ = *from++;
222                                 } while (--op);
223                                 from = out - dist;      /* rest from output */
224                             }
225                         }
226                     }
227                     else {                      /* contiguous in window */
228                         from += wnext - op;
229                         if (op < len) {         /* some from window */
230                             len -= op;
231                             do {
232                                 *out++ = *from++;
233                             } while (--op);
234                             from = out - dist;  /* rest from output */
235                         }
236                     }
237                     while (len > 2) {
238                         *out++ = *from++;
239                         *out++ = *from++;
240                         *out++ = *from++;
241                         len -= 3;
242                     }
243                     if (len) {
244                         *out++ = *from++;
245                         if (len > 1)
246                             *out++ = *from++;
247                     }
248                 }
249                 else {
250                     from = out - dist;          /* copy direct from output */
251                     do {                        /* minimum length is three */
252                         *out++ = *from++;
253                         *out++ = *from++;
254                         *out++ = *from++;
255                         len -= 3;
256                     } while (len > 2);
257                     if (len) {
258                         *out++ = *from++;
259                         if (len > 1)
260                             *out++ = *from++;
261                     }
262                 }
263             }
264             else if ((op & 64) == 0) {          /* 2nd level distance code */
265                 here = dcode[here.val + (hold & ((1U << op) - 1))];
266                 goto dodist;
267             }
268             else {
269                 strm->msg = (char *)"invalid distance code";
270                 state->mode = BAD;
271                 break;
272             }
273         }
274         else if ((op & 64) == 0) {              /* 2nd level length code */
275             here = lcode[here.val + (hold & ((1U << op) - 1))];
276             goto dolen;
277         }
278         else if (op & 32) {                     /* end-of-block */
279             Tracevv((stderr, "inflate:         end of block\n"));
280             state->mode = TYPE;
281             break;
282         }
283         else {
284             strm->msg = (char *)"invalid literal/length code";
285             state->mode = BAD;
286             break;
287         }
288     } while (in < last && out < end);
289 
290     /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
291     len = bits >> 3;
292     in -= len;
293     bits -= len << 3;
294     hold &= (1U << bits) - 1;
295 
296     /* update state and return */
297     strm->next_in = in;
298     strm->next_out = out;
299     strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
300     strm->avail_out = (unsigned)(out < end ?
301                                  257 + (end - out) : 257 - (out - end));
302     state->hold = hold;
303     state->bits = bits;
304     return;
305 }
306 
307 /*
308    inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
309    - Using bit fields for code structure
310    - Different op definition to avoid & for extra bits (do & for table bits)
311    - Three separate decoding do-loops for direct, window, and wnext == 0
312    - Special case for distance > 1 copies to do overlapped load and store copy
313    - Explicit branch predictions (based on measured branch probabilities)
314    - Deferring match copy and interspersed it with decoding subsequent codes
315    - Swapping literal/length else
316    - Swapping window/direct else
317    - Larger unrolled copy loops (three is about right)
318    - Moving len -= 3 statement into middle of loop
319  */
320 
321 #endif /* !ASMINF */
322