SecurityServer/MacYarrow/zlib/infcodes.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 /* infcodes.c -- process literals and length/distance pairs
  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 /* simplify the use of the inflate_huft type with some defines */
  32 #define exop word.what.Exop
  33 #define bits word.what.Bits
  34
  35 typedef enum {        /* waiting for "i:"=input, "o:"=output, "x:"=nothing */
  36       START,    /* x: set up for LEN */
  37       LEN,      /* i: get length/literal/eob next */
  38       LENEXT,   /* i: getting length extra (have base) */
  39       DIST,     /* i: get distance next */
  40       DISTEXT,  /* i: getting distance extra */
  41       COPY,     /* o: copying bytes in window, waiting for space */
  42       LIT,      /* o: got literal, waiting for output space */
  43       WASH,     /* o: got eob, possibly still output waiting */
  44       END,      /* x: got eob and all data flushed */
  45       BADCODE}  /* x: got error */
  46 inflate_codes_mode;
  47
  48 /* inflate codes private state */
  49 struct inflate_codes_state {
  50
  51   /* mode */
  52   inflate_codes_mode mode;      /* current inflate_codes mode */
  53
  54   /* mode dependent information */
  55   uInt len;
  56   union {
  57     struct {
  58       inflate_huft *tree;       /* pointer into tree */
  59       uInt need;                /* bits needed */
  60     } code;             /* if LEN or DIST, where in tree */
  61     uInt lit;           /* if LIT, literal */
  62     struct {
  63       uInt get;                 /* bits to get for extra */
  64       uInt dist;                /* distance back to copy from */
  65     } copy;             /* if EXT or COPY, where and how much */
  66   } sub;                /* submode */
  67
  68   /* mode independent information */
  69   Byte lbits;           /* ltree bits decoded per branch */
  70   Byte dbits;           /* dtree bits decoder per branch */
  71   inflate_huft *ltree;          /* literal/length/eob tree */
  72   inflate_huft *dtree;          /* distance tree */
  73
  74 };
  75
  76
  77 inflate_codes_statef *inflate_codes_new(bl, bd, tl, td, z)
  78 uInt bl, bd;
  79 inflate_huft *tl;
  80 inflate_huft *td; /* need separate declaration for Borland C++ */
  81 z_streamp z;
  82 {
  83   inflate_codes_statef *c;
  84
  85   if ((c = (inflate_codes_statef *)
  86        ZALLOC(z,1,sizeof(struct inflate_codes_state))) != Z_NULL)
  87   {
  88     c->mode = START;
  89     c->lbits = (Byte)bl;
  90     c->dbits = (Byte)bd;
  91     c->ltree = tl;
  92     c->dtree = td;
  93     Tracev((stderr, "inflate:       codes new\n"));
  94   }
  95   return c;
  96 }
  97
  98
  99 int inflate_codes(s, z, r)
 100 inflate_blocks_statef *s;
 101 z_streamp z;
 102 int r;
 103 {
 104   uInt j;               /* temporary storage */
 105   inflate_huft *t;      /* temporary pointer */
 106   uInt e;               /* extra bits or operation */
 107   uLong b;              /* bit buffer */
 108   uInt k;               /* bits in bit buffer */
 109   Bytef *p;             /* input data pointer */
 110   uInt n;               /* bytes available there */
 111   Bytef *q;             /* output window write pointer */
 112   uInt m;               /* bytes to end of window or read pointer */
 113   Bytef *f;             /* pointer to copy strings from */
 114   inflate_codes_statef *c = s->sub.decode.codes;  /* codes state */
 115
 116   /* copy input/output information to locals (UPDATE macro restores) */
 117   LOAD
 118
 119   /* process input and output based on current state */
 120   while (1) switch (c->mode)
 121   {             /* waiting for "i:"=input, "o:"=output, "x:"=nothing */
 122     case START:         /* x: set up for LEN */
 123 #ifndef SLOW
 124       if (m >= 258 && n >= 10)
 125       {
 126         UPDATE
 127         r = inflate_fast(c->lbits, c->dbits, c->ltree, c->dtree, s, z);
 128         LOAD
 129         if (r != Z_OK)
 130         {
 131           c->mode = r == Z_STREAM_END ? WASH : BADCODE;
 132           break;
 133         }
 134       }
 135 #endif /* !SLOW */
 136       c->sub.code.need = c->lbits;
 137       c->sub.code.tree = c->ltree;
 138       c->mode = LEN;
 139     case LEN:           /* i: get length/literal/eob next */
 140       j = c->sub.code.need;
 141       NEEDBITS(j)
 142       t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
 143       DUMPBITS(t->bits)
 144       e = (uInt)(t->exop);
 145       if (e == 0)               /* literal */
 146       {
 147         c->sub.lit = t->base;
 148         Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
 149                  "inflate:         literal '%c'\n" :
 150                  "inflate:         literal 0x%02x\n", t->base));
 151         c->mode = LIT;
 152         break;
 153       }
 154       if (e & 16)               /* length */
 155       {
 156         c->sub.copy.get = e & 15;
 157         c->len = t->base;
 158         c->mode = LENEXT;
 159         break;
 160       }
 161       if ((e & 64) == 0)        /* next table */
 162       {
 163         c->sub.code.need = e;
 164         c->sub.code.tree = t + t->base;
 165         break;
 166       }
 167       if (e & 32)               /* end of block */
 168       {
 169         Tracevv((stderr, "inflate:         end of block\n"));
 170         c->mode = WASH;
 171         break;
 172       }
 173       c->mode = BADCODE;        /* invalid code */
 174       z->msg = (char*)"invalid literal/length code";
 175       r = Z_DATA_ERROR;
 176       LEAVE
 177     case LENEXT:        /* i: getting length extra (have base) */
 178       j = c->sub.copy.get;
 179       NEEDBITS(j)
 180       c->len += (uInt)b & inflate_mask[j];
 181       DUMPBITS(j)
 182       c->sub.code.need = c->dbits;
 183       c->sub.code.tree = c->dtree;
 184       Tracevv((stderr, "inflate:         length %u\n", c->len));
 185       c->mode = DIST;
 186     case DIST:          /* i: get distance next */
 187       j = c->sub.code.need;
 188       NEEDBITS(j)
 189       t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
 190       DUMPBITS(t->bits)
 191       e = (uInt)(t->exop);
 192       if (e & 16)               /* distance */
 193       {
 194         c->sub.copy.get = e & 15;
 195         c->sub.copy.dist = t->base;
 196         c->mode = DISTEXT;
 197         break;
 198       }
 199       if ((e & 64) == 0)        /* next table */
 200       {
 201         c->sub.code.need = e;
 202         c->sub.code.tree = t + t->base;
 203         break;
 204       }
 205       c->mode = BADCODE;        /* invalid code */
 206       z->msg = (char*)"invalid distance code";
 207       r = Z_DATA_ERROR;
 208       LEAVE
 209     case DISTEXT:       /* i: getting distance extra */
 210       j = c->sub.copy.get;
 211       NEEDBITS(j)
 212       c->sub.copy.dist += (uInt)b & inflate_mask[j];
 213       DUMPBITS(j)
 214       Tracevv((stderr, "inflate:         distance %u\n", c->sub.copy.dist));
 215       c->mode = COPY;
 216     case COPY:          /* o: copying bytes in window, waiting for space */
 217 #ifndef __TURBOC__ /* Turbo C bug for following expression */
 218       f = (uInt)(q - s->window) < c->sub.copy.dist ?
 219           s->end - (c->sub.copy.dist - (q - s->window)) :
 220           q - c->sub.copy.dist;
 221 #else
 222       f = q - c->sub.copy.dist;
 223       if ((uInt)(q - s->window) < c->sub.copy.dist)
 224         f = s->end - (c->sub.copy.dist - (uInt)(q - s->window));
 225 #endif
 226       while (c->len)
 227       {
 228         NEEDOUT
 229         OUTBYTE(*f++)
 230         if (f == s->end)
 231           f = s->window;
 232         c->len--;
 233       }
 234       c->mode = START;
 235       break;
 236     case LIT:           /* o: got literal, waiting for output space */
 237       NEEDOUT
 238       OUTBYTE(c->sub.lit)
 239       c->mode = START;
 240       break;
 241     case WASH:          /* o: got eob, possibly more output */
 242       if (k > 7)        /* return unused byte, if any */
 243       {
 244         Assert(k < 16, "inflate_codes grabbed too many bytes")
 245         k -= 8;
 246         n++;
 247         p--;            /* can always return one */
 248       }
 249       FLUSH
 250       if (s->read != s->write)
 251         LEAVE
 252       c->mode = END;
 253     case END:
 254       r = Z_STREAM_END;
 255       LEAVE
 256     case BADCODE:       /* x: got error */
 257       r = Z_DATA_ERROR;
 258       LEAVE
 259     default:
 260       r = Z_STREAM_ERROR;
 261       LEAVE
 262   }
 263 #ifdef NEED_DUMMY_RETURN
 264   return Z_STREAM_ERROR;  /* Some dumb compilers complain without this */
 265 #endif
 266 }
 267
 268
 269 void inflate_codes_free(c, z)
 270 inflate_codes_statef *c;
 271 z_streamp z;
 272 {
 273   ZFREE(z, c);
 274   Tracev((stderr, "inflate:       codes free\n"));
 275 }