1 | /* |
2 | * Copyright (c) 2008-2016 Apple Inc. All rights reserved. |
3 | * |
4 | * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ |
5 | * |
6 | * This file contains Original Code and/or Modifications of Original Code |
7 | * as defined in and that are subject to the Apple Public Source License |
8 | * Version 2.0 (the 'License'). You may not use this file except in |
9 | * compliance with the License. The rights granted to you under the License |
10 | * may not be used to create, or enable the creation or redistribution of, |
11 | * unlawful or unlicensed copies of an Apple operating system, or to |
12 | * circumvent, violate, or enable the circumvention or violation of, any |
13 | * terms of an Apple operating system software license agreement. |
14 | * |
15 | * Please obtain a copy of the License at |
16 | * http://www.opensource.apple.com/apsl/ and read it before using this file. |
17 | * |
18 | * The Original Code and all software distributed under the License are |
19 | * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER |
20 | * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, |
21 | * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, |
22 | * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. |
23 | * Please see the License for the specific language governing rights and |
24 | * limitations under the License. |
25 | * |
26 | * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ |
27 | */ |
28 | /* inffast.c -- fast decoding |
29 | * Copyright (C) 1995-2004 Mark Adler |
30 | * For conditions of distribution and use, see copyright notice in zlib.h |
31 | */ |
32 | |
33 | |
34 | #include "zutil.h" |
35 | #include "inftrees.h" |
36 | #include "inflate.h" |
37 | #include "inffast.h" |
38 | |
39 | #ifndef ASMINF |
40 | |
41 | /* Allow machine dependent optimization for post-increment or pre-increment. |
42 | Based on testing to date, |
43 | Pre-increment preferred for: |
44 | - PowerPC G3 (Adler) |
45 | - MIPS R5000 (Randers-Pehrson) |
46 | Post-increment preferred for: |
47 | - none |
48 | No measurable difference: |
49 | - Pentium III (Anderson) |
50 | - M68060 (Nikl) |
51 | */ |
52 | #ifdef POSTINC |
53 | # define OFF 0 |
54 | # define PUP(a) *(a)++ |
55 | #else |
56 | # define OFF 1 |
57 | # define PUP(a) *++(a) |
58 | #endif |
59 | |
60 | /* |
61 | Decode literal, length, and distance codes and write out the resulting |
62 | literal and match bytes until either not enough input or output is |
63 | available, an end-of-block is encountered, or a data error is encountered. |
64 | When large enough input and output buffers are supplied to inflate(), for |
65 | example, a 16K input buffer and a 64K output buffer, more than 95% of the |
66 | inflate execution time is spent in this routine. |
67 | |
68 | Entry assumptions: |
69 | |
70 | state->mode == LEN |
71 | strm->avail_in >= 6 |
72 | strm->avail_out >= 258 |
73 | start >= strm->avail_out |
74 | state->bits < 8 |
75 | |
76 | On return, state->mode is one of: |
77 | |
78 | LEN -- ran out of enough output space or enough available input |
79 | TYPE -- reached end of block code, inflate() to interpret next block |
80 | BAD -- error in block data |
81 | |
82 | Notes: |
83 | |
84 | - The maximum input bits used by a length/distance pair is 15 bits for the |
85 | length code, 5 bits for the length extra, 15 bits for the distance code, |
86 | and 13 bits for the distance extra. This totals 48 bits, or six bytes. |
87 | Therefore if strm->avail_in >= 6, then there is enough input to avoid |
88 | checking for available input while decoding. |
89 | |
90 | - The maximum bytes that a single length/distance pair can output is 258 |
91 | bytes, which is the maximum length that can be coded. inflate_fast() |
92 | requires strm->avail_out >= 258 for each loop to avoid checking for |
93 | output space. |
94 | |
95 | @param start inflate()'s starting value for strm->avail_out |
96 | */ |
97 | void |
98 | inflate_fast(z_streamp strm, unsigned start) |
99 | { |
100 | struct inflate_state FAR *state; |
101 | unsigned char FAR *in; /* local strm->next_in */ |
102 | unsigned char FAR *last; /* while in < last, enough input available */ |
103 | unsigned char FAR *out; /* local strm->next_out */ |
104 | unsigned char FAR *beg; /* inflate()'s initial strm->next_out */ |
105 | unsigned char FAR *end; /* while out < end, enough space available */ |
106 | #ifdef INFLATE_STRICT |
107 | unsigned dmax; /* maximum distance from zlib header */ |
108 | #endif |
109 | unsigned wsize; /* window size or zero if not using window */ |
110 | unsigned whave; /* valid bytes in the window */ |
111 | unsigned write; /* window write index */ |
112 | unsigned char FAR *window; /* allocated sliding window, if wsize != 0 */ |
113 | unsigned long hold; /* local strm->hold */ |
114 | unsigned bits; /* local strm->bits */ |
115 | code const FAR *lcode; /* local strm->lencode */ |
116 | code const FAR *dcode; /* local strm->distcode */ |
117 | unsigned lmask; /* mask for first level of length codes */ |
118 | unsigned dmask; /* mask for first level of distance codes */ |
119 | code this; /* retrieved table entry */ |
120 | unsigned op; /* code bits, operation, extra bits, or */ |
121 | /* window position, window bytes to copy */ |
122 | unsigned len; /* match length, unused bytes */ |
123 | unsigned dist; /* match distance */ |
124 | unsigned char FAR *from; /* where to copy match from */ |
125 | |
126 | /* copy state to local variables */ |
127 | state = (struct inflate_state FAR *)strm->state; |
128 | in = strm->next_in - OFF; |
129 | last = in + (strm->avail_in - 5); |
130 | out = strm->next_out - OFF; |
131 | beg = out - (start - strm->avail_out); |
132 | end = out + (strm->avail_out - 257); |
133 | #ifdef INFLATE_STRICT |
134 | dmax = state->dmax; |
135 | #endif |
136 | wsize = state->wsize; |
137 | whave = state->whave; |
138 | write = state->write; |
139 | window = state->window; |
140 | hold = state->hold; |
141 | bits = state->bits; |
142 | lcode = state->lencode; |
143 | dcode = state->distcode; |
144 | lmask = (1U << state->lenbits) - 1; |
145 | dmask = (1U << state->distbits) - 1; |
146 | |
147 | /* decode literals and length/distances until end-of-block or not enough |
148 | input data or output space */ |
149 | do { |
150 | if (bits < 15) { |
151 | hold += (unsigned long)(PUP(in)) << bits; |
152 | bits += 8; |
153 | hold += (unsigned long)(PUP(in)) << bits; |
154 | bits += 8; |
155 | } |
156 | this = lcode[hold & lmask]; |
157 | dolen: |
158 | op = (unsigned)(this.bits); |
159 | hold >>= op; |
160 | bits -= op; |
161 | op = (unsigned)(this.op); |
162 | if (op == 0) { /* literal */ |
163 | Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ? |
164 | "inflate: literal '%c'\n" : |
165 | "inflate: literal 0x%02x\n" , this.val)); |
166 | PUP(out) = (unsigned char)(this.val); |
167 | } |
168 | else if (op & 16) { /* length base */ |
169 | len = (unsigned)(this.val); |
170 | op &= 15; /* number of extra bits */ |
171 | if (op) { |
172 | if (bits < op) { |
173 | hold += (unsigned long)(PUP(in)) << bits; |
174 | bits += 8; |
175 | } |
176 | len += (unsigned)hold & ((1U << op) - 1); |
177 | hold >>= op; |
178 | bits -= op; |
179 | } |
180 | Tracevv((stderr, "inflate: length %u\n" , len)); |
181 | if (bits < 15) { |
182 | hold += (unsigned long)(PUP(in)) << bits; |
183 | bits += 8; |
184 | hold += (unsigned long)(PUP(in)) << bits; |
185 | bits += 8; |
186 | } |
187 | this = dcode[hold & dmask]; |
188 | dodist: |
189 | op = (unsigned)(this.bits); |
190 | hold >>= op; |
191 | bits -= op; |
192 | op = (unsigned)(this.op); |
193 | if (op & 16) { /* distance base */ |
194 | dist = (unsigned)(this.val); |
195 | op &= 15; /* number of extra bits */ |
196 | if (bits < op) { |
197 | hold += (unsigned long)(PUP(in)) << bits; |
198 | bits += 8; |
199 | if (bits < op) { |
200 | hold += (unsigned long)(PUP(in)) << bits; |
201 | bits += 8; |
202 | } |
203 | } |
204 | dist += (unsigned)hold & ((1U << op) - 1); |
205 | #ifdef INFLATE_STRICT |
206 | if (dist > dmax) { |
207 | strm->msg = (char *)"invalid distance too far back" ; |
208 | state->mode = BAD; |
209 | break; |
210 | } |
211 | #endif |
212 | hold >>= op; |
213 | bits -= op; |
214 | Tracevv((stderr, "inflate: distance %u\n" , dist)); |
215 | op = (unsigned)(out - beg); /* max distance in output */ |
216 | if (dist > op) { /* see if copy from window */ |
217 | op = dist - op; /* distance back in window */ |
218 | if (op > whave) { |
219 | strm->msg = (char *)"invalid distance too far back" ; |
220 | state->mode = BAD; |
221 | break; |
222 | } |
223 | from = window - OFF; |
224 | if (write == 0) { /* very common case */ |
225 | from += wsize - op; |
226 | if (op < len) { /* some from window */ |
227 | len -= op; |
228 | do { |
229 | PUP(out) = PUP(from); |
230 | } while (--op); |
231 | from = out - dist; /* rest from output */ |
232 | } |
233 | } |
234 | else if (write < op) { /* wrap around window */ |
235 | from += wsize + write - op; |
236 | op -= write; |
237 | if (op < len) { /* some from end of window */ |
238 | len -= op; |
239 | do { |
240 | PUP(out) = PUP(from); |
241 | } while (--op); |
242 | from = window - OFF; |
243 | if (write < len) { /* some from start of window */ |
244 | op = write; |
245 | len -= op; |
246 | do { |
247 | PUP(out) = PUP(from); |
248 | } while (--op); |
249 | from = out - dist; /* rest from output */ |
250 | } |
251 | } |
252 | } |
253 | else { /* contiguous in window */ |
254 | from += write - op; |
255 | if (op < len) { /* some from window */ |
256 | len -= op; |
257 | do { |
258 | PUP(out) = PUP(from); |
259 | } while (--op); |
260 | from = out - dist; /* rest from output */ |
261 | } |
262 | } |
263 | while (len > 2) { |
264 | PUP(out) = PUP(from); |
265 | PUP(out) = PUP(from); |
266 | PUP(out) = PUP(from); |
267 | len -= 3; |
268 | } |
269 | if (len) { |
270 | PUP(out) = PUP(from); |
271 | if (len > 1) |
272 | PUP(out) = PUP(from); |
273 | } |
274 | } |
275 | else { |
276 | from = out - dist; /* copy direct from output */ |
277 | do { /* minimum length is three */ |
278 | PUP(out) = PUP(from); |
279 | PUP(out) = PUP(from); |
280 | PUP(out) = PUP(from); |
281 | len -= 3; |
282 | } while (len > 2); |
283 | if (len) { |
284 | PUP(out) = PUP(from); |
285 | if (len > 1) |
286 | PUP(out) = PUP(from); |
287 | } |
288 | } |
289 | } |
290 | else if ((op & 64) == 0) { /* 2nd level distance code */ |
291 | this = dcode[this.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 | this = lcode[this.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 + OFF; |
324 | strm->next_out = out + OFF; |
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 write == 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 */ |
348 | |