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