archival/gunzip.c

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