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