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