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