archival/gunzip.c

   1 /* vi: set sw=4 ts=4: */
   2 /*
   3  * Gzip implementation for busybox
   4  *
   5  * Based on GNU gzip 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 <andersen@lineo.com>, <andersee@debian.org>
  11  * to support files as well as stdin/stdout, and to generally behave itself wrt
  12  * command line handling.
  13  *
  14  * This program is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU General Public License as published by
  16  * the Free Software Foundation; either version 2 of the License, or
  17  * (at your option) any later version.
  18  *
  19  * This program is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  22  * General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU General Public License
  25  * along with this program; if not, write to the Free Software
  26  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  27  *
  28  */
  29
  30 #include "internal.h"
  31 static const char gunzip_usage[] =
  32         "gunzip [OPTION]... FILE\n\n"
  33         "Uncompress FILE (or standard input if FILE is '-').\n\n"
  34         "Options:\n"
  35
  36         "\t-c\tWrite output to standard output\n"
  37         "\t-t\tTest compressed file integrity\n";
  38
  39
  40         /* These defines are very important for BusyBox.  Without these,
  41  * huge chunks of ram are pre-allocated making the BusyBox bss
  42  * size Freaking Huge(tm), which is a bad thing.*/
  43 #define SMALL_MEM
  44 #define DYN_ALLOC
  45
  46 #define bb_need_name_too_long
  47 #define BB_DECLARE_EXTERN
  48 #include "messages.c"
  49
  50
  51 /* gzip (GNU zip) -- compress files with zip algorithm and 'compress' interface
  52  * Copyright (C) 1992-1993 Jean-loup Gailly
  53  * The unzip code was written and put in the public domain by Mark Adler.
  54  * Portions of the lzw code are derived from the public domain 'compress'
  55  * written by Spencer Thomas, Joe Orost, James Woods, Jim McKie, Steve Davies,
  56  * Ken Turkowski, Dave Mack and Peter Jannesen.
  57  *
  58  * See the license_msg below and the file COPYING for the software license.
  59  * See the file algorithm.doc for the compression algorithms and file formats.
  60  */
  61
  62 #if 0
  63 static char *license_msg[] = {
  64         "   Copyright (C) 1992-1993 Jean-loup Gailly",
  65         "   This program is free software; you can redistribute it and/or modify",
  66         "   it under the terms of the GNU General Public License as published by",
  67         "   the Free Software Foundation; either version 2, or (at your option)",
  68         "   any later version.",
  69         "",
  70         "   This program is distributed in the hope that it will be useful,",
  71         "   but WITHOUT ANY WARRANTY; without even the implied warranty of",
  72         "   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the",
  73         "   GNU General Public License for more details.",
  74         "",
  75         "   You should have received a copy of the GNU General Public License",
  76         "   along with this program; if not, write to the Free Software",
  77         "   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.",
  78         0
  79 };
  80 #endif
  81
  82 /* Compress files with zip algorithm and 'compress' interface.
  83  * See usage() and help() functions below for all options.
  84  * Outputs:
  85  *        file.gz:   compressed file with same mode, owner, and utimes
  86  *     or stdout with -c option or if stdin used as input.
  87  * If the output file name had to be truncated, the original name is kept
  88  * in the compressed file.
  89  * On MSDOS, file.tmp -> file.tmz. On VMS, file.tmp -> file.tmp-gz.
  90  *
  91  * Using gz on MSDOS would create too many file name conflicts. For
  92  * example, foo.txt -> foo.tgz (.tgz must be reserved as shorthand for
  93  * tar.gz). Similarly, foo.dir and foo.doc would both be mapped to foo.dgz.
  94  * I also considered 12345678.txt -> 12345txt.gz but this truncates the name
  95  * too heavily. There is no ideal solution given the MSDOS 8+3 limitation.
  96  *
  97  * For the meaning of all compilation flags, see comments in Makefile.in.
  98  */
  99
 100 #include <ctype.h>
 101 #include <sys/types.h>
 102 #include <signal.h>
 103 #include <sys/stat.h>
 104 #include <errno.h>
 105
 106 /* #include "tailor.h" */
 107
 108 /* tailor.h -- target dependent definitions
 109  * Copyright (C) 1992-1993 Jean-loup Gailly.
 110  * This is free software; you can redistribute it and/or modify it under the
 111  * terms of the GNU General Public License, see the file COPYING.
 112  */
 113
 114 /* The target dependent definitions should be defined here only.
 115  * The target dependent functions should be defined in tailor.c.
 116  */
 117
 118 #define RECORD_IO 0
 119
 120 #define get_char() get_byte()
 121 #define put_char(c) put_byte(c)
 122
 123
 124 /* I don't like nested includes, but the string and io functions are used
 125  * too often
 126  */
 127 #include <stdio.h>
 128 #if !defined(NO_STRING_H) || defined(STDC_HEADERS)
 129 #  include <string.h>
 130 #  if !defined(STDC_HEADERS) && !defined(NO_MEMORY_H) && !defined(__GNUC__)
 131 #    include <memory.h>
 132 #  endif
 133 #  define memzero(s, n)     memset ((void *)(s), 0, (n))
 134 #else
 135 #  include <strings.h>
 136 #  define strchr            index
 137 #  define strrchr           rindex
 138 #  define memcpy(d, s, n)   bcopy((s), (d), (n))
 139 #  define memcmp(s1, s2, n) bcmp((s1), (s2), (n))
 140 #  define memzero(s, n)     bzero((s), (n))
 141 #endif
 142
 143 #ifndef RETSIGTYPE
 144 #  define RETSIGTYPE void
 145 #endif
 146
 147 #define local static
 148
 149 typedef unsigned char uch;
 150 typedef unsigned short ush;
 151 typedef unsigned long ulg;
 152
 153 /* Return codes from gzip */
 154 #define OK      0
 155 #define ERROR   1
 156 #define WARNING 2
 157
 158 /* Compression methods (see algorithm.doc) */
 159 #define DEFLATED    8
 160
 161 extern int method;                              /* compression method */
 162
 163 /* To save memory for 16 bit systems, some arrays are overlaid between
 164  * the various modules:
 165  * deflate:  prev+head   window      d_buf  l_buf  outbuf
 166  * unlzw:    tab_prefix  tab_suffix  stack  inbuf  outbuf
 167  * inflate:              window             inbuf
 168  * unpack:               window             inbuf  prefix_len
 169  * unlzh:    left+right  window      c_table inbuf c_len
 170  * For compression, input is done in window[]. For decompression, output
 171  * is done in window except for unlzw.
 172  */
 173
 174 #ifndef INBUFSIZ
 175 #  ifdef SMALL_MEM
 176 #    define INBUFSIZ  0x2000    /* input buffer size */
 177 #  else
 178 #    define INBUFSIZ  0x8000    /* input buffer size */
 179 #  endif
 180 #endif
 181 #define INBUF_EXTRA  64                 /* required by unlzw() */
 182
 183 #ifndef OUTBUFSIZ
 184 #  ifdef SMALL_MEM
 185 #    define OUTBUFSIZ   8192    /* output buffer size */
 186 #  else
 187 #    define OUTBUFSIZ  16384    /* output buffer size */
 188 #  endif
 189 #endif
 190 #define OUTBUF_EXTRA 2048               /* required by unlzw() */
 191
 192 #define SMALL_MEM
 193
 194 #ifndef DIST_BUFSIZE
 195 #  ifdef SMALL_MEM
 196 #    define DIST_BUFSIZE 0x2000 /* buffer for distances, see trees.c */
 197 #  else
 198 #    define DIST_BUFSIZE 0x8000 /* buffer for distances, see trees.c */
 199 #  endif
 200 #endif
 201
 202 /*#define DYN_ALLOC*/
 203
 204 #ifdef DYN_ALLOC
 205 #  define EXTERN(type, array)  extern type * array
 206 #  define DECLARE(type, array, size)  type * array
 207 #  define ALLOC(type, array, size) { \
 208       array = (type*)calloc((size_t)(((size)+1L)/2), 2*sizeof(type)); \
 209       if (array == NULL) errorMsg("insufficient memory"); \
 210    }
 211 #  define FREE(array) {if (array != NULL) free(array), array=NULL;}
 212 #else
 213 #  define EXTERN(type, array)  extern type array[]
 214 #  define DECLARE(type, array, size)  type array[size]
 215 #  define ALLOC(type, array, size)
 216 #  define FREE(array)
 217 #endif
 218
 219 EXTERN(uch, inbuf);                             /* input buffer */
 220 EXTERN(uch, outbuf);                    /* output buffer */
 221 EXTERN(ush, d_buf);                             /* buffer for distances, see trees.c */
 222 EXTERN(uch, window);                    /* Sliding window and suffix table (unlzw) */
 223 #define tab_suffix window
 224 #ifndef MAXSEG_64K
 225 #  define tab_prefix prev               /* hash link (see deflate.c) */
 226 #  define head (prev+WSIZE)             /* hash head (see deflate.c) */
 227 EXTERN(ush, tab_prefix);                /* prefix code (see unlzw.c) */
 228 #else
 229 #  define tab_prefix0 prev
 230 #  define head tab_prefix1
 231 EXTERN(ush, tab_prefix0);               /* prefix for even codes */
 232 EXTERN(ush, tab_prefix1);               /* prefix for odd  codes */
 233 #endif
 234
 235 extern unsigned insize;                 /* valid bytes in inbuf */
 236 extern unsigned inptr;                  /* index of next byte to be processed in inbuf */
 237 extern unsigned outcnt;                 /* bytes in output buffer */
 238
 239 extern long bytes_in;                   /* number of input bytes */
 240 extern long bytes_out;                  /* number of output bytes */
 241 extern long header_bytes;               /* number of bytes in gzip header */
 242
 243 extern long ifile_size;                 /* input file size, -1 for devices (debug only) */
 244
 245 typedef int file_t;                             /* Do not use stdio */
 246
 247 #define NO_FILE  (-1)                   /* in memory compression */
 248
 249
 250 #define GZIP_MAGIC     "\037\213"       /* Magic header for gzip files, 1F 8B */
 251
 252 /* gzip flag byte */
 253 #define ASCII_FLAG   0x01               /* bit 0 set: file probably ascii text */
 254 #define CONTINUATION 0x02               /* bit 1 set: continuation of multi-part gzip file */
 255 #define EXTRA_FIELD  0x04               /* bit 2 set: extra field present */
 256 #define ORIG_NAME    0x08               /* bit 3 set: original file name present */
 257 #define COMMENT      0x10               /* bit 4 set: file comment present */
 258 #define ENCRYPTED    0x20               /* bit 5 set: file is encrypted */
 259 #define RESERVED     0xC0               /* bit 6,7:   reserved */
 260
 261 #ifndef WSIZE
 262 #  define WSIZE 0x8000                  /* window size--must be a power of two, and */
 263 #endif                                                  /*  at least 32K for zip's deflate method */
 264
 265 #define MIN_MATCH  3
 266 #define MAX_MATCH  258
 267 /* The minimum and maximum match lengths */
 268
 269 #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
 270 /* Minimum amount of lookahead, except at the end of the input file.
 271  * See deflate.c for comments about the MIN_MATCH+1.
 272  */
 273
 274 #define MAX_DIST  (WSIZE-MIN_LOOKAHEAD)
 275 /* In order to simplify the code, particularly on 16 bit machines, match
 276  * distances are limited to MAX_DIST instead of WSIZE.
 277  */
 278
 279 extern int exit_code;                   /* program exit code */
 280 extern int verbose;                             /* be verbose (-v) */
 281 extern int level;                               /* compression level */
 282 extern int test;                                /* check .z file integrity */
 283 extern int save_orig_name;              /* set if original name must be saved */
 284
 285 #define get_byte()  (inptr < insize ? inbuf[inptr++] : fill_inbuf(0))
 286 #define try_byte()  (inptr < insize ? inbuf[inptr++] : fill_inbuf(1))
 287
 288 /* put_byte is used for the compressed output, put_ubyte for the
 289  * uncompressed output. However unlzw() uses window for its
 290  * suffix table instead of its output buffer, so it does not use put_ubyte
 291  * (to be cleaned up).
 292  */
 293 #define put_byte(c) {outbuf[outcnt++]=(uch)(c); if (outcnt==OUTBUFSIZ)\
 294    flush_outbuf();}
 295 #define put_ubyte(c) {window[outcnt++]=(uch)(c); if (outcnt==WSIZE)\
 296    flush_window();}
 297
 298 /* Output a 16 bit value, lsb first */
 299 #define put_short(w) \
 300 { if (outcnt < OUTBUFSIZ-2) { \
 301     outbuf[outcnt++] = (uch) ((w) & 0xff); \
 302     outbuf[outcnt++] = (uch) ((ush)(w) >> 8); \
 303   } else { \
 304     put_byte((uch)((w) & 0xff)); \
 305     put_byte((uch)((ush)(w) >> 8)); \
 306   } \
 307 }
 308
 309 /* Output a 32 bit value to the bit stream, lsb first */
 310 #define put_long(n) { \
 311     put_short((n) & 0xffff); \
 312     put_short(((ulg)(n)) >> 16); \
 313 }
 314
 315 #define seekable()    0                 /* force sequential output */
 316 #define translate_eol 0                 /* no option -a yet */
 317
 318 #define tolow(c)  (isupper(c) ? (c)-'A'+'a' : (c))      /* force to lower case */
 319
 320 /* Macros for getting two-byte and four-byte header values */
 321 #define SH(p) ((ush)(uch)((p)[0]) | ((ush)(uch)((p)[1]) << 8))
 322 #define LG(p) ((ulg)(SH(p)) | ((ulg)(SH((p)+2)) << 16))
 323
 324 /* Diagnostic functions */
 325 #ifdef DEBUG
 326 #  define Assert(cond,msg) {if(!(cond)) errorMsg(msg);}
 327 #  define Trace(x) fprintf x
 328 #  define Tracev(x) {if (verbose) fprintf x ;}
 329 #  define Tracevv(x) {if (verbose>1) fprintf x ;}
 330 #  define Tracec(c,x) {if (verbose && (c)) fprintf x ;}
 331 #  define Tracecv(c,x) {if (verbose>1 && (c)) fprintf x ;}
 332 #else
 333 #  define Assert(cond,msg)
 334 #  define Trace(x)
 335 #  define Tracev(x)
 336 #  define Tracevv(x)
 337 #  define Tracec(c,x)
 338 #  define Tracecv(c,x)
 339 #endif
 340
 341 #define WARN(msg) {fprintf msg ; \
 342                    if (exit_code == OK) exit_code = WARNING;}
 343
 344         /* in unzip.c */
 345 extern int unzip (int in, int out);
 346
 347         /* in gzip.c */
 348 RETSIGTYPE abort_gzip (void);
 349
 350                 /* in deflate.c */
 351 void lm_init (int pack_level, ush * flags);
 352 ulg deflate (void);
 353
 354                 /* in trees.c */
 355 void ct_init (ush * attr, int *method);
 356 int ct_tally (int dist, int lc);
 357 ulg flush_block (char *buf, ulg stored_len, int eof);
 358
 359                 /* in bits.c */
 360 void bi_init (file_t zipfile);
 361 void send_bits (int value, int length);
 362 unsigned bi_reverse (unsigned value, int length);
 363 void bi_windup (void);
 364 void copy_block (char *buf, unsigned len, int header);
 365 extern int (*read_buf) (char *buf, unsigned size);
 366
 367         /* in util.c: */
 368 extern int copy (int in, int out);
 369 extern ulg updcrc (uch * s, unsigned n);
 370 extern void clear_bufs (void);
 371 extern int fill_inbuf (int eof_ok);
 372 extern void flush_outbuf (void);
 373 extern void flush_window (void);
 374 extern void write_buf (int fd, void * buf, unsigned cnt);
 375
 376 #ifndef __linux__
 377 extern char *basename (char *fname);
 378 #endif                                                  /* not __linux__ */
 379 extern void read_error (void);
 380 extern void write_error (void);
 381
 382         /* in inflate.c */
 383 extern int inflate (void);
 384
 385 /* #include "lzw.h" */
 386
 387 /* lzw.h -- define the lzw functions.
 388  * Copyright (C) 1992-1993 Jean-loup Gailly.
 389  * This is free software; you can redistribute it and/or modify it under the
 390  * terms of the GNU General Public License, see the file COPYING.
 391  */
 392
 393 #if !defined(OF) && defined(lint)
 394 #  include "gzip.h"
 395 #endif
 396
 397 #ifndef BITS
 398 #  define BITS 16
 399 #endif
 400 #define INIT_BITS 9                             /* Initial number of bits per code */
 401
 402 #define LZW_MAGIC  "\037\235"   /* Magic header for lzw files, 1F 9D */
 403
 404 #define BIT_MASK    0x1f                /* Mask for 'number of compression bits' */
 405 /* Mask 0x20 is reserved to mean a fourth header byte, and 0x40 is free.
 406  * It's a pity that old uncompress does not check bit 0x20. That makes
 407  * extension of the format actually undesirable because old compress
 408  * would just crash on the new format instead of giving a meaningful
 409  * error message. It does check the number of bits, but it's more
 410  * helpful to say "unsupported format, get a new version" than
 411  * "can only handle 16 bits".
 412  */
 413
 414 #define BLOCK_MODE  0x80
 415 /* Block compression: if table is full and compression rate is dropping,
 416  * clear the dictionary.
 417  */
 418
 419 #define LZW_RESERVED 0x60               /* reserved bits */
 420
 421 #define CLEAR  256                              /* flush the dictionary */
 422 #define FIRST  (CLEAR+1)                /* first free entry */
 423
 424 extern int maxbits;                             /* max bits per code for LZW */
 425 extern int block_mode;                  /* block compress mode -C compatible with 2.0 */
 426
 427 extern int lzw (int in, int out);
 428 extern int unlzw (int in, int out);
 429
 430
 431 /* #include "revision.h" */
 432
 433 /* revision.h -- define the version number
 434  * Copyright (C) 1992-1993 Jean-loup Gailly.
 435  * This is free software; you can redistribute it and/or modify it under the
 436  * terms of the GNU General Public License, see the file COPYING.
 437  */
 438
 439 #define VERSION "1.2.4"
 440 #define PATCHLEVEL 0
 441 #define REVDATE "18 Aug 93"
 442
 443 /* This version does not support compression into old compress format: */
 444 #ifdef LZW
 445 #  undef LZW
 446 #endif
 447
 448 /* #include "getopt.h" */
 449
 450 /* Declarations for getopt.
 451    Copyright (C) 1989, 1990, 1991, 1992, 1993 Free Software Foundation, Inc.
 452
 453    This program is free software; you can redistribute it and/or modify it
 454    under the terms of the GNU General Public License as published by the
 455    Free Software Foundation; either version 2, or (at your option) any
 456    later version.
 457
 458    This program is distributed in the hope that it will be useful,
 459    but WITHOUT ANY WARRANTY; without even the implied warranty of
 460    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 461    GNU General Public License for more details.
 462
 463    You should have received a copy of the GNU General Public License
 464    along with this program; if not, write to the Free Software
 465    Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
 466
 467 #ifndef _GETOPT_H
 468 #define _GETOPT_H 1
 469
 470 #ifdef  __cplusplus
 471 extern "C" {
 472 #endif
 473 /* For communication from `getopt' to the caller.
 474    When `getopt' finds an option that takes an argument,
 475    the argument value is returned here.
 476    Also, when `ordering' is RETURN_IN_ORDER,
 477    each non-option ARGV-element is returned here.  */
 478                 extern char *optarg;
 479
 480 /* Index in ARGV of the next element to be scanned.
 481    This is used for communication to and from the caller
 482    and for communication between successive calls to `getopt'.
 483
 484    On entry to `getopt', zero means this is the first call; initialize.
 485
 486    When `getopt' returns EOF, this is the index of the first of the
 487    non-option elements that the caller should itself scan.
 488
 489    Otherwise, `optind' communicates from one call to the next
 490    how much of ARGV has been scanned so far.  */
 491
 492         extern int optind;
 493
 494 /* Callers store zero here to inhibit the error message `getopt' prints
 495    for unrecognized options.  */
 496
 497         extern int opterr;
 498
 499 /* Set to an option character which was unrecognized.  */
 500
 501         extern int optopt;
 502
 503 /* Describe the long-named options requested by the application.
 504    The LONG_OPTIONS argument to getopt_long or getopt_long_only is a vector
 505    of `struct option' terminated by an element containing a name which is
 506    zero.
 507
 508    The field `has_arg' is:
 509    no_argument          (or 0) if the option does not take an argument,
 510    required_argument    (or 1) if the option requires an argument,
 511    optional_argument    (or 2) if the option takes an optional argument.
 512
 513    If the field `flag' is not NULL, it points to a variable that is set
 514    to the value given in the field `val' when the option is found, but
 515    left unchanged if the option is not found.
 516
 517    To have a long-named option do something other than set an `int' to
 518    a compiled-in constant, such as set a value from `optarg', set the
 519    option's `flag' field to zero and its `val' field to a nonzero
 520    value (the equivalent single-letter option character, if there is
 521    one).  For long options that have a zero `flag' field, `getopt'
 522    returns the contents of the `val' field.  */
 523
 524         struct option {
 525 #if     __STDC__
 526                 const char *name;
 527 #else
 528                 char *name;
 529 #endif
 530                 /* has_arg can't be an enum because some compilers complain about
 531                    type mismatches in all the code that assumes it is an int.  */
 532                 int has_arg;
 533                 int *flag;
 534                 int val;
 535         };
 536
 537 /* Names for the values of the `has_arg' field of `struct option'.  */
 538
 539 #define no_argument             0
 540 #define required_argument       1
 541 #define optional_argument       2
 542
 543 #if __STDC__ || defined(PROTO)
 544 #if defined(__GNU_LIBRARY__)
 545 /* Many other libraries have conflicting prototypes for getopt, with
 546    differences in the consts, in stdlib.h.  To avoid compilation
 547    errors, only prototype getopt for the GNU C library.  */
 548         extern int getopt(int argc, char *const *argv, const char *shortopts);
 549 #endif                                                  /* not __GNU_LIBRARY__ */
 550         extern int getopt_long(int argc, char *const *argv,
 551                                                    const char *shortopts,
 552                                                    const struct option *longopts, int *longind);
 553         extern int getopt_long_only(int argc, char *const *argv,
 554                                                                 const char *shortopts,
 555                                                                 const struct option *longopts,
 556                                                                 int *longind);
 557
 558 /* Internal only.  Users should not call this directly.  */
 559         extern int _getopt_internal(int argc, char *const *argv,
 560                                                                 const char *shortopts,
 561                                                                 const struct option *longopts,
 562                                                                 int *longind, int long_only);
 563 #else                                                   /* not __STDC__ */
 564         extern int getopt();
 565         extern int getopt_long();
 566         extern int getopt_long_only();
 567
 568         extern int _getopt_internal();
 569 #endif                                                  /* not __STDC__ */
 570
 571 #ifdef  __cplusplus
 572 }
 573 #endif
 574 #endif                                                  /* _GETOPT_H */
 575 #include <time.h>
 576 #include <fcntl.h>
 577 #include <unistd.h>
 578 #include <stdlib.h>
 579 #if defined(DIRENT)
 580 #  include <dirent.h>
 581 typedef struct dirent dir_type;
 582
 583 #  define NLENGTH(dirent) ((int)strlen((dirent)->d_name))
 584 #  define DIR_OPT "DIRENT"
 585 #else
 586 #  define NLENGTH(dirent) ((dirent)->d_namlen)
 587 #  ifdef SYSDIR
 588 #    include <sys/dir.h>
 589 typedef struct direct dir_type;
 590
 591 #    define DIR_OPT "SYSDIR"
 592 #  else
 593 #    ifdef SYSNDIR
 594 #      include <sys/ndir.h>
 595 typedef struct direct dir_type;
 596
 597 #      define DIR_OPT "SYSNDIR"
 598 #    else
 599 #      ifdef NDIR
 600 #        include <ndir.h>
 601 typedef struct direct dir_type;
 602
 603 #        define DIR_OPT "NDIR"
 604 #      else
 605 #        define NO_DIR
 606 #        define DIR_OPT "NO_DIR"
 607 #      endif
 608 #    endif
 609 #  endif
 610 #endif
 611 #if !defined(S_ISDIR) && defined(S_IFDIR)
 612 #  define S_ISDIR(m) (((m) & S_IFMT) == S_IFDIR)
 613 #endif
 614 #if !defined(S_ISREG) && defined(S_IFREG)
 615 #  define S_ISREG(m) (((m) & S_IFMT) == S_IFREG)
 616 #endif
 617 typedef RETSIGTYPE(*sig_type) (int);
 618
 619 #ifndef O_BINARY
 620 #  define  O_BINARY  0                  /* creation mode for open() */
 621 #endif
 622
 623 #ifndef O_CREAT
 624    /* Pure BSD system? */
 625 #  include <sys/file.h>
 626 #  ifndef O_CREAT
 627 #    define O_CREAT FCREAT
 628 #  endif
 629 #  ifndef O_EXCL
 630 #    define O_EXCL FEXCL
 631 #  endif
 632 #endif
 633
 634 #ifndef S_IRUSR
 635 #  define S_IRUSR 0400
 636 #endif
 637 #ifndef S_IWUSR
 638 #  define S_IWUSR 0200
 639 #endif
 640 #define RW_USER (S_IRUSR | S_IWUSR)     /* creation mode for open() */
 641
 642 #ifndef MAX_PATH_LEN                    /* max pathname length */
 643 #  ifdef BUFSIZ
 644 #    define MAX_PATH_LEN   BUFSIZ
 645 #  else
 646 #    define MAX_PATH_LEN   1024
 647 #  endif
 648 #endif
 649
 650 #ifndef SEEK_END
 651 #  define SEEK_END 2
 652 #endif
 653
 654 #ifdef NO_OFF_T
 655 typedef long off_t;
 656 off_t lseek (int fd, off_t offset, int whence);
 657 #endif
 658
 659
 660                 /* global buffers */
 661
 662 DECLARE(uch, inbuf, INBUFSIZ + INBUF_EXTRA);
 663 DECLARE(uch, outbuf, OUTBUFSIZ + OUTBUF_EXTRA);
 664 DECLARE(ush, d_buf, DIST_BUFSIZE);
 665 DECLARE(uch, window, 2L * WSIZE);
 666 #ifndef MAXSEG_64K
 667 DECLARE(ush, tab_prefix, 1L << BITS);
 668 #else
 669 DECLARE(ush, tab_prefix0, 1L << (BITS - 1));
 670 DECLARE(ush, tab_prefix1, 1L << (BITS - 1));
 671 #endif
 672
 673                 /* local variables */
 674
 675 int test_mode = 0;                              /* check file integrity option */
 676 int foreground;                                 /* set if program run in foreground */
 677 int maxbits = BITS;                             /* max bits per code for LZW */
 678 int method = DEFLATED;                  /* compression method */
 679 int exit_code = OK;                             /* program exit code */
 680 int last_member;                                /* set for .zip and .Z files */
 681 int part_nb;                                    /* number of parts in .gz file */
 682 long ifile_size;                                /* input file size, -1 for devices (debug only) */
 683
 684 long bytes_in;                                  /* number of input bytes */
 685 long bytes_out;                                 /* number of output bytes */
 686 long total_in = 0;                              /* input bytes for all files */
 687 long total_out = 0;                             /* output bytes for all files */
 688 struct stat istat;                              /* status for input file */
 689 int ifd;                                                /* input file descriptor */
 690 int ofd;                                                /* output file descriptor */
 691 unsigned insize;                                /* valid bytes in inbuf */
 692 unsigned inptr;                                 /* index of next byte to be processed in inbuf */
 693 unsigned outcnt;                                /* bytes in output buffer */
 694
 695 long header_bytes;                              /* number of bytes in gzip header */
 696
 697 /* local functions */
 698
 699 local int get_method (int in);
 700
 701 #define strequ(s1, s2) (strcmp((s1),(s2)) == 0)
 702
 703 /* ======================================================================== */
 704 int gunzip_main(int argc, char **argv)
 705 {
 706         int file_count;                         /* number of files to precess */
 707         int to_stdout = 0;
 708         int fromstdin = 0;
 709         int result;
 710         int inFileNum;
 711         int outFileNum;
 712         int delInputFile = 0;
 713         struct stat statBuf;
 714         char *delFileName;
 715         char ifname[MAX_PATH_LEN + 1];  /* input file name */
 716         char ofname[MAX_PATH_LEN + 1];  /* output file name */
 717
 718         if (strcmp(*argv, "zcat") == 0) {
 719                 to_stdout = 1;
 720                 if (argc == 1) {
 721                         fromstdin = 1;
 722                 }
 723         }
 724
 725         /* Parse any options */
 726         while (--argc > 0 && **(++argv) == '-') {
 727                 if (*((*argv) + 1) == '\0') {
 728                         fromstdin = 1;
 729                         to_stdout = 1;
 730                 }
 731                 while (*(++(*argv))) {
 732                         switch (**argv) {
 733                         case 'c':
 734                                 to_stdout = 1;
 735                                 break;
 736                         case 't':
 737                                 test_mode = 1;
 738                                 break;
 739
 740                         default:
 741                                 usage(gunzip_usage);
 742                         }
 743                 }
 744         }
 745
 746         foreground = signal(SIGINT, SIG_IGN) != SIG_IGN;
 747         if (foreground) {
 748                 (void) signal(SIGINT, (sig_type) abort_gzip);
 749         }
 750 #ifdef SIGTERM
 751         if (signal(SIGTERM, SIG_IGN) != SIG_IGN) {
 752                 (void) signal(SIGTERM, (sig_type) abort_gzip);
 753         }
 754 #endif
 755 #ifdef SIGHUP
 756         if (signal(SIGHUP, SIG_IGN) != SIG_IGN) {
 757                 (void) signal(SIGHUP, (sig_type) abort_gzip);
 758         }
 759 #endif
 760
 761         file_count = argc - optind;
 762
 763         /* Allocate all global buffers (for DYN_ALLOC option) */
 764         ALLOC(uch, inbuf, INBUFSIZ + INBUF_EXTRA);
 765         ALLOC(uch, outbuf, OUTBUFSIZ + OUTBUF_EXTRA);
 766         ALLOC(ush, d_buf, DIST_BUFSIZE);
 767         ALLOC(uch, window, 2L * WSIZE);
 768 #ifndef MAXSEG_64K
 769         ALLOC(ush, tab_prefix, 1L << BITS);
 770 #else
 771         ALLOC(ush, tab_prefix0, 1L << (BITS - 1));
 772         ALLOC(ush, tab_prefix1, 1L << (BITS - 1));
 773 #endif
 774
 775         if (fromstdin == 1) {
 776                 strcpy(ofname, "stdin");
 777
 778                 inFileNum = fileno(stdin);
 779                 ifile_size = -1L;               /* convention for unknown size */
 780         } else {
 781                 /* Open up the input file */
 782                 if (*argv == '\0')
 783                         usage(gunzip_usage);
 784                 if (strlen(*argv) > MAX_PATH_LEN) {
 785                         fprintf(stderr, name_too_long, "gunzip");
 786                         exit(WARNING);
 787                 }
 788                 strcpy(ifname, *argv);
 789
 790                 /* Open input fille */
 791                 inFileNum = open(ifname, O_RDONLY);
 792                 if (inFileNum < 0) {
 793                         perror(ifname);
 794                         exit(WARNING);
 795                 }
 796                 /* Get the time stamp on the input file. */
 797                 result = stat(ifname, &statBuf);
 798                 if (result < 0) {
 799                         perror(ifname);
 800                         exit(WARNING);
 801                 }
 802                 ifile_size = statBuf.st_size;
 803         }
 804
 805         if (to_stdout == 1) {
 806                 /* And get to work */
 807                 strcpy(ofname, "stdout");
 808                 outFileNum = fileno(stdout);
 809
 810                 clear_bufs();                   /* clear input and output buffers */
 811                 part_nb = 0;
 812
 813                 /* Actually do the compression/decompression. */
 814                 unzip(inFileNum, outFileNum);
 815
 816         } else if (test_mode) {
 817                 /* Actually do the compression/decompression. */
 818                 unzip(inFileNum, 2);
 819         } else {
 820                 char *pos;
 821
 822                 /* And get to work */
 823                 if (strlen(ifname) > MAX_PATH_LEN - 4) {
 824                         fprintf(stderr, name_too_long, "gunzip");
 825                         exit(WARNING);
 826                 }
 827                 strcpy(ofname, ifname);
 828                 pos = strstr(ofname, ".gz");
 829                 if (pos != NULL) {
 830                         *pos = '\0';
 831                         delInputFile = 1;
 832                 } else {
 833                         pos = strstr(ofname, ".tgz");
 834                         if (pos != NULL) {
 835                                 *pos = '\0';
 836                                 strcat(pos, ".tar");
 837                                 delInputFile = 1;
 838                         }
 839                 }
 840
 841                 /* Open output fille */
 842 #if (__GLIBC__ >= 2) && (__GLIBC_MINOR__ >= 1)
 843                 outFileNum = open(ofname, O_RDWR | O_CREAT | O_EXCL | O_NOFOLLOW);
 844 #else
 845                 outFileNum = open(ofname, O_RDWR | O_CREAT | O_EXCL);
 846 #endif
 847                 if (outFileNum < 0) {
 848                         perror(ofname);
 849                         exit(WARNING);
 850                 }
 851                 /* Set permissions on the file */
 852                 fchmod(outFileNum, statBuf.st_mode);
 853
 854                 clear_bufs();                   /* clear input and output buffers */
 855                 part_nb = 0;
 856
 857                 /* Actually do the compression/decompression. */
 858                 result = unzip(inFileNum, outFileNum);
 859
 860                 close(outFileNum);
 861                 close(inFileNum);
 862                 /* Delete the original file */
 863                 if (result == OK)
 864                         delFileName = ifname;
 865                 else
 866                         delFileName = ofname;
 867
 868                 if (delInputFile == 1 && unlink(delFileName) < 0) {
 869                         perror(delFileName);
 870                         exit(FALSE);
 871                 }
 872         }
 873         exit(exit_code);
 874 }
 875
 876
 877 /* ========================================================================
 878  * Check the magic number of the input file and update ofname if an
 879  * original name was given and to_stdout is not set.
 880  * Return the compression method, -1 for error, -2 for warning.
 881  * Set inptr to the offset of the next byte to be processed.
 882  * Updates time_stamp if there is one and --no-time is not used.
 883  * This function may be called repeatedly for an input file consisting
 884  * of several contiguous gzip'ed members.
 885  * IN assertions: there is at least one remaining compressed member.
 886  *   If the member is a zip file, it must be the only one.
 887  */
 888 local int get_method(in)
 889 int in;                                                 /* input file descriptor */
 890 {
 891         uch flags;                                      /* compression flags */
 892         char magic[2];                          /* magic header */
 893
 894         magic[0] = (char) get_byte();
 895         magic[1] = (char) get_byte();
 896         method = -1;                            /* unknown yet */
 897         part_nb++;                                      /* number of parts in gzip file */
 898         header_bytes = 0;
 899         last_member = RECORD_IO;
 900         /* assume multiple members in gzip file except for record oriented I/O */
 901
 902         if (memcmp(magic, GZIP_MAGIC, 2) == 0) {
 903
 904                 method = (int) get_byte();
 905                 if (method != DEFLATED) {
 906                         fprintf(stderr,
 907                                         "unknown method %d -- get newer version of gzip\n",
 908                                         method);
 909                         exit_code = ERROR;
 910                         return -1;
 911                 }
 912                 flags = (uch) get_byte();
 913
 914                 (ulg) get_byte();               /* Ignore time stamp */
 915                 (ulg) get_byte();
 916                 (ulg) get_byte();
 917                 (ulg) get_byte();
 918
 919                 (void) get_byte();              /* Ignore extra flags for the moment */
 920                 (void) get_byte();              /* Ignore OS type for the moment */
 921
 922                 if ((flags & EXTRA_FIELD) != 0) {
 923                         unsigned len = (unsigned) get_byte();
 924
 925                         len |= ((unsigned) get_byte()) << 8;
 926
 927                         while (len--)
 928                                 (void) get_byte();
 929                 }
 930
 931                 /* Discard original name if any */
 932                 if ((flags & ORIG_NAME) != 0) {
 933                         while (get_char() != 0) /* null */
 934                                 ;
 935                 }
 936
 937                 /* Discard file comment if any */
 938                 if ((flags & COMMENT) != 0) {
 939                         while (get_char() != 0) /* null */
 940                                 ;
 941                 }
 942                 if (part_nb == 1) {
 943                         header_bytes = inptr + 2 * sizeof(long);        /* include crc and size */
 944                 }
 945
 946         }
 947
 948         if (method >= 0)
 949                 return method;
 950
 951         if (part_nb == 1) {
 952                 fprintf(stderr, "\nnot in gzip format\n");
 953                 exit_code = ERROR;
 954                 return -1;
 955         } else {
 956                 WARN((stderr, "\ndecompression OK, trailing garbage ignored\n"));
 957                 return -2;
 958         }
 959 }
 960
 961 /* ========================================================================
 962  * Signal and error handler.
 963  */
 964 RETSIGTYPE abort_gzip()
 965 {
 966         exit(ERROR);
 967 }
 968
 969 /* unzip.c -- decompress files in gzip or pkzip format.
 970  * Copyright (C) 1992-1993 Jean-loup Gailly
 971  * This is free software; you can redistribute it and/or modify it under the
 972  * terms of the GNU General Public License, see the file COPYING.
 973  *
 974  * The code in this file is derived from the file funzip.c written
 975  * and put in the public domain by Mark Adler.
 976  */
 977
 978 /*
 979    This version can extract files in gzip or pkzip format.
 980    For the latter, only the first entry is extracted, and it has to be
 981    either deflated or stored.
 982  */
 983
 984 /* #include "crypt.h" */
 985
 986 /* crypt.h (dummy version) -- do not perform encryption
 987  * Hardly worth copyrighting :-)
 988  */
 989
 990 #ifdef CRYPT
 991 #  undef CRYPT                                  /* dummy version */
 992 #endif
 993
 994 #define RAND_HEAD_LEN  12               /* length of encryption random header */
 995
 996 #define zencode
 997 #define zdecode
 998
 999 /* PKZIP header definitions */
