1 /******************************************************************************
2 *
3 * NSSDC/CDF GnuZIP compression/decompression.
4 *
5 * Version 1.0b, 2-Sep-97.
6 *
7 * Modification history:
8 *
9 * V1.0 27-Aug-96, J Love Original version, but...the `zip' and `unzip'
10 * routines (and their supporting routines) are
11 * modified versions of routines provided by the
12 * named institutions and/or individuals.
13 * V1.0a 20-Dec-96, J Love Renamed BIT macro to avoid collision on
14 * Linux systems. Eliminated sanity check if
15 * using Salford C.
16 * V1.0b 2-Sep-97, J Love Type casting for ANSI C.
17 *
18 ******************************************************************************/
19
20 #include "cdflib.h"
21 #include "cdflib64.h"
22
23 #if !SUPPORT_GZIP_c && defined(BORLANDC)
24 #pragma warn -par
25 #endif
26
27 /******************************************************************************
28 * Macros.
29 ******************************************************************************/
30
31 #if 0 /* MS-DOS? */
32 #define SMALL_MEM
33 #endif
34
35 #if 0 /* MacOS? */
36 #define MEDIUM_MEM
37 #endif
38
39 #define N_BORDER 19
40 #define N_CPLENS 31
41 #define N_CPLEXT 31
42 #define N_CPDIST 30
43 #define N_CPDEXT 30
44 #define N_MASK_BITS 17
45 #define N_CRC_32_TAB 256
46
47 #define BL_CODES 19
48 /* number of codes used to transfer the bit lengths */
49
50 #define MAX_BITS 15
51 /* All codes must not exceed MAX_BITS bits */
52
53 #define LITERALS 256
54 /* number of literal bytes 0..255 */
55
56 #define LENGTH_CODES 29
57 /* number of length codes, not counting the special END_BLOCK code */
58
59 #define L_CODES (LITERALS+1+LENGTH_CODES)
60 /* number of Literal or Length codes, including the END_BLOCK code */
61
62 #define D_CODES 30
63 /* number of distance codes */
64
65 #define HEAP_SIZE (2*L_CODES+1)
66 /* maximum heap size */
67
68 #define MIN_MATCH 3
69 #define MAX_MATCH 258
70 /* The minimum and maximum match lengths */
71
72 #ifndef LIT_BUFSIZE
73 #ifdef SMALL_MEM
74 #define LIT_BUFSIZE 0x2000
75 #else
76 #ifdef MEDIUM_MEM
77 #define LIT_BUFSIZE 0x4000
78 #else
79 #define LIT_BUFSIZE 0x8000
80 #endif
81 #endif
82 #endif
83
84 /******************************************************************************
85 * Typedef's and structure definitions.
86 ******************************************************************************/
87
88 typedef unsigned char uch;
89 typedef unsigned short ush;
90 typedef unsigned long ulg;
91
92 typedef ush Pos;
93 typedef unsigned IPos;
94 /* A Pos is an index in the character window. We use short instead of int to
95 * save space in the various tables. IPos is used only for parameter passing.
96 */
97
98 typedef struct {
99 ush good_length; /* reduce lazy search above this match length */
100 ush max_lazy; /* do not perform lazy search above this match length */
101 ush nice_length; /* quit search above this match length */
102 ush max_chain;
103 } config;
104
105 /* Data structure describing a single value and its code string. */
106 typedef struct ct_data {
107 union {
108 ush freq; /* frequency count */
109 ush code; /* bit string */
110 } fc;
111 union {
112 ush dad; /* father node in Huffman tree */
113 ush len; /* length of bit string */
114 } dl;
115 } ct_data;
116
117 typedef struct tree_desc {
118 ct_data *dyn_tree; /* the dynamic tree */
119 ct_data *static_tree; /* corresponding static tree or NULL */
120 int *extra_bits; /* extra bits for each code or NULL */
121 int extra_base; /* base index for extra_bits */
122 int elems; /* max number of elements in the tree */
123 int max_length; /* max bit length for the codes */
124 int max_code; /* largest code with non zero frequency */
125 } tree_desc;
126
127 /* Huffman code lookup table entry--this entry is four bytes for machines
128 that have 16-bit pointers (e.g. PC's in the small or medium model).
129 Valid extra bits are 0..13. e == 15 is EOB (end of block), e == 16
130 means that v is a literal, 16 < e < 32 means that v is a pointer to
131 the next table, which codes e - 16 bits, and lastly e == 99 indicates
132 an unused code. If a code with e == 99 is looked up, this implies an
133 error in the data. */
134
135 struct huft {
136 uch e; /* number of extra bits or operation */
137 uch b; /* number of bits in this code or subcode */
138 union {
139 ush n; /* literal, length base, or distance base */
140 struct huft *t; /* pointer to next level of table */
141 } v;
142 };
143
144 struct gZipStruct {
145 vFILE *iFp;
146 vFILE *oFp;
147 CDFstatus iError; /* Returned if input file error. */
148 CDFstatus oError; /* Returned if output file error. */
149 OFF_T ifile_size; /* input file size */
150 unsigned short bi_buf;/* Output buffer. bits are inserted starting
151 at the bottom (least significant bits). */
152 int bi_valid; /* Number of valid bits in bi_buf. All bits above
153 the last valid bit are always zero. */
154 OFF_T block_start; /* window position at the beginning of the current
155 output block. Gets negative when the window is
156 moved backwards. */
157 unsigned ins_h; /* hash index of string to be inserted */
158 unsigned strstart; /* start of string to insert */
159 unsigned match_start; /* start of matching string */
160 int eofile; /* flag set at end of input file */
161 unsigned lookahead; /* number of valid bytes ahead in window */
162 unsigned int prev_length;
163 /* Length of the best match at previous step. Matches
164 not greater than this are discarded. This is used
165 in the lazy match evaluation. */
166 ush bl_count[MAX_BITS+1];
167 /* number of codes at each bit length for an optimal
168 tree */
169 int heap[2*L_CODES+1];/* heap used to build the Huffman trees */
170 int heap_len; /* number of elements in the heap */
171 int heap_max; /* element of largest frequency */
172 /* The sons of heap[n] are heap[2*n] and heap[2*n+1].
173 * heap[0] is not used.
174 * The same heap array is used to build all trees.
175 */
176 uch depth[2*L_CODES+1];
177 /* Depth of each subtree used as tie breaker for
178 trees of equal frequency */
179 uch length_code[MAX_MATCH-MIN_MATCH+1];
180 /* length code for each normalized match length
181 (0 == MIN_MATCH) */
182 uch dist_code[512]; /* distance codes. The first 256 values correspond
183 to the distances 3 .. 258, the last 256 values
184 correspond to the top 8 bits of the 15 bit
185 distances. */
186 int base_length[LENGTH_CODES];
187 /* First normalized length for each code
188 (0 = MIN_MATCH) */
189 int base_dist[D_CODES];
190 /* First normalized distance for each code
191 (0 = distance of 1) */
192 uch flag_buf[(LIT_BUFSIZE/8)];
193 /* flag_buf is a bit array distinguishing literals
194 from lengths in l_buf (inbuf), thus indicating the
195 presence or absence of a distance. */
196 unsigned last_lit; /* running index in l_buf (inbuf) */
197 unsigned last_dist; /* running index in d_buf */
198 unsigned last_flags; /* running index in flag_buf */
199 uch tree_flags; /* current flags not yet saved in flag_buf */
200 uch flag_bit; /* current bit used in flags */
201 /* bits are filled in flags starting at bit 0 (least
202 significant). Note: these flags are overkill in
203 the current code since we don't take advantage of
204 DIST_BUFSIZE == LIT_BUFSIZE. */
205 ulg opt_len; /* bit length of current block with optimal trees */
206 ulg static_len; /* bit length of current block with static trees */
207 int level; /* compression level */
208 unsigned outcnt; /* bytes in output buffer */
209 OFF_T bytes_in; /* number of input bytes */
210 OFF_T bytes_out; /* number of output bytes */
211 ulg crc; /* crc on uncompressed file data */
212 ulg crcReg; /* shift register contents */
213 config configuration_table[10];
214 uch bl_order[BL_CODES];
215 /* The lengths of the bit length codes are sent in
216 order of decreasing probability, to avoid
217 transmitting the lengths for unused bit length
218 codes. */
219 int extra_lbits[LENGTH_CODES];
220 /* extra bits for each length code */
221 ct_data dyn_ltree[HEAP_SIZE];
222 /* literal and length tree */
223 ct_data static_ltree[L_CODES+2];
224 /* The static literal tree. Since the bit lengths are
225 imposed, there is no need for the L_CODES extra
226 codes used during heap construction. However, the
227 codes 286 and 287 are needed to build a canonical
228 tree (see ct_init below). */
229 tree_desc l_desc;
230 int extra_dbits[D_CODES];
231 /* extra bits for each distance code */
232 ct_data dyn_dtree[2*D_CODES+1];
233 /* distance tree */
234 ct_data static_dtree[D_CODES];
235 /* The static distance tree. (Actually a trivial tree
236 since all codes use 5 bits.) */
237 tree_desc d_desc;
238 int extra_blbits[BL_CODES];
239 /* extra bits for each bit length code */
240 ct_data bl_tree[2*BL_CODES+1];
241 /* Huffman tree for the bit lengths */
242 tree_desc bl_desc;
243 ulg crc_32_tab[N_CRC_32_TAB];
244 /* Table of CRC-32's of all single-byte values (made
245 by makecrc.c) */
246 uch *inbuf; /* input buffer */
247 uch *outbuf; /* output buffer */
248 ush *d_buf; /* buffer for distances, see trees.c */
249 uch *window; /* Sliding window and suffix table (unlzw) */
250 ush *prev;
251 ush *head;
252 };
253 typedef struct gZipStruct GZ;
254 typedef struct gZipStruct *GZp;
255
256 struct gUnZipStruct {
257 vFILE *iFp;
258 vFILE *oFp;
259 CDFstatus iError; /* Returned if input file error. */
260 CDFstatus oError; /* Returned if output file error. */
261 ulg bb; /* bit buffer */
262 unsigned bk; /* bits in bit buffer */
263 unsigned hufts; /* track memory usage */
264 unsigned outcnt; /* bytes in output buffer */
265 OFF_T bytes_in; /* number of input bytes */
266 OFF_T bytes_out; /* number of output bytes */
267 ulg crcReg; /* shift register contents */
268 unsigned insize; /* valid bytes in inbuf */
269 unsigned inptr; /* index of next byte to be processed in inbuf */
270 unsigned border[N_BORDER];
271 /* Order of the bit length code lengths */
272 ush cplens[N_CPLENS]; /* Copy lengths for literal codes 257..285 */
273 ush cplext[N_CPLEXT]; /* Extra bits for literal codes 257..285 */
274 ush cpdist[N_CPDIST]; /* Copy offsets for distance codes 0..29 */
275 ush cpdext[N_CPDEXT]; /* Extra bits for distance codes */
276 ush mask_bits[N_MASK_BITS];
277 ulg crc_32_tab[N_CRC_32_TAB];
278 /* Table of CRC-32's of all single-byte values (made
279 by makecrc.c) */
280 uch *inbuf; /* input buffer */
281 uch *window; /* Sliding window and suffix table (unlzw) */
282 };
283 typedef struct gUnZipStruct GU;
284 typedef struct gUnZipStruct *GUp;
285
286 /******************************************************************************
287 * More macros.
288 ******************************************************************************/
289
290 #define OS_CODE 0xFF /* Does it really matter? - JTL */
291 /* <Operating System,OS_CODE>:
292 <MS-DOS,0x0> <OS2,0x6> <WindowsNT,0xB>
293 <VMS,0x2> <UNIX,0x3> <amiga,0x1>
294 <atari,0x5> <MacOS,0x7> <PRIMOS,0xF>
295 <TOPS20,0xA> */
296
297 #define OF(args) PROTOARGs(args)
298 #define memzero(s,n) memset((void*)(s),0,(n))
299
300 /* Compression methods (see algorithm.doc) */
301 #define DEFLATED 8
302
303 /* To save memory for 16 bit systems, some arrays are overlaid between
304 * the various modules:
305 * deflate: prev+head window d_buf l_buf outbuf
306 * unlzw: tab_prefix tab_suffix stack inbuf outbuf
307 * inflate: window inbuf
308 * unpack: window inbuf prefix_len
309 * unlzh: left+right window c_table inbuf c_len
310 * For compression, input is done in window[]. For decompression, output
311 * is done in window except for unlzw.
312 */
313
314 #ifndef INBUFSIZ
315 #ifdef SMALL_MEM
316 #define INBUFSIZ 0x2000 /* input buffer size */
317 #else
318 #define INBUFSIZ 0x8000 /* input buffer size */
319 #endif
320 #endif
321 #define INBUF_EXTRA 64 /* required by unlzw() */
322
323 #ifndef OUTBUFSIZ
324 #ifdef SMALL_MEM
325 #define OUTBUFSIZ 8192 /* output buffer size */
326 #else
327 #define OUTBUFSIZ 16384 /* output buffer size */
328 #endif
329 #endif
330 #define OUTBUF_EXTRA 2048 /* required by unlzw() */
331
332 #ifndef DIST_BUFSIZE
333 #ifdef SMALL_MEM
334 #define DIST_BUFSIZE 0x2000 /* buffer for distances, see trees.c */
335 #else
336 #define DIST_BUFSIZE 0x8000 /* buffer for distances, see trees.c */
337 #endif
338 #endif
339
340 #define GZIP_MAGIC "\037\213" /* Magic header for gzip files, 1F 8B */
341
342 /* gzip flag byte */
343 #define ASCII_FLAG 0x01 /* bit 0 set: file probably ascii text */
344 #define CONTINUATION 0x02 /* bit 1 set: continuation of multi-part gzip file */
345 #define EXTRA_FIELD 0x04 /* bit 2 set: extra field present */
346 #define ORIG_NAME 0x08 /* bit 3 set: original file name present */
347 #define COMMENT 0x10 /* bit 4 set: file comment present */
348 #define ENCRYPTED 0x20 /* bit 5 set: file is encrypted */
349 #define RESERVED 0xC0 /* bit 6,7: reserved */
350
351 #ifndef WSIZE
352 #define WSIZE 0x8000 /* window size--must be a power of two, and */
353 #endif /* at least 32K for zip's deflate method */
354 #define WINDOW_SIZE ((ulg)2*WSIZE)
355
356 #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
357 /* Minimum amount of lookahead, except at the end of the input file.
358 * See deflate.c for comments about the MIN_MATCH+1.
359 */
360
361 #define MAX_DIST (WSIZE-MIN_LOOKAHEAD)
362 /* In order to simplify the code, particularly on 16 bit machines, match
363 * distances are limited to MAX_DIST instead of WSIZE.
364 */
365
366 /* Macros for getting two-byte and four-byte header values */
367 #define SH(p) ((ush)(uch)((p)[0]) | ((ush)(uch)((p)[1]) << 8))
368 #define LG(p) ((ulg)(SH(p)) | ((ulg)(SH((p)+2)) << 16))
369
370 /* lzw.h -- define the lzw functions.
371 * Copyright (C) 1992-1993 Jean-loup Gailly.
372 * This is free software; you can redistribute it and/or modify it under the
373 * terms of the GNU General Public License, see the file COPYING.
374 */
375
376 #define LBITS 9 /* bits in base literal/length lookup table */
377 #define DBITS 6 /* bits in base distance lookup table */
378
379 #ifndef BITSx
380 #define BITSx 16
381 #endif
382 #define INIT_BITS 9 /* Initial number of bits per code */
383
384 #define BUF_SIZE (8 * 2*sizeof(char))
385 /* Number of bits used within bi_buf. (bi_buf might be implemented on
386 * more than 16 bits on some systems.)
387 */
388
389 /* Compile with MEDIUM_MEM to reduce the memory requirements or
390 * with SMALL_MEM to use as little memory as possible. Use BIG_MEM if the
391 * entire input file can be held in memory (not possible on 16 bit systems).
392 * Warning: defining these symbols affects HASH_BITS (see below) and thus
393 * affects the compression ratio. The compressed output
394 * is still correct, and might even be smaller in some cases.
395 */
396
397 #ifdef SMALL_MEM
398 #define HASH_BITS 13 /* Number of bits used to hash strings */
399 #endif
400 #ifdef MEDIUM_MEM
401 #define HASH_BITS 14
402 #endif
403 #ifndef HASH_BITS
404 #define HASH_BITS 15
405 /* For portability to 16 bit machines, do not use values above 15. */
406 #endif
407
408 /* To save space (see unlzw.c), we overlay prev+head with tab_prefix and
409 * window with tab_suffix. Check that we can do this:
410 */
411 #if !defined(SALFORDC)
412 #if (WSIZE<<1) > (1<<BITSx)
413 error: cannot overlay window with tab_suffix and prev with tab_prefix0
414 #endif
415 #endif
416 #if HASH_BITS > BITSx-1
417 error: cannot overlay head with tab_prefix1
418 #endif
419 #if EOF != (-1)
420 error: EOF != (-1)
421 #endif
422
423 #define HASH_SIZE (unsigned)(1<<HASH_BITS)
424 #define HASH_MASK (HASH_SIZE-1)
425 #define WMASK (WSIZE-1)
426 /* HASH_SIZE and WSIZE must be powers of two */
427
428 #define NIL 0
429 /* Tail of hash chains */
430
431 #define FAST 4
432 #define SLOW 2
433 /* speed options for the general purpose bit flag */
434
435 #ifndef TOO_FAR
436 #define TOO_FAR 4096
437 #endif
438 /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
439
440 #define H_SHIFT ((HASH_BITS+MIN_MATCH-1)/MIN_MATCH)
441 /* Number of bits by which ins_h and del_h must be shifted at each
442 * input step. It must be such that after MIN_MATCH steps, the oldest
443 * byte no longer takes part in the hash key, that is:
444 * H_SHIFT * MIN_MATCH >= HASH_BITS
445 */
446
447 /* ===========================================================================
448 * Constants
449 */
450
451 #define MAX_BL_BITS 7
452 /* Bit length codes must not exceed MAX_BL_BITS bits */
453
454 #define END_BLOCK 256
455 /* end of block literal code */
456
457 #define STORED_BLOCK 0
458 #define STATIC_TREES 1
459 #define DYN_TREES 2
460 /* The three kinds of block type */
461
462 #ifndef DIST_BUFSIZE
463 #define DIST_BUFSIZE LIT_BUFSIZE
464 #endif
465 /* Sizes of match buffers for literals/lengths and distances. There are
466 * 4 reasons for limiting LIT_BUFSIZE to 64K:
467 * - frequencies can be kept in 16 bit counters
468 * - if compression is not successful for the first block, all input data is
469 * still in the window so we can still emit a stored block even when input
470 * comes from standard input. (This can also be done for all blocks if
471 * LIT_BUFSIZE is not greater than 32K.)
472 * - if compression is not successful for a file smaller than 64K, we can
473 * even emit a stored file instead of a stored block (saving 5 bytes).
474 * - creating new Huffman trees less frequently may not provide fast
475 * adaptation to changes in the input data statistics. (Take for
476 * example a binary file with poorly compressible code followed by
477 * a highly compressible string table.) Smaller buffer sizes give
478 * fast adaptation but have of course the overhead of transmitting trees
479 * more frequently.
480 * - I can't count above 4
481 * The current code is general and allows DIST_BUFSIZE < LIT_BUFSIZE (to save
482 * memory at the expense of compression). Some optimizations would be possible
483 * if we rely on DIST_BUFSIZE == LIT_BUFSIZE.
484 */
485 #if LIT_BUFSIZE > INBUFSIZ
486 error cannot overlay l_buf and inbuf
487 #endif
488
489 #define REP_3_6 16
490 /* repeat previous bit length 3-6 times (2 bits of repeat count) */
491
492 #define REPZ_3_10 17
493 /* repeat a zero length 3-10 times (3 bits of repeat count) */
494
495 #define REPZ_11_138 18
496 /* repeat a zero length 11-138 times (7 bits of repeat count) */
497
498 #define send_code(gz_, c_, tree_) \
499 send_bits(gz_, tree_[c_].fc.code, tree_[c_].dl.len)
500 /* Send a code of the given tree. c and tree must not have side effects */
501
502 #define d_code(dist_,dist_code_) \
503 ((dist_) < 256 ? dist_code_[dist_] : dist_code_[256+((dist_)>>7)])
504 /* Mapping from a distance to a distance code. dist is the distance - 1 and
505 * must not have side effects. dist_code[256] and dist_code[257] are never
506 * used.
507 */
508
509 /* The inflate algorithm uses a sliding 32K byte window on the uncompressed
510 stream to find repeated byte strings. This is implemented here as a
511 circular buffer. The index is updated simply by incrementing and then
512 and'ing with 0x7fff (32K-1). */
513 /* It is left to other modules to supply the 32K area. It is assumed
514 to be usable as if it were declared "uch slide[32768];" or as just
515 "uch *slide;" and then malloc'ed in the latter case. The definition
516 must be in unzip.h, included above. */
517
518 /* Macros for inflate() bit peeking and grabbing.
519 The usage is:
520
521 NEEDBITS(gu,b,k,j)
522 x = b & mask_bits[j];
523 DUMPBITS(b,k,j)
524
525 where NEEDBITS makes sure that b has at least j bits in it, and
526 DUMPBITS removes the bits from b. The macros use the variable k
527 for the number of bits in b. Normally, b and k are register
528 variables for speed, and are initialized at the beginning of a
529 routine that uses these macros from a global bit buffer and count.
530
531 If we assume that EOB will be the longest code, then we will never
532 ask for bits with NEEDBITS that are beyond the end of the stream.
533 So, NEEDBITS should not read any more bytes than are needed to
534 meet the request. Then no bytes need to be "returned" to the buffer
535 at the end of the last block.
536
537 However, this assumption is not true for fixed blocks--the EOB code
538 is 7 bits, but the other literal/length codes can be 8 or 9 bits.
539 (The EOB code is shorter than other codes because fixed blocks are
540 generally short. So, while a block always has an EOB, many other
541 literal/length codes have a significantly lower probability of
542 showing up at all.) However, by making the first table have a
543 lookup of seven bits, the EOB code will be found in that first
544 lookup, and so will not require that too many bits be pulled from
545 the stream.
546 */
547
548 #define NEEDBITS(gu_,b_,k_,n_) { \
549 while (k_ < (n_)) { \
550 uch byte_; \
551 if (!GetByte(gu_,&byte_)) return 4; /* Read error. */ \
552 b_ |= (((ulg)byte_) << k_); \
553 k_ += 8; \
554 } \
555 }
556
557 #define DUMPBITS(b_,k_,n_) { \
558 b_ >>= (n_); \
559 k_ -= (n_); \
560 }
561
562 /* If BMAX needs to be larger than 16, then h and x[] should be ulg. */
563 #define BMAX 16 /* maximum bit length of any code (16 for explode) */
564 #define N_MAX 288 /* maximum number of codes in any set */
565
566 /******************************************************************************
567 * Function prototypes.
568 ******************************************************************************/
569
570 #if SUPPORT_GZIP64
571 static void initCRC OF((ulg crc_32_tab[N_CRC_32_TAB]));
572 static Logical PutByte OF((GZp gz, unsigned c));
573 static Logical PutShort OF((GZp gz, unsigned w));
574 static Logical PutLong OF((GZp gz, ulg n));
575 static Logical PutLongLong OF((GZp gz, OFF_T n));
576 static Logical GetByte OF((GUp gu, uch *byte));
577 static CDFstatus zip OF((
578 vFILE *iFp, OFF_T iSize, CDFstatus iError, vFILE *oFp, OFF_T *oSize,
579 CDFstatus oError, Int32 level
580 ));
581 static GZp initZip OF((
582 vFILE *iFp, vFILE *oFp, OFF_T iSize, Int32 level, CDFstatus iError,
583 CDFstatus oError
584 ));
585 static void freeZip OF((GZp gz));
586 static int file_read OF((GZp gz, char *buf, unsigned size));
587 static CDFstatus unzip OF((
588 vFILE *iFp, vFILE *oFp, CDFstatus iError, CDFstatus oError
589 ));
590 static GUp initUnZip OF((
591 vFILE *iFp, vFILE *oFp, CDFstatus iError, CDFstatus oError
592 ));
593 static void freeUnZip OF((GUp gu));
594 static Logical lm_init OF((GZp gz, ush *flags));
595 static CDFstatus deflate OF((GZp gz));
596 static void ct_init OF((GZp gz));
597 static int ct_tally OF((GZp gz, int dist, int lc));
598 static Logical flush_block OF((GZp gz, char *buf, OFF_T stored_len, int eof));
599 static void bi_init OF((GZp gz));
600 static Logical send_bits OF((GZp gz, int value, int length));
601 static unsigned bi_reverse OF((unsigned value, int length));
602 static Logical bi_windup OF((GZp gz));
603 static Logical copy_block OF((GZp gz, char *buf, unsigned len, int header));
604 static ulg updcrc OF((
605 uch *s, unsigned n, ulg *crcReg, ulg crc_32_tab[N_CRC_32_TAB]
606 ));
607 static Logical fill_inbuf OF((GUp gu, uch *byte));
608 static Logical flush_outbuf OF((GZp gz));
609 static Logical flush_window OF((GUp gu));
610 static Logical write_buf OF((vFILE *vFp, void *buf, unsigned cnt));
611 static int inflate OF((GUp gu));
612 static Logical fill_window OF((GZp gz));
613 static CDFstatus deflate_fast OF((GZp gz));
614 static int longest_match OF((GZp gz, IPos cur_match));
615 static void init_block OF((GZp gz));
616 static void pqdownheap OF((GZp gz, ct_data *tree, int k));
617 static void gen_bitlen OF((GZp gz, tree_desc *desc));
618 static void gen_codes OF((GZp gz, ct_data *tree, int max_code));
619 static void build_tree_gz OF((GZp gz, tree_desc *desc));
620 static void scan_tree OF((GZp gz, ct_data *tree, int max_code));
621 static Logical send_tree OF((GZp gz, ct_data *tree, int max_code));
622 static int build_bl_tree OF((GZp gz));
623 static Logical send_all_trees OF((
624 GZp gz, int lcodes, int dcodes, int blcodes
625 ));
626 static Logical compress_block OF((GZp gz, ct_data *ltree, ct_data *dtree));
627 static int huft_build OF((
628 GUp gu, unsigned *b, unsigned n, unsigned s, ush *d, ush *e,
629 struct huft **t, int *m
630 ));
631 static int huft_free OF((struct huft *t));
632 static int inflate_codes OF((
633 GUp gu, struct huft *tl, struct huft *td, int bl, int bd
634 ));
635 static int inflate_stored OF((GUp gu));
636 static int inflate_fixed OF((GUp gu));
637 static int inflate_dynamic OF((GUp gu));
638 static int inflate_block OF((GUp gu, int *e));
639 static int inflate OF((GUp gu));
640 #endif
641
642 /******************************************************************************
643 * CompressGZIP_64.
644 ******************************************************************************/
645
CompressGZIP_64(srcFp,srcOffset,srcSize,srcError,destFp,destOffset,destSize,destError,level)646 STATICforIDL CDFstatus CompressGZIP_64 (srcFp, srcOffset, srcSize, srcError,
647 destFp, destOffset, destSize, destError,
648 level)
649 vFILE *srcFp;
650 OFF_T srcOffset;
651 OFF_T srcSize;
652 CDFstatus srcError;
653 vFILE *destFp;
654 OFF_T destOffset;
655 OFF_T *destSize;
656 CDFstatus destError;
657 Int32 level;
658 {
659 #if SUPPORT_GZIP64
660 CDFstatus pStatus = CDF_OK;
661 if (!SEEKv64(srcFp,srcOffset,vSEEK_SET)) return srcError;
662 if (!SEEKv64(destFp,destOffset,vSEEK_SET)) return destError;
663 if (!sX(zip(srcFp,srcSize,srcError,
664 destFp,destSize,destError,level),&pStatus)) return pStatus;
665 return pStatus;
666 #else
667 return UNKNOWN_COMPRESSION;
668 #endif
669 }
670
671 /******************************************************************************
672 * DecompressGZIP_64.
673 ******************************************************************************/
674
DecompressGZIP_64(srcFp,srcOffset,srcError,destFp,destOffset,destError)675 STATICforIDL CDFstatus DecompressGZIP_64 (srcFp, srcOffset, srcError, destFp,
676 destOffset, destError)
677 vFILE *srcFp;
678 OFF_T srcOffset;
679 CDFstatus srcError;
680 vFILE *destFp;
681 OFF_T destOffset;
682 CDFstatus destError;
683 {
684 #if SUPPORT_GZIP64
685 CDFstatus pStatus = CDF_OK;
686 if (!SEEKv64(srcFp,srcOffset,vSEEK_SET)) return srcError;
687 if (!SEEKv64(destFp,destOffset,vSEEK_SET)) return destError;
688 if (!sX(unzip(srcFp,destFp,srcError,destError),&pStatus)) return pStatus;
689 return pStatus;
690 #else
691 return UNKNOWN_COMPRESSION;
692 #endif
693 }
694
695 #if SUPPORT_GZIP64
696 /******************************************************************************
697 * zip.
698 * Returns as soon as an error occurs. Any memory allocated will be freed
699 * by the calling routine. If successful, this routine frees the memory.
700 ******************************************************************************/
701
702 /* zip.c -- compress files to the gzip or pkzip format
703 * Copyright (C) 1992-1993 Jean-loup Gailly
704 * This is free software; you can redistribute it and/or modify it under the
705 * terms of the GNU General Public License, see the file COPYING.
706 */
707
708 /* ===========================================================================
709 * Deflate in to out.
710 * IN assertions: the input and output buffers are cleared.
711 * The variables time_stamp and save_orig_name are initialized.
712 */
713
zip(iFp,iSize,iError,oFp,oSize,oError,level)714 static CDFstatus zip (iFp, iSize, iError, oFp, oSize, oError, level)
715 vFILE *iFp;
716 OFF_T iSize;
717 CDFstatus iError;
718 vFILE *oFp;
719 OFF_T *oSize;
720 CDFstatus oError;
721 Int32 level;
722 {
723 CDFstatus pStatus = CDF_OK;
724 uch flags2 = 0; /* general purpose bit flags */
725 ush deflate_flags = 0; /* pkzip -es, -en or -ex equivalent */
726 long time_stamp = 0; /* JTL */
727 GZp gz;
728 gz = initZip (iFp, oFp, iSize, level, iError, oError);
729 if (gz == NULL) return BAD_MALLOC;
730 /* Write the header to the gzip file. See algorithm.doc for the format */
731 if (!PutByte(gz,(unsigned)GZIP_MAGIC[0])) return gz->oError;
732 /* magic header[0]. */
733 if (!PutByte(gz,(unsigned)GZIP_MAGIC[1])) return gz->oError;
734 /* magic header[1]. */
735 if (!PutByte(gz,(unsigned)DEFLATED)) return gz->oError;
736 /* compression method. */
737 if (!PutByte(gz,(unsigned)flags2)) return gz->oError;
738 /* general flags. */
739 if (!PutLong(gz,time_stamp)) return gz->oError;
740 /* time stamp. */
741 /* Write deflated file to zip file */
742 gz->crc = updcrc (0, 0, &(gz->crcReg), gz->crc_32_tab);
743 bi_init(gz);
744 ct_init(gz);
745 if (!lm_init(gz,&deflate_flags)) return gz->iError; /* Read error. */
746 if (!PutByte(gz,(unsigned)deflate_flags)) return gz->oError;
747 /* extra flags. */
748 if (!PutByte(gz,(unsigned)OS_CODE)) return gz->oError;
749 /* OS identifier. */
750 if (!sX(deflate(gz),&pStatus)) return pStatus;
751 /* Write the crc and uncompressed size */
752 if (!PutLong(gz,gz->crc)) return gz->oError;
753 if (!PutLong(gz,(ulg)gz->bytes_in)) return gz->oError;
754 if (!flush_outbuf(gz)) return gz->oError; /* Write error. */
755 *oSize = (OFF_T) gz->bytes_out;
756 freeZip (gz);
757 return pStatus;
758 }
759
760 /******************************************************************************
761 * initZip.
762 * Returns as soon as an error occurs. Any memory allocated will be freed
763 * by the calling routine.
764 ******************************************************************************/
765
initZip(iFp,oFp,iSize,level,iError,oError)766 static GZp initZip (iFp, oFp, iSize, level, iError, oError)
767 vFILE *iFp;
768 vFILE *oFp;
769 OFF_T iSize;
770 Int32 level;
771 CDFstatus iError;
772 CDFstatus oError;
773 {
774 GZp gz = (GZp) CallocateMemory ((size_t) 1, sizeof(GZ), NULL);
775 if (gz == NULL) return NULL;
776 gz->inbuf = (uch *) CallocateMemory ((size_t) (INBUFSIZ+INBUF_EXTRA),
777 sizeof(uch), NULL);
778 if (gz->inbuf == NULL) return NULL;
779 gz->outbuf = (uch *) CallocateMemory ((size_t) (OUTBUFSIZ+OUTBUF_EXTRA),
780 sizeof(uch), NULL);
781 if (gz->outbuf == NULL) return NULL;
782 gz->d_buf = (ush *) CallocateMemory ((size_t) (DIST_BUFSIZE),
783 sizeof(ush), NULL);
784 if (gz->d_buf == NULL) return NULL;
785 gz->window = (uch *) CallocateMemory ((size_t) (2L*WSIZE),
786 sizeof(uch), NULL);
787 if (gz->window == NULL) return NULL;
788 gz->prev = (ush *) CallocateMemory ((size_t) (1L<<(BITSx-1)),
789 sizeof(ush), NULL);
790 if (gz->prev == NULL) return NULL;
791 gz->head = (ush *) CallocateMemory ((size_t) (1L<<(BITSx-1)),
792 sizeof(ush), NULL);
793 if (gz->head == NULL) return NULL;
794
795 gz->iFp = iFp;
796 gz->oFp = oFp;
797 gz->ifile_size = iSize;
798 gz->level = (int) level;
799 gz->outcnt = 0;
800 gz->bytes_in = 0;
801 gz->bytes_out = 0;
802 gz->crcReg = (ulg) 0xffffffffL;
803 gz->iError = iError;
804 gz->oError = oError;
805
806 gz->configuration_table[0].good_length = 0;
807 gz->configuration_table[0].max_lazy = 0;
808 gz->configuration_table[0].nice_length = 0;
809 gz->configuration_table[0].max_chain = 0;
810 gz->configuration_table[1].good_length = 4;
811 gz->configuration_table[1].max_lazy = 4;
812 gz->configuration_table[1].nice_length = 8;
813 gz->configuration_table[1].max_chain = 4;
814 gz->configuration_table[2].good_length = 4;
815 gz->configuration_table[2].max_lazy = 5;
816 gz->configuration_table[2].nice_length = 16;
817 gz->configuration_table[2].max_chain = 8;
818 gz->configuration_table[3].good_length = 4;
819 gz->configuration_table[3].max_lazy = 6;
820 gz->configuration_table[3].nice_length = 32;
821 gz->configuration_table[3].max_chain = 32;
822 gz->configuration_table[4].good_length = 4;
823 gz->configuration_table[4].max_lazy = 4;
824 gz->configuration_table[4].nice_length = 16;
825 gz->configuration_table[4].max_chain = 16;
826 gz->configuration_table[5].good_length = 8;
827 gz->configuration_table[5].max_lazy = 16;
828 gz->configuration_table[5].nice_length = 32;
829 gz->configuration_table[5].max_chain = 32;
830 gz->configuration_table[6].good_length = 8;
831 gz->configuration_table[6].max_lazy = 16;
832 gz->configuration_table[6].nice_length = 128;
833 gz->configuration_table[6].max_chain = 128;
834 gz->configuration_table[7].good_length = 8;
835 gz->configuration_table[7].max_lazy = 32;
836 gz->configuration_table[7].nice_length = 128;
837 gz->configuration_table[7].max_chain = 256;
838 gz->configuration_table[8].good_length = 32;
839 gz->configuration_table[8].max_lazy = 128;
840 gz->configuration_table[8].nice_length = 258;
841 gz->configuration_table[8].max_chain = 1024;
842 gz->configuration_table[9].good_length = 32;
843 gz->configuration_table[9].max_lazy = 258;
844 gz->configuration_table[9].nice_length = 258;
845 gz->configuration_table[9].max_chain = 4096;
846
847 gz->bl_order[0] = 16;
848 gz->bl_order[1] = 17;
849 gz->bl_order[2] = 18;
850 gz->bl_order[3] = 0;
851 gz->bl_order[4] = 8;
852 gz->bl_order[5] = 7;
853 gz->bl_order[6] = 9;
854 gz->bl_order[7] = 6;
855 gz->bl_order[8] = 10;
856 gz->bl_order[9] = 5;
857 gz->bl_order[10] = 11;
858 gz->bl_order[11] = 4;
859 gz->bl_order[12] = 12;
860 gz->bl_order[13] = 3;
861 gz->bl_order[14] = 13;
862 gz->bl_order[15] = 2;
863 gz->bl_order[16] = 14;
864 gz->bl_order[17] = 1;
865 gz->bl_order[18] = 15;
866
867 gz->extra_lbits[0] = 0;
868 gz->extra_lbits[1] = 0;
869 gz->extra_lbits[2] = 0;
870 gz->extra_lbits[3] = 0;
871 gz->extra_lbits[4] = 0;
872 gz->extra_lbits[5] = 0;
873 gz->extra_lbits[6] = 0;
874 gz->extra_lbits[7] = 0;
875 gz->extra_lbits[8] = 1;
876 gz->extra_lbits[9] = 1;
877 gz->extra_lbits[10] = 1;
878 gz->extra_lbits[11] = 1;
879 gz->extra_lbits[12] = 2;
880 gz->extra_lbits[13] = 2;
881 gz->extra_lbits[14] = 2;
882 gz->extra_lbits[15] = 2;
883 gz->extra_lbits[16] = 3;
884 gz->extra_lbits[17] = 3;
885 gz->extra_lbits[18] = 3;
886 gz->extra_lbits[19] = 3;
887 gz->extra_lbits[20] = 4;
888 gz->extra_lbits[21] = 4;
889 gz->extra_lbits[22] = 4;
890 gz->extra_lbits[23] = 4;
891 gz->extra_lbits[24] = 5;
892 gz->extra_lbits[25] = 5;
893 gz->extra_lbits[26] = 5;
894 gz->extra_lbits[27] = 5;
895 gz->extra_lbits[28] = 0;
896
897 gz->extra_dbits[0] = 0;
898 gz->extra_dbits[1] = 0;
899 gz->extra_dbits[2] = 0;
900 gz->extra_dbits[3] = 0;
901 gz->extra_dbits[4] = 1;
902 gz->extra_dbits[5] = 1;
903 gz->extra_dbits[6] = 2;
904 gz->extra_dbits[7] = 2;
905 gz->extra_dbits[8] = 3;
906 gz->extra_dbits[9] = 3;
907 gz->extra_dbits[10] = 4;
908 gz->extra_dbits[11] = 4;
909 gz->extra_dbits[12] = 5;
910 gz->extra_dbits[13] = 5;
911 gz->extra_dbits[14] = 6;
912 gz->extra_dbits[15] = 6;
913 gz->extra_dbits[16] = 7;
914 gz->extra_dbits[17] = 7;
915 gz->extra_dbits[18] = 8;
916 gz->extra_dbits[19] = 8;
917 gz->extra_dbits[20] = 9;
918 gz->extra_dbits[21] = 9;
919 gz->extra_dbits[22] = 10;
920 gz->extra_dbits[23] = 10;
921 gz->extra_dbits[24] = 11;
922 gz->extra_dbits[25] = 11;
923 gz->extra_dbits[26] = 12;
924 gz->extra_dbits[27] = 12;
925 gz->extra_dbits[28] = 13;
926 gz->extra_dbits[29] = 13;
927
928 gz->extra_blbits[0] = 0;
929 gz->extra_blbits[1] = 0;
930 gz->extra_blbits[2] = 0;
931 gz->extra_blbits[3] = 0;
932 gz->extra_blbits[4] = 0;
933 gz->extra_blbits[5] = 0;
934 gz->extra_blbits[6] = 0;
935 gz->extra_blbits[7] = 0;
936 gz->extra_blbits[8] = 0;
937 gz->extra_blbits[9] = 0;
938 gz->extra_blbits[10] = 0;
939 gz->extra_blbits[11] = 0;
940 gz->extra_blbits[12] = 0;
941 gz->extra_blbits[13] = 0;
942 gz->extra_blbits[14] = 0;
943 gz->extra_blbits[15] = 0;
944 gz->extra_blbits[16] = 2;
945 gz->extra_blbits[17] = 3;
946 gz->extra_blbits[18] = 7;
947
948 gz->l_desc.dyn_tree = gz->dyn_ltree;
949 gz->l_desc.static_tree = gz->static_ltree;
950 gz->l_desc.extra_bits = gz->extra_lbits;
951 gz->l_desc.extra_base = LITERALS+1;
952 gz->l_desc.elems = L_CODES;
953 gz->l_desc.max_length = MAX_BITS;
954 gz->l_desc.max_code = 0;
955
956 gz->d_desc.dyn_tree = gz->dyn_dtree;
957 gz->d_desc.static_tree = gz->static_dtree;
958 gz->d_desc.extra_bits = gz->extra_dbits;
959 gz->d_desc.extra_base = 0;
960 gz->d_desc.elems = D_CODES;
961 gz->d_desc.max_length = MAX_BITS;
962 gz->d_desc.max_code = 0;
963
964 gz->bl_desc.dyn_tree = gz->bl_tree;
965 gz->bl_desc.static_tree = NULL;
966 gz->bl_desc.extra_bits = gz->extra_blbits;
967 gz->bl_desc.extra_base = 0;
968 gz->bl_desc.elems = BL_CODES;
969 gz->bl_desc.max_length = MAX_BL_BITS;
970 gz->bl_desc.max_code = 0;
971
972 initCRC (gz->crc_32_tab);
973
974 return gz;
975 }
976
977 /******************************************************************************
978 * freeZip.
979 ******************************************************************************/
980
freeZip(gz)981 static void freeZip (gz)
982 GZp gz;
983 {
984 cdf_FreeMemory (gz->head, NULL);
985 cdf_FreeMemory (gz->prev, NULL);
986 cdf_FreeMemory (gz->window, NULL);
987 cdf_FreeMemory (gz->d_buf, NULL);
988 cdf_FreeMemory (gz->outbuf, NULL);
989 cdf_FreeMemory (gz->inbuf, NULL);
990 cdf_FreeMemory (gz, NULL);
991 return;
992 }
993
994 /******************************************************************************
995 * unzip.
996 * Returns as soon as an error occurs. Any memory allocated will be freed
997 * by the calling routine. If successful, this routine frees the memory.
998 ******************************************************************************/
999
1000 /* unzip.c -- decompress files in gzip or pkzip format.
1001 * Copyright (C) 1992-1993 Jean-loup Gailly
1002 * This is free software; you can redistribute it and/or modify it under the
1003 * terms of the GNU General Public License, see the file COPYING.
1004 *
1005 * The code in this file is derived from the file funzip.c written
1006 * and put in the public domain by Mark Adler.
1007 */
1008
1009 /*
1010 This version can extract files in gzip or pkzip format.
1011 For the latter, only the first entry is extracted, and it has to be
1012 either deflated or stored.
1013 */
1014
1015 /* ===========================================================================
1016 * Unzip in to out. This routine works on both gzip and pkzip files.
1017 *
1018 * IN assertions: the buffer inbuf contains already the beginning of
1019 * the compressed data, from offsets inptr to insize-1 included.
1020 * The magic header has already been checked. The output buffer is cleared.
1021 */
1022
unzip(iFp,oFp,iError,oError)1023 static CDFstatus unzip (iFp, oFp, iError, oError)
1024 vFILE *iFp;
1025 vFILE *oFp;
1026 CDFstatus iError;
1027 CDFstatus oError;
1028 {
1029 ulg orig_crc = 0; /* original crc */
1030 ulg orig_len = 0; /* original uncompressed length */
1031 int n; uch buf[8], byte;
1032 /* uch flags1; */ /* compression flags */
1033 /* char magic[2]; */ /* magic header */
1034 /* ulg stamp; */ /* time stamp */
1035 int method; GUp gu;
1036 gu = initUnZip (iFp, oFp, iError, oError);
1037 if (gu == NULL) return BAD_MALLOC;
1038 if (!GetByte(gu,&byte)) return gu->iError; /* magic[0]. */
1039 if (!GetByte(gu,&byte)) return gu->iError; /* magic[1]. */
1040 if (!GetByte(gu,&byte)) return gu->iError; /* method. */
1041 method = (int) byte;
1042 if (!GetByte(gu,&byte)) return gu->iError; /* flags1. */
1043 if (!GetByte(gu,&byte)) return gu->iError; /* stamp[0]. */
1044 if (!GetByte(gu,&byte)) return gu->iError; /* stamp[1]. */
1045 if (!GetByte(gu,&byte)) return gu->iError; /* stamp[2]. */
1046 if (!GetByte(gu,&byte)) return gu->iError; /* stamp[3]. */
1047 if (!GetByte(gu,&byte)) return gu->iError; /* "extra flags". */
1048 if (!GetByte(gu,&byte)) return gu->iError; /* "OS type". */
1049 updcrc (NULL, 0, &(gu->crcReg), gu->crc_32_tab); /* initialize crc */
1050 /* Decompress */
1051 if (method == DEFLATED) {
1052 switch (inflate(gu)) {
1053 case 0:
1054 break; /* Success. */
1055 case 1:
1056 case 2:
1057 return DECOMPRESSION_ERROR;
1058 case 3:
1059 return BAD_MALLOC;
1060 case 4:
1061 return gu->iError; /* Read error. */
1062 case 5:
1063 return gu->oError; /* Write error. */
1064 default:
1065 return CDF_INTERNAL_ERROR; /* ??? */
1066 }
1067 }
1068 else {
1069 /* error("internal error, invalid method"); */
1070 return DECOMPRESSION_ERROR;
1071 }
1072 /* Get the crc and original length */
1073 /* crc32 (see algorithm.doc)
1074 * uncompressed input size modulo 2^32
1075 */
1076 for (n = 0; n < 8; n++) {
1077 if (!GetByte(gu,&byte)) return gu->iError;
1078 buf[n] = (uch) byte;
1079 }
1080 orig_crc = LG(buf);
1081 orig_len = LG(buf+4);
1082 /* Validate decompression */
1083 if (orig_crc != updcrc(gu->window,0,&(gu->crcReg),gu->crc_32_tab)) {
1084 /* JTL: outbuf --> window */
1085 /* error("invalid compressed data--crc error"); */
1086 return DECOMPRESSION_ERROR;
1087 }
1088 if (orig_len != (ulg)(gu->bytes_out & 0xffffffff)) {
1089 /* error("invalid compressed data--length error"); */
1090 return DECOMPRESSION_ERROR;
1091 }
1092 freeUnZip (gu);
1093 return CDF_OK;
1094 }
1095
1096 /******************************************************************************
1097 * initUnZip.
1098 * Returns as soon as an error occurs. Any memory allocated will be freed
1099 * by the calling routine.
1100 ******************************************************************************/
1101
initUnZip(iFp,oFp,iError,oError)1102 static GUp initUnZip (iFp, oFp, iError, oError)
1103 vFILE *iFp;
1104 vFILE *oFp;
1105 CDFstatus iError;
1106 CDFstatus oError;
1107 {
1108 GUp gu = (GUp) CallocateMemory ((size_t) 1, sizeof(GU), NULL);
1109 if (gu == NULL) return NULL;
1110 gu->inbuf = (uch *) CallocateMemory ((size_t) (INBUFSIZ+INBUF_EXTRA),
1111 sizeof(uch), NULL);
1112 if (gu->inbuf == NULL) return NULL;
1113 gu->window = (uch *) CallocateMemory ((size_t) (2L*WSIZE), sizeof(uch),
1114 NULL);
1115 if (gu->window == NULL) return NULL;
1116
1117 gu->iFp = iFp;
1118 gu->oFp = oFp;
1119 gu->iError = iError;
1120 gu->oError = oError;
1121 gu->outcnt = 0;
1122 gu->bytes_in = 0;
1123 gu->bytes_out = 0;
1124 gu->insize = 0;
1125 gu->inptr = 0;
1126 gu->crcReg = (ulg) 0xffffffffL;
1127
1128 gu->border[0] = 16;
1129 gu->border[1] = 17;
1130 gu->border[2] = 18;
1131 gu->border[3] = 0;
1132 gu->border[4] = 8;
1133 gu->border[5] = 7;
1134 gu->border[6] = 9;
1135 gu->border[7] = 6;
1136 gu->border[8] = 10;
1137 gu->border[9] = 5;
1138 gu->border[10] = 11;
1139 gu->border[11] = 4;
1140 gu->border[12] = 12;
1141 gu->border[13] = 3;
1142 gu->border[14] = 13;
1143 gu->border[15] = 2;
1144 gu->border[16] = 14;
1145 gu->border[17] = 1;
1146 gu->border[18] = 15;
1147
1148 gu->cplens[0] = 3;
1149 gu->cplens[1] = 4;
1150 gu->cplens[2] = 5;
1151 gu->cplens[3] = 6;
1152 gu->cplens[4] = 7;
1153 gu->cplens[5] = 8;
1154 gu->cplens[6] = 9;
1155 gu->cplens[7] = 10;
1156 gu->cplens[8] = 11;
1157 gu->cplens[9] = 13;
1158 gu->cplens[10] = 15;
1159 gu->cplens[11] = 17;
1160 gu->cplens[12] = 19;
1161 gu->cplens[13] = 23;
1162 gu->cplens[14] = 27;
1163 gu->cplens[15] = 31;
1164 gu->cplens[16] = 35;
1165 gu->cplens[17] = 43;
1166 gu->cplens[18] = 51;
1167 gu->cplens[19] = 59;
1168 gu->cplens[20] = 67;
1169 gu->cplens[21] = 83;
1170 gu->cplens[22] = 99;
1171 gu->cplens[23] = 115;
1172 gu->cplens[24] = 131;
1173 gu->cplens[25] = 163;
1174 gu->cplens[26] = 195;
1175 gu->cplens[27] = 227;
1176 gu->cplens[28] = 258;
1177 gu->cplens[29] = 0;
1178 gu->cplens[30] = 0;
1179
1180 gu->cplext[0] = 0;
1181 gu->cplext[1] = 0;
1182 gu->cplext[2] = 0;
1183 gu->cplext[3] = 0;
1184 gu->cplext[4] = 0;
1185 gu->cplext[5] = 0;
1186 gu->cplext[6] = 0;
1187 gu->cplext[7] = 0;
1188 gu->cplext[8] = 1;
1189 gu->cplext[9] = 1;
1190 gu->cplext[10] = 1;
1191 gu->cplext[11] = 1;
1192 gu->cplext[12] = 2;
1193 gu->cplext[13] = 2;
1194 gu->cplext[14] = 2;
1195 gu->cplext[15] = 2;
1196 gu->cplext[16] = 3;
1197 gu->cplext[17] = 3;
1198 gu->cplext[18] = 3;
1199 gu->cplext[19] = 3;
1200 gu->cplext[20] = 4;
1201 gu->cplext[21] = 4;
1202 gu->cplext[22] = 4;
1203 gu->cplext[23] = 4;
1204 gu->cplext[24] = 5;
1205 gu->cplext[25] = 5;
1206 gu->cplext[26] = 5;
1207 gu->cplext[27] = 5;
1208 gu->cplext[28] = 0;
1209 gu->cplext[29] = 99;
1210 gu->cplext[30] = 99;
1211
1212 gu->cpdist[0] = 1;
1213 gu->cpdist[1] = 2;
1214 gu->cpdist[2] = 3;
1215 gu->cpdist[3] = 4;
1216 gu->cpdist[4] = 5;
1217 gu->cpdist[5] = 7;
1218 gu->cpdist[6] = 9;
1219 gu->cpdist[7] = 13;
1220 gu->cpdist[8] = 17;
1221 gu->cpdist[9] = 25;
1222 gu->cpdist[10] = 33;
1223 gu->cpdist[11] = 49;
1224 gu->cpdist[12] = 65;
1225 gu->cpdist[13] = 97;
1226 gu->cpdist[14] = 129;
1227 gu->cpdist[15] = 193;
1228 gu->cpdist[16] = 257;
1229 gu->cpdist[17] = 385;
1230 gu->cpdist[18] = 513;
1231 gu->cpdist[19] = 769;
1232 gu->cpdist[20] = 1025;
1233 gu->cpdist[21] = 1537;
1234 gu->cpdist[22] = 2049;
1235 gu->cpdist[23] = 3073;
1236 gu->cpdist[24] = 4097;
1237 gu->cpdist[25] = 6145;
1238 gu->cpdist[26] = 8193;
1239 gu->cpdist[27] = 12289;
1240 gu->cpdist[28] = 16385;
1241 gu->cpdist[29] = 24577;
1242
1243 gu->cpdext[0] = 0;
1244 gu->cpdext[1] = 0;
1245 gu->cpdext[2] = 0;
1246 gu->cpdext[3] = 0;
1247 gu->cpdext[4] = 1;
1248 gu->cpdext[5] = 1;
1249 gu->cpdext[6] = 2;
1250 gu->cpdext[7] = 2;
1251 gu->cpdext[8] = 3;
1252 gu->cpdext[9] = 3;
1253 gu->cpdext[10] = 4;
1254 gu->cpdext[11] = 4;
1255 gu->cpdext[12] = 5;
1256 gu->cpdext[13] = 5;
1257 gu->cpdext[14] = 6;
1258 gu->cpdext[15] = 6;
1259 gu->cpdext[16] = 7;
1260 gu->cpdext[17] = 7;
1261 gu->cpdext[18] = 8;
1262 gu->cpdext[19] = 8;
1263 gu->cpdext[20] = 9;
1264 gu->cpdext[21] = 9;
1265 gu->cpdext[22] = 10;
1266 gu->cpdext[23] = 10;
1267 gu->cpdext[24] = 11;
1268 gu->cpdext[25] = 11;
1269 gu->cpdext[26] = 12;
1270 gu->cpdext[27] = 12;
1271 gu->cpdext[28] = 13;
1272 gu->cpdext[29] = 13;
1273
1274 gu->mask_bits[0] = 0x0000;
1275 gu->mask_bits[1] = 0x0001;
1276 gu->mask_bits[2] = 0x0003;
1277 gu->mask_bits[3] = 0x0007;
1278 gu->mask_bits[4] = 0x000f;
1279 gu->mask_bits[5] = 0x001f;
1280 gu->mask_bits[6] = 0x003f;
1281 gu->mask_bits[7] = 0x007f;
1282 gu->mask_bits[8] = 0x00ff;
1283 gu->mask_bits[9] = 0x01ff;
1284 gu->mask_bits[10] = 0x03ff;
1285 gu->mask_bits[11] = 0x07ff;
1286 gu->mask_bits[12] = 0x0fff;
1287 gu->mask_bits[13] = 0x1fff;
1288 gu->mask_bits[14] = 0x3fff;
1289 gu->mask_bits[15] = 0x7fff;
1290 gu->mask_bits[16] = 0xffff;
1291
1292 initCRC (gu->crc_32_tab);
1293
1294 return gu;
1295 }
1296
1297 /******************************************************************************
1298 * freeUnZip.
1299 ******************************************************************************/
1300
freeUnZip(gu)1301 static void freeUnZip (gu)
1302 GUp gu;
1303 {
1304 cdf_FreeMemory (gu->window, NULL);
1305 cdf_FreeMemory (gu->inbuf, NULL);
1306 cdf_FreeMemory (gu, NULL);
1307 return;
1308 }
1309
1310 /* ===========================================================================
1311 * Read a new buffer from the current input file, perform end-of-line
1312 * translation, and update the crc and input file size.
1313 * IN assertion: size >= 2 (for end-of-line translation)
1314 */
1315 /* Returns: >0 number of bytes read, - JTL...
1316 0 fake EOF,
1317 -1 error or real EOF.
1318 */
1319
file_read(gz,buf,size)1320 static int file_read(gz, buf, size)
1321 GZp gz;
1322 char *buf;
1323 unsigned size;
1324 {
1325 unsigned len;
1326 OFF_T remaining = gz->ifile_size - gz->bytes_in; /* JTL... */
1327 if (remaining == 0) return 0; /* Fake `EOF'. */
1328 size = (unsigned) MINIMUM64(size,remaining); /* ...JTL */
1329 len = (unsigned) V_read64 (buf, (size_t) 1, (size_t) size, gz->iFp);
1330 if (len == 0) return (int)(-1); /* V_read returns 0 if an error. */
1331 gz->crc = updcrc ((uch*) buf, len, &(gz->crcReg), gz->crc_32_tab);
1332 gz->bytes_in += (ulg)len;
1333 return (int)len;
1334 }
1335
1336
1337
1338 /* bits.c -- output variable-length bit strings
1339 * Copyright (C) 1992-1993 Jean-loup Gailly
1340 * This is free software; you can redistribute it and/or modify it under the
1341 * terms of the GNU General Public License, see the file COPYING.
1342 */
1343
1344
1345 /*
1346 * PURPOSE
1347 *
1348 * Output variable-length bit strings. Compression can be done
1349 * to a file or to memory. (The latter is not supported in this version.)
1350 *
1351 * DISCUSSION
1352 *
1353 * The PKZIP "deflate" file format interprets compressed file data
1354 * as a sequence of bits. Multi-bit strings in the file may cross
1355 * byte boundaries without restriction.
1356 *
1357 * The first bit of each byte is the low-order bit.
1358 *
1359 * The routines in this file allow a variable-length bit value to
1360 * be output right-to-left (useful for literal values). For
1361 * left-to-right output (useful for code strings from the tree routines),
1362 * the bits must have been reversed first with bi_reverse().
1363 *
1364 * For in-memory compression, the compressed bit stream goes directly
1365 * into the requested output buffer. The input data is read in blocks
1366 * by the mem_read() function. The buffer is limited to 64K on 16 bit
1367 * machines.
1368 *
1369 * INTERFACE
1370 *
1371 * void bi_init (GZp gz)
1372 * Initialize the bit string routines.
1373 *
1374 * Logical send_bits (GZp gz, int value, int length)
1375 * Write out a bit string, taking the source bits right to
1376 * left.
1377 *
1378 * int bi_reverse (int value, int length)
1379 * Reverse the bits of a bit string, taking the source bits left to
1380 * right and emitting them right to left.
1381 *
1382 * Logical bi_windup (GZp gz)
1383 * Write out any remaining bits in an incomplete byte.
1384 *
1385 * Logical copy_block(GZp gz, char *buf, unsigned len, int header)
1386 * Copy a stored block to the zip file, storing first the length and
1387 * its one's complement if requested.
1388 *
1389 */
1390
1391 /* ===========================================================================
1392 * Initialize the bit string routines.
1393 */
bi_init(gz)1394 static void bi_init (gz)
1395 GZp gz;
1396 {
1397 gz->bi_buf = 0;
1398 gz->bi_valid = 0;
1399 }
1400
1401 /* ===========================================================================
1402 * Send a value on a given number of bits.
1403 * IN assertion: length <= 16 and value fits in length bits.
1404 */
send_bits(gz,value,length)1405 static Logical send_bits(gz, value, length)
1406 GZp gz;
1407 int value; /* value to send */
1408 int length; /* number of bits */
1409 {
1410 /* If not enough room in bi_buf, use (valid) bits from bi_buf and
1411 * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))
1412 * unused bits in value.
1413 */
1414 if (gz->bi_valid > (int)BUF_SIZE - length) {
1415 gz->bi_buf |= (value << gz->bi_valid);
1416 if (!PutShort(gz,(unsigned)gz->bi_buf)) return FALSE;
1417 gz->bi_buf = (ush)value >> (BUF_SIZE - gz->bi_valid);
1418 gz->bi_valid += length - BUF_SIZE;
1419 } else {
1420 gz->bi_buf |= value << gz->bi_valid;
1421 gz->bi_valid += length;
1422 }
1423 return TRUE;
1424 }
1425
1426 /* ===========================================================================
1427 * Reverse the first len bits of a code, using straightforward code (a faster
1428 * method would use a table)
1429 * IN assertion: 1 <= len <= 15
1430 */
bi_reverse(code,len)1431 static unsigned bi_reverse(code, len)
1432 unsigned code; /* the value to invert */
1433 int len; /* its bit length */
1434 {
1435 register unsigned res = 0;
1436 do {
1437 res |= code & 1;
1438 code >>= 1, res <<= 1;
1439 } while (--len > 0);
1440 return res >> 1;
1441 }
1442
1443 /* ===========================================================================
1444 * Write out any remaining bits in an incomplete byte.
1445 */
bi_windup(gz)1446 static Logical bi_windup(gz)
1447 GZp gz;
1448 {
1449 if (gz->bi_valid > 8) {
1450 if (!PutShort(gz,(unsigned)gz->bi_buf)) return FALSE;
1451 } else if (gz->bi_valid > 0) {
1452 if (!PutByte(gz,(unsigned)gz->bi_buf)) return FALSE;
1453 }
1454 gz->bi_buf = 0;
1455 gz->bi_valid = 0;
1456 return TRUE;
1457 }
1458
1459 /* ===========================================================================
1460 * Copy a stored block to the zip file, storing first the length and its
1461 * one's complement if requested.
1462 */
copy_block(gz,buf,len,header)1463 static Logical copy_block(gz, buf, len, header)
1464 GZp gz;
1465 char *buf; /* the input data */
1466 unsigned len; /* its length */
1467 int header; /* true if block header must be written */
1468 {
1469 if (!bi_windup(gz)) return FALSE; /* align on byte boundary */
1470 if (header) {
1471 if (!PutShort(gz,(unsigned)len)) return FALSE;
1472 if (!PutShort(gz,(unsigned)~len)) return FALSE;
1473 }
1474 while (len--) {
1475 if (!PutByte(gz,(unsigned)*buf++)) return FALSE;
1476 }
1477 return TRUE;
1478 }
1479
1480
1481 /* deflate.c -- compress data using the deflation algorithm
1482 * Copyright (C) 1992-1993 Jean-loup Gailly
1483 * This is free software; you can redistribute it and/or modify it under the
1484 * terms of the GNU General Public License, see the file COPYING.
1485 */
1486
1487 /*
1488 * PURPOSE
1489 *
1490 * Identify new text as repetitions of old text within a fixed-
1491 * length sliding window trailing behind the new text.
1492 *
1493 * DISCUSSION
1494 *
1495 * The "deflation" process depends on being able to identify portions
1496 * of the input text which are identical to earlier input (within a
1497 * sliding window trailing behind the input currently being processed).
1498 *
1499 * The most straightforward technique turns out to be the fastest for
1500 * most input files: try all possible matches and select the longest.
1501 * The key feature of this algorithm is that insertions into the string
1502 * dictionary are very simple and thus fast, and deletions are avoided
1503 * completely. Insertions are performed at each input character, whereas
1504 * string matches are performed only when the previous match ends. So it
1505 * is preferable to spend more time in matches to allow very fast string
1506 * insertions and avoid deletions. The matching algorithm for small
1507 * strings is inspired from that of Rabin & Karp. A brute force approach
1508 * is used to find longer strings when a small match has been found.
1509 * A similar algorithm is used in comic (by Jan-Mark Wams) and freeze
1510 * (by Leonid Broukhis).
1511 * A previous version of this file used a more sophisticated algorithm
1512 * (by Fiala and Greene) which is guaranteed to run in linear amortized
1513 * time, but has a larger average cost, uses more memory and is patented.
1514 * However the F&G algorithm may be faster for some highly redundant
1515 * files if the parameter max_chain_length (described below) is too large.
1516 *
1517 * ACKNOWLEDGEMENTS
1518 *
1519 * The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
1520 * I found it in 'freeze' written by Leonid Broukhis.
1521 * Thanks to many info-zippers for bug reports and testing.
1522 *
1523 * REFERENCES
1524 *
1525 * APPNOTE.TXT documentation file in PKZIP 1.93a distribution.
1526 *
1527 * A description of the Rabin and Karp algorithm is given in the book
1528 * "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
1529 *
1530 * Fiala,E.R., and Greene,D.H.
1531 * Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
1532 *
1533 * INTERFACE
1534 *
1535 * Logical lm_init (GZp gz, ush *flags)
1536 * Initialize the "longest match" routines for a new file
1537 *
1538 * ulg deflate (GZp gz)
1539 * Processes a new input file and return its compressed length. Sets
1540 * the compressed length, crc, deflate flags and internal file
1541 * attributes.
1542 */
1543
1544 /* ===========================================================================
1545 * Initialize the "longest match" routines for a new file
1546 */
lm_init(gz,flags)1547 static Logical lm_init (gz, flags)
1548 GZp gz;
1549 ush *flags; /* general purpose bit flag */
1550 {
1551 register unsigned j;
1552
1553 /* Initialize the hash table. */
1554 #if HASH_BITS == 15
1555 for (j = 0; j < HASH_SIZE; j++) gz->head[j] = NIL;
1556 #else
1557 memzero((char *)gz->head, HASH_SIZE * sizeof(*gz->head));
1558 #endif
1559 /* prev will be initialized on the fly */
1560
1561 /* Set the default configuration parameters:
1562 */
1563 if (gz->level == 1) {
1564 *flags |= FAST;
1565 } else if (gz->level == 9) {
1566 *flags |= SLOW;
1567 }
1568 /* ??? reduce max_chain_length for binary files */
1569
1570 gz->strstart = 0;
1571 gz->block_start = 0L;
1572
1573 gz->lookahead = file_read(gz, (char *) gz->window,
1574 sizeof(int) <= 2 ? (unsigned)WSIZE : 2*WSIZE);
1575 if (gz->lookahead == (unsigned)(-1)) {
1576 return FALSE; /* Error/real EOF shouldn't ever occur - JTL */
1577 }
1578 if (gz->lookahead == 0) {
1579 gz->eofile = 1, gz->lookahead = 0;
1580 return TRUE;
1581 }
1582 gz->eofile = 0;
1583 /* Make sure that we always have enough lookahead. This is important
1584 * if input comes from a device such as a tty.
1585 */
1586 while (gz->lookahead < MIN_LOOKAHEAD && !gz->eofile) {
1587 if (!fill_window(gz)) return FALSE;
1588 }
1589
1590 gz->ins_h = 0;
1591 for (j=0; j<MIN_MATCH-1; j++) {
1592 gz->ins_h = ((gz->ins_h << H_SHIFT) ^ gz->window[j]) & HASH_MASK;
1593 }
1594 /* If lookahead < MIN_MATCH, gz->ins_h is garbage, but this is
1595 * not important since only literal bytes will be emitted.
1596 */
1597 return TRUE;
1598 }
1599
1600 /* ===========================================================================
1601 * Set match_start to the longest match starting at the given string and
1602 * return its length. Matches shorter or equal to prev_length are discarded,
1603 * in which case the result is equal to prev_length and match_start is
1604 * garbage.
1605 * IN assertions: cur_match is the head of the hash chain for the current
1606 * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
1607 */
1608
longest_match(gz,cur_match)1609 static int longest_match(gz, cur_match)
1610 GZp gz;
1611 IPos cur_match; /* current match */
1612 {
1613 unsigned chain_length = gz->configuration_table[gz->level].max_chain;
1614 /* max hash chain length */
1615 register uch *scan = gz->window + gz->strstart; /* current string */
1616 register uch *match; /* matched string */
1617 register int len; /* length of current match */
1618 int best_len = gz->prev_length; /* best match length so far */
1619 IPos limit = gz->strstart > (IPos)MAX_DIST ? gz->strstart - (IPos)MAX_DIST : NIL;
1620 /* Stop when cur_match becomes <= limit. To simplify the code,
1621 * we prevent matches with the string of window index 0.
1622 */
1623
1624 /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
1625 * It is easy to get rid of this optimization if necessary.
1626 */
1627 #if HASH_BITS < 8 || MAX_MATCH != 258
1628 error: Code too clever
1629 #endif
1630
1631 #ifdef UNALIGNED_OK
1632 /* Compare two bytes at a time. Note: this is not always beneficial.
1633 * Try with and without -DUNALIGNED_OK to check.
1634 */
1635 register uch *strend = gz->window + gz->strstart + MAX_MATCH - 1;
1636 register ush scan_start = *(ush*)scan;
1637 register ush scan_end = *(ush*)(scan+best_len-1);
1638 #else
1639 register uch *strend = gz->window + gz->strstart + MAX_MATCH;
1640 register uch scan_end1 = scan[best_len-1];
1641 register uch scan_end = scan[best_len];
1642 #endif
1643
1644 /* Do not waste too much time if we already have a good match: */
1645 if (gz->prev_length >= gz->configuration_table[gz->level].good_length) {
1646 chain_length >>= 2;
1647 }
1648
1649 do {
1650 match = gz->window + cur_match;
1651
1652 /* Skip to next match if the match length cannot increase
1653 * or if the match length is less than 2:
1654 */
1655 #if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
1656 /* This code assumes sizeof(unsigned short) == 2. Do not use
1657 * UNALIGNED_OK if your compiler uses a different size.
1658 */
1659 if (*(ush*)(match+best_len-1) != scan_end ||
1660 *(ush*)match != scan_start) continue;
1661
1662 /* It is not necessary to compare scan[2] and match[2] since they are
1663 * always equal when the other bytes match, given that the hash keys
1664 * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at
1665 * strstart+3, +5, ... up to strstart+257. We check for insufficient
1666 * lookahead only every 4th comparison; the 128th check will be made
1667 * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is
1668 * necessary to put more guard bytes at the end of the window, or
1669 * to check more often for insufficient lookahead.
1670 */
1671 scan++, match++;
1672 do {
1673 } while (*(ush*)(scan+=2) == *(ush*)(match+=2) &&
1674 *(ush*)(scan+=2) == *(ush*)(match+=2) &&
1675 *(ush*)(scan+=2) == *(ush*)(match+=2) &&
1676 *(ush*)(scan+=2) == *(ush*)(match+=2) &&
1677 scan < strend);
1678 /* The funny "do {}" generates better code on most compilers */
1679
1680 /* Here, scan <= window+strstart+257 */
1681 if (*scan == *match) scan++;
1682
1683 len = (MAX_MATCH - 1) - (int)(strend-scan);
1684 scan = strend - (MAX_MATCH-1);
1685
1686 #else /* UNALIGNED_OK */
1687
1688 if (match[best_len] != scan_end ||
1689 match[best_len-1] != scan_end1 ||
1690 *match != *scan ||
1691 *++match != scan[1]) continue;
1692
1693 /* The check at best_len-1 can be removed because it will be made
1694 * again later. (This heuristic is not always a win.)
1695 * It is not necessary to compare scan[2] and match[2] since they
1696 * are always equal when the other bytes match, given that
1697 * the hash keys are equal and that HASH_BITS >= 8.
1698 */
1699 scan += 2, match++;
1700
1701 /* We check for insufficient lookahead only every 8th comparison;
1702 * the 256th check will be made at strstart+258.
1703 */
1704 do {
1705 } while (*++scan == *++match && *++scan == *++match &&
1706 *++scan == *++match && *++scan == *++match &&
1707 *++scan == *++match && *++scan == *++match &&
1708 *++scan == *++match && *++scan == *++match &&
1709 scan < strend);
1710
1711 len = MAX_MATCH - (int)(strend - scan);
1712 scan = strend - MAX_MATCH;
1713
1714 #endif /* UNALIGNED_OK */
1715
1716 if (len > best_len) {
1717 gz->match_start = cur_match;
1718 best_len = len;
1719 if (len >=
1720 (int) gz->configuration_table[gz->level].nice_length) break;
1721 #ifdef UNALIGNED_OK
1722 scan_end = *(ush*)(scan+best_len-1);
1723 #else
1724 scan_end1 = scan[best_len-1];
1725 scan_end = scan[best_len];
1726 #endif
1727 }
1728 } while ((cur_match = gz->prev[cur_match & WMASK]) > limit
1729 && --chain_length != 0);
1730
1731 return best_len;
1732 }
1733
1734 /* ===========================================================================
1735 * Fill the window when the lookahead becomes insufficient.
1736 * Updates strstart and lookahead, and sets eofile if end of input file.
1737 * IN assertion: lookahead < MIN_LOOKAHEAD && strstart + lookahead > 0
1738 * OUT assertions: at least one byte has been read, or eofile is set;
1739 * file reads are performed for at least two bytes (required for the
1740 * translate_eol option).
1741 */
fill_window(gz)1742 static Logical fill_window(gz)
1743 GZp gz;
1744 {
1745 register unsigned n, m;
1746 unsigned more = (unsigned)(WINDOW_SIZE - (ulg)gz->lookahead - (ulg)gz->strstart);
1747 /* Amount of free space at the end of the window. */
1748
1749 /* If the window is almost full and there is insufficient lookahead,
1750 * move the upper half to the lower one to make room in the upper half.
1751 */
1752 if (more == (unsigned)EOF) {
1753 /* Very unlikely, but possible on 16 bit machine if strstart == 0
1754 * and lookahead == 1 (input done one byte at time)
1755 */
1756 more--;
1757 } else if (gz->strstart >= WSIZE+MAX_DIST) {
1758 /* By the IN assertion, the window is not empty so we can't confuse
1759 * more == 0 with more == 64K on a 16 bit machine.
1760 */
1761 memcpy((char*)gz->window, (char*)gz->window+WSIZE, (unsigned)WSIZE);
1762 gz->match_start -= WSIZE;
1763 gz->strstart -= WSIZE; /* we now have strstart >= MAX_DIST: */
1764 gz->block_start -= (OFF_T) WSIZE;
1765 for (n = 0; n < HASH_SIZE; n++) {
1766 m = gz->head[n];
1767 gz->head[n] = (Pos)(m >= WSIZE ? m-WSIZE : NIL);
1768 }
1769 for (n = 0; n < WSIZE; n++) {
1770 m = gz->prev[n];
1771 gz->prev[n] = (Pos)(m >= WSIZE ? m-WSIZE : NIL);
1772 /* If n is not on any hash chain, prev[n] is garbage but
1773 * its value will never be used.
1774 */
1775 }
1776 more += WSIZE;
1777 }
1778 /* At this point, more >= 2 */
1779 if (!gz->eofile) {
1780 n = file_read(gz, (char*)gz->window+gz->strstart+gz->lookahead, more);
1781 if (n == (unsigned)(-1)) {
1782 return FALSE; /* Error/real EOF should never occur - JTL */
1783 }
1784 if (n == 0) {
1785 gz->eofile = 1;
1786 }
1787 else {
1788 gz->lookahead += n;
1789 }
1790 }
1791 return TRUE;
1792 }
1793
1794 /* ===========================================================================
1795 * Processes a new input file and return its compressed length. This
1796 * function does not perform lazy evaluationof matches and inserts
1797 * new strings in the dictionary only for unmatched strings or for short
1798 * matches. It is used only for the fast compression options.
1799 */
deflate_fast(gz)1800 static CDFstatus deflate_fast(gz)
1801 GZp gz;
1802 {
1803 IPos hash_head; /* head of the hash chain */
1804 int flush; /* set if current block must be flushed */
1805 unsigned match_length = 0; /* length of best match */
1806
1807 gz->prev_length = MIN_MATCH-1;
1808 while (gz->lookahead != 0) {
1809 /* Insert the string window[strstart .. strstart+2] in the
1810 * dictionary, and set hash_head to the head of the hash chain:
1811 */
1812 gz->ins_h = ((gz->ins_h << H_SHIFT) ^ gz->window[(gz->strstart) + MIN_MATCH-1]) & HASH_MASK;
1813 gz->prev[(gz->strstart) & WMASK] = hash_head = gz->head[gz->ins_h];
1814 gz->head[gz->ins_h] = (gz->strstart);
1815
1816 /* Find the longest match, discarding those <= prev_length.
1817 * At this point we have always match_length < MIN_MATCH
1818 */
1819 if (hash_head != NIL && gz->strstart - hash_head <= MAX_DIST) {
1820 /* To simplify the code, we prevent matches with the string
1821 * of window index 0 (in particular we have to avoid a match
1822 * of the string with itself at the start of the input file).
1823 */
1824 match_length = longest_match (gz, hash_head);
1825 /* longest_match() sets match_start */
1826 if (match_length > gz->lookahead) match_length = gz->lookahead;
1827 }
1828 if (match_length >= MIN_MATCH) {
1829 flush = ct_tally (gz, gz->strstart - gz->match_start,
1830 match_length - MIN_MATCH);
1831 gz->lookahead -= match_length;
1832 /* Insert new strings in the hash table only if the match length
1833 * is not too large. This saves time but degrades compression.
1834 */
1835 if (match_length <= gz->configuration_table[gz->level].max_lazy) {
1836 match_length--; /* string at strstart already in hash table */
1837 do {
1838 gz->strstart++;
1839 gz->ins_h = ((gz->ins_h << H_SHIFT) ^ gz->window[(gz->strstart) +
1840 MIN_MATCH-1]) & HASH_MASK;
1841 gz->prev[(gz->strstart) & WMASK] = hash_head = gz->head[gz->ins_h];
1842 gz->head[gz->ins_h] = (gz->strstart);
1843
1844 /* strstart never exceeds WSIZE-MAX_MATCH, so there are
1845 * always MIN_MATCH bytes ahead. If lookahead < MIN_MATCH
1846 * these bytes are garbage, but it does not matter since
1847 * the next lookahead bytes will be emitted as literals.
1848 */
1849 } while (--match_length != 0);
1850 gz->strstart++;
1851 } else {
1852 gz->strstart += match_length;
1853 match_length = 0;
1854 gz->ins_h = gz->window[gz->strstart];
1855 gz->ins_h = ((gz->ins_h << H_SHIFT) ^ gz->window[gz->strstart+1]) & HASH_MASK;
1856 }
1857 } else {
1858 /* No match, output a literal byte */
1859 flush = ct_tally (gz, 0, gz->window[gz->strstart]);
1860 gz->lookahead--;
1861 gz->strstart++;
1862 }
1863 if (flush) {
1864 if (!flush_block(gz, gz->block_start >= 0L ?
1865 (char*) &(gz->window[(unsigned)gz->block_start]) :
1866 (char*) NULL,
1867 (OFF_T) gz->strstart - gz->block_start,
1868 0)) return gz->oError; /* Write error. */
1869 gz->block_start = gz->strstart;
1870 }
1871
1872 /* Make sure that we always have enough lookahead, except
1873 * at the end of the input file. We need MAX_MATCH bytes
1874 * for the next match, plus MIN_MATCH bytes to insert the
1875 * string following the next match.
1876 */
1877 while (gz->lookahead < MIN_LOOKAHEAD && !gz->eofile) {
1878 if (!fill_window(gz)) return gz->iError; /* Read error. */
1879 }
1880 }
1881 if (!flush_block(gz, gz->block_start >= 0L ?
1882 (char *) &(gz->window[(unsigned)gz->block_start]) :
1883 (char *) NULL,
1884 (OFF_T) gz->strstart - gz->block_start,
1885 1)) return gz->oError; /* Write error. */ /* eof */
1886 return CDF_OK;
1887 }
1888
1889 /* ===========================================================================
1890 * Same as above, but achieves better compression. We use a lazy
1891 * evaluation for matches: a match is finally adopted only if there is
1892 * no better match at the next window position.
1893 */
deflate(gz)1894 static CDFstatus deflate(gz)
1895 GZp gz;
1896 {
1897 IPos hash_head; /* head of hash chain */
1898 IPos prev_match; /* previous match */
1899 int flush; /* set if current block must be flushed */
1900 int match_available = 0; /* set if previous match exists */
1901 register unsigned match_length = MIN_MATCH-1; /* length of best match */
1902
1903 if (gz->level <= 3) return deflate_fast(gz); /* optimized for speed */
1904
1905 /* Process the input block. */
1906 while (gz->lookahead != 0) {
1907 /* Insert the string window[strstart .. strstart+2] in the
1908 * dictionary, and set hash_head to the head of the hash chain:
1909 */
1910 gz->ins_h = ((gz->ins_h << H_SHIFT) ^ gz->window[(gz->strstart) + MIN_MATCH-1]) &
1911 HASH_MASK;
1912 gz->prev[(gz->strstart) & WMASK] = hash_head = gz->head[gz->ins_h];
1913 gz->head[gz->ins_h] = (gz->strstart);
1914
1915 /* Find the longest match, discarding those <= prev_length.
1916 */
1917 gz->prev_length = match_length, prev_match = gz->match_start;
1918 match_length = MIN_MATCH-1;
1919
1920 if (hash_head != NIL &&
1921 gz->prev_length < gz->configuration_table[gz->level].max_lazy &&
1922 gz->strstart - hash_head <= MAX_DIST) {
1923 /* To simplify the code, we prevent matches with the string
1924 * of window index 0 (in particular we have to avoid a match
1925 * of the string with itself at the start of the input file).
1926 */
1927 match_length = longest_match (gz, hash_head);
1928 /* longest_match() sets match_start */
1929 if (match_length > gz->lookahead) match_length = gz->lookahead;
1930
1931 /* Ignore a length 3 match if it is too distant: */
1932 if (match_length == MIN_MATCH && gz->strstart-gz->match_start > TOO_FAR){
1933 /* If prev_match is also MIN_MATCH, match_start is garbage
1934 * but we will ignore the current match anyway.
1935 */
1936 match_length--;
1937 }
1938 }
1939 /* If there was a match at the previous step and the current
1940 * match is not better, output the previous match:
1941 */
1942 if (gz->prev_length >= MIN_MATCH && match_length <= gz->prev_length) {
1943 flush = ct_tally (gz, gz->strstart - 1 - prev_match,
1944 gz->prev_length - MIN_MATCH);
1945 /* Insert in hash table all strings up to the end of the match.
1946 * strstart-1 and strstart are already inserted.
1947 */
1948 gz->lookahead -= gz->prev_length-1;
1949 gz->prev_length -= 2;
1950 do {
1951 gz->strstart++;
1952 gz->ins_h = ((gz->ins_h << H_SHIFT) ^ gz->window[(gz->strstart) + MIN_MATCH-1]) & HASH_MASK;
1953 gz->prev[(gz->strstart) & WMASK] = hash_head = gz->head[gz->ins_h];
1954 gz->head[gz->ins_h] = (gz->strstart);
1955
1956 /* strstart never exceeds WSIZE-MAX_MATCH, so there are
1957 * always MIN_MATCH bytes ahead. If lookahead < MIN_MATCH
1958 * these bytes are garbage, but it does not matter since the
1959 * next lookahead bytes will always be emitted as literals.
1960 */
1961 } while (--gz->prev_length != 0);
1962 match_available = 0;
1963 match_length = MIN_MATCH-1;
1964 gz->strstart++;
1965 if (flush) {
1966 if (!flush_block(gz, gz->block_start >= 0L ?
1967 (char *) &(gz->window[(unsigned)gz->block_start]) :
1968 (char *) NULL, (OFF_T) gz->strstart - gz->block_start,
1969 0)) return gz->oError; /* Write error. */
1970 gz->block_start = gz->strstart;
1971 }
1972 } else if (match_available) {
1973 /* If there was no match at the previous position, output a
1974 * single literal. If there was a match but the current match
1975 * is longer, truncate the previous match to a single literal.
1976 */
1977 if (ct_tally (gz, 0, gz->window[gz->strstart-1])) {
1978 if (!flush_block(gz, gz->block_start >= 0L ?
1979 (char *) &(gz->window[(unsigned)gz->block_start]) :
1980 (char *) NULL, (OFF_T) gz->strstart - gz->block_start,
1981 0)) return gz->oError; /* Write error. */
1982 gz->block_start = gz->strstart;
1983 }
1984 gz->strstart++;
1985 gz->lookahead--;
1986 } else {
1987 /* There is no previous match to compare with, wait for
1988 * the next step to decide.
1989 */
1990 match_available = 1;
1991 gz->strstart++;
1992 gz->lookahead--;
1993 }
1994
1995 /* Make sure that we always have enough lookahead, except
1996 * at the end of the input file. We need MAX_MATCH bytes
1997 * for the next match, plus MIN_MATCH bytes to insert the
1998 * string following the next match.
1999 */
2000 while (gz->lookahead < MIN_LOOKAHEAD && !gz->eofile) {
2001 if (!fill_window(gz)) return gz->iError; /* Read error. */
2002 }
2003 }
2004 if (match_available) ct_tally (gz, 0, gz->window[gz->strstart-1]);
2005
2006 if (!flush_block(gz, gz->block_start >= 0L ?
2007 (char *) &(gz->window[(unsigned)gz->block_start]) :
2008 (char *) NULL,
2009 (OFF_T) gz->strstart - gz->block_start,
2010 1)) return gz->oError; /* Write error. */ /* eof */
2011 return CDF_OK;
2012 }
2013
2014
2015
2016 /* trees.c -- output deflated data using Huffman coding
2017 * Copyright (C) 1992-1993 Jean-loup Gailly
2018 * This is free software; you can redistribute it and/or modify it under the
2019 * terms of the GNU General Public License, see the file COPYING.
2020 */
2021
2022 /*
2023 * PURPOSE
2024 *
2025 * Encode various sets of source values using variable-length
2026 * binary code trees.
2027 *
2028 * DISCUSSION
2029 *
2030 * The PKZIP "deflation" process uses several Huffman trees. The more
2031 * common source values are represented by shorter bit sequences.
2032 *
2033 * Each code tree is stored in the ZIP file in a compressed form
2034 * which is itself a Huffman encoding of the lengths of
2035 * all the code strings (in ascending order by source values).
2036 * The actual code strings are reconstructed from the lengths in
2037 * the UNZIP process, as described in the "application note"
2038 * (APPNOTE.TXT) distributed as part of PKWARE's PKZIP program.
2039 *
2040 * REFERENCES
2041 *
2042 * Lynch, Thomas J.
2043 * Data Compression: Techniques and Applications, pp. 53-55.
2044 * Lifetime Learning Publications, 1985. ISBN 0-534-03418-7.
2045 *
2046 * Storer, James A.
2047 * Data Compression: Methods and Theory, pp. 49-50.
2048 * Computer Science Press, 1988. ISBN 0-7167-8156-5.
2049 *
2050 * Sedgewick, R.
2051 * Algorithms, p290.
2052 * Addison-Wesley, 1983. ISBN 0-201-06672-6.
2053 *
2054 * INTERFACE
2055 *
2056 * void ct_init (GZp gz)
2057 * Allocate the match buffer, initialize the various tables.
2058 *
2059 * void ct_tally (GZp gz, int dist, int lc);
2060 * Save the match info and tally the frequency counts.
2061 *
2062 * Logical flush_block (GZp gz, char *buf, OFF_T stored_len, int eof)
2063 * Determine the best encoding for the current block: dynamic trees,
2064 * static trees or store, and output the encoded block to the zip
2065 * file.
2066 *
2067 */
2068
2069 /* ===========================================================================
2070 * Allocate the match buffer and initialize the various tables.
2071 */
ct_init(gz)2072 static void ct_init(gz)
2073 GZp gz;
2074 {
2075 int n; /* iterates over tree elements */
2076 int bits; /* bit counter */
2077 int length; /* length value */
2078 int code; /* code value */
2079 int dist; /* distance index */
2080
2081 if (gz->static_dtree[0].dl.len != 0) return; /* ct_init already called */
2082
2083 /* Initialize the mapping length (0..255) -> length code (0..28) */
2084 length = 0;
2085 for (code = 0; code < LENGTH_CODES-1; code++) {
2086 gz->base_length[code] = length;
2087 for (n = 0; n < (1<<gz->extra_lbits[code]); n++) {
2088 gz->length_code[length++] = (uch)code;
2089 }
2090 }
2091 /* Note that the length 255 (match length 258) can be represented
2092 * in two different ways: code 284 + 5 bits or code 285, so we
2093 * overwrite length_code[255] to use the best encoding:
2094 */
2095 gz->length_code[length-1] = (uch)code;
2096
2097 /* Initialize the mapping dist (0..32K) -> dist code (0..29) */
2098 dist = 0;
2099 for (code = 0 ; code < 16; code++) {
2100 gz->base_dist[code] = dist;
2101 for (n = 0; n < (1<<gz->extra_dbits[code]); n++) {
2102 gz->dist_code[dist++] = (uch)code;
2103 }
2104 }
2105 dist >>= 7; /* from now on, all distances are divided by 128 */
2106 for ( ; code < D_CODES; code++) {
2107 gz->base_dist[code] = dist << 7;
2108 for (n = 0; n < (1<<(gz->extra_dbits[code]-7)); n++) {
2109 gz->dist_code[256 + dist++] = (uch)code;
2110 }
2111 }
2112
2113 /* Construct the codes of the static literal tree */
2114 for (bits = 0; bits <= MAX_BITS; bits++) gz->bl_count[bits] = 0;
2115 n = 0;
2116 while (n <= 143) gz->static_ltree[n++].dl.len = 8, gz->bl_count[8]++;
2117 while (n <= 255) gz->static_ltree[n++].dl.len = 9, gz->bl_count[9]++;
2118 while (n <= 279) gz->static_ltree[n++].dl.len = 7, gz->bl_count[7]++;
2119 while (n <= 287) gz->static_ltree[n++].dl.len = 8, gz->bl_count[8]++;
2120 /* Codes 286 and 287 do not exist, but we must include them in the
2121 * tree construction to get a canonical Huffman tree (longest code
2122 * all ones)
2123 */
2124 gen_codes(gz, (ct_data *)gz->static_ltree, L_CODES+1);
2125
2126 /* The static distance tree is trivial: */
2127 for (n = 0; n < D_CODES; n++) {
2128 gz->static_dtree[n].dl.len = 5;
2129 gz->static_dtree[n].fc.code = bi_reverse(n, 5);
2130 }
2131
2132 /* Initialize the first block of the first file: */
2133 init_block(gz);
2134 }
2135
2136 /* ===========================================================================
2137 * Initialize a new block.
2138 */
init_block(gz)2139 static void init_block(gz)
2140 GZp gz;
2141 {
2142 int n; /* iterates over tree elements */
2143
2144 /* Initialize the trees. */
2145 for (n = 0; n < L_CODES; n++) gz->dyn_ltree[n].fc.freq = 0;
2146 for (n = 0; n < D_CODES; n++) gz->dyn_dtree[n].fc.freq = 0;
2147 for (n = 0; n < BL_CODES; n++) gz->bl_tree[n].fc.freq = 0;
2148
2149 gz->dyn_ltree[END_BLOCK].fc.freq = 1;
2150 gz->opt_len = gz->static_len = 0L;
2151 gz->last_lit = gz->last_dist = gz->last_flags = 0;
2152 gz->tree_flags = 0; gz->flag_bit = 1;
2153 return;
2154 }
2155
2156 #define SMALLEST 1
2157 /* Index within the heap array of least frequent node in the Huffman tree */
2158
2159 /* ===========================================================================
2160 * Compares to subtrees, using the tree depth as tie breaker when
2161 * the subtrees have equal frequency. This minimizes the worst case length.
2162 */
2163 #define smaller(tree_, depth_, n_, m_) \
2164 (tree_[n_].fc.freq < tree_[m_].fc.freq || \
2165 (tree_[n_].fc.freq == tree_[m_].fc.freq && depth_[n_] <= depth_[m_]))
2166
2167 /* ===========================================================================
2168 * Restore the heap property by moving down the tree starting at node k,
2169 * exchanging a node with the smallest of its two sons if necessary, stopping
2170 * when the heap property is re-established (each father smaller than its
2171 * two sons).
2172 */
pqdownheap(gz,tree,k)2173 static void pqdownheap (gz, tree, k)
2174 GZp gz;
2175 ct_data *tree; /* the tree to restore */
2176 int k; /* node to move down */
2177 {
2178 int v = gz->heap[k];
2179 int j = k << 1; /* left son of k */
2180 while (j <= gz->heap_len) {
2181 /* Set j to the smallest of the two sons: */
2182 if (j < gz->heap_len && smaller(tree, gz->depth, gz->heap[j+1], gz->heap[j])) j++;
2183
2184 /* Exit if v is smaller than both sons */
2185 if (smaller(tree, gz->depth, v, gz->heap[j])) break;
2186
2187 /* Exchange v with the smallest son */
2188 gz->heap[k] = gz->heap[j]; k = j;
2189
2190 /* And continue down the tree, setting j to the left son of k */
2191 j <<= 1;
2192 }
2193 gz->heap[k] = v;
2194 return;
2195 }
2196
2197 /* ===========================================================================
2198 * Compute the optimal bit lengths for a tree and update the total bit length
2199 * for the current block.
2200 * IN assertion: the fields freq and dad are set, heap[heap_max] and
2201 * above are the tree nodes sorted by increasing frequency.
2202 * OUT assertions: the field len is set to the optimal bit length, the
2203 * array bl_count contains the frequencies for each bit length.
2204 * The length opt_len is updated; static_len is also updated if stree is
2205 * not null.
2206 */
gen_bitlen(gz,desc)2207 static void gen_bitlen(gz, desc)
2208 GZp gz;
2209 tree_desc *desc; /* the tree descriptor */
2210 {
2211 ct_data *tree = desc->dyn_tree;
2212 int *extra = desc->extra_bits;
2213 int base = desc->extra_base;
2214 int max_code = desc->max_code;
2215 int max_length = desc->max_length;
2216 ct_data *stree = desc->static_tree;
2217 int h; /* heap index */
2218 int n, m; /* iterate over the tree elements */
2219 int bits; /* bit length */
2220 int xbits; /* extra bits */
2221 ush f; /* frequency */
2222 int overflow = 0; /* number of elements with bit length too large */
2223
2224 for (bits = 0; bits <= MAX_BITS; bits++) gz->bl_count[bits] = 0;
2225
2226 /* In a first pass, compute the optimal bit lengths (which may
2227 * overflow in the case of the bit length tree).
2228 */
2229 tree[gz->heap[gz->heap_max]].dl.len = 0; /* root of the heap */
2230
2231 for (h = gz->heap_max+1; h < HEAP_SIZE; h++) {
2232 n = gz->heap[h];
2233 bits = tree[tree[n].dl.dad].dl.len + 1;
2234 if (bits > max_length) bits = max_length, overflow++;
2235 tree[n].dl.len = (ush)bits;
2236 /* We overwrite tree[n].dl.dad which is no longer needed */
2237
2238 if (n > max_code) continue; /* not a leaf node */
2239
2240 gz->bl_count[bits]++;
2241 xbits = 0;
2242 if (n >= base) xbits = extra[n-base];
2243 f = tree[n].fc.freq;
2244 gz->opt_len += (ulg)f * (bits + xbits);
2245 if (stree) gz->static_len += (ulg)f * (stree[n].dl.len + xbits);
2246 }
2247 if (overflow == 0) return;
2248
2249 /* Find the first bit length which could increase: */
2250 do {
2251 bits = max_length-1;
2252 while (gz->bl_count[bits] == 0) bits--;
2253 gz->bl_count[bits]--; /* move one leaf down the tree */
2254 gz->bl_count[bits+1] += 2; /* move one overflow item as its brother */
2255 gz->bl_count[max_length]--;
2256 /* The brother of the overflow item also moves one step up,
2257 * but this does not affect bl_count[max_length]
2258 */
2259 overflow -= 2;
2260 } while (overflow > 0);
2261
2262 /* Now recompute all bit lengths, scanning in increasing frequency.
2263 * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all
2264 * lengths instead of fixing only the wrong ones. This idea is taken
2265 * from 'ar' written by Haruhiko Okumura.)
2266 */
2267 for (bits = max_length; bits != 0; bits--) {
2268 n = gz->bl_count[bits];
2269 while (n != 0) {
2270 m = gz->heap[--h];
2271 if (m > max_code) continue;
2272 if (tree[m].dl.len != (unsigned) bits) {
2273 gz->opt_len += ((long)bits-(long)tree[m].dl.len) *
2274 (long)tree[m].fc.freq;
2275 tree[m].dl.len = (ush)bits;
2276 }
2277 n--;
2278 }
2279 }
2280 return;
2281 }
2282
2283 /* ===========================================================================
2284 * Generate the codes for a given tree and bit counts (which need not be
2285 * optimal).
2286 * IN assertion: the array bl_count contains the bit length statistics for
2287 * the given tree and the field len is set for all tree elements.
2288 * OUT assertion: the field code is set for all tree elements of non
2289 * zero code length.
2290 */
gen_codes(gz,tree,max_code)2291 static void gen_codes (gz, tree, max_code)
2292 GZp gz;
2293 ct_data *tree; /* the tree to decorate */
2294 int max_code; /* largest code with non zero frequency */
2295 {
2296 ush next_code[MAX_BITS+1]; /* next code value for each bit length */
2297 ush code = 0; /* running code value */
2298 int bits; /* bit index */
2299 int n; /* code index */
2300
2301 /* The distribution counts are first used to generate the code values
2302 * without bit reversal.
2303 */
2304 for (bits = 1; bits <= MAX_BITS; bits++) {
2305 next_code[bits] = code = (code + gz->bl_count[bits-1]) << 1;
2306 }
2307 /* Check that the bit counts in bl_count are consistent. The last code
2308 * must be all ones.
2309 */
2310
2311 for (n = 0; n <= max_code; n++) {
2312 int len = tree[n].dl.len;
2313 if (len == 0) continue;
2314 /* Now reverse the bits */
2315 tree[n].fc.code = bi_reverse(next_code[len]++, len);
2316 }
2317 return;
2318 }
2319
2320 /* ===========================================================================
2321 * Construct one Huffman tree and assigns the code bit strings and lengths.
2322 * Update the total bit length for the current block.
2323 * IN assertion: the field freq is set for all tree elements.
2324 * OUT assertions: the fields len and code are set to the optimal bit length
2325 * and corresponding code. The length opt_len is updated; static_len is
2326 * also updated if stree is not null. The field max_code is set.
2327 */
build_tree_gz(gz,desc)2328 static void build_tree_gz(gz, desc)
2329 GZp gz;
2330 tree_desc *desc; /* the tree descriptor */
2331 {
2332 ct_data *tree = desc->dyn_tree;
2333 ct_data *stree = desc->static_tree;
2334 int elems = desc->elems;
2335 int n, m; /* iterate over heap elements */
2336 int max_code = -1; /* largest code with non zero frequency */
2337 int node = elems; /* next internal node of the tree */
2338
2339 /* Construct the initial heap, with least frequent element in
2340 * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
2341 * heap[0] is not used.
2342 */
2343 gz->heap_len = 0, gz->heap_max = HEAP_SIZE;
2344
2345 for (n = 0; n < elems; n++) {
2346 if (tree[n].fc.freq != 0) {
2347 gz->heap[++gz->heap_len] = max_code = n;
2348 gz->depth[n] = 0;
2349 } else {
2350 tree[n].dl.len = 0;
2351 }
2352 }
2353
2354 /* The pkzip format requires that at least one distance code exists,
2355 * and that at least one bit should be sent even if there is only one
2356 * possible code. So to avoid special checks later on we force at least
2357 * two codes of non zero frequency.
2358 */
2359 while (gz->heap_len < 2) {
2360 int newX = gz->heap[++gz->heap_len] = (max_code < 2 ? ++max_code : 0);
2361 tree[newX].fc.freq = 1;
2362 gz->depth[newX] = 0;
2363 gz->opt_len--; if (stree) gz->static_len -= stree[newX].dl.len;
2364 /* newX is 0 or 1 so it does not have extra bits */
2365 }
2366 desc->max_code = max_code;
2367
2368 /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
2369 * establish sub-heaps of increasing lengths:
2370 */
2371 for (n = gz->heap_len/2; n >= 1; n--) pqdownheap (gz, tree, n);
2372
2373 /* Construct the Huffman tree by repeatedly combining the least two
2374 * frequent nodes.
2375 */
2376 do {
2377 n = gz->heap[SMALLEST];
2378 gz->heap[SMALLEST] = gz->heap[gz->heap_len--];
2379 pqdownheap (gz, tree, SMALLEST);
2380 /* n = node of least frequency */
2381 m = gz->heap[SMALLEST]; /* m = node of next least frequency */
2382
2383 gz->heap[--gz->heap_max] = n; /* keep the nodes sorted by frequency */
2384 gz->heap[--gz->heap_max] = m;
2385
2386 /* Create a new node father of n and m */
2387 tree[node].fc.freq = tree[n].fc.freq + tree[m].fc.freq;
2388 gz->depth[node] = (uch) (MAXIMUM(gz->depth[n],gz->depth[m]) + 1);
2389 tree[n].dl.dad = tree[m].dl.dad = (ush)node;
2390 /* and insert the new node in the heap */
2391 gz->heap[SMALLEST] = node++;
2392 pqdownheap (gz, tree, SMALLEST);
2393
2394 } while (gz->heap_len >= 2);
2395
2396 gz->heap[--gz->heap_max] = gz->heap[SMALLEST];
2397
2398 /* At this point, the fields freq and dad are set. We can now
2399 * generate the bit lengths.
2400 */
2401 gen_bitlen(gz, (tree_desc *)desc);
2402
2403 /* The field len is now set, we can generate the bit codes */
2404 gen_codes (gz, (ct_data *)tree, max_code);
2405
2406 return;
2407 }
2408
2409 /* ===========================================================================
2410 * Scan a literal or distance tree to determine the frequencies of the codes
2411 * in the bit length tree. Updates opt_len to take into account the repeat
2412 * counts. (The contribution of the bit length codes will be added later
2413 * during the construction of bl_tree.)
2414 */
scan_tree(gz,tree,max_code)2415 static void scan_tree (gz, tree, max_code)
2416 GZp gz;
2417 ct_data *tree; /* the tree to be scanned */
2418 int max_code; /* and its largest code of non zero frequency */
2419 {
2420 int n; /* iterates over all tree elements */
2421 int prevlen = -1; /* last emitted length */
2422 int curlen; /* length of current code */
2423 int nextlen = tree[0].dl.len; /* length of next code */
2424 int count = 0; /* repeat count of the current code */
2425 int max_count = 7; /* max repeat count */
2426 int min_count = 4; /* min repeat count */
2427
2428 if (nextlen == 0) max_count = 138, min_count = 3;
2429 tree[max_code+1].dl.len = (ush)0xffff; /* guard */
2430
2431 for (n = 0; n <= max_code; n++) {
2432 curlen = nextlen; nextlen = tree[n+1].dl.len;
2433 if (++count < max_count && curlen == nextlen) {
2434 continue;
2435 } else if (count < min_count) {
2436 gz->bl_tree[curlen].fc.freq += count;
2437 } else if (curlen != 0) {
2438 if (curlen != prevlen) gz->bl_tree[curlen].fc.freq++;
2439 gz->bl_tree[REP_3_6].fc.freq++;
2440 } else if (count <= 10) {
2441 gz->bl_tree[REPZ_3_10].fc.freq++;
2442 } else {
2443 gz->bl_tree[REPZ_11_138].fc.freq++;
2444 }
2445 count = 0; prevlen = curlen;
2446 if (nextlen == 0) {
2447 max_count = 138, min_count = 3;
2448 } else if (curlen == nextlen) {
2449 max_count = 6, min_count = 3;
2450 } else {
2451 max_count = 7, min_count = 4;
2452 }
2453 }
2454 return;
2455 }
2456
2457 /* ===========================================================================
2458 * Send a literal or distance tree in compressed form, using the codes in
2459 * bl_tree.
2460 */
send_tree(gz,tree,max_code)2461 static Logical send_tree (gz, tree, max_code)
2462 GZp gz;
2463 ct_data *tree; /* the tree to be scanned */
2464 int max_code; /* and its largest code of non zero frequency */
2465 {
2466 int n; /* iterates over all tree elements */
2467 int prevlen = -1; /* last emitted length */
2468 int curlen; /* length of current code */
2469 int nextlen = tree[0].dl.len; /* length of next code */
2470 int count = 0; /* repeat count of the current code */
2471 int max_count = 7; /* max repeat count */
2472 int min_count = 4; /* min repeat count */
2473
2474 /* tree[max_code+1].dl.len = -1; */ /* guard already set */
2475 if (nextlen == 0) max_count = 138, min_count = 3;
2476
2477 for (n = 0; n <= max_code; n++) {
2478 curlen = nextlen; nextlen = tree[n+1].dl.len;
2479 if (++count < max_count && curlen == nextlen) {
2480 continue;
2481 } else if (count < min_count) {
2482 do {
2483 if (!send_code(gz,curlen,gz->bl_tree)) return FALSE;
2484 } while (--count != 0);
2485 } else if (curlen != 0) {
2486 if (curlen != prevlen) {
2487 if (!send_code(gz,curlen,gz->bl_tree)) return FALSE;
2488 count--;
2489 }
2490 if (!send_code(gz,REP_3_6,gz->bl_tree)) return FALSE;
2491 if (!send_bits(gz,count-3,2)) return FALSE;
2492
2493 } else if (count <= 10) {
2494 if (!send_code(gz,REPZ_3_10,gz->bl_tree)) return FALSE;
2495 if (!send_bits(gz,count-3,3)) return FALSE;
2496
2497 } else {
2498 if (!send_code(gz,REPZ_11_138,gz->bl_tree)) return FALSE;
2499 if (!send_bits(gz,count-11,7)) return FALSE;
2500 }
2501 count = 0; prevlen = curlen;
2502 if (nextlen == 0) {
2503 max_count = 138, min_count = 3;
2504 } else if (curlen == nextlen) {
2505 max_count = 6, min_count = 3;
2506 } else {
2507 max_count = 7, min_count = 4;
2508 }
2509 }
2510 return TRUE;
2511 }
2512
2513 /* ===========================================================================
2514 * Construct the Huffman tree for the bit lengths and return the index in
2515 * bl_order of the last bit length code to send.
2516 */
build_bl_tree(gz)2517 static int build_bl_tree(gz)
2518 GZp gz;
2519 {
2520 int max_blindex; /* index of last bit length code of non zero freq */
2521
2522 /* Determine the bit length frequencies for literal and distance trees */
2523 scan_tree(gz, (ct_data *)gz->dyn_ltree, gz->l_desc.max_code);
2524 scan_tree(gz, (ct_data *)gz->dyn_dtree, gz->d_desc.max_code);
2525
2526 /* Build the bit length tree: */
2527 build_tree_gz(gz, (tree_desc *)(&(gz->bl_desc)));
2528 /* opt_len now includes the length of the tree representations, except
2529 * the lengths of the bit lengths codes and the 5+5+4 bits for the counts.
2530 */
2531
2532 /* Determine the number of bit length codes to send. The pkzip format
2533 * requires that at least 4 bit length codes be sent. (appnote.txt says
2534 * 3 but the actual value used is 4.)
2535 */
2536 for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) {
2537 if (gz->bl_tree[gz->bl_order[max_blindex]].dl.len != 0) break;
2538 }
2539 /* Update opt_len to include the bit length tree and counts */
2540 gz->opt_len += 3*(max_blindex+1) + 5+5+4;
2541
2542 return max_blindex;
2543 }
2544
2545 /* ===========================================================================
2546 * Send the header for a block using dynamic Huffman trees: the counts, the
2547 * lengths of the bit length codes, the literal tree and the distance tree.
2548 * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.
2549 */
send_all_trees(gz,lcodes,dcodes,blcodes)2550 static Logical send_all_trees (gz, lcodes, dcodes, blcodes)
2551 GZp gz;
2552 int lcodes, dcodes, blcodes; /* number of codes for each tree */
2553 {
2554 int rank; /* index in bl_order */
2555 if (!send_bits(gz,lcodes-257,5)) return FALSE;
2556 /* not +255 as stated in appnote.txt */
2557 if (!send_bits(gz,dcodes-1,5)) return FALSE;
2558 if (!send_bits(gz,blcodes-4,4)) return FALSE;
2559 /* not -3 as stated in appnote.txt */
2560 for (rank = 0; rank < blcodes; rank++) {
2561 if (!send_bits(gz,gz->bl_tree[gz->bl_order[rank]].dl.len,3)) return FALSE;
2562 }
2563 if (!send_tree(gz,(ct_data *)gz->dyn_ltree,lcodes-1)) return FALSE;
2564 /* send the literal tree */
2565 if (!send_tree(gz,(ct_data *)gz->dyn_dtree,dcodes-1)) return FALSE;
2566 /* send the distance tree*/
2567 return TRUE;
2568 }
2569
2570 /* ===========================================================================
2571 * Determine the best encoding for the current block: dynamic trees, static
2572 * trees or store, and output the encoded block to the zip file.
2573 */
flush_block(gz,buf,stored_len,eof)2574 static Logical flush_block(gz, buf, stored_len, eof)
2575 GZp gz;
2576 char *buf; /* input block, or NULL if too old */
2577 OFF_T stored_len; /* length of input block */
2578 int eof; /* true if this is the last block for a file */
2579 {
2580 ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */
2581 int max_blindex; /* index of last bit length code of non zero freq */
2582
2583 gz->flag_buf[gz->last_flags] = gz->tree_flags;
2584 /*Save the flags for the last 8 items */
2585
2586 /* Construct the literal and distance trees */
2587 build_tree_gz(gz, (tree_desc *)(&(gz->l_desc)));
2588
2589 build_tree_gz(gz, (tree_desc *)(&(gz->d_desc)));
2590 /* At this point, opt_len and static_len are the total bit lengths of
2591 * the compressed block data, excluding the tree representations.
2592 */
2593
2594 /* Build the bit length tree for the above two trees, and get the index
2595 * in bl_order of the last bit length code to send.
2596 */
2597 max_blindex = build_bl_tree(gz);
2598
2599 /* Determine the best encoding. Compute first the block length in bytes */
2600 opt_lenb = (gz->opt_len+3+7)>>3;
2601 static_lenb = (gz->static_len+3+7)>>3;
2602
2603 if (static_lenb <= opt_lenb) opt_lenb = static_lenb;
2604
2605 if (stored_len+4 <= opt_lenb && buf != (char*)0) {
2606 /* 4: two words for the lengths */
2607 /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE.
2608 * Otherwise we can't have processed more than WSIZE input bytes since
2609 * the last block flush, because compression would have been
2610 * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to
2611 * transform a block into a stored block.
2612 */
2613 if (!send_bits(gz,(STORED_BLOCK<<1)+eof, 3)) return FALSE;
2614 /* send block type */
2615 if (!copy_block(gz,buf,(unsigned)stored_len,1)) return FALSE;
2616 /* with header */
2617 }
2618 else
2619 if (static_lenb == opt_lenb) {
2620 if (!send_bits(gz,(STATIC_TREES<<1)+eof,3)) return FALSE;
2621 if (!compress_block(gz,(ct_data *)gz->static_ltree,
2622 (ct_data *)gz->static_dtree)) return FALSE;
2623 }
2624 else {
2625 if (!send_bits(gz,(DYN_TREES<<1)+eof,3)) return FALSE;
2626 if (!send_all_trees(gz,gz->l_desc.max_code+1,
2627 gz->d_desc.max_code+1,
2628 max_blindex+1)) return FALSE;
2629 if (!compress_block(gz,(ct_data *)gz->dyn_ltree,
2630 (ct_data *)gz->dyn_dtree)) return FALSE;
2631 }
2632
2633 init_block(gz);
2634
2635 if (eof) {
2636 if (!bi_windup(gz)) return FALSE;
2637 }
2638
2639 return TRUE;
2640 }
2641
2642 /* ===========================================================================
2643 * Save the match info and tally the frequency counts. Return true if
2644 * the current block must be flushed.
2645 */
ct_tally(gz,dist,lc)2646 static int ct_tally (gz, dist, lc)
2647 GZp gz;
2648 int dist; /* distance of matched string */
2649 int lc; /* match length-MIN_MATCH or unmatched char (if dist==0) */
2650 {
2651 gz->inbuf[gz->last_lit++] = (uch)lc;
2652 if (dist == 0) {
2653 /* lc is the unmatched char */
2654 gz->dyn_ltree[lc].fc.freq++;
2655 } else {
2656 /* Here, lc is the match length - MIN_MATCH */
2657 dist--; /* dist = match distance - 1 */
2658
2659 gz->dyn_ltree[gz->length_code[lc]+LITERALS+1].fc.freq++;
2660 gz->dyn_dtree[d_code(dist,gz->dist_code)].fc.freq++;
2661
2662 gz->d_buf[gz->last_dist++] = (ush)dist;
2663 gz->tree_flags |= gz->flag_bit;
2664 }
2665 gz->flag_bit <<= 1;
2666
2667 /* Output the flags if they fill a byte: */
2668 if ((gz->last_lit & 7) == 0) {
2669 gz->flag_buf[gz->last_flags++] = gz->tree_flags;
2670 gz->tree_flags = 0, gz->flag_bit = 1;
2671 }
2672 /* Try to guess if it is profitable to stop the current block here */
2673 if (gz->level > 2 && (gz->last_lit & 0xfff) == 0) {
2674 /* Compute an upper bound for the compressed length */
2675 OFF_T out_length = (OFF_T)gz->last_lit*8L;
2676 OFF_T in_length = (OFF_T)gz->strstart - gz->block_start;
2677 int dcode;
2678 for (dcode = 0; dcode < D_CODES; dcode++) {
2679 out_length += (OFF_T)gz->dyn_dtree[dcode].fc.freq *
2680 (5L+gz->extra_dbits[dcode]);
2681 }
2682 out_length >>= 3;
2683 if (gz->last_dist < gz->last_lit/2 && out_length < in_length/2) return 1;
2684 }
2685 return (gz->last_lit == LIT_BUFSIZE-1 || gz->last_dist == DIST_BUFSIZE);
2686 /* We avoid equality with LIT_BUFSIZE because of wraparound at 64K
2687 * on 16 bit machines and because stored blocks are restricted to
2688 * 64K-1 bytes.
2689 */
2690 }
2691
2692 /* ===========================================================================
2693 * Send the block data compressed using the given Huffman trees
2694 */
compress_block(gz,ltree,dtree)2695 static Logical compress_block (gz, ltree, dtree)
2696 GZp gz;
2697 ct_data *ltree; /* literal tree */
2698 ct_data *dtree; /* distance tree */
2699 {
2700 unsigned dist; /* distance of matched string */
2701 int lc; /* match length or unmatched char (if dist == 0) */
2702 unsigned lx = 0; /* running index in l_buf (inbuf) */
2703 unsigned dx = 0; /* running index in d_buf */
2704 unsigned fx = 0; /* running index in flag_buf */
2705 uch flag = 0; /* current flags */
2706 unsigned code; /* the code to send */
2707 int extra; /* number of extra bits to send */
2708
2709 if (gz->last_lit != 0) do {
2710 if ((lx & 7) == 0) flag = gz->flag_buf[fx++];
2711 lc = gz->inbuf[lx++];
2712 if ((flag & 1) == 0) {
2713 if (!send_code(gz,lc,ltree)) return FALSE;
2714 /* send a literal byte */
2715 } else {
2716 /* Here, lc is the match length - MIN_MATCH */
2717 code = gz->length_code[lc];
2718 if (!send_code(gz,code+LITERALS+1,ltree)) return FALSE;
2719 /* send the length code */
2720 extra = gz->extra_lbits[code];
2721 if (extra != 0) {
2722 lc -= gz->base_length[code];
2723 if (!send_bits(gz,lc,extra)) return FALSE;
2724 /* send the extra length bits */
2725 }
2726 dist = gz->d_buf[dx++];
2727 /* Here, dist is the match distance - 1 */
2728 code = d_code(dist,gz->dist_code);
2729
2730 if (!send_code(gz,code,dtree)) return FALSE;
2731 /* send the distance code */
2732 extra = gz->extra_dbits[code];
2733 if (extra != 0) {
2734 dist -= gz->base_dist[code];
2735 if (!send_bits(gz,dist,extra)) return FALSE;
2736 /* send the extra distance bits */
2737 }
2738 } /* literal or match pair ? */
2739 flag >>= 1;
2740 } while (lx < gz->last_lit);
2741 if (!send_code(gz,END_BLOCK,ltree)) return FALSE;
2742 return TRUE;
2743 }
2744
2745
2746
2747 /* util.c -- utility functions for gzip support
2748 * Copyright (C) 1992-1993 Jean-loup Gailly
2749 * This is free software; you can redistribute it and/or modify it under the
2750 * terms of the GNU General Public License, see the file COPYING.
2751 */
2752
2753 /* ===========================================================================
2754 * Run a set of bytes through the crc shift register. If s is a NULL
2755 * pointer, then initialize the crc shift register contents instead.
2756 * Return the current crc in either case.
2757 */
updcrc(s,n,crcReg,crc_32_tab)2758 static ulg updcrc (s, n, crcReg, crc_32_tab)
2759 uch *s; /* pointer to bytes to pump through */
2760 unsigned n; /* number of bytes in s[] */
2761 ulg *crcReg; /* shift register contents */
2762 ulg crc_32_tab[N_CRC_32_TAB];
2763 /* Table of CRC-32's of all single-byte values. */
2764 {
2765 register ulg c; /* temporary variable */
2766
2767 if (s == NULL) {
2768 c = 0xffffffffL;
2769 } else {
2770 c = *crcReg;
2771 if (n) do {
2772 c = crc_32_tab[((int)c ^ (*s++)) & 0xff] ^ (c >> 8);
2773 } while (--n);
2774 }
2775 *crcReg = c;
2776 return c ^ 0xffffffffL; /* (instead of ~c for 64-bit machines) */
2777 }
2778
2779 /* ===========================================================================
2780 * Fill the input buffer. This is called only when the buffer is empty.
2781 */
fill_inbuf(gu,byte)2782 static Logical fill_inbuf (gu, byte) /* JTL */
2783 GUp gu;
2784 uch *byte;
2785 {
2786 int len;
2787 /* Read as much as possible */
2788 gu->insize = 0;
2789 do {
2790 len = (int) V_read64 ((char *) gu->inbuf + gu->insize, (size_t) 1,
2791 (size_t) (INBUFSIZ - gu->insize), gu->iFp);
2792 if (len == 0) break; /* V_read returns 0 if an error. */
2793 gu->insize += len;
2794 } while (gu->insize < INBUFSIZ);
2795 if (gu->insize == 0) return FALSE;
2796 gu->bytes_in += (ulg)gu->insize;
2797 gu->inptr = 1;
2798 *byte = gu->inbuf[0];
2799 return TRUE;
2800 }
2801
2802 /* ===========================================================================
2803 * Write the output buffer outbuf[0..outcnt-1] and update bytes_out.
2804 * (used for the compressed data only)
2805 */
flush_outbuf(gz)2806 static Logical flush_outbuf(gz)
2807 GZp gz;
2808 {
2809 if (gz->outcnt == 0) return TRUE;
2810 if (!write_buf(gz->oFp,(char *)gz->outbuf,gz->outcnt)) return FALSE;
2811 gz->bytes_out += (ulg)gz->outcnt;
2812 gz->outcnt = 0;
2813 return TRUE;
2814 }
2815
2816 /* ===========================================================================
2817 * Write the output window window[0..outcnt-1] and update crc and bytes_out.
2818 * (Used for the decompressed data only.)
2819 */
flush_window(gu)2820 static Logical flush_window(gu)
2821 GUp gu;
2822 {
2823 if (gu->outcnt == 0) return TRUE;
2824 updcrc (gu->window, gu->outcnt, &(gu->crcReg), gu->crc_32_tab);
2825 if (!write_buf(gu->oFp,(char *)gu->window,gu->outcnt)) return FALSE;
2826 gu->bytes_out += (ulg)gu->outcnt;
2827 gu->outcnt = 0;
2828 return TRUE;
2829 }
2830
2831 /* ===========================================================================
2832 * Does the same as write(), but also handles partial pipe writes and checks
2833 * for error return.
2834 */
write_buf(vFp,buf,cnt)2835 static Logical write_buf(vFp, buf, cnt)
2836 vFILE *vFp;
2837 void *buf;
2838 unsigned cnt;
2839 {
2840 unsigned n;
2841 while (cnt > 0) {
2842 n = (unsigned) V_write64 (buf, (size_t) 1, (size_t) cnt, vFp);
2843 if (n == 0) return FALSE; /* V_write returns 0 if error. */
2844 cnt -= n;
2845 buf = (void *)((char*)buf+n);
2846 }
2847 return TRUE;
2848 }
2849
2850 /* inflate.c -- Not copyrighted 1992 by Mark Adler
2851 version c10p1, 10 January 1993 */
2852
2853 /* You can do whatever you like with this source file, though I would
2854 prefer that if you modify it and redistribute it that you include
2855 comments to that effect with your name and the date. Thank you.
2856 [The history has been moved to the file ChangeLog.]
2857 */
2858
2859 /*
2860 Inflate deflated (PKZIP's method 8 compressed) data. The compression
2861 method searches for as much of the current string of bytes (up to a
2862 length of 258) in the previous 32K bytes. If it doesn't find any
2863 matches (of at least length 3), it codes the next byte. Otherwise, it
2864 codes the length of the matched string and its distance backwards from
2865 the current position. There is a single Huffman code that codes both
2866 single bytes (called "literals") and match lengths. A second Huffman
2867 code codes the distance information, which follows a length code. Each
2868 length or distance code actually represents a base value and a number
2869 of "extra" (sometimes zero) bits to get to add to the base value. At
2870 the end of each deflated block is a special end-of-block (EOB) literal/
2871 length code. The decoding process is basically: get a literal/length
2872 code; if EOB then done; if a literal, emit the decoded byte; if a
2873 length then get the distance and emit the referred-to bytes from the
2874 sliding window of previously emitted data.
2875
2876 There are (currently) three kinds of inflate blocks: stored, fixed, and
2877 dynamic. The compressor deals with some chunk of data at a time, and
2878 decides which method to use on a chunk-by-chunk basis. A chunk might
2879 typically be 32K or 64K. If the chunk is uncompressible, then the
2880 "stored" method is used. In this case, the bytes are simply stored as
2881 is, eight bits per byte, with none of the above coding. The bytes are
2882 preceded by a count, since there is no longer an EOB code.
2883
2884 If the data is compressible, then either the fixed or dynamic methods
2885 are used. In the dynamic method, the compressed data is preceded by
2886 an encoding of the literal/length and distance Huffman codes that are
2887 to be used to decode this block. The representation is itself Huffman
2888 coded, and so is preceded by a description of that code. These code
2889 descriptions take up a little space, and so for small blocks, there is
2890 a predefined set of codes, called the fixed codes. The fixed method is
2891 used if the block codes up smaller that way (usually for quite small
2892 chunks), otherwise the dynamic method is used. In the latter case, the
2893 codes are customized to the probabilities in the current block, and so
2894 can code it much better than the pre-determined fixed codes.
2895
2896 The Huffman codes themselves are decoded using a mutli-level table
2897 lookup, in order to maximize the speed of decoding plus the speed of
2898 building the decoding tables. See the comments below that precede the
2899 LBITS and DBITS tuning parameters.
2900 */
2901
2902
2903 /*
2904 Notes beyond the 1.93a appnote.txt:
2905
2906 1. Distance pointers never point before the beginning of the output
2907 stream.
2908 2. Distance pointers can point back across blocks, up to 32k away.
2909 3. There is an implied maximum of 7 bits for the bit length table and
2910 15 bits for the actual data.
2911 4. If only one code exists, then it is encoded using one bit. (Zero
2912 would be more efficient, but perhaps a little confusing.) If two
2913 codes exist, they are coded using one bit each (0 and 1).
2914 5. There is no way of sending zero distance codes--a dummy must be
2915 sent if there are none. (History: a pre 2.0 version of PKZIP would
2916 store blocks with no distance codes, but this was discovered to be
2917 too harsh a criterion.) Valid only for 1.93a. 2.04c does allow
2918 zero distance codes, which is sent as one code of zero bits in
2919 length.
2920 6. There are up to 286 literal/length codes. Code 256 represents the
2921 end-of-block. Note however that the static length tree defines
2922 288 codes just to fill out the Huffman codes. Codes 286 and 287
2923 cannot be used though, since there is no length base or extra bits
2924 defined for them. Similarly, there are up to 30 distance codes.
2925 However, static trees define 32 codes (all 5 bits) to fill out the
2926 Huffman codes, but the last two had better not show up in the data.
2927 7. Unzip can check dynamic Huffman blocks for complete code sets.
2928 The exception is that a single code would not be complete (see #4).
2929 8. The five bits following the block type is really the number of
2930 literal codes sent minus 257.
2931 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
2932 (1+6+6). Therefore, to output three times the length, you output
2933 three codes (1+1+1), whereas to output four times the same length,
2934 you only need two codes (1+3). Hmm.
2935 10. In the tree reconstruction algorithm, Code = Code + Increment
2936 only if BitLength(i) is not zero. (Pretty obvious.)
2937 11. Correction: 4 Bits: #of Bit Length codes - 4 (4 - 19)
2938 12. Note: length code 284 can represent 227-258, but length code 285
2939 really is 258. The last length deserves its own, short code
2940 since it gets used a lot in very redundant files. The length
2941 258 is special since 258 - 3 (the min match length) is 255.
2942 13. The literal/length and distance code bit lengths are read as a
2943 single stream of lengths. It is possible (and advantageous) for
2944 a repeat code (16, 17, or 18) to go across the boundary between
2945 the two sets of lengths.
2946 */
2947
2948
huft_build(gu,b,n,s,d,e,t,m)2949 static int huft_build(gu, b, n, s, d, e, t, m)
2950 GUp gu;
2951 unsigned *b; /* code lengths in bits (all assumed <= BMAX) */
2952 unsigned n; /* number of codes (assumed <= N_MAX) */
2953 unsigned s; /* number of simple-valued codes (0..s-1) */
2954 ush *d; /* list of base values for non-simple codes */
2955 ush *e; /* list of extra bits for non-simple codes */
2956 struct huft **t; /* result: starting table */
2957 int *m; /* maximum lookup bits, returns actual */
2958 /* Given a list of code lengths and a maximum table size, make a set of
2959 tables to decode that set of codes. Return zero on success, one if
2960 the given code set is incomplete (the tables are still built in this
2961 case), two if the input is invalid (all zero length codes or an
2962 oversubscribed set of lengths), and three if not enough memory. */
2963 {
2964 unsigned a; /* counter for codes of length k */
2965 unsigned c[BMAX+1]; /* bit length count table */
2966 unsigned f; /* i repeats in table every f entries */
2967 int g; /* maximum code length */
2968 int h; /* table level */
2969 register unsigned i; /* counter, current code */
2970 register unsigned j; /* counter */
2971 register int k; /* number of bits in current code */
2972 int l; /* bits per table (returned in m) */
2973 register unsigned *p; /* pointer into c[], b[], or v[] */
2974 register struct huft *q; /* points to current table */
2975 struct huft r; /* table entry for structure assignment */
2976 struct huft *u[BMAX]; /* table stack */
2977 unsigned v[N_MAX]; /* values in order of bit length */
2978 register int w; /* bits before this table == (l * h) */
2979 unsigned x[BMAX+1]; /* bit offsets, then code stack */
2980 unsigned *xp; /* pointer into x */
2981 int y; /* number of dummy codes added */
2982 unsigned z; /* number of entries in current table */
2983
2984 /* Generate counts for each bit length */
2985 memzero(c, sizeof(c));
2986 p = b; i = n;
2987 do {
2988 c[*p]++; /* assume all entries <= BMAX */
2989 p++; /* Can't combine with above line (Solaris bug) */
2990 } while (--i);
2991 if (c[0] == n) /* null input--all zero length codes */
2992 {
2993 *t = (struct huft *)NULL;
2994 *m = 0;
2995 return 0;
2996 }
2997
2998
2999 /* Find minimum and maximum length, bound *m by those */
3000 l = *m;
3001 for (j = 1; j <= BMAX; j++)
3002 if (c[j])
3003 break;
3004 k = j; /* minimum code length */
3005 if ((unsigned)l < j)
3006 l = j;
3007 for (i = BMAX; i; i--)
3008 if (c[i])
3009 break;
3010 g = i; /* maximum code length */
3011 if ((unsigned)l > i)
3012 l = i;
3013 *m = l;
3014
3015
3016 /* Adjust last length count to fill out codes, if needed */
3017 for (y = 1 << j; j < i; j++, y <<= 1)
3018 if ((y -= c[j]) < 0)
3019 return 2; /* bad input: more codes than bits */
3020 if ((y -= c[i]) < 0)
3021 return 2;
3022 c[i] += y;
3023
3024
3025 /* Generate starting offsets into the value table for each length */
3026 x[1] = j = 0;
3027 p = c + 1; xp = x + 2;
3028 while (--i) { /* note that i == g from above */
3029 *xp++ = (j += *p++);
3030 }
3031
3032
3033 /* Make a table of values in order of bit lengths */
3034 p = b; i = 0;
3035 do {
3036 if ((j = *p++) != 0)
3037 v[x[j]++] = i;
3038 } while (++i < n);
3039
3040
3041 /* Generate the Huffman codes and for each, make the table entries */
3042 x[0] = i = 0; /* first Huffman code is zero */
3043 p = v; /* grab values in bit order */
3044 h = -1; /* no tables yet--level -1 */
3045 w = -l; /* bits decoded == (l * h) */
3046 u[0] = (struct huft *)NULL; /* just to keep compilers happy */
3047 q = (struct huft *)NULL; /* ditto */
3048 z = 0; /* ditto */
3049
3050 /* go through the bit lengths (k already is bits in shortest code) */
3051 for (; k <= g; k++)
3052 {
3053 a = c[k];
3054 while (a--)
3055 {
3056 /* here i is the Huffman code of length k bits for value *p */
3057 /* make tables up to required level */
3058 while (k > w + l)
3059 {
3060 h++;
3061 w += l; /* previous table always l bits */
3062
3063 /* compute minimum size table less than or equal to l bits */
3064 z = (z = g - w) > (unsigned)l ? l : z; /* upper limit on table size */
3065 if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */
3066 { /* too few codes for k-w bit table */
3067 f -= a + 1; /* deduct codes from patterns left */
3068 xp = c + k;
3069 while (++j < z) /* try smaller tables up to z bits */
3070 {
3071 if ((f <<= 1) <= *++xp)
3072 break; /* enough codes to use up j bits */
3073 f -= *xp; /* else deduct codes from patterns */
3074 }
3075 }
3076 z = 1 << j; /* table entries for j-bit table */
3077
3078 /* allocate and link in new table */
3079 if ((q = (struct huft *)
3080 CallocateMemory((size_t) 1,
3081 (z + 1) * sizeof(struct huft),NULL)) == NULL) {
3082 if (h) huft_free(u[0]);
3083 return 3; /* not enough memory */
3084 }
3085 gu->hufts += z + 1; /* track memory usage */
3086 *t = q + 1; /* link to list for huft_free() */
3087 *(t = &(q->v.t)) = (struct huft *)NULL;
3088 u[h] = ++q; /* table starts after link */
3089
3090 /* connect to last table, if there is one */
3091 if (h)
3092 {
3093 x[h] = i; /* save pattern for backing up */
3094 r.b = (uch)l; /* bits to dump before this table */
3095 r.e = (uch)(16 + j); /* bits in this table */
3096 r.v.t = q; /* pointer to this table */
3097 j = i >> (w - l); /* (get around Turbo C bug) */
3098 u[h-1][j] = r; /* connect to last table */
3099 }
3100 }
3101
3102 /* set up table entry in r */
3103 r.b = (uch)(k - w);
3104 if (p >= v + n)
3105 r.e = 99; /* out of values--invalid code */
3106 else if (*p < s)
3107 {
3108 r.e = (uch)(*p < 256 ? 16 : 15); /* 256 is end-of-block code */
3109 r.v.n = (ush)(*p); /* simple code is just the value */
3110 p++; /* one compiler does not like *p++ */
3111 }
3112 else
3113 {
3114 r.e = (uch)e[*p - s]; /* non-simple--look up in lists */
3115 r.v.n = d[*p++ - s];
3116 }
3117
3118 /* fill code-like entries with r */
3119 f = 1 << (k - w);
3120 for (j = i >> w; j < z; j += f)
3121 q[j] = r;
3122
3123 /* backwards increment the k-bit code i */
3124 for (j = 1 << (k - 1); i & j; j >>= 1)
3125 i ^= j;
3126 i ^= j;
3127
3128 /* backup over finished tables */
3129 while ((i & ((1 << w) - 1)) != x[h])
3130 {
3131 h--; /* don't need to update q */
3132 w -= l;
3133 }
3134 }
3135 }
3136
3137 /* Return 1 if we were given an incomplete table */
3138 return (y != 0 && g != 1 ? 1 : 0);
3139 }
3140
3141
3142
huft_free(t)3143 static int huft_free(t)
3144 struct huft *t; /* table to free */
3145 /* Free the malloc'ed tables built by huft_build(), which makes a linked
3146 list of the tables it made, with the links in a dummy first entry of
3147 each table. */
3148 {
3149 register struct huft *p, *q;
3150
3151
3152 /* Go through linked list, freeing from the malloced (t[-1]) address. */
3153 p = t;
3154 while (p != (struct huft *)NULL)
3155 {
3156 q = (--p)->v.t;
3157 cdf_FreeMemory ((char *) p, NULL);
3158 p = q;
3159 }
3160 return 0;
3161 }
3162
3163
inflate_codes(gu,tl,td,bl,bd)3164 static int inflate_codes(gu, tl, td, bl, bd)
3165 GUp gu;
3166 struct huft *tl, *td; /* literal/length and distance decoder tables */
3167 int bl, bd; /* number of bits decoded by tl[] and td[] */
3168 /* inflate (decompress) the codes in a deflated (compressed) block.
3169 Return an error code or zero if it all goes ok. */
3170 {
3171 register unsigned e; /* table entry flag/number of extra bits */
3172 unsigned n, d; /* length and index for copy */
3173 unsigned w; /* current window position */
3174 struct huft *t; /* pointer to table entry */
3175 unsigned ml, md; /* masks for bl and bd bits */
3176 register ulg b; /* bit buffer */
3177 register unsigned k; /* number of bits in bit buffer */
3178
3179 /* make local copies of globals */
3180 b = gu->bb; /* initialize bit buffer */
3181 k = gu->bk;
3182 w = gu->outcnt; /* initialize window position */
3183
3184 /* inflate the coded data */
3185 ml = gu->mask_bits[bl]; /* precompute masks for speed */
3186 md = gu->mask_bits[bd];
3187 for (;;) /* do until end of block */
3188 {
3189 NEEDBITS(gu,b,k,(unsigned)bl)
3190 if ((e = (t = tl + ((unsigned)b & ml))->e) > 16)
3191 do {
3192 if (e == 99) return 1;
3193 DUMPBITS(b,k,t->b)
3194 e -= 16;
3195 NEEDBITS(gu,b,k,e)
3196 } while ((e = (t = t->v.t + ((unsigned)b & gu->mask_bits[e]))->e) > 16);
3197 DUMPBITS(b,k,t->b)
3198 if (e == 16) /* then it's a literal */
3199 {
3200 gu->window[w++] = (uch)t->v.n;
3201 if (w == WSIZE) {
3202 gu->outcnt = w;
3203 if (!flush_window(gu)) return 5; /* Write error - JTL */
3204 w = 0;
3205 }
3206 }
3207 else /* it's an EOB or a length */
3208 {
3209 /* exit if end of block */
3210 if (e == 15)
3211 break;
3212
3213 /* get length of block to copy */
3214 NEEDBITS(gu,b,k,e)
3215 n = t->v.n + ((unsigned)b & gu->mask_bits[e]);
3216 DUMPBITS(b,k,e);
3217
3218 /* decode distance of block to copy */
3219 NEEDBITS(gu,b,k,(unsigned)bd)
3220 if ((e = (t = td + ((unsigned)b & md))->e) > 16)
3221 do {
3222 if (e == 99) return 1;
3223 DUMPBITS(b,k,t->b)
3224 e -= 16;
3225 NEEDBITS(gu,b,k,e)
3226 } while ((e = (t = t->v.t + ((unsigned)b & gu->mask_bits[e]))->e) > 16);
3227 DUMPBITS(b,k,t->b)
3228 NEEDBITS(gu,b,k,e)
3229 d = w - t->v.n - ((unsigned)b & gu->mask_bits[e]);
3230 DUMPBITS(b,k,e)
3231
3232 /* do the copy */
3233 do {
3234 n -= (e = (e = WSIZE - ((d &= WSIZE-1) > w ? d : w)) > n ? n : e);
3235 if (w - d >= e) /* (this test assumes unsigned comparison) */
3236 {
3237 memcpy(gu->window + w, gu->window + d, e);
3238 w += e;
3239 d += e;
3240 }
3241 else /* do it slow to avoid memcpy() overlap */
3242 do {
3243 gu->window[w++] = gu->window[d++];
3244 } while (--e);
3245 if (w == WSIZE)
3246 {
3247 gu->outcnt = w;
3248 if (!flush_window(gu)) return 5; /* Write error. */
3249 w = 0;
3250 }
3251 } while (n);
3252 }
3253 }
3254
3255 /* restore the globals from the locals */
3256 gu->outcnt = w; /* restore global window pointer */
3257 gu->bb = b; /* restore global bit buffer */
3258 gu->bk = k;
3259
3260 /* done */
3261 return 0;
3262 }
3263
inflate_stored(gu)3264 static int inflate_stored(gu)
3265 GUp gu;
3266 /* "decompress" an inflated type 0 (stored) block. */
3267 {
3268 unsigned n; /* number of bytes in block */
3269 unsigned w; /* current window position */
3270 register ulg b; /* bit buffer */
3271 register unsigned k; /* number of bits in bit buffer */
3272
3273 /* make local copies of globals */
3274 b = gu->bb; /* initialize bit buffer */
3275 k = gu->bk;
3276 w = gu->outcnt; /* initialize window position */
3277
3278 /* go to byte boundary */
3279 n = k & 7;
3280 DUMPBITS(b,k,n);
3281
3282 /* get the length and its complement */
3283 NEEDBITS(gu,b,k,16)
3284 n = ((unsigned)b & 0xffff);
3285 DUMPBITS(b,k,16)
3286 NEEDBITS(gu,b,k,16)
3287 if (n != (unsigned)((~b) & 0xffff))
3288 return 1; /* error in compressed data */
3289 DUMPBITS(b,k,16)
3290
3291 /* read and output the compressed data */
3292 while (n--)
3293 {
3294 NEEDBITS(gu,b,k,8)
3295 gu->window[w++] = (uch)b;
3296 if (w == WSIZE)
3297 {
3298 gu->outcnt = w;
3299 if (!flush_window(gu)) return 5; /* Write error. */
3300 w = 0;
3301 }
3302 DUMPBITS(b,k,8)
3303 }
3304
3305 /* restore the globals from the locals */
3306 gu->outcnt = w; /* restore global window pointer */
3307 gu->bb = b; /* restore global bit buffer */
3308 gu->bk = k;
3309 return 0;
3310 }
3311
inflate_fixed(gu)3312 static int inflate_fixed(gu)
3313 GUp gu;
3314 /* decompress an inflated type 1 (fixed Huffman codes) block. We should
3315 either replace this with a custom decoder, or at least precompute the
3316 Huffman tables. */
3317 {
3318 int i; /* temporary variable */
3319 struct huft *tl; /* literal/length code table */
3320 struct huft *td; /* distance code table */
3321 int bl; /* lookup bits for tl */
3322 int bd; /* lookup bits for td */
3323 unsigned l[288]; /* length list for huft_build */
3324
3325 /* set up literal table */
3326 for (i = 0; i < 144; i++)
3327 l[i] = 8;
3328 for (; i < 256; i++)
3329 l[i] = 9;
3330 for (; i < 280; i++)
3331 l[i] = 7;
3332 for (; i < 288; i++) /* make a complete, but wrong code set */
3333 l[i] = 8;
3334 bl = 7;
3335 if ((i = huft_build(gu, l, 288, 257, gu->cplens, gu->cplext, &tl, &bl)) != 0)
3336 return i;
3337
3338 /* set up distance table */
3339 for (i = 0; i < 30; i++) /* make an incomplete code set */
3340 l[i] = 5;
3341 bd = 5;
3342 if ((i = huft_build(gu, l, 30, 0, gu->cpdist, gu->cpdext, &td, &bd)) > 1)
3343 {
3344 huft_free(tl);
3345 return i;
3346 }
3347
3348 /* decompress until an end-of-block code */
3349 if ((i = inflate_codes(gu,tl,td,bl,bd)) != 0) return i; /* JTL */
3350
3351 /* free the decoding tables, return */
3352 huft_free (tl);
3353 huft_free (td);
3354 return 0;
3355 }
3356
inflate_dynamic(gu)3357 static int inflate_dynamic(gu)
3358 GUp gu;
3359 /* decompress an inflated type 2 (dynamic Huffman codes) block. */
3360 {
3361 int i; /* temporary variables */
3362 unsigned j;
3363 unsigned l; /* last length */
3364 unsigned m; /* mask for bit lengths table */
3365 unsigned n; /* number of lengths to get */
3366 struct huft *tl; /* literal/length code table */
3367 struct huft *td; /* distance code table */
3368 int bl; /* lookup bits for tl */
3369 int bd; /* lookup bits for td */
3370 unsigned nb; /* number of bit length codes */
3371 unsigned nl; /* number of literal/length codes */
3372 unsigned nd; /* number of distance codes */
3373 unsigned ll[286+30]; /* literal/length and distance code lengths */
3374 register ulg b; /* bit buffer */
3375 register unsigned k; /* number of bits in bit buffer */
3376
3377 /* make local bit buffer */
3378 b = gu->bb;
3379 k = gu->bk;
3380
3381 /* read in table lengths */
3382 NEEDBITS(gu,b,k,5)
3383 nl = 257 + ((unsigned)b & 0x1f); /* number of literal/length codes */
3384 DUMPBITS(b,k,5)
3385 NEEDBITS(gu,b,k,5)
3386 nd = 1 + ((unsigned)b & 0x1f); /* number of distance codes */
3387 DUMPBITS(b,k,5)
3388 NEEDBITS(gu,b,k,4)
3389 nb = 4 + ((unsigned)b & 0xf); /* number of bit length codes */
3390 DUMPBITS(b,k,4)
3391 if (nl > 286 || nd > 30) return 1; /* bad lengths */
3392
3393 /* read in bit-length-code lengths */
3394 for (j = 0; j < nb; j++)
3395 {
3396 NEEDBITS(gu,b,k,3)
3397 ll[gu->border[j]] = (unsigned)b & 7;
3398 DUMPBITS(b,k,3)
3399 }
3400 for (; j < 19; j++) ll[gu->border[j]] = 0;
3401
3402 /* build decoding table for trees--single level, 7 bit lookup */
3403 bl = 7;
3404 if ((i = huft_build(gu, ll, 19, 19, NULL, NULL, &tl, &bl)) != 0)
3405 {
3406 if (i == 1) huft_free (tl);
3407 return i; /* incomplete code set */
3408 }
3409
3410 /* read in literal and distance code lengths */
3411 n = nl + nd;
3412 m = gu->mask_bits[bl];
3413 i = l = 0;
3414 while ((unsigned)i < n)
3415 {
3416 NEEDBITS(gu,b,k,(unsigned)bl)
3417 j = (td = tl + ((unsigned)b & m))->b;
3418 DUMPBITS(b,k,j)
3419 j = td->v.n;
3420 if (j < 16) /* length of code in bits (0..15) */
3421 ll[i++] = l = j; /* save last length in l */
3422 else if (j == 16) /* repeat last length 3 to 6 times */
3423 {
3424 NEEDBITS(gu,b,k,2)
3425 j = 3 + ((unsigned)b & 3);
3426 DUMPBITS(b,k,2)
3427 if ((unsigned)i + j > n)
3428 return 1;
3429 while (j--)
3430 ll[i++] = l;
3431 }
3432 else if (j == 17) /* 3 to 10 zero length codes */
3433 {
3434 NEEDBITS(gu,b,k,3)
3435 j = 3 + ((unsigned)b & 7);
3436 DUMPBITS(b,k,3)
3437 if ((unsigned)i + j > n)
3438 return 1;
3439 while (j--)
3440 ll[i++] = 0;
3441 l = 0;
3442 }
3443 else /* j == 18: 11 to 138 zero length codes */
3444 {
3445 NEEDBITS(gu,b,k,7)
3446 j = 11 + ((unsigned)b & 0x7f);
3447 DUMPBITS(b,k,7)
3448 if ((unsigned)i + j > n)
3449 return 1;
3450 while (j--)
3451 ll[i++] = 0;
3452 l = 0;
3453 }
3454 }
3455
3456 /* free decoding table for trees */
3457 huft_free (tl);
3458
3459 /* restore the global bit buffer */
3460 gu->bb = b;
3461 gu->bk = k;
3462
3463 /* build the decoding tables for literal/length and distance codes */
3464 bl = LBITS;
3465 if ((i = huft_build(gu, ll, nl, 257, gu->cplens, gu->cplext, &tl, &bl)) != 0)
3466 {
3467 if (i == 1) {
3468 /* fprintf(stderr, " incomplete literal tree\n"); */
3469 huft_free (tl);
3470 }
3471 return i; /* incomplete code set */
3472 }
3473 bd = DBITS;
3474 if ((i = huft_build(gu, ll + nl, nd, 0, gu->cpdist, gu->cpdext, &td, &bd)) != 0) {
3475 if (i == 1) {
3476 /* fprintf(stderr, " incomplete distance tree\n"); */
3477 huft_free (td);
3478 }
3479 huft_free (tl);
3480 return i; /* incomplete code set */
3481 }
3482
3483
3484 /* decompress until an end-of-block code */
3485 if ((i = inflate_codes(gu,tl,td,bl,bd)) != 0) return i; /* JTL */
3486
3487 /* free the decoding tables, return */
3488 huft_free (tl);
3489 huft_free (td);
3490 return 0;
3491 }
3492
inflate_block(gu,e)3493 static int inflate_block(gu, e)
3494 GUp gu;
3495 int *e; /* last block flag */
3496 /* decompress an inflated block */
3497 {
3498 unsigned t; /* block type */
3499 register ulg b; /* bit buffer */
3500 register unsigned k; /* number of bits in bit buffer */
3501
3502 /* make local bit buffer */
3503 b = gu->bb;
3504 k = gu->bk;
3505
3506 /* read in last block bit */
3507 NEEDBITS(gu,b,k,1)
3508 *e = (int)b & 1;
3509 DUMPBITS(b,k,1)
3510
3511 /* read in block type */
3512 NEEDBITS(gu,b,k,2)
3513 t = (unsigned)b & 3;
3514 DUMPBITS(b,k,2)
3515
3516 /* restore the global bit buffer */
3517 gu->bb = b;
3518 gu->bk = k;
3519
3520 /* inflate that block type */
3521 if (t == 2) return inflate_dynamic(gu);
3522 if (t == 0) return inflate_stored(gu);
3523 if (t == 1) return inflate_fixed(gu);
3524
3525 /* bad block type */
3526 return 2;
3527 }
3528
3529
3530
inflate(gu)3531 static int inflate(gu)
3532 GUp gu;
3533 /* decompress an inflated entry */
3534 {
3535 int e; /* last block flag */
3536 int r; /* result code */
3537 unsigned h; /* maximum struct huft's malloc'ed */
3538
3539 /* initialize window, bit buffer */
3540 gu->outcnt = 0;
3541 gu->bk = 0;
3542 gu->bb = 0;
3543
3544 /* decompress until the last block */
3545 h = 0;
3546 do {
3547 gu->hufts = 0;
3548 if ((r = inflate_block(gu,&e)) != 0) return r;
3549 if (gu->hufts > h) h = gu->hufts;
3550 } while (!e);
3551
3552 /* Undo too much lookahead. The next read will be byte aligned so we
3553 * can discard unused bits in the last meaningful byte.
3554 */
3555 while (gu->bk >= 8) {
3556 gu->bk -= 8;
3557 gu->inptr--;
3558 }
3559
3560 /* flush out slide */
3561 if (!flush_window(gu)) return 5; /* Write error. */
3562
3563 /* return success */
3564 return 0;
3565 }
3566
3567 /******************************************************************************
3568 * PutByte.
3569 ******************************************************************************/
3570
PutByte(gz,c)3571 static Logical PutByte (gz, c)
3572 GZp gz;
3573 unsigned c;
3574 {
3575 gz->outbuf[gz->outcnt++] = (uch) c;
3576 if (gz->outcnt == OUTBUFSIZ) {
3577 if (!flush_outbuf(gz)) return FALSE;
3578 }
3579 return TRUE;
3580 }
3581
3582 /******************************************************************************
3583 * PutShort.
3584 ******************************************************************************/
3585
PutShort(gz,w)3586 static Logical PutShort (gz, w)
3587 GZp gz;
3588 unsigned w;
3589 {
3590 if (gz->outcnt < OUTBUFSIZ-2) {
3591 gz->outbuf[gz->outcnt++] = (uch) ((ush)(w) & 0xff);
3592 gz->outbuf[gz->outcnt++] = (uch) ((ush)(w) >> 8);
3593 }
3594 else {
3595 if (!PutByte(gz,(unsigned)((ush)(w) & 0xff))) return FALSE;
3596 if (!PutByte(gz,(unsigned)((ush)(w) >> 8))) return FALSE;
3597 }
3598 return TRUE;
3599 }
3600
3601 /******************************************************************************
3602 * PutLong.
3603 ******************************************************************************/
3604
PutLong(gz,n)3605 static Logical PutLong (gz, n)
3606 GZp gz;
3607 ulg n;
3608 {
3609 if (!PutShort(gz,(unsigned)((n) & 0xffff))) return FALSE;
3610 if (!PutShort(gz,(unsigned)((n) >> 16))) return FALSE;
3611 return TRUE;
3612 }
3613
3614 /******************************************************************************
3615 * PutLongLong.
3616 ******************************************************************************/
3617
PutLongLong(gz,n)3618 static Logical PutLongLong (gz, n)
3619 GZp gz;
3620 OFF_T n;
3621 {
3622 if (!PutLong(gz,(unsigned)((n) & 0xffffffff))) return FALSE;
3623 if (!PutLong(gz,(unsigned)((n) >> 32))) return FALSE;
3624 return TRUE;
3625 }
3626
3627 /******************************************************************************
3628 * GetByte.
3629 ******************************************************************************/
3630
GetByte(gu,byte)3631 static Logical GetByte (gu, byte)
3632 GUp gu;
3633 uch *byte;
3634 {
3635 if (gu->inptr < gu->insize)
3636 *byte = gu->inbuf[gu->inptr++];
3637 else
3638 if (!fill_inbuf(gu,byte)) return FALSE;
3639 return TRUE;
3640 }
3641
3642 /******************************************************************************
3643 * initCRC.
3644 ******************************************************************************/
3645
initCRC(crc_32_tab)3646 static void initCRC (crc_32_tab)
3647 ulg crc_32_tab[N_CRC_32_TAB];
3648 {
3649 crc_32_tab[0]= 0x00000000L;
3650 crc_32_tab[1]= 0x77073096L;
3651 crc_32_tab[2]= 0xee0e612cL;
3652 crc_32_tab[3]= 0x990951baL;
3653 crc_32_tab[4]= 0x076dc419L;
3654 crc_32_tab[5]= 0x706af48fL;
3655 crc_32_tab[6]= 0xe963a535L;
3656 crc_32_tab[7]= 0x9e6495a3L;
3657 crc_32_tab[8]= 0x0edb8832L;
3658 crc_32_tab[9]= 0x79dcb8a4L;
3659 crc_32_tab[10]= 0xe0d5e91eL;
3660 crc_32_tab[11]= 0x97d2d988L;
3661 crc_32_tab[12]= 0x09b64c2bL;
3662 crc_32_tab[13]= 0x7eb17cbdL;
3663 crc_32_tab[14]= 0xe7b82d07L;
3664 crc_32_tab[15]= 0x90bf1d91L;
3665 crc_32_tab[16]= 0x1db71064L;
3666 crc_32_tab[17]= 0x6ab020f2L;
3667 crc_32_tab[18]= 0xf3b97148L;
3668 crc_32_tab[19]= 0x84be41deL;
3669 crc_32_tab[20]= 0x1adad47dL;
3670 crc_32_tab[21]= 0x6ddde4ebL;
3671 crc_32_tab[22]= 0xf4d4b551L;
3672 crc_32_tab[23]= 0x83d385c7L;
3673 crc_32_tab[24]= 0x136c9856L;
3674 crc_32_tab[25]= 0x646ba8c0L;
3675 crc_32_tab[26]= 0xfd62f97aL;
3676 crc_32_tab[27]= 0x8a65c9ecL;
3677 crc_32_tab[28]= 0x14015c4fL;
3678 crc_32_tab[29]= 0x63066cd9L;
3679 crc_32_tab[30]= 0xfa0f3d63L;
3680 crc_32_tab[31]= 0x8d080df5L;
3681 crc_32_tab[32]= 0x3b6e20c8L;
3682 crc_32_tab[33]= 0x4c69105eL;
3683 crc_32_tab[34]= 0xd56041e4L;
3684 crc_32_tab[35]= 0xa2677172L;
3685 crc_32_tab[36]= 0x3c03e4d1L;
3686 crc_32_tab[37]= 0x4b04d447L;
3687 crc_32_tab[38]= 0xd20d85fdL;
3688 crc_32_tab[39]= 0xa50ab56bL;
3689 crc_32_tab[40]= 0x35b5a8faL;
3690 crc_32_tab[41]= 0x42b2986cL;
3691 crc_32_tab[42]= 0xdbbbc9d6L;
3692 crc_32_tab[43]= 0xacbcf940L;
3693 crc_32_tab[44]= 0x32d86ce3L;
3694 crc_32_tab[45]= 0x45df5c75L;
3695 crc_32_tab[46]= 0xdcd60dcfL;
3696 crc_32_tab[47]= 0xabd13d59L;
3697 crc_32_tab[48]= 0x26d930acL;
3698 crc_32_tab[49]= 0x51de003aL;
3699 crc_32_tab[50]= 0xc8d75180L;
3700 crc_32_tab[51]= 0xbfd06116L;
3701 crc_32_tab[52]= 0x21b4f4b5L;
3702 crc_32_tab[53]= 0x56b3c423L;
3703 crc_32_tab[54]= 0xcfba9599L;
3704 crc_32_tab[55]= 0xb8bda50fL;
3705 crc_32_tab[56]= 0x2802b89eL;
3706 crc_32_tab[57]= 0x5f058808L;
3707 crc_32_tab[58]= 0xc60cd9b2L;
3708 crc_32_tab[59]= 0xb10be924L;
3709 crc_32_tab[60]= 0x2f6f7c87L;
3710 crc_32_tab[61]= 0x58684c11L;
3711 crc_32_tab[62]= 0xc1611dabL;
3712 crc_32_tab[63]= 0xb6662d3dL;
3713 crc_32_tab[64]= 0x76dc4190L;
3714 crc_32_tab[65]= 0x01db7106L;
3715 crc_32_tab[66]= 0x98d220bcL;
3716 crc_32_tab[67]= 0xefd5102aL;
3717 crc_32_tab[68]= 0x71b18589L;
3718 crc_32_tab[69]= 0x06b6b51fL;
3719 crc_32_tab[70]= 0x9fbfe4a5L;
3720 crc_32_tab[71]= 0xe8b8d433L;
3721 crc_32_tab[72]= 0x7807c9a2L;
3722 crc_32_tab[73]= 0x0f00f934L;
3723 crc_32_tab[74]= 0x9609a88eL;
3724 crc_32_tab[75]= 0xe10e9818L;
3725 crc_32_tab[76]= 0x7f6a0dbbL;
3726 crc_32_tab[77]= 0x086d3d2dL;
3727 crc_32_tab[78]= 0x91646c97L;
3728 crc_32_tab[79]= 0xe6635c01L;
3729 crc_32_tab[80]= 0x6b6b51f4L;
3730 crc_32_tab[81]= 0x1c6c6162L;
3731 crc_32_tab[82]= 0x856530d8L;
3732 crc_32_tab[83]= 0xf262004eL;
3733 crc_32_tab[84]= 0x6c0695edL;
3734 crc_32_tab[85]= 0x1b01a57bL;
3735 crc_32_tab[86]= 0x8208f4c1L;
3736 crc_32_tab[87]= 0xf50fc457L;
3737 crc_32_tab[88]= 0x65b0d9c6L;
3738 crc_32_tab[89]= 0x12b7e950L;
3739 crc_32_tab[90]= 0x8bbeb8eaL;
3740 crc_32_tab[91]= 0xfcb9887cL;
3741 crc_32_tab[92]= 0x62dd1ddfL;
3742 crc_32_tab[93]= 0x15da2d49L;
3743 crc_32_tab[94]= 0x8cd37cf3L;
3744 crc_32_tab[95]= 0xfbd44c65L;
3745 crc_32_tab[96]= 0x4db26158L;
3746 crc_32_tab[97]= 0x3ab551ceL;
3747 crc_32_tab[98]= 0xa3bc0074L;
3748 crc_32_tab[99]= 0xd4bb30e2L;
3749 crc_32_tab[100]= 0x4adfa541L;
3750 crc_32_tab[101]= 0x3dd895d7L;
3751 crc_32_tab[102]= 0xa4d1c46dL;
3752 crc_32_tab[103]= 0xd3d6f4fbL;
3753 crc_32_tab[104]= 0x4369e96aL;
3754 crc_32_tab[105]= 0x346ed9fcL;
3755 crc_32_tab[106]= 0xad678846L;
3756 crc_32_tab[107]= 0xda60b8d0L;
3757 crc_32_tab[108]= 0x44042d73L;
3758 crc_32_tab[109]= 0x33031de5L;
3759 crc_32_tab[110]= 0xaa0a4c5fL;
3760 crc_32_tab[111]= 0xdd0d7cc9L;
3761 crc_32_tab[112]= 0x5005713cL;
3762 crc_32_tab[113]= 0x270241aaL;
3763 crc_32_tab[114]= 0xbe0b1010L;
3764 crc_32_tab[115]= 0xc90c2086L;
3765 crc_32_tab[116]= 0x5768b525L;
3766 crc_32_tab[117]= 0x206f85b3L;
3767 crc_32_tab[118]= 0xb966d409L;
3768 crc_32_tab[119]= 0xce61e49fL;
3769 crc_32_tab[120]= 0x5edef90eL;
3770 crc_32_tab[121]= 0x29d9c998L;
3771 crc_32_tab[122]= 0xb0d09822L;
3772 crc_32_tab[123]= 0xc7d7a8b4L;
3773 crc_32_tab[124]= 0x59b33d17L;
3774 crc_32_tab[125]= 0x2eb40d81L;
3775 crc_32_tab[126]= 0xb7bd5c3bL;
3776 crc_32_tab[127]= 0xc0ba6cadL;
3777 crc_32_tab[128]= 0xedb88320L;
3778 crc_32_tab[129]= 0x9abfb3b6L;
3779 crc_32_tab[130]= 0x03b6e20cL;
3780 crc_32_tab[131]= 0x74b1d29aL;
3781 crc_32_tab[132]= 0xead54739L;
3782 crc_32_tab[133]= 0x9dd277afL;
3783 crc_32_tab[134]= 0x04db2615L;
3784 crc_32_tab[135]= 0x73dc1683L;
3785 crc_32_tab[136]= 0xe3630b12L;
3786 crc_32_tab[137]= 0x94643b84L;
3787 crc_32_tab[138]= 0x0d6d6a3eL;
3788 crc_32_tab[139]= 0x7a6a5aa8L;
3789 crc_32_tab[140]= 0xe40ecf0bL;
3790 crc_32_tab[141]= 0x9309ff9dL;
3791 crc_32_tab[142]= 0x0a00ae27L;
3792 crc_32_tab[143]= 0x7d079eb1L;
3793 crc_32_tab[144]= 0xf00f9344L;
3794 crc_32_tab[145]= 0x8708a3d2L;
3795 crc_32_tab[146]= 0x1e01f268L;
3796 crc_32_tab[147]= 0x6906c2feL;
3797 crc_32_tab[148]= 0xf762575dL;
3798 crc_32_tab[149]= 0x806567cbL;
3799 crc_32_tab[150]= 0x196c3671L;
3800 crc_32_tab[151]= 0x6e6b06e7L;
3801 crc_32_tab[152]= 0xfed41b76L;
3802 crc_32_tab[153]= 0x89d32be0L;
3803 crc_32_tab[154]= 0x10da7a5aL;
3804 crc_32_tab[155]= 0x67dd4accL;
3805 crc_32_tab[156]= 0xf9b9df6fL;
3806 crc_32_tab[157]= 0x8ebeeff9L;
3807 crc_32_tab[158]= 0x17b7be43L;
3808 crc_32_tab[159]= 0x60b08ed5L;
3809 crc_32_tab[160]= 0xd6d6a3e8L;
3810 crc_32_tab[161]= 0xa1d1937eL;
3811 crc_32_tab[162]= 0x38d8c2c4L;
3812 crc_32_tab[163]= 0x4fdff252L;
3813 crc_32_tab[164]= 0xd1bb67f1L;
3814 crc_32_tab[165]= 0xa6bc5767L;
3815 crc_32_tab[166]= 0x3fb506ddL;
3816 crc_32_tab[167]= 0x48b2364bL;
3817 crc_32_tab[168]= 0xd80d2bdaL;
3818 crc_32_tab[169]= 0xaf0a1b4cL;
3819 crc_32_tab[170]= 0x36034af6L;
3820 crc_32_tab[171]= 0x41047a60L;
3821 crc_32_tab[172]= 0xdf60efc3L;
3822 crc_32_tab[173]= 0xa867df55L;
3823 crc_32_tab[174]= 0x316e8eefL;
3824 crc_32_tab[175]= 0x4669be79L;
3825 crc_32_tab[176]= 0xcb61b38cL;
3826 crc_32_tab[177]= 0xbc66831aL;
3827 crc_32_tab[178]= 0x256fd2a0L;
3828 crc_32_tab[179]= 0x5268e236L;
3829 crc_32_tab[180]= 0xcc0c7795L;
3830 crc_32_tab[181]= 0xbb0b4703L;
3831 crc_32_tab[182]= 0x220216b9L;
3832 crc_32_tab[183]= 0x5505262fL;
3833 crc_32_tab[184]= 0xc5ba3bbeL;
3834 crc_32_tab[185]= 0xb2bd0b28L;
3835 crc_32_tab[186]= 0x2bb45a92L;
3836 crc_32_tab[187]= 0x5cb36a04L;
3837 crc_32_tab[188]= 0xc2d7ffa7L;
3838 crc_32_tab[189]= 0xb5d0cf31L;
3839 crc_32_tab[190]= 0x2cd99e8bL;
3840 crc_32_tab[191]= 0x5bdeae1dL;
3841 crc_32_tab[192]= 0x9b64c2b0L;
3842 crc_32_tab[193]= 0xec63f226L;
3843 crc_32_tab[194]= 0x756aa39cL;
3844 crc_32_tab[195]= 0x026d930aL;
3845 crc_32_tab[196]= 0x9c0906a9L;
3846 crc_32_tab[197]= 0xeb0e363fL;
3847 crc_32_tab[198]= 0x72076785L;
3848 crc_32_tab[199]= 0x05005713L;
3849 crc_32_tab[200]= 0x95bf4a82L;
3850 crc_32_tab[201]= 0xe2b87a14L;
3851 crc_32_tab[202]= 0x7bb12baeL;
3852 crc_32_tab[203]= 0x0cb61b38L;
3853 crc_32_tab[204]= 0x92d28e9bL;
3854 crc_32_tab[205]= 0xe5d5be0dL;
3855 crc_32_tab[206]= 0x7cdcefb7L;
3856 crc_32_tab[207]= 0x0bdbdf21L;
3857 crc_32_tab[208]= 0x86d3d2d4L;
3858 crc_32_tab[209]= 0xf1d4e242L;
3859 crc_32_tab[210]= 0x68ddb3f8L;
3860 crc_32_tab[211]= 0x1fda836eL;
3861 crc_32_tab[212]= 0x81be16cdL;
3862 crc_32_tab[213]= 0xf6b9265bL;
3863 crc_32_tab[214]= 0x6fb077e1L;
3864 crc_32_tab[215]= 0x18b74777L;
3865 crc_32_tab[216]= 0x88085ae6L;
3866 crc_32_tab[217]= 0xff0f6a70L;
3867 crc_32_tab[218]= 0x66063bcaL;
3868 crc_32_tab[219]= 0x11010b5cL;
3869 crc_32_tab[220]= 0x8f659effL;
3870 crc_32_tab[221]= 0xf862ae69L;
3871 crc_32_tab[222]= 0x616bffd3L;
3872 crc_32_tab[223]= 0x166ccf45L;
3873 crc_32_tab[224]= 0xa00ae278L;
3874 crc_32_tab[225]= 0xd70dd2eeL;
3875 crc_32_tab[226]= 0x4e048354L;
3876 crc_32_tab[227]= 0x3903b3c2L;
3877 crc_32_tab[228]= 0xa7672661L;
3878 crc_32_tab[229]= 0xd06016f7L;
3879 crc_32_tab[230]= 0x4969474dL;
3880 crc_32_tab[231]= 0x3e6e77dbL;
3881 crc_32_tab[232]= 0xaed16a4aL;
3882 crc_32_tab[233]= 0xd9d65adcL;
3883 crc_32_tab[234]= 0x40df0b66L;
3884 crc_32_tab[235]= 0x37d83bf0L;
3885 crc_32_tab[236]= 0xa9bcae53L;
3886 crc_32_tab[237]= 0xdebb9ec5L;
3887 crc_32_tab[238]= 0x47b2cf7fL;
3888 crc_32_tab[239]= 0x30b5ffe9L;
3889 crc_32_tab[240]= 0xbdbdf21cL;
3890 crc_32_tab[241]= 0xcabac28aL;
3891 crc_32_tab[242]= 0x53b39330L;
3892 crc_32_tab[243]= 0x24b4a3a6L;
3893 crc_32_tab[244]= 0xbad03605L;
3894 crc_32_tab[245]= 0xcdd70693L;
3895 crc_32_tab[246]= 0x54de5729L;
3896 crc_32_tab[247]= 0x23d967bfL;
3897 crc_32_tab[248]= 0xb3667a2eL;
3898 crc_32_tab[249]= 0xc4614ab8L;
3899 crc_32_tab[250]= 0x5d681b02L;
3900 crc_32_tab[251]= 0x2a6f2b94L;
3901 crc_32_tab[252]= 0xb40bbe37L;
3902 crc_32_tab[253]= 0xc30c8ea1L;
3903 crc_32_tab[254]= 0x5a05df1bL;
3904 crc_32_tab[255]= 0x2d02ef8dL;
3905 return;
3906 }
3907 #endif /* SUPPORT_GZIP64 */
3908
3909 /******************************************************************************
3910 * Miscellaneous...most of this could be reimplemented as global constants if
3911 * that were a "safe" thing to do considering that the routines in this file
3912 * are part of a shareable library.
3913 ******************************************************************************/
3914
3915 #if 0
3916 config configuration_table[10] = {
3917 /* good lazy nice chain */
3918 {0, 0, 0, 0}, /* 0 */ /* store only */
3919 {4, 4, 8, 4}, /* 1 */ /* maximum speed, no lazy matches */
3920 {4, 5, 16, 8}, /* 2 */
3921 {4, 6, 32, 32}, /* 3 */
3922 {4, 4, 16, 16}, /* 4 */ /* lazy matches */
3923 {8, 16, 32, 32}, /* 5 */
3924 {8, 16, 128, 128}, /* 6 */
3925 {8, 32, 128, 256}, /* 7 */
3926 {32, 128, 258, 1024}, /* 8 */
3927 {32, 258, 258, 4096} /* 9 */ /* maximum compression */
3928 };
3929 uch bl_order[BL_CODES] = {
3930 16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15
3931 };
3932 /* Tables for deflate from PKZIP's appnote.txt. */
3933 unsigned border[] = { /* Order of the bit length code lengths */
3934 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
3935 ush cplens[] = { /* Copy lengths for literal codes 257..285 */
3936 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
3937 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
3938 /* note: see note #13 above about the 258 in this list. */
3939 ush cplext[] = { /* Extra bits for literal codes 257..285 */
3940 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
3941 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 99, 99}; /* 99==invalid */
3942 ush cpdist[] = { /* Copy offsets for distance codes 0..29 */
3943 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
3944 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
3945 8193, 12289, 16385, 24577};
3946 ush cpdext[] = { /* Extra bits for distance codes */
3947 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
3948 7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
3949 12, 12, 13, 13};
3950 ush mask_bits[] = {
3951 0x0000,
3952 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
3953 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
3954 };
3955 int extra_lbits[LENGTH_CODES] /* extra bits for each length code */
3956 = {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};
3957 ct_data dyn_ltree[HEAP_SIZE];
3958 /* literal and length tree */
3959 ct_data static_ltree[L_CODES+2];
3960 /* The static literal tree. Since the bit lengths are imposed, there is no
3961 * need for the L_CODES extra codes used during heap construction. However
3962 * The codes 286 and 287 are needed to build a canonical tree (see ct_init
3963 * below).
3964 */
3965 tree_desc l_desc = {
3966 dyn_ltree, static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS, 0
3967 };
3968 int extra_dbits[D_CODES] /* extra bits for each distance code */
3969 = {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};
3970 ct_data dyn_dtree[2*D_CODES+1];
3971 /* distance tree */
3972 ct_data static_dtree[D_CODES];
3973 /* The static distance tree. (Actually a trivial tree since all codes use
3974 * 5 bits.)
3975 */
3976 tree_desc d_desc = {
3977 dyn_dtree, static_dtree, extra_dbits, 0, D_CODES, MAX_BITS, 0
3978 };
3979 int extra_blbits[BL_CODES]/* extra bits for each bit length code */
3980 = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7};
3981 ct_data bl_tree[2*BL_CODES+1];
3982 /* Huffman tree for the bit lengths */
3983 tree_desc bl_desc = {
3984 bl_tree, (ct_data *) NULL, extra_blbits, 0, BL_CODES, MAX_BL_BITS, 0
3985 };
3986 /* ========================================================================
3987 * Table of CRC-32's of all single-byte values (made by makecrc.c)
3988 */
3989 ulg crc_32_tab[] = {
3990 0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L,
3991 0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0x0edb8832L, 0x79dcb8a4L,
3992 0xe0d5e91eL, 0x97d2d988L, 0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L,
3993 0x90bf1d91L, 0x1db71064L, 0x6ab020f2L, 0xf3b97148L, 0x84be41deL,
3994 0x1adad47dL, 0x6ddde4ebL, 0xf4d4b551L, 0x83d385c7L, 0x136c9856L,
3995 0x646ba8c0L, 0xfd62f97aL, 0x8a65c9ecL, 0x14015c4fL, 0x63066cd9L,
3996 0xfa0f3d63L, 0x8d080df5L, 0x3b6e20c8L, 0x4c69105eL, 0xd56041e4L,
3997 0xa2677172L, 0x3c03e4d1L, 0x4b04d447L, 0xd20d85fdL, 0xa50ab56bL,
3998 0x35b5a8faL, 0x42b2986cL, 0xdbbbc9d6L, 0xacbcf940L, 0x32d86ce3L,
3999 0x45df5c75L, 0xdcd60dcfL, 0xabd13d59L, 0x26d930acL, 0x51de003aL,
4000 0xc8d75180L, 0xbfd06116L, 0x21b4f4b5L, 0x56b3c423L, 0xcfba9599L,
4001 0xb8bda50fL, 0x2802b89eL, 0x5f058808L, 0xc60cd9b2L, 0xb10be924L,
4002 0x2f6f7c87L, 0x58684c11L, 0xc1611dabL, 0xb6662d3dL, 0x76dc4190L,
4003 0x01db7106L, 0x98d220bcL, 0xefd5102aL, 0x71b18589L, 0x06b6b51fL,
4004 0x9fbfe4a5L, 0xe8b8d433L, 0x7807c9a2L, 0x0f00f934L, 0x9609a88eL,
4005 0xe10e9818L, 0x7f6a0dbbL, 0x086d3d2dL, 0x91646c97L, 0xe6635c01L,
4006 0x6b6b51f4L, 0x1c6c6162L, 0x856530d8L, 0xf262004eL, 0x6c0695edL,
4007 0x1b01a57bL, 0x8208f4c1L, 0xf50fc457L, 0x65b0d9c6L, 0x12b7e950L,
4008 0x8bbeb8eaL, 0xfcb9887cL, 0x62dd1ddfL, 0x15da2d49L, 0x8cd37cf3L,
4009 0xfbd44c65L, 0x4db26158L, 0x3ab551ceL, 0xa3bc0074L, 0xd4bb30e2L,
4010 0x4adfa541L, 0x3dd895d7L, 0xa4d1c46dL, 0xd3d6f4fbL, 0x4369e96aL,
4011 0x346ed9fcL, 0xad678846L, 0xda60b8d0L, 0x44042d73L, 0x33031de5L,
4012 0xaa0a4c5fL, 0xdd0d7cc9L, 0x5005713cL, 0x270241aaL, 0xbe0b1010L,
4013 0xc90c2086L, 0x5768b525L, 0x206f85b3L, 0xb966d409L, 0xce61e49fL,
4014 0x5edef90eL, 0x29d9c998L, 0xb0d09822L, 0xc7d7a8b4L, 0x59b33d17L,
4015 0x2eb40d81L, 0xb7bd5c3bL, 0xc0ba6cadL, 0xedb88320L, 0x9abfb3b6L,
4016 0x03b6e20cL, 0x74b1d29aL, 0xead54739L, 0x9dd277afL, 0x04db2615L,
4017 0x73dc1683L, 0xe3630b12L, 0x94643b84L, 0x0d6d6a3eL, 0x7a6a5aa8L,
4018 0xe40ecf0bL, 0x9309ff9dL, 0x0a00ae27L, 0x7d079eb1L, 0xf00f9344L,
4019 0x8708a3d2L, 0x1e01f268L, 0x6906c2feL, 0xf762575dL, 0x806567cbL,
4020 0x196c3671L, 0x6e6b06e7L, 0xfed41b76L, 0x89d32be0L, 0x10da7a5aL,
4021 0x67dd4accL, 0xf9b9df6fL, 0x8ebeeff9L, 0x17b7be43L, 0x60b08ed5L,
4022 0xd6d6a3e8L, 0xa1d1937eL, 0x38d8c2c4L, 0x4fdff252L, 0xd1bb67f1L,
4023 0xa6bc5767L, 0x3fb506ddL, 0x48b2364bL, 0xd80d2bdaL, 0xaf0a1b4cL,
4024 0x36034af6L, 0x41047a60L, 0xdf60efc3L, 0xa867df55L, 0x316e8eefL,
4025 0x4669be79L, 0xcb61b38cL, 0xbc66831aL, 0x256fd2a0L, 0x5268e236L,
4026 0xcc0c7795L, 0xbb0b4703L, 0x220216b9L, 0x5505262fL, 0xc5ba3bbeL,
4027 0xb2bd0b28L, 0x2bb45a92L, 0x5cb36a04L, 0xc2d7ffa7L, 0xb5d0cf31L,
4028 0x2cd99e8bL, 0x5bdeae1dL, 0x9b64c2b0L, 0xec63f226L, 0x756aa39cL,
4029 0x026d930aL, 0x9c0906a9L, 0xeb0e363fL, 0x72076785L, 0x05005713L,
4030 0x95bf4a82L, 0xe2b87a14L, 0x7bb12baeL, 0x0cb61b38L, 0x92d28e9bL,
4031 0xe5d5be0dL, 0x7cdcefb7L, 0x0bdbdf21L, 0x86d3d2d4L, 0xf1d4e242L,
4032 0x68ddb3f8L, 0x1fda836eL, 0x81be16cdL, 0xf6b9265bL, 0x6fb077e1L,
4033 0x18b74777L, 0x88085ae6L, 0xff0f6a70L, 0x66063bcaL, 0x11010b5cL,
4034 0x8f659effL, 0xf862ae69L, 0x616bffd3L, 0x166ccf45L, 0xa00ae278L,
4035 0xd70dd2eeL, 0x4e048354L, 0x3903b3c2L, 0xa7672661L, 0xd06016f7L,
4036 0x4969474dL, 0x3e6e77dbL, 0xaed16a4aL, 0xd9d65adcL, 0x40df0b66L,
4037 0x37d83bf0L, 0xa9bcae53L, 0xdebb9ec5L, 0x47b2cf7fL, 0x30b5ffe9L,
4038 0xbdbdf21cL, 0xcabac28aL, 0x53b39330L, 0x24b4a3a6L, 0xbad03605L,
4039 0xcdd70693L, 0x54de5729L, 0x23d967bfL, 0xb3667a2eL, 0xc4614ab8L,
4040 0x5d681b02L, 0x2a6f2b94L, 0xb40bbe37L, 0xc30c8ea1L, 0x5a05df1bL,
4041 0x2d02ef8dL
4042 };
4043 #endif
4044