SecurityServer/MacYarrow/zlib/inffast.c

   1 /*
   2  * Copyright (c) 2000-2001 Apple Computer, Inc. All Rights Reserved.
   3  *
   4  * The contents of this file constitute Original Code as defined in and are
   5  * subject to the Apple Public Source License Version 1.2 (the 'License').
   6  * You may not use this file except in compliance with the License. Please obtain
   7  * a copy of the License at http://www.apple.com/publicsource and read it before
   8  * using this file.
   9  *
  10  * This Original Code and all software distributed under the License are
  11  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESS
  12  * OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, INCLUDING WITHOUT
  13  * LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
  14  * PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. Please see the License for the
  15  * specific language governing rights and limitations under the License.
  16  */
  17
  18
  19 /* inffast.c -- process literals and length/distance pairs fast
  20  * Copyright (C) 1995-1998 Mark Adler
  21  * For conditions of distribution and use, see copyright notice in zlib.h
  22  */
  23
  24 #include "zutil.h"
  25 #include "inftrees.h"
  26 #include "infblock.h"
  27 #include "infcodes.h"
  28 #include "infutil.h"
  29 #include "inffast.h"
  30
  31 struct inflate_codes_state {int dummy;}; /* for buggy compilers */
  32
  33 /* simplify the use of the inflate_huft type with some defines */
  34 #define exop word.what.Exop
  35 #define bits word.what.Bits
  36
  37 /* macros for bit input with no checking and for returning unused bytes */
  38 #define GRABBITS(j) {while(k<(j)){b|=((uLong)NEXTBYTE)<<k;k+=8;}}
  39 #define UNGRAB {c=z->avail_in-n;c=(k>>3)<c?k>>3:c;n+=c;p-=c;k-=c<<3;}
  40
  41 /* Called with number of bytes left to write in window at least 258
  42    (the maximum string length) and number of input bytes available
  43    at least ten.  The ten bytes are six bytes for the longest length/
  44    distance pair plus four bytes for overloading the bit buffer. */
  45
  46 int inflate_fast(bl, bd, tl, td, s, z)
  47 uInt bl, bd;
  48 inflate_huft *tl;
  49 inflate_huft *td; /* need separate declaration for Borland C++ */
  50 inflate_blocks_statef *s;
  51 z_streamp z;
  52 {
  53   inflate_huft *t;      /* temporary pointer */
  54   uInt e;               /* extra bits or operation */
  55   uLong b;              /* bit buffer */
  56   uInt k;               /* bits in bit buffer */
  57   Bytef *p;             /* input data pointer */
  58   uInt n;               /* bytes available there */
  59   Bytef *q;             /* output window write pointer */
  60   uInt m;               /* bytes to end of window or read pointer */
  61   uInt ml;              /* mask for literal/length tree */
  62   uInt md;              /* mask for distance tree */
  63   uInt c;               /* bytes to copy */
  64   uInt d;               /* distance back to copy from */
  65   Bytef *r;             /* copy source pointer */
  66
  67   /* load input, output, bit values */
  68   LOAD
  69
  70   /* initialize masks */
  71   ml = inflate_mask[bl];
  72   md = inflate_mask[bd];
  73
  74   /* do until not enough input or output space for fast loop */
  75   do {                          /* assume called with m >= 258 && n >= 10 */
  76     /* get literal/length code */
  77     GRABBITS(20)                /* max bits for literal/length code */
  78     if ((e = (t = tl + ((uInt)b & ml))->exop) == 0)
  79     {
  80       DUMPBITS(t->bits)
  81       Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
  82                 "inflate:         * literal '%c'\n" :
  83                 "inflate:         * literal 0x%02x\n", t->base));
  84       *q++ = (Byte)t->base;
  85       m--;
  86       continue;
  87     }
  88     do {
  89       DUMPBITS(t->bits)
  90       if (e & 16)
  91       {
  92         /* get extra bits for length */
  93         e &= 15;
  94         c = t->base + ((uInt)b & inflate_mask[e]);
  95         DUMPBITS(e)
  96         Tracevv((stderr, "inflate:         * length %u\n", c));
  97
  98         /* decode distance base of block to copy */
  99         GRABBITS(15);           /* max bits for distance code */
 100         e = (t = td + ((uInt)b & md))->exop;
 101         do {
 102           DUMPBITS(t->bits)
 103           if (e & 16)
 104           {
 105             /* get extra bits to add to distance base */
 106             e &= 15;
 107             GRABBITS(e)         /* get extra bits (up to 13) */
 108             d = t->base + ((uInt)b & inflate_mask[e]);
 109             DUMPBITS(e)
 110             Tracevv((stderr, "inflate:         * distance %u\n", d));
 111
 112             /* do the copy */
 113             m -= c;
 114             if ((uInt)(q - s->window) >= d)     /* offset before dest */
 115             {                                   /*  just copy */
 116               r = q - d;
 117               *q++ = *r++;  c--;        /* minimum count is three, */
 118               *q++ = *r++;  c--;        /*  so unroll loop a little */
 119             }
 120             else                        /* else offset after destination */
 121             {
 122               e = d - (uInt)(q - s->window); /* bytes from offset to end */
 123               r = s->end - e;           /* pointer to offset */
 124               if (c > e)                /* if source crosses, */
 125               {
 126                 c -= e;                 /* copy to end of window */
 127                 do {
 128                   *q++ = *r++;
 129                 } while (--e);
 130                 r = s->window;          /* copy rest from start of window */
 131               }
 132             }
 133             do {                        /* copy all or what's left */
 134               *q++ = *r++;
 135             } while (--c);
 136             break;
 137           }
 138           else if ((e & 64) == 0)
 139           {
 140             t += t->base;
 141             e = (t += ((uInt)b & inflate_mask[e]))->exop;
 142           }
 143           else
 144           {
 145             z->msg = (char*)"invalid distance code";
 146             UNGRAB
 147             UPDATE
 148             return Z_DATA_ERROR;
 149           }
 150         } while (1);
 151         break;
 152       }
 153       if ((e & 64) == 0)
 154       {
 155         t += t->base;
 156         if ((e = (t += ((uInt)b & inflate_mask[e]))->exop) == 0)
 157         {
 158           DUMPBITS(t->bits)
 159           Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
 160                     "inflate:         * literal '%c'\n" :
 161                     "inflate:         * literal 0x%02x\n", t->base));
 162           *q++ = (Byte)t->base;
 163           m--;
 164           break;
 165         }
 166       }
 167       else if (e & 32)
 168       {
 169         Tracevv((stderr, "inflate:         * end of block\n"));
 170         UNGRAB
 171         UPDATE
 172         return Z_STREAM_END;
 173       }
 174       else
 175       {
 176         z->msg = (char*)"invalid literal/length code";
 177         UNGRAB
 178         UPDATE
 179         return Z_DATA_ERROR;
 180       }
 181     } while (1);
 182   } while (m >= 258 && n >= 10);
 183
 184   /* not enough input or output--restore pointers and return */
 185   UNGRAB
 186   UPDATE
 187   return Z_OK;
 188 }