archival/libunarchive/decompress_unzip.c

   1 /* vi: set sw=4 ts=4: */
   2 /*
   3  * gunzip implementation for busybox
   4  *
   5  * Based on GNU gzip v1.2.4 Copyright (C) 1992-1993 Jean-loup Gailly.
   6  *
   7  * Originally adjusted for busybox by Sven Rudolph <sr1@inf.tu-dresden.de>
   8  * based on gzip sources
   9  *
  10  * Adjusted further by Erik Andersen <andersen@lineo.com>, <andersee@debian.org>
  11  * to support 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 "libbb.h"
  69
  70 static FILE *in_file, *out_file;
  71
  72 /* these are freed by gz_close */
  73 static unsigned char *window;
  74 static unsigned long *crc_table;
  75
  76 static unsigned long crc = 0xffffffffL; /* shift register contents */
  77
  78 /* Return codes from gzip */
  79 static const int ERROR = 1;
  80
  81 /*
  82  * window size--must be a power of two, and
  83  *  at least 32K for zip's deflate method
  84  */
  85 static const int WSIZE = 0x8000;
  86
  87 /* If BMAX needs to be larger than 16, then h and x[] should be ulg. */
  88 static const int BMAX = 16;             /* maximum bit length of any code (16 for explode) */
  89 static const int N_MAX = 288;           /* maximum number of codes in any set */
  90
  91 static long bytes_out;          /* number of output bytes */
  92 static unsigned long outcnt;    /* bytes in output buffer */
  93
  94 static unsigned hufts;          /* track memory usage */
  95 static unsigned long bb;                        /* bit buffer */
  96 static unsigned bk;             /* bits in bit buffer */
  97
  98 typedef struct huft_s {
  99         unsigned char e;                /* number of extra bits or operation */
 100         unsigned char b;                /* number of bits in this code or subcode */
 101         union {
 102                 unsigned short n;               /* literal, length base, or distance base */
 103                 struct huft_s *t;       /* pointer to next level of table */
 104         } v;
 105 } huft_t;
 106
 107 static const unsigned short mask_bits[] = {
 108         0x0000,
 109         0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
 110         0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
 111 };
 112
 113 //static int error_number = 0;
 114 /* ========================================================================
 115  * Signal and error handler.
 116  */
 117
 118 static void abort_gzip(void)
 119 {
 120         error_msg("gzip aborted\n");
 121         exit(ERROR);
 122 }
 123
 124 static void make_crc_table(void)
 125 {
 126         const unsigned long poly = 0xedb88320;      /* polynomial exclusive-or pattern */
 127         unsigned short i;                /* counter for all possible eight bit values */
 128
 129         crc_table = (unsigned long *) malloc(256 * sizeof(unsigned long));
 130
 131         /* Compute and print table of CRC's, five per line */
 132         for (i = 0; i < 256; i++) {
 133                 unsigned long table_entry;      /* crc shift register */
 134                 char k; /* byte being shifted into crc apparatus */
 135
 136                 table_entry = i;
 137            /* The idea to initialize the register with the byte instead of
 138              * zero was stolen from Haruhiko Okumura's ar002
 139              */
 140                 for (k = 8; k; k--) {
 141                         table_entry = table_entry & 1 ? (table_entry >> 1) ^ poly : table_entry >> 1;
 142                 }
 143                 crc_table[i]=table_entry;
 144         }
 145 }
 146
 147 /* ===========================================================================
 148  * Write the output window window[0..outcnt-1] and update crc and bytes_out.
 149  * (Used for the decompressed data only.)
 150  */
 151 static void flush_window(void)
 152 {
 153         int n;
 154
 155         if (outcnt == 0)
 156                 return;
 157
 158         for (n = 0; n < outcnt; n++) {
 159                 crc = crc_table[((int) crc ^ (window[n])) & 0xff] ^ (crc >> 8);
 160         }
 161
 162         if (fwrite(window, 1, outcnt, out_file) != outcnt) {
 163                 error_msg_and_die("Couldnt write");
 164         }
 165         bytes_out += (unsigned long) outcnt;
 166         outcnt = 0;
 167 }
 168
 169 /*
 170  * Free the malloc'ed tables built by huft_build(), which makes a linked
 171  * list of the tables it made, with the links in a dummy first entry of
 172  * each table.
 173  * t: table to free
 174  */
 175 static int huft_free(huft_t *t)
 176 {
 177         huft_t *p, *q;
 178
 179         /* Go through linked list, freeing from the malloced (t[-1]) address. */
 180         p = t;
 181         while (p != (huft_t *) NULL) {
 182                 q = (--p)->v.t;
 183                 free((char *) p);
 184                 p = q;
 185         }
 186         return 0;
 187 }
 188
 189 /* Given a list of code lengths and a maximum table size, make a set of
 190  * tables to decode that set of codes.  Return zero on success, one if
 191  * the given code set is incomplete (the tables are still built in this
 192  * case), two if the input is invalid (all zero length codes or an
 193  * oversubscribed set of lengths), and three if not enough memory.
 194  *
 195  * b:   code lengths in bits (all assumed <= BMAX)
 196  * n:   number of codes (assumed <= N_MAX)
 197  * s:   number of simple-valued codes (0..s-1)
 198  * d:   list of base values for non-simple codes
 199  * e:   list of extra bits for non-simple codes
 200  * t:   result: starting table
 201  * m:   maximum lookup bits, returns actual
 202  */
 203 static int huft_build(unsigned int *b, const unsigned int n, const unsigned int s,
 204         const unsigned short *d, const unsigned short *e, huft_t **t, int *m)
 205 {
 206         unsigned a;             /* counter for codes of length k */
 207         unsigned c[BMAX + 1];   /* bit length count table */
 208         unsigned f;             /* i repeats in table every f entries */
 209         int g;                  /* maximum code length */
 210         int h;                  /* table level */
 211         register unsigned i;    /* counter, current code */
 212         register unsigned j;    /* counter */
 213         register int k;         /* number of bits in current code */
 214         int l;                  /* bits per table (returned in m) */
 215         register unsigned *p;           /* pointer into c[], b[], or v[] */
 216         register huft_t *q;     /* points to current table */
 217         huft_t r;               /* table entry for structure assignment */
 218         huft_t *u[BMAX];        /* table stack */
 219         unsigned v[N_MAX];      /* values in order of bit length */
 220         register int w;         /* bits before this table == (l * h) */
 221         unsigned x[BMAX + 1];   /* bit offsets, then code stack */
 222         unsigned *xp;           /* pointer into x */
 223         int y;                  /* number of dummy codes added */
 224         unsigned z;             /* number of entries in current table */
 225
 226         /* Generate counts for each bit length */
 227         memset ((void *)(c), 0, sizeof(c));
 228         p = b;
 229         i = n;
 230         do {
 231                 c[*p]++;        /* assume all entries <= BMAX */
 232                 p++;            /* Can't combine with above line (Solaris bug) */
 233         } while (--i);
 234         if (c[0] == n) {        /* null input--all zero length codes */
 235                 *t = (huft_t *) NULL;
 236                 *m = 0;
 237                 return 0;
 238         }
 239
 240         /* Find minimum and maximum length, bound *m by those */
 241         l = *m;
 242         for (j = 1; j <= BMAX; j++)
 243                 if (c[j])
 244                         break;
 245         k = j;                          /* minimum code length */
 246         if ((unsigned) l < j)
 247                 l = j;
 248         for (i = BMAX; i; i--)
 249                 if (c[i])
 250                         break;
 251         g = i;                          /* maximum code length */
 252         if ((unsigned) l > i)
 253                 l = i;
 254         *m = l;
 255
 256         /* Adjust last length count to fill out codes, if needed */
 257         for (y = 1 << j; j < i; j++, y <<= 1)
 258                 if ((y -= c[j]) < 0)
 259                         return 2;       /* bad input: more codes than bits */
 260         if ((y -= c[i]) < 0)
 261                 return 2;
 262         c[i] += y;
 263
 264         /* Generate starting offsets into the value table for each length */
 265         x[1] = j = 0;
 266         p = c + 1;
 267         xp = x + 2;
 268         while (--i) {                   /* note that i == g from above */
 269                 *xp++ = (j += *p++);
 270         }
 271
 272         /* Make a table of values in order of bit lengths */
 273         p = b;
 274         i = 0;
 275         do {
 276                 if ((j = *p++) != 0)
 277                         v[x[j]++] = i;
 278         } while (++i < n);
 279
 280         /* Generate the Huffman codes and for each, make the table entries */
 281         x[0] = i = 0;                   /* first Huffman code is zero */
 282         p = v;                          /* grab values in bit order */
 283         h = -1;                         /* no tables yet--level -1 */
 284         w = -l;                         /* bits decoded == (l * h) */
 285         u[0] = (huft_t *) NULL; /* just to keep compilers happy */
 286         q = (huft_t *) NULL;    /* ditto */
 287         z = 0;                          /* ditto */
 288
 289         /* go through the bit lengths (k already is bits in shortest code) */
 290         for (; k <= g; k++) {
 291                 a = c[k];
 292                 while (a--) {
 293                         /* here i is the Huffman code of length k bits for value *p */
 294                         /* make tables up to required level */
 295                         while (k > w + l) {
 296                                 h++;
 297                                 w += l;         /* previous table always l bits */
 298
 299                                 /* compute minimum size table less than or equal to l bits */
 300                                 z = (z = g - w) > (unsigned) l ? l : z; /* upper limit on table size */
 301                                 if ((f = 1 << (j = k - w)) > a + 1) {   /* try a k-w bit table *//* too few codes for k-w bit table */
 302                                         f -= a + 1;     /* deduct codes from patterns left */
 303                                         xp = c + k;
 304                                         while (++j < z) {       /* try smaller tables up to z bits */
 305                                                 if ((f <<= 1) <= *++xp)
 306                                                         break;  /* enough codes to use up j bits */
 307                                                 f -= *xp;       /* else deduct codes from patterns */
 308                                         }
 309                                 }
 310                                 z = 1 << j;             /* table entries for j-bit table */
 311
 312                                 /* allocate and link in new table */
 313                                 if ((q = (huft_t *) xmalloc((z + 1) * sizeof(huft_t))) == NULL) {
 314                                         if (h) {
 315                                                 huft_free(u[0]);
 316                                         }
 317                                         return 3;       /* not enough memory */
 318                                 }
 319                                 hufts += z + 1; /* track memory usage */
 320                                 *t = q + 1;             /* link to list for huft_free() */
 321                                 *(t = &(q->v.t)) = NULL;
 322                                 u[h] = ++q;             /* table starts after link */
 323
 324                                 /* connect to last table, if there is one */
 325                                 if (h) {
 326                                         x[h] = i;       /* save pattern for backing up */
 327                                         r.b = (unsigned char) l;        /* bits to dump before this table */
 328                                         r.e = (unsigned char) (16 + j); /* bits in this table */
 329                                         r.v.t = q;      /* pointer to this table */
 330                                         j = i >> (w - l);       /* (get around Turbo C bug) */
 331                                         u[h - 1][j] = r;        /* connect to last table */
 332                                 }
 333                         }
 334
 335                         /* set up table entry in r */
 336                         r.b = (unsigned char) (k - w);
 337                         if (p >= v + n)
 338                                 r.e = 99;               /* out of values--invalid code */
 339                         else if (*p < s) {
 340                                 r.e = (unsigned char) (*p < 256 ? 16 : 15);     /* 256 is end-of-block code */
 341                                 r.v.n = (unsigned short) (*p);  /* simple code is just the value */
 342                                 p++;                    /* one compiler does not like *p++ */
 343                         } else {
 344                                 r.e = (unsigned char) e[*p - s];        /* non-simple--look up in lists */
 345                                 r.v.n = d[*p++ - s];
 346                         }
 347
 348                         /* fill code-like entries with r */
 349                         f = 1 << (k - w);
 350                         for (j = i >> w; j < z; j += f)
 351                                 q[j] = r;
 352
 353                         /* backwards increment the k-bit code i */
 354                         for (j = 1 << (k - 1); i & j; j >>= 1)
 355                                 i ^= j;
 356                         i ^= j;
 357
 358                         /* backup over finished tables */
 359                         while ((i & ((1 << w) - 1)) != x[h]) {
 360                                 h--;                    /* don't need to update q */
 361                                 w -= l;
 362                         }
 363                 }
 364         }
 365         /* Return true (1) if we were given an incomplete table */
 366         return y != 0 && g != 1;
 367 }
 368
 369 /*
 370  * inflate (decompress) the codes in a deflated (compressed) block.
 371  * Return an error code or zero if it all goes ok.
 372  *
 373  * tl, td: literal/length and distance decoder tables
 374  * bl, bd: number of bits decoded by tl[] and td[]
 375  */
 376 static int inflate_codes(huft_t *tl, huft_t *td, int bl, int bd)
 377 {
 378         register unsigned long e;               /* table entry flag/number of extra bits */
 379         unsigned long n, d;                             /* length and index for copy */
 380         unsigned long w;                                /* current window position */
 381         huft_t *t;                              /* pointer to table entry */
 382         unsigned ml, md;                        /* masks for bl and bd bits */
 383         register unsigned long b;                               /* bit buffer */
 384         register unsigned k;            /* number of bits in bit buffer */
 385
 386         /* make local copies of globals */
 387         b = bb;                                 /* initialize bit buffer */
 388         k = bk;
 389         w = outcnt;                             /* initialize window position */
 390
 391         /* inflate the coded data */
 392         ml = mask_bits[bl];                     /* precompute masks for speed */
 393         md = mask_bits[bd];
 394         for (;;) {                              /* do until end of block */
 395                 while (k < (unsigned) bl) {
 396                         b |= ((unsigned long)fgetc(in_file)) << k;
 397                         k += 8;
 398                 }
 399                 if ((e = (t = tl + ((unsigned) b & ml))->e) > 16)
 400                 do {
 401                         if (e == 99) {
 402                                 return 1;
 403                         }
 404                         b >>= t->b;
 405                         k -= t->b;
 406                         e -= 16;
 407                         while (k < e) {
 408                                 b |= ((unsigned long)fgetc(in_file)) << k;
 409                                 k += 8;
 410                         }
 411                 } while ((e = (t = t->v.t + ((unsigned) b & mask_bits[e]))->e) > 16);
 412                 b >>= t->b;
 413                 k -= t->b;
 414                 if (e == 16) {          /* then it's a literal */
 415                         window[w++] = (unsigned char) t->v.n;
 416                         if (w == WSIZE) {
 417                                 outcnt=(w),
 418                                 flush_window();
 419                                 w = 0;
 420                         }
 421                 } else {                                /* it's an EOB or a length */
 422
 423                         /* exit if end of block */
 424                         if (e == 15) {
 425                                 break;
 426                         }
 427
 428                         /* get length of block to copy */
 429                         while (k < e) {
 430                                 b |= ((unsigned long)fgetc(in_file)) << k;
 431                                 k += 8;
 432                         }
 433                         n = t->v.n + ((unsigned) b & mask_bits[e]);
 434                         b >>= e;
 435                         k -= e;
 436
 437                         /* decode distance of block to copy */
 438                         while (k < (unsigned) bd) {
 439                                 b |= ((unsigned long)fgetc(in_file)) << k;
 440                                 k += 8;
 441                         }
 442
 443                         if ((e = (t = td + ((unsigned) b & md))->e) > 16)
 444                                 do {
 445                                         if (e == 99)
 446                                                 return 1;
 447                                         b >>= t->b;
 448                                         k -= t->b;
 449                                         e -= 16;
 450                                         while (k < e) {
 451                                                 b |= ((unsigned long)fgetc(in_file)) << k;
 452                                                 k += 8;
 453                                         }
 454                                 } while ((e = (t = t->v.t + ((unsigned) b & mask_bits[e]))->e) > 16);
 455                         b >>= t->b;
 456                         k -= t->b;
 457                         while (k < e) {
 458                                 b |= ((unsigned long)fgetc(in_file)) << k;
 459                                 k += 8;
 460                         }
 461                         d = w - t->v.n - ((unsigned) b & mask_bits[e]);
 462                         b >>= e;
 463                         k -= e;
 464
 465                         /* do the copy */
 466                         do {
 467                                 n -= (e = (e = WSIZE - ((d &= WSIZE - 1) > w ? d : w)) > n ? n : e);
 468 #if !defined(NOMEMCPY) && !defined(DEBUG)
 469                                 if (w - d >= e) {       /* (this test assumes unsigned comparison) */
 470                                         memcpy(window + w, window + d, e);
 471                                         w += e;
 472                                         d += e;
 473                                 } else                  /* do it slow to avoid memcpy() overlap */
 474 #endif                                                  /* !NOMEMCPY */
 475                                         do {
 476                                                 window[w++] = window[d++];
 477                                         } while (--e);
 478                                 if (w == WSIZE) {
 479                                         outcnt=(w),
 480                                         flush_window();
 481                                         w = 0;
 482                                 }
 483                         } while (n);
 484                 }
 485         }
 486
 487         /* restore the globals from the locals */
 488         outcnt = w;                     /* restore global window pointer */
 489         bb = b;                         /* restore global bit buffer */
 490         bk = k;
 491
 492         /* done */
 493         return 0;
 494 }
 495
 496 /*
 497  * decompress an inflated block
 498  * e: last block flag
 499  *
 500  * GLOBAL VARIABLES: bb, kk,
 501  */
 502 static int inflate_block(int *e)
 503 {
 504         unsigned t;                     /* block type */
 505         register unsigned long b;                       /* bit buffer */
 506         register unsigned k;            /* number of bits in bit buffer */
 507         static unsigned short cplens[] = {              /* Copy lengths for literal codes 257..285 */
 508                 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
 509                 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0
 510         };
 511         /* note: see note #13 above about the 258 in this list. */
 512         static unsigned short cplext[] = {              /* Extra bits for literal codes 257..285 */
 513                 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
 514                 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 99, 99
 515         };                              /* 99==invalid */
 516         static unsigned short cpdist[] = {              /* Copy offsets for distance codes 0..29 */
 517                 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
 518                 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
 519                 8193, 12289, 16385, 24577
 520         };
 521         static unsigned short cpdext[] = {              /* Extra bits for distance codes */
 522                 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
 523                 7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
 524                 12, 12, 13, 13
 525         };
 526
 527         /* make local bit buffer */
 528         b = bb;
 529         k = bk;
 530
 531         /* read in last block bit */
 532         while (k < 1) {
 533                 b |= ((unsigned long)fgetc(in_file)) << k;
 534                 k += 8;
 535         }
 536         *e = (int) b & 1;
 537         b >>= 1;
 538         k -= 1;
 539
 540         /* read in block type */
 541         while (k < 2) {
 542                 b |= ((unsigned long)fgetc(in_file)) << k;
 543                 k += 8;
 544         }
 545         t = (unsigned) b & 3;
 546         b >>= 2;
 547         k -= 2;
 548
 549         /* restore the global bit buffer */
 550         bb = b;
 551         bk = k;
 552
 553         /* inflate that block type */
 554         switch (t) {
 555         case 0: /* Inflate stored */
 556                 {
 557                         unsigned long n;                        /* number of bytes in block */
 558                         unsigned long w;                        /* current window position */
 559                         register unsigned long b_stored;                        /* bit buffer */
 560                         register unsigned long k_stored;                /* number of bits in bit buffer */
 561
 562                         /* make local copies of globals */
 563                         b_stored = bb;                          /* initialize bit buffer */
 564                         k_stored = bk;
 565                         w = outcnt;                     /* initialize window position */
 566
 567                         /* go to byte boundary */
 568                         n = k_stored & 7;
 569                         b_stored >>= n;
 570                         k_stored -= n;
 571
 572                         /* get the length and its complement */
 573                         while (k_stored < 16) {
 574                                 b_stored |= ((unsigned long)fgetc(in_file)) << k_stored;
 575                                 k_stored += 8;
 576                         }
 577                         n = ((unsigned) b_stored & 0xffff);
 578                         b_stored >>= 16;
 579                         k_stored -= 16;
 580                         while (k_stored < 16) {
 581                                 b_stored |= ((unsigned long)fgetc(in_file)) << k_stored;
 582                                 k_stored += 8;
 583                         }
 584                         if (n != (unsigned) ((~b_stored) & 0xffff)) {
 585                                 return 1;               /* error in compressed data */
 586                         }
 587                         b_stored >>= 16;
 588                         k_stored -= 16;
 589
 590                         /* read and output the compressed data */
 591                         while (n--) {
 592                                 while (k_stored < 8) {
 593                                         b_stored |= ((unsigned long)fgetc(in_file)) << k_stored;
 594                                         k_stored += 8;
 595                                 }
 596                                 window[w++] = (unsigned char) b_stored;
 597                                 if (w == (unsigned long)WSIZE) {
 598                                         outcnt=(w),
 599                                         flush_window();
 600                                         w = 0;
 601                                 }
 602                                 b_stored >>= 8;
 603                                 k_stored -= 8;
 604                         }
 605
 606                         /* restore the globals from the locals */
 607                         outcnt = w;                     /* restore global window pointer */
 608                         bb = b_stored;                          /* restore global bit buffer */
 609                         bk = k_stored;
 610                         return 0;
 611                 }
 612         case 1: /* Inflate fixed
 613                          * decompress an inflated type 1 (fixed Huffman codes) block.  We should
 614                          * either replace this with a custom decoder, or at least precompute the
 615                          * Huffman tables.
 616                          */
 617                 {
 618                         int i;                                  /* temporary variable */
 619                         huft_t *tl;                             /* literal/length code table */
 620                         huft_t *td;                             /* distance code table */
 621                         int bl;                                 /* lookup bits for tl */
 622                         int bd;                                 /* lookup bits for td */
 623                         unsigned int l[288];    /* length list for huft_build */
 624
 625                         /* set up literal table */
 626                         for (i = 0; i < 144; i++) {
 627                                 l[i] = 8;
 628                         }
 629                         for (; i < 256; i++) {
 630                                 l[i] = 9;
 631                         }
 632                         for (; i < 280; i++) {
 633                                 l[i] = 7;
 634                         }
 635                         for (; i < 288; i++) {  /* make a complete, but wrong code set */
 636                                 l[i] = 8;
 637                         }
 638                         bl = 7;
 639                         if ((i = huft_build(l, 288, 257, cplens, cplext, &tl, &bl)) != 0) {
 640                                 return i;
 641                         }
 642
 643                         /* set up distance table */
 644                         for (i = 0; i < 30; i++) {      /* make an incomplete code set */
 645                                 l[i] = 5;
 646                         }
 647                         bd = 5;
 648                         if ((i = huft_build(l, 30, 0, cpdist, cpdext, &td, &bd)) > 1) {
 649                                 huft_free(tl);
 650                                 return i;
 651                         }
 652
 653                         /* decompress until an end-of-block code */
 654                         if (inflate_codes(tl, td, bl, bd))
 655                                 return 1;
 656
 657                         /* free the decoding tables, return */
 658                         huft_free(tl);
 659                         huft_free(td);
 660                         return 0;
 661                 }
 662         case 2: /* Inflate dynamic */
 663                 {
 664                         /* Tables for deflate from PKZIP's appnote.txt. */
 665                         static unsigned border[] = {    /* Order of the bit length code lengths */
 666                                 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
 667                         };
 668                         int dbits = 6;                                  /* bits in base distance lookup table */
 669                         int lbits = 9;                                  /* bits in base literal/length lookup table */
 670
 671                         int i;                                          /* temporary variables */
 672                         unsigned j;
 673                         unsigned l;                                     /* last length */
 674                         unsigned m;                                     /* mask for bit lengths table */
 675                         unsigned n;                                     /* number of lengths to get */
 676                         huft_t *tl;                     /* literal/length code table */
 677                         huft_t *td;                     /* distance code table */
 678                         int bl;                                         /* lookup bits for tl */
 679                         int bd;                                         /* lookup bits for td */
 680                         unsigned nb;                            /* number of bit length codes */
 681                         unsigned nl;                            /* number of literal/length codes */
 682                         unsigned nd;                            /* number of distance codes */
 683
 684                         unsigned ll[286 + 30];          /* literal/length and distance code lengths */
 685                         register unsigned long b_dynamic;       /* bit buffer */
 686                         register unsigned k_dynamic;            /* number of bits in bit buffer */
 687
 688                         /* make local bit buffer */
 689                         b_dynamic = bb;
 690                         k_dynamic = bk;
 691
 692                         /* read in table lengths */
 693                         while (k_dynamic < 5) {
 694                                 b_dynamic |= ((unsigned long)fgetc(in_file)) << k_dynamic;
 695                                 k_dynamic += 8;
 696                         }
 697                         nl = 257 + ((unsigned) b_dynamic & 0x1f);       /* number of literal/length codes */
 698                         b_dynamic >>= 5;
 699                         k_dynamic -= 5;
 700                         while (k_dynamic < 5) {
 701                                 b_dynamic |= ((unsigned long)fgetc(in_file)) << k_dynamic;
 702                                 k_dynamic += 8;
 703                         }
 704                         nd = 1 + ((unsigned) b_dynamic & 0x1f); /* number of distance codes */
 705                         b_dynamic >>= 5;
 706                         k_dynamic -= 5;
 707                         while (k_dynamic < 4) {
 708                                 b_dynamic |= ((unsigned long)fgetc(in_file)) << k_dynamic;
 709                                 k_dynamic += 8;
 710                         }
 711                         nb = 4 + ((unsigned) b_dynamic & 0xf);  /* number of bit length codes */
 712                         b_dynamic >>= 4;
 713                         k_dynamic -= 4;
 714                         if (nl > 286 || nd > 30) {
 715                                 return 1;       /* bad lengths */
 716                         }
 717
 718                         /* read in bit-length-code lengths */
 719                         for (j = 0; j < nb; j++) {
 720                                 while (k_dynamic < 3) {
 721                                         b_dynamic |= ((unsigned long)fgetc(in_file)) << k_dynamic;
 722                                         k_dynamic += 8;
 723                                 }
 724                                 ll[border[j]] = (unsigned) b_dynamic & 7;
 725                                 b_dynamic >>= 3;
 726                                 k_dynamic -= 3;
 727                         }
 728                         for (; j < 19; j++) {
 729                                 ll[border[j]] = 0;
 730                         }
 731
 732                         /* build decoding table for trees--single level, 7 bit lookup */
 733                         bl = 7;
 734                         if ((i = huft_build(ll, 19, 19, NULL, NULL, &tl, &bl)) != 0) {
 735                                 if (i == 1) {
 736                                         huft_free(tl);
 737                                 }
 738                                 return i;                       /* incomplete code set */
 739                         }
 740
 741                         /* read in literal and distance code lengths */
 742                         n = nl + nd;
 743                         m = mask_bits[bl];
 744                         i = l = 0;
 745                         while ((unsigned) i < n) {
 746                                 while (k_dynamic < (unsigned) bl) {
 747                                         b_dynamic |= ((unsigned long)fgetc(in_file)) << k_dynamic;
 748                                         k_dynamic += 8;
 749                                 }
 750                                 j = (td = tl + ((unsigned) b_dynamic & m))->b;
 751                                 b_dynamic >>= j;
 752                                 k_dynamic -= j;
 753                                 j = td->v.n;
 754                                 if (j < 16) {                   /* length of code in bits (0..15) */
 755                                         ll[i++] = l = j;        /* save last length in l */
 756                                 }
 757                                 else if (j == 16) {             /* repeat last length 3 to 6 times */
 758                                         while (k_dynamic < 2) {
 759                                                 b_dynamic |= ((unsigned long)fgetc(in_file)) << k_dynamic;
 760                                                 k_dynamic += 8;
 761                                         }
 762                                         j = 3 + ((unsigned) b_dynamic & 3);
 763                                         b_dynamic >>= 2;
 764                                         k_dynamic -= 2;
 765                                         if ((unsigned) 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                                         while (k_dynamic < 3) {
 773                                                 b_dynamic |= ((unsigned long)fgetc(in_file)) << k_dynamic;
 774                                                 k_dynamic += 8;
 775                                         }
 776                                         j = 3 + ((unsigned) b_dynamic & 7);
 777                                         b_dynamic >>= 3;
 778                                         k_dynamic -= 3;
 779                                         if ((unsigned) i + j > n) {
 780                                                 return 1;
 781                                         }
 782                                         while (j--) {
 783                                                 ll[i++] = 0;
 784                                         }
 785                                         l = 0;
 786                                 } else {                /* j == 18: 11 to 138 zero length codes */
 787                                         while (k_dynamic < 7) {
 788                                                 b_dynamic |= ((unsigned long)fgetc(in_file)) << k_dynamic;
 789                                                 k_dynamic += 8;
 790                                         }
 791                                         j = 11 + ((unsigned) b_dynamic & 0x7f);
 792                                         b_dynamic >>= 7;
 793                                         k_dynamic -= 7;
 794                                         if ((unsigned) i + j > n) {
 795                                                 return 1;
 796                                         }
 797                                         while (j--) {
 798                                                 ll[i++] = 0;
 799                                         }
 800                                         l = 0;
 801                                 }
 802                         }
 803
 804                         /* free decoding table for trees */
 805                         huft_free(tl);
 806
 807                         /* restore the global bit buffer */
 808                         bb = b_dynamic;
 809                         bk = k_dynamic;
 810
 811                         /* build the decoding tables for literal/length and distance codes */
 812                         bl = lbits;
 813                         if ((i = huft_build(ll, nl, 257, cplens, cplext, &tl, &bl)) != 0) {
 814                                 if (i == 1) {
 815                                         error_msg("Incomplete literal tree");
 816                                         huft_free(tl);
 817                                 }
 818                                 return i;                       /* incomplete code set */
 819                         }
 820                         bd = dbits;
 821                         if ((i = huft_build(ll + nl, nd, 0, cpdist, cpdext, &td, &bd)) != 0) {
 822                                 if (i == 1) {
 823                                         error_msg("incomplete distance tree");
 824                                         huft_free(td);
 825                                 }
 826                                 huft_free(tl);
 827                                 return i;                       /* incomplete code set */
 828                         }
 829
 830                         /* decompress until an end-of-block code */
 831                         if (inflate_codes(tl, td, bl, bd))
 832                                 return 1;
 833
 834                         /* free the decoding tables, return */
 835                         huft_free(tl);
 836                         huft_free(td);
 837                         return 0;
 838                 }
 839         default:
 840                 /* bad block type */
 841                 return 2;
 842         }
 843 }
 844
 845 /*
 846  * decompress an inflated entry
 847  *
 848  * GLOBAL VARIABLES: outcnt, bk, bb, hufts, inptr
 849  */
 850 static int inflate(void)
 851 {
 852         int e;                          /* last block flag */
 853         int r;                          /* result code */
 854         unsigned h = 0;         /* maximum struct huft's malloc'ed */
 855
 856         /* initialize window, bit buffer */
 857         outcnt = 0;
 858         bk = 0;
 859         bb = 0;
 860
 861         /* decompress until the last block */
 862         do {
 863                 hufts = 0;
 864                 if ((r = inflate_block(&e)) != 0) {
 865                         return r;
 866                 }
 867                 if (hufts > h) {
 868                         h = hufts;
 869                 }
 870         } while (!e);
 871
 872         /* Undo too much lookahead. The next read will be byte aligned so we
 873          * can discard unused bits in the last meaningful byte.
 874          */
 875         while (bk >= 8) {
 876                 bk -= 8;
 877                 ungetc((bb << bk), in_file);
 878         }
 879
 880         /* flush out window */
 881         flush_window();
 882
 883         /* return success */
 884         return 0;
 885 }
 886
 887 /* ===========================================================================
 888  * Unzip in to out.  This routine works on both gzip and pkzip files.
 889  *
 890  * IN assertions: the buffer inbuf contains already the beginning of
 891  *   the compressed data, from offsets inptr to insize-1 included.
 892  *   The magic header has already been checked. The output buffer is cleared.
 893  * in, out: input and output file descriptors
 894  */
 895 extern int unzip(FILE *l_in_file, FILE *l_out_file)
 896 {
 897         const int extra_field = 0x04;   /* bit 2 set: extra field present */
 898         const int orig_name = 0x08;     /* bit 3 set: original file name present */
 899         const int comment = 0x10;       /* bit 4 set: file comment present */
 900         unsigned char buf[8];   /* extended local header */
 901         unsigned char flags;    /* compression flags */
 902         char magic[2];                  /* magic header */
 903         int method;
 904         typedef void (*sig_type) (int);
 905         int exit_code=0;        /* program exit code */
 906         int i;
 907
 908         in_file = l_in_file;
 909         out_file = l_out_file;
 910
 911         if (signal(SIGINT, SIG_IGN) != SIG_IGN) {
 912                 (void) signal(SIGINT, (sig_type) abort_gzip);
 913         }
 914 #ifdef SIGTERM
 915 //      if (signal(SIGTERM, SIG_IGN) != SIG_IGN) {
 916 //              (void) signal(SIGTERM, (sig_type) abort_gzip);
 917 //      }
 918 #endif
 919 #ifdef SIGHUP
 920         if (signal(SIGHUP, SIG_IGN) != SIG_IGN) {
 921                 (void) signal(SIGHUP, (sig_type) abort_gzip);
 922         }
 923 #endif
 924
 925         /* Allocate all global buffers (for DYN_ALLOC option) */
 926         window = xmalloc((size_t)(((2L*WSIZE)+1L)*sizeof(unsigned char)));
 927         outcnt = 0;
 928         bytes_out = 0L;
 929
 930         magic[0] = fgetc(in_file);
 931         magic[1] = fgetc(in_file);
 932
 933         /* Magic header for gzip files, 1F 8B = \037\213 */
 934         if (memcmp(magic, "\037\213", 2) != 0) {
 935                 error_msg("Invalid gzip magic");
 936                 return EXIT_FAILURE;
 937         }
 938
 939         method = (int) fgetc(in_file);
 940         if (method != 8) {
 941                 error_msg("unknown method %d -- get newer version of gzip", method);
 942                 exit_code = 1;
 943                 return -1;
 944         }
 945
 946         flags = (unsigned char) fgetc(in_file);
 947
 948         /* Ignore time stamp(4), extra flags(1), OS type(1) */
 949         for (i = 0; i < 6; i++)
 950                 fgetc(in_file);
 951
 952         if ((flags & extra_field) != 0) {
 953                 size_t extra;
 954                 extra = fgetc(in_file);
 955                 extra += fgetc(in_file) << 8;
 956
 957                 for (i = 0; i < extra; i++)
 958                         fgetc(in_file);
 959         }
 960
 961         /* Discard original name if any */
 962         if ((flags & orig_name) != 0) {
 963                 while (fgetc(in_file) != 0);    /* null */
 964         }
 965
 966         /* Discard file comment if any */
 967         if ((flags & comment) != 0) {
 968                 while (fgetc(in_file) != 0);    /* null */
 969         }
 970
 971         if (method < 0) {
 972                 printf("it failed\n");
 973                 return(exit_code);              /* error message already emitted */
 974         }
 975
 976         make_crc_table();
 977
 978         /* Decompress */
 979         if (method == 8) {
 980
 981                 int res = inflate();
 982
 983                 if (res == 3) {
 984                         error_msg(memory_exhausted);
 985                 } else if (res != 0) {
 986                         error_msg("invalid compressed data--format violated");
 987                 }
 988
 989         } else {
 990                 error_msg("internal error, invalid method");
 991         }
 992
 993         /* Get the crc and original length
 994          * crc32  (see algorithm.doc)
 995          * uncompressed input size modulo 2^32
 996          */
 997         fread(buf, 1, 8, in_file);
 998
 999         /* Validate decompression - crc */
1000         if ((unsigned int)((buf[0] | (buf[1] << 8)) |((buf[2] | (buf[3] << 8)) << 16)) != (crc ^ 0xffffffffL)) {
1001                 error_msg("invalid compressed data--crc error");
1002         }
1003         /* Validate decompression - size */
1004         if (((buf[4] | (buf[5] << 8)) |((buf[6] | (buf[7] << 8)) << 16)) != (unsigned long) bytes_out) {
1005                 error_msg("invalid compressed data--length error");
1006         }
1007
1008         free(window);
1009         free(crc_table);
1010
1011         return 0;
1012 }
1013
1014 /*
1015  * This needs access to global variables wondow and crc_table, so its not in its own file.
1016  */
1017 extern void gz_close(int gunzip_pid)
1018 {
1019         if (kill(gunzip_pid, SIGTERM) == -1) {
1020                 error_msg_and_die("***  Couldnt kill old gunzip process *** aborting");
1021         }
1022
1023         if (waitpid(gunzip_pid, NULL, 0) == -1) {
1024                 printf("Couldnt wait ?");
1025         }
1026                 free(window);
1027                 free(crc_table);
1028 }