gunzip.c

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