archival/gunzip.c

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