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