aboutsummaryrefslogtreecommitdiff
path: root/gzip.c
diff options
context:
space:
mode:
Diffstat (limited to 'gzip.c')
-rw-r--r--gzip.c3132
1 files changed, 1636 insertions, 1496 deletions
diff --git a/gzip.c b/gzip.c
index 3438ee42f..f132679f7 100644
--- a/gzip.c
+++ b/gzip.c
@@ -1,3 +1,4 @@
1/* vi: set sw=4 ts=4: */
1/* gzip.c -- this is a stripped down version of gzip I put into busybox, it does 2/* gzip.c -- this is a stripped down version of gzip I put into busybox, it does
2 * only standard in to standard out with -9 compression. It also requires the 3 * only standard in to standard out with -9 compression. It also requires the
3 * zcat module for some important functions. 4 * zcat module for some important functions.
@@ -12,11 +13,12 @@
12//#endif 13//#endif
13 14
14static const char gzip_usage[] = 15static const char gzip_usage[] =
15 "gzip [OPTION]... FILE\n\n" 16 "gzip [OPTION]... FILE\n\n"
16 "Compress FILE with maximum compression.\n" 17 "Compress FILE with maximum compression.\n"
17 "When FILE is -, reads standard input. Implies -c.\n\n" 18 "When FILE is -, reads standard input. Implies -c.\n\n"
18 "Options:\n" 19
19 "\t-c\tWrite output to standard output instead of FILE.gz\n"; 20 "Options:\n"
21 "\t-c\tWrite output to standard output instead of FILE.gz\n";
20 22
21 23
22/* gzip.h -- common declarations for all gzip modules 24/* gzip.h -- common declarations for all gzip modules
@@ -32,9 +34,9 @@ static const char gzip_usage[] =
32#endif 34#endif
33 35
34#ifdef __STDC__ 36#ifdef __STDC__
35 typedef void *voidp; 37typedef void *voidp;
36#else 38#else
37 typedef char *voidp; 39typedef char *voidp;
38#endif 40#endif
39 41
40/* I don't like nested includes, but the string and io functions are used 42/* I don't like nested includes, but the string and io functions are used
@@ -49,10 +51,10 @@ static const char gzip_usage[] =
49# define memzero(s, n) memset ((voidp)(s), 0, (n)) 51# define memzero(s, n) memset ((voidp)(s), 0, (n))
50#else 52#else
51# include <strings.h> 53# include <strings.h>
52# define strchr index 54# define strchr index
53# define strrchr rindex 55# define strrchr rindex
54# define memcpy(d, s, n) bcopy((s), (d), (n)) 56# define memcpy(d, s, n) bcopy((s), (d), (n))
55# define memcmp(s1, s2, n) bcmp((s1), (s2), (n)) 57# define memcmp(s1, s2, n) bcmp((s1), (s2), (n))
56# define memzero(s, n) bzero((s), (n)) 58# define memzero(s, n) bzero((s), (n))
57#endif 59#endif
58 60
@@ -62,9 +64,9 @@ static const char gzip_usage[] =
62 64
63#define local static 65#define local static
64 66
65typedef unsigned char uch; 67typedef unsigned char uch;
66typedef unsigned short ush; 68typedef unsigned short ush;
67typedef unsigned long ulg; 69typedef unsigned long ulg;
68 70
69/* Return codes from gzip */ 71/* Return codes from gzip */
70#define OK 0 72#define OK 0
@@ -79,7 +81,7 @@ typedef unsigned long ulg;
79/* methods 4 to 7 reserved */ 81/* methods 4 to 7 reserved */
80#define DEFLATED 8 82#define DEFLATED 8
81#define MAX_METHODS 9 83#define MAX_METHODS 9
82extern int method; /* compression method */ 84extern int method; /* compression method */
83 85
84/* To save memory for 16 bit systems, some arrays are overlaid between 86/* To save memory for 16 bit systems, some arrays are overlaid between
85 * the various modules: 87 * the various modules:
@@ -94,27 +96,27 @@ extern int method; /* compression method */
94 96
95#ifndef INBUFSIZ 97#ifndef INBUFSIZ
96# ifdef SMALL_MEM 98# ifdef SMALL_MEM
97# define INBUFSIZ 0x2000 /* input buffer size */ 99# define INBUFSIZ 0x2000 /* input buffer size */
98# else 100# else
99# define INBUFSIZ 0x8000 /* input buffer size */ 101# define INBUFSIZ 0x8000 /* input buffer size */
100# endif 102# endif
101#endif 103#endif
102#define INBUF_EXTRA 64 /* required by unlzw() */ 104#define INBUF_EXTRA 64 /* required by unlzw() */
103 105
104#ifndef OUTBUFSIZ 106#ifndef OUTBUFSIZ
105# ifdef SMALL_MEM 107# ifdef SMALL_MEM
106# define OUTBUFSIZ 8192 /* output buffer size */ 108# define OUTBUFSIZ 8192 /* output buffer size */
107# else 109# else
108# define OUTBUFSIZ 16384 /* output buffer size */ 110# define OUTBUFSIZ 16384 /* output buffer size */
109# endif 111# endif
110#endif 112#endif
111#define OUTBUF_EXTRA 2048 /* required by unlzw() */ 113#define OUTBUF_EXTRA 2048 /* required by unlzw() */
112 114
113#ifndef DIST_BUFSIZE 115#ifndef DIST_BUFSIZE
114# ifdef SMALL_MEM 116# ifdef SMALL_MEM
115# define DIST_BUFSIZE 0x2000 /* buffer for distances, see trees.c */ 117# define DIST_BUFSIZE 0x2000 /* buffer for distances, see trees.c */
116# else 118# else
117# define DIST_BUFSIZE 0x8000 /* buffer for distances, see trees.c */ 119# define DIST_BUFSIZE 0x8000 /* buffer for distances, see trees.c */
118# endif 120# endif
119#endif 121#endif
120 122
@@ -133,60 +135,61 @@ extern int method; /* compression method */
133# define FREE(array) 135# define FREE(array)
134#endif 136#endif
135 137
136EXTERN(uch, inbuf); /* input buffer */ 138EXTERN(uch, inbuf); /* input buffer */
137EXTERN(uch, outbuf); /* output buffer */ 139EXTERN(uch, outbuf); /* output buffer */
138EXTERN(ush, d_buf); /* buffer for distances, see trees.c */ 140EXTERN(ush, d_buf); /* buffer for distances, see trees.c */
139EXTERN(uch, window); /* Sliding window and suffix table (unlzw) */ 141EXTERN(uch, window); /* Sliding window and suffix table (unlzw) */
140#define tab_suffix window 142#define tab_suffix window
141#ifndef MAXSEG_64K 143#ifndef MAXSEG_64K
142# define tab_prefix prev /* hash link (see deflate.c) */ 144# define tab_prefix prev /* hash link (see deflate.c) */
143# define head (prev+WSIZE) /* hash head (see deflate.c) */ 145# define head (prev+WSIZE) /* hash head (see deflate.c) */
144 EXTERN(ush, tab_prefix); /* prefix code (see unlzw.c) */ 146EXTERN(ush, tab_prefix); /* prefix code (see unlzw.c) */
145#else 147#else
146# define tab_prefix0 prev 148# define tab_prefix0 prev
147# define head tab_prefix1 149# define head tab_prefix1
148 EXTERN(ush, tab_prefix0); /* prefix for even codes */ 150EXTERN(ush, tab_prefix0); /* prefix for even codes */
149 EXTERN(ush, tab_prefix1); /* prefix for odd codes */ 151EXTERN(ush, tab_prefix1); /* prefix for odd codes */
150#endif 152#endif
151 153
152extern unsigned insize; /* valid bytes in inbuf */ 154extern unsigned insize; /* valid bytes in inbuf */
153extern unsigned inptr; /* index of next byte to be processed in inbuf */ 155extern unsigned inptr; /* index of next byte to be processed in inbuf */
154extern unsigned outcnt; /* bytes in output buffer */ 156extern unsigned outcnt; /* bytes in output buffer */
155 157
156extern long bytes_in; /* number of input bytes */ 158extern long bytes_in; /* number of input bytes */
157extern long bytes_out; /* number of output bytes */ 159extern long bytes_out; /* number of output bytes */
158extern long header_bytes;/* number of bytes in gzip header */ 160extern long header_bytes; /* number of bytes in gzip header */
159 161
160#define isize bytes_in 162#define isize bytes_in
161/* for compatibility with old zip sources (to be cleaned) */ 163/* for compatibility with old zip sources (to be cleaned) */
162 164
163extern int ifd; /* input file descriptor */ 165extern int ifd; /* input file descriptor */
164extern int ofd; /* output file descriptor */ 166extern int ofd; /* output file descriptor */
165extern char ifname[]; /* input file name or "stdin" */ 167extern char ifname[]; /* input file name or "stdin" */
166extern char ofname[]; /* output file name or "stdout" */ 168extern char ofname[]; /* output file name or "stdout" */
167extern char *progname; /* program name */ 169extern char *progname; /* program name */
170
171extern long time_stamp; /* original time stamp (modification time) */
172extern long ifile_size; /* input file size, -1 for devices (debug only) */
168 173
169extern long time_stamp; /* original time stamp (modification time) */ 174typedef int file_t; /* Do not use stdio */
170extern long ifile_size; /* input file size, -1 for devices (debug only) */
171 175
172typedef int file_t; /* Do not use stdio */ 176#define NO_FILE (-1) /* in memory compression */
173#define NO_FILE (-1) /* in memory compression */
174 177
175 178
176#define PACK_MAGIC "\037\036" /* Magic header for packed files */ 179#define PACK_MAGIC "\037\036" /* Magic header for packed files */
177#define GZIP_MAGIC "\037\213" /* Magic header for gzip files, 1F 8B */ 180#define GZIP_MAGIC "\037\213" /* Magic header for gzip files, 1F 8B */
178#define OLD_GZIP_MAGIC "\037\236" /* Magic header for gzip 0.5 = freeze 1.x */ 181#define OLD_GZIP_MAGIC "\037\236" /* Magic header for gzip 0.5 = freeze 1.x */
179#define LZH_MAGIC "\037\240" /* Magic header for SCO LZH Compress files*/ 182#define LZH_MAGIC "\037\240" /* Magic header for SCO LZH Compress files */
180#define PKZIP_MAGIC "\120\113\003\004" /* Magic header for pkzip files */ 183#define PKZIP_MAGIC "\120\113\003\004" /* Magic header for pkzip files */
181 184
182/* gzip flag byte */ 185/* gzip flag byte */
183#define ASCII_FLAG 0x01 /* bit 0 set: file probably ascii text */ 186#define ASCII_FLAG 0x01 /* bit 0 set: file probably ascii text */
184#define CONTINUATION 0x02 /* bit 1 set: continuation of multi-part gzip file */ 187#define CONTINUATION 0x02 /* bit 1 set: continuation of multi-part gzip file */
185#define EXTRA_FIELD 0x04 /* bit 2 set: extra field present */ 188#define EXTRA_FIELD 0x04 /* bit 2 set: extra field present */
186#define ORIG_NAME 0x08 /* bit 3 set: original file name present */ 189#define ORIG_NAME 0x08 /* bit 3 set: original file name present */
187#define COMMENT 0x10 /* bit 4 set: file comment present */ 190#define COMMENT 0x10 /* bit 4 set: file comment present */
188#define ENCRYPTED 0x20 /* bit 5 set: file is encrypted */ 191#define ENCRYPTED 0x20 /* bit 5 set: file is encrypted */
189#define RESERVED 0xC0 /* bit 6,7: reserved */ 192#define RESERVED 0xC0 /* bit 6,7: reserved */
190 193
191/* internal file attribute */ 194/* internal file attribute */
192#define UNKNOWN 0xffff 195#define UNKNOWN 0xffff
@@ -194,8 +197,8 @@ typedef int file_t; /* Do not use stdio */
194#define ASCII 1 197#define ASCII 1
195 198
196#ifndef WSIZE 199#ifndef WSIZE
197# define WSIZE 0x8000 /* window size--must be a power of two, and */ 200# define WSIZE 0x8000 /* window size--must be a power of two, and */
198#endif /* at least 32K for zip's deflate method */ 201#endif /* at least 32K for zip's deflate method */
199 202
200#define MIN_MATCH 3 203#define MIN_MATCH 3
201#define MAX_MATCH 258 204#define MAX_MATCH 258
@@ -211,12 +214,12 @@ typedef int file_t; /* Do not use stdio */
211 * distances are limited to MAX_DIST instead of WSIZE. 214 * distances are limited to MAX_DIST instead of WSIZE.
212 */ 215 */
213 216
214extern int decrypt; /* flag to turn on decryption */ 217extern int decrypt; /* flag to turn on decryption */
215extern int exit_code; /* program exit code */ 218extern int exit_code; /* program exit code */
216extern int verbose; /* be verbose (-v) */ 219extern int verbose; /* be verbose (-v) */
217extern int quiet; /* be quiet (-q) */ 220extern int quiet; /* be quiet (-q) */
218extern int test; /* check .z file integrity */ 221extern int test; /* check .z file integrity */
219extern int save_orig_name; /* set if original name must be saved */ 222extern int save_orig_name; /* set if original name must be saved */
220 223
221#define get_byte() (inptr < insize ? inbuf[inptr++] : fill_inbuf(0)) 224#define get_byte() (inptr < insize ? inbuf[inptr++] : fill_inbuf(0))
222#define try_byte() (inptr < insize ? inbuf[inptr++] : fill_inbuf(1)) 225#define try_byte() (inptr < insize ? inbuf[inptr++] : fill_inbuf(1))
@@ -248,10 +251,10 @@ extern int save_orig_name; /* set if original name must be saved */
248 put_short(((ulg)(n)) >> 16); \ 251 put_short(((ulg)(n)) >> 16); \
249} 252}
250 253
251#define seekable() 0 /* force sequential output */ 254#define seekable() 0 /* force sequential output */
252#define translate_eol 0 /* no option -a yet */ 255#define translate_eol 0 /* no option -a yet */
253 256
254#define tolow(c) (isupper(c) ? (c)-'A'+'a' : (c)) /* force to lower case */ 257#define tolow(c) (isupper(c) ? (c)-'A'+'a' : (c)) /* force to lower case */
255 258
256/* Macros for getting two-byte and four-byte header values */ 259/* Macros for getting two-byte and four-byte header values */
257#define SH(p) ((ush)(uch)((p)[0]) | ((ush)(uch)((p)[1]) << 8)) 260#define SH(p) ((ush)(uch)((p)[0]) | ((ush)(uch)((p)[1]) << 8))
@@ -281,57 +284,58 @@ extern int save_orig_name; /* set if original name must be saved */
281 284
282 285
283 /* in zip.c: */ 286 /* in zip.c: */
284extern int zip OF((int in, int out)); 287extern int zip OF((int in, int out));
285extern int file_read OF((char *buf, unsigned size)); 288extern int file_read OF((char *buf, unsigned size));
286 289
287 /* in unzip.c */ 290 /* in unzip.c */
288extern int unzip OF((int in, int out)); 291extern int unzip OF((int in, int out));
289extern int check_zipfile OF((int in)); 292extern int check_zipfile OF((int in));
290 293
291 /* in unpack.c */ 294 /* in unpack.c */
292extern int unpack OF((int in, int out)); 295extern int unpack OF((int in, int out));
293 296
294 /* in unlzh.c */ 297 /* in unlzh.c */
295extern int unlzh OF((int in, int out)); 298extern int unlzh OF((int in, int out));
296 299
297 /* in gzip.c */ 300 /* in gzip.c */
298RETSIGTYPE abort_gzip OF((void)); 301RETSIGTYPE abort_gzip OF((void));
299 302
300 /* in deflate.c */ 303 /* in deflate.c */
301void lm_init OF((ush *flags)); 304void lm_init OF((ush * flags));
302ulg deflate OF((void)); 305ulg deflate OF((void));
303 306
304 /* in trees.c */ 307 /* in trees.c */
305void ct_init OF((ush *attr, int *method)); 308void ct_init OF((ush * attr, int *method));
306int ct_tally OF((int dist, int lc)); 309int ct_tally OF((int dist, int lc));
307ulg flush_block OF((char *buf, ulg stored_len, int eof)); 310ulg flush_block OF((char *buf, ulg stored_len, int eof));
308 311
309 /* in bits.c */ 312 /* in bits.c */
310void bi_init OF((file_t zipfile)); 313void bi_init OF((file_t zipfile));
311void send_bits OF((int value, int length)); 314void send_bits OF((int value, int length));
312unsigned bi_reverse OF((unsigned value, int length)); 315unsigned bi_reverse OF((unsigned value, int length));
313void bi_windup OF((void)); 316void bi_windup OF((void));
314void copy_block OF((char *buf, unsigned len, int header)); 317void copy_block OF((char *buf, unsigned len, int header));
315extern int (*read_buf) OF((char *buf, unsigned size)); 318extern int (*read_buf) OF((char *buf, unsigned size));
316 319
317 /* in util.c: */ 320 /* in util.c: */
318extern int copy OF((int in, int out)); 321extern int copy OF((int in, int out));
319extern ulg updcrc OF((uch *s, unsigned n)); 322extern ulg updcrc OF((uch * s, unsigned n));
320extern void clear_bufs OF((void)); 323extern void clear_bufs OF((void));
321extern int fill_inbuf OF((int eof_ok)); 324extern int fill_inbuf OF((int eof_ok));
322extern void flush_outbuf OF((void)); 325extern void flush_outbuf OF((void));
323extern void flush_window OF((void)); 326extern void flush_window OF((void));
324extern void write_buf OF((int fd, voidp buf, unsigned cnt)); 327extern void write_buf OF((int fd, voidp buf, unsigned cnt));
325extern char *strlwr OF((char *s)); 328extern char *strlwr OF((char *s));
326extern char *add_envopt OF((int *argcp, char ***argvp, char *env)); 329extern char *add_envopt OF((int *argcp, char ***argvp, char *env));
327extern void error OF((char *m)); 330extern void error OF((char *m));
328extern void warn OF((char *a, char *b)); 331extern void warn OF((char *a, char *b));
329extern void read_error OF((void)); 332extern void read_error OF((void));
330extern void write_error OF((void)); 333extern void write_error OF((void));
331extern void display_ratio OF((long num, long den, FILE *file)); 334extern void display_ratio OF((long num, long den, FILE * file));
332 335
333 /* in inflate.c */ 336 /* in inflate.c */
334extern int inflate OF((void)); 337extern int inflate OF((void));
338
335/* lzw.h -- define the lzw functions. 339/* lzw.h -- define the lzw functions.
336 * Copyright (C) 1992-1993 Jean-loup Gailly. 340 * Copyright (C) 1992-1993 Jean-loup Gailly.
337 * This is free software; you can redistribute it and/or modify it under the 341 * This is free software; you can redistribute it and/or modify it under the
@@ -345,9 +349,9 @@ extern int inflate OF((void));
345#ifndef BITS 349#ifndef BITS
346# define BITS 16 350# define BITS 16
347#endif 351#endif
348#define INIT_BITS 9 /* Initial number of bits per code */ 352#define INIT_BITS 9 /* Initial number of bits per code */
349 353
350#define BIT_MASK 0x1f /* Mask for 'number of compression bits' */ 354#define BIT_MASK 0x1f /* Mask for 'number of compression bits' */
351/* Mask 0x20 is reserved to mean a fourth header byte, and 0x40 is free. 355/* Mask 0x20 is reserved to mean a fourth header byte, and 0x40 is free.
352 * It's a pity that old uncompress does not check bit 0x20. That makes 356 * It's a pity that old uncompress does not check bit 0x20. That makes
353 * extension of the format actually undesirable because old compress 357 * extension of the format actually undesirable because old compress
@@ -362,13 +366,13 @@ extern int inflate OF((void));
362 * clear the dictionary. 366 * clear the dictionary.
363 */ 367 */
364 368
365#define LZW_RESERVED 0x60 /* reserved bits */ 369#define LZW_RESERVED 0x60 /* reserved bits */
366 370
367#define CLEAR 256 /* flush the dictionary */ 371#define CLEAR 256 /* flush the dictionary */
368#define FIRST (CLEAR+1) /* first free entry */ 372#define FIRST (CLEAR+1) /* first free entry */
369 373
370extern int maxbits; /* max bits per code for LZW */ 374extern int maxbits; /* max bits per code for LZW */
371extern int block_mode; /* block compress mode -C compatible with 2.0 */ 375extern int block_mode; /* block compress mode -C compatible with 2.0 */
372 376
373/* revision.h -- define the version number 377/* revision.h -- define the version number
374 * Copyright (C) 1992-1993 Jean-loup Gailly. 378 * Copyright (C) 1992-1993 Jean-loup Gailly.
@@ -404,18 +408,18 @@ extern int block_mode; /* block compress mode -C compatible with 2.0 */
404# define OS2 408# define OS2
405#endif 409#endif
406 410
407#if defined(OS2) && defined(MSDOS) /* MS C under OS/2 */ 411#if defined(OS2) && defined(MSDOS) /* MS C under OS/2 */
408# undef MSDOS 412# undef MSDOS
409#endif 413#endif
410 414
411#ifdef MSDOS 415#ifdef MSDOS
412# ifdef __GNUC__ 416# ifdef __GNUC__
413 /* DJGPP version 1.09+ on MS-DOS. 417 /* DJGPP version 1.09+ on MS-DOS.
414 * The DJGPP 1.09 stat() function must be upgraded before gzip will 418 * The DJGPP 1.09 stat() function must be upgraded before gzip will
415 * fully work. 419 * fully work.
416 * No need for DIRENT, since <unistd.h> defines POSIX_SOURCE which 420 * No need for DIRENT, since <unistd.h> defines POSIX_SOURCE which
417 * implies DIRENT. 421 * implies DIRENT.
418 */ 422 */
419# define near 423# define near
420# else 424# else
421# define MAXSEG_64K 425# define MAXSEG_64K
@@ -426,7 +430,7 @@ extern int block_mode; /* block compress mode -C compatible with 2.0 */
426# else 430# else
427# define NO_UTIME 431# define NO_UTIME
428# endif 432# endif
429# else /* MSC */ 433# else /* MSC */
430# define HAVE_SYS_UTIME_H 434# define HAVE_SYS_UTIME_H
431# define NO_UTIME_H 435# define NO_UTIME_H
432# endif 436# endif
@@ -441,7 +445,7 @@ extern int block_mode; /* block compress mode -C compatible with 2.0 */
441# define PROTO 445# define PROTO
442# define STDC_HEADERS 446# define STDC_HEADERS
443# define NO_SIZE_CHECK 447# define NO_SIZE_CHECK
444# define casemap(c) tolow(c) /* Force file names to lower case */ 448# define casemap(c) tolow(c) /* Force file names to lower case */
445# include <io.h> 449# include <io.h>
446# define OS_CODE 0x00 450# define OS_CODE 0x00
447# define SET_BINARY_MODE(fd) setmode(fd, O_BINARY) 451# define SET_BINARY_MODE(fd) setmode(fd, O_BINARY)
@@ -494,7 +498,7 @@ extern int block_mode; /* block compress mode -C compatible with 2.0 */
494# endif 498# endif
495#endif 499#endif
496 500
497#ifdef WIN32 /* Windows NT */ 501#ifdef WIN32 /* Windows NT */
498# define HAVE_SYS_UTIME_H 502# define HAVE_SYS_UTIME_H
499# define NO_UTIME_H 503# define NO_UTIME_H
500# define PATH_SEP2 '\\' 504# define PATH_SEP2 '\\'
@@ -510,7 +514,7 @@ extern int block_mode; /* block compress mode -C compatible with 2.0 */
510# define NO_MULTIPLE_DOTS 514# define NO_MULTIPLE_DOTS
511# define MAX_EXT_CHARS 3 515# define MAX_EXT_CHARS 3
512# define Z_SUFFIX "z" 516# define Z_SUFFIX "z"
513# define casemap(c) tolow(c) /* Force file names to lower case */ 517# define casemap(c) tolow(c) /* Force file names to lower case */
514# endif 518# endif
515# define OS_CODE 0x0b 519# define OS_CODE 0x0b
516#endif 520#endif
@@ -519,10 +523,10 @@ extern int block_mode; /* block compress mode -C compatible with 2.0 */
519# ifdef __TURBOC__ 523# ifdef __TURBOC__
520# include <alloc.h> 524# include <alloc.h>
521# define DYN_ALLOC 525# define DYN_ALLOC
522 /* Turbo C 2.0 does not accept static allocations of large arrays */ 526 /* Turbo C 2.0 does not accept static allocations of large arrays */
523 void * fcalloc (unsigned items, unsigned size); 527void *fcalloc(unsigned items, unsigned size);
524 void fcfree (void *ptr); 528void fcfree(void *ptr);
525# else /* MSC */ 529# else /* MSC */
526# include <malloc.h> 530# include <malloc.h>
527# define fcalloc(nitems,itemsize) halloc((long)(nitems),(itemsize)) 531# define fcalloc(nitems,itemsize) halloc((long)(nitems),(itemsize))
528# define fcfree(ptr) hfree(ptr) 532# define fcfree(ptr) hfree(ptr)
@@ -565,17 +569,18 @@ extern int block_mode; /* block compress mode -C compatible with 2.0 */
565# ifdef __GNUC__ 569# ifdef __GNUC__
566# define DIRENT 570# define DIRENT
567# define HAVE_UNISTD_H 571# define HAVE_UNISTD_H
568# else /* SASC */ 572# else /* SASC */
569# define NO_STDIN_FSTAT 573# define NO_STDIN_FSTAT
570# define SYSDIR 574# define SYSDIR
571# define NO_SYMLINK 575# define NO_SYMLINK
572# define NO_CHOWN 576# define NO_CHOWN
573# define NO_FCNTL_H 577# define NO_FCNTL_H
574# include <fcntl.h> /* for read() and write() */ 578# include <fcntl.h> /* for read() and write() */
575# define direct dirent 579# define direct dirent
576 extern void _expand_args(int *argc, char ***argv); 580extern void _expand_args(int *argc, char ***argv);
581
577# define EXPAND(argc,argv) _expand_args(&argc,&argv); 582# define EXPAND(argc,argv) _expand_args(&argc,&argv);
578# undef O_BINARY /* disable useless --ascii option */ 583# undef O_BINARY /* disable useless --ascii option */
579# endif 584# endif
580#endif 585#endif
581 586
@@ -595,7 +600,7 @@ extern int block_mode; /* block compress mode -C compatible with 2.0 */
595# define MAX_EXT_CHARS 3 600# define MAX_EXT_CHARS 3
596# define Z_SUFFIX "z" 601# define Z_SUFFIX "z"
597# define NO_CHOWN 602# define NO_CHOWN
598# define casemap(c) tolow(c) /* Force file names to lower case */ 603# define casemap(c) tolow(c) /* Force file names to lower case */
599# define NO_SYMLINK 604# define NO_SYMLINK
600# endif 605# endif
601#endif 606#endif
@@ -615,28 +620,28 @@ extern int block_mode; /* block compress mode -C compatible with 2.0 */
615# endif 620# endif
616#endif 621#endif
617 622
618#ifdef __50SERIES /* Prime/PRIMOS */ 623#ifdef __50SERIES /* Prime/PRIMOS */
619# define PATH_SEP '>' 624# define PATH_SEP '>'
620# define STDC_HEADERS 625# define STDC_HEADERS
621# define NO_MEMORY_H 626# define NO_MEMORY_H
622# define NO_UTIME_H 627# define NO_UTIME_H
623# define NO_UTIME 628# define NO_UTIME
624# define NO_CHOWN 629# define NO_CHOWN
625# define NO_STDIN_FSTAT 630# define NO_STDIN_FSTAT
626# define NO_SIZE_CHECK 631# define NO_SIZE_CHECK
627# define NO_SYMLINK 632# define NO_SYMLINK
628# define RECORD_IO 1 633# define RECORD_IO 1
629# define casemap(c) tolow(c) /* Force file names to lower case */ 634# define casemap(c) tolow(c) /* Force file names to lower case */
630# define put_char(c) put_byte((c) & 0x7F) 635# define put_char(c) put_byte((c) & 0x7F)
631# define get_char(c) ascii2pascii(get_byte()) 636# define get_char(c) ascii2pascii(get_byte())
632# define OS_CODE 0x0F /* temporary, subject to change */ 637# define OS_CODE 0x0F /* temporary, subject to change */
633# ifdef SIGTERM 638# ifdef SIGTERM
634# undef SIGTERM /* We don't want a signal handler for SIGTERM */ 639# undef SIGTERM /* We don't want a signal handler for SIGTERM */
635# endif 640# endif
636#endif 641#endif
637 642
638#if defined(pyr) && !defined(NOMEMCPY) /* Pyramid */ 643#if defined(pyr) && !defined(NOMEMCPY) /* Pyramid */
639# define NOMEMCPY /* problem with overlapping copies */ 644# define NOMEMCPY /* problem with overlapping copies */
640#endif 645#endif
641 646
642#ifdef TOPS20 647#ifdef TOPS20
@@ -644,14 +649,14 @@ extern int block_mode; /* block compress mode -C compatible with 2.0 */
644#endif 649#endif
645 650
646#ifndef unix 651#ifndef unix
647# define NO_ST_INO /* don't rely on inode numbers */ 652# define NO_ST_INO /* don't rely on inode numbers */
648#endif 653#endif
649 654
650 655
651 /* Common defaults */ 656 /* Common defaults */
652 657
653#ifndef OS_CODE 658#ifndef OS_CODE
654# define OS_CODE 0x03 /* assume Unix */ 659# define OS_CODE 0x03 /* assume Unix */
655#endif 660#endif
656 661
657#ifndef PATH_SEP 662#ifndef PATH_SEP
@@ -773,9 +778,10 @@ extern int block_mode; /* block compress mode -C compatible with 2.0 */
773 * Local data used by the "bit string" routines. 778 * Local data used by the "bit string" routines.
774 */ 779 */
775 780
776local file_t zfile; /* output gzip file */ 781local file_t zfile; /* output gzip file */
777 782
778local unsigned short bi_buf; 783local unsigned short bi_buf;
784
779/* Output buffer. bits are inserted starting at the bottom (least significant 785/* Output buffer. bits are inserted starting at the bottom (least significant
780 * bits). 786 * bits).
781 */ 787 */
@@ -786,36 +792,38 @@ local unsigned short bi_buf;
786 */ 792 */
787 793
788local int bi_valid; 794local int bi_valid;
795
789/* Number of valid bits in bi_buf. All bits above the last valid bit 796/* Number of valid bits in bi_buf. All bits above the last valid bit
790 * are always zero. 797 * are always zero.
791 */ 798 */
792 799
793int (*read_buf) OF((char *buf, unsigned size)); 800int (*read_buf) OF((char *buf, unsigned size));
801
794/* Current input function. Set to mem_read for in-memory compression */ 802/* Current input function. Set to mem_read for in-memory compression */
795 803
796#ifdef DEBUG 804#ifdef DEBUG
797 ulg bits_sent; /* bit length of the compressed data */ 805ulg bits_sent; /* bit length of the compressed data */
798#endif 806#endif
799 807
800/* =========================================================================== 808/* ===========================================================================
801 * Initialize the bit string routines. 809 * Initialize the bit string routines.
802 */ 810 */
803void bi_init (zipfile) 811void bi_init(zipfile)
804 file_t zipfile; /* output zip file, NO_FILE for in-memory compression */ 812file_t zipfile; /* output zip file, NO_FILE for in-memory compression */
805{ 813{
806 zfile = zipfile; 814 zfile = zipfile;
807 bi_buf = 0; 815 bi_buf = 0;
808 bi_valid = 0; 816 bi_valid = 0;
809#ifdef DEBUG 817#ifdef DEBUG
810 bits_sent = 0L; 818 bits_sent = 0L;
811#endif 819#endif
812 820
813 /* Set the defaults for file compression. They are set by memcompress 821 /* Set the defaults for file compression. They are set by memcompress
814 * for in-memory compression. 822 * for in-memory compression.
815 */ 823 */
816 if (zfile != NO_FILE) { 824 if (zfile != NO_FILE) {
817 read_buf = file_read; 825 read_buf = file_read;
818 } 826 }
819} 827}
820 828
821/* =========================================================================== 829/* ===========================================================================
@@ -823,27 +831,27 @@ void bi_init (zipfile)
823 * IN assertion: length <= 16 and value fits in length bits. 831 * IN assertion: length <= 16 and value fits in length bits.
824 */ 832 */
825void send_bits(value, length) 833void send_bits(value, length)
826 int value; /* value to send */ 834int value; /* value to send */
827 int length; /* number of bits */ 835int length; /* number of bits */
828{ 836{
829#ifdef DEBUG 837#ifdef DEBUG
830 Tracev((stderr," l %2d v %4x ", length, value)); 838 Tracev((stderr, " l %2d v %4x ", length, value));
831 Assert(length > 0 && length <= 15, "invalid length"); 839 Assert(length > 0 && length <= 15, "invalid length");
832 bits_sent += (ulg)length; 840 bits_sent += (ulg) length;
833#endif 841#endif
834 /* If not enough room in bi_buf, use (valid) bits from bi_buf and 842 /* If not enough room in bi_buf, use (valid) bits from bi_buf and
835 * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid)) 843 * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))
836 * unused bits in value. 844 * unused bits in value.
837 */ 845 */
838 if (bi_valid > (int)Buf_size - length) { 846 if (bi_valid > (int) Buf_size - length) {
839 bi_buf |= (value << bi_valid); 847 bi_buf |= (value << bi_valid);
840 put_short(bi_buf); 848 put_short(bi_buf);
841 bi_buf = (ush)value >> (Buf_size - bi_valid); 849 bi_buf = (ush) value >> (Buf_size - bi_valid);
842 bi_valid += length - Buf_size; 850 bi_valid += length - Buf_size;
843 } else { 851 } else {
844 bi_buf |= value << bi_valid; 852 bi_buf |= value << bi_valid;
845 bi_valid += length; 853 bi_valid += length;
846 } 854 }
847} 855}
848 856
849/* =========================================================================== 857/* ===========================================================================
@@ -852,15 +860,16 @@ void send_bits(value, length)
852 * IN assertion: 1 <= len <= 15 860 * IN assertion: 1 <= len <= 15
853 */ 861 */
854unsigned bi_reverse(code, len) 862unsigned bi_reverse(code, len)
855 unsigned code; /* the value to invert */ 863unsigned code; /* the value to invert */
856 int len; /* its bit length */ 864int len; /* its bit length */
857{ 865{
858 register unsigned res = 0; 866 register unsigned res = 0;
859 do { 867
860 res |= code & 1; 868 do {
861 code >>= 1, res <<= 1; 869 res |= code & 1;
862 } while (--len > 0); 870 code >>= 1, res <<= 1;
863 return res >> 1; 871 } while (--len > 0);
872 return res >> 1;
864} 873}
865 874
866/* =========================================================================== 875/* ===========================================================================
@@ -868,15 +877,15 @@ unsigned bi_reverse(code, len)
868 */ 877 */
869void bi_windup() 878void bi_windup()
870{ 879{
871 if (bi_valid > 8) { 880 if (bi_valid > 8) {
872 put_short(bi_buf); 881 put_short(bi_buf);
873 } else if (bi_valid > 0) { 882 } else if (bi_valid > 0) {
874 put_byte(bi_buf); 883 put_byte(bi_buf);
875 } 884 }
876 bi_buf = 0; 885 bi_buf = 0;
877 bi_valid = 0; 886 bi_valid = 0;
878#ifdef DEBUG 887#ifdef DEBUG
879 bits_sent = (bits_sent+7) & ~7; 888 bits_sent = (bits_sent + 7) & ~7;
880#endif 889#endif
881} 890}
882 891
@@ -885,30 +894,33 @@ void bi_windup()
885 * one's complement if requested. 894 * one's complement if requested.
886 */ 895 */
887void copy_block(buf, len, header) 896void copy_block(buf, len, header)
888 char *buf; /* the input data */ 897char *buf; /* the input data */
889 unsigned len; /* its length */ 898unsigned len; /* its length */
890 int header; /* true if block header must be written */ 899int header; /* true if block header must be written */
891{ 900{
892 bi_windup(); /* align on byte boundary */ 901 bi_windup(); /* align on byte boundary */
893 902
894 if (header) { 903 if (header) {
895 put_short((ush)len); 904 put_short((ush) len);
896 put_short((ush)~len); 905 put_short((ush) ~ len);
897#ifdef DEBUG 906#ifdef DEBUG
898 bits_sent += 2*16; 907 bits_sent += 2 * 16;
899#endif 908#endif
900 } 909 }
901#ifdef DEBUG 910#ifdef DEBUG
902 bits_sent += (ulg)len<<3; 911 bits_sent += (ulg) len << 3;
903#endif 912#endif
904 while (len--) { 913 while (len--) {
905#ifdef CRYPT 914#ifdef CRYPT
906 int t; 915 int t;
907 if (key) zencode(*buf, t); 916
917 if (key)
918 zencode(*buf, t);
908#endif 919#endif
909 put_byte(*buf++); 920 put_byte(*buf++);
910 } 921 }
911} 922}
923
912/* deflate.c -- compress data using the deflation algorithm 924/* deflate.c -- compress data using the deflation algorithm
913 * Copyright (C) 1992-1993 Jean-loup Gailly 925 * Copyright (C) 1992-1993 Jean-loup Gailly
914 * This is free software; you can redistribute it and/or modify it under the 926 * This is free software; you can redistribute it and/or modify it under the
@@ -987,7 +999,7 @@ void copy_block(buf, len, header)
987 */ 999 */
988 1000
989#ifdef SMALL_MEM 1001#ifdef SMALL_MEM
990# define HASH_BITS 13 /* Number of bits used to hash strings */ 1002# define HASH_BITS 13 /* Number of bits used to hash strings */
991#endif 1003#endif
992#ifdef MEDIUM_MEM 1004#ifdef MEDIUM_MEM
993# define HASH_BITS 14 1005# define HASH_BITS 14
@@ -1001,35 +1013,30 @@ void copy_block(buf, len, header)
1001 * window with tab_suffix. Check that we can do this: 1013 * window with tab_suffix. Check that we can do this:
1002 */ 1014 */
1003#if (WSIZE<<1) > (1<<BITS) 1015#if (WSIZE<<1) > (1<<BITS)
1004 error: cannot overlay window with tab_suffix and prev with tab_prefix0 1016error:cannot overlay window with tab_suffix and prev with tab_prefix0
1005#endif 1017#endif
1006#if HASH_BITS > BITS-1 1018#if HASH_BITS > BITS-1
1007 error: cannot overlay head with tab_prefix1 1019error:cannot overlay head with tab_prefix1
1008#endif 1020#endif
1009
1010#define HASH_SIZE (unsigned)(1<<HASH_BITS) 1021#define HASH_SIZE (unsigned)(1<<HASH_BITS)
1011#define HASH_MASK (HASH_SIZE-1) 1022#define HASH_MASK (HASH_SIZE-1)
1012#define WMASK (WSIZE-1) 1023#define WMASK (WSIZE-1)
1013/* HASH_SIZE and WSIZE must be powers of two */ 1024/* HASH_SIZE and WSIZE must be powers of two */
1014
1015#define NIL 0 1025#define NIL 0
1016/* Tail of hash chains */ 1026/* Tail of hash chains */
1017
1018#define FAST 4 1027#define FAST 4
1019#define SLOW 2 1028#define SLOW 2
1020/* speed options for the general purpose bit flag */ 1029/* speed options for the general purpose bit flag */
1021
1022#ifndef TOO_FAR 1030#ifndef TOO_FAR
1023# define TOO_FAR 4096 1031# define TOO_FAR 4096
1024#endif 1032#endif
1025/* Matches of length 3 are discarded if their distance exceeds TOO_FAR */ 1033/* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
1026
1027/* =========================================================================== 1034/* ===========================================================================
1028 * Local data used by the "longest match" routines. 1035 * Local data used by the "longest match" routines.
1029 */ 1036 */
1030
1031typedef ush Pos; 1037typedef ush Pos;
1032typedef unsigned IPos; 1038typedef unsigned IPos;
1039
1033/* A Pos is an index in the character window. We use short instead of int to 1040/* A Pos is an index in the character window. We use short instead of int to
1034 * save space in the various tables. IPos is used only for parameter passing. 1041 * save space in the various tables. IPos is used only for parameter passing.
1035 */ 1042 */
@@ -1054,17 +1061,19 @@ typedef unsigned IPos;
1054/* DECLARE(Pos, head, 1<<HASH_BITS); */ 1061/* DECLARE(Pos, head, 1<<HASH_BITS); */
1055/* Heads of the hash chains or NIL. */ 1062/* Heads of the hash chains or NIL. */
1056 1063
1057ulg window_size = (ulg)2*WSIZE; 1064ulg window_size = (ulg) 2 * WSIZE;
1065
1058/* window size, 2*WSIZE except for MMAP or BIG_MEM, where it is the 1066/* window size, 2*WSIZE except for MMAP or BIG_MEM, where it is the
1059 * input file length plus MIN_LOOKAHEAD. 1067 * input file length plus MIN_LOOKAHEAD.
1060 */ 1068 */
1061 1069
1062long block_start; 1070long block_start;
1071
1063/* window position at the beginning of the current output block. Gets 1072/* window position at the beginning of the current output block. Gets
1064 * negative when the window is moved backwards. 1073 * negative when the window is moved backwards.
1065 */ 1074 */
1066 1075
1067local unsigned ins_h; /* hash index of string to be inserted */ 1076local unsigned ins_h; /* hash index of string to be inserted */
1068 1077
1069#define H_SHIFT ((HASH_BITS+MIN_MATCH-1)/MIN_MATCH) 1078#define H_SHIFT ((HASH_BITS+MIN_MATCH-1)/MIN_MATCH)
1070/* Number of bits by which ins_h and del_h must be shifted at each 1079/* Number of bits by which ins_h and del_h must be shifted at each
@@ -1074,21 +1083,24 @@ local unsigned ins_h; /* hash index of string to be inserted */
1074 */ 1083 */
1075 1084
1076unsigned int near prev_length; 1085unsigned int near prev_length;
1086
1077/* Length of the best match at previous step. Matches not greater than this 1087/* Length of the best match at previous step. Matches not greater than this
1078 * are discarded. This is used in the lazy match evaluation. 1088 * are discarded. This is used in the lazy match evaluation.
1079 */ 1089 */
1080 1090
1081 unsigned near strstart; /* start of string to insert */ 1091unsigned near strstart; /* start of string to insert */
1082 unsigned near match_start; /* start of matching string */ 1092unsigned near match_start; /* start of matching string */
1083local int eofile; /* flag set at end of input file */ 1093local int eofile; /* flag set at end of input file */
1084local unsigned lookahead; /* number of valid bytes ahead in window */ 1094local unsigned lookahead; /* number of valid bytes ahead in window */
1085 1095
1086unsigned near max_chain_length; 1096unsigned near max_chain_length;
1097
1087/* To speed up deflation, hash chains are never searched beyond this length. 1098/* To speed up deflation, hash chains are never searched beyond this length.
1088 * A higher limit improves compression ratio but degrades the speed. 1099 * A higher limit improves compression ratio but degrades the speed.
1089 */ 1100 */
1090 1101
1091local unsigned int max_lazy_match; 1102local unsigned int max_lazy_match;
1103
1092/* Attempt to find a better match only when the current match is strictly 1104/* Attempt to find a better match only when the current match is strictly
1093 * smaller than this value. This mechanism is used only for compression 1105 * smaller than this value. This mechanism is used only for compression
1094 * levels >= 4. 1106 * levels >= 4.
@@ -1100,6 +1112,7 @@ local unsigned int max_lazy_match;
1100 */ 1112 */
1101 1113
1102unsigned near good_match; 1114unsigned near good_match;
1115
1103/* Use a faster search when the previous match is longer than this */ 1116/* Use a faster search when the previous match is longer than this */
1104 1117
1105 1118
@@ -1110,20 +1123,21 @@ unsigned near good_match;
1110 */ 1123 */
1111 1124
1112typedef struct config { 1125typedef struct config {
1113 ush good_length; /* reduce lazy search above this match length */ 1126 ush good_length; /* reduce lazy search above this match length */
1114 ush max_lazy; /* do not perform lazy search above this match length */ 1127 ush max_lazy; /* do not perform lazy search above this match length */
1115 ush nice_length; /* quit search above this match length */ 1128 ush nice_length; /* quit search above this match length */
1116 ush max_chain; 1129 ush max_chain;
1117} config; 1130} config;
1118 1131
1119#ifdef FULL_SEARCH 1132#ifdef FULL_SEARCH
1120# define nice_match MAX_MATCH 1133# define nice_match MAX_MATCH
1121#else 1134#else
1122 int near nice_match; /* Stop searching when current match exceeds this */ 1135int near nice_match; /* Stop searching when current match exceeds this */
1123#endif 1136#endif
1124 1137
1125local config configuration_table = 1138local config configuration_table =
1126/* 9 */ {32, 258, 258, 4096}; /* maximum compression */ 1139 /* 9 */ { 32, 258, 258, 4096 };
1140 /* maximum compression */
1127 1141
1128/* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4 1142/* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
1129 * For deflate_fast() (levels <= 3) good is ignored and lazy has a different 1143 * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
@@ -1136,15 +1150,16 @@ local config configuration_table =
1136/* =========================================================================== 1150/* ===========================================================================
1137 * Prototypes for local functions. 1151 * Prototypes for local functions.
1138 */ 1152 */
1139local void fill_window OF((void)); 1153local void fill_window OF((void));
1154
1155int longest_match OF((IPos cur_match));
1140 1156
1141 int longest_match OF((IPos cur_match));
1142#ifdef ASMV 1157#ifdef ASMV
1143 void match_init OF((void)); /* asm code initialization */ 1158void match_init OF((void)); /* asm code initialization */
1144#endif 1159#endif
1145 1160
1146#ifdef DEBUG 1161#ifdef DEBUG
1147local void check_match OF((IPos start, IPos match, int length)); 1162local void check_match OF((IPos start, IPos match, int length));
1148#endif 1163#endif
1149 1164
1150/* =========================================================================== 1165/* ===========================================================================
@@ -1171,54 +1186,57 @@ local void check_match OF((IPos start, IPos match, int length));
1171/* =========================================================================== 1186/* ===========================================================================
1172 * Initialize the "longest match" routines for a new file 1187 * Initialize the "longest match" routines for a new file
1173 */ 1188 */
1174void lm_init (flags) 1189void lm_init(flags)
1175 ush *flags; /* general purpose bit flag */ 1190ush *flags; /* general purpose bit flag */
1176{ 1191{
1177 register unsigned j; 1192 register unsigned j;
1178 1193
1179 /* Initialize the hash table. */ 1194 /* Initialize the hash table. */
1180#if defined(MAXSEG_64K) && HASH_BITS == 15 1195#if defined(MAXSEG_64K) && HASH_BITS == 15
1181 for (j = 0; j < HASH_SIZE; j++) head[j] = NIL; 1196 for (j = 0; j < HASH_SIZE; j++)
1197 head[j] = NIL;
1182#else 1198#else
1183 memzero((char*)head, HASH_SIZE*sizeof(*head)); 1199 memzero((char *) head, HASH_SIZE * sizeof(*head));
1184#endif 1200#endif
1185 /* prev will be initialized on the fly */ 1201 /* prev will be initialized on the fly */
1186 1202
1187 /* Set the default configuration parameters: 1203 /* Set the default configuration parameters:
1188 */ 1204 */
1189 max_lazy_match = configuration_table.max_lazy; 1205 max_lazy_match = configuration_table.max_lazy;
1190 good_match = configuration_table.good_length; 1206 good_match = configuration_table.good_length;
1191#ifndef FULL_SEARCH 1207#ifndef FULL_SEARCH
1192 nice_match = configuration_table.nice_length; 1208 nice_match = configuration_table.nice_length;
1193#endif 1209#endif
1194 max_chain_length = configuration_table.max_chain; 1210 max_chain_length = configuration_table.max_chain;
1195 *flags |= SLOW; 1211 *flags |= SLOW;
1196 /* ??? reduce max_chain_length for binary files */ 1212 /* ??? reduce max_chain_length for binary files */
1197 1213
1198 strstart = 0; 1214 strstart = 0;
1199 block_start = 0L; 1215 block_start = 0L;
1200#ifdef ASMV 1216#ifdef ASMV
1201 match_init(); /* initialize the asm code */ 1217 match_init(); /* initialize the asm code */
1202#endif 1218#endif
1203 1219
1204 lookahead = read_buf((char*)window, 1220 lookahead = read_buf((char *) window,
1205 sizeof(int) <= 2 ? (unsigned)WSIZE : 2*WSIZE); 1221 sizeof(int) <= 2 ? (unsigned) WSIZE : 2 * WSIZE);
1206 1222
1207 if (lookahead == 0 || lookahead == (unsigned)EOF) { 1223 if (lookahead == 0 || lookahead == (unsigned) EOF) {
1208 eofile = 1, lookahead = 0; 1224 eofile = 1, lookahead = 0;
1209 return; 1225 return;
1210 } 1226 }
1211 eofile = 0; 1227 eofile = 0;
1212 /* Make sure that we always have enough lookahead. This is important 1228 /* Make sure that we always have enough lookahead. This is important
1213 * if input comes from a device such as a tty. 1229 * if input comes from a device such as a tty.
1214 */ 1230 */
1215 while (lookahead < MIN_LOOKAHEAD && !eofile) fill_window(); 1231 while (lookahead < MIN_LOOKAHEAD && !eofile)
1216 1232 fill_window();
1217 ins_h = 0; 1233
1218 for (j=0; j<MIN_MATCH-1; j++) UPDATE_HASH(ins_h, window[j]); 1234 ins_h = 0;
1219 /* If lookahead < MIN_MATCH, ins_h is garbage, but this is 1235 for (j = 0; j < MIN_MATCH - 1; j++)
1220 * not important since only literal bytes will be emitted. 1236 UPDATE_HASH(ins_h, window[j]);
1221 */ 1237 /* If lookahead < MIN_MATCH, ins_h is garbage, but this is
1238 * not important since only literal bytes will be emitted.
1239 */
1222} 1240}
1223 1241
1224/* =========================================================================== 1242/* ===========================================================================
@@ -1235,151 +1253,157 @@ void lm_init (flags)
1235 * if desired. 1253 * if desired.
1236 */ 1254 */
1237int longest_match(cur_match) 1255int longest_match(cur_match)
1238 IPos cur_match; /* current match */ 1256IPos cur_match; /* current match */
1239{ 1257{
1240 unsigned chain_length = max_chain_length; /* max hash chain length */ 1258 unsigned chain_length = max_chain_length; /* max hash chain length */
1241 register uch *scan = window + strstart; /* current string */ 1259 register uch *scan = window + strstart; /* current string */
1242 register uch *match; /* matched string */ 1260 register uch *match; /* matched string */
1243 register int len; /* length of current match */ 1261 register int len; /* length of current match */
1244 int best_len = prev_length; /* best match length so far */ 1262 int best_len = prev_length; /* best match length so far */
1245 IPos limit = strstart > (IPos)MAX_DIST ? strstart - (IPos)MAX_DIST : NIL; 1263 IPos limit =
1246 /* Stop when cur_match becomes <= limit. To simplify the code, 1264
1247 * we prevent matches with the string of window index 0. 1265 strstart > (IPos) MAX_DIST ? strstart - (IPos) MAX_DIST : NIL;
1248 */ 1266 /* Stop when cur_match becomes <= limit. To simplify the code,
1267 * we prevent matches with the string of window index 0.
1268 */
1249 1269
1250/* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. 1270/* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
1251 * It is easy to get rid of this optimization if necessary. 1271 * It is easy to get rid of this optimization if necessary.
1252 */ 1272 */
1253#if HASH_BITS < 8 || MAX_MATCH != 258 1273#if HASH_BITS < 8 || MAX_MATCH != 258
1254 error: Code too clever 1274 error:Code too clever
1255#endif 1275#endif
1256
1257#ifdef UNALIGNED_OK 1276#ifdef UNALIGNED_OK
1258 /* Compare two bytes at a time. Note: this is not always beneficial. 1277 /* Compare two bytes at a time. Note: this is not always beneficial.
1259 * Try with and without -DUNALIGNED_OK to check. 1278 * Try with and without -DUNALIGNED_OK to check.
1260 */ 1279 */
1261 register uch *strend = window + strstart + MAX_MATCH - 1; 1280 register uch *strend = window + strstart + MAX_MATCH - 1;
1262 register ush scan_start = *(ush*)scan; 1281 register ush scan_start = *(ush *) scan;
1263 register ush scan_end = *(ush*)(scan+best_len-1); 1282 register ush scan_end = *(ush *) (scan + best_len - 1);
1264#else 1283#else
1265 register uch *strend = window + strstart + MAX_MATCH; 1284 register uch *strend = window + strstart + MAX_MATCH;
1266 register uch scan_end1 = scan[best_len-1]; 1285 register uch scan_end1 = scan[best_len - 1];
1267 register uch scan_end = scan[best_len]; 1286 register uch scan_end = scan[best_len];
1268#endif 1287#endif
1269 1288
1270 /* Do not waste too much time if we already have a good match: */ 1289 /* Do not waste too much time if we already have a good match: */
1271 if (prev_length >= good_match) { 1290 if (prev_length >= good_match) {
1272 chain_length >>= 2; 1291 chain_length >>= 2;
1273 } 1292 }
1274 Assert(strstart <= window_size-MIN_LOOKAHEAD, "insufficient lookahead"); 1293 Assert(strstart <= window_size - MIN_LOOKAHEAD,
1294 "insufficient lookahead");
1275 1295
1276 do { 1296 do {
1277 Assert(cur_match < strstart, "no future"); 1297 Assert(cur_match < strstart, "no future");
1278 match = window + cur_match; 1298 match = window + cur_match;
1279 1299
1280 /* Skip to next match if the match length cannot increase 1300 /* Skip to next match if the match length cannot increase
1281 * or if the match length is less than 2: 1301 * or if the match length is less than 2:
1282 */ 1302 */
1283#if (defined(UNALIGNED_OK) && MAX_MATCH == 258) 1303#if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
1284 /* This code assumes sizeof(unsigned short) == 2. Do not use 1304 /* This code assumes sizeof(unsigned short) == 2. Do not use
1285 * UNALIGNED_OK if your compiler uses a different size. 1305 * UNALIGNED_OK if your compiler uses a different size.
1286 */ 1306 */
1287 if (*(ush*)(match+best_len-1) != scan_end || 1307 if (*(ush *) (match + best_len - 1) != scan_end ||
1288 *(ush*)match != scan_start) continue; 1308 *(ush *) match != scan_start)
1289 1309 continue;
1290 /* It is not necessary to compare scan[2] and match[2] since they are 1310
1291 * always equal when the other bytes match, given that the hash keys 1311 /* It is not necessary to compare scan[2] and match[2] since they are
1292 * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at 1312 * always equal when the other bytes match, given that the hash keys
1293 * strstart+3, +5, ... up to strstart+257. We check for insufficient 1313 * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at
1294 * lookahead only every 4th comparison; the 128th check will be made 1314 * strstart+3, +5, ... up to strstart+257. We check for insufficient
1295 * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is 1315 * lookahead only every 4th comparison; the 128th check will be made
1296 * necessary to put more guard bytes at the end of the window, or 1316 * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is
1297 * to check more often for insufficient lookahead. 1317 * necessary to put more guard bytes at the end of the window, or
1298 */ 1318 * to check more often for insufficient lookahead.
1299 scan++, match++; 1319 */
1300 do { 1320 scan++, match++;
1301 } while (*(ush*)(scan+=2) == *(ush*)(match+=2) && 1321 do {
1302 *(ush*)(scan+=2) == *(ush*)(match+=2) && 1322 } while (*(ush *) (scan += 2) == *(ush *) (match += 2) &&
1303 *(ush*)(scan+=2) == *(ush*)(match+=2) && 1323 *(ush *) (scan += 2) == *(ush *) (match += 2) &&
1304 *(ush*)(scan+=2) == *(ush*)(match+=2) && 1324 *(ush *) (scan += 2) == *(ush *) (match += 2) &&
1305 scan < strend); 1325 *(ush *) (scan += 2) == *(ush *) (match += 2) &&
1306 /* The funny "do {}" generates better code on most compilers */ 1326 scan < strend);
1307 1327 /* The funny "do {}" generates better code on most compilers */
1308 /* Here, scan <= window+strstart+257 */ 1328
1309 Assert(scan <= window+(unsigned)(window_size-1), "wild scan"); 1329 /* Here, scan <= window+strstart+257 */
1310 if (*scan == *match) scan++; 1330 Assert(scan <= window + (unsigned) (window_size - 1), "wild scan");
1311 1331 if (*scan == *match)
1312 len = (MAX_MATCH - 1) - (int)(strend-scan); 1332 scan++;
1313 scan = strend - (MAX_MATCH-1); 1333
1314 1334 len = (MAX_MATCH - 1) - (int) (strend - scan);
1315#else /* UNALIGNED_OK */ 1335 scan = strend - (MAX_MATCH - 1);
1316 1336
1317 if (match[best_len] != scan_end || 1337#else /* UNALIGNED_OK */
1318 match[best_len-1] != scan_end1 || 1338
1319 *match != *scan || 1339 if (match[best_len] != scan_end ||
1320 *++match != scan[1]) continue; 1340 match[best_len - 1] != scan_end1 ||
1321 1341 *match != *scan || *++match != scan[1])
1322 /* The check at best_len-1 can be removed because it will be made 1342 continue;
1323 * again later. (This heuristic is not always a win.) 1343
1324 * It is not necessary to compare scan[2] and match[2] since they 1344 /* The check at best_len-1 can be removed because it will be made
1325 * are always equal when the other bytes match, given that 1345 * again later. (This heuristic is not always a win.)
1326 * the hash keys are equal and that HASH_BITS >= 8. 1346 * It is not necessary to compare scan[2] and match[2] since they
1327 */ 1347 * are always equal when the other bytes match, given that
1328 scan += 2, match++; 1348 * the hash keys are equal and that HASH_BITS >= 8.
1329 1349 */
1330 /* We check for insufficient lookahead only every 8th comparison; 1350 scan += 2, match++;
1331 * the 256th check will be made at strstart+258. 1351
1332 */ 1352 /* We check for insufficient lookahead only every 8th comparison;
1333 do { 1353 * the 256th check will be made at strstart+258.
1334 } while (*++scan == *++match && *++scan == *++match && 1354 */
1335 *++scan == *++match && *++scan == *++match && 1355 do {
1336 *++scan == *++match && *++scan == *++match && 1356 } while (*++scan == *++match && *++scan == *++match &&
1337 *++scan == *++match && *++scan == *++match && 1357 *++scan == *++match && *++scan == *++match &&
1338 scan < strend); 1358 *++scan == *++match && *++scan == *++match &&
1339 1359 *++scan == *++match && *++scan == *++match &&
1340 len = MAX_MATCH - (int)(strend - scan); 1360 scan < strend);
1341 scan = strend - MAX_MATCH; 1361
1342 1362 len = MAX_MATCH - (int) (strend - scan);
1343#endif /* UNALIGNED_OK */ 1363 scan = strend - MAX_MATCH;
1344 1364
1345 if (len > best_len) { 1365#endif /* UNALIGNED_OK */
1346 match_start = cur_match; 1366
1347 best_len = len; 1367 if (len > best_len) {
1348 if (len >= nice_match) break; 1368 match_start = cur_match;
1369 best_len = len;
1370 if (len >= nice_match)
1371 break;
1349#ifdef UNALIGNED_OK 1372#ifdef UNALIGNED_OK
1350 scan_end = *(ush*)(scan+best_len-1); 1373 scan_end = *(ush *) (scan + best_len - 1);
1351#else 1374#else
1352 scan_end1 = scan[best_len-1]; 1375 scan_end1 = scan[best_len - 1];
1353 scan_end = scan[best_len]; 1376 scan_end = scan[best_len];
1354#endif 1377#endif
1355 } 1378 }
1356 } while ((cur_match = prev[cur_match & WMASK]) > limit 1379 } while ((cur_match = prev[cur_match & WMASK]) > limit
1357 && --chain_length != 0); 1380 && --chain_length != 0);
1358 1381
1359 return best_len; 1382 return best_len;
1360} 1383}
1361#endif /* ASMV */ 1384#endif /* ASMV */
1362 1385
1363#ifdef DEBUG 1386#ifdef DEBUG
1364/* =========================================================================== 1387/* ===========================================================================
1365 * Check that the match at match_start is indeed a match. 1388 * Check that the match at match_start is indeed a match.
1366 */ 1389 */
1367local void check_match(start, match, length) 1390local void check_match(start, match, length)
1368 IPos start, match; 1391IPos start, match;
1369 int length; 1392int length;
1370{ 1393{
1371 /* check that the match is indeed a match */ 1394 /* check that the match is indeed a match */
1372 if (memcmp((char*)window + match, 1395 if (memcmp((char *) window + match,
1373 (char*)window + start, length) != EQUAL) { 1396 (char *) window + start, length) != EQUAL) {
1374 fprintf(stderr, 1397 fprintf(stderr,
1375 " start %d, match %d, length %d\n", 1398 " start %d, match %d, length %d\n", start, match, length);
1376 start, match, length); 1399 error("invalid match");
1377 error("invalid match"); 1400 }
1378 } 1401 if (verbose > 1) {
1379 if (verbose > 1) { 1402 fprintf(stderr, "\\[%d,%d]", start - match, length);
1380 fprintf(stderr,"\\[%d,%d]", start-match, length); 1403 do {
1381 do { putc(window[start++], stderr); } while (--length != 0); 1404 putc(window[start++], stderr);
1382 } 1405 } while (--length != 0);
1406 }
1383} 1407}
1384#else 1408#else
1385# define check_match(start, match, length) 1409# define check_match(start, match, length)
@@ -1395,52 +1419,54 @@ local void check_match(start, match, length)
1395 */ 1419 */
1396local void fill_window() 1420local void fill_window()
1397{ 1421{
1398 register unsigned n, m; 1422 register unsigned n, m;
1399 unsigned more = (unsigned)(window_size - (ulg)lookahead - (ulg)strstart); 1423 unsigned more =
1400 /* Amount of free space at the end of the window. */ 1424
1401 1425 (unsigned) (window_size - (ulg) lookahead - (ulg) strstart);
1402 /* If the window is almost full and there is insufficient lookahead, 1426 /* Amount of free space at the end of the window. */
1403 * move the upper half to the lower one to make room in the upper half. 1427
1404 */ 1428 /* If the window is almost full and there is insufficient lookahead,
1405 if (more == (unsigned)EOF) { 1429 * move the upper half to the lower one to make room in the upper half.
1406 /* Very unlikely, but possible on 16 bit machine if strstart == 0 1430 */
1407 * and lookahead == 1 (input done one byte at time) 1431 if (more == (unsigned) EOF) {
1408 */ 1432 /* Very unlikely, but possible on 16 bit machine if strstart == 0
1409 more--; 1433 * and lookahead == 1 (input done one byte at time)
1410 } else if (strstart >= WSIZE+MAX_DIST) { 1434 */
1411 /* By the IN assertion, the window is not empty so we can't confuse 1435 more--;
1412 * more == 0 with more == 64K on a 16 bit machine. 1436 } else if (strstart >= WSIZE + MAX_DIST) {
1413 */ 1437 /* By the IN assertion, the window is not empty so we can't confuse
1414 Assert(window_size == (ulg)2*WSIZE, "no sliding with BIG_MEM"); 1438 * more == 0 with more == 64K on a 16 bit machine.
1415 1439 */
1416 memcpy((char*)window, (char*)window+WSIZE, (unsigned)WSIZE); 1440 Assert(window_size == (ulg) 2 * WSIZE, "no sliding with BIG_MEM");
1417 match_start -= WSIZE; 1441
1418 strstart -= WSIZE; /* we now have strstart >= MAX_DIST: */ 1442 memcpy((char *) window, (char *) window + WSIZE, (unsigned) WSIZE);
1419 1443 match_start -= WSIZE;
1420 block_start -= (long) WSIZE; 1444 strstart -= WSIZE; /* we now have strstart >= MAX_DIST: */
1421 1445
1422 for (n = 0; n < HASH_SIZE; n++) { 1446 block_start -= (long) WSIZE;
1423 m = head[n]; 1447
1424 head[n] = (Pos)(m >= WSIZE ? m-WSIZE : NIL); 1448 for (n = 0; n < HASH_SIZE; n++) {
1425 } 1449 m = head[n];
1426 for (n = 0; n < WSIZE; n++) { 1450 head[n] = (Pos) (m >= WSIZE ? m - WSIZE : NIL);
1427 m = prev[n]; 1451 }
1428 prev[n] = (Pos)(m >= WSIZE ? m-WSIZE : NIL); 1452 for (n = 0; n < WSIZE; n++) {
1429 /* If n is not on any hash chain, prev[n] is garbage but 1453 m = prev[n];
1430 * its value will never be used. 1454 prev[n] = (Pos) (m >= WSIZE ? m - WSIZE : NIL);
1431 */ 1455 /* If n is not on any hash chain, prev[n] is garbage but
1432 } 1456 * its value will never be used.
1433 more += WSIZE; 1457 */
1434 } 1458 }
1435 /* At this point, more >= 2 */ 1459 more += WSIZE;
1436 if (!eofile) { 1460 }
1437 n = read_buf((char*)window+strstart+lookahead, more); 1461 /* At this point, more >= 2 */
1438 if (n == 0 || n == (unsigned)EOF) { 1462 if (!eofile) {
1439 eofile = 1; 1463 n = read_buf((char *) window + strstart + lookahead, more);
1440 } else { 1464 if (n == 0 || n == (unsigned) EOF) {
1441 lookahead += n; 1465 eofile = 1;
1442 } 1466 } else {
1443 } 1467 lookahead += n;
1468 }
1469 }
1444} 1470}
1445 1471
1446/* =========================================================================== 1472/* ===========================================================================
@@ -1458,105 +1484,114 @@ local void fill_window()
1458 */ 1484 */
1459ulg deflate() 1485ulg deflate()
1460{ 1486{
1461 IPos hash_head; /* head of hash chain */ 1487 IPos hash_head; /* head of hash chain */
1462 IPos prev_match; /* previous match */ 1488 IPos prev_match; /* previous match */
1463 int flush; /* set if current block must be flushed */ 1489 int flush; /* set if current block must be flushed */
1464 int match_available = 0; /* set if previous match exists */ 1490 int match_available = 0; /* set if previous match exists */
1465 register unsigned match_length = MIN_MATCH-1; /* length of best match */ 1491 register unsigned match_length = MIN_MATCH - 1; /* length of best match */
1492
1466#ifdef DEBUG 1493#ifdef DEBUG
1467 extern long isize; /* byte length of input file, for debug only */ 1494 extern long isize; /* byte length of input file, for debug only */
1468#endif 1495#endif
1469 1496
1470 /* Process the input block. */ 1497 /* Process the input block. */
1471 while (lookahead != 0) { 1498 while (lookahead != 0) {
1472 /* Insert the string window[strstart .. strstart+2] in the 1499 /* Insert the string window[strstart .. strstart+2] in the
1473 * dictionary, and set hash_head to the head of the hash chain: 1500 * dictionary, and set hash_head to the head of the hash chain:
1474 */ 1501 */
1475 INSERT_STRING(strstart, hash_head); 1502 INSERT_STRING(strstart, hash_head);
1476 1503
1477 /* Find the longest match, discarding those <= prev_length. 1504 /* Find the longest match, discarding those <= prev_length.
1478 */ 1505 */
1479 prev_length = match_length, prev_match = match_start; 1506 prev_length = match_length, prev_match = match_start;
1480 match_length = MIN_MATCH-1; 1507 match_length = MIN_MATCH - 1;
1481 1508
1482 if (hash_head != NIL && prev_length < max_lazy_match && 1509 if (hash_head != NIL && prev_length < max_lazy_match &&
1483 strstart - hash_head <= MAX_DIST) { 1510 strstart - hash_head <= MAX_DIST) {
1484 /* To simplify the code, we prevent matches with the string 1511 /* To simplify the code, we prevent matches with the string
1485 * of window index 0 (in particular we have to avoid a match 1512 * of window index 0 (in particular we have to avoid a match
1486 * of the string with itself at the start of the input file). 1513 * of the string with itself at the start of the input file).
1487 */ 1514 */
1488 match_length = longest_match (hash_head); 1515 match_length = longest_match(hash_head);
1489 /* longest_match() sets match_start */ 1516 /* longest_match() sets match_start */
1490 if (match_length > lookahead) match_length = lookahead; 1517 if (match_length > lookahead)
1491 1518 match_length = lookahead;
1492 /* Ignore a length 3 match if it is too distant: */ 1519
1493 if (match_length == MIN_MATCH && strstart-match_start > TOO_FAR){ 1520 /* Ignore a length 3 match if it is too distant: */
1494 /* If prev_match is also MIN_MATCH, match_start is garbage 1521 if (match_length == MIN_MATCH
1495 * but we will ignore the current match anyway. 1522 && strstart - match_start > TOO_FAR) {
1496 */ 1523 /* If prev_match is also MIN_MATCH, match_start is garbage
1497 match_length--; 1524 * but we will ignore the current match anyway.
1498 } 1525 */
1499 } 1526 match_length--;
1500 /* If there was a match at the previous step and the current 1527 }
1501 * match is not better, output the previous match: 1528 }
1502 */ 1529 /* If there was a match at the previous step and the current
1503 if (prev_length >= MIN_MATCH && match_length <= prev_length) { 1530 * match is not better, output the previous match:
1504 1531 */
1505 check_match(strstart-1, prev_match, prev_length); 1532 if (prev_length >= MIN_MATCH && match_length <= prev_length) {
1506 1533
1507 flush = ct_tally(strstart-1-prev_match, prev_length - MIN_MATCH); 1534 check_match(strstart - 1, prev_match, prev_length);
1508 1535
1509 /* Insert in hash table all strings up to the end of the match. 1536 flush =
1510 * strstart-1 and strstart are already inserted. 1537 ct_tally(strstart - 1 - prev_match,
1511 */ 1538 prev_length - MIN_MATCH);
1512 lookahead -= prev_length-1; 1539
1513 prev_length -= 2; 1540 /* Insert in hash table all strings up to the end of the match.
1514 do { 1541 * strstart-1 and strstart are already inserted.
1515 strstart++; 1542 */
1516 INSERT_STRING(strstart, hash_head); 1543 lookahead -= prev_length - 1;
1517 /* strstart never exceeds WSIZE-MAX_MATCH, so there are 1544 prev_length -= 2;
1518 * always MIN_MATCH bytes ahead. If lookahead < MIN_MATCH 1545 do {
1519 * these bytes are garbage, but it does not matter since the 1546 strstart++;
1520 * next lookahead bytes will always be emitted as literals. 1547 INSERT_STRING(strstart, hash_head);
1521 */ 1548 /* strstart never exceeds WSIZE-MAX_MATCH, so there are
1522 } while (--prev_length != 0); 1549 * always MIN_MATCH bytes ahead. If lookahead < MIN_MATCH
1523 match_available = 0; 1550 * these bytes are garbage, but it does not matter since the
1524 match_length = MIN_MATCH-1; 1551 * next lookahead bytes will always be emitted as literals.
1525 strstart++; 1552 */
1526 if (flush) FLUSH_BLOCK(0), block_start = strstart; 1553 } while (--prev_length != 0);
1527 1554 match_available = 0;
1528 } else if (match_available) { 1555 match_length = MIN_MATCH - 1;
1529 /* If there was no match at the previous position, output a 1556 strstart++;
1530 * single literal. If there was a match but the current match 1557 if (flush)
1531 * is longer, truncate the previous match to a single literal. 1558 FLUSH_BLOCK(0), block_start = strstart;
1532 */ 1559
1533 Tracevv((stderr,"%c",window[strstart-1])); 1560 } else if (match_available) {
1534 if (ct_tally (0, window[strstart-1])) { 1561 /* If there was no match at the previous position, output a
1535 FLUSH_BLOCK(0), block_start = strstart; 1562 * single literal. If there was a match but the current match
1536 } 1563 * is longer, truncate the previous match to a single literal.
1537 strstart++; 1564 */
1538 lookahead--; 1565 Tracevv((stderr, "%c", window[strstart - 1]));
1539 } else { 1566 if (ct_tally(0, window[strstart - 1])) {
1540 /* There is no previous match to compare with, wait for 1567 FLUSH_BLOCK(0), block_start = strstart;
1541 * the next step to decide. 1568 }
1542 */ 1569 strstart++;
1543 match_available = 1; 1570 lookahead--;
1544 strstart++; 1571 } else {
1545 lookahead--; 1572 /* There is no previous match to compare with, wait for
1546 } 1573 * the next step to decide.
1547 Assert (strstart <= isize && lookahead <= isize, "a bit too far"); 1574 */
1548 1575 match_available = 1;
1549 /* Make sure that we always have enough lookahead, except 1576 strstart++;
1550 * at the end of the input file. We need MAX_MATCH bytes 1577 lookahead--;
1551 * for the next match, plus MIN_MATCH bytes to insert the 1578 }
1552 * string following the next match. 1579 Assert(strstart <= isize && lookahead <= isize, "a bit too far");
1553 */ 1580
1554 while (lookahead < MIN_LOOKAHEAD && !eofile) fill_window(); 1581 /* Make sure that we always have enough lookahead, except
1555 } 1582 * at the end of the input file. We need MAX_MATCH bytes
1556 if (match_available) ct_tally (0, window[strstart-1]); 1583 * for the next match, plus MIN_MATCH bytes to insert the
1557 1584 * string following the next match.
1558 return FLUSH_BLOCK(1); /* eof */ 1585 */
1586 while (lookahead < MIN_LOOKAHEAD && !eofile)
1587 fill_window();
1588 }
1589 if (match_available)
1590 ct_tally(0, window[strstart - 1]);
1591
1592 return FLUSH_BLOCK(1); /* eof */
1559} 1593}
1594
1560/* gzip (GNU zip) -- compress files with zip algorithm and 'compress' interface 1595/* gzip (GNU zip) -- compress files with zip algorithm and 'compress' interface
1561 * Copyright (C) 1992-1993 Jean-loup Gailly 1596 * Copyright (C) 1992-1993 Jean-loup Gailly
1562 * The unzip code was written and put in the public domain by Mark Adler. 1597 * The unzip code was written and put in the public domain by Mark Adler.
@@ -1611,29 +1646,33 @@ ulg deflate()
1611#if defined(STDC_HEADERS) || !defined(NO_STDLIB_H) 1646#if defined(STDC_HEADERS) || !defined(NO_STDLIB_H)
1612# include <stdlib.h> 1647# include <stdlib.h>
1613#else 1648#else
1614 extern int errno; 1649extern int errno;
1615#endif 1650#endif
1616 1651
1617#if defined(DIRENT) 1652#if defined(DIRENT)
1618# include <dirent.h> 1653# include <dirent.h>
1619 typedef struct dirent dir_type; 1654typedef struct dirent dir_type;
1655
1620# define NLENGTH(dirent) ((int)strlen((dirent)->d_name)) 1656# define NLENGTH(dirent) ((int)strlen((dirent)->d_name))
1621# define DIR_OPT "DIRENT" 1657# define DIR_OPT "DIRENT"
1622#else 1658#else
1623# define NLENGTH(dirent) ((dirent)->d_namlen) 1659# define NLENGTH(dirent) ((dirent)->d_namlen)
1624# ifdef SYSDIR 1660# ifdef SYSDIR
1625# include <sys/dir.h> 1661# include <sys/dir.h>
1626 typedef struct direct dir_type; 1662typedef struct direct dir_type;
1663
1627# define DIR_OPT "SYSDIR" 1664# define DIR_OPT "SYSDIR"
1628# else 1665# else
1629# ifdef SYSNDIR 1666# ifdef SYSNDIR
1630# include <sys/ndir.h> 1667# include <sys/ndir.h>
1631 typedef struct direct dir_type; 1668typedef struct direct dir_type;
1669
1632# define DIR_OPT "SYSNDIR" 1670# define DIR_OPT "SYSNDIR"
1633# else 1671# else
1634# ifdef NDIR 1672# ifdef NDIR
1635# include <ndir.h> 1673# include <ndir.h>
1636 typedef struct direct dir_type; 1674typedef struct direct dir_type;
1675
1637# define DIR_OPT "NDIR" 1676# define DIR_OPT "NDIR"
1638# else 1677# else
1639# define NO_DIR 1678# define NO_DIR
@@ -1652,10 +1691,11 @@ ulg deflate()
1652# include <sys/utime.h> 1691# include <sys/utime.h>
1653# define TIME_OPT "SYS_UTIME" 1692# define TIME_OPT "SYS_UTIME"
1654# else 1693# else
1655 struct utimbuf { 1694struct utimbuf {
1656 time_t actime; 1695 time_t actime;
1657 time_t modtime; 1696 time_t modtime;
1658 }; 1697};
1698
1659# define TIME_OPT "" 1699# define TIME_OPT ""
1660# endif 1700# endif
1661# endif 1701# endif
@@ -1670,10 +1710,10 @@ ulg deflate()
1670# define S_ISREG(m) (((m) & S_IFMT) == S_IFREG) 1710# define S_ISREG(m) (((m) & S_IFMT) == S_IFREG)
1671#endif 1711#endif
1672 1712
1673typedef RETSIGTYPE (*sig_type) OF((int)); 1713typedef RETSIGTYPE(*sig_type) OF((int));
1674 1714
1675#ifndef O_BINARY 1715#ifndef O_BINARY
1676# define O_BINARY 0 /* creation mode for open() */ 1716# define O_BINARY 0 /* creation mode for open() */
1677#endif 1717#endif
1678 1718
1679#ifndef O_CREAT 1719#ifndef O_CREAT
@@ -1693,10 +1733,10 @@ typedef RETSIGTYPE (*sig_type) OF((int));
1693#ifndef S_IWUSR 1733#ifndef S_IWUSR
1694# define S_IWUSR 0200 1734# define S_IWUSR 0200
1695#endif 1735#endif
1696#define RW_USER (S_IRUSR | S_IWUSR) /* creation mode for open() */ 1736#define RW_USER (S_IRUSR | S_IWUSR) /* creation mode for open() */
1697 1737
1698#ifndef MAX_PATH_LEN 1738#ifndef MAX_PATH_LEN
1699# define MAX_PATH_LEN 1024 /* max pathname length */ 1739# define MAX_PATH_LEN 1024 /* max pathname length */
1700#endif 1740#endif
1701 1741
1702#ifndef SEEK_END 1742#ifndef SEEK_END
@@ -1704,8 +1744,8 @@ typedef RETSIGTYPE (*sig_type) OF((int));
1704#endif 1744#endif
1705 1745
1706#ifdef NO_OFF_T 1746#ifdef NO_OFF_T
1707 typedef long off_t; 1747typedef long off_t;
1708 off_t lseek OF((int fd, off_t offset, int whence)); 1748off_t lseek OF((int fd, off_t offset, int whence));
1709#endif 1749#endif
1710 1750
1711/* Separator for file name parts (see shorten_name()) */ 1751/* Separator for file name parts (see shorten_name()) */
@@ -1717,48 +1757,48 @@ typedef RETSIGTYPE (*sig_type) OF((int));
1717 1757
1718 /* global buffers */ 1758 /* global buffers */
1719 1759
1720DECLARE(uch, inbuf, INBUFSIZ +INBUF_EXTRA); 1760DECLARE(uch, inbuf, INBUFSIZ + INBUF_EXTRA);
1721DECLARE(uch, outbuf, OUTBUFSIZ+OUTBUF_EXTRA); 1761DECLARE(uch, outbuf, OUTBUFSIZ + OUTBUF_EXTRA);
1722DECLARE(ush, d_buf, DIST_BUFSIZE); 1762DECLARE(ush, d_buf, DIST_BUFSIZE);
1723DECLARE(uch, window, 2L*WSIZE); 1763DECLARE(uch, window, 2L * WSIZE);
1724#ifndef MAXSEG_64K 1764#ifndef MAXSEG_64K
1725 DECLARE(ush, tab_prefix, 1L<<BITS); 1765DECLARE(ush, tab_prefix, 1L << BITS);
1726#else 1766#else
1727 DECLARE(ush, tab_prefix0, 1L<<(BITS-1)); 1767DECLARE(ush, tab_prefix0, 1L << (BITS - 1));
1728 DECLARE(ush, tab_prefix1, 1L<<(BITS-1)); 1768DECLARE(ush, tab_prefix1, 1L << (BITS - 1));
1729#endif 1769#endif
1730 1770
1731 /* local variables */ 1771 /* local variables */
1732 1772
1733int ascii = 0; /* convert end-of-lines to local OS conventions */ 1773int ascii = 0; /* convert end-of-lines to local OS conventions */
1734int decompress = 0; /* decompress (-d) */ 1774int decompress = 0; /* decompress (-d) */
1735int no_name = -1; /* don't save or restore the original file name */ 1775int no_name = -1; /* don't save or restore the original file name */
1736int no_time = -1; /* don't save or restore the original file time */ 1776int no_time = -1; /* don't save or restore the original file time */
1737int foreground; /* set if program run in foreground */ 1777int foreground; /* set if program run in foreground */
1738char *progname; /* program name */ 1778char *progname; /* program name */
1739static int method = DEFLATED;/* compression method */ 1779static int method = DEFLATED; /* compression method */
1740static int exit_code = OK; /* program exit code */ 1780static int exit_code = OK; /* program exit code */
1741int save_orig_name; /* set if original name must be saved */ 1781int save_orig_name; /* set if original name must be saved */
1742int last_member; /* set for .zip and .Z files */ 1782int last_member; /* set for .zip and .Z files */
1743int part_nb; /* number of parts in .gz file */ 1783int part_nb; /* number of parts in .gz file */
1744long time_stamp; /* original time stamp (modification time) */ 1784long time_stamp; /* original time stamp (modification time) */
1745long ifile_size; /* input file size, -1 for devices (debug only) */ 1785long ifile_size; /* input file size, -1 for devices (debug only) */
1746char *env; /* contents of GZIP env variable */ 1786char *env; /* contents of GZIP env variable */
1747char **args = NULL; /* argv pointer if GZIP env variable defined */ 1787char **args = NULL; /* argv pointer if GZIP env variable defined */
1748char z_suffix[MAX_SUFFIX+1]; /* default suffix (can be set with --suffix) */ 1788char z_suffix[MAX_SUFFIX + 1]; /* default suffix (can be set with --suffix) */
1749int z_len; /* strlen(z_suffix) */ 1789int z_len; /* strlen(z_suffix) */
1750 1790
1751long bytes_in; /* number of input bytes */ 1791long bytes_in; /* number of input bytes */
1752long bytes_out; /* number of output bytes */ 1792long bytes_out; /* number of output bytes */
1753char ifname[MAX_PATH_LEN]; /* input file name */ 1793char ifname[MAX_PATH_LEN]; /* input file name */
1754char ofname[MAX_PATH_LEN]; /* output file name */ 1794char ofname[MAX_PATH_LEN]; /* output file name */
1755int remove_ofname = 0; /* remove output file on error */ 1795int remove_ofname = 0; /* remove output file on error */
1756struct stat istat; /* status for input file */ 1796struct stat istat; /* status for input file */
1757int ifd; /* input file descriptor */ 1797int ifd; /* input file descriptor */
1758int ofd; /* output file descriptor */ 1798int ofd; /* output file descriptor */
1759unsigned insize; /* valid bytes in inbuf */ 1799unsigned insize; /* valid bytes in inbuf */
1760unsigned inptr; /* index of next byte to be processed in inbuf */ 1800unsigned inptr; /* index of next byte to be processed in inbuf */
1761unsigned outcnt; /* bytes in output buffer */ 1801unsigned outcnt; /* bytes in output buffer */
1762 1802
1763/* local functions */ 1803/* local functions */
1764 1804
@@ -1768,148 +1808,148 @@ unsigned outcnt; /* bytes in output buffer */
1768// int main (argc, argv) 1808// int main (argc, argv)
1769// int argc; 1809// int argc;
1770// char **argv; 1810// char **argv;
1771int gzip_main(int argc, char ** argv) 1811int gzip_main(int argc, char **argv)
1772{ 1812{
1773 int result; 1813 int result;
1774 int inFileNum; 1814 int inFileNum;
1775 int outFileNum; 1815 int outFileNum;
1776 struct stat statBuf; 1816 struct stat statBuf;
1777 char* delFileName; 1817 char *delFileName;
1778 int tostdout = 0; 1818 int tostdout = 0;
1779 int fromstdin = 0; 1819 int fromstdin = 0;
1780 1820
1781 if (argc==1) 1821 if (argc == 1)
1782 usage(gzip_usage);
1783
1784 /* Parse any options */
1785 while (--argc > 0 && **(++argv) == '-') {
1786 if (*((*argv)+1) == '\0') {
1787 fromstdin = 1;
1788 tostdout = 1;
1789 }
1790 while (*(++(*argv))) {
1791 switch (**argv) {
1792 case 'c':
1793 tostdout = 1;
1794 break;
1795 default:
1796 usage(gzip_usage); 1822 usage(gzip_usage);
1797 } 1823
1824 /* Parse any options */
1825 while (--argc > 0 && **(++argv) == '-') {
1826 if (*((*argv) + 1) == '\0') {
1827 fromstdin = 1;
1828 tostdout = 1;
1829 }
1830 while (*(++(*argv))) {
1831 switch (**argv) {
1832 case 'c':
1833 tostdout = 1;
1834 break;
1835 default:
1836 usage(gzip_usage);
1837 }
1838 }
1798 } 1839 }
1799 }
1800 1840
1801 foreground = signal(SIGINT, SIG_IGN) != SIG_IGN; 1841 foreground = signal(SIGINT, SIG_IGN) != SIG_IGN;
1802 if (foreground) { 1842 if (foreground) {
1803 (void) signal (SIGINT, (sig_type)abort_gzip); 1843 (void) signal(SIGINT, (sig_type) abort_gzip);
1804 } 1844 }
1805#ifdef SIGTERM 1845#ifdef SIGTERM
1806 if (signal(SIGTERM, SIG_IGN) != SIG_IGN) { 1846 if (signal(SIGTERM, SIG_IGN) != SIG_IGN) {
1807 (void) signal(SIGTERM, (sig_type)abort_gzip); 1847 (void) signal(SIGTERM, (sig_type) abort_gzip);
1808 } 1848 }
1809#endif 1849#endif
1810#ifdef SIGHUP 1850#ifdef SIGHUP
1811 if (signal(SIGHUP, SIG_IGN) != SIG_IGN) { 1851 if (signal(SIGHUP, SIG_IGN) != SIG_IGN) {
1812 (void) signal(SIGHUP, (sig_type)abort_gzip); 1852 (void) signal(SIGHUP, (sig_type) abort_gzip);
1813 } 1853 }
1814#endif 1854#endif
1815 1855
1816 strncpy(z_suffix, Z_SUFFIX, sizeof(z_suffix)-1); 1856 strncpy(z_suffix, Z_SUFFIX, sizeof(z_suffix) - 1);
1817 z_len = strlen(z_suffix); 1857 z_len = strlen(z_suffix);
1818 1858
1819 /* Allocate all global buffers (for DYN_ALLOC option) */ 1859 /* Allocate all global buffers (for DYN_ALLOC option) */
1820 ALLOC(uch, inbuf, INBUFSIZ +INBUF_EXTRA); 1860 ALLOC(uch, inbuf, INBUFSIZ + INBUF_EXTRA);
1821 ALLOC(uch, outbuf, OUTBUFSIZ+OUTBUF_EXTRA); 1861 ALLOC(uch, outbuf, OUTBUFSIZ + OUTBUF_EXTRA);
1822 ALLOC(ush, d_buf, DIST_BUFSIZE); 1862 ALLOC(ush, d_buf, DIST_BUFSIZE);
1823 ALLOC(uch, window, 2L*WSIZE); 1863 ALLOC(uch, window, 2L * WSIZE);
1824#ifndef MAXSEG_64K 1864#ifndef MAXSEG_64K
1825 ALLOC(ush, tab_prefix, 1L<<BITS); 1865 ALLOC(ush, tab_prefix, 1L << BITS);
1826#else 1866#else
1827 ALLOC(ush, tab_prefix0, 1L<<(BITS-1)); 1867 ALLOC(ush, tab_prefix0, 1L << (BITS - 1));
1828 ALLOC(ush, tab_prefix1, 1L<<(BITS-1)); 1868 ALLOC(ush, tab_prefix1, 1L << (BITS - 1));
1829#endif 1869#endif
1830 1870
1831 if (fromstdin==1) { 1871 if (fromstdin == 1) {
1832 strcpy(ofname, "stdin"); 1872 strcpy(ofname, "stdin");
1833 1873
1834 inFileNum=fileno(stdin); 1874 inFileNum = fileno(stdin);
1835 time_stamp = 0; /* time unknown by default */ 1875 time_stamp = 0; /* time unknown by default */
1836 ifile_size = -1L; /* convention for unknown size */ 1876 ifile_size = -1L; /* convention for unknown size */
1837 } else { 1877 } else {
1838 /* Open up the input file */ 1878 /* Open up the input file */
1839 if (*argv=='\0') 1879 if (*argv == '\0')
1840 usage(gzip_usage); 1880 usage(gzip_usage);
1841 strncpy(ifname, *argv, MAX_PATH_LEN); 1881 strncpy(ifname, *argv, MAX_PATH_LEN);
1842 1882
1843 /* Open input fille */ 1883 /* Open input fille */
1844 inFileNum=open( ifname, O_RDONLY); 1884 inFileNum = open(ifname, O_RDONLY);
1845 if (inFileNum < 0) { 1885 if (inFileNum < 0) {
1846 perror(ifname); 1886 perror(ifname);
1847 do_exit(WARNING); 1887 do_exit(WARNING);
1848 } 1888 }
1849 /* Get the time stamp on the input file. */ 1889 /* Get the time stamp on the input file. */
1850 result = stat(ifname, &statBuf); 1890 result = stat(ifname, &statBuf);
1851 if (result < 0) { 1891 if (result < 0) {
1852 perror(ifname); 1892 perror(ifname);
1853 do_exit(WARNING); 1893 do_exit(WARNING);
1894 }
1895 time_stamp = statBuf.st_ctime;
1896 ifile_size = statBuf.st_size;
1854 } 1897 }
1855 time_stamp = statBuf.st_ctime;
1856 ifile_size = statBuf.st_size;
1857 }
1858 1898
1859 1899
1860 if (tostdout==1) { 1900 if (tostdout == 1) {
1861 /* And get to work */ 1901 /* And get to work */
1862 strcpy(ofname, "stdout"); 1902 strcpy(ofname, "stdout");
1863 outFileNum=fileno(stdout); 1903 outFileNum = fileno(stdout);
1864 SET_BINARY_MODE(fileno(stdout)); 1904 SET_BINARY_MODE(fileno(stdout));
1865 1905
1866 clear_bufs(); /* clear input and output buffers */ 1906 clear_bufs(); /* clear input and output buffers */
1867 part_nb = 0; 1907 part_nb = 0;
1868 1908
1869 /* Actually do the compression/decompression. */ 1909 /* Actually do the compression/decompression. */
1870 zip(inFileNum, outFileNum); 1910 zip(inFileNum, outFileNum);
1871 1911
1872 } else { 1912 } else {
1873 1913
1874 /* And get to work */ 1914 /* And get to work */
1875 strncpy(ofname, ifname, MAX_PATH_LEN-4); 1915 strncpy(ofname, ifname, MAX_PATH_LEN - 4);
1876 strcat(ofname, ".gz"); 1916 strcat(ofname, ".gz");
1877 1917
1878 1918
1879 /* Open output fille */ 1919 /* Open output fille */
1880#if (__GLIBC__ >= 2) && (__GLIBC_MINOR__ >= 1) 1920#if (__GLIBC__ >= 2) && (__GLIBC_MINOR__ >= 1)
1881 outFileNum=open( ofname, O_RDWR|O_CREAT|O_EXCL|O_NOFOLLOW); 1921 outFileNum = open(ofname, O_RDWR | O_CREAT | O_EXCL | O_NOFOLLOW);
1882#else 1922#else
1883 outFileNum=open( ofname, O_RDWR|O_CREAT|O_EXCL); 1923 outFileNum = open(ofname, O_RDWR | O_CREAT | O_EXCL);
1884#endif 1924#endif
1885 if (outFileNum < 0) { 1925 if (outFileNum < 0) {
1886 perror(ofname); 1926 perror(ofname);
1887 do_exit(WARNING); 1927 do_exit(WARNING);
1888 } 1928 }
1889 SET_BINARY_MODE(outFileNum); 1929 SET_BINARY_MODE(outFileNum);
1890 /* Set permissions on the file */ 1930 /* Set permissions on the file */
1891 fchmod(outFileNum, statBuf.st_mode); 1931 fchmod(outFileNum, statBuf.st_mode);
1892 1932
1893 clear_bufs(); /* clear input and output buffers */ 1933 clear_bufs(); /* clear input and output buffers */
1894 part_nb = 0; 1934 part_nb = 0;
1895 1935
1896 /* Actually do the compression/decompression. */ 1936 /* Actually do the compression/decompression. */
1897 result=zip(inFileNum, outFileNum); 1937 result = zip(inFileNum, outFileNum);
1898 close( outFileNum); 1938 close(outFileNum);
1899 close( inFileNum); 1939 close(inFileNum);
1900 /* Delete the original file */ 1940 /* Delete the original file */
1901 if (result == OK) 1941 if (result == OK)
1902 delFileName=ifname; 1942 delFileName = ifname;
1903 else 1943 else
1904 delFileName=ofname; 1944 delFileName = ofname;
1905 1945
1906 if (unlink (delFileName) < 0) { 1946 if (unlink(delFileName) < 0) {
1907 perror (delFileName); 1947 perror(delFileName);
1908 exit( FALSE); 1948 exit(FALSE);
1949 }
1909 } 1950 }
1910 }
1911 1951
1912 do_exit(exit_code); 1952 do_exit(exit_code);
1913} 1953}
1914 1954
1915/* trees.c -- output deflated data using Huffman coding 1955/* trees.c -- output deflated data using Huffman coding
@@ -1998,14 +2038,16 @@ int gzip_main(int argc, char ** argv)
1998/* number of codes used to transfer the bit lengths */ 2038/* number of codes used to transfer the bit lengths */
1999 2039
2000 2040
2001local int near extra_lbits[LENGTH_CODES] /* extra bits for each length code */ 2041local int near extra_lbits[LENGTH_CODES] /* extra bits for each length code */
2002 = {0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0}; 2042 = { 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4,
2043 4, 4, 5, 5, 5, 5, 0 };
2003 2044
2004local int near extra_dbits[D_CODES] /* extra bits for each distance code */ 2045local int near extra_dbits[D_CODES] /* extra bits for each distance code */
2005 = {0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13}; 2046 = { 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9,
2047 10, 10, 11, 11, 12, 12, 13, 13 };
2006 2048
2007local int near extra_blbits[BL_CODES]/* extra bits for each bit length code */ 2049local int near extra_blbits[BL_CODES] /* extra bits for each bit length code */
2008 = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7}; 2050= { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 7 };
2009 2051
2010#define STORED_BLOCK 0 2052#define STORED_BLOCK 0
2011#define STATIC_TREES 1 2053#define STATIC_TREES 1
@@ -2047,32 +2089,24 @@ local int near extra_blbits[BL_CODES]/* extra bits for each bit length code */
2047 * if we rely on DIST_BUFSIZE == LIT_BUFSIZE. 2089 * if we rely on DIST_BUFSIZE == LIT_BUFSIZE.
2048 */ 2090 */
2049#if LIT_BUFSIZE > INBUFSIZ 2091#if LIT_BUFSIZE > INBUFSIZ
2050 error cannot overlay l_buf and inbuf 2092error cannot overlay l_buf and inbuf
2051#endif 2093#endif
2052
2053#define REP_3_6 16 2094#define REP_3_6 16
2054/* repeat previous bit length 3-6 times (2 bits of repeat count) */ 2095/* repeat previous bit length 3-6 times (2 bits of repeat count) */
2055
2056#define REPZ_3_10 17 2096#define REPZ_3_10 17
2057/* repeat a zero length 3-10 times (3 bits of repeat count) */ 2097/* repeat a zero length 3-10 times (3 bits of repeat count) */
2058
2059#define REPZ_11_138 18 2098#define REPZ_11_138 18
2060/* repeat a zero length 11-138 times (7 bits of repeat count) */ 2099/* repeat a zero length 11-138 times (7 bits of repeat count) *//* ===========================================================================
2061
2062/* ===========================================================================
2063 * Local data 2100 * Local data
2064 */ 2101 *//* Data structure describing a single value and its code string. */ typedef struct ct_data {
2065 2102 union {
2066/* Data structure describing a single value and its code string. */ 2103 ush freq; /* frequency count */
2067typedef struct ct_data { 2104 ush code; /* bit string */
2068 union { 2105 } fc;
2069 ush freq; /* frequency count */ 2106 union {
2070 ush code; /* bit string */ 2107 ush dad; /* father node in Huffman tree */
2071 } fc; 2108 ush len; /* length of bit string */
2072 union { 2109 } dl;
2073 ush dad; /* father node in Huffman tree */
2074 ush len; /* length of bit string */
2075 } dl;
2076} ct_data; 2110} ct_data;
2077 2111
2078#define Freq fc.freq 2112#define Freq fc.freq
@@ -2083,10 +2117,11 @@ typedef struct ct_data {
2083#define HEAP_SIZE (2*L_CODES+1) 2117#define HEAP_SIZE (2*L_CODES+1)
2084/* maximum heap size */ 2118/* maximum heap size */
2085 2119
2086local ct_data near dyn_ltree[HEAP_SIZE]; /* literal and length tree */ 2120local ct_data near dyn_ltree[HEAP_SIZE]; /* literal and length tree */
2087local ct_data near dyn_dtree[2*D_CODES+1]; /* distance tree */ 2121local ct_data near dyn_dtree[2 * D_CODES + 1]; /* distance tree */
2122
2123local ct_data near static_ltree[L_CODES + 2];
2088 2124
2089local ct_data near static_ltree[L_CODES+2];
2090/* The static literal tree. Since the bit lengths are imposed, there is no 2125/* The static literal tree. Since the bit lengths are imposed, there is no
2091 * need for the L_CODES extra codes used during heap construction. However 2126 * need for the L_CODES extra codes used during heap construction. However
2092 * The codes 286 and 287 are needed to build a canonical tree (see ct_init 2127 * The codes 286 and 287 are needed to build a canonical tree (see ct_init
@@ -2094,65 +2129,77 @@ local ct_data near static_ltree[L_CODES+2];
2094 */ 2129 */
2095 2130
2096local ct_data near static_dtree[D_CODES]; 2131local ct_data near static_dtree[D_CODES];
2132
2097/* The static distance tree. (Actually a trivial tree since all codes use 2133/* The static distance tree. (Actually a trivial tree since all codes use
2098 * 5 bits.) 2134 * 5 bits.)
2099 */ 2135 */
2100 2136
2101local ct_data near bl_tree[2*BL_CODES+1]; 2137local ct_data near bl_tree[2 * BL_CODES + 1];
2138
2102/* Huffman tree for the bit lengths */ 2139/* Huffman tree for the bit lengths */
2103 2140
2104typedef struct tree_desc { 2141typedef struct tree_desc {
2105 ct_data near *dyn_tree; /* the dynamic tree */ 2142 ct_data near *dyn_tree; /* the dynamic tree */
2106 ct_data near *static_tree; /* corresponding static tree or NULL */ 2143 ct_data near *static_tree; /* corresponding static tree or NULL */
2107 int near *extra_bits; /* extra bits for each code or NULL */ 2144 int near *extra_bits; /* extra bits for each code or NULL */
2108 int extra_base; /* base index for extra_bits */ 2145 int extra_base; /* base index for extra_bits */
2109 int elems; /* max number of elements in the tree */ 2146 int elems; /* max number of elements in the tree */
2110 int max_length; /* max bit length for the codes */ 2147 int max_length; /* max bit length for the codes */
2111 int max_code; /* largest code with non zero frequency */ 2148 int max_code; /* largest code with non zero frequency */
2112} tree_desc; 2149} tree_desc;
2113 2150
2114local tree_desc near l_desc = 2151local tree_desc near l_desc =
2115{dyn_ltree, static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS, 0}; 2152 { dyn_ltree, static_ltree, extra_lbits, LITERALS + 1, L_CODES,
2153 MAX_BITS, 0 };
2116 2154
2117local tree_desc near d_desc = 2155local tree_desc near d_desc =
2118{dyn_dtree, static_dtree, extra_dbits, 0, D_CODES, MAX_BITS, 0}; 2156 { dyn_dtree, static_dtree, extra_dbits, 0, D_CODES, MAX_BITS, 0 };
2119 2157
2120local tree_desc near bl_desc = 2158local tree_desc near bl_desc =
2121{bl_tree, (ct_data near *)0, extra_blbits, 0, BL_CODES, MAX_BL_BITS, 0}; 2159 { bl_tree, (ct_data near *) 0, extra_blbits, 0, BL_CODES, MAX_BL_BITS,
2160 0 };
2122 2161
2123 2162
2124local ush near bl_count[MAX_BITS+1]; 2163local ush near bl_count[MAX_BITS + 1];
2164
2125/* number of codes at each bit length for an optimal tree */ 2165/* number of codes at each bit length for an optimal tree */
2126 2166
2127local uch near bl_order[BL_CODES] 2167local uch near bl_order[BL_CODES]
2128 = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15}; 2168= { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
2169
2129/* The lengths of the bit length codes are sent in order of decreasing 2170/* The lengths of the bit length codes are sent in order of decreasing
2130 * probability, to avoid transmitting the lengths for unused bit length codes. 2171 * probability, to avoid transmitting the lengths for unused bit length codes.
2131 */ 2172 */
2132 2173
2133local int near heap[2*L_CODES+1]; /* heap used to build the Huffman trees */ 2174local int near heap[2 * L_CODES + 1]; /* heap used to build the Huffman trees */
2134local int heap_len; /* number of elements in the heap */ 2175local int heap_len; /* number of elements in the heap */
2135local int heap_max; /* element of largest frequency */ 2176local int heap_max; /* element of largest frequency */
2177
2136/* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used. 2178/* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.
2137 * The same heap array is used to build all trees. 2179 * The same heap array is used to build all trees.
2138 */ 2180 */
2139 2181
2140local uch near depth[2*L_CODES+1]; 2182local uch near depth[2 * L_CODES + 1];
2183
2141/* Depth of each subtree used as tie breaker for trees of equal frequency */ 2184/* Depth of each subtree used as tie breaker for trees of equal frequency */
2142 2185
2143local uch length_code[MAX_MATCH-MIN_MATCH+1]; 2186local uch length_code[MAX_MATCH - MIN_MATCH + 1];
2187
2144/* length code for each normalized match length (0 == MIN_MATCH) */ 2188/* length code for each normalized match length (0 == MIN_MATCH) */
2145 2189
2146local uch dist_code[512]; 2190local uch dist_code[512];
2191
2147/* distance codes. The first 256 values correspond to the distances 2192/* distance codes. The first 256 values correspond to the distances
2148 * 3 .. 258, the last 256 values correspond to the top 8 bits of 2193 * 3 .. 258, the last 256 values correspond to the top 8 bits of
2149 * the 15 bit distances. 2194 * the 15 bit distances.
2150 */ 2195 */
2151 2196
2152local int near base_length[LENGTH_CODES]; 2197local int near base_length[LENGTH_CODES];
2198
2153/* First normalized length for each code (0 = MIN_MATCH) */ 2199/* First normalized length for each code (0 = MIN_MATCH) */
2154 2200
2155local int near base_dist[D_CODES]; 2201local int near base_dist[D_CODES];
2202
2156/* First normalized distance for each code (0 = distance of 1) */ 2203/* First normalized distance for each code (0 = distance of 1) */
2157 2204
2158#define l_buf inbuf 2205#define l_buf inbuf
@@ -2160,62 +2207,65 @@ local int near base_dist[D_CODES];
2160 2207
2161/* DECLARE(ush, d_buf, DIST_BUFSIZE); buffer for distances */ 2208/* DECLARE(ush, d_buf, DIST_BUFSIZE); buffer for distances */
2162 2209
2163local uch near flag_buf[(LIT_BUFSIZE/8)]; 2210local uch near flag_buf[(LIT_BUFSIZE / 8)];
2211
2164/* flag_buf is a bit array distinguishing literals from lengths in 2212/* flag_buf is a bit array distinguishing literals from lengths in
2165 * l_buf, thus indicating the presence or absence of a distance. 2213 * l_buf, thus indicating the presence or absence of a distance.
2166 */ 2214 */
2167 2215
2168local unsigned last_lit; /* running index in l_buf */ 2216local unsigned last_lit; /* running index in l_buf */
2169local unsigned last_dist; /* running index in d_buf */ 2217local unsigned last_dist; /* running index in d_buf */
2170local unsigned last_flags; /* running index in flag_buf */ 2218local unsigned last_flags; /* running index in flag_buf */
2171local uch flags; /* current flags not yet saved in flag_buf */ 2219local uch flags; /* current flags not yet saved in flag_buf */
2172local uch flag_bit; /* current bit used in flags */ 2220local uch flag_bit; /* current bit used in flags */
2221
2173/* bits are filled in flags starting at bit 0 (least significant). 2222/* bits are filled in flags starting at bit 0 (least significant).
2174 * Note: these flags are overkill in the current code since we don't 2223 * Note: these flags are overkill in the current code since we don't
2175 * take advantage of DIST_BUFSIZE == LIT_BUFSIZE. 2224 * take advantage of DIST_BUFSIZE == LIT_BUFSIZE.
2176 */ 2225 */
2177 2226
2178local ulg opt_len; /* bit length of current block with optimal trees */ 2227local ulg opt_len; /* bit length of current block with optimal trees */
2179local ulg static_len; /* bit length of current block with static trees */ 2228local ulg static_len; /* bit length of current block with static trees */
2229
2230local ulg compressed_len; /* total bit length of compressed file */
2180 2231
2181local ulg compressed_len; /* total bit length of compressed file */ 2232local ulg input_len; /* total byte length of input file */
2182 2233
2183local ulg input_len; /* total byte length of input file */
2184/* input_len is for debugging only since we can get it by other means. */ 2234/* input_len is for debugging only since we can get it by other means. */
2185 2235
2186ush *file_type; /* pointer to UNKNOWN, BINARY or ASCII */ 2236ush *file_type; /* pointer to UNKNOWN, BINARY or ASCII */
2187int *file_method; /* pointer to DEFLATE or STORE */ 2237int *file_method; /* pointer to DEFLATE or STORE */
2188 2238
2189#ifdef DEBUG 2239#ifdef DEBUG
2190extern ulg bits_sent; /* bit length of the compressed data */ 2240extern ulg bits_sent; /* bit length of the compressed data */
2191extern long isize; /* byte length of input file */ 2241extern long isize; /* byte length of input file */
2192#endif 2242#endif
2193 2243
2194extern long block_start; /* window offset of current block */ 2244extern long block_start; /* window offset of current block */
2195extern unsigned near strstart; /* window offset of current string */ 2245extern unsigned near strstart; /* window offset of current string */
2196 2246
2197/* =========================================================================== 2247/* ===========================================================================
2198 * Local (static) routines in this file. 2248 * Local (static) routines in this file.
2199 */ 2249 */
2200 2250
2201local void init_block OF((void)); 2251local void init_block OF((void));
2202local void pqdownheap OF((ct_data near *tree, int k)); 2252local void pqdownheap OF((ct_data near * tree, int k));
2203local void gen_bitlen OF((tree_desc near *desc)); 2253local void gen_bitlen OF((tree_desc near * desc));
2204local void gen_codes OF((ct_data near *tree, int max_code)); 2254local void gen_codes OF((ct_data near * tree, int max_code));
2205local void build_tree OF((tree_desc near *desc)); 2255local void build_tree OF((tree_desc near * desc));
2206local void scan_tree OF((ct_data near *tree, int max_code)); 2256local void scan_tree OF((ct_data near * tree, int max_code));
2207local void send_tree OF((ct_data near *tree, int max_code)); 2257local void send_tree OF((ct_data near * tree, int max_code));
2208local int build_bl_tree OF((void)); 2258local int build_bl_tree OF((void));
2209local void send_all_trees OF((int lcodes, int dcodes, int blcodes)); 2259local void send_all_trees OF((int lcodes, int dcodes, int blcodes));
2210local void compress_block OF((ct_data near *ltree, ct_data near *dtree)); 2260local void compress_block OF((ct_data near * ltree, ct_data near * dtree));
2211local void set_file_type OF((void)); 2261local void set_file_type OF((void));
2212 2262
2213 2263
2214#ifndef DEBUG 2264#ifndef DEBUG
2215# define send_code(c, tree) send_bits(tree[c].Code, tree[c].Len) 2265# define send_code(c, tree) send_bits(tree[c].Code, tree[c].Len)
2216 /* Send a code of the given tree. c and tree must not have side effects */ 2266 /* Send a code of the given tree. c and tree must not have side effects */
2217 2267
2218#else /* DEBUG */ 2268#else /* DEBUG */
2219# define send_code(c, tree) \ 2269# define send_code(c, tree) \
2220 { if (verbose>1) fprintf(stderr,"\ncd %3d ",(c)); \ 2270 { if (verbose>1) fprintf(stderr,"\ncd %3d ",(c)); \
2221 send_bits(tree[c].Code, tree[c].Len); } 2271 send_bits(tree[c].Code, tree[c].Len); }
@@ -2237,75 +2287,81 @@ local void set_file_type OF((void));
2237 * (DEFLATE/STORE). 2287 * (DEFLATE/STORE).
2238 */ 2288 */
2239void ct_init(attr, methodp) 2289void ct_init(attr, methodp)
2240 ush *attr; /* pointer to internal file attribute */ 2290ush *attr; /* pointer to internal file attribute */
2241 int *methodp; /* pointer to compression method */ 2291int *methodp; /* pointer to compression method */
2242{ 2292{
2243 int n; /* iterates over tree elements */ 2293 int n; /* iterates over tree elements */
2244 int bits; /* bit counter */ 2294 int bits; /* bit counter */
2245 int length; /* length value */ 2295 int length; /* length value */
2246 int code; /* code value */ 2296 int code; /* code value */
2247 int dist; /* distance index */ 2297 int dist; /* distance index */
2248 2298
2249 file_type = attr; 2299 file_type = attr;
2250 file_method = methodp; 2300 file_method = methodp;
2251 compressed_len = input_len = 0L; 2301 compressed_len = input_len = 0L;
2252 2302
2253 if (static_dtree[0].Len != 0) return; /* ct_init already called */ 2303 if (static_dtree[0].Len != 0)
2254 2304 return; /* ct_init already called */
2255 /* Initialize the mapping length (0..255) -> length code (0..28) */ 2305
2256 length = 0; 2306 /* Initialize the mapping length (0..255) -> length code (0..28) */
2257 for (code = 0; code < LENGTH_CODES-1; code++) { 2307 length = 0;
2258 base_length[code] = length; 2308 for (code = 0; code < LENGTH_CODES - 1; code++) {
2259 for (n = 0; n < (1<<extra_lbits[code]); n++) { 2309 base_length[code] = length;
2260 length_code[length++] = (uch)code; 2310 for (n = 0; n < (1 << extra_lbits[code]); n++) {
2261 } 2311 length_code[length++] = (uch) code;
2262 } 2312 }
2263 Assert (length == 256, "ct_init: length != 256"); 2313 }
2264 /* Note that the length 255 (match length 258) can be represented 2314 Assert(length == 256, "ct_init: length != 256");
2265 * in two different ways: code 284 + 5 bits or code 285, so we 2315 /* Note that the length 255 (match length 258) can be represented
2266 * overwrite length_code[255] to use the best encoding: 2316 * in two different ways: code 284 + 5 bits or code 285, so we
2267 */ 2317 * overwrite length_code[255] to use the best encoding:
2268 length_code[length-1] = (uch)code; 2318 */
2269 2319 length_code[length - 1] = (uch) code;
2270 /* Initialize the mapping dist (0..32K) -> dist code (0..29) */ 2320
2271 dist = 0; 2321 /* Initialize the mapping dist (0..32K) -> dist code (0..29) */
2272 for (code = 0 ; code < 16; code++) { 2322 dist = 0;
2273 base_dist[code] = dist; 2323 for (code = 0; code < 16; code++) {
2274 for (n = 0; n < (1<<extra_dbits[code]); n++) { 2324 base_dist[code] = dist;
2275 dist_code[dist++] = (uch)code; 2325 for (n = 0; n < (1 << extra_dbits[code]); n++) {
2276 } 2326 dist_code[dist++] = (uch) code;
2277 } 2327 }
2278 Assert (dist == 256, "ct_init: dist != 256"); 2328 }
2279 dist >>= 7; /* from now on, all distances are divided by 128 */ 2329 Assert(dist == 256, "ct_init: dist != 256");
2280 for ( ; code < D_CODES; code++) { 2330 dist >>= 7; /* from now on, all distances are divided by 128 */
2281 base_dist[code] = dist << 7; 2331 for (; code < D_CODES; code++) {
2282 for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) { 2332 base_dist[code] = dist << 7;
2283 dist_code[256 + dist++] = (uch)code; 2333 for (n = 0; n < (1 << (extra_dbits[code] - 7)); n++) {
2284 } 2334 dist_code[256 + dist++] = (uch) code;
2285 } 2335 }
2286 Assert (dist == 256, "ct_init: 256+dist != 512"); 2336 }
2287 2337 Assert(dist == 256, "ct_init: 256+dist != 512");
2288 /* Construct the codes of the static literal tree */ 2338
2289 for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0; 2339 /* Construct the codes of the static literal tree */
2290 n = 0; 2340 for (bits = 0; bits <= MAX_BITS; bits++)
2291 while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++; 2341 bl_count[bits] = 0;
2292 while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++; 2342 n = 0;
2293 while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++; 2343 while (n <= 143)
2294 while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++; 2344 static_ltree[n++].Len = 8, bl_count[8]++;
2295 /* Codes 286 and 287 do not exist, but we must include them in the 2345 while (n <= 255)
2296 * tree construction to get a canonical Huffman tree (longest code 2346 static_ltree[n++].Len = 9, bl_count[9]++;
2297 * all ones) 2347 while (n <= 279)
2298 */ 2348 static_ltree[n++].Len = 7, bl_count[7]++;
2299 gen_codes((ct_data near *)static_ltree, L_CODES+1); 2349 while (n <= 287)
2300 2350 static_ltree[n++].Len = 8, bl_count[8]++;
2301 /* The static distance tree is trivial: */ 2351 /* Codes 286 and 287 do not exist, but we must include them in the
2302 for (n = 0; n < D_CODES; n++) { 2352 * tree construction to get a canonical Huffman tree (longest code
2303 static_dtree[n].Len = 5; 2353 * all ones)
2304 static_dtree[n].Code = bi_reverse(n, 5); 2354 */
2305 } 2355 gen_codes((ct_data near *) static_ltree, L_CODES + 1);
2306 2356
2307 /* Initialize the first block of the first file: */ 2357 /* The static distance tree is trivial: */
2308 init_block(); 2358 for (n = 0; n < D_CODES; n++) {
2359 static_dtree[n].Len = 5;
2360 static_dtree[n].Code = bi_reverse(n, 5);
2361 }
2362
2363 /* Initialize the first block of the first file: */
2364 init_block();
2309} 2365}
2310 2366
2311/* =========================================================================== 2367/* ===========================================================================
@@ -2313,17 +2369,21 @@ void ct_init(attr, methodp)
2313 */ 2369 */
2314local void init_block() 2370local void init_block()
2315{ 2371{
2316 int n; /* iterates over tree elements */ 2372 int n; /* iterates over tree elements */
2317 2373
2318 /* Initialize the trees. */ 2374 /* Initialize the trees. */
2319 for (n = 0; n < L_CODES; n++) dyn_ltree[n].Freq = 0; 2375 for (n = 0; n < L_CODES; n++)
2320 for (n = 0; n < D_CODES; n++) dyn_dtree[n].Freq = 0; 2376 dyn_ltree[n].Freq = 0;
2321 for (n = 0; n < BL_CODES; n++) bl_tree[n].Freq = 0; 2377 for (n = 0; n < D_CODES; n++)
2322 2378 dyn_dtree[n].Freq = 0;
2323 dyn_ltree[END_BLOCK].Freq = 1; 2379 for (n = 0; n < BL_CODES; n++)
2324 opt_len = static_len = 0L; 2380 bl_tree[n].Freq = 0;
2325 last_lit = last_dist = last_flags = 0; 2381
2326 flags = 0; flag_bit = 1; 2382 dyn_ltree[END_BLOCK].Freq = 1;
2383 opt_len = static_len = 0L;
2384 last_lit = last_dist = last_flags = 0;
2385 flags = 0;
2386 flag_bit = 1;
2327} 2387}
2328 2388
2329#define SMALLEST 1 2389#define SMALLEST 1
@@ -2356,25 +2416,29 @@ local void init_block()
2356 * two sons). 2416 * two sons).
2357 */ 2417 */
2358local void pqdownheap(tree, k) 2418local void pqdownheap(tree, k)
2359 ct_data near *tree; /* the tree to restore */ 2419ct_data near *tree; /* the tree to restore */
2360 int k; /* node to move down */ 2420int k; /* node to move down */
2361{ 2421{
2362 int v = heap[k]; 2422 int v = heap[k];
2363 int j = k << 1; /* left son of k */ 2423 int j = k << 1; /* left son of k */
2364 while (j <= heap_len) { 2424
2365 /* Set j to the smallest of the two sons: */ 2425 while (j <= heap_len) {
2366 if (j < heap_len && smaller(tree, heap[j+1], heap[j])) j++; 2426 /* Set j to the smallest of the two sons: */
2367 2427 if (j < heap_len && smaller(tree, heap[j + 1], heap[j]))
2368 /* Exit if v is smaller than both sons */ 2428 j++;
2369 if (smaller(tree, v, heap[j])) break; 2429
2370 2430 /* Exit if v is smaller than both sons */
2371 /* Exchange v with the smallest son */ 2431 if (smaller(tree, v, heap[j]))
2372 heap[k] = heap[j]; k = j; 2432 break;
2373 2433
2374 /* And continue down the tree, setting j to the left son of k */ 2434 /* Exchange v with the smallest son */
2375 j <<= 1; 2435 heap[k] = heap[j];
2376 } 2436 k = j;
2377 heap[k] = v; 2437
2438 /* And continue down the tree, setting j to the left son of k */
2439 j <<= 1;
2440 }
2441 heap[k] = v;
2378} 2442}
2379 2443
2380/* =========================================================================== 2444/* ===========================================================================
@@ -2388,80 +2452,93 @@ local void pqdownheap(tree, k)
2388 * not null. 2452 * not null.
2389 */ 2453 */
2390local void gen_bitlen(desc) 2454local void gen_bitlen(desc)
2391 tree_desc near *desc; /* the tree descriptor */ 2455tree_desc near *desc; /* the tree descriptor */
2392{ 2456{
2393 ct_data near *tree = desc->dyn_tree; 2457 ct_data near *tree = desc->dyn_tree;
2394 int near *extra = desc->extra_bits; 2458 int near *extra = desc->extra_bits;
2395 int base = desc->extra_base; 2459 int base = desc->extra_base;
2396 int max_code = desc->max_code; 2460 int max_code = desc->max_code;
2397 int max_length = desc->max_length; 2461 int max_length = desc->max_length;
2398 ct_data near *stree = desc->static_tree; 2462 ct_data near *stree = desc->static_tree;
2399 int h; /* heap index */ 2463 int h; /* heap index */
2400 int n, m; /* iterate over the tree elements */ 2464 int n, m; /* iterate over the tree elements */
2401 int bits; /* bit length */ 2465 int bits; /* bit length */
2402 int xbits; /* extra bits */ 2466 int xbits; /* extra bits */
2403 ush f; /* frequency */ 2467 ush f; /* frequency */
2404 int overflow = 0; /* number of elements with bit length too large */ 2468 int overflow = 0; /* number of elements with bit length too large */
2405 2469
2406 for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0; 2470 for (bits = 0; bits <= MAX_BITS; bits++)
2407 2471 bl_count[bits] = 0;
2408 /* In a first pass, compute the optimal bit lengths (which may 2472
2409 * overflow in the case of the bit length tree). 2473 /* In a first pass, compute the optimal bit lengths (which may
2410 */ 2474 * overflow in the case of the bit length tree).
2411 tree[heap[heap_max]].Len = 0; /* root of the heap */ 2475 */
2412 2476 tree[heap[heap_max]].Len = 0; /* root of the heap */
2413 for (h = heap_max+1; h < HEAP_SIZE; h++) { 2477
2414 n = heap[h]; 2478 for (h = heap_max + 1; h < HEAP_SIZE; h++) {
2415 bits = tree[tree[n].Dad].Len + 1; 2479 n = heap[h];
2416 if (bits > max_length) bits = max_length, overflow++; 2480 bits = tree[tree[n].Dad].Len + 1;
2417 tree[n].Len = (ush)bits; 2481 if (bits > max_length)
2418 /* We overwrite tree[n].Dad which is no longer needed */ 2482 bits = max_length, overflow++;
2419 2483 tree[n].Len = (ush) bits;
2420 if (n > max_code) continue; /* not a leaf node */ 2484 /* We overwrite tree[n].Dad which is no longer needed */
2421 2485
2422 bl_count[bits]++; 2486 if (n > max_code)
2423 xbits = 0; 2487 continue; /* not a leaf node */
2424 if (n >= base) xbits = extra[n-base]; 2488
2425 f = tree[n].Freq; 2489 bl_count[bits]++;
2426 opt_len += (ulg)f * (bits + xbits); 2490 xbits = 0;
2427 if (stree) static_len += (ulg)f * (stree[n].Len + xbits); 2491 if (n >= base)
2428 } 2492 xbits = extra[n - base];
2429 if (overflow == 0) return; 2493 f = tree[n].Freq;
2430 2494 opt_len += (ulg) f *(bits + xbits);
2431 Trace((stderr,"\nbit length overflow\n")); 2495
2432 /* This happens for example on obj2 and pic of the Calgary corpus */ 2496 if (stree)
2433 2497 static_len += (ulg) f *(stree[n].Len + xbits);
2434 /* Find the first bit length which could increase: */ 2498 }
2435 do { 2499 if (overflow == 0)
2436 bits = max_length-1; 2500 return;
2437 while (bl_count[bits] == 0) bits--; 2501
2438 bl_count[bits]--; /* move one leaf down the tree */ 2502 Trace((stderr, "\nbit length overflow\n"));
2439 bl_count[bits+1] += 2; /* move one overflow item as its brother */ 2503 /* This happens for example on obj2 and pic of the Calgary corpus */
2440 bl_count[max_length]--; 2504
2441 /* The brother of the overflow item also moves one step up, 2505 /* Find the first bit length which could increase: */
2442 * but this does not affect bl_count[max_length] 2506 do {
2443 */ 2507 bits = max_length - 1;
2444 overflow -= 2; 2508 while (bl_count[bits] == 0)
2445 } while (overflow > 0); 2509 bits--;
2446 2510 bl_count[bits]--; /* move one leaf down the tree */
2447 /* Now recompute all bit lengths, scanning in increasing frequency. 2511 bl_count[bits + 1] += 2; /* move one overflow item as its brother */
2448 * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all 2512 bl_count[max_length]--;
2449 * lengths instead of fixing only the wrong ones. This idea is taken 2513 /* The brother of the overflow item also moves one step up,
2450 * from 'ar' written by Haruhiko Okumura.) 2514 * but this does not affect bl_count[max_length]
2451 */ 2515 */
2452 for (bits = max_length; bits != 0; bits--) { 2516 overflow -= 2;
2453 n = bl_count[bits]; 2517 } while (overflow > 0);
2454 while (n != 0) { 2518
2455 m = heap[--h]; 2519 /* Now recompute all bit lengths, scanning in increasing frequency.
2456 if (m > max_code) continue; 2520 * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all
2457 if (tree[m].Len != (unsigned) bits) { 2521 * lengths instead of fixing only the wrong ones. This idea is taken
2458 Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits)); 2522 * from 'ar' written by Haruhiko Okumura.)
2459 opt_len += ((long)bits-(long)tree[m].Len)*(long)tree[m].Freq; 2523 */
2460 tree[m].Len = (ush)bits; 2524 for (bits = max_length; bits != 0; bits--) {
2461 } 2525 n = bl_count[bits];
2462 n--; 2526 while (n != 0) {
2463 } 2527 m = heap[--h];
2464 } 2528 if (m > max_code)
2529 continue;
2530 if (tree[m].Len != (unsigned) bits) {
2531 Trace(
2532 (stderr, "code %d bits %d->%d\n", m, tree[m].Len,
2533 bits));
2534 opt_len +=
2535 ((long) bits -
2536 (long) tree[m].Len) * (long) tree[m].Freq;
2537 tree[m].Len = (ush) bits;
2538 }
2539 n--;
2540 }
2541 }
2465} 2542}
2466 2543
2467/* =========================================================================== 2544/* ===========================================================================
@@ -2472,37 +2549,41 @@ local void gen_bitlen(desc)
2472 * OUT assertion: the field code is set for all tree elements of non 2549 * OUT assertion: the field code is set for all tree elements of non
2473 * zero code length. 2550 * zero code length.
2474 */ 2551 */
2475local void gen_codes (tree, max_code) 2552local void gen_codes(tree, max_code)
2476 ct_data near *tree; /* the tree to decorate */ 2553ct_data near *tree; /* the tree to decorate */
2477 int max_code; /* largest code with non zero frequency */ 2554int max_code; /* largest code with non zero frequency */
2478{ 2555{
2479 ush next_code[MAX_BITS+1]; /* next code value for each bit length */ 2556 ush next_code[MAX_BITS + 1]; /* next code value for each bit length */
2480 ush code = 0; /* running code value */ 2557 ush code = 0; /* running code value */
2481 int bits; /* bit index */ 2558 int bits; /* bit index */
2482 int n; /* code index */ 2559 int n; /* code index */
2483 2560
2484 /* The distribution counts are first used to generate the code values 2561 /* The distribution counts are first used to generate the code values
2485 * without bit reversal. 2562 * without bit reversal.
2486 */ 2563 */
2487 for (bits = 1; bits <= MAX_BITS; bits++) { 2564 for (bits = 1; bits <= MAX_BITS; bits++) {
2488 next_code[bits] = code = (code + bl_count[bits-1]) << 1; 2565 next_code[bits] = code = (code + bl_count[bits - 1]) << 1;
2489 } 2566 }
2490 /* Check that the bit counts in bl_count are consistent. The last code 2567 /* Check that the bit counts in bl_count are consistent. The last code
2491 * must be all ones. 2568 * must be all ones.
2492 */ 2569 */
2493 Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1, 2570 Assert(code + bl_count[MAX_BITS] - 1 == (1 << MAX_BITS) - 1,
2494 "inconsistent bit counts"); 2571 "inconsistent bit counts");
2495 Tracev((stderr,"\ngen_codes: max_code %d ", max_code)); 2572 Tracev((stderr, "\ngen_codes: max_code %d ", max_code));
2496 2573
2497 for (n = 0; n <= max_code; n++) { 2574 for (n = 0; n <= max_code; n++) {
2498 int len = tree[n].Len; 2575 int len = tree[n].Len;
2499 if (len == 0) continue; 2576
2500 /* Now reverse the bits */ 2577 if (len == 0)
2501 tree[n].Code = bi_reverse(next_code[len]++, len); 2578 continue;
2502 2579 /* Now reverse the bits */
2503 Tracec(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ", 2580 tree[n].Code = bi_reverse(next_code[len]++, len);
2504 n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1)); 2581
2505 } 2582 Tracec(tree != static_ltree,
2583 (stderr, "\nn %3d %c l %2d c %4x (%x) ", n,
2584 (isgraph(n) ? n : ' '), len, tree[n].Code,
2585 next_code[len] - 1));
2586 }
2506} 2587}
2507 2588
2508/* =========================================================================== 2589/* ===========================================================================
@@ -2514,84 +2595,89 @@ local void gen_codes (tree, max_code)
2514 * also updated if stree is not null. The field max_code is set. 2595 * also updated if stree is not null. The field max_code is set.
2515 */ 2596 */
2516local void build_tree(desc) 2597local void build_tree(desc)
2517 tree_desc near *desc; /* the tree descriptor */ 2598tree_desc near *desc; /* the tree descriptor */
2518{ 2599{
2519 ct_data near *tree = desc->dyn_tree; 2600 ct_data near *tree = desc->dyn_tree;
2520 ct_data near *stree = desc->static_tree; 2601 ct_data near *stree = desc->static_tree;
2521 int elems = desc->elems; 2602 int elems = desc->elems;
2522 int n, m; /* iterate over heap elements */ 2603 int n, m; /* iterate over heap elements */
2523 int max_code = -1; /* largest code with non zero frequency */ 2604 int max_code = -1; /* largest code with non zero frequency */
2524 int node = elems; /* next internal node of the tree */ 2605 int node = elems; /* next internal node of the tree */
2525 2606
2526 /* Construct the initial heap, with least frequent element in 2607 /* Construct the initial heap, with least frequent element in
2527 * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1]. 2608 * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
2528 * heap[0] is not used. 2609 * heap[0] is not used.
2529 */ 2610 */
2530 heap_len = 0, heap_max = HEAP_SIZE; 2611 heap_len = 0, heap_max = HEAP_SIZE;
2531 2612
2532 for (n = 0; n < elems; n++) { 2613 for (n = 0; n < elems; n++) {
2533 if (tree[n].Freq != 0) { 2614 if (tree[n].Freq != 0) {
2534 heap[++heap_len] = max_code = n; 2615 heap[++heap_len] = max_code = n;
2535 depth[n] = 0; 2616 depth[n] = 0;
2536 } else { 2617 } else {
2537 tree[n].Len = 0; 2618 tree[n].Len = 0;
2538 } 2619 }
2539 } 2620 }
2540 2621
2541 /* The pkzip format requires that at least one distance code exists, 2622 /* The pkzip format requires that at least one distance code exists,
2542 * and that at least one bit should be sent even if there is only one 2623 * and that at least one bit should be sent even if there is only one
2543 * possible code. So to avoid special checks later on we force at least 2624 * possible code. So to avoid special checks later on we force at least
2544 * two codes of non zero frequency. 2625 * two codes of non zero frequency.
2545 */ 2626 */
2546 while (heap_len < 2) { 2627 while (heap_len < 2) {
2547 int new = heap[++heap_len] = (max_code < 2 ? ++max_code : 0); 2628 int new = heap[++heap_len] = (max_code < 2 ? ++max_code : 0);
2548 tree[new].Freq = 1; 2629
2549 depth[new] = 0; 2630 tree[new].Freq = 1;
2550 opt_len--; if (stree) static_len -= stree[new].Len; 2631 depth[new] = 0;
2551 /* new is 0 or 1 so it does not have extra bits */ 2632 opt_len--;
2552 } 2633 if (stree)
2553 desc->max_code = max_code; 2634 static_len -= stree[new].Len;
2554 2635 /* new is 0 or 1 so it does not have extra bits */
2555 /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree, 2636 }
2556 * establish sub-heaps of increasing lengths: 2637 desc->max_code = max_code;
2557 */ 2638
2558 for (n = heap_len/2; n >= 1; n--) pqdownheap(tree, n); 2639 /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
2559 2640 * establish sub-heaps of increasing lengths:
2560 /* Construct the Huffman tree by repeatedly combining the least two 2641 */
2561 * frequent nodes. 2642 for (n = heap_len / 2; n >= 1; n--)
2562 */ 2643 pqdownheap(tree, n);
2563 do { 2644
2564 pqremove(tree, n); /* n = node of least frequency */ 2645 /* Construct the Huffman tree by repeatedly combining the least two
2565 m = heap[SMALLEST]; /* m = node of next least frequency */ 2646 * frequent nodes.
2566 2647 */
2567 heap[--heap_max] = n; /* keep the nodes sorted by frequency */ 2648 do {
2568 heap[--heap_max] = m; 2649 pqremove(tree, n); /* n = node of least frequency */
2569 2650 m = heap[SMALLEST]; /* m = node of next least frequency */
2570 /* Create a new node father of n and m */ 2651
2571 tree[node].Freq = tree[n].Freq + tree[m].Freq; 2652 heap[--heap_max] = n; /* keep the nodes sorted by frequency */
2572 depth[node] = (uch) (MAX(depth[n], depth[m]) + 1); 2653 heap[--heap_max] = m;
2573 tree[n].Dad = tree[m].Dad = (ush)node; 2654
2655 /* Create a new node father of n and m */
2656 tree[node].Freq = tree[n].Freq + tree[m].Freq;
2657 depth[node] = (uch) (MAX(depth[n], depth[m]) + 1);
2658 tree[n].Dad = tree[m].Dad = (ush) node;
2574#ifdef DUMP_BL_TREE 2659#ifdef DUMP_BL_TREE
2575 if (tree == bl_tree) { 2660 if (tree == bl_tree) {
2576 fprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)", 2661 fprintf(stderr, "\nnode %d(%d), sons %d(%d) %d(%d)",
2577 node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq); 2662 node, tree[node].Freq, n, tree[n].Freq, m,
2578 } 2663 tree[m].Freq);
2664 }
2579#endif 2665#endif
2580 /* and insert the new node in the heap */ 2666 /* and insert the new node in the heap */
2581 heap[SMALLEST] = node++; 2667 heap[SMALLEST] = node++;
2582 pqdownheap(tree, SMALLEST); 2668 pqdownheap(tree, SMALLEST);
2583 2669
2584 } while (heap_len >= 2); 2670 } while (heap_len >= 2);
2585 2671
2586 heap[--heap_max] = heap[SMALLEST]; 2672 heap[--heap_max] = heap[SMALLEST];
2587 2673
2588 /* At this point, the fields freq and dad are set. We can now 2674 /* At this point, the fields freq and dad are set. We can now
2589 * generate the bit lengths. 2675 * generate the bit lengths.
2590 */ 2676 */
2591 gen_bitlen((tree_desc near *)desc); 2677 gen_bitlen((tree_desc near *) desc);
2592 2678
2593 /* The field len is now set, we can generate the bit codes */ 2679 /* The field len is now set, we can generate the bit codes */
2594 gen_codes ((ct_data near *)tree, max_code); 2680 gen_codes((ct_data near *) tree, max_code);
2595} 2681}
2596 2682
2597/* =========================================================================== 2683/* ===========================================================================
@@ -2600,94 +2686,107 @@ local void build_tree(desc)
2600 * counts. (The contribution of the bit length codes will be added later 2686 * counts. (The contribution of the bit length codes will be added later
2601 * during the construction of bl_tree.) 2687 * during the construction of bl_tree.)
2602 */ 2688 */
2603local void scan_tree (tree, max_code) 2689local void scan_tree(tree, max_code)
2604 ct_data near *tree; /* the tree to be scanned */ 2690ct_data near *tree; /* the tree to be scanned */
2605 int max_code; /* and its largest code of non zero frequency */ 2691int max_code; /* and its largest code of non zero frequency */
2606{ 2692{
2607 int n; /* iterates over all tree elements */ 2693 int n; /* iterates over all tree elements */
2608 int prevlen = -1; /* last emitted length */ 2694 int prevlen = -1; /* last emitted length */
2609 int curlen; /* length of current code */ 2695 int curlen; /* length of current code */
2610 int nextlen = tree[0].Len; /* length of next code */ 2696 int nextlen = tree[0].Len; /* length of next code */
2611 int count = 0; /* repeat count of the current code */ 2697 int count = 0; /* repeat count of the current code */
2612 int max_count = 7; /* max repeat count */ 2698 int max_count = 7; /* max repeat count */
2613 int min_count = 4; /* min repeat count */ 2699 int min_count = 4; /* min repeat count */
2614 2700
2615 if (nextlen == 0) max_count = 138, min_count = 3; 2701 if (nextlen == 0)
2616 tree[max_code+1].Len = (ush)0xffff; /* guard */ 2702 max_count = 138, min_count = 3;
2617 2703 tree[max_code + 1].Len = (ush) 0xffff; /* guard */
2618 for (n = 0; n <= max_code; n++) { 2704
2619 curlen = nextlen; nextlen = tree[n+1].Len; 2705 for (n = 0; n <= max_code; n++) {
2620 if (++count < max_count && curlen == nextlen) { 2706 curlen = nextlen;
2621 continue; 2707 nextlen = tree[n + 1].Len;
2622 } else if (count < min_count) { 2708 if (++count < max_count && curlen == nextlen) {
2623 bl_tree[curlen].Freq += count; 2709 continue;
2624 } else if (curlen != 0) { 2710 } else if (count < min_count) {
2625 if (curlen != prevlen) bl_tree[curlen].Freq++; 2711 bl_tree[curlen].Freq += count;
2626 bl_tree[REP_3_6].Freq++; 2712 } else if (curlen != 0) {
2627 } else if (count <= 10) { 2713 if (curlen != prevlen)
2628 bl_tree[REPZ_3_10].Freq++; 2714 bl_tree[curlen].Freq++;
2629 } else { 2715 bl_tree[REP_3_6].Freq++;
2630 bl_tree[REPZ_11_138].Freq++; 2716 } else if (count <= 10) {
2631 } 2717 bl_tree[REPZ_3_10].Freq++;
2632 count = 0; prevlen = curlen; 2718 } else {
2633 if (nextlen == 0) { 2719 bl_tree[REPZ_11_138].Freq++;
2634 max_count = 138, min_count = 3; 2720 }
2635 } else if (curlen == nextlen) { 2721 count = 0;
2636 max_count = 6, min_count = 3; 2722 prevlen = curlen;
2637 } else { 2723 if (nextlen == 0) {
2638 max_count = 7, min_count = 4; 2724 max_count = 138, min_count = 3;
2639 } 2725 } else if (curlen == nextlen) {
2640 } 2726 max_count = 6, min_count = 3;
2727 } else {
2728 max_count = 7, min_count = 4;
2729 }
2730 }
2641} 2731}
2642 2732
2643/* =========================================================================== 2733/* ===========================================================================
2644 * Send a literal or distance tree in compressed form, using the codes in 2734 * Send a literal or distance tree in compressed form, using the codes in
2645 * bl_tree. 2735 * bl_tree.
2646 */ 2736 */
2647local void send_tree (tree, max_code) 2737local void send_tree(tree, max_code)
2648 ct_data near *tree; /* the tree to be scanned */ 2738ct_data near *tree; /* the tree to be scanned */
2649 int max_code; /* and its largest code of non zero frequency */ 2739int max_code; /* and its largest code of non zero frequency */
2650{ 2740{
2651 int n; /* iterates over all tree elements */ 2741 int n; /* iterates over all tree elements */
2652 int prevlen = -1; /* last emitted length */ 2742 int prevlen = -1; /* last emitted length */
2653 int curlen; /* length of current code */ 2743 int curlen; /* length of current code */
2654 int nextlen = tree[0].Len; /* length of next code */ 2744 int nextlen = tree[0].Len; /* length of next code */
2655 int count = 0; /* repeat count of the current code */ 2745 int count = 0; /* repeat count of the current code */
2656 int max_count = 7; /* max repeat count */ 2746 int max_count = 7; /* max repeat count */
2657 int min_count = 4; /* min repeat count */ 2747 int min_count = 4; /* min repeat count */
2658 2748
2659 /* tree[max_code+1].Len = -1; */ /* guard already set */ 2749/* tree[max_code+1].Len = -1; *//* guard already set */
2660 if (nextlen == 0) max_count = 138, min_count = 3; 2750 if (nextlen == 0)
2661 2751 max_count = 138, min_count = 3;
2662 for (n = 0; n <= max_code; n++) { 2752
2663 curlen = nextlen; nextlen = tree[n+1].Len; 2753 for (n = 0; n <= max_code; n++) {
2664 if (++count < max_count && curlen == nextlen) { 2754 curlen = nextlen;
2665 continue; 2755 nextlen = tree[n + 1].Len;
2666 } else if (count < min_count) { 2756 if (++count < max_count && curlen == nextlen) {
2667 do { send_code(curlen, bl_tree); } while (--count != 0); 2757 continue;
2668 2758 } else if (count < min_count) {
2669 } else if (curlen != 0) { 2759 do {
2670 if (curlen != prevlen) { 2760 send_code(curlen, bl_tree);
2671 send_code(curlen, bl_tree); count--; 2761 } while (--count != 0);
2672 } 2762
2673 Assert(count >= 3 && count <= 6, " 3_6?"); 2763 } else if (curlen != 0) {
2674 send_code(REP_3_6, bl_tree); send_bits(count-3, 2); 2764 if (curlen != prevlen) {
2675 2765 send_code(curlen, bl_tree);
2676 } else if (count <= 10) { 2766 count--;
2677 send_code(REPZ_3_10, bl_tree); send_bits(count-3, 3); 2767 }
2678 2768 Assert(count >= 3 && count <= 6, " 3_6?");
2679 } else { 2769 send_code(REP_3_6, bl_tree);
2680 send_code(REPZ_11_138, bl_tree); send_bits(count-11, 7); 2770 send_bits(count - 3, 2);
2681 } 2771
2682 count = 0; prevlen = curlen; 2772 } else if (count <= 10) {
2683 if (nextlen == 0) { 2773 send_code(REPZ_3_10, bl_tree);
2684 max_count = 138, min_count = 3; 2774 send_bits(count - 3, 3);
2685 } else if (curlen == nextlen) { 2775
2686 max_count = 6, min_count = 3; 2776 } else {
2687 } else { 2777 send_code(REPZ_11_138, bl_tree);
2688 max_count = 7, min_count = 4; 2778 send_bits(count - 11, 7);
2689 } 2779 }
2690 } 2780 count = 0;
2781 prevlen = curlen;
2782 if (nextlen == 0) {
2783 max_count = 138, min_count = 3;
2784 } else if (curlen == nextlen) {
2785 max_count = 6, min_count = 3;
2786 } else {
2787 max_count = 7, min_count = 4;
2788 }
2789 }
2691} 2790}
2692 2791
2693/* =========================================================================== 2792/* ===========================================================================
@@ -2696,30 +2795,33 @@ local void send_tree (tree, max_code)
2696 */ 2795 */
2697local int build_bl_tree() 2796local int build_bl_tree()
2698{ 2797{
2699 int max_blindex; /* index of last bit length code of non zero freq */ 2798 int max_blindex; /* index of last bit length code of non zero freq */
2700 2799
2701 /* Determine the bit length frequencies for literal and distance trees */ 2800 /* Determine the bit length frequencies for literal and distance trees */
2702 scan_tree((ct_data near *)dyn_ltree, l_desc.max_code); 2801 scan_tree((ct_data near *) dyn_ltree, l_desc.max_code);
2703 scan_tree((ct_data near *)dyn_dtree, d_desc.max_code); 2802 scan_tree((ct_data near *) dyn_dtree, d_desc.max_code);
2704 2803
2705 /* Build the bit length tree: */ 2804 /* Build the bit length tree: */
2706 build_tree((tree_desc near *)(&bl_desc)); 2805 build_tree((tree_desc near *) (&bl_desc));
2707 /* opt_len now includes the length of the tree representations, except 2806 /* opt_len now includes the length of the tree representations, except
2708 * the lengths of the bit lengths codes and the 5+5+4 bits for the counts. 2807 * the lengths of the bit lengths codes and the 5+5+4 bits for the counts.
2709 */ 2808 */
2710 2809
2711 /* Determine the number of bit length codes to send. The pkzip format 2810 /* Determine the number of bit length codes to send. The pkzip format
2712 * requires that at least 4 bit length codes be sent. (appnote.txt says 2811 * requires that at least 4 bit length codes be sent. (appnote.txt says
2713 * 3 but the actual value used is 4.) 2812 * 3 but the actual value used is 4.)
2714 */ 2813 */
2715 for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) { 2814 for (max_blindex = BL_CODES - 1; max_blindex >= 3; max_blindex--) {
2716 if (bl_tree[bl_order[max_blindex]].Len != 0) break; 2815 if (bl_tree[bl_order[max_blindex]].Len != 0)
2717 } 2816 break;
2718 /* Update opt_len to include the bit length tree and counts */ 2817 }
2719 opt_len += 3*(max_blindex+1) + 5+5+4; 2818 /* Update opt_len to include the bit length tree and counts */
2720 Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", opt_len, static_len)); 2819 opt_len += 3 * (max_blindex + 1) + 5 + 5 + 4;
2721 2820 Tracev(
2722 return max_blindex; 2821 (stderr, "\ndyn trees: dyn %ld, stat %ld", opt_len,
2822 static_len));
2823
2824 return max_blindex;
2723} 2825}
2724 2826
2725/* =========================================================================== 2827/* ===========================================================================
@@ -2728,28 +2830,29 @@ local int build_bl_tree()
2728 * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4. 2830 * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.
2729 */ 2831 */
2730local void send_all_trees(lcodes, dcodes, blcodes) 2832local void send_all_trees(lcodes, dcodes, blcodes)
2731 int lcodes, dcodes, blcodes; /* number of codes for each tree */ 2833int lcodes, dcodes, blcodes; /* number of codes for each tree */
2732{ 2834{
2733 int rank; /* index in bl_order */ 2835 int rank; /* index in bl_order */
2734 2836
2735 Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes"); 2837 Assert(lcodes >= 257 && dcodes >= 1
2736 Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES, 2838 && blcodes >= 4, "not enough codes");
2737 "too many codes"); 2839 Assert(lcodes <= L_CODES && dcodes <= D_CODES
2738 Tracev((stderr, "\nbl counts: ")); 2840 && blcodes <= BL_CODES, "too many codes");
2739 send_bits(lcodes-257, 5); /* not +255 as stated in appnote.txt */ 2841 Tracev((stderr, "\nbl counts: "));
2740 send_bits(dcodes-1, 5); 2842 send_bits(lcodes - 257, 5); /* not +255 as stated in appnote.txt */
2741 send_bits(blcodes-4, 4); /* not -3 as stated in appnote.txt */ 2843 send_bits(dcodes - 1, 5);
2742 for (rank = 0; rank < blcodes; rank++) { 2844 send_bits(blcodes - 4, 4); /* not -3 as stated in appnote.txt */
2743 Tracev((stderr, "\nbl code %2d ", bl_order[rank])); 2845 for (rank = 0; rank < blcodes; rank++) {
2744 send_bits(bl_tree[bl_order[rank]].Len, 3); 2846 Tracev((stderr, "\nbl code %2d ", bl_order[rank]));
2745 } 2847 send_bits(bl_tree[bl_order[rank]].Len, 3);
2746 Tracev((stderr, "\nbl tree: sent %ld", bits_sent)); 2848 }
2747 2849 Tracev((stderr, "\nbl tree: sent %ld", bits_sent));
2748 send_tree((ct_data near *)dyn_ltree, lcodes-1); /* send the literal tree */ 2850
2749 Tracev((stderr, "\nlit tree: sent %ld", bits_sent)); 2851 send_tree((ct_data near *) dyn_ltree, lcodes - 1); /* send the literal tree */
2750 2852 Tracev((stderr, "\nlit tree: sent %ld", bits_sent));
2751 send_tree((ct_data near *)dyn_dtree, dcodes-1); /* send the distance tree */ 2853
2752 Tracev((stderr, "\ndist tree: sent %ld", bits_sent)); 2854 send_tree((ct_data near *) dyn_dtree, dcodes - 1); /* send the distance tree */
2855 Tracev((stderr, "\ndist tree: sent %ld", bits_sent));
2753} 2856}
2754 2857
2755/* =========================================================================== 2858/* ===========================================================================
@@ -2758,204 +2861,222 @@ local void send_all_trees(lcodes, dcodes, blcodes)
2758 * returns the total compressed length for the file so far. 2861 * returns the total compressed length for the file so far.
2759 */ 2862 */
2760ulg flush_block(buf, stored_len, eof) 2863ulg flush_block(buf, stored_len, eof)
2761 char *buf; /* input block, or NULL if too old */ 2864char *buf; /* input block, or NULL if too old */
2762 ulg stored_len; /* length of input block */ 2865ulg stored_len; /* length of input block */
2763 int eof; /* true if this is the last block for a file */ 2866int eof; /* true if this is the last block for a file */
2764{ 2867{
2765 ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */ 2868 ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */
2766 int max_blindex; /* index of last bit length code of non zero freq */ 2869 int max_blindex; /* index of last bit length code of non zero freq */
2767 2870
2768 flag_buf[last_flags] = flags; /* Save the flags for the last 8 items */ 2871 flag_buf[last_flags] = flags; /* Save the flags for the last 8 items */
2769 2872
2770 /* Check if the file is ascii or binary */ 2873 /* Check if the file is ascii or binary */
2771 if (*file_type == (ush)UNKNOWN) set_file_type(); 2874 if (*file_type == (ush) UNKNOWN)
2772 2875 set_file_type();
2773 /* Construct the literal and distance trees */ 2876
2774 build_tree((tree_desc near *)(&l_desc)); 2877 /* Construct the literal and distance trees */
2775 Tracev((stderr, "\nlit data: dyn %ld, stat %ld", opt_len, static_len)); 2878 build_tree((tree_desc near *) (&l_desc));
2776 2879 Tracev((stderr, "\nlit data: dyn %ld, stat %ld", opt_len, static_len));
2777 build_tree((tree_desc near *)(&d_desc)); 2880
2778 Tracev((stderr, "\ndist data: dyn %ld, stat %ld", opt_len, static_len)); 2881 build_tree((tree_desc near *) (&d_desc));
2779 /* At this point, opt_len and static_len are the total bit lengths of 2882 Tracev(
2780 * the compressed block data, excluding the tree representations. 2883 (stderr, "\ndist data: dyn %ld, stat %ld", opt_len,
2781 */ 2884 static_len));
2782 2885 /* At this point, opt_len and static_len are the total bit lengths of
2783 /* Build the bit length tree for the above two trees, and get the index 2886 * the compressed block data, excluding the tree representations.
2784 * in bl_order of the last bit length code to send. 2887 */
2785 */ 2888
2786 max_blindex = build_bl_tree(); 2889 /* Build the bit length tree for the above two trees, and get the index
2787 2890 * in bl_order of the last bit length code to send.
2788 /* Determine the best encoding. Compute first the block length in bytes */ 2891 */
2789 opt_lenb = (opt_len+3+7)>>3; 2892 max_blindex = build_bl_tree();
2790 static_lenb = (static_len+3+7)>>3; 2893
2791 input_len += stored_len; /* for debugging only */ 2894 /* Determine the best encoding. Compute first the block length in bytes */
2792 2895 opt_lenb = (opt_len + 3 + 7) >> 3;
2793 Trace((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u dist %u ", 2896 static_lenb = (static_len + 3 + 7) >> 3;
2794 opt_lenb, opt_len, static_lenb, static_len, stored_len, 2897 input_len += stored_len; /* for debugging only */
2795 last_lit, last_dist)); 2898
2796 2899 Trace(
2797 if (static_lenb <= opt_lenb) opt_lenb = static_lenb; 2900 (stderr,
2798 2901 "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u dist %u ",
2799 /* If compression failed and this is the first and last block, 2902 opt_lenb, opt_len, static_lenb, static_len, stored_len,
2800 * and if the zip file can be seeked (to rewrite the local header), 2903 last_lit, last_dist));
2801 * the whole file is transformed into a stored file: 2904
2802 */ 2905 if (static_lenb <= opt_lenb)
2906 opt_lenb = static_lenb;
2907
2908 /* If compression failed and this is the first and last block,
2909 * and if the zip file can be seeked (to rewrite the local header),
2910 * the whole file is transformed into a stored file:
2911 */
2803#ifdef FORCE_METHOD 2912#ifdef FORCE_METHOD
2804#else 2913#else
2805 if (stored_len <= opt_lenb && eof && compressed_len == 0L && seekable()) { 2914 if (stored_len <= opt_lenb && eof && compressed_len == 0L
2915 && seekable()) {
2806#endif 2916#endif
2807 /* Since LIT_BUFSIZE <= 2*WSIZE, the input data must be there: */ 2917 /* Since LIT_BUFSIZE <= 2*WSIZE, the input data must be there: */
2808 if (buf == (char*)0) error ("block vanished"); 2918 if (buf == (char *) 0)
2919 error("block vanished");
2809 2920
2810 copy_block(buf, (unsigned)stored_len, 0); /* without header */ 2921 copy_block(buf, (unsigned) stored_len, 0); /* without header */
2811 compressed_len = stored_len << 3; 2922 compressed_len = stored_len << 3;
2812 *file_method = STORED; 2923 *file_method = STORED;
2813 2924
2814#ifdef FORCE_METHOD 2925#ifdef FORCE_METHOD
2815#else 2926#else
2816 } else if (stored_len+4 <= opt_lenb && buf != (char*)0) { 2927 } else if (stored_len + 4 <= opt_lenb && buf != (char *) 0) {
2817 /* 4: two words for the lengths */ 2928 /* 4: two words for the lengths */
2818#endif 2929#endif
2819 /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE. 2930 /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE.
2820 * Otherwise we can't have processed more than WSIZE input bytes since 2931 * Otherwise we can't have processed more than WSIZE input bytes since
2821 * the last block flush, because compression would have been 2932 * the last block flush, because compression would have been
2822 * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to 2933 * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to
2823 * transform a block into a stored block. 2934 * transform a block into a stored block.
2824 */ 2935 */
2825 send_bits((STORED_BLOCK<<1)+eof, 3); /* send block type */ 2936 send_bits((STORED_BLOCK << 1) + eof, 3); /* send block type */
2826 compressed_len = (compressed_len + 3 + 7) & ~7L; 2937 compressed_len = (compressed_len + 3 + 7) & ~7L;
2827 compressed_len += (stored_len + 4) << 3; 2938 compressed_len += (stored_len + 4) << 3;
2828 2939
2829 copy_block(buf, (unsigned)stored_len, 1); /* with header */ 2940 copy_block(buf, (unsigned) stored_len, 1); /* with header */
2830 2941
2831#ifdef FORCE_METHOD 2942#ifdef FORCE_METHOD
2832#else 2943#else
2833 } else if (static_lenb == opt_lenb) { 2944 } else if (static_lenb == opt_lenb) {
2834#endif 2945#endif
2835 send_bits((STATIC_TREES<<1)+eof, 3); 2946 send_bits((STATIC_TREES << 1) + eof, 3);
2836 compress_block((ct_data near *)static_ltree, (ct_data near *)static_dtree); 2947 compress_block((ct_data near *) static_ltree,
2837 compressed_len += 3 + static_len; 2948 (ct_data near *) static_dtree);
2838 } else { 2949 compressed_len += 3 + static_len;
2839 send_bits((DYN_TREES<<1)+eof, 3); 2950 } else {
2840 send_all_trees(l_desc.max_code+1, d_desc.max_code+1, max_blindex+1); 2951 send_bits((DYN_TREES << 1) + eof, 3);
2841 compress_block((ct_data near *)dyn_ltree, (ct_data near *)dyn_dtree); 2952 send_all_trees(l_desc.max_code + 1, d_desc.max_code + 1,
2842 compressed_len += 3 + opt_len; 2953 max_blindex + 1);
2843 } 2954 compress_block((ct_data near *) dyn_ltree,
2844 Assert (compressed_len == bits_sent, "bad compressed size"); 2955 (ct_data near *) dyn_dtree);
2845 init_block(); 2956 compressed_len += 3 + opt_len;
2846 2957 }
2847 if (eof) { 2958 Assert(compressed_len == bits_sent, "bad compressed size");
2848 Assert (input_len == isize, "bad input size"); 2959 init_block();
2849 bi_windup(); 2960
2850 compressed_len += 7; /* align on byte boundary */ 2961 if (eof) {
2851 } 2962 Assert(input_len == isize, "bad input size");
2852 Tracev((stderr,"\ncomprlen %lu(%lu) ", compressed_len>>3, 2963 bi_windup();
2853 compressed_len-7*eof)); 2964 compressed_len += 7; /* align on byte boundary */
2854 2965 }
2855 return compressed_len >> 3; 2966 Tracev((stderr, "\ncomprlen %lu(%lu) ", compressed_len >> 3,
2967 compressed_len - 7 * eof));
2968
2969 return compressed_len >> 3;
2856} 2970}
2857 2971
2858/* =========================================================================== 2972/* ===========================================================================
2859 * Save the match info and tally the frequency counts. Return true if 2973 * Save the match info and tally the frequency counts. Return true if
2860 * the current block must be flushed. 2974 * the current block must be flushed.
2861 */ 2975 */
2862int ct_tally (dist, lc) 2976int ct_tally(dist, lc)
2863 int dist; /* distance of matched string */ 2977int dist; /* distance of matched string */
2864 int lc; /* match length-MIN_MATCH or unmatched char (if dist==0) */ 2978int lc; /* match length-MIN_MATCH or unmatched char (if dist==0) */
2865{ 2979{
2866 l_buf[last_lit++] = (uch)lc; 2980 l_buf[last_lit++] = (uch) lc;
2867 if (dist == 0) { 2981 if (dist == 0) {
2868 /* lc is the unmatched char */ 2982 /* lc is the unmatched char */
2869 dyn_ltree[lc].Freq++; 2983 dyn_ltree[lc].Freq++;
2870 } else { 2984 } else {
2871 /* Here, lc is the match length - MIN_MATCH */ 2985 /* Here, lc is the match length - MIN_MATCH */
2872 dist--; /* dist = match distance - 1 */ 2986 dist--; /* dist = match distance - 1 */
2873 Assert((ush)dist < (ush)MAX_DIST && 2987 Assert((ush) dist < (ush) MAX_DIST &&
2874 (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) && 2988 (ush) lc <= (ush) (MAX_MATCH - MIN_MATCH) &&
2875 (ush)d_code(dist) < (ush)D_CODES, "ct_tally: bad match"); 2989 (ush) d_code(dist) < (ush) D_CODES, "ct_tally: bad match");
2876 2990
2877 dyn_ltree[length_code[lc]+LITERALS+1].Freq++; 2991 dyn_ltree[length_code[lc] + LITERALS + 1].Freq++;
2878 dyn_dtree[d_code(dist)].Freq++; 2992 dyn_dtree[d_code(dist)].Freq++;
2879 2993
2880 d_buf[last_dist++] = (ush)dist; 2994 d_buf[last_dist++] = (ush) dist;
2881 flags |= flag_bit; 2995 flags |= flag_bit;
2882 } 2996 }
2883 flag_bit <<= 1; 2997 flag_bit <<= 1;
2884 2998
2885 /* Output the flags if they fill a byte: */ 2999 /* Output the flags if they fill a byte: */
2886 if ((last_lit & 7) == 0) { 3000 if ((last_lit & 7) == 0) {
2887 flag_buf[last_flags++] = flags; 3001 flag_buf[last_flags++] = flags;
2888 flags = 0, flag_bit = 1; 3002 flags = 0, flag_bit = 1;
2889 } 3003 }
2890 /* Try to guess if it is profitable to stop the current block here */ 3004 /* Try to guess if it is profitable to stop the current block here */
2891 if ((last_lit & 0xfff) == 0) { 3005 if ((last_lit & 0xfff) == 0) {
2892 /* Compute an upper bound for the compressed length */ 3006 /* Compute an upper bound for the compressed length */
2893 ulg out_length = (ulg)last_lit*8L; 3007 ulg out_length = (ulg) last_lit * 8L;
2894 ulg in_length = (ulg)strstart-block_start; 3008 ulg in_length = (ulg) strstart - block_start;
2895 int dcode; 3009 int dcode;
2896 for (dcode = 0; dcode < D_CODES; dcode++) { 3010
2897 out_length += (ulg)dyn_dtree[dcode].Freq*(5L+extra_dbits[dcode]); 3011 for (dcode = 0; dcode < D_CODES; dcode++) {
2898 } 3012 out_length +=
2899 out_length >>= 3; 3013 (ulg) dyn_dtree[dcode].Freq * (5L + extra_dbits[dcode]);
2900 Trace((stderr,"\nlast_lit %u, last_dist %u, in %ld, out ~%ld(%ld%%) ", 3014 }
2901 last_lit, last_dist, in_length, out_length, 3015 out_length >>= 3;
2902 100L - out_length*100L/in_length)); 3016 Trace(
2903 if (last_dist < last_lit/2 && out_length < in_length/2) return 1; 3017 (stderr,
2904 } 3018 "\nlast_lit %u, last_dist %u, in %ld, out ~%ld(%ld%%) ",
2905 return (last_lit == LIT_BUFSIZE-1 || last_dist == DIST_BUFSIZE); 3019 last_lit, last_dist, in_length, out_length,
2906 /* We avoid equality with LIT_BUFSIZE because of wraparound at 64K 3020 100L - out_length * 100L / in_length));
2907 * on 16 bit machines and because stored blocks are restricted to 3021 if (last_dist < last_lit / 2 && out_length < in_length / 2)
2908 * 64K-1 bytes. 3022 return 1;
2909 */ 3023 }
3024 return (last_lit == LIT_BUFSIZE - 1 || last_dist == DIST_BUFSIZE);
3025 /* We avoid equality with LIT_BUFSIZE because of wraparound at 64K
3026 * on 16 bit machines and because stored blocks are restricted to
3027 * 64K-1 bytes.
3028 */
2910} 3029}
2911 3030
2912/* =========================================================================== 3031/* ===========================================================================
2913 * Send the block data compressed using the given Huffman trees 3032 * Send the block data compressed using the given Huffman trees
2914 */ 3033 */
2915local void compress_block(ltree, dtree) 3034local void compress_block(ltree, dtree)
2916 ct_data near *ltree; /* literal tree */ 3035ct_data near *ltree; /* literal tree */
2917 ct_data near *dtree; /* distance tree */ 3036ct_data near *dtree; /* distance tree */
2918{ 3037{
2919 unsigned dist; /* distance of matched string */ 3038 unsigned dist; /* distance of matched string */
2920 int lc; /* match length or unmatched char (if dist == 0) */ 3039 int lc; /* match length or unmatched char (if dist == 0) */
2921 unsigned lx = 0; /* running index in l_buf */ 3040 unsigned lx = 0; /* running index in l_buf */
2922 unsigned dx = 0; /* running index in d_buf */ 3041 unsigned dx = 0; /* running index in d_buf */
2923 unsigned fx = 0; /* running index in flag_buf */ 3042 unsigned fx = 0; /* running index in flag_buf */
2924 uch flag = 0; /* current flags */ 3043 uch flag = 0; /* current flags */
2925 unsigned code; /* the code to send */ 3044 unsigned code; /* the code to send */
2926 int extra; /* number of extra bits to send */ 3045 int extra; /* number of extra bits to send */
2927 3046
2928 if (last_lit != 0) do { 3047 if (last_lit != 0)
2929 if ((lx & 7) == 0) flag = flag_buf[fx++]; 3048 do {
2930 lc = l_buf[lx++]; 3049 if ((lx & 7) == 0)
2931 if ((flag & 1) == 0) { 3050 flag = flag_buf[fx++];
2932 send_code(lc, ltree); /* send a literal byte */ 3051 lc = l_buf[lx++];
2933 Tracecv(isgraph(lc), (stderr," '%c' ", lc)); 3052 if ((flag & 1) == 0) {
2934 } else { 3053 send_code(lc, ltree); /* send a literal byte */
2935 /* Here, lc is the match length - MIN_MATCH */ 3054 Tracecv(isgraph(lc), (stderr, " '%c' ", lc));
2936 code = length_code[lc]; 3055 } else {
2937 send_code(code+LITERALS+1, ltree); /* send the length code */ 3056 /* Here, lc is the match length - MIN_MATCH */
2938 extra = extra_lbits[code]; 3057 code = length_code[lc];
2939 if (extra != 0) { 3058 send_code(code + LITERALS + 1, ltree); /* send the length code */
2940 lc -= base_length[code]; 3059 extra = extra_lbits[code];
2941 send_bits(lc, extra); /* send the extra length bits */ 3060 if (extra != 0) {
2942 } 3061 lc -= base_length[code];
2943 dist = d_buf[dx++]; 3062 send_bits(lc, extra); /* send the extra length bits */
2944 /* Here, dist is the match distance - 1 */ 3063 }
2945 code = d_code(dist); 3064 dist = d_buf[dx++];
2946 Assert (code < D_CODES, "bad d_code"); 3065 /* Here, dist is the match distance - 1 */
2947 3066 code = d_code(dist);
2948 send_code(code, dtree); /* send the distance code */ 3067 Assert(code < D_CODES, "bad d_code");
2949 extra = extra_dbits[code]; 3068
2950 if (extra != 0) { 3069 send_code(code, dtree); /* send the distance code */
2951 dist -= base_dist[code]; 3070 extra = extra_dbits[code];
2952 send_bits(dist, extra); /* send the extra distance bits */ 3071 if (extra != 0) {
2953 } 3072 dist -= base_dist[code];
2954 } /* literal or match pair ? */ 3073 send_bits(dist, extra); /* send the extra distance bits */
2955 flag >>= 1; 3074 }
2956 } while (lx < last_lit); 3075 } /* literal or match pair ? */
2957 3076 flag >>= 1;
2958 send_code(END_BLOCK, ltree); 3077 } while (lx < last_lit);
3078
3079 send_code(END_BLOCK, ltree);
2959} 3080}
2960 3081
2961/* =========================================================================== 3082/* ===========================================================================
@@ -2966,17 +3087,22 @@ local void compress_block(ltree, dtree)
2966 */ 3087 */
2967local void set_file_type() 3088local void set_file_type()
2968{ 3089{
2969 int n = 0; 3090 int n = 0;
2970 unsigned ascii_freq = 0; 3091 unsigned ascii_freq = 0;
2971 unsigned bin_freq = 0; 3092 unsigned bin_freq = 0;
2972 while (n < 7) bin_freq += dyn_ltree[n++].Freq; 3093
2973 while (n < 128) ascii_freq += dyn_ltree[n++].Freq; 3094 while (n < 7)
2974 while (n < LITERALS) bin_freq += dyn_ltree[n++].Freq; 3095 bin_freq += dyn_ltree[n++].Freq;
2975 *file_type = bin_freq > (ascii_freq >> 2) ? BINARY : ASCII; 3096 while (n < 128)
2976 if (*file_type == BINARY && translate_eol) { 3097 ascii_freq += dyn_ltree[n++].Freq;
2977 warn("-l used on binary file", ""); 3098 while (n < LITERALS)
2978 } 3099 bin_freq += dyn_ltree[n++].Freq;
3100 *file_type = bin_freq > (ascii_freq >> 2) ? BINARY : ASCII;
3101 if (*file_type == BINARY && translate_eol) {
3102 warn("-l used on binary file", "");
3103 }
2979} 3104}
3105
2980/* util.c -- utility functions for gzip support 3106/* util.c -- utility functions for gzip support
2981 * Copyright (C) 1992-1993 Jean-loup Gailly 3107 * Copyright (C) 1992-1993 Jean-loup Gailly
2982 * This is free software; you can redistribute it and/or modify it under the 3108 * This is free software; you can redistribute it and/or modify it under the
@@ -2997,7 +3123,7 @@ local void set_file_type()
2997#if defined(STDC_HEADERS) || !defined(NO_STDLIB_H) 3123#if defined(STDC_HEADERS) || !defined(NO_STDLIB_H)
2998# include <stdlib.h> 3124# include <stdlib.h>
2999#else 3125#else
3000 extern int errno; 3126extern int errno;
3001#endif 3127#endif
3002 3128
3003/* =========================================================================== 3129/* ===========================================================================
@@ -3005,30 +3131,32 @@ local void set_file_type()
3005 * IN assertion: insize bytes have already been read in inbuf. 3131 * IN assertion: insize bytes have already been read in inbuf.
3006 */ 3132 */
3007int copy(in, out) 3133int copy(in, out)
3008 int in, out; /* input and output file descriptors */ 3134int in, out; /* input and output file descriptors */
3009{ 3135{
3010 errno = 0; 3136 errno = 0;
3011 while (insize != 0 && (int)insize != EOF) { 3137 while (insize != 0 && (int) insize != EOF) {
3012 write_buf(out, (char*)inbuf, insize); 3138 write_buf(out, (char *) inbuf, insize);
3013 bytes_out += insize; 3139 bytes_out += insize;
3014 insize = read(in, (char*)inbuf, INBUFSIZ); 3140 insize = read(in, (char *) inbuf, INBUFSIZ);
3015 } 3141 }
3016 if ((int)insize == EOF && errno != 0) { 3142 if ((int) insize == EOF && errno != 0) {
3017 read_error(); 3143 read_error();
3018 } 3144 }
3019 bytes_in = bytes_out; 3145 bytes_in = bytes_out;
3020 return OK; 3146 return OK;
3021} 3147}
3022 3148
3023/* ======================================================================== 3149/* ========================================================================
3024 * Put string s in lower case, return s. 3150 * Put string s in lower case, return s.
3025 */ 3151 */
3026char *strlwr(s) 3152char *strlwr(s)
3027 char *s; 3153char *s;
3028{ 3154{
3029 char *t; 3155 char *t;
3030 for (t = s; *t; t++) *t = tolow(*t); 3156
3031 return s; 3157 for (t = s; *t; t++)
3158 *t = tolow(*t);
3159 return s;
3032} 3160}
3033 3161
3034#if defined(NO_STRING_H) && !defined(STDC_HEADERS) 3162#if defined(NO_STRING_H) && !defined(STDC_HEADERS)
@@ -3039,7 +3167,7 @@ char *strlwr(s)
3039# define const 3167# define const
3040# endif 3168# endif
3041 3169
3042int strspn OF((const char *s, const char *accept)); 3170int strspn OF((const char *s, const char *accept));
3043int strcspn OF((const char *s, const char *reject)); 3171int strcspn OF((const char *s, const char *reject));
3044 3172
3045/* ======================================================================== 3173/* ========================================================================
@@ -3047,21 +3175,23 @@ int strcspn OF((const char *s, const char *reject));
3047 * of s which contains only characters in accept. 3175 * of s which contains only characters in accept.
3048 */ 3176 */
3049int strspn(s, accept) 3177int strspn(s, accept)
3050 const char *s; 3178const char *s;
3051 const char *accept; 3179const char *accept;
3052{ 3180{
3053 register const char *p; 3181 register const char *p;
3054 register const char *a; 3182 register const char *a;
3055 register int count = 0; 3183 register int count = 0;
3056 3184
3057 for (p = s; *p != '\0'; ++p) { 3185 for (p = s; *p != '\0'; ++p) {
3058 for (a = accept; *a != '\0'; ++a) { 3186 for (a = accept; *a != '\0'; ++a) {
3059 if (*p == *a) break; 3187 if (*p == *a)
3188 break;
3189 }
3190 if (*a == '\0')
3191 return count;
3192 ++count;
3060 } 3193 }
3061 if (*a == '\0') return count; 3194 return count;
3062 ++count;
3063 }
3064 return count;
3065} 3195}
3066 3196
3067/* ======================================================================== 3197/* ========================================================================
@@ -3069,104 +3199,113 @@ int strspn(s, accept)
3069 * which contains no characters from reject. 3199 * which contains no characters from reject.
3070 */ 3200 */
3071int strcspn(s, reject) 3201int strcspn(s, reject)
3072 const char *s; 3202const char *s;
3073 const char *reject; 3203const char *reject;
3074{ 3204{
3075 register int count = 0; 3205 register int count = 0;
3076 3206
3077 while (*s != '\0') { 3207 while (*s != '\0') {
3078 if (strchr(reject, *s++) != NULL) return count; 3208 if (strchr(reject, *s++) != NULL)
3079 ++count; 3209 return count;
3080 } 3210 ++count;
3081 return count; 3211 }
3212 return count;
3082} 3213}
3083 3214
3084#endif /* NO_STRING_H */ 3215#endif /* NO_STRING_H */
3085 3216
3086/* ======================================================================== 3217/* ========================================================================
3087 * Add an environment variable (if any) before argv, and update argc. 3218 * Add an environment variable (if any) before argv, and update argc.
3088 * Return the expanded environment variable to be freed later, or NULL 3219 * Return the expanded environment variable to be freed later, or NULL
3089 * if no options were added to argv. 3220 * if no options were added to argv.
3090 */ 3221 */
3091#define SEPARATOR " \t" /* separators in env variable */ 3222#define SEPARATOR " \t" /* separators in env variable */
3092 3223
3093char *add_envopt(argcp, argvp, env) 3224char *add_envopt(argcp, argvp, env)
3094 int *argcp; /* pointer to argc */ 3225int *argcp; /* pointer to argc */
3095 char ***argvp; /* pointer to argv */ 3226char ***argvp; /* pointer to argv */
3096 char *env; /* name of environment variable */ 3227char *env; /* name of environment variable */
3097{ 3228{
3098 char *p; /* running pointer through env variable */ 3229 char *p; /* running pointer through env variable */
3099 char **oargv; /* runs through old argv array */ 3230 char **oargv; /* runs through old argv array */
3100 char **nargv; /* runs through new argv array */ 3231 char **nargv; /* runs through new argv array */
3101 int oargc = *argcp; /* old argc */ 3232 int oargc = *argcp; /* old argc */
3102 int nargc = 0; /* number of arguments in env variable */ 3233 int nargc = 0; /* number of arguments in env variable */
3103 3234
3104 env = (char*)getenv(env); 3235 env = (char *) getenv(env);
3105 if (env == NULL) return NULL; 3236 if (env == NULL)
3106 3237 return NULL;
3107 p = (char*)xmalloc(strlen(env)+1); 3238
3108 env = strcpy(p, env); /* keep env variable intact */ 3239 p = (char *) xmalloc(strlen(env) + 1);
3109 3240 env = strcpy(p, env); /* keep env variable intact */
3110 for (p = env; *p; nargc++ ) { /* move through env */ 3241
3111 p += strspn(p, SEPARATOR); /* skip leading separators */ 3242 for (p = env; *p; nargc++) { /* move through env */
3112 if (*p == '\0') break; 3243 p += strspn(p, SEPARATOR); /* skip leading separators */
3113 3244 if (*p == '\0')
3114 p += strcspn(p, SEPARATOR); /* find end of word */ 3245 break;
3115 if (*p) *p++ = '\0'; /* mark it */ 3246
3116 } 3247 p += strcspn(p, SEPARATOR); /* find end of word */
3117 if (nargc == 0) { 3248 if (*p)
3118 free(env); 3249 *p++ = '\0'; /* mark it */
3119 return NULL; 3250 }
3120 } 3251 if (nargc == 0) {
3121 *argcp += nargc; 3252 free(env);
3122 /* Allocate the new argv array, with an extra element just in case 3253 return NULL;
3123 * the original arg list did not end with a NULL. 3254 }
3124 */ 3255 *argcp += nargc;
3125 nargv = (char**)calloc(*argcp+1, sizeof(char *)); 3256 /* Allocate the new argv array, with an extra element just in case
3126 if (nargv == NULL) error("out of memory"); 3257 * the original arg list did not end with a NULL.
3127 oargv = *argvp; 3258 */
3128 *argvp = nargv; 3259 nargv = (char **) calloc(*argcp + 1, sizeof(char *));
3129 3260
3130 /* Copy the program name first */ 3261 if (nargv == NULL)
3131 if (oargc-- < 0) error("argc<=0"); 3262 error("out of memory");
3132 *(nargv++) = *(oargv++); 3263 oargv = *argvp;
3133 3264 *argvp = nargv;
3134 /* Then copy the environment args */ 3265
3135 for (p = env; nargc > 0; nargc--) { 3266 /* Copy the program name first */
3136 p += strspn(p, SEPARATOR); /* skip separators */ 3267 if (oargc-- < 0)
3137 *(nargv++) = p; /* store start */ 3268 error("argc<=0");
3138 while (*p++) ; /* skip over word */ 3269 *(nargv++) = *(oargv++);
3139 } 3270
3140 3271 /* Then copy the environment args */
3141 /* Finally copy the old args and add a NULL (usual convention) */ 3272 for (p = env; nargc > 0; nargc--) {
3142 while (oargc--) *(nargv++) = *(oargv++); 3273 p += strspn(p, SEPARATOR); /* skip separators */
3143 *nargv = NULL; 3274 *(nargv++) = p; /* store start */
3144 return env; 3275 while (*p++); /* skip over word */
3276 }
3277
3278 /* Finally copy the old args and add a NULL (usual convention) */
3279 while (oargc--)
3280 *(nargv++) = *(oargv++);
3281 *nargv = NULL;
3282 return env;
3145} 3283}
3284
3146/* ======================================================================== 3285/* ========================================================================
3147 * Display compression ratio on the given stream on 6 characters. 3286 * Display compression ratio on the given stream on 6 characters.
3148 */ 3287 */
3149void display_ratio(num, den, file) 3288void display_ratio(num, den, file)
3150 long num; 3289long num;
3151 long den; 3290long den;
3152 FILE *file; 3291FILE *file;
3153{ 3292{
3154 long ratio; /* 1000 times the compression ratio */ 3293 long ratio; /* 1000 times the compression ratio */
3155 3294
3156 if (den == 0) { 3295 if (den == 0) {
3157 ratio = 0; /* no compression */ 3296 ratio = 0; /* no compression */
3158 } else if (den < 2147483L) { /* (2**31 -1)/1000 */ 3297 } else if (den < 2147483L) { /* (2**31 -1)/1000 */
3159 ratio = 1000L*num/den; 3298 ratio = 1000L * num / den;
3160 } else { 3299 } else {
3161 ratio = num/(den/1000L); 3300 ratio = num / (den / 1000L);
3162 } 3301 }
3163 if (ratio < 0) { 3302 if (ratio < 0) {
3164 putc('-', file); 3303 putc('-', file);
3165 ratio = -ratio; 3304 ratio = -ratio;
3166 } else { 3305 } else {
3167 putc(' ', file); 3306 putc(' ', file);
3168 } 3307 }
3169 fprintf(file, "%2ld.%1ld%%", ratio / 10L, ratio % 10L); 3308 fprintf(file, "%2ld.%1ld%%", ratio / 10L, ratio % 10L);
3170} 3309}
3171 3310
3172 3311
@@ -3186,8 +3325,8 @@ void display_ratio(num, den, file)
3186# include <fcntl.h> 3325# include <fcntl.h>
3187#endif 3326#endif
3188 3327
3189local ulg crc; /* crc on uncompressed file data */ 3328local ulg crc; /* crc on uncompressed file data */
3190long header_bytes; /* number of bytes in gzip header */ 3329long header_bytes; /* number of bytes in gzip header */
3191 3330
3192/* =========================================================================== 3331/* ===========================================================================
3193 * Deflate in to out. 3332 * Deflate in to out.
@@ -3195,48 +3334,48 @@ long header_bytes; /* number of bytes in gzip header */
3195 * The variables time_stamp and save_orig_name are initialized. 3334 * The variables time_stamp and save_orig_name are initialized.
3196 */ 3335 */
3197int zip(in, out) 3336int zip(in, out)
3198 int in, out; /* input and output file descriptors */ 3337int in, out; /* input and output file descriptors */
3199{ 3338{
3200 uch flags = 0; /* general purpose bit flags */ 3339 uch flags = 0; /* general purpose bit flags */
3201 ush attr = 0; /* ascii/binary flag */ 3340 ush attr = 0; /* ascii/binary flag */
3202 ush deflate_flags = 0; /* pkzip -es, -en or -ex equivalent */ 3341 ush deflate_flags = 0; /* pkzip -es, -en or -ex equivalent */
3203 3342
3204 ifd = in; 3343 ifd = in;
3205 ofd = out; 3344 ofd = out;
3206 outcnt = 0; 3345 outcnt = 0;
3207 3346
3208 /* Write the header to the gzip file. See algorithm.doc for the format */ 3347 /* Write the header to the gzip file. See algorithm.doc for the format */
3209 3348
3210 3349
3211 method = DEFLATED; 3350 method = DEFLATED;
3212 put_byte(GZIP_MAGIC[0]); /* magic header */ 3351 put_byte(GZIP_MAGIC[0]); /* magic header */
3213 put_byte(GZIP_MAGIC[1]); 3352 put_byte(GZIP_MAGIC[1]);
3214 put_byte(DEFLATED); /* compression method */ 3353 put_byte(DEFLATED); /* compression method */
3215 3354
3216 put_byte(flags); /* general flags */ 3355 put_byte(flags); /* general flags */
3217 put_long(time_stamp); 3356 put_long(time_stamp);
3218 3357
3219 /* Write deflated file to zip file */ 3358 /* Write deflated file to zip file */
3220 crc = updcrc(0, 0); 3359 crc = updcrc(0, 0);
3221 3360
3222 bi_init(out); 3361 bi_init(out);
3223 ct_init(&attr, &method); 3362 ct_init(&attr, &method);
3224 lm_init(&deflate_flags); 3363 lm_init(&deflate_flags);
3225 3364
3226 put_byte((uch)deflate_flags); /* extra flags */ 3365 put_byte((uch) deflate_flags); /* extra flags */
3227 put_byte(OS_CODE); /* OS identifier */ 3366 put_byte(OS_CODE); /* OS identifier */
3228 3367
3229 header_bytes = (long)outcnt; 3368 header_bytes = (long) outcnt;
3230 3369
3231 (void)deflate(); 3370 (void) deflate();
3232 3371
3233 /* Write the crc and uncompressed size */ 3372 /* Write the crc and uncompressed size */
3234 put_long(crc); 3373 put_long(crc);
3235 put_long(isize); 3374 put_long(isize);
3236 header_bytes += 2*sizeof(long); 3375 header_bytes += 2 * sizeof(long);
3237 3376
3238 flush_outbuf(); 3377 flush_outbuf();
3239 return OK; 3378 return OK;
3240} 3379}
3241 3380
3242 3381
@@ -3246,18 +3385,19 @@ int zip(in, out)
3246 * IN assertion: size >= 2 (for end-of-line translation) 3385 * IN assertion: size >= 2 (for end-of-line translation)
3247 */ 3386 */
3248int file_read(buf, size) 3387int file_read(buf, size)
3249 char *buf; 3388char *buf;
3250 unsigned size; 3389unsigned size;
3251{ 3390{
3252 unsigned len; 3391 unsigned len;
3253 3392
3254 Assert(insize == 0, "inbuf not empty"); 3393 Assert(insize == 0, "inbuf not empty");
3255 3394
3256 len = read(ifd, buf, size); 3395 len = read(ifd, buf, size);
3257 if (len == (unsigned)(-1) || len == 0) return (int)len; 3396 if (len == (unsigned) (-1) || len == 0)
3397 return (int) len;
3258 3398
3259 crc = updcrc((uch*)buf, len); 3399 crc = updcrc((uch *) buf, len);
3260 isize += (ulg)len; 3400 isize += (ulg) len;
3261 return (int)len; 3401 return (int) len;
3262} 3402}
3263#endif 3403#endif
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-03-28 09:48:13 +0000