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