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