archival/libunarchive/decompress_unzip.c

   1 /* vi: set sw=4 ts=4: */
   2 /*
   3  * gunzip implementation for busybox
   4  *
   5  * Based on GNU gzip v1.2.4 Copyright (C) 1992-1993 Jean-loup Gailly.
   6  *
   7  * Originally adjusted for busybox by Sven Rudolph <sr1@inf.tu-dresden.de>
   8  * based on gzip sources
   9  *
  10  * Adjusted further by Erik Andersen <andersen@codepoet.org> to support
  11  * files as well as stdin/stdout, and to generally behave itself wrt
  12  * command line handling.
  13  *
  14  * General cleanup to better adhere to the style guide and make use of standard
  15  * busybox functions by Glenn McGrath <bug1@iinet.net.au>
  16  *
  17  * read_gz interface + associated hacking by Laurence Anderson
  18  *
  19  * Fixed huft_build() so decoding end-of-block code does not grab more bits
  20  * than necessary (this is required by unzip applet), added inflate_cleanup()
  21  * to free leaked bytebuffer memory (used in unzip.c), and some minor style
  22  * guide cleanups by Ed Clark
  23  *
  24  * gzip (GNU zip) -- compress files with zip algorithm and 'compress' interface
  25  * Copyright (C) 1992-1993 Jean-loup Gailly
  26  * The unzip code was written and put in the public domain by Mark Adler.
  27  * Portions of the lzw code are derived from the public domain 'compress'
  28  * written by Spencer Thomas, Joe Orost, James Woods, Jim McKie, Steve Davies,
  29  * Ken Turkowski, Dave Mack and Peter Jannesen.
  30  *
  31  * See the file algorithm.doc for the compression algorithms and file formats.
  32  *
  33  * Licensed under GPLv2 or later, see file LICENSE in this tarball for details.
  34  */
  35
  36 #include "libbb.h"
  37 #include "unarchive.h"
  38
  39 typedef struct huft_s {
  40         unsigned char e;        /* number of extra bits or operation */
  41         unsigned char b;        /* number of bits in this code or subcode */
  42         union {
  43                 unsigned short n;       /* literal, length base, or distance base */
  44                 struct huft_s *t;       /* pointer to next level of table */
  45         } v;
  46 } huft_t;
  47
  48 static int gunzip_src_fd;
  49 unsigned int gunzip_bytes_out;  /* number of output bytes */
  50 static unsigned int gunzip_outbuf_count;        /* bytes in output buffer */
  51
  52 /* gunzip_window size--must be a power of two, and
  53  *  at least 32K for zip's deflate method */
  54 enum { gunzip_wsize = 0x8000 };
  55 static unsigned char *gunzip_window;
  56
  57 static uint32_t *gunzip_crc_table;
  58 uint32_t gunzip_crc;
  59
  60 /* If BMAX needs to be larger than 16, then h and x[] should be ulg. */
  61 #define BMAX 16 /* maximum bit length of any code (16 for explode) */
  62 #define N_MAX 288       /* maximum number of codes in any set */
  63
  64 /* bitbuffer */
  65 static unsigned int gunzip_bb;  /* bit buffer */
  66 static unsigned char gunzip_bk; /* bits in bit buffer */
  67
  68 /* These control the size of the bytebuffer */
  69 static unsigned int bytebuffer_max = 0x8000;
  70 static unsigned char *bytebuffer = NULL;
  71 static unsigned int bytebuffer_offset = 0;
  72 static unsigned int bytebuffer_size = 0;
  73
  74 static const unsigned short mask_bits[] = {
  75         0x0000, 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
  76         0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
  77 };
  78
  79 /* Copy lengths for literal codes 257..285 */
  80 static const unsigned short cplens[] = {
  81         3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59,
  82         67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0
  83 };
  84
  85 /* note: see note #13 above about the 258 in this list. */
  86 /* Extra bits for literal codes 257..285 */
  87 static const unsigned char cplext[] = {
  88         0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5,
  89         5, 5, 5, 0, 99, 99
  90 };                                              /* 99==invalid */
  91
  92 /* Copy offsets for distance codes 0..29 */
  93 static const unsigned short cpdist[] = {
  94         1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513,
  95         769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577
  96 };
  97
  98 /* Extra bits for distance codes */
  99 static const unsigned char cpdext[] = {
 100         0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10,
 101         11, 11, 12, 12, 13, 13
 102 };
 103
 104 /* Tables for deflate from PKZIP's appnote.txt. */
 105 /* Order of the bit length code lengths */
 106 static const unsigned char border[] = {
 107         16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
 108 };
 109
 110 static unsigned int fill_bitbuffer(unsigned int bitbuffer, unsigned int *current, const unsigned int required)
 111 {
 112         while (*current < required) {
 113                 if (bytebuffer_offset >= bytebuffer_size) {
 114                         /* Leave the first 4 bytes empty so we can always unwind the bitbuffer
 115                          * to the front of the bytebuffer, leave 4 bytes free at end of tail
 116                          * so we can easily top up buffer in check_trailer_gzip() */
 117                         if (1 > (bytebuffer_size = safe_read(gunzip_src_fd, &bytebuffer[4], bytebuffer_max - 8)))
 118                                 bb_error_msg_and_die("unexpected end of file");
 119                         bytebuffer_size += 4;
 120                         bytebuffer_offset = 4;
 121                 }
 122                 bitbuffer |= ((unsigned int) bytebuffer[bytebuffer_offset]) << *current;
 123                 bytebuffer_offset++;
 124                 *current += 8;
 125         }
 126         return(bitbuffer);
 127 }
 128
 129 /*
 130  * Free the malloc'ed tables built by huft_build(), which makes a linked
 131  * list of the tables it made, with the links in a dummy first entry of
 132  * each table.
 133  * t: table to free
 134  */
 135 static int huft_free(huft_t * t)
 136 {
 137         huft_t *p;
 138         huft_t *q;
 139
 140         /* Go through linked list, freeing from the malloced (t[-1]) address. */
 141         p = t;
 142         while (p != (huft_t *) NULL) {
 143                 q = (--p)->v.t;
 144                 free((char *) p);
 145                 p = q;
 146         }
 147         return 0;
 148 }
 149
 150 /* Given a list of code lengths and a maximum table size, make a set of
 151  * tables to decode that set of codes.  Return zero on success, one if
 152  * the given code set is incomplete (the tables are still built in this
 153  * case), two if the input is invalid (all zero length codes or an
 154  * oversubscribed set of lengths), and three if not enough memory.
 155  *
 156  * b:   code lengths in bits (all assumed <= BMAX)
 157  * n:   number of codes (assumed <= N_MAX)
 158  * s:   number of simple-valued codes (0..s-1)
 159  * d:   list of base values for non-simple codes
 160  * e:   list of extra bits for non-simple codes
 161  * t:   result: starting table
 162  * m:   maximum lookup bits, returns actual
 163  */
 164 static
 165 int huft_build(unsigned int *b, const unsigned int n,
 166                            const unsigned int s, const unsigned short *d,
 167                            const unsigned char *e, huft_t ** t, unsigned int *m)
 168 {
 169         unsigned a;                             /* counter for codes of length k */
 170         unsigned c[BMAX + 1];   /* bit length count table */
 171         unsigned eob_len;               /* length of end-of-block code (value 256) */
 172         unsigned f;                             /* i repeats in table every f entries */
 173         int g;                                  /* maximum code length */
 174         int htl;                                /* table level */
 175         unsigned i;                             /* counter, current code */
 176         unsigned j;                             /* counter */
 177         int k;                                  /* number of bits in current code */
 178         unsigned *p;                    /* pointer into c[], b[], or v[] */
 179         huft_t *q;                              /* points to current table */
 180         huft_t r;                               /* table entry for structure assignment */
 181         huft_t *u[BMAX];                /* table stack */
 182         unsigned v[N_MAX];              /* values in order of bit length */
 183         int ws[BMAX+1];                 /* bits decoded stack */
 184         int w;                                  /* bits decoded */
 185         unsigned x[BMAX + 1];   /* bit offsets, then code stack */
 186         unsigned *xp;                   /* pointer into x */
 187         int y;                                  /* number of dummy codes added */
 188         unsigned z;                             /* number of entries in current table */
 189
 190         /* Length of EOB code, if any */
 191         eob_len = n > 256 ? b[256] : BMAX;
 192
 193         /* Generate counts for each bit length */
 194         memset((void *)c, 0, sizeof(c));
 195         p = b;
 196         i = n;
 197         do {
 198                 c[*p]++; /* assume all entries <= BMAX */
 199                 p++; /* Can't combine with above line (Solaris bug) */
 200         } while (--i);
 201         if (c[0] == n) { /* null input--all zero length codes */
 202                 *t = (huft_t *) NULL;
 203                 *m = 0;
 204                 return 2;
 205         }
 206
 207         /* Find minimum and maximum length, bound *m by those */
 208         for (j = 1; (c[j] == 0) && (j <= BMAX); j++);
 209         k = j; /* minimum code length */
 210         for (i = BMAX; (c[i] == 0) && i; i--);
 211         g = i; /* maximum code length */
 212         *m = (*m < j) ? j : ((*m > i) ? i : *m);
 213
 214         /* Adjust last length count to fill out codes, if needed */
 215         for (y = 1 << j; j < i; j++, y <<= 1) {
 216                 if ((y -= c[j]) < 0) {
 217                         return 2; /* bad input: more codes than bits */
 218                 }
 219         }
 220         if ((y -= c[i]) < 0) {
 221                 return 2;
 222         }
 223         c[i] += y;
 224
 225         /* Generate starting offsets into the value table for each length */
 226         x[1] = j = 0;
 227         p = c + 1;
 228         xp = x + 2;
 229         while (--i) { /* note that i == g from above */
 230                 *xp++ = (j += *p++);
 231         }
 232
 233         /* Make a table of values in order of bit lengths */
 234         p = b;
 235         i = 0;
 236         do {
 237                 if ((j = *p++) != 0) {
 238                         v[x[j]++] = i;
 239                 }
 240         } while (++i < n);
 241
 242         /* Generate the Huffman codes and for each, make the table entries */
 243         x[0] = i = 0;                   /* first Huffman code is zero */
 244         p = v;                                  /* grab values in bit order */
 245         htl = -1;                               /* no tables yet--level -1 */
 246         w = ws[0] = 0;                  /* bits decoded */
 247         u[0] = (huft_t *) NULL; /* just to keep compilers happy */
 248         q = (huft_t *) NULL;    /* ditto */
 249         z = 0;                                  /* ditto */
 250
 251         /* go through the bit lengths (k already is bits in shortest code) */
 252         for (; k <= g; k++) {
 253                 a = c[k];
 254                 while (a--) {
 255                         /* here i is the Huffman code of length k bits for value *p */
 256                         /* make tables up to required level */
 257                         while (k > ws[htl + 1]) {
 258                                 w = ws[++htl];
 259
 260                                 /* compute minimum size table less than or equal to *m bits */
 261                                 z = (z = g - w) > *m ? *m : z; /* upper limit on table size */
 262                                 if ((f = 1 << (j = k - w)) > a + 1) { /* try a k-w bit table */
 263                                         /* too few codes for k-w bit table */
 264                                         f -= a + 1; /* deduct codes from patterns left */
 265                                         xp = c + k;
 266                                         while (++j < z) { /* try smaller tables up to z bits */
 267                                                 if ((f <<= 1) <= *++xp) {
 268                                                         break; /* enough codes to use up j bits */
 269                                                 }
 270                                                 f -= *xp; /* else deduct codes from patterns */
 271                                         }
 272                                 }
 273                                 j = (w + j > eob_len && w < eob_len) ? eob_len - w : j; /* make EOB code end at table */
 274                                 z = 1 << j;     /* table entries for j-bit table */
 275                                 ws[htl+1] = w + j;      /* set bits decoded in stack */
 276
 277                                 /* allocate and link in new table */
 278                                 q = (huft_t *) xzalloc((z + 1) * sizeof(huft_t));
 279                                 *t = q + 1;     /* link to list for huft_free() */
 280                                 t = &(q->v.t);
 281                                 u[htl] = ++q;   /* table starts after link */
 282
 283                                 /* connect to last table, if there is one */
 284                                 if (htl) {
 285                                         x[htl] = i; /* save pattern for backing up */
 286                                         r.b = (unsigned char) (w - ws[htl - 1]); /* bits to dump before this table */
 287                                         r.e = (unsigned char) (16 + j); /* bits in this table */
 288                                         r.v.t = q; /* pointer to this table */
 289                                         j = (i & ((1 << w) - 1)) >> ws[htl - 1];
 290                                         u[htl - 1][j] = r; /* connect to last table */
 291                                 }
 292                         }
 293
 294                         /* set up table entry in r */
 295                         r.b = (unsigned char) (k - w);
 296                         if (p >= v + n) {
 297                                 r.e = 99; /* out of values--invalid code */
 298                         } else if (*p < s) {
 299                                 r.e = (unsigned char) (*p < 256 ? 16 : 15);     /* 256 is EOB code */
 300                                 r.v.n = (unsigned short) (*p++); /* simple code is just the value */
 301                         } else {
 302                                 r.e = (unsigned char) e[*p - s]; /* non-simple--look up in lists */
 303                                 r.v.n = d[*p++ - s];
 304                         }
 305
 306                         /* fill code-like entries with r */
 307                         f = 1 << (k - w);
 308                         for (j = i >> w; j < z; j += f) {
 309                                 q[j] = r;
 310                         }
 311
 312                         /* backwards increment the k-bit code i */
 313                         for (j = 1 << (k - 1); i & j; j >>= 1) {
 314                                 i ^= j;
 315                         }
 316                         i ^= j;
 317
 318                         /* backup over finished tables */
 319                         while ((i & ((1 << w) - 1)) != x[htl]) {
 320                                 w = ws[--htl];
 321                         }
 322                 }
 323         }
 324
 325         /* return actual size of base table */
 326         *m = ws[1];
 327
 328         /* Return true (1) if we were given an incomplete table */
 329         return y != 0 && g != 1;
 330 }
 331
 332 /*
 333  * inflate (decompress) the codes in a deflated (compressed) block.
 334  * Return an error code or zero if it all goes ok.
 335  *
 336  * tl, td: literal/length and distance decoder tables
 337  * bl, bd: number of bits decoded by tl[] and td[]
 338  */
 339 static int inflate_codes(huft_t * my_tl, huft_t * my_td, const unsigned int my_bl, const unsigned int my_bd, int setup)
 340 {
 341         static unsigned int e;  /* table entry flag/number of extra bits */
 342         static unsigned int n, d;       /* length and index for copy */
 343         static unsigned int w;  /* current gunzip_window position */
 344         static huft_t *t;                       /* pointer to table entry */
 345         static unsigned int ml, md;     /* masks for bl and bd bits */
 346         static unsigned int b;  /* bit buffer */
 347         static unsigned int k;                  /* number of bits in bit buffer */
 348         static huft_t *tl, *td;
 349         static unsigned int bl, bd;
 350         static int resumeCopy = 0;
 351
 352         if (setup) { // 1st time we are called, copy in variables
 353                 tl = my_tl;
 354                 td = my_td;
 355                 bl = my_bl;
 356                 bd = my_bd;
 357                 /* make local copies of globals */
 358                 b = gunzip_bb;                          /* initialize bit buffer */
 359                 k = gunzip_bk;
 360                 w = gunzip_outbuf_count;                        /* initialize gunzip_window position */
 361
 362                 /* inflate the coded data */
 363                 ml = mask_bits[bl];     /* precompute masks for speed */
 364                 md = mask_bits[bd];
 365                 return 0; // Don't actually do anything the first time
 366         }
 367
 368         if (resumeCopy) goto do_copy;
 369
 370         while (1) {                     /* do until end of block */
 371                 b = fill_bitbuffer(b, &k, bl);
 372                 if ((e = (t = tl + ((unsigned) b & ml))->e) > 16)
 373                         do {
 374                                 if (e == 99) {
 375                                         bb_error_msg_and_die("inflate_codes error 1");
 376                                 }
 377                                 b >>= t->b;
 378                                 k -= t->b;
 379                                 e -= 16;
 380                                 b = fill_bitbuffer(b, &k, e);
 381                         } while ((e =
 382                                           (t = t->v.t + ((unsigned) b & mask_bits[e]))->e) > 16);
 383                 b >>= t->b;
 384                 k -= t->b;
 385                 if (e == 16) {  /* then it's a literal */
 386                         gunzip_window[w++] = (unsigned char) t->v.n;
 387                         if (w == gunzip_wsize) {
 388                                 gunzip_outbuf_count = (w);
 389                                 //flush_gunzip_window();
 390                                 w = 0;
 391                                 return 1; // We have a block to read
 392                         }
 393                 } else {                /* it's an EOB or a length */
 394
 395                         /* exit if end of block */
 396                         if (e == 15) {
 397                                 break;
 398                         }
 399
 400                         /* get length of block to copy */
 401                         b = fill_bitbuffer(b, &k, e);
 402                         n = t->v.n + ((unsigned) b & mask_bits[e]);
 403                         b >>= e;
 404                         k -= e;
 405
 406                         /* decode distance of block to copy */
 407                         b = fill_bitbuffer(b, &k, bd);
 408                         if ((e = (t = td + ((unsigned) b & md))->e) > 16)
 409                                 do {
 410                                         if (e == 99)
 411                                                 bb_error_msg_and_die("inflate_codes error 2");
 412                                         b >>= t->b;
 413                                         k -= t->b;
 414                                         e -= 16;
 415                                         b = fill_bitbuffer(b, &k, e);
 416                                 } while ((e =
 417                                                   (t =
 418                                                    t->v.t + ((unsigned) b & mask_bits[e]))->e) > 16);
 419                         b >>= t->b;
 420                         k -= t->b;
 421                         b = fill_bitbuffer(b, &k, e);
 422                         d = w - t->v.n - ((unsigned) b & mask_bits[e]);
 423                         b >>= e;
 424                         k -= e;
 425
 426                         /* do the copy */
 427 do_copy:                do {
 428                                 n -= (e =
 429                                           (e =
 430                                            gunzip_wsize - ((d &= gunzip_wsize - 1) > w ? d : w)) > n ? n : e);
 431                            /* copy to new buffer to prevent possible overwrite */
 432                                 if (w - d >= e) {       /* (this test assumes unsigned comparison) */
 433                                         memcpy(gunzip_window + w, gunzip_window + d, e);
 434                                         w += e;
 435                                         d += e;
 436                                 } else {
 437                                    /* do it slow to avoid memcpy() overlap */
 438                                    /* !NOMEMCPY */
 439                                         do {
 440                                                 gunzip_window[w++] = gunzip_window[d++];
 441                                         } while (--e);
 442                                 }
 443                                 if (w == gunzip_wsize) {
 444                                         gunzip_outbuf_count = (w);
 445                                         if (n) resumeCopy = 1;
 446                                         else resumeCopy = 0;
 447                                         //flush_gunzip_window();
 448                                         w = 0;
 449                                         return 1;
 450                                 }
 451                         } while (n);
 452                         resumeCopy = 0;
 453                 }
 454         }
 455
 456         /* restore the globals from the locals */
 457         gunzip_outbuf_count = w;                        /* restore global gunzip_window pointer */
 458         gunzip_bb = b;                          /* restore global bit buffer */
 459         gunzip_bk = k;
 460
 461         /* normally just after call to inflate_codes, but save code by putting it here */
 462         /* free the decoding tables, return */
 463         huft_free(tl);
 464         huft_free(td);
 465
 466         /* done */
 467         return 0;
 468 }
 469
 470 static int inflate_stored(int my_n, int my_b_stored, int my_k_stored, int setup)
 471 {
 472         static unsigned int n, b_stored, k_stored, w;
 473         if (setup) {
 474                 n = my_n;
 475                 b_stored = my_b_stored;
 476                 k_stored = my_k_stored;
 477                 w = gunzip_outbuf_count;                /* initialize gunzip_window position */
 478                 return 0; // Don't do anything first time
 479         }
 480
 481         /* read and output the compressed data */
 482         while (n--) {
 483                 b_stored = fill_bitbuffer(b_stored, &k_stored, 8);
 484                 gunzip_window[w++] = (unsigned char) b_stored;
 485                 if (w == gunzip_wsize) {
 486                         gunzip_outbuf_count = (w);
 487                         //flush_gunzip_window();
 488                         w = 0;
 489                         b_stored >>= 8;
 490                         k_stored -= 8;
 491                         return 1; // We have a block
 492                 }
 493                 b_stored >>= 8;
 494                 k_stored -= 8;
 495         }
 496
 497         /* restore the globals from the locals */
 498         gunzip_outbuf_count = w;                /* restore global gunzip_window pointer */
 499         gunzip_bb = b_stored;   /* restore global bit buffer */
 500         gunzip_bk = k_stored;
 501         return 0; // Finished
 502 }
 503
 504 /*
 505  * decompress an inflated block
 506  * e: last block flag
 507  *
 508  * GLOBAL VARIABLES: bb, kk,
 509  */
 510  // Return values: -1 = inflate_stored, -2 = inflate_codes
 511 static int inflate_block(int *e)
 512 {
 513         unsigned t;                     /* block type */
 514         unsigned int b; /* bit buffer */
 515         unsigned int k; /* number of bits in bit buffer */
 516
 517         /* make local bit buffer */
 518
 519         b = gunzip_bb;
 520         k = gunzip_bk;
 521
 522         /* read in last block bit */
 523         b = fill_bitbuffer(b, &k, 1);
 524         *e = (int) b & 1;
 525         b >>= 1;
 526         k -= 1;
 527
 528         /* read in block type */
 529         b = fill_bitbuffer(b, &k, 2);
 530         t = (unsigned) b & 3;
 531         b >>= 2;
 532         k -= 2;
 533
 534         /* restore the global bit buffer */
 535         gunzip_bb = b;
 536         gunzip_bk = k;
 537
 538         /* inflate that block type */
 539         switch (t) {
 540         case 0:                 /* Inflate stored */
 541         {
 542                 unsigned int n; /* number of bytes in block */
 543                 unsigned int b_stored;  /* bit buffer */
 544                 unsigned int k_stored;  /* number of bits in bit buffer */
 545
 546                 /* make local copies of globals */
 547                 b_stored = gunzip_bb;   /* initialize bit buffer */
 548                 k_stored = gunzip_bk;
 549
 550                 /* go to byte boundary */
 551                 n = k_stored & 7;
 552                 b_stored >>= n;
 553                 k_stored -= n;
 554
 555                 /* get the length and its complement */
 556                 b_stored = fill_bitbuffer(b_stored, &k_stored, 16);
 557                 n = ((unsigned) b_stored & 0xffff);
 558                 b_stored >>= 16;
 559                 k_stored -= 16;
 560
 561                 b_stored = fill_bitbuffer(b_stored, &k_stored, 16);
 562                 if (n != (unsigned) ((~b_stored) & 0xffff)) {
 563                         return 1;       /* error in compressed data */
 564                 }
 565                 b_stored >>= 16;
 566                 k_stored -= 16;
 567
 568                 inflate_stored(n, b_stored, k_stored, 1); // Setup inflate_stored
 569                 return -1;
 570         }
 571         case 1:                 /* Inflate fixed
 572                                                    * decompress an inflated type 1 (fixed Huffman codes) block.  We should
 573                                                    * either replace this with a custom decoder, or at least precompute the
 574                                                    * Huffman tables.
 575                                                  */
 576         {
 577                 int i;                  /* temporary variable */
 578                 huft_t *tl;             /* literal/length code table */
 579                 huft_t *td;             /* distance code table */
 580                 unsigned int bl;                        /* lookup bits for tl */
 581                 unsigned int bd;                        /* lookup bits for td */
 582                 unsigned int l[288];    /* length list for huft_build */
 583
 584                 /* set up literal table */
 585                 for (i = 0; i < 144; i++) {
 586                         l[i] = 8;
 587                 }
 588                 for (; i < 256; i++) {
 589                         l[i] = 9;
 590                 }
 591                 for (; i < 280; i++) {
 592                         l[i] = 7;
 593                 }
 594                 for (; i < 288; i++) {  /* make a complete, but wrong code set */
 595                         l[i] = 8;
 596                 }
 597                 bl = 7;
 598                 if ((i = huft_build(l, 288, 257, cplens, cplext, &tl, &bl)) != 0) {
 599                         return i;
 600                 }
 601
 602                 /* set up distance table */
 603                 for (i = 0; i < 30; i++) {      /* make an incomplete code set */
 604                         l[i] = 5;
 605                 }
 606                 bd = 5;
 607                 if ((i = huft_build(l, 30, 0, cpdist, cpdext, &td, &bd)) > 1) {
 608                         huft_free(tl);
 609                         return i;
 610                 }
 611
 612                 /* decompress until an end-of-block code */
 613                 inflate_codes(tl, td, bl, bd, 1); // Setup inflate_codes
 614
 615                 /* huft_free code moved into inflate_codes */
 616
 617                 return -2;
 618         }
 619         case 2:                 /* Inflate dynamic */
 620         {
 621                 const int dbits = 6;    /* bits in base distance lookup table */
 622                 const int lbits = 9;    /* bits in base literal/length lookup table */
 623
 624                 huft_t *tl;             /* literal/length code table */
 625                 huft_t *td;             /* distance code table */
 626                 unsigned int i;                 /* temporary variables */
 627                 unsigned int j;
 628                 unsigned int l;         /* last length */
 629                 unsigned int m;         /* mask for bit lengths table */
 630                 unsigned int n;         /* number of lengths to get */
 631                 unsigned int bl;                        /* lookup bits for tl */
 632                 unsigned int bd;                        /* lookup bits for td */
 633                 unsigned int nb;        /* number of bit length codes */
 634                 unsigned int nl;        /* number of literal/length codes */
 635                 unsigned int nd;        /* number of distance codes */
 636
 637                 unsigned int ll[286 + 30];      /* literal/length and distance code lengths */
 638                 unsigned int b_dynamic; /* bit buffer */
 639                 unsigned int k_dynamic; /* number of bits in bit buffer */
 640
 641                 /* make local bit buffer */
 642                 b_dynamic = gunzip_bb;
 643                 k_dynamic = gunzip_bk;
 644
 645                 /* read in table lengths */
 646                 b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 5);
 647                 nl = 257 + ((unsigned int) b_dynamic & 0x1f);   /* number of literal/length codes */
 648
 649                 b_dynamic >>= 5;
 650                 k_dynamic -= 5;
 651                 b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 5);
 652                 nd = 1 + ((unsigned int) b_dynamic & 0x1f);     /* number of distance codes */
 653
 654                 b_dynamic >>= 5;
 655                 k_dynamic -= 5;
 656                 b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 4);
 657                 nb = 4 + ((unsigned int) b_dynamic & 0xf);      /* number of bit length codes */
 658
 659                 b_dynamic >>= 4;
 660                 k_dynamic -= 4;
 661                 if (nl > 286 || nd > 30) {
 662                         return 1;       /* bad lengths */
 663                 }
 664
 665                 /* read in bit-length-code lengths */
 666                 for (j = 0; j < nb; j++) {
 667                         b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 3);
 668                         ll[border[j]] = (unsigned int) b_dynamic & 7;
 669                         b_dynamic >>= 3;
 670                         k_dynamic -= 3;
 671                 }
 672                 for (; j < 19; j++) {
 673                         ll[border[j]] = 0;
 674                 }
 675
 676                 /* build decoding table for trees--single level, 7 bit lookup */
 677                 bl = 7;
 678                 i = huft_build(ll, 19, 19, NULL, NULL, &tl, &bl);
 679                 if (i != 0) {
 680                         if (i == 1) {
 681                                 huft_free(tl);
 682                         }
 683                         return i;       /* incomplete code set */
 684                 }
 685
 686                 /* read in literal and distance code lengths */
 687                 n = nl + nd;
 688                 m = mask_bits[bl];
 689                 i = l = 0;
 690                 while ((unsigned int) i < n) {
 691                         b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, (unsigned int)bl);
 692                         j = (td = tl + ((unsigned int) b_dynamic & m))->b;
 693                         b_dynamic >>= j;
 694                         k_dynamic -= j;
 695                         j = td->v.n;
 696                         if (j < 16) {   /* length of code in bits (0..15) */
 697                                 ll[i++] = l = j;        /* save last length in l */
 698                         } else if (j == 16) {   /* repeat last length 3 to 6 times */
 699                                 b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 2);
 700                                 j = 3 + ((unsigned int) b_dynamic & 3);
 701                                 b_dynamic >>= 2;
 702                                 k_dynamic -= 2;
 703                                 if ((unsigned int) i + j > n) {
 704                                         return 1;
 705                                 }
 706                                 while (j--) {
 707                                         ll[i++] = l;
 708                                 }
 709                         } else if (j == 17) {   /* 3 to 10 zero length codes */
 710                                 b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 3);
 711                                 j = 3 + ((unsigned int) b_dynamic & 7);
 712                                 b_dynamic >>= 3;
 713                                 k_dynamic -= 3;
 714                                 if ((unsigned int) i + j > n) {
 715                                         return 1;
 716                                 }
 717                                 while (j--) {
 718                                         ll[i++] = 0;
 719                                 }
 720                                 l = 0;
 721                         } else {        /* j == 18: 11 to 138 zero length codes */
 722                                 b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 7);
 723                                 j = 11 + ((unsigned int) b_dynamic & 0x7f);
 724                                 b_dynamic >>= 7;
 725                                 k_dynamic -= 7;
 726                                 if ((unsigned int) i + j > n) {
 727                                         return 1;
 728                                 }
 729                                 while (j--) {
 730                                         ll[i++] = 0;
 731                                 }
 732                                 l = 0;
 733                         }
 734                 }
 735
 736                 /* free decoding table for trees */
 737                 huft_free(tl);
 738
 739                 /* restore the global bit buffer */
 740                 gunzip_bb = b_dynamic;
 741                 gunzip_bk = k_dynamic;
 742
 743                 /* build the decoding tables for literal/length and distance codes */
 744                 bl = lbits;
 745
 746                 if ((i = huft_build(ll, nl, 257, cplens, cplext, &tl, &bl)) != 0) {
 747                         if (i == 1) {
 748                                 bb_error_msg_and_die("Incomplete literal tree");
 749                                 huft_free(tl);
 750                         }
 751                         return i;       /* incomplete code set */
 752                 }
 753
 754                 bd = dbits;
 755                 if ((i = huft_build(ll + nl, nd, 0, cpdist, cpdext, &td, &bd)) != 0) {
 756                         if (i == 1) {
 757                                 bb_error_msg_and_die("incomplete distance tree");
 758                                 huft_free(td);
 759                         }
 760                         huft_free(tl);
 761                         return i;       /* incomplete code set */
 762                 }
 763
 764                 /* decompress until an end-of-block code */
 765                 inflate_codes(tl, td, bl, bd, 1); // Setup inflate_codes
 766
 767                 /* huft_free code moved into inflate_codes */
 768
 769                 return -2;
 770         }
 771         default:
 772                 /* bad block type */
 773                 bb_error_msg_and_die("bad block type %d", t);
 774         }
 775 }
 776
 777 static void calculate_gunzip_crc(void)
 778 {
 779         int n;
 780         for (n = 0; n < gunzip_outbuf_count; n++) {
 781                 gunzip_crc = gunzip_crc_table[((int) gunzip_crc ^ (gunzip_window[n])) & 0xff] ^ (gunzip_crc >> 8);
 782         }
 783         gunzip_bytes_out += gunzip_outbuf_count;
 784 }
 785
 786 static int inflate_get_next_window(void)
 787 {
 788         static int method = -1; // Method == -1 for stored, -2 for codes
 789         static int e = 0;
 790         static int needAnotherBlock = 1;
 791
 792         gunzip_outbuf_count = 0;
 793
 794         while(1) {
 795                 int ret;
 796
 797                 if (needAnotherBlock) {
 798                         if(e) {
 799                                 calculate_gunzip_crc();
 800                                 e = 0;
 801                                 needAnotherBlock = 1;
 802                                 return 0;
 803                         } // Last block
 804                         method = inflate_block(&e);
 805                         needAnotherBlock = 0;
 806                 }
 807
 808                 switch (method) {
 809                         case -1:        ret = inflate_stored(0,0,0,0);
 810                                         break;
 811                         case -2:        ret = inflate_codes(0,0,0,0,0);
 812                                         break;
 813                         default:        bb_error_msg_and_die("inflate error %d", method);
 814                 }
 815
 816                 if (ret == 1) {
 817                         calculate_gunzip_crc();
 818                         return 1; // More data left
 819                 } else needAnotherBlock = 1; // End of that block
 820         }
 821         /* Doesnt get here */
 822 }
 823
 824 /* Initialise bytebuffer, be careful not to overfill the buffer */
 825 void inflate_init(unsigned int bufsize)
 826 {
 827         /* Set the bytebuffer size, default is same as gunzip_wsize */
 828         bytebuffer_max = bufsize + 8;
 829         bytebuffer_offset = 4;
 830         bytebuffer_size = 0;
 831 }
 832
 833 void inflate_cleanup(void)
 834 {
 835         free(bytebuffer);
 836 }
 837
 838 int inflate_unzip(int in, int out)
 839 {
 840         ssize_t nwrote;
 841         typedef void (*sig_type) (int);
 842
 843         /* Allocate all global buffers (for DYN_ALLOC option) */
 844         gunzip_window = xmalloc(gunzip_wsize);
 845         gunzip_outbuf_count = 0;
 846         gunzip_bytes_out = 0;
 847         gunzip_src_fd = in;
 848
 849         /* initialize gunzip_window, bit buffer */
 850         gunzip_bk = 0;
 851         gunzip_bb = 0;
 852
 853         /* Create the crc table */
 854         gunzip_crc_table = crc32_filltable(0);
 855         gunzip_crc = ~0;
 856
 857         /* Allocate space for buffer */
 858         bytebuffer = xmalloc(bytebuffer_max);
 859
 860         while(1) {
 861                 int ret = inflate_get_next_window();
 862                 nwrote = full_write(out, gunzip_window, gunzip_outbuf_count);
 863                 if (nwrote == -1) {
 864                         bb_perror_msg("write");
 865                         return -1;
 866                 }
 867                 if (ret == 0) break;
 868         }
 869
 870         /* Cleanup */
 871         free(gunzip_window);
 872         free(gunzip_crc_table);
 873
 874         /* Store unused bytes in a global buffer so calling applets can access it */
 875         if (gunzip_bk >= 8) {
 876                 /* Undo too much lookahead. The next read will be byte aligned
 877                  * so we can discard unused bits in the last meaningful byte. */
 878                 bytebuffer_offset--;
 879                 bytebuffer[bytebuffer_offset] = gunzip_bb & 0xff;
 880                 gunzip_bb >>= 8;
 881                 gunzip_bk -= 8;
 882         }
 883         return 0;
 884 }
 885
 886 int inflate_gunzip(int in, int out)
 887 {
 888         uint32_t stored_crc = 0;
 889         unsigned int count;
 890
 891         inflate_unzip(in, out);
 892
 893         /* top up the input buffer with the rest of the trailer */
 894         count = bytebuffer_size - bytebuffer_offset;
 895         if (count < 8) {
 896                 xread(in, &bytebuffer[bytebuffer_size], 8 - count);
 897                 bytebuffer_size += 8 - count;
 898         }
 899         for (count = 0; count != 4; count++) {
 900                 stored_crc |= (bytebuffer[bytebuffer_offset] << (count * 8));
 901                 bytebuffer_offset++;
 902         }
 903
 904         /* Validate decompression - crc */
 905         if (stored_crc != (~gunzip_crc)) {
 906                 bb_error_msg("crc error");
 907                 return -1;
 908         }
 909
 910         /* Validate decompression - size */
 911         if (gunzip_bytes_out !=
 912                 (bytebuffer[bytebuffer_offset] | (bytebuffer[bytebuffer_offset+1] << 8) |
 913                 (bytebuffer[bytebuffer_offset+2] << 16) | (bytebuffer[bytebuffer_offset+3] << 24))) {
 914                 bb_error_msg("Incorrect length");
 915                 return -1;
 916         }
 917
 918         return 0;
 919 }