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