/* 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 */