sl@0: /* inffast.c -- process literals and length/distance pairs fast
sl@0:  * Copyright (C) 1995-1998 Mark Adler
sl@0:  * For conditions of distribution and use, see copyright notice in zlib.h 
sl@0:  */
sl@0: 
sl@0: #include "zutil.h"
sl@0: #include "inftrees.h"
sl@0: #include "infblock.h"
sl@0: #include "infcodes.h"
sl@0: #include "infutil.h"
sl@0: #include "inffast.h"
sl@0: 
sl@0: struct inflate_codes_state {int dummy;}; /* for buggy compilers */
sl@0: 
sl@0: /* simplify the use of the inflate_huft type with some defines */
sl@0: #define exop word.what.Exop
sl@0: #define bits word.what.Bits
sl@0: 
sl@0: /* macros for bit input with no checking and for returning unused bytes */
sl@0: #define GRABBITS(j) {while(k<(j)){b|=((uLong)NEXTBYTE)<<k;k+=8;}}
sl@0: #define UNGRAB {c=z->avail_in-n;c=(k>>3)<c?k>>3:c;n+=c;p-=c;k-=c<<3;}
sl@0: 
sl@0: /* Called with number of bytes left to write in window at least 258
sl@0:    (the maximum string length) and number of input bytes available
sl@0:    at least ten.  The ten bytes are six bytes for the longest length/
sl@0:    distance pair plus four bytes for overloading the bit buffer. */
sl@0: 
sl@0: int inflate_fast(uInt bl, uInt bd, inflate_huft *tl, inflate_huft *td, inflate_blocks_statef *s, z_streamp z)
sl@0: /* inflate_huft *td        need separate declaration for Borland C++ */
sl@0: {
sl@0:   inflate_huft *t;      /* temporary pointer */
sl@0:   uInt e;               /* extra bits or operation */
sl@0:   uLong b;              /* bit buffer */
sl@0:   uInt k;               /* bits in bit buffer */
sl@0:   Bytef *p;             /* input data pointer */
sl@0:   uInt n;               /* bytes available there */
sl@0:   Bytef *q;             /* output window write pointer */
sl@0:   uInt m;               /* bytes to end of window or read pointer */
sl@0:   uInt ml;              /* mask for literal/length tree */
sl@0:   uInt md;              /* mask for distance tree */
sl@0:   uInt c;               /* bytes to copy */
sl@0:   uInt d;               /* distance back to copy from */
sl@0:   Bytef *r;             /* copy source pointer */
sl@0: 
sl@0:   /* load input, output, bit values */
sl@0:   LOAD
sl@0: 
sl@0:   /* initialize masks */
sl@0:   ml = inflate_mask[bl];
sl@0:   md = inflate_mask[bd];
sl@0: 
sl@0:   /* do until not enough input or output space for fast loop */
sl@0:   do {                          /* assume called with m >= 258 && n >= 10 */
sl@0:     /* get literal/length code */
sl@0:     GRABBITS(20)                /* max bits for literal/length code */
sl@0:     if ((e = (t = tl + ((uInt)b & ml))->exop) == 0)
sl@0:     {
sl@0:       DUMPBITS(t->bits)
sl@0:       Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
sl@0:                 "inflate:         * literal '%c'\n" :
sl@0:                 "inflate:         * literal 0x%02x\n", t->base));
sl@0:       *q++ = (Byte)t->base;
sl@0:       m--;
sl@0:       continue;
sl@0:     }
sl@0:     do {
sl@0:       DUMPBITS(t->bits)
sl@0:       if (e & 16)
sl@0:       {
sl@0:         /* get extra bits for length */
sl@0:         e &= 15;
sl@0:         c = t->base + ((uInt)b & inflate_mask[e]);
sl@0:         DUMPBITS(e)
sl@0:         Tracevv((stderr, "inflate:         * length %u\n", c));
sl@0: 
sl@0:         /* decode distance base of block to copy */
sl@0:         GRABBITS(15);           /* max bits for distance code */
sl@0:         e = (t = td + ((uInt)b & md))->exop;
sl@0:         do {
sl@0:           DUMPBITS(t->bits)
sl@0:           if (e & 16)
sl@0:           {
sl@0:             /* get extra bits to add to distance base */
sl@0:             e &= 15;
sl@0:             GRABBITS(e)         /* get extra bits (up to 13) */
sl@0:             d = t->base + ((uInt)b & inflate_mask[e]);
sl@0:             DUMPBITS(e)
sl@0:             Tracevv((stderr, "inflate:         * distance %u\n", d));
sl@0: 
sl@0:             /* do the copy */
sl@0:             m -= c;
sl@0:             if ((uInt)(q - s->window) >= d)     /* offset before dest */
sl@0:             {                                   /*  just copy */
sl@0:               r = q - d;
sl@0:               *q++ = *r++;  c--;        /* minimum count is three, */
sl@0:               *q++ = *r++;  c--;        /*  so unroll loop a little */
sl@0:             }
sl@0:             else                        /* else offset after destination */
sl@0:             {
sl@0:               e = d - (uInt)(q - s->window); /* bytes from offset to end */
sl@0:               r = s->end - e;           /* pointer to offset */
sl@0:               if (c > e)                /* if source crosses, */
sl@0:               {
sl@0:                 c -= e;                 /* copy to end of window */
sl@0:                 do {
sl@0:                   *q++ = *r++;
sl@0:                 } while (--e);
sl@0:                 r = s->window;          /* copy rest from start of window */
sl@0:               }
sl@0:             }
sl@0:             do {                        /* copy all or what's left */
sl@0:               *q++ = *r++;
sl@0:             } while (--c);
sl@0:             break;
sl@0:           }
sl@0:           else if ((e & 64) == 0)
sl@0:           {
sl@0:             t += t->base;
sl@0:             e = (t += ((uInt)b & inflate_mask[e]))->exop;
sl@0:           }
sl@0:           else
sl@0:           {
sl@0:             z->msg = (char*)"invalid distance code";
sl@0:             UNGRAB
sl@0:             UPDATE
sl@0:             return Z_DATA_ERROR;
sl@0:           }
sl@0:         } while (1);
sl@0:         break;
sl@0:       }
sl@0:       if ((e & 64) == 0)
sl@0:       {
sl@0:         t += t->base;
sl@0:         if ((e = (t += ((uInt)b & inflate_mask[e]))->exop) == 0)
sl@0:         {
sl@0:           DUMPBITS(t->bits)
sl@0:           Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
sl@0:                     "inflate:         * literal '%c'\n" :
sl@0:                     "inflate:         * literal 0x%02x\n", t->base));
sl@0:           *q++ = (Byte)t->base;
sl@0:           m--;
sl@0:           break;
sl@0:         }
sl@0:       }
sl@0:       else if (e & 32)
sl@0:       {
sl@0:         Tracevv((stderr, "inflate:         * end of block\n"));
sl@0:         UNGRAB
sl@0:         UPDATE
sl@0:         return Z_STREAM_END;
sl@0:       }
sl@0:       else
sl@0:       {
sl@0:         z->msg = (char*)"invalid literal/length code";
sl@0:         UNGRAB
sl@0:         UPDATE
sl@0:         return Z_DATA_ERROR;
sl@0:       }
sl@0:     } while (1);
sl@0:   } while (m >= 258 && n >= 10);
sl@0: 
sl@0:   /* not enough input or output--restore pointers and return */
sl@0:   UNGRAB
sl@0:   UPDATE
sl@0:   return Z_OK;
sl@0: }