busybox/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 "config.h"
  78 #include "busybox.h"
  79 #include "unarchive.h"
  80
  81 typedef struct huft_s {
  82         unsigned char e;        /* number of extra bits or operation */
  83         unsigned char b;        /* number of bits in this code or subcode */
  84         union {
  85                 unsigned short n;       /* literal, length base, or distance base */
  86                 struct huft_s *t;       /* pointer to next level of table */
  87         } v;
  88 } huft_t;
  89
  90 static int gunzip_src_fd;
  91 unsigned int gunzip_bytes_out;  /* number of output bytes */
  92 static unsigned int gunzip_outbuf_count;        /* bytes in output buffer */
  93
  94 /* gunzip_window size--must be a power of two, and
  95  *  at least 32K for zip's deflate method */
  96 static const int gunzip_wsize = 0x8000;
  97 static unsigned char *gunzip_window;
  98
  99 static unsigned int *gunzip_crc_table;
 100 unsigned int gunzip_crc;
 101
 102 /* If BMAX needs to be larger than 16, then h and x[] should be ulg. */
 103 #define BMAX 16 /* maximum bit length of any code (16 for explode) */
 104 #define N_MAX 288       /* maximum number of codes in any set */
 105
 106 /* bitbuffer */
 107 static unsigned int gunzip_bb;  /* bit buffer */
 108 static unsigned char gunzip_bk; /* bits in bit buffer */
 109
 110 /* These control the size of the bytebuffer */
 111 static unsigned int bytebuffer_max = 0x8000;
 112 static unsigned char *bytebuffer = NULL;
 113 static unsigned int bytebuffer_offset = 0;
 114 static unsigned int bytebuffer_size = 0;
 115
 116 static const unsigned short mask_bits[] = {
 117         0x0000, 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
 118         0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
 119 };
 120
 121 /* Copy lengths for literal codes 257..285 */
 122 static const unsigned short cplens[] = {
 123         3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59,
 124         67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0
 125 };
 126
 127 /* note: see note #13 above about the 258 in this list. */
 128 /* Extra bits for literal codes 257..285 */
 129 static const unsigned char cplext[] = {
 130         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,
 131         5, 5, 5, 0, 99, 99
 132 };                                              /* 99==invalid */
 133
 134 /* Copy offsets for distance codes 0..29 */
 135 static const unsigned short cpdist[] = {
 136         1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513,
 137         769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577
 138 };
 139
 140 /* Extra bits for distance codes */
 141 static const unsigned char cpdext[] = {
 142         0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10,
 143         11, 11, 12, 12, 13, 13
 144 };
 145
 146 /* Tables for deflate from PKZIP's appnote.txt. */
 147 /* Order of the bit length code lengths */
 148 static const unsigned char border[] = {
 149         16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
 150 };
 151
 152 static unsigned int fill_bitbuffer(unsigned int bitbuffer, unsigned int *current, const unsigned int required)
 153 {
 154         while (*current < required) {
 155                 if (bytebuffer_offset >= bytebuffer_size) {
 156                         /* Leave the first 4 bytes empty so we can always unwind the bitbuffer
 157                          * to the front of the bytebuffer, leave 4 bytes free at end of tail
 158                          * so we can easily top up buffer in check_trailer_gzip() */
 159                         if (!(bytebuffer_size = bb_xread(gunzip_src_fd, &bytebuffer[4], bytebuffer_max - 8))) {
 160                                 bb_error_msg_and_die("unexpected end of file");
 161                         }
 162                         bytebuffer_size += 4;
 163                         bytebuffer_offset = 4;
 164                 }
 165                 bitbuffer |= ((unsigned int) bytebuffer[bytebuffer_offset]) << *current;
 166                 bytebuffer_offset++;
 167                 *current += 8;
 168         }
 169         return(bitbuffer);
 170 }
 171
 172 static void make_gunzip_crc_table(void)
 173 {
 174         const unsigned int poly = 0xedb88320;   /* polynomial exclusive-or pattern */
 175         unsigned short i;       /* counter for all possible eight bit values */
 176
 177         /* initial shift register value */
 178         gunzip_crc = 0xffffffffL;
 179         gunzip_crc_table = (unsigned int *) xmalloc(256 * sizeof(unsigned int));
 180
 181         /* Compute and print table of CRC's, five per line */
 182         for (i = 0; i < 256; i++) {
 183                 unsigned int table_entry;       /* crc shift register */
 184                 unsigned char k;        /* byte being shifted into crc apparatus */
 185
 186                 table_entry = i;
 187                 /* The idea to initialize the register with the byte instead of
 188                    * zero was stolen from Haruhiko Okumura's ar002
 189                  */
 190                 for (k = 8; k; k--) {
 191                         if (table_entry & 1) {
 192                                 table_entry = (table_entry >> 1) ^ poly;
 193                         } else {
 194                                 table_entry >>= 1;
 195                         }
 196                 }
 197                 gunzip_crc_table[i] = table_entry;
 198         }
 199 }
 200
 201 /*
 202  * Free the malloc'ed tables built by huft_build(), which makes a linked
 203  * list of the tables it made, with the links in a dummy first entry of
 204  * each table.
 205  * t: table to free
 206  */
 207 static int huft_free(huft_t * t)
 208 {
 209         huft_t *p;
 210         huft_t *q;
 211
 212         /* Go through linked list, freeing from the malloced (t[-1]) address. */
 213         p = t;
 214         while (p != (huft_t *) NULL) {
 215                 q = (--p)->v.t;
 216                 free((char *) p);
 217                 p = q;
 218         }
 219         return 0;
 220 }
 221
 222 /* Given a list of code lengths and a maximum table size, make a set of
 223  * tables to decode that set of codes.  Return zero on success, one if
 224  * the given code set is incomplete (the tables are still built in this
 225  * case), two if the input is invalid (all zero length codes or an
 226  * oversubscribed set of lengths), and three if not enough memory.
 227  *
 228  * b:   code lengths in bits (all assumed <= BMAX)
 229  * n:   number of codes (assumed <= N_MAX)
 230  * s:   number of simple-valued codes (0..s-1)
 231  * d:   list of base values for non-simple codes
 232  * e:   list of extra bits for non-simple codes
 233  * t:   result: starting table
 234  * m:   maximum lookup bits, returns actual
 235  */
 236 int huft_build(unsigned int *b, const unsigned int n,
 237                            const unsigned int s, const unsigned short *d,
 238                            const unsigned char *e, huft_t ** t, int *m)
 239 {
 240         unsigned a;                             /* counter for codes of length k */
 241         unsigned c[BMAX + 1];   /* bit length count table */
 242         unsigned eob_len;               /* length of end-of-block code (value 256) */
 243         unsigned f;                             /* i repeats in table every f entries */
 244         int g;                                  /* maximum code length */
 245         int h;                                  /* table level */
 246         register unsigned i;    /* counter, current code */
 247         register unsigned j;    /* counter */
 248         register int k;                 /* number of bits in current code */
 249         register unsigned *p;   /* pointer into c[], b[], or v[] */
 250         register huft_t *q;             /* points to current table */
 251         huft_t r;                               /* table entry for structure assignment */
 252         huft_t *u[BMAX];                /* table stack */
 253         unsigned v[N_MAX];              /* values in order of bit length */
 254         int ws[BMAX+1];                 /* bits decoded stack */
 255         register int w;                 /* bits decoded */
 256         unsigned x[BMAX + 1];   /* bit offsets, then code stack */
 257         unsigned *xp;                   /* pointer into x */
 258         int y;                                  /* number of dummy codes added */
 259         unsigned z;                             /* number of entries in current table */
 260
 261         /* Length of EOB code, if any */
 262         eob_len = n > 256 ? b[256] : BMAX;
 263
 264         /* Generate counts for each bit length */
 265         memset((void *)c, 0, sizeof(c));
 266         p = b;
 267         i = n;
 268         do {
 269                 c[*p]++; /* assume all entries <= BMAX */
 270                 p++; /* Can't combine with above line (Solaris bug) */
 271         } while (--i);
 272         if (c[0] == n) { /* null input--all zero length codes */
 273                 *t = (huft_t *) NULL;
 274                 *m = 0;
 275                 return 0;
 276         }
 277
 278         /* Find minimum and maximum length, bound *m by those */
 279         for (j = 1; (c[j] == 0) && (j <= BMAX); j++);
 280         k = j; /* minimum code length */
 281         for (i = BMAX; (c[i] == 0) && i; i--);
 282         g = i; /* maximum code length */
 283         *m = (*m < j) ? j : ((*m > i) ? i : *m);
 284
 285         /* Adjust last length count to fill out codes, if needed */
 286         for (y = 1 << j; j < i; j++, y <<= 1) {
 287                 if ((y -= c[j]) < 0) {
 288                         return 2; /* bad input: more codes than bits */
 289                 }
 290         }
 291         if ((y -= c[i]) < 0) {
 292                 return 2;
 293         }
 294         c[i] += y;
 295
 296         /* Generate starting offsets into the value table for each length */
 297         x[1] = j = 0;
 298         p = c + 1;
 299         xp = x + 2;
 300         while (--i) { /* note that i == g from above */
 301                 *xp++ = (j += *p++);
 302         }
 303
 304         /* Make a table of values in order of bit lengths */
 305         p = b;
 306         i = 0;
 307         do {
 308                 if ((j = *p++) != 0) {
 309                         v[x[j]++] = i;
 310                 }
 311         } while (++i < n);
 312
 313         /* Generate the Huffman codes and for each, make the table entries */
 314         x[0] = i = 0;                   /* first Huffman code is zero */
 315         p = v;                                  /* grab values in bit order */
 316         h = -1;                                 /* no tables yet--level -1 */
 317         w = ws[0] = 0;                  /* bits decoded */
 318         u[0] = (huft_t *) NULL; /* just to keep compilers happy */
 319         q = (huft_t *) NULL;    /* ditto */
 320         z = 0;                                  /* ditto */
 321
 322         /* go through the bit lengths (k already is bits in shortest code) */
 323         for (; k <= g; k++) {
 324                 a = c[k];
 325                 while (a--) {
 326                         /* here i is the Huffman code of length k bits for value *p */
 327                         /* make tables up to required level */
 328                         while (k > ws[h + 1]) {
 329                                 w = ws[++h];
 330
 331                                 /* compute minimum size table less than or equal to *m bits */
 332                                 z = (z = g - w) > *m ? *m : z; /* upper limit on table size */
 333                                 if ((f = 1 << (j = k - w)) > a + 1) { /* try a k-w bit table */
 334                                         /* too few codes for k-w bit table */
 335                                         f -= a + 1; /* deduct codes from patterns left */
 336                                         xp = c + k;
 337                                         while (++j < z) { /* try smaller tables up to z bits */
 338                                                 if ((f <<= 1) <= *++xp) {
 339                                                         break; /* enough codes to use up j bits */
 340                                                 }
 341                                                 f -= *xp; /* else deduct codes from patterns */
 342                                         }
 343                                 }
 344                                 j = (w + j > eob_len && w < eob_len) ? eob_len - w : j; /* make EOB code end at table */
 345                                 z = 1 << j;     /* table entries for j-bit table */
 346                                 ws[h+1] = w + j;        /* set bits decoded in stack */
 347
 348                                 /* allocate and link in new table */
 349                                 q = (huft_t *) xmalloc((z + 1) * sizeof(huft_t));
 350                                 *t = q + 1;     /* link to list for huft_free() */
 351                                 *(t = &(q->v.t)) = NULL;
 352                                 u[h] = ++q;     /* table starts after link */
 353
 354                                 /* connect to last table, if there is one */
 355                                 if (h) {
 356                                         x[h] = i; /* save pattern for backing up */
 357                                         r.b = (unsigned char) (w - ws[h - 1]); /* bits to dump before this table */
 358                                         r.e = (unsigned char) (16 + j); /* bits in this table */
 359                                         r.v.t = q; /* pointer to this table */
 360                                         j = (i & ((1 << w) - 1)) >> ws[h - 1];
 361                                         u[h - 1][j] = r; /* connect to last table */
 362                                 }
 363                         }
 364
 365                         /* set up table entry in r */
 366                         r.b = (unsigned char) (k - w);
 367                         if (p >= v + n) {
 368                                 r.e = 99; /* out of values--invalid code */
 369                         } else if (*p < s) {
 370                                 r.e = (unsigned char) (*p < 256 ? 16 : 15);     /* 256 is EOB code */
 371                                 r.v.n = (unsigned short) (*p++); /* simple code is just the value */
 372                         } else {
 373                                 r.e = (unsigned char) e[*p - s]; /* non-simple--look up in lists */
 374                                 r.v.n = d[*p++ - s];
 375                         }
 376
 377                         /* fill code-like entries with r */
 378                         f = 1 << (k - w);
 379                         for (j = i >> w; j < z; j += f) {
 380                                 q[j] = r;
 381                         }
 382
 383                         /* backwards increment the k-bit code i */
 384                         for (j = 1 << (k - 1); i & j; j >>= 1) {
 385                                 i ^= j;
 386                         }
 387                         i ^= j;
 388
 389                         /* backup over finished tables */
 390                         while ((i & ((1 << w) - 1)) != x[h]) {
 391                                 w = ws[--h];
 392                         }
 393                 }
 394         }
 395
 396         /* return actual size of base table */
 397         *m = ws[1];
 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 careful 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 void inflate_cleanup(void)
 905 {
 906         free(bytebuffer);
 907 }
 908
 909 extern int inflate_unzip(int in, int out)
 910 {
 911         ssize_t nwrote;
 912         typedef void (*sig_type) (int);
 913
 914         /* Allocate all global buffers (for DYN_ALLOC option) */
 915         gunzip_window = xmalloc(gunzip_wsize);
 916         gunzip_outbuf_count = 0;
 917         gunzip_bytes_out = 0;
 918         gunzip_src_fd = in;
 919
 920         /* initialize gunzip_window, bit buffer */
 921         gunzip_bk = 0;
 922         gunzip_bb = 0;
 923
 924         /* Create the crc table */
 925         make_gunzip_crc_table();
 926
 927         /* Allocate space for buffer */
 928         bytebuffer = xmalloc(bytebuffer_max);
 929
 930         while(1) {
 931                 int ret = inflate_get_next_window();
 932                 nwrote = bb_full_write(out, gunzip_window, gunzip_outbuf_count);
 933                 if (nwrote == -1) {
 934                         bb_perror_msg("write");
 935                         return -1;
 936                 }
 937                 if (ret == 0) break;
 938         }
 939
 940         /* Cleanup */
 941         free(gunzip_window);
 942         free(gunzip_crc_table);
 943
 944         /* Store unused bytes in a global buffer so calling applets can access it */
 945         if (gunzip_bk >= 8) {
 946                 /* Undo too much lookahead. The next read will be byte aligned
 947                  * so we can discard unused bits in the last meaningful byte. */
 948                 bytebuffer_offset--;
 949                 bytebuffer[bytebuffer_offset] = gunzip_bb & 0xff;
 950                 gunzip_bb >>= 8;
 951                 gunzip_bk -= 8;
 952         }
 953         return 0;
 954 }
 955
 956 extern int inflate_gunzip(int in, int out)
 957 {
 958         unsigned int stored_crc = 0;
 959         unsigned int count;
 960
 961         inflate_unzip(in, out);
 962
 963         /* top up the input buffer with the rest of the trailer */
 964         count = bytebuffer_size - bytebuffer_offset;
 965         if (count < 8) {
 966                 bb_xread_all(in, &bytebuffer[bytebuffer_size], 8 - count);
 967                 bytebuffer_size += 8 - count;
 968         }
 969         for (count = 0; count != 4; count++) {
 970                 stored_crc |= (bytebuffer[bytebuffer_offset] << (count * 8));
 971                 bytebuffer_offset++;
 972         }
 973
 974         /* Validate decompression - crc */
 975         if (stored_crc != (gunzip_crc ^ 0xffffffffL)) {
 976                 bb_error_msg("crc error");
 977         }
 978
 979         /* Validate decompression - size */
 980         if (gunzip_bytes_out !=
 981                 (bytebuffer[bytebuffer_offset] | (bytebuffer[bytebuffer_offset+1] << 8) |
 982                 (bytebuffer[bytebuffer_offset+2] << 16) | (bytebuffer[bytebuffer_offset+3] << 24))) {
 983                 bb_error_msg("Incorrect length");
 984         }
 985
 986         return 0;
 987 }