1000 #define LOCSIG 0x04034b50L              /* four-byte lead-in (lsb first) */
1001 #define LOCFLG 6                                /* offset of bit flag */
1002 #define  CRPFLG 1                               /*  bit for encrypted entry */
1003 #define  EXTFLG 8                               /*  bit for extended local header */
1004 #define LOCHOW 8                                /* offset of compression method */
1005 #define LOCTIM 10                               /* file mod time (for decryption) */
1006 #define LOCCRC 14                               /* offset of crc */
1007 #define LOCSIZ 18                               /* offset of compressed size */
1008 #define LOCLEN 22                               /* offset of uncompressed length */
1009 #define LOCFIL 26                               /* offset of file name field length */
1010 #define LOCEXT 28                               /* offset of extra field length */
1011 #define LOCHDR 30                               /* size of local header, including sig */
1012 #define EXTHDR 16                               /* size of extended local header, inc sig */
1013
1014
1015 /* Globals */
1016
1017 char *key;                                              /* not used--needed to link crypt.c */
1018 int pkzip = 0;                                  /* set for a pkzip file */
1019 int ext_header = 0;                             /* set if extended local header */
1020
1021 /* ===========================================================================
1022  * Unzip in to out.  This routine works on both gzip and pkzip files.
1023  *
1024  * IN assertions: the buffer inbuf contains already the beginning of
1025  *   the compressed data, from offsets inptr to insize-1 included.
1026  *   The magic header has already been checked. The output buffer is cleared.
1027  */
1028 int unzip(in, out)
1029 int in, out;                                    /* input and output file descriptors */
1030 {
1031         ulg orig_crc = 0;                       /* original crc */
1032         ulg orig_len = 0;                       /* original uncompressed length */
1033         int n;
1034         uch buf[EXTHDR];                        /* extended local header */
1035
1036         ifd = in;
1037         ofd = out;
1038         method = get_method(ifd);
1039         if (method < 0) {
1040                 exit(exit_code);                /* error message already emitted */
1041         }
1042
1043         updcrc(NULL, 0);                        /* initialize crc */
1044
1045         if (pkzip && !ext_header) {     /* crc and length at the end otherwise */
1046                 orig_crc = LG(inbuf + LOCCRC);
1047                 orig_len = LG(inbuf + LOCLEN);
1048         }
1049
1050         /* Decompress */
1051         if (method == DEFLATED) {
1052
1053                 int res = inflate();
1054
1055                 if (res == 3) {
1056                         errorMsg("out of memory");
1057                 } else if (res != 0) {
1058                         errorMsg("invalid compressed data--format violated");
1059                 }
1060
1061         } else {
1062                 errorMsg("internal error, invalid method");
1063         }
1064
1065         /* Get the crc and original length */
1066         if (!pkzip) {
1067                 /* crc32  (see algorithm.doc)
1068                    * uncompressed input size modulo 2^32
1069                  */
1070                 for (n = 0; n < 8; n++) {
1071                         buf[n] = (uch) get_byte();      /* may cause an error if EOF */
1072                 }
1073                 orig_crc = LG(buf);
1074                 orig_len = LG(buf + 4);
1075
1076         } else if (ext_header) {        /* If extended header, check it */
1077                 /* signature - 4bytes: 0x50 0x4b 0x07 0x08
1078                  * CRC-32 value
1079                  * compressed size 4-bytes
1080                  * uncompressed size 4-bytes
1081                  */
1082                 for (n = 0; n < EXTHDR; n++) {
1083                         buf[n] = (uch) get_byte();      /* may cause an error if EOF */
1084                 }
1085                 orig_crc = LG(buf + 4);
1086                 orig_len = LG(buf + 12);
1087         }
1088
1089         /* Validate decompression */
1090         if (orig_crc != updcrc(outbuf, 0)) {
1091                 errorMsg("invalid compressed data--crc error");
1092         }
1093         if (orig_len != (ulg) bytes_out) {
1094                 errorMsg("invalid compressed data--length error");
1095         }
1096
1097         /* Check if there are more entries in a pkzip file */
1098         if (pkzip && inptr + 4 < insize && LG(inbuf + inptr) == LOCSIG) {
1099                 WARN((stderr, "has more than one entry--rest ignored\n"));
1100         }
1101         ext_header = pkzip = 0;         /* for next file */
1102         return OK;
1103 }
1104
1105 /* util.c -- utility functions for gzip support
1106  * Copyright (C) 1992-1993 Jean-loup Gailly
1107  * This is free software; you can redistribute it and/or modify it under the
1108  * terms of the GNU General Public License, see the file COPYING.
1109  */
1110
1111 #include <ctype.h>
1112 #include <errno.h>
1113 #include <sys/types.h>
1114
1115 #ifdef HAVE_UNISTD_H
1116 #  include <unistd.h>
1117 #endif
1118 #ifndef NO_FCNTL_H
1119 #  include <fcntl.h>
1120 #endif
1121
1122 #if defined(STDC_HEADERS) || !defined(NO_STDLIB_H)
1123 #  include <stdlib.h>
1124 #else
1125 extern int errno;
1126 #endif
1127
1128 static const ulg crc_32_tab[];  /* crc table, defined below */
1129
1130 /* ===========================================================================
1131  * Run a set of bytes through the crc shift register.  If s is a NULL
1132  * pointer, then initialize the crc shift register contents instead.
1133  * Return the current crc in either case.
1134  */
1135 ulg updcrc(s, n)
1136 uch *s;                                                 /* pointer to bytes to pump through */
1137 unsigned n;                                             /* number of bytes in s[] */
1138 {
1139         register ulg c;                         /* temporary variable */
1140
1141         static ulg crc = (ulg) 0xffffffffL;     /* shift register contents */
1142
1143         if (s == NULL) {
1144                 c = 0xffffffffL;
1145         } else {
1146                 c = crc;
1147                 if (n)
1148                         do {
1149                                 c = crc_32_tab[((int) c ^ (*s++)) & 0xff] ^ (c >> 8);
1150                         } while (--n);
1151         }
1152         crc = c;
1153         return c ^ 0xffffffffL;         /* (instead of ~c for 64-bit machines) */
1154 }
1155
1156 /* ===========================================================================
1157  * Clear input and output buffers
1158  */
1159 void clear_bufs()
1160 {
1161         outcnt = 0;
1162         insize = inptr = 0;
1163         bytes_in = bytes_out = 0L;
1164 }
1165
1166 /* ===========================================================================
1167  * Fill the input buffer. This is called only when the buffer is empty.
1168  */
1169 int fill_inbuf(eof_ok)
1170 int eof_ok;                                             /* set if EOF acceptable as a result */
1171 {
1172         int len;
1173
1174         /* Read as much as possible */
1175         insize = 0;
1176         errno = 0;
1177         do {
1178                 len = read(ifd, (char *) inbuf + insize, INBUFSIZ - insize);
1179                 if (len == 0 || len == EOF)
1180                         break;
1181                 insize += len;
1182         } while (insize < INBUFSIZ);
1183
1184         if (insize == 0) {
1185                 if (eof_ok)
1186                         return EOF;
1187                 read_error();
1188         }
1189         bytes_in += (ulg) insize;
1190         inptr = 1;
1191         return inbuf[0];
1192 }
1193
1194 /* ===========================================================================
1195  * Write the output buffer outbuf[0..outcnt-1] and update bytes_out.
1196  * (used for the compressed data only)
1197  */
1198 void flush_outbuf()
1199 {
1200         if (outcnt == 0)
1201                 return;
1202
1203         if (!test_mode)
1204                 write_buf(ofd, (char *) outbuf, outcnt);
1205         bytes_out += (ulg) outcnt;
1206         outcnt = 0;
1207 }
1208
1209 /* ===========================================================================
1210  * Write the output window window[0..outcnt-1] and update crc and bytes_out.
1211  * (Used for the decompressed data only.)
1212  */
1213 void flush_window()
1214 {
1215         if (outcnt == 0)
1216                 return;
1217         updcrc(window, outcnt);
1218
1219         if (!test_mode)
1220                 write_buf(ofd, (char *) window, outcnt);
1221         bytes_out += (ulg) outcnt;
1222         outcnt = 0;
1223 }
1224
1225 /* ===========================================================================
1226  * Does the same as write(), but also handles partial pipe writes and checks
1227  * for error return.
1228  */
1229 void write_buf(fd, buf, cnt)
1230 int fd;
1231 void * buf;
1232 unsigned cnt;
1233 {
1234         unsigned n;
1235
1236         while ((n = write(fd, buf, cnt)) != cnt) {
1237                 if (n == (unsigned) (-1)) {
1238                         write_error();
1239                 }
1240                 cnt -= n;
1241                 buf = (void *) ((char *) buf + n);
1242         }
1243 }
1244
1245 #if defined(NO_STRING_H) && !defined(STDC_HEADERS)
1246
1247 /* Provide missing strspn and strcspn functions. */
1248
1249 #  ifndef __STDC__
1250 #    define const
1251 #  endif
1252
1253 int strspn (const char *s, const char *accept);
1254 int strcspn (const char *s, const char *reject);
1255
1256 /* ========================================================================
1257  * Return the length of the maximum initial segment
1258  * of s which contains only characters in accept.
1259  */
1260 int strspn(s, accept)
1261 const char *s;
1262 const char *accept;
1263 {
1264         register const char *p;
1265         register const char *a;
1266         register int count = 0;
1267
1268         for (p = s; *p != '\0'; ++p) {
1269                 for (a = accept; *a != '\0'; ++a) {
1270                         if (*p == *a)
1271                                 break;
1272                 }
1273                 if (*a == '\0')
1274                         return count;
1275                 ++count;
1276         }
1277         return count;
1278 }
1279
1280 /* ========================================================================
1281  * Return the length of the maximum inital segment of s
1282  * which contains no characters from reject.
1283  */
1284 int strcspn(s, reject)
1285 const char *s;
1286 const char *reject;
1287 {
1288         register int count = 0;
1289
1290         while (*s != '\0') {
1291                 if (strchr(reject, *s++) != NULL)
1292                         return count;
1293                 ++count;
1294         }
1295         return count;
1296 }
1297
1298 #endif                                                  /* NO_STRING_H */
1299
1300
1301 /* ========================================================================
1302  * Error handlers.
1303  */
1304 void read_error()
1305 {
1306         fprintf(stderr, "\n");
1307         if (errno != 0) {
1308                 perror("");
1309         } else {
1310                 fprintf(stderr, "unexpected end of file\n");
1311         }
1312         abort_gzip();
1313 }
1314
1315 void write_error()
1316 {
1317         fprintf(stderr, "\n");
1318         perror("");
1319         abort_gzip();
1320 }
1321
1322
1323 /* ========================================================================
1324  * Table of CRC-32's of all single-byte values (made by makecrc.c)
1325  */
1326 static const ulg crc_32_tab[] = {
1327         0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L,
1328         0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0x0edb8832L, 0x79dcb8a4L,
1329         0xe0d5e91eL, 0x97d2d988L, 0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L,
1330         0x90bf1d91L, 0x1db71064L, 0x6ab020f2L, 0xf3b97148L, 0x84be41deL,
1331         0x1adad47dL, 0x6ddde4ebL, 0xf4d4b551L, 0x83d385c7L, 0x136c9856L,
1332         0x646ba8c0L, 0xfd62f97aL, 0x8a65c9ecL, 0x14015c4fL, 0x63066cd9L,
1333         0xfa0f3d63L, 0x8d080df5L, 0x3b6e20c8L, 0x4c69105eL, 0xd56041e4L,
1334         0xa2677172L, 0x3c03e4d1L, 0x4b04d447L, 0xd20d85fdL, 0xa50ab56bL,
1335         0x35b5a8faL, 0x42b2986cL, 0xdbbbc9d6L, 0xacbcf940L, 0x32d86ce3L,
1336         0x45df5c75L, 0xdcd60dcfL, 0xabd13d59L, 0x26d930acL, 0x51de003aL,
1337         0xc8d75180L, 0xbfd06116L, 0x21b4f4b5L, 0x56b3c423L, 0xcfba9599L,
1338         0xb8bda50fL, 0x2802b89eL, 0x5f058808L, 0xc60cd9b2L, 0xb10be924L,
1339         0x2f6f7c87L, 0x58684c11L, 0xc1611dabL, 0xb6662d3dL, 0x76dc4190L,
1340         0x01db7106L, 0x98d220bcL, 0xefd5102aL, 0x71b18589L, 0x06b6b51fL,
1341         0x9fbfe4a5L, 0xe8b8d433L, 0x7807c9a2L, 0x0f00f934L, 0x9609a88eL,
1342         0xe10e9818L, 0x7f6a0dbbL, 0x086d3d2dL, 0x91646c97L, 0xe6635c01L,
1343         0x6b6b51f4L, 0x1c6c6162L, 0x856530d8L, 0xf262004eL, 0x6c0695edL,
1344         0x1b01a57bL, 0x8208f4c1L, 0xf50fc457L, 0x65b0d9c6L, 0x12b7e950L,
1345         0x8bbeb8eaL, 0xfcb9887cL, 0x62dd1ddfL, 0x15da2d49L, 0x8cd37cf3L,
1346         0xfbd44c65L, 0x4db26158L, 0x3ab551ceL, 0xa3bc0074L, 0xd4bb30e2L,
1347         0x4adfa541L, 0x3dd895d7L, 0xa4d1c46dL, 0xd3d6f4fbL, 0x4369e96aL,
1348         0x346ed9fcL, 0xad678846L, 0xda60b8d0L, 0x44042d73L, 0x33031de5L,
1349         0xaa0a4c5fL, 0xdd0d7cc9L, 0x5005713cL, 0x270241aaL, 0xbe0b1010L,
1350         0xc90c2086L, 0x5768b525L, 0x206f85b3L, 0xb966d409L, 0xce61e49fL,
1351         0x5edef90eL, 0x29d9c998L, 0xb0d09822L, 0xc7d7a8b4L, 0x59b33d17L,
1352         0x2eb40d81L, 0xb7bd5c3bL, 0xc0ba6cadL, 0xedb88320L, 0x9abfb3b6L,
1353         0x03b6e20cL, 0x74b1d29aL, 0xead54739L, 0x9dd277afL, 0x04db2615L,
1354         0x73dc1683L, 0xe3630b12L, 0x94643b84L, 0x0d6d6a3eL, 0x7a6a5aa8L,
1355         0xe40ecf0bL, 0x9309ff9dL, 0x0a00ae27L, 0x7d079eb1L, 0xf00f9344L,
1356         0x8708a3d2L, 0x1e01f268L, 0x6906c2feL, 0xf762575dL, 0x806567cbL,
1357         0x196c3671L, 0x6e6b06e7L, 0xfed41b76L, 0x89d32be0L, 0x10da7a5aL,
1358         0x67dd4accL, 0xf9b9df6fL, 0x8ebeeff9L, 0x17b7be43L, 0x60b08ed5L,
1359         0xd6d6a3e8L, 0xa1d1937eL, 0x38d8c2c4L, 0x4fdff252L, 0xd1bb67f1L,
1360         0xa6bc5767L, 0x3fb506ddL, 0x48b2364bL, 0xd80d2bdaL, 0xaf0a1b4cL,
1361         0x36034af6L, 0x41047a60L, 0xdf60efc3L, 0xa867df55L, 0x316e8eefL,
1362         0x4669be79L, 0xcb61b38cL, 0xbc66831aL, 0x256fd2a0L, 0x5268e236L,
1363         0xcc0c7795L, 0xbb0b4703L, 0x220216b9L, 0x5505262fL, 0xc5ba3bbeL,
1364         0xb2bd0b28L, 0x2bb45a92L, 0x5cb36a04L, 0xc2d7ffa7L, 0xb5d0cf31L,
1365         0x2cd99e8bL, 0x5bdeae1dL, 0x9b64c2b0L, 0xec63f226L, 0x756aa39cL,
1366         0x026d930aL, 0x9c0906a9L, 0xeb0e363fL, 0x72076785L, 0x05005713L,
1367         0x95bf4a82L, 0xe2b87a14L, 0x7bb12baeL, 0x0cb61b38L, 0x92d28e9bL,
1368         0xe5d5be0dL, 0x7cdcefb7L, 0x0bdbdf21L, 0x86d3d2d4L, 0xf1d4e242L,
1369         0x68ddb3f8L, 0x1fda836eL, 0x81be16cdL, 0xf6b9265bL, 0x6fb077e1L,
1370         0x18b74777L, 0x88085ae6L, 0xff0f6a70L, 0x66063bcaL, 0x11010b5cL,
1371         0x8f659effL, 0xf862ae69L, 0x616bffd3L, 0x166ccf45L, 0xa00ae278L,
1372         0xd70dd2eeL, 0x4e048354L, 0x3903b3c2L, 0xa7672661L, 0xd06016f7L,
1373         0x4969474dL, 0x3e6e77dbL, 0xaed16a4aL, 0xd9d65adcL, 0x40df0b66L,
1374         0x37d83bf0L, 0xa9bcae53L, 0xdebb9ec5L, 0x47b2cf7fL, 0x30b5ffe9L,
1375         0xbdbdf21cL, 0xcabac28aL, 0x53b39330L, 0x24b4a3a6L, 0xbad03605L,
1376         0xcdd70693L, 0x54de5729L, 0x23d967bfL, 0xb3667a2eL, 0xc4614ab8L,
1377         0x5d681b02L, 0x2a6f2b94L, 0xb40bbe37L, 0xc30c8ea1L, 0x5a05df1bL,
1378         0x2d02ef8dL
1379 };
1380
1381 /* inflate.c -- Not copyrighted 1992 by Mark Adler
1382    version c10p1, 10 January 1993 */
1383
1384 /* You can do whatever you like with this source file, though I would
1385    prefer that if you modify it and redistribute it that you include
1386    comments to that effect with your name and the date.  Thank you.
1387    [The history has been moved to the file ChangeLog.]
1388  */
1389
1390 /*
1391    Inflate deflated (PKZIP's method 8 compressed) data.  The compression
1392    method searches for as much of the current string of bytes (up to a
1393    length of 258) in the previous 32K bytes.  If it doesn't find any
1394    matches (of at least length 3), it codes the next byte.  Otherwise, it
1395    codes the length of the matched string and its distance backwards from
1396    the current position.  There is a single Huffman code that codes both
1397    single bytes (called "literals") and match lengths.  A second Huffman
1398    code codes the distance information, which follows a length code.  Each
1399    length or distance code actually represents a base value and a number
1400    of "extra" (sometimes zero) bits to get to add to the base value.  At
1401    the end of each deflated block is a special end-of-block (EOB) literal/
1402    length code.  The decoding process is basically: get a literal/length
1403    code; if EOB then done; if a literal, emit the decoded byte; if a
1404    length then get the distance and emit the referred-to bytes from the
1405    sliding window of previously emitted data.
1406
1407    There are (currently) three kinds of inflate blocks: stored, fixed, and
1408    dynamic.  The compressor deals with some chunk of data at a time, and
1409    decides which method to use on a chunk-by-chunk basis.  A chunk might
1410    typically be 32K or 64K.  If the chunk is uncompressible, then the
1411    "stored" method is used.  In this case, the bytes are simply stored as
1412    is, eight bits per byte, with none of the above coding.  The bytes are
1413    preceded by a count, since there is no longer an EOB code.
1414
1415    If the data is compressible, then either the fixed or dynamic methods
1416    are used.  In the dynamic method, the compressed data is preceded by
1417    an encoding of the literal/length and distance Huffman codes that are
1418    to be used to decode this block.  The representation is itself Huffman
1419    coded, and so is preceded by a description of that code.  These code
1420    descriptions take up a little space, and so for small blocks, there is
1421    a predefined set of codes, called the fixed codes.  The fixed method is
1422    used if the block codes up smaller that way (usually for quite small
1423    chunks), otherwise the dynamic method is used.  In the latter case, the
1424    codes are customized to the probabilities in the current block, and so
1425    can code it much better than the pre-determined fixed codes.
1426
1427    The Huffman codes themselves are decoded using a mutli-level table
1428    lookup, in order to maximize the speed of decoding plus the speed of
1429    building the decoding tables.  See the comments below that precede the
1430    lbits and dbits tuning parameters.
1431  */
1432
1433
1434 /*
1435    Notes beyond the 1.93a appnote.txt:
1436
1437    1. Distance pointers never point before the beginning of the output
1438       stream.
1439    2. Distance pointers can point back across blocks, up to 32k away.
1440    3. There is an implied maximum of 7 bits for the bit length table and
1441       15 bits for the actual data.
1442    4. If only one code exists, then it is encoded using one bit.  (Zero
1443       would be more efficient, but perhaps a little confusing.)  If two
1444       codes exist, they are coded using one bit each (0 and 1).
1445    5. There is no way of sending zero distance codes--a dummy must be
1446       sent if there are none.  (History: a pre 2.0 version of PKZIP would
1447       store blocks with no distance codes, but this was discovered to be
1448       too harsh a criterion.)  Valid only for 1.93a.  2.04c does allow
1449       zero distance codes, which is sent as one code of zero bits in
1450       length.
1451    6. There are up to 286 literal/length codes.  Code 256 represents the
1452       end-of-block.  Note however that the static length tree defines
1453       288 codes just to fill out the Huffman codes.  Codes 286 and 287
1454       cannot be used though, since there is no length base or extra bits
1455       defined for them.  Similarly, there are up to 30 distance codes.
1456       However, static trees define 32 codes (all 5 bits) to fill out the
1457       Huffman codes, but the last two had better not show up in the data.
1458    7. Unzip can check dynamic Huffman blocks for complete code sets.
1459       The exception is that a single code would not be complete (see #4).
1460    8. The five bits following the block type is really the number of
1461       literal codes sent minus 257.
1462    9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
1463       (1+6+6).  Therefore, to output three times the length, you output
1464       three codes (1+1+1), whereas to output four times the same length,
1465       you only need two codes (1+3).  Hmm.
1466   10. In the tree reconstruction algorithm, Code = Code + Increment
1467       only if BitLength(i) is not zero.  (Pretty obvious.)
1468   11. Correction: 4 Bits: # of Bit Length codes - 4     (4 - 19)
1469   12. Note: length code 284 can represent 227-258, but length code 285
1470       really is 258.  The last length deserves its own, short code
1471       since it gets used a lot in very redundant files.  The length
1472       258 is special since 258 - 3 (the min match length) is 255.
1473   13. The literal/length and distance code bit lengths are read as a
1474       single stream of lengths.  It is possible (and advantageous) for
1475       a repeat code (16, 17, or 18) to go across the boundary between
1476       the two sets of lengths.
1477  */
1478
1479 #include <sys/types.h>
1480
1481 #if defined(STDC_HEADERS) || !defined(NO_STDLIB_H)
1482 #  include <stdlib.h>
1483 #endif
1484
1485
1486 #define slide window
1487
1488 /* Huffman code lookup table entry--this entry is four bytes for machines
1489    that have 16-bit pointers (e.g. PC's in the small or medium model).
1490    Valid extra bits are 0..13.  e == 15 is EOB (end of block), e == 16
1491    means that v is a literal, 16 < e < 32 means that v is a pointer to
1492    the next table, which codes e - 16 bits, and lastly e == 99 indicates
1493    an unused code.  If a code with e == 99 is looked up, this implies an
1494    error in the data. */
1495 struct huft {
1496         uch e;                                          /* number of extra bits or operation */
1497         uch b;                                          /* number of bits in this code or subcode */
1498         union {
1499                 ush n;                                  /* literal, length base, or distance base */
1500                 struct huft *t;                 /* pointer to next level of table */
1501         } v;
1502 };
1503
1504
1505 /* Function prototypes */
1506 int huft_build (unsigned *, unsigned, unsigned, ush *, ush *,
1507                                    struct huft **, int *);
1508 int huft_free (struct huft *);
1509 int inflate_codes (struct huft *, struct huft *, int, int);
1510 int inflate_stored (void);
1511 int inflate_fixed (void);
1512 int inflate_dynamic (void);
1513 int inflate_block (int *);
1514 int inflate (void);
1515
1516
1517 /* The inflate algorithm uses a sliding 32K byte window on the uncompressed
1518    stream to find repeated byte strings.  This is implemented here as a
1519    circular buffer.  The index is updated simply by incrementing and then
1520    and'ing with 0x7fff (32K-1). */
1521 /* It is left to other modules to supply the 32K area.  It is assumed
1522    to be usable as if it were declared "uch slide[32768];" or as just
1523    "uch *slide;" and then malloc'ed in the latter case.  The definition
1524    must be in unzip.h, included above. */
1525 /* unsigned wp;             current position in slide */
1526 #define wp outcnt
1527 #define flush_output(w) (wp=(w),flush_window())
1528
1529 /* Tables for deflate from PKZIP's appnote.txt. */
1530 static unsigned border[] = {    /* Order of the bit length code lengths */
1531         16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
1532 };
1533 static ush cplens[] = {                 /* Copy lengths for literal codes 257..285 */
1534         3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
1535         35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0
1536 };
1537
1538                 /* note: see note #13 above about the 258 in this list. */
1539 static ush cplext[] = {                 /* Extra bits for literal codes 257..285 */
1540         0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
1541         3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 99, 99
1542 };                                                              /* 99==invalid */
1543 static ush cpdist[] = {                 /* Copy offsets for distance codes 0..29 */
1544         1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
1545         257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
1546         8193, 12289, 16385, 24577
1547 };
1548 static ush cpdext[] = {                 /* Extra bits for distance codes */
1549         0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
1550         7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
1551         12, 12, 13, 13
1552 };
1553
1554
1555
1556 /* Macros for inflate() bit peeking and grabbing.
1557    The usage is:
1558
1559         NEEDBITS(j)
1560         x = b & mask_bits[j];
1561         DUMPBITS(j)
1562
1563    where NEEDBITS makes sure that b has at least j bits in it, and
1564    DUMPBITS removes the bits from b.  The macros use the variable k
1565    for the number of bits in b.  Normally, b and k are register
1566    variables for speed, and are initialized at the beginning of a
1567    routine that uses these macros from a global bit buffer and count.
1568
1569    If we assume that EOB will be the longest code, then we will never
1570    ask for bits with NEEDBITS that are beyond the end of the stream.
1571    So, NEEDBITS should not read any more bytes than are needed to
1572    meet the request.  Then no bytes need to be "returned" to the buffer
1573    at the end of the last block.
1574
1575    However, this assumption is not true for fixed blocks--the EOB code
1576    is 7 bits, but the other literal/length codes can be 8 or 9 bits.
1577    (The EOB code is shorter than other codes because fixed blocks are
1578    generally short.  So, while a block always has an EOB, many other
1579    literal/length codes have a significantly lower probability of
1580    showing up at all.)  However, by making the first table have a
1581    lookup of seven bits, the EOB code will be found in that first
1582    lookup, and so will not require that too many bits be pulled from
1583    the stream.
1584  */
1585
1586 ulg bb;                                                 /* bit buffer */
1587 unsigned bk;                                    /* bits in bit buffer */
1588
1589 ush mask_bits[] = {
1590         0x0000,
1591         0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
1592         0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
1593 };
1594
1595 #ifdef CRYPT
1596 uch cc;
1597
1598 #  define NEXTBYTE() (cc = get_byte(), zdecode(cc), cc)
1599 #else
1600 #  define NEXTBYTE()  (uch)get_byte()
1601 #endif
1602 #define NEEDBITS(n) {while(k<(n)){b|=((ulg)NEXTBYTE())<<k;k+=8;}}
1603 #define DUMPBITS(n) {b>>=(n);k-=(n);}
1604
1605
1606 /*
1607    Huffman code decoding is performed using a multi-level table lookup.
1608    The fastest way to decode is to simply build a lookup table whose
1609    size is determined by the longest code.  However, the time it takes
1610    to build this table can also be a factor if the data being decoded
1611    is not very long.  The most common codes are necessarily the
1612    shortest codes, so those codes dominate the decoding time, and hence
1613    the speed.  The idea is you can have a shorter table that decodes the
1614    shorter, more probable codes, and then point to subsidiary tables for
1615    the longer codes.  The time it costs to decode the longer codes is
1616    then traded against the time it takes to make longer tables.
1617
1618    This results of this trade are in the variables lbits and dbits
1619    below.  lbits is the number of bits the first level table for literal/
1620    length codes can decode in one step, and dbits is the same thing for
1621    the distance codes.  Subsequent tables are also less than or equal to
1622    those sizes.  These values may be adjusted either when all of the
1623    codes are shorter than that, in which case the longest code length in
1624    bits is used, or when the shortest code is *longer* than the requested
1625    table size, in which case the length of the shortest code in bits is
1626    used.
1627
1628    There are two different values for the two tables, since they code a
1629    different number of possibilities each.  The literal/length table
1630    codes 286 possible values, or in a flat code, a little over eight
1631    bits.  The distance table codes 30 possible values, or a little less
1632    than five bits, flat.  The optimum values for speed end up being
1633    about one bit more than those, so lbits is 8+1 and dbits is 5+1.
1634    The optimum values may differ though from machine to machine, and
1635    possibly even between compilers.  Your mileage may vary.
1636  */
1637
1638
1639 int lbits = 9;                                  /* bits in base literal/length lookup table */
1640 int dbits = 6;                                  /* bits in base distance lookup table */
1641
1642
1643 /* If BMAX needs to be larger than 16, then h and x[] should be ulg. */
1644 #define BMAX 16                                 /* maximum bit length of any code (16 for explode) */
1645 #define N_MAX 288                               /* maximum number of codes in any set */
1646
1647
1648 unsigned hufts;                                 /* track memory usage */
1649
1650
1651 int huft_build(b, n, s, d, e, t, m)
1652 unsigned *b;                                    /* code lengths in bits (all assumed <= BMAX) */
1653 unsigned n;                                             /* number of codes (assumed <= N_MAX) */
1654 unsigned s;                                             /* number of simple-valued codes (0..s-1) */
1655 ush *d;                                                 /* list of base values for non-simple codes */
1656 ush *e;                                                 /* list of extra bits for non-simple codes */
1657 struct huft **t;                                /* result: starting table */
1658 int *m;                                                 /* maximum lookup bits, returns actual */
1659
1660 /* Given a list of code lengths and a maximum table size, make a set of
1661    tables to decode that set of codes.  Return zero on success, one if
1662    the given code set is incomplete (the tables are still built in this
1663    case), two if the input is invalid (all zero length codes or an
1664    oversubscribed set of lengths), and three if not enough memory. */
1665 {
1666         unsigned a;                                     /* counter for codes of length k */
1667         unsigned c[BMAX + 1];           /* bit length count table */
1668         unsigned f;                                     /* i repeats in table every f entries */
1669         int g;                                          /* maximum code length */
1670         int h;                                          /* table level */
1671         register unsigned i;            /* counter, current code */
1672         register unsigned j;            /* counter */
1673         register int k;                         /* number of bits in current code */
1674         int l;                                          /* bits per table (returned in m) */
1675         register unsigned *p;           /* pointer into c[], b[], or v[] */
1676         register struct huft *q;        /* points to current table */
1677         struct huft r;                          /* table entry for structure assignment */
1678         struct huft *u[BMAX];           /* table stack */
1679         unsigned v[N_MAX];                      /* values in order of bit length */
1680         register int w;                         /* bits before this table == (l * h) */
1681         unsigned x[BMAX + 1];           /* bit offsets, then code stack */
1682         unsigned *xp;                           /* pointer into x */
1683         int y;                                          /* number of dummy codes added */
1684         unsigned z;                                     /* number of entries in current table */
1685
1686
1687         /* Generate counts for each bit length */
1688         memzero(c, sizeof(c));
1689         p = b;
1690         i = n;
1691         do {
1692                 Tracecv(*p,
1693                                 (stderr,
1694                                  (n - i >= ' '
1695                                   && n - i <= '~' ? "%c %d\n" : "0x%x %d\n"), n - i, *p));
1696                 c[*p]++;                                /* assume all entries <= BMAX */
1697                 p++;                                    /* Can't combine with above line (Solaris bug) */
1698         } while (--i);
1699         if (c[0] == n) {                        /* null input--all zero length codes */
1700                 *t = (struct huft *) NULL;
1701                 *m = 0;
1702                 return 0;
1703         }
1704
1705
1706         /* Find minimum and maximum length, bound *m by those */
1707         l = *m;
1708         for (j = 1; j <= BMAX; j++)
1709                 if (c[j])
1710                         break;
1711         k = j;                                          /* minimum code length */
1712         if ((unsigned) l < j)
1713                 l = j;
1714         for (i = BMAX; i; i--)
1715                 if (c[i])
1716                         break;
1717         g = i;                                          /* maximum code length */
1718         if ((unsigned) l > i)
1719                 l = i;
1720         *m = l;
1721
1722
1723         /* Adjust last length count to fill out codes, if needed */
1724         for (y = 1 << j; j < i; j++, y <<= 1)
1725                 if ((y -= c[j]) < 0)
1726                         return 2;                       /* bad input: more codes than bits */
1727         if ((y -= c[i]) < 0)
1728                 return 2;
1729         c[i] += y;
1730
1731
1732         /* Generate starting offsets into the value table for each length */
1733         x[1] = j = 0;
1734         p = c + 1;
1735         xp = x + 2;
1736         while (--i) {                           /* note that i == g from above */
1737                 *xp++ = (j += *p++);
1738         }
1739
1740
1741         /* Make a table of values in order of bit lengths */
1742         p = b;
1743         i = 0;
1744         do {
1745                 if ((j = *p++) != 0)
1746                         v[x[j]++] = i;
1747         } while (++i < n);
1748
1749
1750         /* Generate the Huffman codes and for each, make the table entries */
1751         x[0] = i = 0;                           /* first Huffman code is zero */
1752         p = v;                                          /* grab values in bit order */
1753         h = -1;                                         /* no tables yet--level -1 */
1754         w = -l;                                         /* bits decoded == (l * h) */
1755         u[0] = (struct huft *) NULL;    /* just to keep compilers happy */
1756         q = (struct huft *) NULL;       /* ditto */
1757         z = 0;                                          /* ditto */
1758
1759         /* go through the bit lengths (k already is bits in shortest code) */
1760         for (; k <= g; k++) {
1761                 a = c[k];
1762                 while (a--) {
1763                         /* here i is the Huffman code of length k bits for value *p */
1764                         /* make tables up to required level */
1765                         while (k > w + l) {
1766                                 h++;
1767                                 w += l;                 /* previous table always l bits */
1768
1769                                 /* compute minimum size table less than or equal to l bits */
1770                                 z = (z = g - w) > (unsigned) l ? l : z; /* upper limit on table size */
1771                                 if ((f = 1 << (j = k - w)) > a + 1) {   /* try a k-w bit table *//* too few codes for k-w bit table */
1772                                         f -= a + 1;     /* deduct codes from patterns left */
1773                                         xp = c + k;
1774                                         while (++j < z) {       /* try smaller tables up to z bits */
1775                                                 if ((f <<= 1) <= *++xp)
1776                                                         break;  /* enough codes to use up j bits */
1777                                                 f -= *xp;       /* else deduct codes from patterns */
1778                                         }
1779                                 }
1780                                 z = 1 << j;             /* table entries for j-bit table */
1781
1782                                 /* allocate and link in new table */
1783                                 if (
1784                                         (q =
1785                                          (struct huft *) malloc((z + 1) *
1786                                                                                         sizeof(struct huft))) ==
1787                                         (struct huft *) NULL) {
1788                                         if (h)
1789                                                 huft_free(u[0]);
1790                                         return 3;       /* not enough memory */
1791                                 }
1792                                 hufts += z + 1; /* track memory usage */
1793                                 *t = q + 1;             /* link to list for huft_free() */
1794                                 *(t = &(q->v.t)) = (struct huft *) NULL;
1795                                 u[h] = ++q;             /* table starts after link */
1796
1797                                 /* connect to last table, if there is one */
1798                                 if (h) {
1799                                         x[h] = i;       /* save pattern for backing up */
1800                                         r.b = (uch) l;  /* bits to dump before this table */
1801                                         r.e = (uch) (16 + j);   /* bits in this table */
1802                                         r.v.t = q;      /* pointer to this table */
1803                                         j = i >> (w - l);       /* (get around Turbo C bug) */
1804                                         u[h - 1][j] = r;        /* connect to last table */
1805                                 }
1806                         }
1807
1808                         /* set up table entry in r */
1809                         r.b = (uch) (k - w);
1810                         if (p >= v + n)
1811                                 r.e = 99;               /* out of values--invalid code */
1812                         else if (*p < s) {
1813                                 r.e = (uch) (*p < 256 ? 16 : 15);       /* 256 is end-of-block code */
1814                                 r.v.n = (ush) (*p);     /* simple code is just the value */
1815                                 p++;                    /* one compiler does not like *p++ */
1816                         } else {
1817                                 r.e = (uch) e[*p - s];  /* non-simple--look up in lists */
1818                                 r.v.n = d[*p++ - s];
1819                         }
1820
1821                         /* fill code-like entries with r */
1822                         f = 1 << (k - w);
1823                         for (j = i >> w; j < z; j += f)
1824                                 q[j] = r;
1825
1826                         /* backwards increment the k-bit code i */
1827                         for (j = 1 << (k - 1); i & j; j >>= 1)
1828                                 i ^= j;
1829                         i ^= j;
1830
1831                         /* backup over finished tables */
1832                         while ((i & ((1 << w) - 1)) != x[h]) {
1833                                 h--;                    /* don't need to update q */
1834                                 w -= l;
1835                         }
1836                 }
1837         }
1838
1839
1840         /* Return true (1) if we were given an incomplete table */
1841         return y != 0 && g != 1;
1842 }
1843
1844
1845
1846 int huft_free(t)
1847 struct huft *t;                                 /* table to free */
1848
1849 /* Free the malloc'ed tables built by huft_build(), which makes a linked
1850    list of the tables it made, with the links in a dummy first entry of
1851    each table. */
1852 {
1853         register struct huft *p, *q;
1854
1855
1856         /* Go through linked list, freeing from the malloced (t[-1]) address. */
1857         p = t;
1858         while (p != (struct huft *) NULL) {
1859                 q = (--p)->v.t;
1860                 free((char *) p);
1861                 p = q;
1862         }
1863         return 0;
1864 }
1865
1866
1867 int inflate_codes(tl, td, bl, bd)
1868 struct huft *tl, *td;                   /* literal/length and distance decoder tables */
1869 int bl, bd;                                             /* number of bits decoded by tl[] and td[] */
1870
1871 /* inflate (decompress) the codes in a deflated (compressed) block.
1872    Return an error code or zero if it all goes ok. */
1873 {
1874         register unsigned e;            /* table entry flag/number of extra bits */
1875         unsigned n, d;                          /* length and index for copy */
1876         unsigned w;                                     /* current window position */
1877         struct huft *t;                         /* pointer to table entry */
1878         unsigned ml, md;                        /* masks for bl and bd bits */
1879         register ulg b;                         /* bit buffer */
1880         register unsigned k;            /* number of bits in bit buffer */
1881
1882
1883         /* make local copies of globals */
1884         b = bb;                                         /* initialize bit buffer */
1885         k = bk;
1886         w = wp;                                         /* initialize window position */
1887
1888         /* inflate the coded data */
1889         ml = mask_bits[bl];                     /* precompute masks for speed */
1890         md = mask_bits[bd];
1891         for (;;) {                                      /* do until end of block */
1892                 NEEDBITS((unsigned) bl)
1893                         if ((e = (t = tl + ((unsigned) b & ml))->e) > 16)
1894                         do {
1895                                 if (e == 99)
1896                                         return 1;
1897                                 DUMPBITS(t->b)
1898                                         e -= 16;
1899                                 NEEDBITS(e)
1900                         } while ((e = (t = t->v.t + ((unsigned) b & mask_bits[e]))->e)
1901                                          > 16);
1902                 DUMPBITS(t->b)
1903                         if (e == 16) {          /* then it's a literal */
1904                         slide[w++] = (uch) t->v.n;
1905                         Tracevv((stderr, "%c", slide[w - 1]));
1906                         if (w == WSIZE) {
1907                                 flush_output(w);
1908                                 w = 0;
1909                         }
1910                 } else {                                /* it's an EOB or a length */
1911
1912                         /* exit if end of block */
1913                         if (e == 15)
1914                                 break;
1915
1916                         /* get length of block to copy */
1917                         NEEDBITS(e)
1918                                 n = t->v.n + ((unsigned) b & mask_bits[e]);
1919                         DUMPBITS(e);
1920
1921                         /* decode distance of block to copy */
1922                         NEEDBITS((unsigned) bd)
1923                                 if ((e = (t = td + ((unsigned) b & md))->e) > 16)
1924                                 do {
1925                                         if (e == 99)
1926                                                 return 1;
1927                                         DUMPBITS(t->b)
1928                                                 e -= 16;
1929                                         NEEDBITS(e)
1930                                 }
1931                                         while (
1932                                                    (e =
1933                                                         (t =
1934                                                          t->v.t + ((unsigned) b & mask_bits[e]))->e) >
1935                                                    16);
1936                         DUMPBITS(t->b)
1937                                 NEEDBITS(e)
1938                                 d = w - t->v.n - ((unsigned) b & mask_bits[e]);
1939                         DUMPBITS(e)
1940                                 Tracevv((stderr, "\\[%d,%d]", w - d, n));
1941
1942                         /* do the copy */
1943                         do {
1944                                 n -= (e =
1945                                           (e =
1946                                            WSIZE - ((d &= WSIZE - 1) > w ? d : w)) >
1947                                           n ? n : e);
1948 #if !defined(NOMEMCPY) && !defined(DEBUG)
1949                                 if (w - d >= e) {       /* (this test assumes unsigned comparison) */
1950                                         memcpy(slide + w, slide + d, e);
1951                                         w += e;
1952                                         d += e;
1953                                 } else                  /* do it slow to avoid memcpy() overlap */
1954 #endif                                                  /* !NOMEMCPY */
1955                                         do {
1956                                                 slide[w++] = slide[d++];
1957                                                 Tracevv((stderr, "%c", slide[w - 1]));
1958                                         } while (--e);
1959                                 if (w == WSIZE) {
1960                                         flush_output(w);
1961                                         w = 0;
1962                                 }
1963                         } while (n);
1964                 }
1965         }
1966
1967
1968         /* restore the globals from the locals */
1969         wp = w;                                         /* restore global window pointer */
1970         bb = b;                                         /* restore global bit buffer */
1971         bk = k;
1972
1973         /* done */
1974         return 0;
1975 }
1976
1977
1978
1979 int inflate_stored()
1980 /* "decompress" an inflated type 0 (stored) block. */
1981 {
1982         unsigned n;                                     /* number of bytes in block */
1983         unsigned w;                                     /* current window position */
1984         register ulg b;                         /* bit buffer */
1985         register unsigned k;            /* number of bits in bit buffer */
1986
1987
1988         /* make local copies of globals */
1989         b = bb;                                         /* initialize bit buffer */
1990         k = bk;
1991         w = wp;                                         /* initialize window position */
1992
1993
1994         /* go to byte boundary */
1995         n = k & 7;
1996         DUMPBITS(n);
1997
1998
1999         /* get the length and its complement */
2000         NEEDBITS(16)
2001                 n = ((unsigned) b & 0xffff);
2002         DUMPBITS(16)
2003                 NEEDBITS(16)
2004                 if (n != (unsigned) ((~b) & 0xffff))
2005                 return 1;                               /* error in compressed data */
2006         DUMPBITS(16)
2007
2008
2009                 /* read and output the compressed data */
2010                 while (n--) {
2011                 NEEDBITS(8)
2012                         slide[w++] = (uch) b;
2013                 if (w == WSIZE) {
2014                         flush_output(w);
2015                         w = 0;
2016                 }
2017                 DUMPBITS(8)
2018         }
2019
2020
2021         /* restore the globals from the locals */
2022         wp = w;                                         /* restore global window pointer */
2023         bb = b;                                         /* restore global bit buffer */
2024         bk = k;
2025         return 0;
2026 }
2027
2028
2029
2030 int inflate_fixed()
2031 /* decompress an inflated type 1 (fixed Huffman codes) block.  We should
2032    either replace this with a custom decoder, or at least precompute the
2033    Huffman tables. */
2034 {
2035         int i;                                          /* temporary variable */
2036         struct huft *tl;                        /* literal/length code table */
2037         struct huft *td;                        /* distance code table */
2038         int bl;                                         /* lookup bits for tl */
2039         int bd;                                         /* lookup bits for td */
2040         unsigned l[288];                        /* length list for huft_build */
2041
2042
2043         /* set up literal table */
2044         for (i = 0; i < 144; i++)
2045                 l[i] = 8;
2046         for (; i < 256; i++)
2047                 l[i] = 9;
2048         for (; i < 280; i++)
2049                 l[i] = 7;
2050         for (; i < 288; i++)            /* make a complete, but wrong code set */
2051                 l[i] = 8;
2052         bl = 7;
2053         if ((i = huft_build(l, 288, 257, cplens, cplext, &tl, &bl)) != 0)
2054                 return i;
2055
2056
2057         /* set up distance table */
2058         for (i = 0; i < 30; i++)        /* make an incomplete code set */
2059                 l[i] = 5;
2060         bd = 5;
2061         if ((i = huft_build(l, 30, 0, cpdist, cpdext, &td, &bd)) > 1) {
2062                 huft_free(tl);
2063                 return i;
2064         }
2065
2066
2067         /* decompress until an end-of-block code */
2068         if (inflate_codes(tl, td, bl, bd))
2069                 return 1;
2070
2071
2072         /* free the decoding tables, return */
2073         huft_free(tl);
2074         huft_free(td);
2075         return 0;
2076 }
2077
2078
2079
2080 int inflate_dynamic()
2081 /* decompress an inflated type 2 (dynamic Huffman codes) block. */
2082 {
2083         int i;                                          /* temporary variables */
2084         unsigned j;
2085         unsigned l;                                     /* last length */
2086         unsigned m;                                     /* mask for bit lengths table */
2087         unsigned n;                                     /* number of lengths to get */
2088         struct huft *tl;                        /* literal/length code table */
2089         struct huft *td;                        /* distance code table */
2090         int bl;                                         /* lookup bits for tl */
2091         int bd;                                         /* lookup bits for td */
2092         unsigned nb;                            /* number of bit length codes */
2093         unsigned nl;                            /* number of literal/length codes */
2094         unsigned nd;                            /* number of distance codes */
2095
2096 #ifdef PKZIP_BUG_WORKAROUND
2097         unsigned ll[288 + 32];          /* literal/length and distance code lengths */
2098 #else
2099         unsigned ll[286 + 30];          /* literal/length and distance code lengths */
2100 #endif
2101         register ulg b;                         /* bit buffer */
2102         register unsigned k;            /* number of bits in bit buffer */
2103
2104
2105         /* make local bit buffer */
2106         b = bb;
2107         k = bk;
2108
2109
2110         /* read in table lengths */
2111         NEEDBITS(5)
2112                 nl = 257 + ((unsigned) b & 0x1f);       /* number of literal/length codes */
2113         DUMPBITS(5)
2114                 NEEDBITS(5)
2115                 nd = 1 + ((unsigned) b & 0x1f); /* number of distance codes */
2116         DUMPBITS(5)
2117                 NEEDBITS(4)
2118                 nb = 4 + ((unsigned) b & 0xf);  /* number of bit length codes */
2119         DUMPBITS(4)
2120 #ifdef PKZIP_BUG_WORKAROUND
2121                 if (nl > 288 || nd > 32)
2122 #else
2123                 if (nl > 286 || nd > 30)
2124 #endif
2125                 return 1;                               /* bad lengths */
2126
2127
2128         /* read in bit-length-code lengths */
2129         for (j = 0; j < nb; j++) {
2130                 NEEDBITS(3)
2131                         ll[border[j]] = (unsigned) b & 7;
2132                 DUMPBITS(3)
2133         }
2134         for (; j < 19; j++)
2135                 ll[border[j]] = 0;
2136
2137
2138         /* build decoding table for trees--single level, 7 bit lookup */
2139         bl = 7;
2140         if ((i = huft_build(ll, 19, 19, NULL, NULL, &tl, &bl)) != 0) {
2141                 if (i == 1)
2142                         huft_free(tl);
2143                 return i;                               /* incomplete code set */
2144         }
2145
2146
2147         /* read in literal and distance code lengths */
2148         n = nl + nd;
2149         m = mask_bits[bl];
2150         i = l = 0;
2151         while ((unsigned) i < n) {
2152                 NEEDBITS((unsigned) bl)
2153                         j = (td = tl + ((unsigned) b & m))->b;
2154                 DUMPBITS(j)
2155                         j = td->v.n;
2156                 if (j < 16)                             /* length of code in bits (0..15) */
2157                         ll[i++] = l = j;        /* save last length in l */
2158                 else if (j == 16) {             /* repeat last length 3 to 6 times */
2159                         NEEDBITS(2)
2160                                 j = 3 + ((unsigned) b & 3);
2161                         DUMPBITS(2)
2162                                 if ((unsigned) i + j > n)
2163                                 return 1;
2164                         while (j--)
2165                                 ll[i++] = l;
2166                 } else if (j == 17) {   /* 3 to 10 zero length codes */
2167                         NEEDBITS(3)
2168                                 j = 3 + ((unsigned) b & 7);
2169                         DUMPBITS(3)
2170                                 if ((unsigned) i + j > n)
2171                                 return 1;
2172                         while (j--)
2173                                 ll[i++] = 0;
2174                         l = 0;
2175                 } else {                                /* j == 18: 11 to 138 zero length codes */
2176
2177                         NEEDBITS(7)
2178                                 j = 11 + ((unsigned) b & 0x7f);
2179                         DUMPBITS(7)
2180                                 if ((unsigned) i + j > n)
2181                                 return 1;
2182                         while (j--)
2183                                 ll[i++] = 0;
2184                         l = 0;
2185                 }
2186         }
2187
2188
2189         /* free decoding table for trees */
2190         huft_free(tl);
2191
2192
2193         /* restore the global bit buffer */
2194         bb = b;
2195         bk = k;
2196
2197
2198         /* build the decoding tables for literal/length and distance codes */
2199         bl = lbits;
2200         if ((i = huft_build(ll, nl, 257, cplens, cplext, &tl, &bl)) != 0) {
2201                 if (i == 1) {
2202                         fprintf(stderr, " incomplete literal tree\n");
2203                         huft_free(tl);
2204                 }
2205                 return i;                               /* incomplete code set */
2206         }
2207         bd = dbits;
2208         if ((i = huft_build(ll + nl, nd, 0, cpdist, cpdext, &td, &bd)) != 0) {
2209                 if (i == 1) {
2210                         fprintf(stderr, " incomplete distance tree\n");
2211 #ifdef PKZIP_BUG_WORKAROUND
2212                         i = 0;
2213                 }
2214 #else
2215                         huft_free(td);
2216                 }
2217                 huft_free(tl);
2218                 return i;                               /* incomplete code set */
2219 #endif
2220         }
2221
2222
2223         /* decompress until an end-of-block code */
2224         if (inflate_codes(tl, td, bl, bd))
2225                 return 1;
2226
2227
2228         /* free the decoding tables, return */
2229         huft_free(tl);
2230         huft_free(td);
2231         return 0;
2232 }
2233
2234
2235
2236 int inflate_block(e)
2237 int *e;                                                 /* last block flag */
2238
2239 /* decompress an inflated block */
2240 {
2241         unsigned t;                                     /* block type */
2242         register ulg b;                         /* bit buffer */
2243         register unsigned k;            /* number of bits in bit buffer */
2244
2245
2246         /* make local bit buffer */
2247         b = bb;
2248         k = bk;
2249
2250
2251         /* read in last block bit */
2252         NEEDBITS(1)
2253                 * e = (int) b & 1;
2254         DUMPBITS(1)
2255
2256
2257                 /* read in block type */
2258                 NEEDBITS(2)
2259                 t = (unsigned) b & 3;
2260         DUMPBITS(2)
2261
2262
2263                 /* restore the global bit buffer */
2264                 bb = b;
2265         bk = k;
2266
2267
2268         /* inflate that block type */
2269         if (t == 2)
2270                 return inflate_dynamic();
2271         if (t == 0)
2272                 return inflate_stored();
2273         if (t == 1)
2274                 return inflate_fixed();
2275
2276
2277         /* bad block type */
2278         return 2;
2279 }
2280
2281
2282
2283 int inflate()
2284 /* decompress an inflated entry */
2285 {
2286         int e;                                          /* last block flag */
2287         int r;                                          /* result code */
2288         unsigned h;                                     /* maximum struct huft's malloc'ed */
2289
2290
2291         /* initialize window, bit buffer */
2292         wp = 0;
2293         bk = 0;
2294         bb = 0;
2295
2296
2297         /* decompress until the last block */
2298         h = 0;
2299         do {
2300                 hufts = 0;
2301                 if ((r = inflate_block(&e)) != 0)
2302                         return r;
2303                 if (hufts > h)
2304                         h = hufts;
2305         } while (!e);
2306
2307         /* Undo too much lookahead. The next read will be byte aligned so we
2308          * can discard unused bits in the last meaningful byte.
2309          */
2310         while (bk >= 8) {
2311                 bk -= 8;
2312                 inptr--;
2313         }
2314
2315         /* flush out slide */
2316         flush_output(wp);
2317
2318
2319         /* return success */
2320 #ifdef DEBUG
2321         fprintf(stderr, "<%u> ", h);
2322 #endif                                                  /* DEBUG */
2323         return 0;
2324 }