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