text: /* inffast.c -- fast decoding
   * Copyright (C) 1995-2004 Mark Adler
   * For conditions of distribution and use, see copyright notice in zlib.h
   */
  
  #include "zutil.h"
  #include "inftrees.h"
  #include "inflate.h"
  #include "inffast.h"
  
  #ifndef ASMINF
  
  /* Allow machine dependent optimization for post-increment or pre-increment.
     Based on testing to date,
     Pre-increment preferred for:
     - PowerPC G3 (Adler)
     - MIPS R5000 (Randers-Pehrson)
     Post-increment preferred for:
     - none
     No measurable difference:
     - Pentium III (Anderson)
     - M68060 (Nikl)
   */
  #ifdef POSTINC
  #define OFF 0
  #define PUP(a) *(a)++
  #else
  #define OFF 1
  #define PUP(a) *++(a)
  #endif
  
  /*
     Decode literal, length, and distance codes and write out the resulting
     literal and match bytes until either not enough input or output is
     available, an end-of-block is encountered, or a data error is encountered.
     When large enough input and output buffers are supplied to inflate(), for
     example, a 16K input buffer and a 64K output buffer, more than 95% of the
     inflate execution time is spent in this routine.
  
     Entry assumptions:
  
          state->mode == LEN
          strm->avail_in >= 6
          strm->avail_out >= 258
          start >= strm->avail_out
          state->bits < 8
  
     On return, state->mode is one of:
  
          LEN -- ran out of enough output space or enough available input
          TYPE -- reached end of block code, inflate() to interpret next block
          BAD -- error in block data
  
     Notes:
  
      - The maximum input bits used by a length/distance pair is 15 bits for the
        length code, 5 bits for the length extra, 15 bits for the distance code,
        and 13 bits for the distance extra.  This totals 48 bits, or six bytes.
        Therefore if strm->avail_in >= 6, then there is enough input to avoid
        checking for available input while decoding.
  
      - The maximum bytes that a single length/distance pair can output is 258
        bytes, which is the maximum length that can be coded.  inflate_fast()
        requires strm->avail_out >= 258 for each loop to avoid checking for
        output space.
   */
  void inflate_fast(strm, start) z_streamp strm;
  unsigned start; /* inflate()'s starting value for strm->avail_out */
  {
    struct inflate_state FAR *state;
    unsigned char FAR *in;   /* local strm->next_in */
    unsigned char FAR *last; /* while in < last, enough input available */
    unsigned char FAR *out;  /* local strm->next_out */
    unsigned char FAR *beg;  /* inflate()'s initial strm->next_out */
    unsigned char FAR *end;  /* while out < end, enough space available */
  #ifdef INFLATE_STRICT
    unsigned dmax; /* maximum distance from zlib header */
  #endif
    unsigned wsize;            /* window size or zero if not using window */
    unsigned whave;            /* valid bytes in the window */
    unsigned write;            /* window write index */
    unsigned char FAR *window; /* allocated sliding window, if wsize != 0 */
    unsigned long hold;        /* local strm->hold */
    unsigned bits;             /* local strm->bits */
    code const FAR *lcode;     /* local strm->lencode */
    code const FAR *dcode;     /* local strm->distcode */
    unsigned lmask;            /* mask for first level of length codes */
    unsigned dmask;            /* mask for first level of distance codes */
    code this;                 /* retrieved table entry */
    unsigned op;               /* code bits, operation, extra bits, or */
                               /*  window position, window bytes to copy */
    unsigned len;              /* match length, unused bytes */
    unsigned dist;             /* match distance */
    unsigned char FAR *from;   /* where to copy match from */
  
    /* copy state to local variables */
    state = (struct inflate_state FAR *)strm->state;
    in = strm->next_in - OFF;
    last = in + (strm->avail_in - 5);
    out = strm->next_out - OFF;
    beg = out - (start - strm->avail_out);
    end = out + (strm->avail_out - 257);
  #ifdef INFLATE_STRICT
    dmax = state->dmax;
  #endif
    wsize = state->wsize;
    whave = state->whave;
    write = state->write;
    window = state->window;
    hold = state->hold;
    bits = state->bits;
    lcode = state->lencode;
    dcode = state->distcode;
    lmask = (1U << state->lenbits) - 1;
    dmask = (1U << state->distbits) - 1;
  
    /* decode literals and length/distances until end-of-block or not enough
       input data or output space */
    do {
      if (bits < 15) {
        hold += (unsigned long)(PUP(in)) << bits;
        bits += 8;
        hold += (unsigned long)(PUP(in)) << bits;
        bits += 8;
      }
      this = lcode[hold & lmask];
    dolen:
      op = (unsigned)(this.bits);
      hold >>= op;
      bits -= op;
      op = (unsigned)(this.op);
      if (op == 0) {/* literal */
        Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f
                             ? "inflate:         literal '%c'\n"
                             : "inflate:         literal 0x%02x\n",
                 this.val));
        PUP(out) = (unsigned char)(this.val);
      } else if (op & 16) {/* length base */
        len = (unsigned)(this.val);
        op &= 15; /* number of extra bits */
        if (op) {
          if (bits < op) {
            hold += (unsigned long)(PUP(in)) << bits;
            bits += 8;
          }
          len += (unsigned)hold & ((1U << op) - 1);
          hold >>= op;
          bits -= op;
        }
        Tracevv((stderr, "inflate:         length %u\n", len));
        if (bits < 15) {
          hold += (unsigned long)(PUP(in)) << bits;
          bits += 8;
          hold += (unsigned long)(PUP(in)) << bits;
          bits += 8;
        }
        this = dcode[hold & dmask];
      dodist:
        op = (unsigned)(this.bits);
        hold >>= op;
        bits -= op;
        op = (unsigned)(this.op);
        if (op & 16) {/* distance base */
          dist = (unsigned)(this.val);
          op &= 15; /* number of extra bits */
          if (bits < op) {
            hold += (unsigned long)(PUP(in)) << bits;
            bits += 8;
            if (bits < op) {
              hold += (unsigned long)(PUP(in)) << bits;
              bits += 8;
            }
          }
          dist += (unsigned)hold & ((1U << op) - 1);
  #ifdef INFLATE_STRICT
          if (dist > dmax) {
            strm->msg = (char *)"invalid distance too far back";
            state->mode = BAD;
            break;
          }
  #endif
          hold >>= op;
          bits -= op;
          Tracevv((stderr, "inflate:         distance %u\n", dist));
          op = (unsigned)(out - beg); /* max distance in output */
          if (dist > op) {            /* see if copy from window */
            op = dist - op;           /* distance back in window */
            if (op > whave) {
              strm->msg = (char *)"invalid distance too far back";
              state->mode = BAD;
              break;
            }
            from = window - OFF;
            if (write == 0) {/* very common case */
              from += wsize - op;
              if (op < len) {/* some from window */
                len -= op;
                do {
                  PUP(out) = PUP(from);
                } while (--op);
                from = out - dist; /* rest from output */
              }
            } else if (write < op) {/* wrap around window */
              from += wsize + write - op;
              op -= write;
              if (op < len) {/* some from end of window */
                len -= op;
                do {
                  PUP(out) = PUP(from);
                } while (--op);
                from = window - OFF;
                if (write < len) {/* some from start of window */
                  op = write;
                  len -= op;
                  do {
                    PUP(out) = PUP(from);
                  } while (--op);
                  from = out - dist; /* rest from output */
                }
              }
            } else {/* contiguous in window */
              from += write - op;
              if (op < len) {/* some from window */
                len -= op;
                do {
                  PUP(out) = PUP(from);
                } while (--op);
                from = out - dist; /* rest from output */
              }
            }
            while (len > 2) {
              PUP(out) = PUP(from);
              PUP(out) = PUP(from);
              PUP(out) = PUP(from);
              len -= 3;
            }
            if (len) {
              PUP(out) = PUP(from);
              if (len > 1) PUP(out) = PUP(from);
            }
          } else {
            from = out - dist; /* copy direct from output */
            do {               /* minimum length is three */
              PUP(out) = PUP(from);
              PUP(out) = PUP(from);
              PUP(out) = PUP(from);
              len -= 3;
            } while (len > 2);
            if (len) {
              PUP(out) = PUP(from);
              if (len > 1) PUP(out) = PUP(from);
            }
          }
        } else if ((op & 64) == 0) {/* 2nd level distance code */
          this = dcode[this.val + (hold & ((1U << op) - 1))];
          goto dodist;
        } else {
          strm->msg = (char *)"invalid distance code";
          state->mode = BAD;
          break;
        }
      } else if ((op & 64) == 0) {/* 2nd level length code */
        this = lcode[this.val + (hold & ((1U << op) - 1))];
        goto dolen;
      } else if (op & 32) {/* end-of-block */
        Tracevv((stderr, "inflate:         end of block\n"));
        state->mode = TYPE;
        break;
      } else {
        strm->msg = (char *)"invalid literal/length code";
        state->mode = BAD;
        break;
      }
    } while (in < last && out < end);
  
    /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
    len = bits >> 3;
    in -= len;
    bits -= len << 3;
    hold &= (1U << bits) - 1;
  
    /* update state and return */
    strm->next_in = in + OFF;
    strm->next_out = out + OFF;
    strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
    strm->avail_out =
        (unsigned)(out < end ? 257 + (end - out) : 257 - (out - end));
    state->hold = hold;
    state->bits = bits;
    return;
  }
  
  /*
     inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
     - Using bit fields for code structure
     - Different op definition to avoid & for extra bits (do & for table bits)
     - Three separate decoding do-loops for direct, window, and write == 0
     - Special case for distance > 1 copies to do overlapped load and store copy
     - Explicit branch predictions (based on measured branch probabilities)
     - Deferring match copy and interspersed it with decoding subsequent codes
     - Swapping literal/length else
     - Swapping window/direct else
     - Larger unrolled copy loops (three is about right)
     - Moving len -= 3 statement into middle of loop
   */
  
  #endif /* !ASMINF */
  