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