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