root/arch/i386/boot/compressed/inflate.c

/* [previous][next][first][last][top][bottom][index][help] */

DEFINITIONS

This source file includes following definitions.
  1. huft_build
  2. huft_free
  3. inflate_codes
  4. inflate_stored
  5. inflate_fixed
  6. inflate_dynamic
  7. inflate_block
  8. inflate

   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 
  11 #ifndef lint
  12 static char rcsid[] = "$Id: inflate.c,v 0.10 1993/02/04 13:21:06 jloup Exp $";
  13 #endif
  14 
  15 #include "gzip.h"
  16 #define slide window
  17 
  18 #if defined(STDC_HEADERS) || defined(HAVE_STDLIB_H)
  19 #  include <sys/types.h>
  20 #  include <stdlib.h>
  21 #endif
  22 
  23 struct huft {
  24   uch e;                /* number of extra bits or operation */
  25   uch b;                /* number of bits in this code or subcode */
  26   union {
  27     ush n;              /* literal, length base, or distance base */
  28     struct huft *t;     /* pointer to next level of table */
  29   } v;
  30 };
  31 
  32 
  33 /* Function prototypes */
  34 int huft_build OF((unsigned *, unsigned, unsigned, ush *, ush *,
  35                    struct huft **, int *));
  36 int huft_free OF((struct huft *));
  37 int inflate_codes OF((struct huft *, struct huft *, int, int));
  38 int inflate_stored OF((void));
  39 int inflate_fixed OF((void));
  40 int inflate_dynamic OF((void));
  41 int inflate_block OF((int *));
  42 int inflate OF((void));
  43 
  44 
  45 #define wp outcnt
  46 #define flush_output(w) (wp=(w),flush_window())
  47 
  48 /* Tables for deflate from PKZIP's appnote.txt. */
  49 static unsigned border[] = {    /* Order of the bit length code lengths */
  50         16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
  51 static ush cplens[] = {         /* Copy lengths for literal codes 257..285 */
  52         3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
  53         35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
  54         /* note: see note #13 above about the 258 in this list. */
  55 static ush cplext[] = {         /* Extra bits for literal codes 257..285 */
  56         0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
  57         3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 99, 99}; /* 99==invalid */
  58 static ush cpdist[] = {         /* Copy offsets for distance codes 0..29 */
  59         1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
  60         257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
  61         8193, 12289, 16385, 24577};
  62 static ush cpdext[] = {         /* Extra bits for distance codes */
  63         0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
  64         7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
  65         12, 12, 13, 13};
  66 
  67 
  68 ulg bb;                         /* bit buffer */
  69 unsigned bk;                    /* bits in bit buffer */
  70 
  71 ush mask_bits[] = {
  72     0x0000,
  73     0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
  74     0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
  75 };
  76 
  77 #ifdef CRYPT
  78   uch cc;
  79 #  define NEXTBYTE() \
  80      (decrypt ? (cc = get_byte(), zdecode(cc), cc) : get_byte())
  81 #else
  82 #  define NEXTBYTE()  (uch)get_byte()
  83 #endif
  84 #define NEEDBITS(n) {while(k<(n)){b|=((ulg)NEXTBYTE())<<k;k+=8;}}
  85 #define DUMPBITS(n) {b>>=(n);k-=(n);}
  86 
  87 int lbits = 9;          /* bits in base literal/length lookup table */
  88 int dbits = 6;          /* bits in base distance lookup table */
  89 
  90 
  91 /* If BMAX needs to be larger than 16, then h and x[] should be ulg. */
  92 #define BMAX 16         /* maximum bit length of any code (16 for explode) */
  93 #define N_MAX 288       /* maximum number of codes in any set */
  94 
  95 
  96 unsigned hufts;         /* track memory usage */
  97 
  98 
  99 int huft_build(b, n, s, d, e, t, m)
     /* [previous][next][first][last][top][bottom][index][help] */
 100 unsigned *b;            /* code lengths in bits (all assumed <= BMAX) */
 101 unsigned n;             /* number of codes (assumed <= N_MAX) */
 102 unsigned s;             /* number of simple-valued codes (0..s-1) */
 103 ush *d;                 /* list of base values for non-simple codes */
 104 ush *e;                 /* list of extra bits for non-simple codes */
 105 struct huft **t;        /* result: starting table */
 106 int *m;                 /* maximum lookup bits, returns actual */
 107 /* Given a list of code lengths and a maximum table size, make a set of
 108    tables to decode that set of codes.  Return zero on success, one if
 109    the given code set is incomplete (the tables are still built in this
 110    case), two if the input is invalid (all zero length codes or an
 111    oversubscribed set of lengths), and three if not enough memory. */
 112 {
 113   unsigned a;                   /* counter for codes of length k */
 114   unsigned c[BMAX+1];           /* bit length count table */
 115   unsigned f;                   /* i repeats in table every f entries */
 116   int g;                        /* maximum code length */
 117   int h;                        /* table level */
 118   register unsigned i;          /* counter, current code */
 119   register unsigned j;          /* counter */
 120   register int k;               /* number of bits in current code */
 121   int l;                        /* bits per table (returned in m) */
 122   register unsigned *p;         /* pointer into c[], b[], or v[] */
 123   register struct huft *q;      /* points to current table */
 124   struct huft r;                /* table entry for structure assignment */
 125   struct huft *u[BMAX];         /* table stack */
 126   unsigned v[N_MAX];            /* values in order of bit length */
 127   register int w;               /* bits before this table == (l * h) */
 128   unsigned x[BMAX+1];           /* bit offsets, then code stack */
 129   unsigned *xp;                 /* pointer into x */
 130   int y;                        /* number of dummy codes added */
 131   unsigned z;                   /* number of entries in current table */
 132 
 133 DEBG("huft1 ");
 134 
 135   /* Generate counts for each bit length */
 136   memzero(c, sizeof(c));
 137   p = b;  i = n;
 138   do {
 139     c[*p++]++;                  /* assume all entries <= BMAX */
 140   } while (--i);
 141   if (c[0] == n)                /* null input--all zero length codes */
 142   {
 143     *t = (struct huft *)NULL;
 144     *m = 0;
 145     return 0;
 146   }
 147 
 148 DEBG("huft2 ");
 149 
 150   /* Find minimum and maximum length, bound *m by those */
 151   l = *m;
 152   for (j = 1; j <= BMAX; j++)
 153     if (c[j])
 154       break;
 155   k = j;                        /* minimum code length */
 156   if ((unsigned)l < j)
 157     l = j;
 158   for (i = BMAX; i; i--)
 159     if (c[i])
 160       break;
 161   g = i;                        /* maximum code length */
 162   if ((unsigned)l > i)
 163     l = i;
 164   *m = l;
 165 
 166 DEBG("huft3 ");
 167 
 168   /* Adjust last length count to fill out codes, if needed */
 169   for (y = 1 << j; j < i; j++, y <<= 1)
 170     if ((y -= c[j]) < 0)
 171       return 2;                 /* bad input: more codes than bits */
 172   if ((y -= c[i]) < 0)
 173     return 2;
 174   c[i] += y;
 175 
 176 DEBG("huft4 ");
 177 
 178   /* Generate starting offsets into the value table for each length */
 179   x[1] = j = 0;
 180   p = c + 1;  xp = x + 2;
 181   while (--i) {                 /* note that i == g from above */
 182     *xp++ = (j += *p++);
 183   }
 184 
 185 DEBG("huft5 ");
 186 
 187   /* Make a table of values in order of bit lengths */
 188   p = b;  i = 0;
 189   do {
 190     if ((j = *p++) != 0)
 191       v[x[j]++] = i;
 192   } while (++i < n);
 193 
 194 DEBG("h6 ");
 195 
 196   /* Generate the Huffman codes and for each, make the table entries */
 197   x[0] = i = 0;                 /* first Huffman code is zero */
 198   p = v;                        /* grab values in bit order */
 199   h = -1;                       /* no tables yet--level -1 */
 200   w = -l;                       /* bits decoded == (l * h) */
 201   u[0] = (struct huft *)NULL;   /* just to keep compilers happy */
 202   q = (struct huft *)NULL;      /* ditto */
 203   z = 0;                        /* ditto */
 204 DEBG("h6a ");
 205 
 206   /* go through the bit lengths (k already is bits in shortest code) */
 207   for (; k <= g; k++)
 208   {
 209 DEBG("h6b ");
 210     a = c[k];
 211     while (a--)
 212     {
 213 DEBG("h6b1 ");
 214       /* here i is the Huffman code of length k bits for value *p */
 215       /* make tables up to required level */
 216       while (k > w + l)
 217       {
 218 DEBG1("1 ");
 219         h++;
 220         w += l;                 /* previous table always l bits */
 221 
 222         /* compute minimum size table less than or equal to l bits */
 223         z = (z = g - w) > (unsigned)l ? l : z;  /* upper limit on table size */
 224         if ((f = 1 << (j = k - w)) > a + 1)     /* try a k-w bit table */
 225         {                       /* too few codes for k-w bit table */
 226 DEBG1("2 ");
 227           f -= a + 1;           /* deduct codes from patterns left */
 228           xp = c + k;
 229           while (++j < z)       /* try smaller tables up to z bits */
 230           {
 231             if ((f <<= 1) <= *++xp)
 232               break;            /* enough codes to use up j bits */
 233             f -= *xp;           /* else deduct codes from patterns */
 234           }
 235         }
 236 DEBG1("3 ");
 237         z = 1 << j;             /* table entries for j-bit table */
 238 
 239         /* allocate and link in new table */
 240         q = (struct huft *)malloc((z + 1)*sizeof(struct huft));
 241 DEBG1("4 ");
 242         hufts += z + 1;         /* track memory usage */
 243         *t = q + 1;             /* link to list for huft_free() */
 244         *(t = &(q->v.t)) = (struct huft *)NULL;
 245         u[h] = ++q;             /* table starts after link */
 246 
 247 DEBG1("5 ");
 248         /* connect to last table, if there is one */
 249         if (h)
 250         {
 251           x[h] = i;             /* save pattern for backing up */
 252           r.b = (uch)l;         /* bits to dump before this table */
 253           r.e = (uch)(16 + j);  /* bits in this table */
 254           r.v.t = q;            /* pointer to this table */
 255           j = i >> (w - l);     /* (get around Turbo C bug) */
 256           u[h-1][j] = r;        /* connect to last table */
 257         }
 258 DEBG1("6 ");
 259       }
 260 DEBG("h6c ");
 261 
 262       /* set up table entry in r */
 263       r.b = (uch)(k - w);
 264       if (p >= v + n)
 265         r.e = 99;               /* out of values--invalid code */
 266       else if (*p < s)
 267       {
 268         r.e = (uch)(*p < 256 ? 16 : 15);    /* 256 is end-of-block code */
 269         r.v.n = *p++;           /* simple code is just the value */
 270       }
 271       else
 272       {
 273         r.e = (uch)e[*p - s];   /* non-simple--look up in lists */
 274         r.v.n = d[*p++ - s];
 275       }
 276 DEBG("h6d ");
 277 
 278       /* fill code-like entries with r */
 279       f = 1 << (k - w);
 280       for (j = i >> w; j < z; j += f)
 281         q[j] = r;
 282 
 283       /* backwards increment the k-bit code i */
 284       for (j = 1 << (k - 1); i & j; j >>= 1)
 285         i ^= j;
 286       i ^= j;
 287 
 288       /* backup over finished tables */
 289       while ((i & ((1 << w) - 1)) != x[h])
 290       {
 291         h--;                    /* don't need to update q */
 292         w -= l;
 293       }
 294 DEBG("h6e ");
 295     }
 296 DEBG("h6f ");
 297   }
 298 
 299 DEBG("huft7 ");
 300 
 301   /* Return true (1) if we were given an incomplete table */
 302   return y != 0 && g != 1;
 303 }
 304 
 305 
 306 
 307 int huft_free(t)
     /* [previous][next][first][last][top][bottom][index][help] */
 308 struct huft *t;         /* table to free */
 309 /* Free the malloc'ed tables built by huft_build(), which makes a linked
 310    list of the tables it made, with the links in a dummy first entry of
 311    each table. */
 312 {
 313   register struct huft *p, *q;
 314 
 315 
 316   /* Go through linked list, freeing from the malloced (t[-1]) address. */
 317   p = t;
 318   while (p != (struct huft *)NULL)
 319   {
 320     q = (--p)->v.t;
 321     free(p);
 322     p = q;
 323   } 
 324   return 0;
 325 }
 326 
 327 
 328 int inflate_codes(tl, td, bl, bd)
     /* [previous][next][first][last][top][bottom][index][help] */
 329 struct huft *tl, *td;   /* literal/length and distance decoder tables */
 330 int bl, bd;             /* number of bits decoded by tl[] and td[] */
 331 /* inflate (decompress) the codes in a deflated (compressed) block.
 332    Return an error code or zero if it all goes ok. */
 333 {
 334   register unsigned e;  /* table entry flag/number of extra bits */
 335   unsigned n, d;        /* length and index for copy */
 336   unsigned w;           /* current window position */
 337   struct huft *t;       /* pointer to table entry */
 338   unsigned ml, md;      /* masks for bl and bd bits */
 339   register ulg b;       /* bit buffer */
 340   register unsigned k;  /* number of bits in bit buffer */
 341 
 342 
 343   /* make local copies of globals */
 344   b = bb;                       /* initialize bit buffer */
 345   k = bk;
 346   w = wp;                       /* initialize window position */
 347 
 348   /* inflate the coded data */
 349   ml = mask_bits[bl];           /* precompute masks for speed */
 350   md = mask_bits[bd];
 351   for (;;)                      /* do until end of block */
 352   {
 353     NEEDBITS((unsigned)bl)
 354     if ((e = (t = tl + ((unsigned)b & ml))->e) > 16)
 355       do {
 356         if (e == 99)
 357           return 1;
 358         DUMPBITS(t->b)
 359         e -= 16;
 360         NEEDBITS(e)
 361       } while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16);
 362     DUMPBITS(t->b)
 363     if (e == 16)                /* then it's a literal */
 364     {
 365       slide[w++] = (uch)t->v.n;
 366       if (w == WSIZE)
 367       {
 368         flush_output(w);
 369         w = 0;
 370       }
 371     }
 372     else                        /* it's an EOB or a length */
 373     {
 374       /* exit if end of block */
 375       if (e == 15)
 376         break;
 377 
 378       /* get length of block to copy */
 379       NEEDBITS(e)
 380       n = t->v.n + ((unsigned)b & mask_bits[e]);
 381       DUMPBITS(e);
 382 
 383       /* decode distance of block to copy */
 384       NEEDBITS((unsigned)bd)
 385       if ((e = (t = td + ((unsigned)b & md))->e) > 16)
 386         do {
 387           if (e == 99)
 388             return 1;
 389           DUMPBITS(t->b)
 390           e -= 16;
 391           NEEDBITS(e)
 392         } while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16);
 393       DUMPBITS(t->b)
 394       NEEDBITS(e)
 395       d = w - t->v.n - ((unsigned)b & mask_bits[e]);
 396       DUMPBITS(e)
 397 
 398       /* do the copy */
 399       do {
 400         n -= (e = (e = WSIZE - ((d &= WSIZE-1) > w ? d : w)) > n ? n : e);
 401 #if !defined(NOMEMCPY) && !defined(DEBUG)
 402         if (w - d >= e)         /* (this test assumes unsigned comparison) */
 403         {
 404           memcpy(slide + w, slide + d, e);
 405           w += e;
 406           d += e;
 407         }
 408         else                      /* do it slow to avoid memcpy() overlap */
 409 #endif /* !NOMEMCPY */
 410           do {
 411             slide[w++] = slide[d++];
 412           } while (--e);
 413         if (w == WSIZE)
 414         {
 415           flush_output(w);
 416           w = 0;
 417         }
 418       } while (n);
 419     }
 420   }
 421 
 422 
 423   /* restore the globals from the locals */
 424   wp = w;                       /* restore global window pointer */
 425   bb = b;                       /* restore global bit buffer */
 426   bk = k;
 427 
 428   /* done */
 429   return 0;
 430 }
 431 
 432 
 433 
 434 int inflate_stored()
     /* [previous][next][first][last][top][bottom][index][help] */
 435 /* "decompress" an inflated type 0 (stored) block. */
 436 {
 437   unsigned n;           /* number of bytes in block */
 438   unsigned w;           /* current window position */
 439   register ulg b;       /* bit buffer */
 440   register unsigned k;  /* number of bits in bit buffer */
 441 
 442 DEBG("<stor");
 443 
 444   /* make local copies of globals */
 445   b = bb;                       /* initialize bit buffer */
 446   k = bk;
 447   w = wp;                       /* initialize window position */
 448 
 449 
 450   /* go to byte boundary */
 451   n = k & 7;
 452   DUMPBITS(n);
 453 
 454 
 455   /* get the length and its complement */
 456   NEEDBITS(16)
 457   n = ((unsigned)b & 0xffff);
 458   DUMPBITS(16)
 459   NEEDBITS(16)
 460   if (n != (unsigned)((~b) & 0xffff))
 461     return 1;                   /* error in compressed data */
 462   DUMPBITS(16)
 463 
 464 
 465   /* read and output the compressed data */
 466   while (n--)
 467   {
 468     NEEDBITS(8)
 469     slide[w++] = (uch)b;
 470     if (w == WSIZE)
 471     {
 472       flush_output(w);
 473       w = 0;
 474     }
 475     DUMPBITS(8)
 476   }
 477 
 478 
 479   /* restore the globals from the locals */
 480   wp = w;                       /* restore global window pointer */
 481   bb = b;                       /* restore global bit buffer */
 482   bk = k;
 483 
 484   DEBG(">");
 485   return 0;
 486 }
 487 
 488 
 489 
 490 int inflate_fixed()
     /* [previous][next][first][last][top][bottom][index][help] */
 491 /* decompress an inflated type 1 (fixed Huffman codes) block.  We should
 492    either replace this with a custom decoder, or at least precompute the
 493    Huffman tables. */
 494 {
 495   int i;                /* temporary variable */
 496   struct huft *tl;      /* literal/length code table */
 497   struct huft *td;      /* distance code table */
 498   int bl;               /* lookup bits for tl */
 499   int bd;               /* lookup bits for td */
 500   unsigned l[288];      /* length list for huft_build */
 501 
 502 DEBG("<fix");
 503 
 504   /* set up literal table */
 505   for (i = 0; i < 144; i++)
 506     l[i] = 8;
 507   for (; i < 256; i++)
 508     l[i] = 9;
 509   for (; i < 280; i++)
 510     l[i] = 7;
 511   for (; i < 288; i++)          /* make a complete, but wrong code set */
 512     l[i] = 8;
 513   bl = 7;
 514   if ((i = huft_build(l, 288, 257, cplens, cplext, &tl, &bl)) != 0)
 515     return i;
 516 
 517 
 518   /* set up distance table */
 519   for (i = 0; i < 30; i++)      /* make an incomplete code set */
 520     l[i] = 5;
 521   bd = 5;
 522   if ((i = huft_build(l, 30, 0, cpdist, cpdext, &td, &bd)) > 1)
 523   {
 524     huft_free(tl);
 525 
 526     DEBG(">");
 527     return i;
 528   }
 529 
 530 
 531   /* decompress until an end-of-block code */
 532   if (inflate_codes(tl, td, bl, bd))
 533     return 1;
 534 
 535 
 536   /* free the decoding tables, return */
 537   huft_free(tl);
 538   huft_free(td);
 539   return 0;
 540 }
 541 
 542 
 543 
 544 int inflate_dynamic()
     /* [previous][next][first][last][top][bottom][index][help] */
 545 /* decompress an inflated type 2 (dynamic Huffman codes) block. */
 546 {
 547   int i;                /* temporary variables */
 548   unsigned j;
 549   unsigned l;           /* last length */
 550   unsigned m;           /* mask for bit lengths table */
 551   unsigned n;           /* number of lengths to get */
 552   struct huft *tl;      /* literal/length code table */
 553   struct huft *td;      /* distance code table */
 554   int bl;               /* lookup bits for tl */
 555   int bd;               /* lookup bits for td */
 556   unsigned nb;          /* number of bit length codes */
 557   unsigned nl;          /* number of literal/length codes */
 558   unsigned nd;          /* number of distance codes */
 559 #ifdef PKZIP_BUG_WORKAROUND
 560   unsigned ll[288+32];  /* literal/length and distance code lengths */
 561 #else
 562   unsigned ll[286+30];  /* literal/length and distance code lengths */
 563 #endif
 564   register ulg b;       /* bit buffer */
 565   register unsigned k;  /* number of bits in bit buffer */
 566 
 567 DEBG("<dyn");
 568 
 569   /* make local bit buffer */
 570   b = bb;
 571   k = bk;
 572 
 573 
 574   /* read in table lengths */
 575   NEEDBITS(5)
 576   nl = 257 + ((unsigned)b & 0x1f);      /* number of literal/length codes */
 577   DUMPBITS(5)
 578   NEEDBITS(5)
 579   nd = 1 + ((unsigned)b & 0x1f);        /* number of distance codes */
 580   DUMPBITS(5)
 581   NEEDBITS(4)
 582   nb = 4 + ((unsigned)b & 0xf);         /* number of bit length codes */
 583   DUMPBITS(4)
 584 #ifdef PKZIP_BUG_WORKAROUND
 585   if (nl > 288 || nd > 32)
 586 #else
 587   if (nl > 286 || nd > 30)
 588 #endif
 589     return 1;                   /* bad lengths */
 590 
 591 DEBG("dyn1 ");
 592 
 593   /* read in bit-length-code lengths */
 594   for (j = 0; j < nb; j++)
 595   {
 596     NEEDBITS(3)
 597     ll[border[j]] = (unsigned)b & 7;
 598     DUMPBITS(3)
 599   }
 600   for (; j < 19; j++)
 601     ll[border[j]] = 0;
 602 
 603 DEBG("dyn2 ");
 604 
 605   /* build decoding table for trees--single level, 7 bit lookup */
 606   bl = 7;
 607   if ((i = huft_build(ll, 19, 19, NULL, NULL, &tl, &bl)) != 0)
 608   {
 609     if (i == 1)
 610       huft_free(tl);
 611     return i;                   /* incomplete code set */
 612   }
 613 
 614 DEBG("dyn3 ");
 615 
 616   /* read in literal and distance code lengths */
 617   n = nl + nd;
 618   m = mask_bits[bl];
 619   i = l = 0;
 620   while ((unsigned)i < n)
 621   {
 622     NEEDBITS((unsigned)bl)
 623     j = (td = tl + ((unsigned)b & m))->b;
 624     DUMPBITS(j)
 625     j = td->v.n;
 626     if (j < 16)                 /* length of code in bits (0..15) */
 627       ll[i++] = l = j;          /* save last length in l */
 628     else if (j == 16)           /* repeat last length 3 to 6 times */
 629     {
 630       NEEDBITS(2)
 631       j = 3 + ((unsigned)b & 3);
 632       DUMPBITS(2)
 633       if ((unsigned)i + j > n)
 634         return 1;
 635       while (j--)
 636         ll[i++] = l;
 637     }
 638     else if (j == 17)           /* 3 to 10 zero length codes */
 639     {
 640       NEEDBITS(3)
 641       j = 3 + ((unsigned)b & 7);
 642       DUMPBITS(3)
 643       if ((unsigned)i + j > n)
 644         return 1;
 645       while (j--)
 646         ll[i++] = 0;
 647       l = 0;
 648     }
 649     else                        /* j == 18: 11 to 138 zero length codes */
 650     {
 651       NEEDBITS(7)
 652       j = 11 + ((unsigned)b & 0x7f);
 653       DUMPBITS(7)
 654       if ((unsigned)i + j > n)
 655         return 1;
 656       while (j--)
 657         ll[i++] = 0;
 658       l = 0;
 659     }
 660   }
 661 
 662 DEBG("dyn4 ");
 663 
 664   /* free decoding table for trees */
 665   huft_free(tl);
 666 
 667 DEBG("dyn5 ");
 668 
 669   /* restore the global bit buffer */
 670   bb = b;
 671   bk = k;
 672 
 673 DEBG("dyn5a ");
 674 
 675   /* build the decoding tables for literal/length and distance codes */
 676   bl = lbits;
 677   if ((i = huft_build(ll, nl, 257, cplens, cplext, &tl, &bl)) != 0)
 678   {
 679 DEBG("dyn5b ");
 680     if (i == 1) {
 681       error(" incomplete literal tree\n");
 682       huft_free(tl);
 683     }
 684     return i;                   /* incomplete code set */
 685   }
 686 DEBG("dyn5c ");
 687   bd = dbits;
 688   if ((i = huft_build(ll + nl, nd, 0, cpdist, cpdext, &td, &bd)) != 0)
 689   {
 690 DEBG("dyn5d ");
 691     if (i == 1) {
 692       error(" incomplete distance tree\n");
 693 #ifdef PKZIP_BUG_WORKAROUND
 694       i = 0;
 695     }
 696 #else
 697       huft_free(td);
 698     }
 699     huft_free(tl);
 700     return i;                   /* incomplete code set */
 701 #endif
 702   }
 703 
 704 DEBG("dyn6 ");
 705 
 706   /* decompress until an end-of-block code */
 707   if (inflate_codes(tl, td, bl, bd))
 708     return 1;
 709 
 710 DEBG("dyn7 ");
 711 
 712   /* free the decoding tables, return */
 713   huft_free(tl);
 714   huft_free(td);
 715 
 716   DEBG(">");
 717   return 0;
 718 }
 719 
 720 
 721 
 722 int inflate_block(e)
     /* [previous][next][first][last][top][bottom][index][help] */
 723 int *e;                 /* last block flag */
 724 /* decompress an inflated block */
 725 {
 726   unsigned t;           /* block type */
 727   register ulg b;       /* bit buffer */
 728   register unsigned k;  /* number of bits in bit buffer */
 729 
 730   DEBG("<blk");
 731 
 732   /* make local bit buffer */
 733   b = bb;
 734   k = bk;
 735 
 736 
 737   /* read in last block bit */
 738   NEEDBITS(1)
 739   *e = (int)b & 1;
 740   DUMPBITS(1)
 741 
 742 
 743   /* read in block type */
 744   NEEDBITS(2)
 745   t = (unsigned)b & 3;
 746   DUMPBITS(2)
 747 
 748 
 749   /* restore the global bit buffer */
 750   bb = b;
 751   bk = k;
 752 
 753   /* inflate that block type */
 754   if (t == 2)
 755     return inflate_dynamic();
 756   if (t == 0)
 757     return inflate_stored();
 758   if (t == 1)
 759     return inflate_fixed();
 760 
 761   DEBG(">");
 762 
 763   /* bad block type */
 764   return 2;
 765 }
 766 
 767 
 768 
 769 int inflate()
     /* [previous][next][first][last][top][bottom][index][help] */
 770 /* decompress an inflated entry */
 771 {
 772   int e;                /* last block flag */
 773   int r;                /* result code */
 774   unsigned h;           /* maximum struct huft's malloc'ed */
 775 
 776 
 777   /* initialize window, bit buffer */
 778   wp = 0;
 779   bk = 0;
 780   bb = 0;
 781 
 782 
 783   /* decompress until the last block */
 784   h = 0;
 785   do {
 786     hufts = 0;
 787     if ((r = inflate_block(&e)) != 0)
 788       return r;
 789     if (hufts > h)
 790       h = hufts;
 791   } while (!e);
 792 
 793   /* Undo too much lookahead. The next read will be byte aligned so we
 794    * can discard unused bits in the last meaningful byte.
 795    */
 796   while (bk >= 8) {
 797     bk -= 8;
 798     inptr--;
 799   }
 800 
 801   /* flush out slide */
 802   flush_output(wp);
 803 
 804 
 805   /* return success */
 806 #ifdef DEBUG
 807   fprintf(stderr, "<%u> ", h);
 808 #endif /* DEBUG */
 809   return 0;
 810 }

/* [previous][next][first][last][top][bottom][index][help] */