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