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