root/zBoot/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         if ((q = (struct huft *)malloc((z + 1)*sizeof(struct huft))) ==
 241             (struct huft *)NULL)
 242         {
 243 DEBG1("31 ");
 244           error("malloc failed\n");
 245           if (h)
 246             huft_free(u[0]);
 247           return 3;             /* not enough memory */
 248         }
 249 DEBG1("4 ");
 250         hufts += z + 1;         /* track memory usage */
 251         *t = q + 1;             /* link to list for huft_free() */
 252         *(t = &(q->v.t)) = (struct huft *)NULL;
 253         u[h] = ++q;             /* table starts after link */
 254 
 255 DEBG1("5 ");
 256         /* connect to last table, if there is one */
 257         if (h)
 258         {
 259           x[h] = i;             /* save pattern for backing up */
 260           r.b = (uch)l;         /* bits to dump before this table */
 261           r.e = (uch)(16 + j);  /* bits in this table */
 262           r.v.t = q;            /* pointer to this table */
 263           j = i >> (w - l);     /* (get around Turbo C bug) */
 264           u[h-1][j] = r;        /* connect to last table */
 265         }
 266 DEBG1("6 ");
 267       }
 268 DEBG("h6c ");
 269 
 270       /* set up table entry in r */
 271       r.b = (uch)(k - w);
 272       if (p >= v + n)
 273         r.e = 99;               /* out of values--invalid code */
 274       else if (*p < s)
 275       {
 276         r.e = (uch)(*p < 256 ? 16 : 15);    /* 256 is end-of-block code */
 277         r.v.n = *p++;           /* simple code is just the value */
 278       }
 279       else
 280       {
 281         r.e = (uch)e[*p - s];   /* non-simple--look up in lists */
 282         r.v.n = d[*p++ - s];
 283       }
 284 DEBG("h6d ");
 285 
 286       /* fill code-like entries with r */
 287       f = 1 << (k - w);
 288       for (j = i >> w; j < z; j += f)
 289         q[j] = r;
 290 
 291       /* backwards increment the k-bit code i */
 292       for (j = 1 << (k - 1); i & j; j >>= 1)
 293         i ^= j;
 294       i ^= j;
 295 
 296       /* backup over finished tables */
 297       while ((i & ((1 << w) - 1)) != x[h])
 298       {
 299         h--;                    /* don't need to update q */
 300         w -= l;
 301       }
 302 DEBG("h6e ");
 303     }
 304 DEBG("h6f ");
 305   }
 306 
 307 DEBG("huft7 ");
 308 
 309   /* Return true (1) if we were given an incomplete table */
 310   return y != 0 && g != 1;
 311 }
 312 
 313 
 314 
 315 int huft_free(t)
     /* [previous][next][first][last][top][bottom][index][help] */
 316 struct huft *t;         /* table to free */
 317 /* Free the malloc'ed tables built by huft_build(), which makes a linked
 318    list of the tables it made, with the links in a dummy first entry of
 319    each table. */
 320 {
 321   register struct huft *p, *q;
 322 
 323 
 324   /* Go through linked list, freeing from the malloced (t[-1]) address. */
 325   p = t;
 326   while (p != (struct huft *)NULL)
 327   {
 328     q = (--p)->v.t;
 329     free(p);
 330     p = q;
 331   } 
 332   return 0;
 333 }
 334 
 335 
 336 int inflate_codes(tl, td, bl, bd)
     /* [previous][next][first][last][top][bottom][index][help] */
 337 struct huft *tl, *td;   /* literal/length and distance decoder tables */
 338 int bl, bd;             /* number of bits decoded by tl[] and td[] */
 339 /* inflate (decompress) the codes in a deflated (compressed) block.
 340    Return an error code or zero if it all goes ok. */
 341 {
 342   register unsigned e;  /* table entry flag/number of extra bits */
 343   unsigned n, d;        /* length and index for copy */
 344   unsigned w;           /* current window position */
 345   struct huft *t;       /* pointer to table entry */
 346   unsigned ml, md;      /* masks for bl and bd bits */
 347   register ulg b;       /* bit buffer */
 348   register unsigned k;  /* number of bits in bit buffer */
 349 
 350 
 351   /* make local copies of globals */
 352   b = bb;                       /* initialize bit buffer */
 353   k = bk;
 354   w = wp;                       /* initialize window position */
 355 
 356   /* inflate the coded data */
 357   ml = mask_bits[bl];           /* precompute masks for speed */
 358   md = mask_bits[bd];
 359   for (;;)                      /* do until end of block */
 360   {
 361     NEEDBITS((unsigned)bl)
 362     if ((e = (t = tl + ((unsigned)b & ml))->e) > 16)
 363       do {
 364         if (e == 99)
 365           return 1;
 366         DUMPBITS(t->b)
 367         e -= 16;
 368         NEEDBITS(e)
 369       } while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16);
 370     DUMPBITS(t->b)
 371     if (e == 16)                /* then it's a literal */
 372     {
 373       slide[w++] = (uch)t->v.n;
 374       if (w == WSIZE)
 375       {
 376         flush_output(w);
 377         w = 0;
 378       }
 379     }
 380     else                        /* it's an EOB or a length */
 381     {
 382       /* exit if end of block */
 383       if (e == 15)
 384         break;
 385 
 386       /* get length of block to copy */
 387       NEEDBITS(e)
 388       n = t->v.n + ((unsigned)b & mask_bits[e]);
 389       DUMPBITS(e);
 390 
 391       /* decode distance of block to copy */
 392       NEEDBITS((unsigned)bd)
 393       if ((e = (t = td + ((unsigned)b & md))->e) > 16)
 394         do {
 395           if (e == 99)
 396             return 1;
 397           DUMPBITS(t->b)
 398           e -= 16;
 399           NEEDBITS(e)
 400         } while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16);
 401       DUMPBITS(t->b)
 402       NEEDBITS(e)
 403       d = w - t->v.n - ((unsigned)b & mask_bits[e]);
 404       DUMPBITS(e)
 405 
 406       /* do the copy */
 407       do {
 408         n -= (e = (e = WSIZE - ((d &= WSIZE-1) > w ? d : w)) > n ? n : e);
 409 #if !defined(NOMEMCPY) && !defined(DEBUG)
 410         if (w - d >= e)         /* (this test assumes unsigned comparison) */
 411         {
 412           memcpy(slide + w, slide + d, e);
 413           w += e;
 414           d += e;
 415         }
 416         else                      /* do it slow to avoid memcpy() overlap */
 417 #endif /* !NOMEMCPY */
 418           do {
 419             slide[w++] = slide[d++];
 420           } while (--e);
 421         if (w == WSIZE)
 422         {
 423           flush_output(w);
 424           w = 0;
 425         }
 426       } while (n);
 427     }
 428   }
 429 
 430 
 431   /* restore the globals from the locals */
 432   wp = w;                       /* restore global window pointer */
 433   bb = b;                       /* restore global bit buffer */
 434   bk = k;
 435 
 436   /* done */
 437   return 0;
 438 }
 439 
 440 
 441 
 442 int inflate_stored()
     /* [previous][next][first][last][top][bottom][index][help] */
 443 /* "decompress" an inflated type 0 (stored) block. */
 444 {
 445   unsigned n;           /* number of bytes in block */
 446   unsigned w;           /* current window position */
 447   register ulg b;       /* bit buffer */
 448   register unsigned k;  /* number of bits in bit buffer */
 449 
 450 DEBG("<stor");
 451 
 452   /* make local copies of globals */
 453   b = bb;                       /* initialize bit buffer */
 454   k = bk;
 455   w = wp;                       /* initialize window position */
 456 
 457 
 458   /* go to byte boundary */
 459   n = k & 7;
 460   DUMPBITS(n);
 461 
 462 
 463   /* get the length and its complement */
 464   NEEDBITS(16)
 465   n = ((unsigned)b & 0xffff);
 466   DUMPBITS(16)
 467   NEEDBITS(16)
 468   if (n != (unsigned)((~b) & 0xffff))
 469     return 1;                   /* error in compressed data */
 470   DUMPBITS(16)
 471 
 472 
 473   /* read and output the compressed data */
 474   while (n--)
 475   {
 476     NEEDBITS(8)
 477     slide[w++] = (uch)b;
 478     if (w == WSIZE)
 479     {
 480       flush_output(w);
 481       w = 0;
 482     }
 483     DUMPBITS(8)
 484   }
 485 
 486 
 487   /* restore the globals from the locals */
 488   wp = w;                       /* restore global window pointer */
 489   bb = b;                       /* restore global bit buffer */
 490   bk = k;
 491 
 492   DEBG(">");
 493   return 0;
 494 }
 495 
 496 
 497 
 498 int inflate_fixed()
     /* [previous][next][first][last][top][bottom][index][help] */
 499 /* decompress an inflated type 1 (fixed Huffman codes) block.  We should
 500    either replace this with a custom decoder, or at least precompute the
 501    Huffman tables. */
 502 {
 503   int i;                /* temporary variable */
 504   struct huft *tl;      /* literal/length code table */
 505   struct huft *td;      /* distance code table */
 506   int bl;               /* lookup bits for tl */
 507   int bd;               /* lookup bits for td */
 508   unsigned l[288];      /* length list for huft_build */
 509 
 510 DEBG("<fix");
 511 
 512   /* set up literal table */
 513   for (i = 0; i < 144; i++)
 514     l[i] = 8;
 515   for (; i < 256; i++)
 516     l[i] = 9;
 517   for (; i < 280; i++)
 518     l[i] = 7;
 519   for (; i < 288; i++)          /* make a complete, but wrong code set */
 520     l[i] = 8;
 521   bl = 7;
 522   if ((i = huft_build(l, 288, 257, cplens, cplext, &tl, &bl)) != 0)
 523     return i;
 524 
 525 
 526   /* set up distance table */
 527   for (i = 0; i < 30; i++)      /* make an incomplete code set */
 528     l[i] = 5;
 529   bd = 5;
 530   if ((i = huft_build(l, 30, 0, cpdist, cpdext, &td, &bd)) > 1)
 531   {
 532     huft_free(tl);
 533 
 534     DEBG(">");
 535     return i;
 536   }
 537 
 538 
 539   /* decompress until an end-of-block code */
 540   if (inflate_codes(tl, td, bl, bd))
 541     return 1;
 542 
 543 
 544   /* free the decoding tables, return */
 545   huft_free(tl);
 546   huft_free(td);
 547   return 0;
 548 }
 549 
 550 
 551 
 552 int inflate_dynamic()
     /* [previous][next][first][last][top][bottom][index][help] */
 553 /* decompress an inflated type 2 (dynamic Huffman codes) block. */
 554 {
 555   int i;                /* temporary variables */
 556   unsigned j;
 557   unsigned l;           /* last length */
 558   unsigned m;           /* mask for bit lengths table */
 559   unsigned n;           /* number of lengths to get */
 560   struct huft *tl;      /* literal/length code table */
 561   struct huft *td;      /* distance code table */
 562   int bl;               /* lookup bits for tl */
 563   int bd;               /* lookup bits for td */
 564   unsigned nb;          /* number of bit length codes */
 565   unsigned nl;          /* number of literal/length codes */
 566   unsigned nd;          /* number of distance codes */
 567 #ifdef PKZIP_BUG_WORKAROUND
 568   unsigned ll[288+32];  /* literal/length and distance code lengths */
 569 #else
 570   unsigned ll[286+30];  /* literal/length and distance code lengths */
 571 #endif
 572   register ulg b;       /* bit buffer */
 573   register unsigned k;  /* number of bits in bit buffer */
 574 
 575 DEBG("<dyn");
 576 
 577   /* make local bit buffer */
 578   b = bb;
 579   k = bk;
 580 
 581 
 582   /* read in table lengths */
 583   NEEDBITS(5)
 584   nl = 257 + ((unsigned)b & 0x1f);      /* number of literal/length codes */
 585   DUMPBITS(5)
 586   NEEDBITS(5)
 587   nd = 1 + ((unsigned)b & 0x1f);        /* number of distance codes */
 588   DUMPBITS(5)
 589   NEEDBITS(4)
 590   nb = 4 + ((unsigned)b & 0xf);         /* number of bit length codes */
 591   DUMPBITS(4)
 592 #ifdef PKZIP_BUG_WORKAROUND
 593   if (nl > 288 || nd > 32)
 594 #else
 595   if (nl > 286 || nd > 30)
 596 #endif
 597     return 1;                   /* bad lengths */
 598 
 599 DEBG("dyn1 ");
 600 
 601   /* read in bit-length-code lengths */
 602   for (j = 0; j < nb; j++)
 603   {
 604     NEEDBITS(3)
 605     ll[border[j]] = (unsigned)b & 7;
 606     DUMPBITS(3)
 607   }
 608   for (; j < 19; j++)
 609     ll[border[j]] = 0;
 610 
 611 DEBG("dyn2 ");
 612 
 613   /* build decoding table for trees--single level, 7 bit lookup */
 614   bl = 7;
 615   if ((i = huft_build(ll, 19, 19, NULL, NULL, &tl, &bl)) != 0)
 616   {
 617     if (i == 1)
 618       huft_free(tl);
 619     return i;                   /* incomplete code set */
 620   }
 621 
 622 DEBG("dyn3 ");
 623 
 624   /* read in literal and distance code lengths */
 625   n = nl + nd;
 626   m = mask_bits[bl];
 627   i = l = 0;
 628   while ((unsigned)i < n)
 629   {
 630     NEEDBITS((unsigned)bl)
 631     j = (td = tl + ((unsigned)b & m))->b;
 632     DUMPBITS(j)
 633     j = td->v.n;
 634     if (j < 16)                 /* length of code in bits (0..15) */
 635       ll[i++] = l = j;          /* save last length in l */
 636     else if (j == 16)           /* repeat last length 3 to 6 times */
 637     {
 638       NEEDBITS(2)
 639       j = 3 + ((unsigned)b & 3);
 640       DUMPBITS(2)
 641       if ((unsigned)i + j > n)
 642         return 1;
 643       while (j--)
 644         ll[i++] = l;
 645     }
 646     else if (j == 17)           /* 3 to 10 zero length codes */
 647     {
 648       NEEDBITS(3)
 649       j = 3 + ((unsigned)b & 7);
 650       DUMPBITS(3)
 651       if ((unsigned)i + j > n)
 652         return 1;
 653       while (j--)
 654         ll[i++] = 0;
 655       l = 0;
 656     }
 657     else                        /* j == 18: 11 to 138 zero length codes */
 658     {
 659       NEEDBITS(7)
 660       j = 11 + ((unsigned)b & 0x7f);
 661       DUMPBITS(7)
 662       if ((unsigned)i + j > n)
 663         return 1;
 664       while (j--)
 665         ll[i++] = 0;
 666       l = 0;
 667     }
 668   }
 669 
 670 DEBG("dyn4 ");
 671 
 672   /* free decoding table for trees */
 673   huft_free(tl);
 674 
 675 DEBG("dyn5 ");
 676 
 677   /* restore the global bit buffer */
 678   bb = b;
 679   bk = k;
 680 
 681 DEBG("dyn5a ");
 682 
 683   /* build the decoding tables for literal/length and distance codes */
 684   bl = lbits;
 685   if ((i = huft_build(ll, nl, 257, cplens, cplext, &tl, &bl)) != 0)
 686   {
 687 DEBG("dyn5b ");
 688     if (i == 1) {
 689       error(" incomplete literal tree\n");
 690       huft_free(tl);
 691     }
 692     return i;                   /* incomplete code set */
 693   }
 694 DEBG("dyn5c ");
 695   bd = dbits;
 696   if ((i = huft_build(ll + nl, nd, 0, cpdist, cpdext, &td, &bd)) != 0)
 697   {
 698 DEBG("dyn5d ");
 699     if (i == 1) {
 700       error(" incomplete distance tree\n");
 701 #ifdef PKZIP_BUG_WORKAROUND
 702       i = 0;
 703     }
 704 #else
 705       huft_free(td);
 706     }
 707     huft_free(tl);
 708     return i;                   /* incomplete code set */
 709 #endif
 710   }
 711 
 712 DEBG("dyn6 ");
 713 
 714   /* decompress until an end-of-block code */
 715   if (inflate_codes(tl, td, bl, bd))
 716     return 1;
 717 
 718 DEBG("dyn7 ");
 719 
 720   /* free the decoding tables, return */
 721   huft_free(tl);
 722   huft_free(td);
 723 
 724   DEBG(">");
 725   return 0;
 726 }
 727 
 728 
 729 
 730 int inflate_block(e)
     /* [previous][next][first][last][top][bottom][index][help] */
 731 int *e;                 /* last block flag */
 732 /* decompress an inflated block */
 733 {
 734   unsigned t;           /* block type */
 735   register ulg b;       /* bit buffer */
 736   register unsigned k;  /* number of bits in bit buffer */
 737 
 738   DEBG("<blk");
 739 
 740   /* make local bit buffer */
 741   b = bb;
 742   k = bk;
 743 
 744 
 745   /* read in last block bit */
 746   NEEDBITS(1)
 747   *e = (int)b & 1;
 748   DUMPBITS(1)
 749 
 750 
 751   /* read in block type */
 752   NEEDBITS(2)
 753   t = (unsigned)b & 3;
 754   DUMPBITS(2)
 755 
 756 
 757   /* restore the global bit buffer */
 758   bb = b;
 759   bk = k;
 760 
 761   /* inflate that block type */
 762   if (t == 2)
 763     return inflate_dynamic();
 764   if (t == 0)
 765     return inflate_stored();
 766   if (t == 1)
 767     return inflate_fixed();
 768 
 769   DEBG(">");
 770 
 771   /* bad block type */
 772   return 2;
 773 }
 774 
 775 
 776 
 777 int inflate()
     /* [previous][next][first][last][top][bottom][index][help] */
 778 /* decompress an inflated entry */
 779 {
 780   int e;                /* last block flag */
 781   int r;                /* result code */
 782   unsigned h;           /* maximum struct huft's malloc'ed */
 783 
 784 
 785   /* initialize window, bit buffer */
 786   wp = 0;
 787   bk = 0;
 788   bb = 0;
 789 
 790 
 791   /* decompress until the last block */
 792   h = 0;
 793   do {
 794     hufts = 0;
 795     if ((r = inflate_block(&e)) != 0)
 796       return r;
 797     if (hufts > h)
 798       h = hufts;
 799   } while (!e);
 800 
 801   /* Undo too much lookahead. The next read will be byte aligned so we
 802    * can discard unused bits in the last meaningful byte.
 803    */
 804   while (bk >= 8) {
 805     bk -= 8;
 806     inptr--;
 807   }
 808 
 809   /* flush out slide */
 810   flush_output(wp);
 811 
 812 
 813   /* return success */
 814 #ifdef DEBUG
 815   fprintf(stderr, "<%u> ", h);
 816 #endif /* DEBUG */
 817   return 0;
 818 }

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