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