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