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