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