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