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