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