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