archival/gunzip.c

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