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