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