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