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