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