1 /* $OpenBSD: inffast.c,v 1.13 2021/07/04 14:24:49 tb Exp $ */ 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 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 #ifdef SMALL 176 strm->msg = "error"; 177 #else 178 strm->msg = 179 (char *)"invalid distance too far back"; 180 #endif 181 state->mode = BAD; 182 break; 183 } 184 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR 185 if (len <= op - whave) { 186 do { 187 *out++ = 0; 188 } while (--len); 189 continue; 190 } 191 len -= op - whave; 192 do { 193 *out++ = 0; 194 } while (--op > whave); 195 if (op == 0) { 196 from = out - dist; 197 do { 198 *out++ = *from++; 199 } while (--len); 200 continue; 201 } 202 #endif 203 } 204 from = window; 205 if (wnext == 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 (wnext < op) { /* wrap around window */ 216 from += wsize + wnext - op; 217 op -= wnext; 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 (wnext < len) { /* some from start of window */ 225 op = wnext; 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 += wnext - 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 here = dcode[here.val + (hold & ((1U << op) - 1))]; 273 goto dodist; 274 } 275 else { 276 #ifdef SMALL 277 strm->msg = "error"; 278 #else 279 strm->msg = (char *)"invalid distance code"; 280 #endif 281 state->mode = BAD; 282 break; 283 } 284 } 285 else if ((op & 64) == 0) { /* 2nd level length code */ 286 here = lcode[here.val + (hold & ((1U << op) - 1))]; 287 goto dolen; 288 } 289 else if (op & 32) { /* end-of-block */ 290 Tracevv((stderr, "inflate: end of block\n")); 291 state->mode = TYPE; 292 break; 293 } 294 else { 295 #ifdef SMALL 296 strm->msg = "error"; 297 #else 298 strm->msg = (char *)"invalid literal/length code"; 299 #endif 300 state->mode = BAD; 301 break; 302 } 303 } while (in < last && out < end); 304 305 /* return unused bytes (on entry, bits < 8, so in won't go too far back) */ 306 len = bits >> 3; 307 in -= len; 308 bits -= len << 3; 309 hold &= (1U << bits) - 1; 310 311 /* update state and return */ 312 strm->next_in = in; 313 strm->next_out = out; 314 strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last)); 315 strm->avail_out = (unsigned)(out < end ? 316 257 + (end - out) : 257 - (out - end)); 317 state->hold = hold; 318 state->bits = bits; 319 return; 320 } 321 322 /* 323 inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe): 324 - Using bit fields for code structure 325 - Different op definition to avoid & for extra bits (do & for table bits) 326 - Three separate decoding do-loops for direct, window, and wnext == 0 327 - Special case for distance > 1 copies to do overlapped load and store copy 328 - Explicit branch predictions (based on measured branch probabilities) 329 - Deferring match copy and interspersed it with decoding subsequent codes 330 - Swapping literal/length else 331 - Swapping window/direct else 332 - Larger unrolled copy loops (three is about right) 333 - Moving len -= 3 statement into middle of loop 334 */ 335 336 #endif /* !ASMINF */ 337