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