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