/* inffast.c -- fast decoding
   * Copyright (C) 1995-2004 Mark Adler
   * For conditions of distribution and use, see copyright notice in zlib.h

   */
  
  #include <linux/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)
   */

  union uu {
  	unsigned short us;
  	unsigned char b[2];
  };
  
  /* Endian independed version */
  static inline unsigned short
  get_unaligned16(const unsigned short *p)
  {
  	union uu  mm;
  	unsigned char *b = (unsigned char *)p;
  
  	mm.b[0] = b[0];
  	mm.b[1] = b[1];
  	return mm.us;
  }

  #ifdef POSTINC
  #  define OFF 0
  #  define PUP(a) *(a)++

  #  define UP_UNALIGNED(a) get_unaligned16((a)++)

  #else
  #  define OFF 1
  #  define PUP(a) *++(a)

  #  define UP_UNALIGNED(a) get_unaligned16(++(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.

  
      - @start:	inflate()'s starting value for strm->avail_out

   */

  void inflate_fast(z_streamp strm, unsigned start)

  {

      struct inflate_state *state;

      const unsigned char *in;    /* local strm->next_in */
      const unsigned char *last;  /* while in < last, enough input available */
      unsigned char *out;         /* local strm->next_out */
      unsigned char *beg;         /* inflate()'s initial strm->next_out */
      unsigned char *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 *window;      /* allocated sliding window, if wsize != 0 */

      unsigned long hold;         /* local strm->hold */
      unsigned bits;              /* local strm->bits */

      code const *lcode;          /* local strm->lencode */
      code const *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 *from;        /* where to copy match from */

  
      /* copy state to local variables */
      state = (struct inflate_state *)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 */
              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;
              }
              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;
                  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 {

  		    unsigned short *sout;
  		    unsigned long loops;

                      from = out - dist;          /* copy direct from output */

  		    /* minimum length is three */
  		    /* Align out addr */
  		    if (!((long)(out - 1 + OFF) & 1)) {
  			PUP(out) = PUP(from);
  			len--;
  		    }
  		    sout = (unsigned short *)(out - OFF);
  		    if (dist > 2) {
  			unsigned short *sfrom;
  
  			sfrom = (unsigned short *)(from - OFF);
  			loops = len >> 1;
  			do

  #ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
  			    PUP(sout) = PUP(sfrom);
  #else

  			    PUP(sout) = UP_UNALIGNED(sfrom);

  #endif

  			while (--loops);
  			out = (unsigned char *)sout + OFF;
  			from = (unsigned char *)sfrom + OFF;
  		    } else { /* dist == 1 or dist == 2 */
  			unsigned short pat16;

  			pat16 = *(sout-1+OFF);

  			if (dist == 1) {
  				union uu mm;
  				/* copy one char pattern to both bytes */
  				mm.us = pat16;
  				mm.b[0] = mm.b[1];
  				pat16 = mm.us;
  			}

  			loops = len >> 1;
  			do
  			    PUP(sout) = pat16;
  			while (--loops);
  			out = (unsigned char *)sout + OFF;
  		    }
  		    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 */
              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 */