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