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