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