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