OLD | NEW |
1 /* inffast.c -- fast decoding | 1 /* inffast.c -- fast decoding |
2 * Copyright (C) 1995-2008, 2010, 2013 Mark Adler | 2 * Copyright (C) 1995-2017 Mark Adler |
3 * For conditions of distribution and use, see copyright notice in zlib.h | 3 * For conditions of distribution and use, see copyright notice in zlib.h |
4 */ | 4 */ |
5 | 5 |
6 #include "zutil.h" | 6 #include "zutil.h" |
7 #include "inftrees.h" | 7 #include "inftrees.h" |
8 #include "inflate.h" | 8 #include "inflate.h" |
9 #include "inffast.h" | 9 #include "inffast.h" |
10 | 10 |
11 #ifndef ASMINF | 11 #ifdef ASMINF |
12 | 12 # pragma message("Assembler code may have bugs -- use at your own risk") |
13 /* Allow machine dependent optimization for post-increment or pre-increment. | |
14 Based on testing to date, | |
15 Pre-increment preferred for: | |
16 - PowerPC G3 (Adler) | |
17 - MIPS R5000 (Randers-Pehrson) | |
18 Post-increment preferred for: | |
19 - none | |
20 No measurable difference: | |
21 - Pentium III (Anderson) | |
22 - M68060 (Nikl) | |
23 */ | |
24 #ifdef POSTINC | |
25 # define OFF 0 | |
26 # define PUP(a) *(a)++ | |
27 #else | 13 #else |
28 # define OFF 1 | |
29 # define PUP(a) *++(a) | |
30 #endif | |
31 | 14 |
32 /* | 15 /* |
33 Decode literal, length, and distance codes and write out the resulting | 16 Decode literal, length, and distance codes and write out the resulting |
34 literal and match bytes until either not enough input or output is | 17 literal and match bytes until either not enough input or output is |
35 available, an end-of-block is encountered, or a data error is encountered. | 18 available, an end-of-block is encountered, or a data error is encountered. |
36 When large enough input and output buffers are supplied to inflate(), for | 19 When large enough input and output buffers are supplied to inflate(), for |
37 example, a 16K input buffer and a 64K output buffer, more than 95% of the | 20 example, a 16K input buffer and a 64K output buffer, more than 95% of the |
38 inflate execution time is spent in this routine. | 21 inflate execution time is spent in this routine. |
39 | 22 |
40 Entry assumptions: | 23 Entry assumptions: |
(...skipping 48 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
89 unsigned dmask; /* mask for first level of distance codes */ | 72 unsigned dmask; /* mask for first level of distance codes */ |
90 code here; /* retrieved table entry */ | 73 code here; /* retrieved table entry */ |
91 unsigned op; /* code bits, operation, extra bits, or */ | 74 unsigned op; /* code bits, operation, extra bits, or */ |
92 /* window position, window bytes to copy */ | 75 /* window position, window bytes to copy */ |
93 unsigned len; /* match length, unused bytes */ | 76 unsigned len; /* match length, unused bytes */ |
94 unsigned dist; /* match distance */ | 77 unsigned dist; /* match distance */ |
95 unsigned char FAR *from; /* where to copy match from */ | 78 unsigned char FAR *from; /* where to copy match from */ |
96 | 79 |
97 /* copy state to local variables */ | 80 /* copy state to local variables */ |
98 state = (struct inflate_state FAR *)strm->state; | 81 state = (struct inflate_state FAR *)strm->state; |
99 in = strm->next_in - OFF; | 82 in = strm->next_in; |
100 last = in + (strm->avail_in - 5); | 83 last = in + (strm->avail_in - 5); |
101 out = strm->next_out - OFF; | 84 out = strm->next_out; |
102 beg = out - (start - strm->avail_out); | 85 beg = out - (start - strm->avail_out); |
103 end = out + (strm->avail_out - 257); | 86 end = out + (strm->avail_out - 257); |
104 #ifdef INFLATE_STRICT | 87 #ifdef INFLATE_STRICT |
105 dmax = state->dmax; | 88 dmax = state->dmax; |
106 #endif | 89 #endif |
107 wsize = state->wsize; | 90 wsize = state->wsize; |
108 whave = state->whave; | 91 whave = state->whave; |
109 wnext = state->wnext; | 92 wnext = state->wnext; |
110 window = state->window; | 93 window = state->window; |
111 hold = state->hold; | 94 hold = state->hold; |
112 bits = state->bits; | 95 bits = state->bits; |
113 lcode = state->lencode; | 96 lcode = state->lencode; |
114 dcode = state->distcode; | 97 dcode = state->distcode; |
115 lmask = (1U << state->lenbits) - 1; | 98 lmask = (1U << state->lenbits) - 1; |
116 dmask = (1U << state->distbits) - 1; | 99 dmask = (1U << state->distbits) - 1; |
117 | 100 |
118 /* decode literals and length/distances until end-of-block or not enough | 101 /* decode literals and length/distances until end-of-block or not enough |
119 input data or output space */ | 102 input data or output space */ |
120 do { | 103 do { |
121 if (bits < 15) { | 104 if (bits < 15) { |
122 hold += (unsigned long)(PUP(in)) << bits; | 105 hold += (unsigned long)(*in++) << bits; |
123 bits += 8; | 106 bits += 8; |
124 hold += (unsigned long)(PUP(in)) << bits; | 107 hold += (unsigned long)(*in++) << bits; |
125 bits += 8; | 108 bits += 8; |
126 } | 109 } |
127 here = lcode[hold & lmask]; | 110 here = lcode[hold & lmask]; |
128 dolen: | 111 dolen: |
129 op = (unsigned)(here.bits); | 112 op = (unsigned)(here.bits); |
130 hold >>= op; | 113 hold >>= op; |
131 bits -= op; | 114 bits -= op; |
132 op = (unsigned)(here.op); | 115 op = (unsigned)(here.op); |
133 if (op == 0) { /* literal */ | 116 if (op == 0) { /* literal */ |
134 Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ? | 117 Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ? |
135 "inflate: literal '%c'\n" : | 118 "inflate: literal '%c'\n" : |
136 "inflate: literal 0x%02x\n", here.val)); | 119 "inflate: literal 0x%02x\n", here.val)); |
137 PUP(out) = (unsigned char)(here.val); | 120 *out++ = (unsigned char)(here.val); |
138 } | 121 } |
139 else if (op & 16) { /* length base */ | 122 else if (op & 16) { /* length base */ |
140 len = (unsigned)(here.val); | 123 len = (unsigned)(here.val); |
141 op &= 15; /* number of extra bits */ | 124 op &= 15; /* number of extra bits */ |
142 if (op) { | 125 if (op) { |
143 if (bits < op) { | 126 if (bits < op) { |
144 hold += (unsigned long)(PUP(in)) << bits; | 127 hold += (unsigned long)(*in++) << bits; |
145 bits += 8; | 128 bits += 8; |
146 } | 129 } |
147 len += (unsigned)hold & ((1U << op) - 1); | 130 len += (unsigned)hold & ((1U << op) - 1); |
148 hold >>= op; | 131 hold >>= op; |
149 bits -= op; | 132 bits -= op; |
150 } | 133 } |
151 Tracevv((stderr, "inflate: length %u\n", len)); | 134 Tracevv((stderr, "inflate: length %u\n", len)); |
152 if (bits < 15) { | 135 if (bits < 15) { |
153 hold += (unsigned long)(PUP(in)) << bits; | 136 hold += (unsigned long)(*in++) << bits; |
154 bits += 8; | 137 bits += 8; |
155 hold += (unsigned long)(PUP(in)) << bits; | 138 hold += (unsigned long)(*in++) << bits; |
156 bits += 8; | 139 bits += 8; |
157 } | 140 } |
158 here = dcode[hold & dmask]; | 141 here = dcode[hold & dmask]; |
159 dodist: | 142 dodist: |
160 op = (unsigned)(here.bits); | 143 op = (unsigned)(here.bits); |
161 hold >>= op; | 144 hold >>= op; |
162 bits -= op; | 145 bits -= op; |
163 op = (unsigned)(here.op); | 146 op = (unsigned)(here.op); |
164 if (op & 16) { /* distance base */ | 147 if (op & 16) { /* distance base */ |
165 dist = (unsigned)(here.val); | 148 dist = (unsigned)(here.val); |
166 op &= 15; /* number of extra bits */ | 149 op &= 15; /* number of extra bits */ |
167 if (bits < op) { | 150 if (bits < op) { |
168 hold += (unsigned long)(PUP(in)) << bits; | 151 hold += (unsigned long)(*in++) << bits; |
169 bits += 8; | 152 bits += 8; |
170 if (bits < op) { | 153 if (bits < op) { |
171 hold += (unsigned long)(PUP(in)) << bits; | 154 hold += (unsigned long)(*in++) << bits; |
172 bits += 8; | 155 bits += 8; |
173 } | 156 } |
174 } | 157 } |
175 dist += (unsigned)hold & ((1U << op) - 1); | 158 dist += (unsigned)hold & ((1U << op) - 1); |
176 #ifdef INFLATE_STRICT | 159 #ifdef INFLATE_STRICT |
177 if (dist > dmax) { | 160 if (dist > dmax) { |
178 strm->msg = (char *)"invalid distance too far back"; | 161 strm->msg = (char *)"invalid distance too far back"; |
179 state->mode = BAD; | 162 state->mode = BAD; |
180 break; | 163 break; |
181 } | 164 } |
182 #endif | 165 #endif |
183 hold >>= op; | 166 hold >>= op; |
184 bits -= op; | 167 bits -= op; |
185 Tracevv((stderr, "inflate: distance %u\n", dist)); | 168 Tracevv((stderr, "inflate: distance %u\n", dist)); |
186 op = (unsigned)(out - beg); /* max distance in output */ | 169 op = (unsigned)(out - beg); /* max distance in output */ |
187 if (dist > op) { /* see if copy from window */ | 170 if (dist > op) { /* see if copy from window */ |
188 op = dist - op; /* distance back in window */ | 171 op = dist - op; /* distance back in window */ |
189 if (op > whave) { | 172 if (op > whave) { |
190 if (state->sane) { | 173 if (state->sane) { |
191 strm->msg = | 174 strm->msg = |
192 (char *)"invalid distance too far back"; | 175 (char *)"invalid distance too far back"; |
193 state->mode = BAD; | 176 state->mode = BAD; |
194 break; | 177 break; |
195 } | 178 } |
196 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR | 179 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR |
197 if (len <= op - whave) { | 180 if (len <= op - whave) { |
198 do { | 181 do { |
199 PUP(out) = 0; | 182 *out++ = 0; |
200 } while (--len); | 183 } while (--len); |
201 continue; | 184 continue; |
202 } | 185 } |
203 len -= op - whave; | 186 len -= op - whave; |
204 do { | 187 do { |
205 PUP(out) = 0; | 188 *out++ = 0; |
206 } while (--op > whave); | 189 } while (--op > whave); |
207 if (op == 0) { | 190 if (op == 0) { |
208 from = out - dist; | 191 from = out - dist; |
209 do { | 192 do { |
210 PUP(out) = PUP(from); | 193 *out++ = *from++; |
211 } while (--len); | 194 } while (--len); |
212 continue; | 195 continue; |
213 } | 196 } |
214 #endif | 197 #endif |
215 } | 198 } |
216 from = window - OFF; | 199 from = window; |
217 if (wnext == 0) { /* very common case */ | 200 if (wnext == 0) { /* very common case */ |
218 from += wsize - op; | 201 from += wsize - op; |
219 if (op < len) { /* some from window */ | 202 if (op < len) { /* some from window */ |
220 len -= op; | 203 len -= op; |
221 do { | 204 do { |
222 PUP(out) = PUP(from); | 205 *out++ = *from++; |
223 } while (--op); | 206 } while (--op); |
224 from = out - dist; /* rest from output */ | 207 from = out - dist; /* rest from output */ |
225 } | 208 } |
226 } | 209 } |
227 else if (wnext < op) { /* wrap around window */ | 210 else if (wnext < op) { /* wrap around window */ |
228 from += wsize + wnext - op; | 211 from += wsize + wnext - op; |
229 op -= wnext; | 212 op -= wnext; |
230 if (op < len) { /* some from end of window */ | 213 if (op < len) { /* some from end of window */ |
231 len -= op; | 214 len -= op; |
232 do { | 215 do { |
233 PUP(out) = PUP(from); | 216 *out++ = *from++; |
234 } while (--op); | 217 } while (--op); |
235 from = window - OFF; | 218 from = window; |
236 if (wnext < len) { /* some from start of window */ | 219 if (wnext < len) { /* some from start of window */ |
237 op = wnext; | 220 op = wnext; |
238 len -= op; | 221 len -= op; |
239 do { | 222 do { |
240 PUP(out) = PUP(from); | 223 *out++ = *from++; |
241 } while (--op); | 224 } while (--op); |
242 from = out - dist; /* rest from output */ | 225 from = out - dist; /* rest from output */ |
243 } | 226 } |
244 } | 227 } |
245 } | 228 } |
246 else { /* contiguous in window */ | 229 else { /* contiguous in window */ |
247 from += wnext - op; | 230 from += wnext - op; |
248 if (op < len) { /* some from window */ | 231 if (op < len) { /* some from window */ |
249 len -= op; | 232 len -= op; |
250 do { | 233 do { |
251 PUP(out) = PUP(from); | 234 *out++ = *from++; |
252 } while (--op); | 235 } while (--op); |
253 from = out - dist; /* rest from output */ | 236 from = out - dist; /* rest from output */ |
254 } | 237 } |
255 } | 238 } |
256 while (len > 2) { | 239 while (len > 2) { |
257 PUP(out) = PUP(from); | 240 *out++ = *from++; |
258 PUP(out) = PUP(from); | 241 *out++ = *from++; |
259 PUP(out) = PUP(from); | 242 *out++ = *from++; |
260 len -= 3; | 243 len -= 3; |
261 } | 244 } |
262 if (len) { | 245 if (len) { |
263 PUP(out) = PUP(from); | 246 *out++ = *from++; |
264 if (len > 1) | 247 if (len > 1) |
265 PUP(out) = PUP(from); | 248 *out++ = *from++; |
266 } | 249 } |
267 } | 250 } |
268 else { | 251 else { |
269 from = out - dist; /* copy direct from output */ | 252 from = out - dist; /* copy direct from output */ |
270 do { /* minimum length is three */ | 253 do { /* minimum length is three */ |
271 PUP(out) = PUP(from); | 254 *out++ = *from++; |
272 PUP(out) = PUP(from); | 255 *out++ = *from++; |
273 PUP(out) = PUP(from); | 256 *out++ = *from++; |
274 len -= 3; | 257 len -= 3; |
275 } while (len > 2); | 258 } while (len > 2); |
276 if (len) { | 259 if (len) { |
277 PUP(out) = PUP(from); | 260 *out++ = *from++; |
278 if (len > 1) | 261 if (len > 1) |
279 PUP(out) = PUP(from); | 262 *out++ = *from++; |
280 } | 263 } |
281 } | 264 } |
282 } | 265 } |
283 else if ((op & 64) == 0) { /* 2nd level distance code */ | 266 else if ((op & 64) == 0) { /* 2nd level distance code */ |
284 here = dcode[here.val + (hold & ((1U << op) - 1))]; | 267 here = dcode[here.val + (hold & ((1U << op) - 1))]; |
285 goto dodist; | 268 goto dodist; |
286 } | 269 } |
287 else { | 270 else { |
288 strm->msg = (char *)"invalid distance code"; | 271 strm->msg = (char *)"invalid distance code"; |
289 state->mode = BAD; | 272 state->mode = BAD; |
(...skipping 16 matching lines...) Expand all Loading... |
306 } | 289 } |
307 } while (in < last && out < end); | 290 } while (in < last && out < end); |
308 | 291 |
309 /* return unused bytes (on entry, bits < 8, so in won't go too far back) */ | 292 /* return unused bytes (on entry, bits < 8, so in won't go too far back) */ |
310 len = bits >> 3; | 293 len = bits >> 3; |
311 in -= len; | 294 in -= len; |
312 bits -= len << 3; | 295 bits -= len << 3; |
313 hold &= (1U << bits) - 1; | 296 hold &= (1U << bits) - 1; |
314 | 297 |
315 /* update state and return */ | 298 /* update state and return */ |
316 strm->next_in = in + OFF; | 299 strm->next_in = in; |
317 strm->next_out = out + OFF; | 300 strm->next_out = out; |
318 strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last)); | 301 strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last)); |
319 strm->avail_out = (unsigned)(out < end ? | 302 strm->avail_out = (unsigned)(out < end ? |
320 257 + (end - out) : 257 - (out - end)); | 303 257 + (end - out) : 257 - (out - end)); |
321 state->hold = hold; | 304 state->hold = hold; |
322 state->bits = bits; | 305 state->bits = bits; |
323 return; | 306 return; |
324 } | 307 } |
325 | 308 |
326 /* | 309 /* |
327 inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe): | 310 inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe): |
328 - Using bit fields for code structure | 311 - Using bit fields for code structure |
329 - Different op definition to avoid & for extra bits (do & for table bits) | 312 - Different op definition to avoid & for extra bits (do & for table bits) |
330 - Three separate decoding do-loops for direct, window, and wnext == 0 | 313 - Three separate decoding do-loops for direct, window, and wnext == 0 |
331 - Special case for distance > 1 copies to do overlapped load and store copy | 314 - Special case for distance > 1 copies to do overlapped load and store copy |
332 - Explicit branch predictions (based on measured branch probabilities) | 315 - Explicit branch predictions (based on measured branch probabilities) |
333 - Deferring match copy and interspersed it with decoding subsequent codes | 316 - Deferring match copy and interspersed it with decoding subsequent codes |
334 - Swapping literal/length else | 317 - Swapping literal/length else |
335 - Swapping window/direct else | 318 - Swapping window/direct else |
336 - Larger unrolled copy loops (three is about right) | 319 - Larger unrolled copy loops (three is about right) |
337 - Moving len -= 3 statement into middle of loop | 320 - Moving len -= 3 statement into middle of loop |
338 */ | 321 */ |
339 | 322 |
340 #endif /* !ASMINF */ | 323 #endif /* !ASMINF */ |
OLD | NEW |