archival/gunzip.c

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