lib/inflate.c

   1 #define DEBG(x)
   2 #define DEBG1(x)
   3 /* inflate.c -- Not copyrighted 1992 by Mark Adler
   4    version c10p1, 10 January 1993 */
   5
   6 /*
   7  * Adapted for booting Linux by Hannu Savolainen 1993
   8  * based on gzip-1.0.3
   9  *
  10  * Nicolas Pitre <nico@cam.org>, 1999/04/14 :
  11  *   Little mods for all variable to reside either into rodata or bss segments
  12  *   by marking constant variables with 'const' and initializing all the others
  13  *   at run-time only.  This allows for the kernel uncompressor to run
  14  *   directly from Flash or ROM memory on embedded systems.
  15  */
  16
  17 /*
  18    Inflate deflated (PKZIP's method 8 compressed) data.  The compression
  19    method searches for as much of the current string of bytes (up to a
  20    length of 258) in the previous 32 K bytes.  If it doesn't find any
  21    matches (of at least length 3), it codes the next byte.  Otherwise, it
  22    codes the length of the matched string and its distance backwards from
  23    the current position.  There is a single Huffman code that codes both
  24    single bytes (called "literals") and match lengths.  A second Huffman
  25    code codes the distance information, which follows a length code.  Each
  26    length or distance code actually represents a base value and a number
  27    of "extra" (sometimes zero) bits to get to add to the base value.  At
  28    the end of each deflated block is a special end-of-block (EOB) literal/
  29    length code.  The decoding process is basically: get a literal/length
  30    code; if EOB then done; if a literal, emit the decoded byte; if a
  31    length then get the distance and emit the referred-to bytes from the
  32    sliding window of previously emitted data.
  33
  34    There are (currently) three kinds of inflate blocks: stored, fixed, and
  35    dynamic.  The compressor deals with some chunk of data at a time, and
  36    decides which method to use on a chunk-by-chunk basis.  A chunk might
  37    typically be 32 K or 64 K.  If the chunk is incompressible, then the
  38    "stored" method is used.  In this case, the bytes are simply stored as
  39    is, eight bits per byte, with none of the above coding.  The bytes are
  40    preceded by a count, since there is no longer an EOB code.
  41
  42    If the data is compressible, then either the fixed or dynamic methods
  43    are used.  In the dynamic method, the compressed data is preceded by
  44    an encoding of the literal/length and distance Huffman codes that are
  45    to be used to decode this block.  The representation is itself Huffman
  46    coded, and so is preceded by a description of that code.  These code
  47    descriptions take up a little space, and so for small blocks, there is
  48    a predefined set of codes, called the fixed codes.  The fixed method is
  49    used if the block codes up smaller that way (usually for quite small
  50    chunks), otherwise the dynamic method is used.  In the latter case, the
  51    codes are customized to the probabilities in the current block, and so
  52    can code it much better than the pre-determined fixed codes.
  53
  54    The Huffman codes themselves are decoded using a multi-level table
  55    lookup, in order to maximize the speed of decoding plus the speed of
  56    building the decoding tables.  See the comments below that precede the
  57    lbits and dbits tuning parameters.
  58  */
  59
  60
  61 /*
  62    Notes beyond the 1.93a appnote.txt:
  63
  64    1. Distance pointers never point before the beginning of the output
  65       stream.
  66    2. Distance pointers can point back across blocks, up to 32k away.
  67    3. There is an implied maximum of 7 bits for the bit length table and
  68       15 bits for the actual data.
  69    4. If only one code exists, then it is encoded using one bit.  (Zero
  70       would be more efficient, but perhaps a little confusing.)  If two
  71       codes exist, they are coded using one bit each (0 and 1).
  72    5. There is no way of sending zero distance codes--a dummy must be
  73       sent if there are none.  (History: a pre 2.0 version of PKZIP would
  74       store blocks with no distance codes, but this was discovered to be
  75       too harsh a criterion.)  Valid only for 1.93a.  2.04c does allow
  76       zero distance codes, which is sent as one code of zero bits in
  77       length.
  78    6. There are up to 286 literal/length codes.  Code 256 represents the
  79       end-of-block.  Note however that the static length tree defines
  80       288 codes just to fill out the Huffman codes.  Codes 286 and 287
  81       cannot be used though, since there is no length base or extra bits
  82       defined for them.  Similarly, there are up to 30 distance codes.
  83       However, static trees define 32 codes (all 5 bits) to fill out the
  84       Huffman codes, but the last two had better not show up in the data.
  85    7. Unzip can check dynamic Huffman blocks for complete code sets.
  86       The exception is that a single code would not be complete (see #4).
  87    8. The five bits following the block type is really the number of
  88       literal codes sent minus 257.
  89    9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
  90       (1+6+6).  Therefore, to output three times the length, you output
  91       three codes (1+1+1), whereas to output four times the same length,
  92       you only need two codes (1+3).  Hmm.
  93   10. In the tree reconstruction algorithm, Code = Code + Increment
  94       only if BitLength(i) is not zero.  (Pretty obvious.)
  95   11. Correction: 4 Bits: # of Bit Length codes - 4     (4 - 19)
  96   12. Note: length code 284 can represent 227-258, but length code 285
  97       really is 258.  The last length deserves its own, short code
  98       since it gets used a lot in very redundant files.  The length
  99       258 is special since 258 - 3 (the min match length) is 255.
 100   13. The literal/length and distance code bit lengths are read as a
 101       single stream of lengths.  It is possible (and advantageous) for
 102       a repeat code (16, 17, or 18) to go across the boundary between
 103       the two sets of lengths.
 104  */
 105
 106 #ifdef RCSID
 107 static char rcsid[] = "#Id: inflate.c,v 0.14 1993/06/10 13:27:04 jloup Exp #";
 108 #endif
 109
 110 #ifndef STATIC
 111
 112 #if defined(STDC_HEADERS) || defined(HAVE_STDLIB_H)
 113 #  include <sys/types.h>
 114 #  include <stdlib.h>
 115 #endif
 116
 117 #include "gzip.h"
 118 #define STATIC
 119 #endif /* !STATIC */
 120
 121 #define slide window
 122
 123 /* Huffman code lookup table entry--this entry is four bytes for machines
 124    that have 16-bit pointers (e.g. PC's in the small or medium model).
 125    Valid extra bits are 0..13.  e == 15 is EOB (end of block), e == 16
 126    means that v is a literal, 16 < e < 32 means that v is a pointer to
 127    the next table, which codes e - 16 bits, and lastly e == 99 indicates
 128    an unused code.  If a code with e == 99 is looked up, this implies an
 129    error in the data. */
 130 struct huft {
 131   uch e;                /* number of extra bits or operation */
 132   uch b;                /* number of bits in this code or subcode */
 133   union {
 134     ush n;              /* literal, length base, or distance base */
 135     struct huft *t;     /* pointer to next level of table */
 136   } v;
 137 };
 138
 139
 140 /* Function prototypes */
 141 STATIC int huft_build OF((unsigned *, unsigned, unsigned,
 142                 const ush *, const ush *, struct huft **, int *));
 143 STATIC int huft_free OF((struct huft *));
 144 STATIC int inflate_codes OF((struct huft *, struct huft *, int, int));
 145 STATIC int inflate_stored OF((void));
 146 STATIC int inflate_fixed OF((void));
 147 STATIC int inflate_dynamic OF((void));
 148 STATIC int inflate_block OF((int *));
 149 STATIC int inflate OF((void));
 150
 151
 152 /* The inflate algorithm uses a sliding 32 K byte window on the uncompressed
 153    stream to find repeated byte strings.  This is implemented here as a
 154    circular buffer.  The index is updated simply by incrementing and then
 155    ANDing with 0x7fff (32K-1). */
 156 /* It is left to other modules to supply the 32 K area.  It is assumed
 157    to be usable as if it were declared "uch slide[32768];" or as just
 158    "uch *slide;" and then malloc'ed in the latter case.  The definition
 159    must be in unzip.h, included above. */
 160 /* unsigned wp;             current position in slide */
 161 #define wp outcnt
 162 #define flush_output(w) (wp=(w),flush_window())
 163
 164 /* Tables for deflate from PKZIP's appnote.txt. */
 165 static const unsigned border[] = {    /* Order of the bit length code lengths */
 166         16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
 167 static const ush cplens[] = {         /* Copy lengths for literal codes 257..285 */
 168         3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
 169         35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
 170         /* note: see note #13 above about the 258 in this list. */
 171 static const ush cplext[] = {         /* Extra bits for literal codes 257..285 */
 172         0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
 173         3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 99, 99}; /* 99==invalid */
 174 static const ush cpdist[] = {         /* Copy offsets for distance codes 0..29 */
 175         1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
 176         257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
 177         8193, 12289, 16385, 24577};
 178 static const ush cpdext[] = {         /* Extra bits for distance codes */
 179         0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
 180         7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
 181         12, 12, 13, 13};
 182
 183
 184
 185 /* Macros for inflate() bit peeking and grabbing.
 186    The usage is:
 187
 188         NEEDBITS(j)
 189         x = b & mask_bits[j];
 190         DUMPBITS(j)
 191
 192    where NEEDBITS makes sure that b has at least j bits in it, and
 193    DUMPBITS removes the bits from b.  The macros use the variable k
 194    for the number of bits in b.  Normally, b and k are register
 195    variables for speed, and are initialized at the beginning of a
 196    routine that uses these macros from a global bit buffer and count.
 197
 198    If we assume that EOB will be the longest code, then we will never
 199    ask for bits with NEEDBITS that are beyond the end of the stream.
 200    So, NEEDBITS should not read any more bytes than are needed to
 201    meet the request.  Then no bytes need to be "returned" to the buffer
 202    at the end of the last block.
 203
 204    However, this assumption is not true for fixed blocks--the EOB code
 205    is 7 bits, but the other literal/length codes can be 8 or 9 bits.
 206    (The EOB code is shorter than other codes because fixed blocks are
 207    generally short.  So, while a block always has an EOB, many other
 208    literal/length codes have a significantly lower probability of
 209    showing up at all.)  However, by making the first table have a
 210    lookup of seven bits, the EOB code will be found in that first
 211    lookup, and so will not require that too many bits be pulled from
 212    the stream.
 213  */
 214
 215 STATIC ulg bb;                         /* bit buffer */
 216 STATIC unsigned bk;                    /* bits in bit buffer */
 217
 218 STATIC const ush mask_bits[] = {
 219     0x0000,
 220     0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
 221     0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
 222 };
 223
 224 #define NEXTBYTE()  (uch)get_byte()
 225 #define NEEDBITS(n) {while(k<(n)){b|=((ulg)NEXTBYTE())<<k;k+=8;}}
 226 #define DUMPBITS(n) {b>>=(n);k-=(n);}
 227
 228
 229 /*
 230    Huffman code decoding is performed using a multi-level table lookup.
 231    The fastest way to decode is to simply build a lookup table whose
 232    size is determined by the longest code.  However, the time it takes
 233    to build this table can also be a factor if the data being decoded
 234    is not very long.  The most common codes are necessarily the
 235    shortest codes, so those codes dominate the decoding time, and hence
 236    the speed.  The idea is you can have a shorter table that decodes the
 237    shorter, more probable codes, and then point to subsidiary tables for
 238    the longer codes.  The time it costs to decode the longer codes is
 239    then traded against the time it takes to make longer tables.
 240
 241    This results of this trade are in the variables lbits and dbits
 242    below.  lbits is the number of bits the first level table for literal/
 243    length codes can decode in one step, and dbits is the same thing for
 244    the distance codes.  Subsequent tables are also less than or equal to
 245    those sizes.  These values may be adjusted either when all of the
 246    codes are shorter than that, in which case the longest code length in
 247    bits is used, or when the shortest code is *longer* than the requested
 248    table size, in which case the length of the shortest code in bits is
 249    used.
 250
 251    There are two different values for the two tables, since they code a
 252    different number of possibilities each.  The literal/length table
 253    codes 286 possible values, or in a flat code, a little over eight
 254    bits.  The distance table codes 30 possible values, or a little less
 255    than five bits, flat.  The optimum values for speed end up being
 256    about one bit more than those, so lbits is 8+1 and dbits is 5+1.
 257    The optimum values may differ though from machine to machine, and
 258    possibly even between compilers.  Your mileage may vary.
 259  */
 260
 261
 262 STATIC const int lbits = 9;          /* bits in base literal/length lookup table */
 263 STATIC const int dbits = 6;          /* bits in base distance lookup table */
 264
 265
 266 /* If BMAX needs to be larger than 16, then h and x[] should be ulg. */
 267 #define BMAX 16         /* maximum bit length of any code (16 for explode) */
 268 #define N_MAX 288       /* maximum number of codes in any set */
 269
 270
 271 STATIC unsigned hufts;         /* track memory usage */
 272
 273
 274 STATIC int huft_build(
 275         unsigned *b,            /* code lengths in bits (all assumed <= BMAX) */
 276         unsigned n,             /* number of codes (assumed <= N_MAX) */
 277         unsigned s,             /* number of simple-valued codes (0..s-1) */
 278         const ush *d,           /* list of base values for non-simple codes */
 279         const ush *e,           /* list of extra bits for non-simple codes */
 280         struct huft **t,        /* result: starting table */
 281         int *m                  /* maximum lookup bits, returns actual */
 282         )
 283 /* Given a list of code lengths and a maximum table size, make a set of
 284    tables to decode that set of codes.  Return zero on success, one if
 285    the given code set is incomplete (the tables are still built in this
 286    case), two if the input is invalid (all zero length codes or an
 287    oversubscribed set of lengths), and three if not enough memory. */
 288 {
 289   unsigned a;                   /* counter for codes of length k */
 290   unsigned c[BMAX+1];           /* bit length count table */
 291   unsigned f;                   /* i repeats in table every f entries */
 292   int g;                        /* maximum code length */
 293   int h;                        /* table level */
 294   register unsigned i;          /* counter, current code */
 295   register unsigned j;          /* counter */
 296   register int k;               /* number of bits in current code */
 297   int l;                        /* bits per table (returned in m) */
 298   register unsigned *p;         /* pointer into c[], b[], or v[] */
 299   register struct huft *q;      /* points to current table */
 300   struct huft r;                /* table entry for structure assignment */
 301   struct huft *u[BMAX];         /* table stack */
 302   unsigned v[N_MAX];            /* values in order of bit length */
 303   register int w;               /* bits before this table == (l * h) */
 304   unsigned x[BMAX+1];           /* bit offsets, then code stack */
 305   unsigned *xp;                 /* pointer into x */
 306   int y;                        /* number of dummy codes added */
 307   unsigned z;                   /* number of entries in current table */
 308
 309 DEBG("huft1 ");
 310
 311   /* Generate counts for each bit length */
 312   memzero(c, sizeof(c));
 313   p = b;  i = n;
 314   do {
 315     Tracecv(*p, (stderr, (n-i >= ' ' && n-i <= '~' ? "%c %d\n" : "0x%x %d\n"),
 316             n-i, *p));
 317     c[*p]++;                    /* assume all entries <= BMAX */
 318     p++;                      /* Can't combine with above line (Solaris bug) */
 319   } while (--i);
 320   if (c[0] == n)                /* null input--all zero length codes */
 321   {
 322     *t = (struct huft *)NULL;
 323     *m = 0;
 324     return 0;
 325   }
 326
 327 DEBG("huft2 ");
 328
 329   /* Find minimum and maximum length, bound *m by those */
 330   l = *m;
 331   for (j = 1; j <= BMAX; j++)
 332     if (c[j])
 333       break;
 334   k = j;                        /* minimum code length */
 335   if ((unsigned)l < j)
 336     l = j;
 337   for (i = BMAX; i; i--)
 338     if (c[i])
 339       break;
 340   g = i;                        /* maximum code length */
 341   if ((unsigned)l > i)
 342     l = i;
 343   *m = l;
 344
 345 DEBG("huft3 ");
 346
 347   /* Adjust last length count to fill out codes, if needed */
 348   for (y = 1 << j; j < i; j++, y <<= 1)
 349     if ((y -= c[j]) < 0)
 350       return 2;                 /* bad input: more codes than bits */
 351   if ((y -= c[i]) < 0)
 352     return 2;
 353   c[i] += y;
 354
 355 DEBG("huft4 ");
 356
 357   /* Generate starting offsets into the value table for each length */
 358   x[1] = j = 0;
 359   p = c + 1;  xp = x + 2;
 360   while (--i) {                 /* note that i == g from above */
 361     *xp++ = (j += *p++);
 362   }
 363
 364 DEBG("huft5 ");
 365
 366   /* Make a table of values in order of bit lengths */
 367   p = b;  i = 0;
 368   do {
 369     if ((j = *p++) != 0)
 370       v[x[j]++] = i;
 371   } while (++i < n);
 372
 373 DEBG("h6 ");
 374
 375   /* Generate the Huffman codes and for each, make the table entries */
 376   x[0] = i = 0;                 /* first Huffman code is zero */
 377   p = v;                        /* grab values in bit order */
 378   h = -1;                       /* no tables yet--level -1 */
 379   w = -l;                       /* bits decoded == (l * h) */
 380   u[0] = (struct huft *)NULL;   /* just to keep compilers happy */
 381   q = (struct huft *)NULL;      /* ditto */
 382   z = 0;                        /* ditto */
 383 DEBG("h6a ");
 384
 385   /* go through the bit lengths (k already is bits in shortest code) */
 386   for (; k <= g; k++)
 387   {
 388 DEBG("h6b ");
 389     a = c[k];
 390     while (a--)
 391     {
 392 DEBG("h6b1 ");
 393       /* here i is the Huffman code of length k bits for value *p */
 394       /* make tables up to required level */
 395       while (k > w + l)
 396       {
 397 DEBG1("1 ");
 398         h++;
 399         w += l;                 /* previous table always l bits */
 400
 401         /* compute minimum size table less than or equal to l bits */
 402         z = (z = g - w) > (unsigned)l ? l : z;  /* upper limit on table size */
 403         if ((f = 1 << (j = k - w)) > a + 1)     /* try a k-w bit table */
 404         {                       /* too few codes for k-w bit table */
 405 DEBG1("2 ");
 406           f -= a + 1;           /* deduct codes from patterns left */
 407           xp = c + k;
 408           while (++j < z)       /* try smaller tables up to z bits */
 409           {
 410             if ((f <<= 1) <= *++xp)
 411               break;            /* enough codes to use up j bits */
 412             f -= *xp;           /* else deduct codes from patterns */
 413           }
 414         }
 415 DEBG1("3 ");
 416         z = 1 << j;             /* table entries for j-bit table */
 417
 418         /* allocate and link in new table */
 419         if ((q = (struct huft *)malloc((z + 1)*sizeof(struct huft))) ==
 420             (struct huft *)NULL)
 421         {
 422           if (h)
 423             huft_free(u[0]);
 424           return 3;             /* not enough memory */
 425         }
 426 DEBG1("4 ");
 427         hufts += z + 1;         /* track memory usage */
 428         *t = q + 1;             /* link to list for huft_free() */
 429         *(t = &(q->v.t)) = (struct huft *)NULL;
 430         u[h] = ++q;             /* table starts after link */
 431
 432 DEBG1("5 ");
 433         /* connect to last table, if there is one */
 434         if (h)
 435         {
 436           x[h] = i;             /* save pattern for backing up */
 437           r.b = (uch)l;         /* bits to dump before this table */
 438           r.e = (uch)(16 + j);  /* bits in this table */
 439           r.v.t = q;            /* pointer to this table */
 440           j = i >> (w - l);     /* (get around Turbo C bug) */
 441           u[h-1][j] = r;        /* connect to last table */
 442         }
 443 DEBG1("6 ");
 444       }
 445 DEBG("h6c ");
 446
 447       /* set up table entry in r */
 448       r.b = (uch)(k - w);
 449       if (p >= v + n)
 450         r.e = 99;               /* out of values--invalid code */
 451       else if (*p < s)
 452       {
 453         r.e = (uch)(*p < 256 ? 16 : 15);    /* 256 is end-of-block code */
 454         r.v.n = (ush)(*p);             /* simple code is just the value */
 455         p++;                           /* one compiler does not like *p++ */
 456       }
 457       else
 458       {
 459         r.e = (uch)e[*p - s];   /* non-simple--look up in lists */
 460         r.v.n = d[*p++ - s];
 461       }
 462 DEBG("h6d ");
 463
 464       /* fill code-like entries with r */
 465       f = 1 << (k - w);
 466       for (j = i >> w; j < z; j += f)
 467         q[j] = r;
 468
 469       /* backwards increment the k-bit code i */
 470       for (j = 1 << (k - 1); i & j; j >>= 1)
 471         i ^= j;
 472       i ^= j;
 473
 474       /* backup over finished tables */
 475       while ((i & ((1 << w) - 1)) != x[h])
 476       {
 477         h--;                    /* don't need to update q */
 478         w -= l;
 479       }
 480 DEBG("h6e ");
 481     }
 482 DEBG("h6f ");
 483   }
 484
 485 DEBG("huft7 ");
 486
 487   /* Return true (1) if we were given an incomplete table */
 488   return y != 0 && g != 1;
 489 }
 490
 491
 492
 493 STATIC int huft_free(
 494         struct huft *t         /* table to free */
 495         )
 496 /* Free the malloc'ed tables built by huft_build(), which makes a linked
 497    list of the tables it made, with the links in a dummy first entry of
 498    each table. */
 499 {
 500   register struct huft *p, *q;
 501
 502
 503   /* Go through linked list, freeing from the malloced (t[-1]) address. */
 504   p = t;
 505   while (p != (struct huft *)NULL)
 506   {
 507     q = (--p)->v.t;
 508     free((char*)p);
 509     p = q;
 510   }
 511   return 0;
 512 }
 513
 514
 515 STATIC int inflate_codes(
 516         struct huft *tl,    /* literal/length decoder tables */
 517         struct huft *td,    /* distance decoder tables */
 518         int bl,             /* number of bits decoded by tl[] */
 519         int bd              /* number of bits decoded by td[] */
 520         )
 521 /* inflate (decompress) the codes in a deflated (compressed) block.
 522    Return an error code or zero if it all goes ok. */
 523 {
 524   register unsigned e;  /* table entry flag/number of extra bits */
 525   unsigned n, d;        /* length and index for copy */
 526   unsigned w;           /* current window position */
 527   struct huft *t;       /* pointer to table entry */
 528   unsigned ml, md;      /* masks for bl and bd bits */
 529   register ulg b;       /* bit buffer */
 530   register unsigned k;  /* number of bits in bit buffer */
 531
 532
 533   /* make local copies of globals */
 534   b = bb;                       /* initialize bit buffer */
 535   k = bk;
 536   w = wp;                       /* initialize window position */
 537
 538   /* inflate the coded data */
 539   ml = mask_bits[bl];           /* precompute masks for speed */
 540   md = mask_bits[bd];
 541   for (;;)                      /* do until end of block */
 542   {
 543     NEEDBITS((unsigned)bl)
 544     if ((e = (t = tl + ((unsigned)b & ml))->e) > 16)
 545       do {
 546         if (e == 99)
 547           return 1;
 548         DUMPBITS(t->b)
 549         e -= 16;
 550         NEEDBITS(e)
 551       } while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16);
 552     DUMPBITS(t->b)
 553     if (e == 16)                /* then it's a literal */
 554     {
 555       slide[w++] = (uch)t->v.n;
 556       Tracevv((stderr, "%c", slide[w-1]));
 557       if (w == WSIZE)
 558       {
 559         flush_output(w);
 560         w = 0;
 561       }
 562     }
 563     else                        /* it's an EOB or a length */
 564     {
 565       /* exit if end of block */
 566       if (e == 15)
 567         break;
 568
 569       /* get length of block to copy */
 570       NEEDBITS(e)
 571       n = t->v.n + ((unsigned)b & mask_bits[e]);
 572       DUMPBITS(e);
 573
 574       /* decode distance of block to copy */
 575       NEEDBITS((unsigned)bd)
 576       if ((e = (t = td + ((unsigned)b & md))->e) > 16)
 577         do {
 578           if (e == 99)
 579             return 1;
 580           DUMPBITS(t->b)
 581           e -= 16;
 582           NEEDBITS(e)
 583         } while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16);
 584       DUMPBITS(t->b)
 585       NEEDBITS(e)
 586       d = w - t->v.n - ((unsigned)b & mask_bits[e]);
 587       DUMPBITS(e)
 588       Tracevv((stderr,"\\[%d,%d]", w-d, n));
 589
 590       /* do the copy */
 591       do {
 592         n -= (e = (e = WSIZE - ((d &= WSIZE-1) > w ? d : w)) > n ? n : e);
 593 #if !defined(NOMEMCPY) && !defined(DEBUG)
 594         if (w - d >= e)         /* (this test assumes unsigned comparison) */
 595         {
 596           memcpy(slide + w, slide + d, e);
 597           w += e;
 598           d += e;
 599         }
 600         else                      /* do it slow to avoid memcpy() overlap */
 601 #endif /* !NOMEMCPY */
 602           do {
 603             slide[w++] = slide[d++];
 604             Tracevv((stderr, "%c", slide[w-1]));
 605           } while (--e);
 606         if (w == WSIZE)
 607         {
 608           flush_output(w);
 609           w = 0;
 610         }
 611       } while (n);
 612     }
 613   }
 614
 615
 616   /* restore the globals from the locals */
 617   wp = w;                       /* restore global window pointer */
 618   bb = b;                       /* restore global bit buffer */
 619   bk = k;
 620
 621   /* done */
 622   return 0;
 623 }
 624
 625
 626
 627 STATIC int inflate_stored(void)
 628 /* "decompress" an inflated type 0 (stored) block. */
 629 {
 630   unsigned n;           /* number of bytes in block */
 631   unsigned w;           /* current window position */
 632   register ulg b;       /* bit buffer */
 633   register unsigned k;  /* number of bits in bit buffer */
 634
 635 DEBG("<stor");
 636
 637   /* make local copies of globals */
 638   b = bb;                       /* initialize bit buffer */
 639   k = bk;
 640   w = wp;                       /* initialize window position */
 641
 642
 643   /* go to byte boundary */
 644   n = k & 7;
 645   DUMPBITS(n);
 646
 647
 648   /* get the length and its complement */
 649   NEEDBITS(16)
 650   n = ((unsigned)b & 0xffff);
 651   DUMPBITS(16)
 652   NEEDBITS(16)
 653   if (n != (unsigned)((~b) & 0xffff))
 654     return 1;                   /* error in compressed data */
 655   DUMPBITS(16)
 656
 657
 658   /* read and output the compressed data */
 659   while (n--)
 660   {
 661     NEEDBITS(8)
 662     slide[w++] = (uch)b;
 663     if (w == WSIZE)
 664     {
 665       flush_output(w);
 666       w = 0;
 667     }
 668     DUMPBITS(8)
 669   }
 670
 671
 672   /* restore the globals from the locals */
 673   wp = w;                       /* restore global window pointer */
 674   bb = b;                       /* restore global bit buffer */
 675   bk = k;
 676
 677   DEBG(">");
 678   return 0;
 679 }
 680
 681
 682
 683 STATIC int inflate_fixed(void)
 684 /* decompress an inflated type 1 (fixed Huffman codes) block.  We should
 685    either replace this with a custom decoder, or at least precompute the
 686    Huffman tables. */
 687 {
 688   int i;                /* temporary variable */
 689   struct huft *tl;      /* literal/length code table */
 690   struct huft *td;      /* distance code table */
 691   int bl;               /* lookup bits for tl */
 692   int bd;               /* lookup bits for td */
 693   unsigned l[288];      /* length list for huft_build */
 694
 695 DEBG("<fix");
 696
 697   /* set up literal table */
 698   for (i = 0; i < 144; i++)
 699     l[i] = 8;
 700   for (; i < 256; i++)
 701     l[i] = 9;
 702   for (; i < 280; i++)
 703     l[i] = 7;
 704   for (; i < 288; i++)          /* make a complete, but wrong code set */
 705     l[i] = 8;
 706   bl = 7;
 707   if ((i = huft_build(l, 288, 257, cplens, cplext, &tl, &bl)) != 0)
 708     return i;
 709
 710
 711   /* set up distance table */
 712   for (i = 0; i < 30; i++)      /* make an incomplete code set */
 713     l[i] = 5;
 714   bd = 5;
 715   if ((i = huft_build(l, 30, 0, cpdist, cpdext, &td, &bd)) > 1)
 716   {
 717     huft_free(tl);
 718
 719     DEBG(">");
 720     return i;
 721   }
 722
 723
 724   /* decompress until an end-of-block code */
 725   if (inflate_codes(tl, td, bl, bd))
 726     return 1;
 727
 728
 729   /* free the decoding tables, return */
 730   huft_free(tl);
 731   huft_free(td);
 732   return 0;
 733 }
 734
 735
 736
 737 STATIC int inflate_dynamic(void)
 738 /* decompress an inflated type 2 (dynamic Huffman codes) block. */
 739 {
 740   int i;                /* temporary variables */
 741   unsigned j;
 742   unsigned l;           /* last length */
 743   unsigned m;           /* mask for bit lengths table */
 744   unsigned n;           /* number of lengths to get */
 745   struct huft *tl;      /* literal/length code table */
 746   struct huft *td;      /* distance code table */
 747   int bl;               /* lookup bits for tl */
 748   int bd;               /* lookup bits for td */
 749   unsigned nb;          /* number of bit length codes */
 750   unsigned nl;          /* number of literal/length codes */
 751   unsigned nd;          /* number of distance codes */
 752 #ifdef PKZIP_BUG_WORKAROUND
 753   unsigned ll[288+32];  /* literal/length and distance code lengths */
 754 #else
 755   unsigned ll[286+30];  /* literal/length and distance code lengths */
 756 #endif
 757   register ulg b;       /* bit buffer */
 758   register unsigned k;  /* number of bits in bit buffer */
 759
 760 DEBG("<dyn");
 761
 762   /* make local bit buffer */
 763   b = bb;
 764   k = bk;
 765
 766
 767   /* read in table lengths */
 768   NEEDBITS(5)
 769   nl = 257 + ((unsigned)b & 0x1f);      /* number of literal/length codes */
 770   DUMPBITS(5)
 771   NEEDBITS(5)
 772   nd = 1 + ((unsigned)b & 0x1f);        /* number of distance codes */
 773   DUMPBITS(5)
 774   NEEDBITS(4)
 775   nb = 4 + ((unsigned)b & 0xf);         /* number of bit length codes */
 776   DUMPBITS(4)
 777 #ifdef PKZIP_BUG_WORKAROUND
 778   if (nl > 288 || nd > 32)
 779 #else
 780   if (nl > 286 || nd > 30)
 781 #endif
 782     return 1;                   /* bad lengths */
 783
 784 DEBG("dyn1 ");
 785
 786   /* read in bit-length-code lengths */
 787   for (j = 0; j < nb; j++)
 788   {
 789     NEEDBITS(3)
 790     ll[border[j]] = (unsigned)b & 7;
 791     DUMPBITS(3)
 792   }
 793   for (; j < 19; j++)
 794     ll[border[j]] = 0;
 795
 796 DEBG("dyn2 ");
 797
 798   /* build decoding table for trees--single level, 7 bit lookup */
 799   bl = 7;
 800   if ((i = huft_build(ll, 19, 19, NULL, NULL, &tl, &bl)) != 0)
 801   {
 802     if (i == 1)
 803       huft_free(tl);
 804     return i;                   /* incomplete code set */
 805   }
 806
 807 DEBG("dyn3 ");
 808
 809   /* read in literal and distance code lengths */
 810   n = nl + nd;
 811   m = mask_bits[bl];
 812   i = l = 0;
 813   while ((unsigned)i < n)
 814   {
 815     NEEDBITS((unsigned)bl)
 816     j = (td = tl + ((unsigned)b & m))->b;
 817     DUMPBITS(j)
 818     j = td->v.n;
 819     if (j < 16)                 /* length of code in bits (0..15) */
 820       ll[i++] = l = j;          /* save last length in l */
 821     else if (j == 16)           /* repeat last length 3 to 6 times */
 822     {
 823       NEEDBITS(2)
 824       j = 3 + ((unsigned)b & 3);
 825       DUMPBITS(2)
 826       if ((unsigned)i + j > n)
 827         return 1;
 828       while (j--)
 829         ll[i++] = l;
 830     }
 831     else if (j == 17)           /* 3 to 10 zero length codes */
 832     {
 833       NEEDBITS(3)
 834       j = 3 + ((unsigned)b & 7);
 835       DUMPBITS(3)
 836       if ((unsigned)i + j > n)
 837         return 1;
 838       while (j--)
 839         ll[i++] = 0;
 840       l = 0;
 841     }
 842     else                        /* j == 18: 11 to 138 zero length codes */
 843     {
 844       NEEDBITS(7)
 845       j = 11 + ((unsigned)b & 0x7f);
 846       DUMPBITS(7)
 847       if ((unsigned)i + j > n)
 848         return 1;
 849       while (j--)
 850         ll[i++] = 0;
 851       l = 0;
 852     }
 853   }
 854
 855 DEBG("dyn4 ");
 856
 857   /* free decoding table for trees */
 858   huft_free(tl);
 859
 860 DEBG("dyn5 ");
 861
 862   /* restore the global bit buffer */
 863   bb = b;
 864   bk = k;
 865
 866 DEBG("dyn5a ");
 867
 868   /* build the decoding tables for literal/length and distance codes */
 869   bl = lbits;
 870   if ((i = huft_build(ll, nl, 257, cplens, cplext, &tl, &bl)) != 0)
 871   {
 872 DEBG("dyn5b ");
 873     if (i == 1) {
 874       error(" incomplete literal tree\n");
 875       huft_free(tl);
 876     }
 877     return i;                   /* incomplete code set */
 878   }
 879 DEBG("dyn5c ");
 880   bd = dbits;
 881   if ((i = huft_build(ll + nl, nd, 0, cpdist, cpdext, &td, &bd)) != 0)
 882   {
 883 DEBG("dyn5d ");
 884     if (i == 1) {
 885       error(" incomplete distance tree\n");
 886 #ifdef PKZIP_BUG_WORKAROUND
 887       i = 0;
 888     }
 889 #else
 890       huft_free(td);
 891     }
 892     huft_free(tl);
 893     return i;                   /* incomplete code set */
 894 #endif
 895   }
 896
 897 DEBG("dyn6 ");
 898
 899   /* decompress until an end-of-block code */
 900   if (inflate_codes(tl, td, bl, bd))
 901     return 1;
 902
 903 DEBG("dyn7 ");
 904
 905   /* free the decoding tables, return */
 906   huft_free(tl);
 907   huft_free(td);
 908
 909   DEBG(">");
 910   return 0;
 911 }
 912
 913
 914
 915 STATIC int inflate_block(
 916         int *e                  /* last block flag */
 917         )
 918 /* decompress an inflated block */
 919 {
 920   unsigned t;           /* block type */
 921   register ulg b;       /* bit buffer */
 922   register unsigned k;  /* number of bits in bit buffer */
 923
 924   DEBG("<blk");
 925
 926   /* make local bit buffer */
 927   b = bb;
 928   k = bk;
 929
 930
 931   /* read in last block bit */
 932   NEEDBITS(1)
 933   *e = (int)b & 1;
 934   DUMPBITS(1)
 935
 936
 937   /* read in block type */
 938   NEEDBITS(2)
 939   t = (unsigned)b & 3;
 940   DUMPBITS(2)
 941
 942
 943   /* restore the global bit buffer */
 944   bb = b;
 945   bk = k;
 946
 947   /* inflate that block type */
 948   if (t == 2)
 949     return inflate_dynamic();
 950   if (t == 0)
 951     return inflate_stored();
 952   if (t == 1)
 953     return inflate_fixed();
 954
 955   DEBG(">");
 956
 957   /* bad block type */
 958   return 2;
 959 }
 960
 961
 962
 963 STATIC int inflate(void)
 964 /* decompress an inflated entry */
 965 {
 966   int e;                /* last block flag */
 967   int r;                /* result code */
 968   unsigned h;           /* maximum struct huft's malloc'ed */
 969   void *ptr;
 970
 971   /* initialize window, bit buffer */
 972   wp = 0;
 973   bk = 0;
 974   bb = 0;
 975
 976
 977   /* decompress until the last block */
 978   h = 0;
 979   do {
 980     hufts = 0;
 981     gzip_mark(&ptr);
 982     if ((r = inflate_block(&e)) != 0) {
 983       gzip_release(&ptr);
 984       return r;
 985     }
 986     gzip_release(&ptr);
 987     if (hufts > h)
 988       h = hufts;
 989   } while (!e);
 990
 991   /* Undo too much lookahead. The next read will be byte aligned so we
 992    * can discard unused bits in the last meaningful byte.
 993    */
 994   while (bk >= 8) {
 995     bk -= 8;
 996     inptr--;
 997   }
 998
 999   /* flush out slide */
1000   flush_output(wp);
1001
1002
1003   /* return success */
1004 #ifdef DEBUG
1005   fprintf(stderr, "<%u> ", h);
1006 #endif /* DEBUG */
1007   return 0;
1008 }
1009
1010 /**********************************************************************
1011  *
1012  * The following are support routines for inflate.c
1013  *
1014  **********************************************************************/
1015
1016 static ulg crc_32_tab[256];
1017 static ulg crc;         /* initialized in makecrc() so it'll reside in bss */
1018 #define CRC_VALUE (crc ^ 0xffffffffUL)
1019
1020 /*
1021  * Code to compute the CRC-32 table. Borrowed from
1022  * gzip-1.0.3/makecrc.c.
1023  */
1024
1025 static void
1026 makecrc(void)
1027 {
1028 /* Not copyrighted 1990 Mark Adler      */
1029
1030   unsigned long c;      /* crc shift register */
1031   unsigned long e;      /* polynomial exclusive-or pattern */
1032   int i;                /* counter for all possible eight bit values */
1033   int k;                /* byte being shifted into crc apparatus */
1034
1035   /* terms of polynomial defining this crc (except x^32): */
1036   static const int p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};
1037
1038   /* Make exclusive-or pattern from polynomial */
1039   e = 0;
1040   for (i = 0; i < sizeof(p)/sizeof(int); i++)
1041     e |= 1L << (31 - p[i]);
1042
1043   crc_32_tab[0] = 0;
1044
1045   for (i = 1; i < 256; i++)
1046   {
1047     c = 0;
1048     for (k = i | 256; k != 1; k >>= 1)
1049     {
1050       c = c & 1 ? (c >> 1) ^ e : c >> 1;
1051       if (k & 1)
1052         c ^= e;
1053     }
1054     crc_32_tab[i] = c;
1055   }
1056
1057   /* this is initialized here so this code could reside in ROM */
1058   crc = (ulg)0xffffffffUL; /* shift register contents */
1059 }
1060
1061 /* gzip flag byte */
1062 #define ASCII_FLAG   0x01 /* bit 0 set: file probably ASCII text */
1063 #define CONTINUATION 0x02 /* bit 1 set: continuation of multi-part gzip file */
1064 #define EXTRA_FIELD  0x04 /* bit 2 set: extra field present */
1065 #define ORIG_NAME    0x08 /* bit 3 set: original file name present */
1066 #define COMMENT      0x10 /* bit 4 set: file comment present */
1067 #define ENCRYPTED    0x20 /* bit 5 set: file is encrypted */
1068 #define RESERVED     0xC0 /* bit 6,7:   reserved */
1069
1070 /*
1071  * Do the uncompression!
1072  */
1073 static int gunzip(void)
1074 {
1075     uch flags;
1076     unsigned char magic[2]; /* magic header */
1077     char method;
1078     ulg orig_crc = 0;       /* original crc */
1079     ulg orig_len = 0;       /* original uncompressed length */
1080     int res;
1081
1082     magic[0] = (unsigned char)get_byte();
1083     magic[1] = (unsigned char)get_byte();
1084     method = (unsigned char)get_byte();
1085
1086     if (magic[0] != 037 ||
1087         ((magic[1] != 0213) && (magic[1] != 0236))) {
1088             error("bad gzip magic numbers");
1089             return -1;
1090     }
1091
1092     /* We only support method #8, DEFLATED */
1093     if (method != 8)  {
1094             error("internal error, invalid method");
1095             return -1;
1096     }
1097
1098     flags  = (uch)get_byte();
1099     if ((flags & ENCRYPTED) != 0) {
1100             error("Input is encrypted\n");
1101             return -1;
1102     }
1103     if ((flags & CONTINUATION) != 0) {
1104             error("Multi part input\n");
1105             return -1;
1106     }
1107     if ((flags & RESERVED) != 0) {
1108             error("Input has invalid flags\n");
1109             return -1;
1110     }
1111     (ulg)get_byte();    /* Get timestamp */
1112     ((ulg)get_byte()) << 8;
1113     ((ulg)get_byte()) << 16;
1114     ((ulg)get_byte()) << 24;
1115
1116     (void)get_byte();  /* Ignore extra flags for the moment */
1117     (void)get_byte();  /* Ignore OS type for the moment */
1118
1119     if ((flags & EXTRA_FIELD) != 0) {
1120             unsigned len = (unsigned)get_byte();
1121             len |= ((unsigned)get_byte())<<8;
1122             while (len--) (void)get_byte();
1123     }
1124
1125     /* Get original file name if it was truncated */
1126     if ((flags & ORIG_NAME) != 0) {
1127             /* Discard the old name */
1128             while (get_byte() != 0) /* null */ ;
1129     }
1130
1131     /* Discard file comment if any */
1132     if ((flags & COMMENT) != 0) {
1133             while (get_byte() != 0) /* null */ ;
1134     }
1135
1136     /* Decompress */
1137     if ((res = inflate())) {
1138             switch (res) {
1139             case 0:
1140                     break;
1141             case 1:
1142                     error("invalid compressed format (err=1)");
1143                     break;
1144             case 2:
1145                     error("invalid compressed format (err=2)");
1146                     break;
1147             case 3:
1148                     error("out of memory");
1149                     break;
1150             default:
1151                     error("invalid compressed format (other)");
1152             }
1153             return -1;
1154     }
1155
1156     /* Get the crc and original length */
1157     /* crc32  (see algorithm.doc)
1158      * uncompressed input size modulo 2^32
1159      */
1160     orig_crc = (ulg) get_byte();
1161     orig_crc |= (ulg) get_byte() << 8;
1162     orig_crc |= (ulg) get_byte() << 16;
1163     orig_crc |= (ulg) get_byte() << 24;
1164
1165     orig_len = (ulg) get_byte();
1166     orig_len |= (ulg) get_byte() << 8;
1167     orig_len |= (ulg) get_byte() << 16;
1168     orig_len |= (ulg) get_byte() << 24;
1169
1170     /* Validate decompression */
1171     if (orig_crc != CRC_VALUE) {
1172             error("crc error");
1173             return -1;
1174     }
1175     if (orig_len != bytes_out) {
1176             error("length error");
1177             return -1;
1178     }
1179     return 0;
1180 }
1181
1182