util/mkelfImage/kunzip_src/lib/inflate.c

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