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