File indexing completed on 2024-03-24 03:51:15
0001 /* inffast.c -- fast decoding 0002 * Copyright (C) 1995-2008, 2010, 2013 Mark Adler 0003 * For conditions of distribution and use, see copyright notice in zlib.h 0004 */ 0005 0006 #include "zutil.h" 0007 #include "inftrees.h" 0008 #include "inflate.h" 0009 #include "inffast.h" 0010 0011 #ifndef ASMINF 0012 0013 /* Allow machine dependent optimization for post-increment or pre-increment. 0014 Based on testing to date, 0015 Pre-increment preferred for: 0016 - PowerPC G3 (Adler) 0017 - MIPS R5000 (Randers-Pehrson) 0018 Post-increment preferred for: 0019 - none 0020 No measurable difference: 0021 - Pentium III (Anderson) 0022 - M68060 (Nikl) 0023 */ 0024 #ifdef POSTINC 0025 # define OFF 0 0026 # define PUP(a) *(a)++ 0027 #else 0028 # define OFF 1 0029 # define PUP(a) *++(a) 0030 #endif 0031 0032 /* 0033 Decode literal, length, and distance codes and write out the resulting 0034 literal and match bytes until either not enough input or output is 0035 available, an end-of-block is encountered, or a data error is encountered. 0036 When large enough input and output buffers are supplied to inflate(), for 0037 example, a 16K input buffer and a 64K output buffer, more than 95% of the 0038 inflate execution time is spent in this routine. 0039 0040 Entry assumptions: 0041 0042 state->mode == LEN 0043 strm->avail_in >= 6 0044 strm->avail_out >= 258 0045 start >= strm->avail_out 0046 state->bits < 8 0047 0048 On return, state->mode is one of: 0049 0050 LEN -- ran out of enough output space or enough available input 0051 TYPE -- reached end of block code, inflate() to interpret next block 0052 BAD -- error in block data 0053 0054 Notes: 0055 0056 - The maximum input bits used by a length/distance pair is 15 bits for the 0057 length code, 5 bits for the length extra, 15 bits for the distance code, 0058 and 13 bits for the distance extra. This totals 48 bits, or six bytes. 0059 Therefore if strm->avail_in >= 6, then there is enough input to avoid 0060 checking for available input while decoding. 0061 0062 - The maximum bytes that a single length/distance pair can output is 258 0063 bytes, which is the maximum length that can be coded. inflate_fast() 0064 requires strm->avail_out >= 258 for each loop to avoid checking for 0065 output space. 0066 */ 0067 void ZLIB_INTERNAL inflate_fast(strm, start) 0068 z_streamp strm; 0069 unsigned start; /* inflate()'s starting value for strm->avail_out */ 0070 { 0071 struct inflate_state FAR *state; 0072 z_const unsigned char FAR *in; /* local strm->next_in */ 0073 z_const unsigned char FAR *last; /* have enough input while in < last */ 0074 unsigned char FAR *out; /* local strm->next_out */ 0075 unsigned char FAR *beg; /* inflate()'s initial strm->next_out */ 0076 unsigned char FAR *end; /* while out < end, enough space available */ 0077 #ifdef INFLATE_STRICT 0078 unsigned dmax; /* maximum distance from zlib header */ 0079 #endif 0080 unsigned wsize; /* window size or zero if not using window */ 0081 unsigned whave; /* valid bytes in the window */ 0082 unsigned wnext; /* window write index */ 0083 unsigned char FAR *window; /* allocated sliding window, if wsize != 0 */ 0084 unsigned long hold; /* local strm->hold */ 0085 unsigned bits; /* local strm->bits */ 0086 code const FAR *lcode; /* local strm->lencode */ 0087 code const FAR *dcode; /* local strm->distcode */ 0088 unsigned lmask; /* mask for first level of length codes */ 0089 unsigned dmask; /* mask for first level of distance codes */ 0090 code here; /* retrieved table entry */ 0091 unsigned op; /* code bits, operation, extra bits, or */ 0092 /* window position, window bytes to copy */ 0093 unsigned len; /* match length, unused bytes */ 0094 unsigned dist; /* match distance */ 0095 unsigned char FAR *from; /* where to copy match from */ 0096 0097 /* copy state to local variables */ 0098 state = (struct inflate_state FAR *)strm->state; 0099 in = strm->next_in - OFF; 0100 last = in + (strm->avail_in - 5); 0101 out = strm->next_out - OFF; 0102 beg = out - (start - strm->avail_out); 0103 end = out + (strm->avail_out - 257); 0104 #ifdef INFLATE_STRICT 0105 dmax = state->dmax; 0106 #endif 0107 wsize = state->wsize; 0108 whave = state->whave; 0109 wnext = state->wnext; 0110 window = state->window; 0111 hold = state->hold; 0112 bits = state->bits; 0113 lcode = state->lencode; 0114 dcode = state->distcode; 0115 lmask = (1U << state->lenbits) - 1; 0116 dmask = (1U << state->distbits) - 1; 0117 0118 /* decode literals and length/distances until end-of-block or not enough 0119 input data or output space */ 0120 do { 0121 if (bits < 15) { 0122 hold += (unsigned long)(PUP(in)) << bits; 0123 bits += 8; 0124 hold += (unsigned long)(PUP(in)) << bits; 0125 bits += 8; 0126 } 0127 here = lcode[hold & lmask]; 0128 dolen: 0129 op = (unsigned)(here.bits); 0130 hold >>= op; 0131 bits -= op; 0132 op = (unsigned)(here.op); 0133 if (op == 0) { /* literal */ 0134 Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ? 0135 "inflate: literal '%c'\n" : 0136 "inflate: literal 0x%02x\n", here.val)); 0137 PUP(out) = (unsigned char)(here.val); 0138 } 0139 else if (op & 16) { /* length base */ 0140 len = (unsigned)(here.val); 0141 op &= 15; /* number of extra bits */ 0142 if (op) { 0143 if (bits < op) { 0144 hold += (unsigned long)(PUP(in)) << bits; 0145 bits += 8; 0146 } 0147 len += (unsigned)hold & ((1U << op) - 1); 0148 hold >>= op; 0149 bits -= op; 0150 } 0151 Tracevv((stderr, "inflate: length %u\n", len)); 0152 if (bits < 15) { 0153 hold += (unsigned long)(PUP(in)) << bits; 0154 bits += 8; 0155 hold += (unsigned long)(PUP(in)) << bits; 0156 bits += 8; 0157 } 0158 here = dcode[hold & dmask]; 0159 dodist: 0160 op = (unsigned)(here.bits); 0161 hold >>= op; 0162 bits -= op; 0163 op = (unsigned)(here.op); 0164 if (op & 16) { /* distance base */ 0165 dist = (unsigned)(here.val); 0166 op &= 15; /* number of extra bits */ 0167 if (bits < op) { 0168 hold += (unsigned long)(PUP(in)) << bits; 0169 bits += 8; 0170 if (bits < op) { 0171 hold += (unsigned long)(PUP(in)) << bits; 0172 bits += 8; 0173 } 0174 } 0175 dist += (unsigned)hold & ((1U << op) - 1); 0176 #ifdef INFLATE_STRICT 0177 if (dist > dmax) { 0178 strm->msg = (char *)"invalid distance too far back"; 0179 state->mode = BAD; 0180 break; 0181 } 0182 #endif 0183 hold >>= op; 0184 bits -= op; 0185 Tracevv((stderr, "inflate: distance %u\n", dist)); 0186 op = (unsigned)(out - beg); /* max distance in output */ 0187 if (dist > op) { /* see if copy from window */ 0188 op = dist - op; /* distance back in window */ 0189 if (op > whave) { 0190 if (state->sane) { 0191 strm->msg = 0192 (char *)"invalid distance too far back"; 0193 state->mode = BAD; 0194 break; 0195 } 0196 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR 0197 if (len <= op - whave) { 0198 do { 0199 PUP(out) = 0; 0200 } while (--len); 0201 continue; 0202 } 0203 len -= op - whave; 0204 do { 0205 PUP(out) = 0; 0206 } while (--op > whave); 0207 if (op == 0) { 0208 from = out - dist; 0209 do { 0210 PUP(out) = PUP(from); 0211 } while (--len); 0212 continue; 0213 } 0214 #endif 0215 } 0216 from = window - OFF; 0217 if (wnext == 0) { /* very common case */ 0218 from += wsize - op; 0219 if (op < len) { /* some from window */ 0220 len -= op; 0221 do { 0222 PUP(out) = PUP(from); 0223 } while (--op); 0224 from = out - dist; /* rest from output */ 0225 } 0226 } 0227 else if (wnext < op) { /* wrap around window */ 0228 from += wsize + wnext - op; 0229 op -= wnext; 0230 if (op < len) { /* some from end of window */ 0231 len -= op; 0232 do { 0233 PUP(out) = PUP(from); 0234 } while (--op); 0235 from = window - OFF; 0236 if (wnext < len) { /* some from start of window */ 0237 op = wnext; 0238 len -= op; 0239 do { 0240 PUP(out) = PUP(from); 0241 } while (--op); 0242 from = out - dist; /* rest from output */ 0243 } 0244 } 0245 } 0246 else { /* contiguous in window */ 0247 from += wnext - op; 0248 if (op < len) { /* some from window */ 0249 len -= op; 0250 do { 0251 PUP(out) = PUP(from); 0252 } while (--op); 0253 from = out - dist; /* rest from output */ 0254 } 0255 } 0256 while (len > 2) { 0257 PUP(out) = PUP(from); 0258 PUP(out) = PUP(from); 0259 PUP(out) = PUP(from); 0260 len -= 3; 0261 } 0262 if (len) { 0263 PUP(out) = PUP(from); 0264 if (len > 1) 0265 PUP(out) = PUP(from); 0266 } 0267 } 0268 else { 0269 from = out - dist; /* copy direct from output */ 0270 do { /* minimum length is three */ 0271 PUP(out) = PUP(from); 0272 PUP(out) = PUP(from); 0273 PUP(out) = PUP(from); 0274 len -= 3; 0275 } while (len > 2); 0276 if (len) { 0277 PUP(out) = PUP(from); 0278 if (len > 1) 0279 PUP(out) = PUP(from); 0280 } 0281 } 0282 } 0283 else if ((op & 64) == 0) { /* 2nd level distance code */ 0284 here = dcode[here.val + (hold & ((1U << op) - 1))]; 0285 goto dodist; 0286 } 0287 else { 0288 strm->msg = (char *)"invalid distance code"; 0289 state->mode = BAD; 0290 break; 0291 } 0292 } 0293 else if ((op & 64) == 0) { /* 2nd level length code */ 0294 here = lcode[here.val + (hold & ((1U << op) - 1))]; 0295 goto dolen; 0296 } 0297 else if (op & 32) { /* end-of-block */ 0298 Tracevv((stderr, "inflate: end of block\n")); 0299 state->mode = TYPE; 0300 break; 0301 } 0302 else { 0303 strm->msg = (char *)"invalid literal/length code"; 0304 state->mode = BAD; 0305 break; 0306 } 0307 } while (in < last && out < end); 0308 0309 /* return unused bytes (on entry, bits < 8, so in won't go too far back) */ 0310 len = bits >> 3; 0311 in -= len; 0312 bits -= len << 3; 0313 hold &= (1U << bits) - 1; 0314 0315 /* update state and return */ 0316 strm->next_in = in + OFF; 0317 strm->next_out = out + OFF; 0318 strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last)); 0319 strm->avail_out = (unsigned)(out < end ? 0320 257 + (end - out) : 257 - (out - end)); 0321 state->hold = hold; 0322 state->bits = bits; 0323 return; 0324 } 0325 0326 /* 0327 inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe): 0328 - Using bit fields for code structure 0329 - Different op definition to avoid & for extra bits (do & for table bits) 0330 - Three separate decoding do-loops for direct, window, and wnext == 0 0331 - Special case for distance > 1 copies to do overlapped load and store copy 0332 - Explicit branch predictions (based on measured branch probabilities) 0333 - Deferring match copy and interspersed it with decoding subsequent codes 0334 - Swapping literal/length else 0335 - Swapping window/direct else 0336 - Larger unrolled copy loops (three is about right) 0337 - Moving len -= 3 statement into middle of loop 0338 */ 0339 0340 #endif /* !ASMINF */