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(b, n, s, d, e, t, m)
 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 /* Given a list of code lengths and a maximum table size, make a set of
 283    tables to decode that set of codes.  Return zero on success, one if
 284    the given code set is incomplete (the tables are still built in this
 285    case), two if the input is invalid (all zero length codes or an
 286    oversubscribed set of lengths), and three if not enough memory. */
 287 {
 288   unsigned a;                   /* counter for codes of length k */
 289   unsigned c[BMAX+1];           /* bit length count table */
 290   unsigned f;                   /* i repeats in table every f entries */
 291   int g;                        /* maximum code length */
 292   int h;                        /* table level */
 293   register unsigned i;          /* counter, current code */
 294   register unsigned j;          /* counter */
 295   register int k;               /* number of bits in current code */
 296   int l;                        /* bits per table (returned in m) */
 297   register unsigned *p;         /* pointer into c[], b[], or v[] */
 298   register struct huft *q;      /* points to current table */
 299   struct huft r;                /* table entry for structure assignment */
 300   struct huft *u[BMAX];         /* table stack */
 301   unsigned v[N_MAX];            /* values in order of bit length */
 302   register int w;               /* bits before this table == (l * h) */
 303   unsigned x[BMAX+1];           /* bit offsets, then code stack */
 304   unsigned *xp;                 /* pointer into x */
 305   int y;                        /* number of dummy codes added */
 306   unsigned z;                   /* number of entries in current table */
 307
 308 DEBG("huft1 ");
 309
 310   /* Generate counts for each bit length */
 311   memzero(c, sizeof(c));
 312   p = b;  i = n;
 313   do {
 314     Tracecv(*p, (stderr, (n-i >= ' ' && n-i <= '~' ? "%c %d\n" : "0x%x %d\n"),
 315             n-i, *p));
 316     c[*p]++;                    /* assume all entries <= BMAX */
 317     p++;                      /* Can't combine with above line (Solaris bug) */
 318   } while (--i);
 319   if (c[0] == n)                /* null input--all zero length codes */
 320   {
 321     *t = (struct huft *)NULL;
 322     *m = 0;
 323     return 2;
 324   }
 325
 326 DEBG("huft2 ");
 327
 328   /* Find minimum and maximum length, bound *m by those */
 329   l = *m;
 330   for (j = 1; j <= BMAX; j++)
 331     if (c[j])
 332       break;
 333   k = j;                        /* minimum code length */
 334   if ((unsigned)l < j)
 335     l = j;
 336   for (i = BMAX; i; i--)
 337     if (c[i])
 338       break;
 339   g = i;                        /* maximum code length */
 340   if ((unsigned)l > i)
 341     l = i;
 342   *m = l;
 343
 344 DEBG("huft3 ");
 345
 346   /* Adjust last length count to fill out codes, if needed */
 347   for (y = 1 << j; j < i; j++, y <<= 1)
 348     if ((y -= c[j]) < 0)
 349       return 2;                 /* bad input: more codes than bits */
 350   if ((y -= c[i]) < 0)
 351     return 2;
 352   c[i] += y;
 353
 354 DEBG("huft4 ");
 355
 356   /* Generate starting offsets into the value table for each length */
 357   x[1] = j = 0;
 358   p = c + 1;  xp = x + 2;
 359   while (--i) {                 /* note that i == g from above */
 360     *xp++ = (j += *p++);
 361   }
 362
 363 DEBG("huft5 ");
 364
 365   /* Make a table of values in order of bit lengths */
 366   p = b;  i = 0;
 367   do {
 368     if ((j = *p++) != 0)
 369       v[x[j]++] = i;
 370   } while (++i < n);
 371   n = x[g];                   /* set n to length of v */
 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           if (j < z)
 409             while (++j < z)       /* try smaller tables up to z bits */
 410             {
 411               if ((f <<= 1) <= *++xp)
 412                 break;            /* enough codes to use up j bits */
 413               f -= *xp;           /* else deduct codes from patterns */
 414             }
 415         }
 416 DEBG1("3 ");
 417         z = 1 << j;             /* table entries for j-bit table */
 418
 419         /* allocate and link in new table */
 420         if ((q = (struct huft *)malloc((z + 1)*sizeof(struct huft))) ==
 421             (struct huft *)NULL)
 422         {
 423           if (h)
 424             huft_free(u[0]);
 425           return 3;             /* not enough memory */
 426         }
 427 DEBG1("4 ");
 428         hufts += z + 1;         /* track memory usage */
 429         *t = q + 1;             /* link to list for huft_free() */
 430         *(t = &(q->v.t)) = (struct huft *)NULL;
 431         u[h] = ++q;             /* table starts after link */
 432
 433 DEBG1("5 ");
 434         /* connect to last table, if there is one */
 435         if (h)
 436         {
 437           x[h] = i;             /* save pattern for backing up */
 438           r.b = (uch)l;         /* bits to dump before this table */
 439           r.e = (uch)(16 + j);  /* bits in this table */
 440           r.v.t = q;            /* pointer to this table */
 441           j = i >> (w - l);     /* (get around Turbo C bug) */
 442           u[h-1][j] = r;        /* connect to last table */
 443         }
 444 DEBG1("6 ");
 445       }
 446 DEBG("h6c ");
 447
 448       /* set up table entry in r */
 449       r.b = (uch)(k - w);
 450       if (p >= v + n)
 451         r.e = 99;               /* out of values--invalid code */
 452       else if (*p < s)
 453       {
 454         r.e = (uch)(*p < 256 ? 16 : 15);    /* 256 is end-of-block code */
 455         r.v.n = (ush)(*p);             /* simple code is just the value */
 456         p++;                           /* one compiler does not like *p++ */
 457       }
 458       else
 459       {
 460         r.e = (uch)e[*p - s];   /* non-simple--look up in lists */
 461         r.v.n = d[*p++ - s];
 462       }
 463 DEBG("h6d ");
 464
 465       /* fill code-like entries with r */
 466       f = 1 << (k - w);
 467       for (j = i >> w; j < z; j += f)
 468         q[j] = r;
 469
 470       /* backwards increment the k-bit code i */
 471       for (j = 1 << (k - 1); i & j; j >>= 1)
 472         i ^= j;
 473       i ^= j;
 474
 475       /* backup over finished tables */
 476       while ((i & ((1 << w) - 1)) != x[h])
 477       {
 478         h--;                    /* don't need to update q */
 479         w -= l;
 480       }
 481 DEBG("h6e ");
 482     }
 483 DEBG("h6f ");
 484   }
 485
 486 DEBG("huft7 ");
 487
 488   /* Return true (1) if we were given an incomplete table */
 489   return y != 0 && g != 1;
 490 }
 491
 492
 493
 494 STATIC int huft_free(t)
 495 struct huft *t;         /* table to free */
 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(tl, td, bl, bd)
 516 struct huft *tl, *td;   /* literal/length and distance decoder tables */
 517 int bl, bd;             /* number of bits decoded by tl[] and td[] */
 518 /* inflate (decompress) the codes in a deflated (compressed) block.
 519    Return an error code or zero if it all goes ok. */
 520 {
 521   register unsigned e;  /* table entry flag/number of extra bits */
 522   unsigned n, d;        /* length and index for copy */
 523   unsigned w;           /* current window position */
 524   struct huft *t;       /* pointer to table entry */
 525   unsigned ml, md;      /* masks for bl and bd bits */
 526   register ulg b;       /* bit buffer */
 527   register unsigned k;  /* number of bits in bit buffer */
 528
 529
 530   /* make local copies of globals */
 531   b = bb;                       /* initialize bit buffer */
 532   k = bk;
 533   w = wp;                       /* initialize window position */
 534
 535   /* inflate the coded data */
 536   ml = mask_bits[bl];           /* precompute masks for speed */
 537   md = mask_bits[bd];
 538   for (;;)                      /* do until end of block */
 539   {
 540     NEEDBITS((unsigned)bl)
 541     if ((e = (t = tl + ((unsigned)b & ml))->e) > 16)
 542       do {
 543         if (e == 99)
 544           return 1;
 545         DUMPBITS(t->b)
 546         e -= 16;
 547         NEEDBITS(e)
 548       } while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16);
 549     DUMPBITS(t->b)
 550     if (e == 16)                /* then it's a literal */
 551     {
 552       slide[w++] = (uch)t->v.n;
 553       Tracevv((stderr, "%c", slide[w-1]));
 554       if (w == WSIZE)
 555       {
 556         flush_output(w);
 557         w = 0;
 558       }
 559     }
 560     else                        /* it's an EOB or a length */
 561     {
 562       /* exit if end of block */
 563       if (e == 15)
 564         break;
 565
 566       /* get length of block to copy */
 567       NEEDBITS(e)
 568       n = t->v.n + ((unsigned)b & mask_bits[e]);
 569       DUMPBITS(e);
 570
 571       /* decode distance of block to copy */
 572       NEEDBITS((unsigned)bd)
 573       if ((e = (t = td + ((unsigned)b & md))->e) > 16)
 574         do {
 575           if (e == 99)
 576             return 1;
 577           DUMPBITS(t->b)
 578           e -= 16;
 579           NEEDBITS(e)
 580         } while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16);
 581       DUMPBITS(t->b)
 582       NEEDBITS(e)
 583       d = w - t->v.n - ((unsigned)b & mask_bits[e]);
 584       DUMPBITS(e)
 585       Tracevv((stderr,"\\[%d,%d]", w-d, n));
 586
 587       /* do the copy */
 588       do {
 589         n -= (e = (e = WSIZE - ((d &= WSIZE-1) > w ? d : w)) > n ? n : e);
 590 #if !defined(NOMEMCPY) && !defined(DEBUG)
 591         if (w - d >= e)         /* (this test assumes unsigned comparison) */
 592         {
 593           memcpy(slide + w, slide + d, e);
 594           w += e;
 595           d += e;
 596         }
 597         else                      /* do it slow to avoid memcpy() overlap */
 598 #endif /* !NOMEMCPY */
 599           do {
 600             slide[w++] = slide[d++];
 601             Tracevv((stderr, "%c", slide[w-1]));
 602           } while (--e);
 603         if (w == WSIZE)
 604         {
 605           flush_output(w);
 606           w = 0;
 607         }
 608       } while (n);
 609     }
 610   }
 611
 612
 613   /* restore the globals from the locals */
 614   wp = w;                       /* restore global window pointer */
 615   bb = b;                       /* restore global bit buffer */
 616   bk = k;
 617
 618   /* done */
 619   return 0;
 620 }
 621
 622
 623
 624 STATIC int inflate_stored()
 625 /* "decompress" an inflated type 0 (stored) block. */
 626 {
 627   unsigned n;           /* number of bytes in block */
 628   unsigned w;           /* current window position */
 629   register ulg b;       /* bit buffer */
 630   register unsigned k;  /* number of bits in bit buffer */
 631
 632 DEBG("<stor");
 633
 634   /* make local copies of globals */
 635   b = bb;                       /* initialize bit buffer */
 636   k = bk;
 637   w = wp;                       /* initialize window position */
 638
 639
 640   /* go to byte boundary */
 641   n = k & 7;
 642   DUMPBITS(n);
 643
 644
 645   /* get the length and its complement */
 646   NEEDBITS(16)
 647   n = ((unsigned)b & 0xffff);
 648   DUMPBITS(16)
 649   NEEDBITS(16)
 650   if (n != (unsigned)((~b) & 0xffff))
 651     return 1;                   /* error in compressed data */
 652   DUMPBITS(16)
 653
 654
 655   /* read and output the compressed data */
 656   while (n--)
 657   {
 658     NEEDBITS(8)
 659     slide[w++] = (uch)b;
 660     if (w == WSIZE)
 661     {
 662       flush_output(w);
 663       w = 0;
 664     }
 665     DUMPBITS(8)
 666   }
 667
 668
 669   /* restore the globals from the locals */
 670   wp = w;                       /* restore global window pointer */
 671   bb = b;                       /* restore global bit buffer */
 672   bk = k;
 673
 674   DEBG(">");
 675   return 0;
 676 }
 677
 678
 679
 680 STATIC int inflate_fixed()
 681 /* decompress an inflated type 1 (fixed Huffman codes) block.  We should
 682    either replace this with a custom decoder, or at least precompute the
 683    Huffman tables. */
 684 {
 685   int i;                /* temporary variable */
 686   struct huft *tl;      /* literal/length code table */
 687   struct huft *td;      /* distance code table */
 688   int bl;               /* lookup bits for tl */
 689   int bd;               /* lookup bits for td */
 690   unsigned l[288];      /* length list for huft_build */
 691
 692 DEBG("<fix");
 693
 694   /* set up literal table */
 695   for (i = 0; i < 144; i++)
 696     l[i] = 8;
 697   for (; i < 256; i++)
 698     l[i] = 9;
 699   for (; i < 280; i++)
 700     l[i] = 7;
 701   for (; i < 288; i++)          /* make a complete, but wrong code set */
 702     l[i] = 8;
 703   bl = 7;
 704   if ((i = huft_build(l, 288, 257, cplens, cplext, &tl, &bl)) != 0)
 705     return i;
 706
 707
 708   /* set up distance table */
 709   for (i = 0; i < 30; i++)      /* make an incomplete code set */
 710     l[i] = 5;
 711   bd = 5;
 712   if ((i = huft_build(l, 30, 0, cpdist, cpdext, &td, &bd)) > 1)
 713   {
 714     huft_free(tl);
 715
 716     DEBG(">");
 717     return i;
 718   }
 719
 720
 721   /* decompress until an end-of-block code */
 722   if (inflate_codes(tl, td, bl, bd))
 723     return 1;
 724
 725
 726   /* free the decoding tables, return */
 727   huft_free(tl);
 728   huft_free(td);
 729   return 0;
 730 }
 731
 732
 733
 734 STATIC int inflate_dynamic()
 735 /* decompress an inflated type 2 (dynamic Huffman codes) block. */
 736 {
 737   int i;                /* temporary variables */
 738   unsigned j;
 739   unsigned l;           /* last length */
 740   unsigned m;           /* mask for bit lengths table */
 741   unsigned n;           /* number of lengths to get */
 742   struct huft *tl;      /* literal/length code table */
 743   struct huft *td;      /* distance code table */
 744   int bl;               /* lookup bits for tl */
 745   int bd;               /* lookup bits for td */
 746   unsigned nb;          /* number of bit length codes */
 747   unsigned nl;          /* number of literal/length codes */
 748   unsigned nd;          /* number of distance codes */
 749 #ifdef PKZIP_BUG_WORKAROUND
 750   unsigned ll[288+32];  /* literal/length and distance code lengths */
 751 #else
 752   unsigned ll[286+30];  /* literal/length and distance code lengths */
 753 #endif
 754   register ulg b;       /* bit buffer */
 755   register unsigned k;  /* number of bits in bit buffer */
 756
 757 DEBG("<dyn");
 758
 759   /* make local bit buffer */
 760   b = bb;
 761   k = bk;
 762
 763
 764   /* read in table lengths */
 765   NEEDBITS(5)
 766   nl = 257 + ((unsigned)b & 0x1f);      /* number of literal/length codes */
 767   DUMPBITS(5)
 768   NEEDBITS(5)
 769   nd = 1 + ((unsigned)b & 0x1f);        /* number of distance codes */
 770   DUMPBITS(5)
 771   NEEDBITS(4)
 772   nb = 4 + ((unsigned)b & 0xf);         /* number of bit length codes */
 773   DUMPBITS(4)
 774 #ifdef PKZIP_BUG_WORKAROUND
 775   if (nl > 288 || nd > 32)
 776 #else
 777   if (nl > 286 || nd > 30)
 778 #endif
 779     return 1;                   /* bad lengths */
 780
 781 DEBG("dyn1 ");
 782
 783   /* read in bit-length-code lengths */
 784   for (j = 0; j < nb; j++)
 785   {
 786     NEEDBITS(3)
 787     ll[border[j]] = (unsigned)b & 7;
 788     DUMPBITS(3)
 789   }
 790   for (; j < 19; j++)
 791     ll[border[j]] = 0;
 792
 793 DEBG("dyn2 ");
 794
 795   /* build decoding table for trees--single level, 7 bit lookup */
 796   bl = 7;
 797   if ((i = huft_build(ll, 19, 19, NULL, NULL, &tl, &bl)) != 0)
 798   {
 799     if (i == 1)
 800       huft_free(tl);
 801     return i;                   /* incomplete code set */
 802   }
 803
 804 DEBG("dyn3 ");
 805
 806   /* read in literal and distance code lengths */
 807   n = nl + nd;
 808   m = mask_bits[bl];
 809   i = l = 0;
 810   while ((unsigned)i < n)
 811   {
 812     NEEDBITS((unsigned)bl)
 813     j = (td = tl + ((unsigned)b & m))->b;
 814     DUMPBITS(j)
 815     j = td->v.n;
 816     if (j < 16)                 /* length of code in bits (0..15) */
 817       ll[i++] = l = j;          /* save last length in l */
 818     else if (j == 16)           /* repeat last length 3 to 6 times */
 819     {
 820       NEEDBITS(2)
 821       j = 3 + ((unsigned)b & 3);
 822       DUMPBITS(2)
 823       if ((unsigned)i + j > n)
 824         return 1;
 825       while (j--)
 826         ll[i++] = l;
 827     }
 828     else if (j == 17)           /* 3 to 10 zero length codes */
 829     {
 830       NEEDBITS(3)
 831       j = 3 + ((unsigned)b & 7);
 832       DUMPBITS(3)
 833       if ((unsigned)i + j > n)
 834         return 1;
 835       while (j--)
 836         ll[i++] = 0;
 837       l = 0;
 838     }
 839     else                        /* j == 18: 11 to 138 zero length codes */
 840     {
 841       NEEDBITS(7)
 842       j = 11 + ((unsigned)b & 0x7f);
 843       DUMPBITS(7)
 844       if ((unsigned)i + j > n)
 845         return 1;
 846       while (j--)
 847         ll[i++] = 0;
 848       l = 0;
 849     }
 850   }
 851
 852 DEBG("dyn4 ");
 853
 854   /* free decoding table for trees */
 855   huft_free(tl);
 856
 857 DEBG("dyn5 ");
 858
 859   /* restore the global bit buffer */
 860   bb = b;
 861   bk = k;
 862
 863 DEBG("dyn5a ");
 864
 865   /* build the decoding tables for literal/length and distance codes */
 866   bl = lbits;
 867   if ((i = huft_build(ll, nl, 257, cplens, cplext, &tl, &bl)) != 0)
 868   {
 869 DEBG("dyn5b ");
 870     if (i == 1) {
 871       error(" incomplete literal tree\n");
 872       huft_free(tl);
 873     }
 874     return i;                   /* incomplete code set */
 875   }
 876 DEBG("dyn5c ");
 877   bd = dbits;
 878   if ((i = huft_build(ll + nl, nd, 0, cpdist, cpdext, &td, &bd)) != 0)
 879   {
 880 DEBG("dyn5d ");
 881     if (i == 1) {
 882       error(" incomplete distance tree\n");
 883 #ifdef PKZIP_BUG_WORKAROUND
 884       i = 0;
 885     }
 886 #else
 887       huft_free(td);
 888     }
 889     huft_free(tl);
 890     return i;                   /* incomplete code set */
 891 #endif
 892   }
 893
 894 DEBG("dyn6 ");
 895
 896   /* decompress until an end-of-block code */
 897   if (inflate_codes(tl, td, bl, bd))
 898     return 1;
 899
 900 DEBG("dyn7 ");
 901
 902   /* free the decoding tables, return */
 903   huft_free(tl);
 904   huft_free(td);
 905
 906   DEBG(">");
 907   return 0;
 908 }
 909
 910
 911
 912 STATIC int inflate_block(e)
 913 int *e;                 /* last block flag */
 914 /* decompress an inflated block */
 915 {
 916   unsigned t;           /* block type */
 917   register ulg b;       /* bit buffer */
 918   register unsigned k;  /* number of bits in bit buffer */
 919
 920   DEBG("<blk");
 921
 922   /* make local bit buffer */
 923   b = bb;
 924   k = bk;
 925
 926
 927   /* read in last block bit */
 928   NEEDBITS(1)
 929   *e = (int)b & 1;
 930   DUMPBITS(1)
 931
 932
 933   /* read in block type */
 934   NEEDBITS(2)
 935   t = (unsigned)b & 3;
 936   DUMPBITS(2)
 937
 938
 939   /* restore the global bit buffer */
 940   bb = b;
 941   bk = k;
 942
 943   /* inflate that block type */
 944   if (t == 2)
 945     return inflate_dynamic();
 946   if (t == 0)
 947     return inflate_stored();
 948   if (t == 1)
 949     return inflate_fixed();
 950
 951   DEBG(">");
 952
 953   /* bad block type */
 954   return 2;
 955 }
 956
 957
 958
 959 STATIC int inflate()
 960 /* decompress an inflated entry */
 961 {
 962   int e;                /* last block flag */
 963   int r;                /* result code */
 964   unsigned h;           /* maximum struct huft's malloc'ed */
 965   void *ptr;
 966
 967   /* initialize window, bit buffer */
 968   wp = 0;
 969   bk = 0;
 970   bb = 0;
 971
 972
 973   /* decompress until the last block */
 974   h = 0;
 975   do {
 976     hufts = 0;
 977     gzip_mark(&ptr);
 978     if ((r = inflate_block(&e)) != 0) {
 979       gzip_release(&ptr);
 980       return r;
 981     }
 982     gzip_release(&ptr);
 983     if (hufts > h)
 984       h = hufts;
 985   } while (!e);
 986
 987   /* Undo too much lookahead. The next read will be byte aligned so we
 988    * can discard unused bits in the last meaningful byte.
 989    */
 990   while (bk >= 8) {
 991     bk -= 8;
 992     inptr--;
 993   }
 994
 995   /* flush out slide */
 996   flush_output(wp);
 997
 998
 999   /* return success */
1000 #ifdef DEBUG
1001   fprintf(stderr, "<%u> ", h);
1002 #endif /* DEBUG */
1003   return 0;
1004 }
1005
1006 /**********************************************************************
1007  *
1008  * The following are support routines for inflate.c
1009  *
1010  **********************************************************************/
1011
1012 static ulg crc_32_tab[256];
1013 static ulg crc;         /* initialized in makecrc() so it'll reside in bss */
1014 #define CRC_VALUE (crc ^ 0xffffffffUL)
1015
1016 /*
1017  * Code to compute the CRC-32 table. Borrowed from
1018  * gzip-1.0.3/makecrc.c.
1019  */
1020
1021 static void
1022 makecrc(void)
1023 {
1024 /* Not copyrighted 1990 Mark Adler      */
1025
1026   unsigned long c;      /* crc shift register */
1027   unsigned long e;      /* polynomial exclusive-or pattern */
1028   int i;                /* counter for all possible eight bit values */
1029   int k;                /* byte being shifted into crc apparatus */
1030
1031   /* terms of polynomial defining this crc (except x^32): */
1032   static const int p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};
1033
1034   /* Make exclusive-or pattern from polynomial */
1035   e = 0;
1036   for (i = 0; i < sizeof(p)/sizeof(int); i++)
1037     e |= 1L << (31 - p[i]);
1038
1039   crc_32_tab[0] = 0;
1040
1041   for (i = 1; i < 256; i++)
1042   {
1043     c = 0;
1044     for (k = i | 256; k != 1; k >>= 1)
1045     {
1046       c = c & 1 ? (c >> 1) ^ e : c >> 1;
1047       if (k & 1)
1048         c ^= e;
1049     }
1050     crc_32_tab[i] = c;
1051   }
1052
1053   /* this is initialized here so this code could reside in ROM */
1054   crc = (ulg)0xffffffffUL; /* shift register contents */
1055 }
1056
1057 /* gzip flag byte */
1058 #define ASCII_FLAG   0x01 /* bit 0 set: file probably ASCII text */
1059 #define CONTINUATION 0x02 /* bit 1 set: continuation of multi-part gzip file */
1060 #define EXTRA_FIELD  0x04 /* bit 2 set: extra field present */
1061 #define ORIG_NAME    0x08 /* bit 3 set: original file name present */
1062 #define COMMENT      0x10 /* bit 4 set: file comment present */
1063 #define ENCRYPTED    0x20 /* bit 5 set: file is encrypted */
1064 #define RESERVED     0xC0 /* bit 6,7:   reserved */
1065
1066 /*
1067  * Do the uncompression!
1068  */
1069 static int gunzip(void)
1070 {
1071     uch flags;
1072     unsigned char magic[2]; /* magic header */
1073     char method;
1074     ulg orig_crc = 0;       /* original crc */
1075     ulg orig_len = 0;       /* original uncompressed length */
1076     int res;
1077
1078     magic[0] = (unsigned char)get_byte();
1079     magic[1] = (unsigned char)get_byte();
1080     method = (unsigned char)get_byte();
1081
1082     if (magic[0] != 037 ||
1083         ((magic[1] != 0213) && (magic[1] != 0236))) {
1084             error("bad gzip magic numbers");
1085             return -1;
1086     }
1087
1088     /* We only support method #8, DEFLATED */
1089     if (method != 8)  {
1090             error("internal error, invalid method");
1091             return -1;
1092     }
1093
1094     flags  = (uch)get_byte();
1095     if ((flags & ENCRYPTED) != 0) {
1096             error("Input is encrypted\n");
1097             return -1;
1098     }
1099     if ((flags & CONTINUATION) != 0) {
1100             error("Multi part input\n");
1101             return -1;
1102     }
1103     if ((flags & RESERVED) != 0) {
1104             error("Input has invalid flags\n");
1105             return -1;
1106     }
1107     (ulg)get_byte();    /* Get timestamp */
1108     ((ulg)get_byte()) << 8;
1109     ((ulg)get_byte()) << 16;
1110     ((ulg)get_byte()) << 24;
1111
1112     (void)get_byte();  /* Ignore extra flags for the moment */
1113     (void)get_byte();  /* Ignore OS type for the moment */
1114
1115     if ((flags & EXTRA_FIELD) != 0) {
1116             unsigned len = (unsigned)get_byte();
1117             len |= ((unsigned)get_byte())<<8;
1118             while (len--) (void)get_byte();
1119     }
1120
1121     /* Get original file name if it was truncated */
1122     if ((flags & ORIG_NAME) != 0) {
1123             /* Discard the old name */
1124             while (get_byte() != 0) /* null */ ;
1125     }
1126
1127     /* Discard file comment if any */
1128     if ((flags & COMMENT) != 0) {
1129             while (get_byte() != 0) /* null */ ;
1130     }
1131
1132     /* Decompress */
1133     if ((res = inflate())) {
1134             switch (res) {
1135             case 0:
1136                     break;
1137             case 1:
1138                     error("invalid compressed format (err=1)");
1139                     break;
1140             case 2:
1141                     error("invalid compressed format (err=2)");
1142                     break;
1143             case 3:
1144                     error("out of memory");
1145                     break;
1146             default:
1147                     error("invalid compressed format (other)");
1148             }
1149             return -1;
1150     }
1151
1152     /* Get the crc and original length */
1153     /* crc32  (see algorithm.doc)
1154      * uncompressed input size modulo 2^32
1155      */
1156     orig_crc = (ulg) get_byte();
1157     orig_crc |= (ulg) get_byte() << 8;
1158     orig_crc |= (ulg) get_byte() << 16;
1159     orig_crc |= (ulg) get_byte() << 24;
1160
1161     orig_len = (ulg) get_byte();
1162     orig_len |= (ulg) get_byte() << 8;
1163     orig_len |= (ulg) get_byte() << 16;
1164     orig_len |= (ulg) get_byte() << 24;
1165
1166     /* Validate decompression */
1167     if (orig_crc != CRC_VALUE) {
1168             error("crc error");
1169             return -1;
1170     }
1171     if (orig_len != bytes_out) {
1172             error("length error");
1173             return -1;
1174     }
1175     return 0;
1176 }
1177
1178