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