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