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