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