Fossil SCM

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

Keyboard Shortcuts

Open search /
Next entry (timeline) j
Previous entry (timeline) k
Open focused entry Enter
Show this help ?
Toggle theme Top nav button