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