1 /* 2 * This file is derived from various .h and .c files from the zlib-1.0.4 3 * distribution by Jean-loup Gailly and Mark Adler, with some additions 4 * by Paul Mackerras to aid in implementing Deflate compression and 5 * decompression for PPP packets. See zlib.h for conditions of 6 * distribution and use. 7 * 8 * Changes that have been made include: 9 * - added Z_PACKET_FLUSH (see zlib.h for details) 10 * - added inflateIncomp and deflateOutputPending 11 * - allow strm->next_out to be NULL, meaning discard the output 12 * 13 * $FreeBSD: src/sys/net/zlib.c,v 1.10.2.3 2002/03/24 23:12:48 jedgar Exp $ 14 * $DragonFly: src/sys/net/zlib.c,v 1.11 2007/01/07 00:41:29 dillon Exp $ 15 */ 16 17 /* 18 * ==FILEVERSION 971210== 19 * 20 * This marker is used by the Linux installation script to determine 21 * whether an up-to-date version of this file is already installed. 22 */ 23 24 #define NO_DUMMY_DECL 25 #define NO_ZCFUNCS 26 #define MY_ZCALLOC 27 28 #if (defined(__DragonFly__) || defined(__FreeBSD__)) && defined(_KERNEL) 29 #define inflate inflate_ppp /* FreeBSD already has an inflate :-( */ 30 #endif 31 32 33 /* +++ zutil.h */ 34 /* zutil.h -- internal interface and configuration of the compression library 35 * Copyright (C) 1995-1996 Jean-loup Gailly. 36 * For conditions of distribution and use, see copyright notice in zlib.h 37 */ 38 39 /* WARNING: this file should *not* be used by applications. It is 40 part of the implementation of the compression library and is 41 subject to change. Applications should only use zlib.h. 42 */ 43 44 /* From: zutil.h,v 1.16 1996/07/24 13:41:13 me Exp $ */ 45 46 #ifndef _Z_UTIL_H 47 #define _Z_UTIL_H 48 49 #ifdef _KERNEL 50 #include <net/zlib.h> 51 #else 52 #include "zlib.h" 53 #endif 54 55 #ifdef _KERNEL 56 /* Assume this is a *BSD or SVR4 kernel */ 57 #include <sys/param.h> 58 #include <sys/types.h> 59 #include <sys/time.h> 60 #include <sys/systm.h> 61 # define HAVE_MEMCPY 62 # define memcpy(d, s, n) bcopy((s), (d), (n)) 63 # define memset(d, v, n) bzero((d), (n)) 64 # define memcmp bcmp 65 66 #else 67 #if defined(__KERNEL__) 68 /* Assume this is a Linux kernel */ 69 #include <linux/string.h> 70 #define HAVE_MEMCPY 71 72 #else /* not kernel */ 73 74 #if defined(MSDOS)||defined(VMS)||defined(CRAY)||defined(WIN32)||defined(RISCOS) 75 # include <stddef.h> 76 # include <errno.h> 77 #else 78 extern int errno; 79 #endif 80 #ifdef STDC 81 # include <string.h> 82 # include <stdlib.h> 83 #endif 84 #endif /* __KERNEL__ */ 85 #endif /* _KERNEL */ 86 87 #ifndef local 88 # define local static 89 #endif 90 /* compile with -Dlocal if your debugger can't find static symbols */ 91 92 typedef unsigned char uch; 93 typedef uch FAR uchf; 94 typedef unsigned short ush; 95 typedef ush FAR ushf; 96 typedef unsigned long ulg; 97 98 static const char *z_errmsg[10] = { 99 "need dictionary", /* Z_NEED_DICT 2 */ 100 "stream end", /* Z_STREAM_END 1 */ 101 "", /* Z_OK 0 */ 102 "file error", /* Z_ERRNO (-1) */ 103 "stream error", /* Z_STREAM_ERROR (-2) */ 104 "data error", /* Z_DATA_ERROR (-3) */ 105 "insufficient memory", /* Z_MEM_ERROR (-4) */ 106 "buffer error", /* Z_BUF_ERROR (-5) */ 107 "incompatible version",/* Z_VERSION_ERROR (-6) */ 108 ""}; 109 110 #define ERR_MSG(err) z_errmsg[Z_NEED_DICT-(err)] 111 112 #define ERR_RETURN(strm,err) \ 113 return (strm->msg = (const char*)ERR_MSG(err), (err)) 114 /* To be used only when the state is known to be valid */ 115 116 /* common constants */ 117 118 #ifndef DEF_WBITS 119 # define DEF_WBITS MAX_WBITS 120 #endif 121 /* default windowBits for decompression. MAX_WBITS is for compression only */ 122 123 #if MAX_MEM_LEVEL >= 8 124 # define DEF_MEM_LEVEL 8 125 #else 126 # define DEF_MEM_LEVEL MAX_MEM_LEVEL 127 #endif 128 /* default memLevel */ 129 130 #define STORED_BLOCK 0 131 #define STATIC_TREES 1 132 #define DYN_TREES 2 133 /* The three kinds of block type */ 134 135 #define MIN_MATCH 3 136 #define MAX_MATCH 258 137 /* The minimum and maximum match lengths */ 138 139 #define PRESET_DICT 0x20 /* preset dictionary flag in zlib header */ 140 141 /* target dependencies */ 142 143 #ifdef MSDOS 144 # define OS_CODE 0x00 145 # ifdef __TURBOC__ 146 # include <alloc.h> 147 # else /* MSC or DJGPP */ 148 # include <malloc.h> 149 # endif 150 #endif 151 152 #ifdef OS2 153 # define OS_CODE 0x06 154 #endif 155 156 #ifdef WIN32 /* Window 95 & Windows NT */ 157 # define OS_CODE 0x0b 158 #endif 159 160 #if defined(VAXC) || defined(VMS) 161 # define OS_CODE 0x02 162 # define FOPEN(name, mode) \ 163 fopen((name), (mode), "mbc=60", "ctx=stm", "rfm=fix", "mrs=512") 164 #endif 165 166 #ifdef AMIGA 167 # define OS_CODE 0x01 168 #endif 169 170 #if defined(ATARI) || defined(atarist) 171 # define OS_CODE 0x05 172 #endif 173 174 #ifdef MACOS 175 # define OS_CODE 0x07 176 #endif 177 178 #ifdef __50SERIES /* Prime/PRIMOS */ 179 # define OS_CODE 0x0F 180 #endif 181 182 #ifdef TOPS20 183 # define OS_CODE 0x0a 184 #endif 185 186 #if defined(_BEOS_) || defined(RISCOS) 187 # define fdopen(fd,mode) NULL /* No fdopen() */ 188 #endif 189 190 /* Common defaults */ 191 192 #ifndef OS_CODE 193 # define OS_CODE 0x03 /* assume Unix */ 194 #endif 195 196 #ifndef FOPEN 197 # define FOPEN(name, mode) fopen((name), (mode)) 198 #endif 199 200 /* functions */ 201 202 #ifdef HAVE_STRERROR 203 extern char *strerror OF((int)); 204 # define zstrerror(errnum) strerror(errnum) 205 #else 206 # define zstrerror(errnum) "" 207 #endif 208 209 #if defined(pyr) 210 # define NO_MEMCPY 211 #endif 212 #if (defined(M_I86SM) || defined(M_I86MM)) && !defined(_MSC_VER) 213 /* Use our own functions for small and medium model with MSC <= 5.0. 214 * You may have to use the same strategy for Borland C (untested). 215 */ 216 # define NO_MEMCPY 217 #endif 218 #if defined(STDC) && !defined(HAVE_MEMCPY) && !defined(NO_MEMCPY) 219 # define HAVE_MEMCPY 220 #endif 221 #ifdef HAVE_MEMCPY 222 # ifdef SMALL_MEDIUM /* MSDOS small or medium model */ 223 # define zmemcpy _fmemcpy 224 # define zmemcmp _fmemcmp 225 # define zmemzero(dest, len) _fmemset(dest, 0, len) 226 # else 227 # define zmemcpy memcpy 228 # define zmemcmp memcmp 229 # define zmemzero(dest, len) memset(dest, 0, len) 230 # endif 231 #else 232 extern void zmemcpy OF((Bytef* dest, Bytef* source, uInt len)); 233 extern int zmemcmp OF((Bytef* s1, Bytef* s2, uInt len)); 234 extern void zmemzero OF((Bytef* dest, uInt len)); 235 #endif 236 237 /* Diagnostic functions */ 238 #ifdef DEBUG_ZLIB 239 # include <stdio.h> 240 # ifndef verbose 241 # define verbose 0 242 # endif 243 extern void z_error OF((char *m)); 244 # define Assert(cond,msg) {if(!(cond)) z_error(msg);} 245 # define Trace(x) fprintf x 246 # define Tracev(x) {if (verbose) fprintf x ;} 247 # define Tracevv(x) {if (verbose>1) fprintf x ;} 248 # define Tracec(c,x) {if (verbose && (c)) fprintf x ;} 249 # define Tracecv(c,x) {if (verbose>1 && (c)) fprintf x ;} 250 #else 251 # define Assert(cond,msg) 252 # define Trace(x) 253 # define Tracev(x) 254 # define Tracevv(x) 255 # define Tracec(c,x) 256 # define Tracecv(c,x) 257 #endif 258 259 260 typedef uLong (*check_func) OF((uLong check, const Bytef *buf, uInt len)); 261 262 voidpf zcalloc OF((voidpf opaque, unsigned items, unsigned size)); 263 void zcfree OF((voidpf opaque, voidpf ptr)); 264 265 #define ZALLOC(strm, items, size) \ 266 (*((strm)->zalloc))((strm)->opaque, (items), (size)) 267 #define ZFREE(strm, addr) (*((strm)->zfree))((strm)->opaque, (voidpf)(addr)) 268 #define TRY_FREE(s, p) {if (p) ZFREE(s, p);} 269 270 #endif /* _Z_UTIL_H */ 271 /* --- zutil.h */ 272 273 /* +++ deflate.h */ 274 /* deflate.h -- internal compression state 275 * Copyright (C) 1995-1996 Jean-loup Gailly 276 * For conditions of distribution and use, see copyright notice in zlib.h 277 */ 278 279 /* WARNING: this file should *not* be used by applications. It is 280 part of the implementation of the compression library and is 281 subject to change. Applications should only use zlib.h. 282 */ 283 284 /* From: deflate.h,v 1.10 1996/07/02 12:41:00 me Exp $ */ 285 286 #ifndef _DEFLATE_H 287 #define _DEFLATE_H 288 289 /* #include "zutil.h" */ 290 291 /* =========================================================================== 292 * Internal compression state. 293 */ 294 295 #define LENGTH_CODES 29 296 /* number of length codes, not counting the special END_BLOCK code */ 297 298 #define LITERALS 256 299 /* number of literal bytes 0..255 */ 300 301 #define L_CODES (LITERALS+1+LENGTH_CODES) 302 /* number of Literal or Length codes, including the END_BLOCK code */ 303 304 #define D_CODES 30 305 /* number of distance codes */ 306 307 #define BL_CODES 19 308 /* number of codes used to transfer the bit lengths */ 309 310 #define HEAP_SIZE (2*L_CODES+1) 311 /* maximum heap size */ 312 313 #define MAX_BITS 15 314 /* All codes must not exceed MAX_BITS bits */ 315 316 #define INIT_STATE 42 317 #define BUSY_STATE 113 318 #define FINISH_STATE 666 319 /* Stream status */ 320 321 322 /* Data structure describing a single value and its code string. */ 323 typedef struct ct_data_s { 324 union { 325 ush freq; /* frequency count */ 326 ush code; /* bit string */ 327 } fc; 328 union { 329 ush dad; /* father node in Huffman tree */ 330 ush len; /* length of bit string */ 331 } dl; 332 } FAR ct_data; 333 334 #define Freq fc.freq 335 #define Code fc.code 336 #define Dad dl.dad 337 #define Len dl.len 338 339 typedef struct static_tree_desc_s static_tree_desc; 340 341 typedef struct tree_desc_s { 342 ct_data *dyn_tree; /* the dynamic tree */ 343 int max_code; /* largest code with non zero frequency */ 344 static_tree_desc *stat_desc; /* the corresponding static tree */ 345 } FAR tree_desc; 346 347 typedef ush Pos; 348 typedef Pos FAR Posf; 349 typedef unsigned IPos; 350 351 /* A Pos is an index in the character window. We use short instead of int to 352 * save space in the various tables. IPos is used only for parameter passing. 353 */ 354 355 typedef struct deflate_state { 356 z_streamp strm; /* pointer back to this zlib stream */ 357 int status; /* as the name implies */ 358 Bytef *pending_buf; /* output still pending */ 359 ulg pending_buf_size; /* size of pending_buf */ 360 Bytef *pending_out; /* next pending byte to output to the stream */ 361 int pending; /* nb of bytes in the pending buffer */ 362 int noheader; /* suppress zlib header and adler32 */ 363 Byte data_type; /* UNKNOWN, BINARY or ASCII */ 364 Byte method; /* STORED (for zip only) or DEFLATED */ 365 int last_flush; /* value of flush param for previous deflate call */ 366 367 /* used by deflate.c: */ 368 369 uInt w_size; /* LZ77 window size (32K by default) */ 370 uInt w_bits; /* log2(w_size) (8..16) */ 371 uInt w_mask; /* w_size - 1 */ 372 373 Bytef *window; 374 /* Sliding window. Input bytes are read into the second half of the window, 375 * and move to the first half later to keep a dictionary of at least wSize 376 * bytes. With this organization, matches are limited to a distance of 377 * wSize-MAX_MATCH bytes, but this ensures that IO is always 378 * performed with a length multiple of the block size. Also, it limits 379 * the window size to 64K, which is quite useful on MSDOS. 380 * To do: use the user input buffer as sliding window. 381 */ 382 383 ulg window_size; 384 /* Actual size of window: 2*wSize, except when the user input buffer 385 * is directly used as sliding window. 386 */ 387 388 Posf *prev; 389 /* Link to older string with same hash index. To limit the size of this 390 * array to 64K, this link is maintained only for the last 32K strings. 391 * An index in this array is thus a window index modulo 32K. 392 */ 393 394 Posf *head; /* Heads of the hash chains or NIL. */ 395 396 uInt ins_h; /* hash index of string to be inserted */ 397 uInt hash_size; /* number of elements in hash table */ 398 uInt hash_bits; /* log2(hash_size) */ 399 uInt hash_mask; /* hash_size-1 */ 400 401 uInt hash_shift; 402 /* Number of bits by which ins_h must be shifted at each input 403 * step. It must be such that after MIN_MATCH steps, the oldest 404 * byte no longer takes part in the hash key, that is: 405 * hash_shift * MIN_MATCH >= hash_bits 406 */ 407 408 long block_start; 409 /* Window position at the beginning of the current output block. Gets 410 * negative when the window is moved backwards. 411 */ 412 413 uInt match_length; /* length of best match */ 414 IPos prev_match; /* previous match */ 415 int match_available; /* set if previous match exists */ 416 uInt strstart; /* start of string to insert */ 417 uInt match_start; /* start of matching string */ 418 uInt lookahead; /* number of valid bytes ahead in window */ 419 420 uInt prev_length; 421 /* Length of the best match at previous step. Matches not greater than this 422 * are discarded. This is used in the lazy match evaluation. 423 */ 424 425 uInt max_chain_length; 426 /* To speed up deflation, hash chains are never searched beyond this 427 * length. A higher limit improves compression ratio but degrades the 428 * speed. 429 */ 430 431 uInt max_lazy_match; 432 /* Attempt to find a better match only when the current match is strictly 433 * smaller than this value. This mechanism is used only for compression 434 * levels >= 4. 435 */ 436 # define max_insert_length max_lazy_match 437 /* Insert new strings in the hash table only if the match length is not 438 * greater than this length. This saves time but degrades compression. 439 * max_insert_length is used only for compression levels <= 3. 440 */ 441 442 int level; /* compression level (1..9) */ 443 int strategy; /* favor or force Huffman coding*/ 444 445 uInt good_match; 446 /* Use a faster search when the previous match is longer than this */ 447 448 int nice_match; /* Stop searching when current match exceeds this */ 449 450 /* used by trees.c: */ 451 /* Didn't use ct_data typedef below to supress compiler warning */ 452 struct ct_data_s dyn_ltree[HEAP_SIZE]; /* literal and length tree */ 453 struct ct_data_s dyn_dtree[2*D_CODES+1]; /* distance tree */ 454 struct ct_data_s bl_tree[2*BL_CODES+1]; /* Huffman tree for bit lengths */ 455 456 struct tree_desc_s l_desc; /* desc. for literal tree */ 457 struct tree_desc_s d_desc; /* desc. for distance tree */ 458 struct tree_desc_s bl_desc; /* desc. for bit length tree */ 459 460 ush bl_count[MAX_BITS+1]; 461 /* number of codes at each bit length for an optimal tree */ 462 463 int heap[2*L_CODES+1]; /* heap used to build the Huffman trees */ 464 int heap_len; /* number of elements in the heap */ 465 int heap_max; /* element of largest frequency */ 466 /* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used. 467 * The same heap array is used to build all trees. 468 */ 469 470 uch depth[2*L_CODES+1]; 471 /* Depth of each subtree used as tie breaker for trees of equal frequency 472 */ 473 474 uchf *l_buf; /* buffer for literals or lengths */ 475 476 uInt lit_bufsize; 477 /* Size of match buffer for literals/lengths. There are 4 reasons for 478 * limiting lit_bufsize to 64K: 479 * - frequencies can be kept in 16 bit counters 480 * - if compression is not successful for the first block, all input 481 * data is still in the window so we can still emit a stored block even 482 * when input comes from standard input. (This can also be done for 483 * all blocks if lit_bufsize is not greater than 32K.) 484 * - if compression is not successful for a file smaller than 64K, we can 485 * even emit a stored file instead of a stored block (saving 5 bytes). 486 * This is applicable only for zip (not gzip or zlib). 487 * - creating new Huffman trees less frequently may not provide fast 488 * adaptation to changes in the input data statistics. (Take for 489 * example a binary file with poorly compressible code followed by 490 * a highly compressible string table.) Smaller buffer sizes give 491 * fast adaptation but have of course the overhead of transmitting 492 * trees more frequently. 493 * - I can't count above 4 494 */ 495 496 uInt last_lit; /* running index in l_buf */ 497 498 ushf *d_buf; 499 /* Buffer for distances. To simplify the code, d_buf and l_buf have 500 * the same number of elements. To use different lengths, an extra flag 501 * array would be necessary. 502 */ 503 504 ulg opt_len; /* bit length of current block with optimal trees */ 505 ulg static_len; /* bit length of current block with static trees */ 506 ulg compressed_len; /* total bit length of compressed file */ 507 uInt matches; /* number of string matches in current block */ 508 int last_eob_len; /* bit length of EOB code for last block */ 509 510 #ifdef DEBUG_ZLIB 511 ulg bits_sent; /* bit length of the compressed data */ 512 #endif 513 514 ush bi_buf; 515 /* Output buffer. bits are inserted starting at the bottom (least 516 * significant bits). 517 */ 518 int bi_valid; 519 /* Number of valid bits in bi_buf. All bits above the last valid bit 520 * are always zero. 521 */ 522 523 } FAR deflate_state; 524 525 /* Output a byte on the stream. 526 * IN assertion: there is enough room in pending_buf. 527 */ 528 #define put_byte(s, c) {s->pending_buf[s->pending++] = (c);} 529 530 531 #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1) 532 /* Minimum amount of lookahead, except at the end of the input file. 533 * See deflate.c for comments about the MIN_MATCH+1. 534 */ 535 536 #define MAX_DIST(s) ((s)->w_size-MIN_LOOKAHEAD) 537 /* In order to simplify the code, particularly on 16 bit machines, match 538 * distances are limited to MAX_DIST instead of WSIZE. 539 */ 540 541 /* in trees.c */ 542 void _tr_init OF((deflate_state *s)); 543 int _tr_tally OF((deflate_state *s, unsigned dist, unsigned lc)); 544 ulg _tr_flush_block OF((deflate_state *s, charf *buf, ulg stored_len, 545 int eof)); 546 void _tr_align OF((deflate_state *s)); 547 void _tr_stored_block OF((deflate_state *s, charf *buf, ulg stored_len, 548 int eof)); 549 void _tr_stored_type_only OF((deflate_state *)); 550 551 #endif 552 /* --- deflate.h */ 553 554 /* +++ deflate.c */ 555 /* deflate.c -- compress data using the deflation algorithm 556 * Copyright (C) 1995-1996 Jean-loup Gailly. 557 * For conditions of distribution and use, see copyright notice in zlib.h 558 */ 559 560 /* 561 * ALGORITHM 562 * 563 * The "deflation" process depends on being able to identify portions 564 * of the input text which are identical to earlier input (within a 565 * sliding window trailing behind the input currently being processed). 566 * 567 * The most straightforward technique turns out to be the fastest for 568 * most input files: try all possible matches and select the longest. 569 * The key feature of this algorithm is that insertions into the string 570 * dictionary are very simple and thus fast, and deletions are avoided 571 * completely. Insertions are performed at each input character, whereas 572 * string matches are performed only when the previous match ends. So it 573 * is preferable to spend more time in matches to allow very fast string 574 * insertions and avoid deletions. The matching algorithm for small 575 * strings is inspired from that of Rabin & Karp. A brute force approach 576 * is used to find longer strings when a small match has been found. 577 * A similar algorithm is used in comic (by Jan-Mark Wams) and freeze 578 * (by Leonid Broukhis). 579 * A previous version of this file used a more sophisticated algorithm 580 * (by Fiala and Greene) which is guaranteed to run in linear amortized 581 * time, but has a larger average cost, uses more memory and is patented. 582 * However the F&G algorithm may be faster for some highly redundant 583 * files if the parameter max_chain_length (described below) is too large. 584 * 585 * ACKNOWLEDGEMENTS 586 * 587 * The idea of lazy evaluation of matches is due to Jan-Mark Wams, and 588 * I found it in 'freeze' written by Leonid Broukhis. 589 * Thanks to many people for bug reports and testing. 590 * 591 * REFERENCES 592 * 593 * Deutsch, L.P.,"DEFLATE Compressed Data Format Specification". 594 * Available in ftp://ds.internic.net/rfc/rfc1951.txt 595 * 596 * A description of the Rabin and Karp algorithm is given in the book 597 * "Algorithms" by R. Sedgewick, Addison-Wesley, p252. 598 * 599 * Fiala,E.R., and Greene,D.H. 600 * Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595 601 * 602 */ 603 604 /* From: deflate.c,v 1.15 1996/07/24 13:40:58 me Exp $ */ 605 606 /* #include "deflate.h" */ 607 608 char deflate_copyright[] = " deflate 1.0.4 Copyright 1995-1996 Jean-loup Gailly "; 609 /* 610 If you use the zlib library in a product, an acknowledgment is welcome 611 in the documentation of your product. If for some reason you cannot 612 include such an acknowledgment, I would appreciate that you keep this 613 copyright string in the executable of your product. 614 */ 615 616 /* =========================================================================== 617 * Function prototypes. 618 */ 619 typedef enum { 620 need_more, /* block not completed, need more input or more output */ 621 block_done, /* block flush performed */ 622 finish_started, /* finish started, need only more output at next deflate */ 623 finish_done /* finish done, accept no more input or output */ 624 } block_state; 625 626 typedef block_state (*compress_func) OF((deflate_state *s, int flush)); 627 /* Compression function. Returns the block state after the call. */ 628 629 local void fill_window OF((deflate_state *s)); 630 local block_state deflate_stored OF((deflate_state *s, int flush)); 631 local block_state deflate_fast OF((deflate_state *s, int flush)); 632 local block_state deflate_slow OF((deflate_state *s, int flush)); 633 local void lm_init OF((deflate_state *s)); 634 local void putShortMSB OF((deflate_state *s, uInt b)); 635 local void flush_pending OF((z_streamp strm)); 636 local int read_buf OF((z_streamp strm, charf *buf, unsigned size)); 637 #ifdef ASMV 638 void match_init OF((void)); /* asm code initialization */ 639 uInt longest_match OF((deflate_state *s, IPos cur_match)); 640 #else 641 local uInt longest_match OF((deflate_state *s, IPos cur_match)); 642 #endif 643 644 #ifdef DEBUG_ZLIB 645 local void check_match OF((deflate_state *s, IPos start, IPos match, 646 int length)); 647 #endif 648 649 /* =========================================================================== 650 * Local data 651 */ 652 653 #define NIL 0 654 /* Tail of hash chains */ 655 656 #ifndef TOO_FAR 657 # define TOO_FAR 4096 658 #endif 659 /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */ 660 661 #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1) 662 /* Minimum amount of lookahead, except at the end of the input file. 663 * See deflate.c for comments about the MIN_MATCH+1. 664 */ 665 666 /* Values for max_lazy_match, good_match and max_chain_length, depending on 667 * the desired pack level (0..9). The values given below have been tuned to 668 * exclude worst case performance for pathological files. Better values may be 669 * found for specific files. 670 */ 671 typedef struct config_s { 672 ush good_length; /* reduce lazy search above this match length */ 673 ush max_lazy; /* do not perform lazy search above this match length */ 674 ush nice_length; /* quit search above this match length */ 675 ush max_chain; 676 compress_func func; 677 } config; 678 679 local config configuration_table[10] = { 680 /* good lazy nice chain */ 681 /* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */ 682 /* 1 */ {4, 4, 8, 4, deflate_fast}, /* maximum speed, no lazy matches */ 683 /* 2 */ {4, 5, 16, 8, deflate_fast}, 684 /* 3 */ {4, 6, 32, 32, deflate_fast}, 685 686 /* 4 */ {4, 4, 16, 16, deflate_slow}, /* lazy matches */ 687 /* 5 */ {8, 16, 32, 32, deflate_slow}, 688 /* 6 */ {8, 16, 128, 128, deflate_slow}, 689 /* 7 */ {8, 32, 128, 256, deflate_slow}, 690 /* 8 */ {32, 128, 258, 1024, deflate_slow}, 691 /* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* maximum compression */ 692 693 /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4 694 * For deflate_fast() (levels <= 3) good is ignored and lazy has a different 695 * meaning. 696 */ 697 698 #define EQUAL 0 699 /* result of memcmp for equal strings */ 700 701 #ifndef NO_DUMMY_DECL 702 struct static_tree_desc_s {int dummy;}; /* for buggy compilers */ 703 #endif 704 705 /* =========================================================================== 706 * Update a hash value with the given input byte 707 * IN assertion: all calls to to UPDATE_HASH are made with consecutive 708 * input characters, so that a running hash key can be computed from the 709 * previous key instead of complete recalculation each time. 710 */ 711 #define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask) 712 713 714 /* =========================================================================== 715 * Insert string str in the dictionary and set match_head to the previous head 716 * of the hash chain (the most recent string with same hash key). Return 717 * the previous length of the hash chain. 718 * IN assertion: all calls to to INSERT_STRING are made with consecutive 719 * input characters and the first MIN_MATCH bytes of str are valid 720 * (except for the last MIN_MATCH-1 bytes of the input file). 721 */ 722 #define INSERT_STRING(s, str, match_head) \ 723 (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \ 724 s->prev[(str) & s->w_mask] = match_head = s->head[s->ins_h], \ 725 s->head[s->ins_h] = (Pos)(str)) 726 727 /* =========================================================================== 728 * Initialize the hash table (avoiding 64K overflow for 16 bit systems). 729 * prev[] will be initialized on the fly. 730 */ 731 #define CLEAR_HASH(s) \ 732 s->head[s->hash_size-1] = NIL; \ 733 zmemzero((charf *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head)); 734 735 /* ========================================================================= */ 736 int 737 deflateInit_(z_streamp strm, int level, const char * version, 738 int stream_size) 739 { 740 return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL, 741 Z_DEFAULT_STRATEGY, version, stream_size); 742 /* To do: ignore strm->next_in if we use it as window */ 743 } 744 745 /* ========================================================================= */ 746 int 747 deflateInit2_(z_streamp strm, int level, int method, int windowBits, 748 int memLevel, int strategy, const char *version, 749 int stream_size) 750 { 751 deflate_state *s; 752 int noheader = 0; 753 static char* my_version = ZLIB_VERSION; 754 755 ushf *overlay; 756 /* We overlay pending_buf and d_buf+l_buf. This works since the average 757 * output size for (length,distance) codes is <= 24 bits. 758 */ 759 760 if (version == Z_NULL || version[0] != my_version[0] || 761 stream_size != sizeof(z_stream)) { 762 return Z_VERSION_ERROR; 763 } 764 if (strm == Z_NULL) return Z_STREAM_ERROR; 765 766 strm->msg = Z_NULL; 767 #ifndef NO_ZCFUNCS 768 if (strm->zalloc == Z_NULL) { 769 strm->zalloc = zcalloc; 770 strm->opaque = (voidpf)0; 771 } 772 if (strm->zfree == Z_NULL) strm->zfree = zcfree; 773 #endif 774 775 if (level == Z_DEFAULT_COMPRESSION) level = 6; 776 777 if (windowBits < 0) { /* undocumented feature: suppress zlib header */ 778 noheader = 1; 779 windowBits = -windowBits; 780 } 781 if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED || 782 windowBits < 9 || windowBits > 15 || level < 0 || level > 9 || 783 strategy < 0 || strategy > Z_HUFFMAN_ONLY) { 784 return Z_STREAM_ERROR; 785 } 786 s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state)); 787 if (s == Z_NULL) return Z_MEM_ERROR; 788 strm->state = (struct internal_state FAR *)s; 789 s->strm = strm; 790 791 s->noheader = noheader; 792 s->w_bits = windowBits; 793 s->w_size = 1 << s->w_bits; 794 s->w_mask = s->w_size - 1; 795 796 s->hash_bits = memLevel + 7; 797 s->hash_size = 1 << s->hash_bits; 798 s->hash_mask = s->hash_size - 1; 799 s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH); 800 801 s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte)); 802 s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos)); 803 s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos)); 804 805 s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */ 806 807 overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2); 808 s->pending_buf = (uchf *) overlay; 809 s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L); 810 811 if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL || 812 s->pending_buf == Z_NULL) { 813 strm->msg = (const char*)ERR_MSG(Z_MEM_ERROR); 814 deflateEnd (strm); 815 return Z_MEM_ERROR; 816 } 817 s->d_buf = overlay + s->lit_bufsize/sizeof(ush); 818 s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize; 819 820 s->level = level; 821 s->strategy = strategy; 822 s->method = (Byte)method; 823 824 return deflateReset(strm); 825 } 826 827 /* ========================================================================= */ 828 int 829 deflateSetDictionary(z_streamp strm, const Bytef *dictionary, uInt dictLength) 830 { 831 deflate_state *s; 832 uInt length = dictLength; 833 uInt n; 834 IPos hash_head = 0; 835 836 if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL) 837 return Z_STREAM_ERROR; 838 839 s = (deflate_state *) strm->state; 840 if (s->status != INIT_STATE) return Z_STREAM_ERROR; 841 842 strm->adler = adler32(strm->adler, dictionary, dictLength); 843 844 if (length < MIN_MATCH) return Z_OK; 845 if (length > MAX_DIST(s)) { 846 length = MAX_DIST(s); 847 #ifndef USE_DICT_HEAD 848 dictionary += dictLength - length; /* use the tail of the dictionary */ 849 #endif 850 } 851 zmemcpy((charf *)s->window, dictionary, length); 852 s->strstart = length; 853 s->block_start = (long)length; 854 855 /* Insert all strings in the hash table (except for the last two bytes). 856 * s->lookahead stays null, so s->ins_h will be recomputed at the next 857 * call of fill_window. 858 */ 859 s->ins_h = s->window[0]; 860 UPDATE_HASH(s, s->ins_h, s->window[1]); 861 for (n = 0; n <= length - MIN_MATCH; n++) { 862 INSERT_STRING(s, n, hash_head); 863 } 864 if (hash_head) hash_head = 0; /* to make compiler happy */ 865 return Z_OK; 866 } 867 868 /* ========================================================================= */ 869 int 870 deflateReset(z_streamp strm) 871 { 872 deflate_state *s; 873 874 if (strm == Z_NULL || strm->state == Z_NULL || 875 strm->zalloc == Z_NULL || strm->zfree == Z_NULL) return Z_STREAM_ERROR; 876 877 strm->total_in = strm->total_out = 0; 878 strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */ 879 strm->data_type = Z_UNKNOWN; 880 881 s = (deflate_state *)strm->state; 882 s->pending = 0; 883 s->pending_out = s->pending_buf; 884 885 if (s->noheader < 0) { 886 s->noheader = 0; /* was set to -1 by deflate(..., Z_FINISH); */ 887 } 888 s->status = s->noheader ? BUSY_STATE : INIT_STATE; 889 strm->adler = 1; 890 s->last_flush = Z_NO_FLUSH; 891 892 _tr_init(s); 893 lm_init(s); 894 895 return Z_OK; 896 } 897 898 /* ========================================================================= */ 899 int 900 deflateParams(z_streamp strm, int level, int strategy) 901 { 902 deflate_state *s; 903 compress_func func; 904 int err = Z_OK; 905 906 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 907 s = (deflate_state *) strm->state; 908 909 if (level == Z_DEFAULT_COMPRESSION) { 910 level = 6; 911 } 912 if (level < 0 || level > 9 || strategy < 0 || strategy > Z_HUFFMAN_ONLY) { 913 return Z_STREAM_ERROR; 914 } 915 func = configuration_table[s->level].func; 916 917 if (func != configuration_table[level].func && strm->total_in != 0) { 918 /* Flush the last buffer: */ 919 err = deflate(strm, Z_PARTIAL_FLUSH); 920 } 921 if (s->level != level) { 922 s->level = level; 923 s->max_lazy_match = configuration_table[level].max_lazy; 924 s->good_match = configuration_table[level].good_length; 925 s->nice_match = configuration_table[level].nice_length; 926 s->max_chain_length = configuration_table[level].max_chain; 927 } 928 s->strategy = strategy; 929 return err; 930 } 931 932 /* ========================================================================= 933 * Put a short in the pending buffer. The 16-bit value is put in MSB order. 934 * IN assertion: the stream state is correct and there is enough room in 935 * pending_buf. 936 */ 937 local void 938 putShortMSB(deflate_state *s, uInt b) 939 { 940 put_byte(s, (Byte)(b >> 8)); 941 put_byte(s, (Byte)(b & 0xff)); 942 } 943 944 /* ========================================================================= 945 * Flush as much pending output as possible. All deflate() output goes 946 * through this function so some applications may wish to modify it 947 * to avoid allocating a large strm->next_out buffer and copying into it. 948 * (See also read_buf()). 949 */ 950 local void 951 flush_pending(z_streamp strm) 952 { 953 deflate_state *s = (deflate_state *) strm->state; 954 unsigned len = s->pending; 955 956 if (len > strm->avail_out) len = strm->avail_out; 957 if (len == 0) return; 958 959 if (strm->next_out != Z_NULL) { 960 zmemcpy(strm->next_out, s->pending_out, len); 961 strm->next_out += len; 962 } 963 s->pending_out += len; 964 strm->total_out += len; 965 strm->avail_out -= len; 966 s->pending -= len; 967 if (s->pending == 0) { 968 s->pending_out = s->pending_buf; 969 } 970 } 971 972 /* ========================================================================= */ 973 int 974 deflate(z_streamp strm, int flush) 975 { 976 int old_flush; /* value of flush param for previous deflate call */ 977 deflate_state *s; 978 979 if (strm == Z_NULL || strm->state == Z_NULL || 980 flush > Z_FINISH || flush < 0) { 981 return Z_STREAM_ERROR; 982 } 983 s = (deflate_state *) strm->state; 984 985 if ((strm->next_in == Z_NULL && strm->avail_in != 0) || 986 (s->status == FINISH_STATE && flush != Z_FINISH)) { 987 ERR_RETURN(strm, Z_STREAM_ERROR); 988 } 989 if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR); 990 991 s->strm = strm; /* just in case */ 992 old_flush = s->last_flush; 993 s->last_flush = flush; 994 995 /* Write the zlib header */ 996 if (s->status == INIT_STATE) { 997 998 uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8; 999 uInt level_flags = (s->level-1) >> 1; 1000 1001 if (level_flags > 3) level_flags = 3; 1002 header |= (level_flags << 6); 1003 if (s->strstart != 0) header |= PRESET_DICT; 1004 header += 31 - (header % 31); 1005 1006 s->status = BUSY_STATE; 1007 putShortMSB(s, header); 1008 1009 /* Save the adler32 of the preset dictionary: */ 1010 if (s->strstart != 0) { 1011 putShortMSB(s, (uInt)(strm->adler >> 16)); 1012 putShortMSB(s, (uInt)(strm->adler & 0xffff)); 1013 } 1014 strm->adler = 1L; 1015 } 1016 1017 /* Flush as much pending output as possible */ 1018 if (s->pending != 0) { 1019 flush_pending(strm); 1020 if (strm->avail_out == 0) { 1021 /* Since avail_out is 0, deflate will be called again with 1022 * more output space, but possibly with both pending and 1023 * avail_in equal to zero. There won't be anything to do, 1024 * but this is not an error situation so make sure we 1025 * return OK instead of BUF_ERROR at next call of deflate: 1026 */ 1027 s->last_flush = -1; 1028 return Z_OK; 1029 } 1030 1031 /* Make sure there is something to do and avoid duplicate consecutive 1032 * flushes. For repeated and useless calls with Z_FINISH, we keep 1033 * returning Z_STREAM_END instead of Z_BUFF_ERROR. 1034 */ 1035 } else if (strm->avail_in == 0 && flush <= old_flush && 1036 flush != Z_FINISH) { 1037 ERR_RETURN(strm, Z_BUF_ERROR); 1038 } 1039 1040 /* User must not provide more input after the first FINISH: */ 1041 if (s->status == FINISH_STATE && strm->avail_in != 0) { 1042 ERR_RETURN(strm, Z_BUF_ERROR); 1043 } 1044 1045 /* Start a new block or continue the current one. 1046 */ 1047 if (strm->avail_in != 0 || s->lookahead != 0 || 1048 (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) { 1049 block_state bstate; 1050 1051 bstate = (*(configuration_table[s->level].func))(s, flush); 1052 1053 if (bstate == finish_started || bstate == finish_done) { 1054 s->status = FINISH_STATE; 1055 } 1056 if (bstate == need_more || bstate == finish_started) { 1057 if (strm->avail_out == 0) { 1058 s->last_flush = -1; /* avoid BUF_ERROR next call, see above */ 1059 } 1060 return Z_OK; 1061 /* If flush != Z_NO_FLUSH && avail_out == 0, the next call 1062 * of deflate should use the same flush parameter to make sure 1063 * that the flush is complete. So we don't have to output an 1064 * empty block here, this will be done at next call. This also 1065 * ensures that for a very small output buffer, we emit at most 1066 * one empty block. 1067 */ 1068 } 1069 if (bstate == block_done) { 1070 if (flush == Z_PARTIAL_FLUSH) { 1071 _tr_align(s); 1072 } else if (flush == Z_PACKET_FLUSH) { 1073 /* Output just the 3-bit `stored' block type value, 1074 but not a zero length. */ 1075 _tr_stored_type_only(s); 1076 } else { /* FULL_FLUSH or SYNC_FLUSH */ 1077 _tr_stored_block(s, NULL, 0L, 0); 1078 /* For a full flush, this empty block will be recognized 1079 * as a special marker by inflate_sync(). 1080 */ 1081 if (flush == Z_FULL_FLUSH) { 1082 CLEAR_HASH(s); /* forget history */ 1083 } 1084 } 1085 flush_pending(strm); 1086 if (strm->avail_out == 0) { 1087 s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */ 1088 return Z_OK; 1089 } 1090 } 1091 } 1092 Assert(strm->avail_out > 0, "bug2"); 1093 1094 if (flush != Z_FINISH) return Z_OK; 1095 if (s->noheader) return Z_STREAM_END; 1096 1097 /* Write the zlib trailer (adler32) */ 1098 putShortMSB(s, (uInt)(strm->adler >> 16)); 1099 putShortMSB(s, (uInt)(strm->adler & 0xffff)); 1100 flush_pending(strm); 1101 /* If avail_out is zero, the application will call deflate again 1102 * to flush the rest. 1103 */ 1104 s->noheader = -1; /* write the trailer only once! */ 1105 return s->pending != 0 ? Z_OK : Z_STREAM_END; 1106 } 1107 1108 /* ========================================================================= */ 1109 int 1110 deflateEnd(z_streamp strm) 1111 { 1112 int status; 1113 deflate_state *s; 1114 1115 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1116 s = (deflate_state *) strm->state; 1117 1118 status = s->status; 1119 if (status != INIT_STATE && status != BUSY_STATE && 1120 status != FINISH_STATE) { 1121 return Z_STREAM_ERROR; 1122 } 1123 1124 /* Deallocate in reverse order of allocations: */ 1125 TRY_FREE(strm, s->pending_buf); 1126 TRY_FREE(strm, s->head); 1127 TRY_FREE(strm, s->prev); 1128 TRY_FREE(strm, s->window); 1129 1130 ZFREE(strm, s); 1131 strm->state = Z_NULL; 1132 1133 return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK; 1134 } 1135 1136 /* ========================================================================= 1137 * Copy the source state to the destination state. 1138 */ 1139 int 1140 deflateCopy(z_streamp dest, z_streamp source) 1141 { 1142 deflate_state *ds; 1143 deflate_state *ss; 1144 ushf *overlay; 1145 1146 if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL) 1147 return Z_STREAM_ERROR; 1148 ss = (deflate_state *) source->state; 1149 1150 zmemcpy(dest, source, sizeof(*dest)); 1151 1152 ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state)); 1153 if (ds == Z_NULL) return Z_MEM_ERROR; 1154 dest->state = (struct internal_state FAR *) ds; 1155 zmemcpy(ds, ss, sizeof(*ds)); 1156 ds->strm = dest; 1157 1158 ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte)); 1159 ds->prev = (Posf *) ZALLOC(dest, ds->w_size, sizeof(Pos)); 1160 ds->head = (Posf *) ZALLOC(dest, ds->hash_size, sizeof(Pos)); 1161 overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof(ush)+2); 1162 ds->pending_buf = (uchf *) overlay; 1163 1164 if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL || 1165 ds->pending_buf == Z_NULL) { 1166 deflateEnd (dest); 1167 return Z_MEM_ERROR; 1168 } 1169 /* ??? following zmemcpy doesn't work for 16-bit MSDOS */ 1170 zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte)); 1171 zmemcpy(ds->prev, ss->prev, ds->w_size * sizeof(Pos)); 1172 zmemcpy(ds->head, ss->head, ds->hash_size * sizeof(Pos)); 1173 zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size); 1174 1175 ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf); 1176 ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush); 1177 ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize; 1178 1179 ds->l_desc.dyn_tree = ds->dyn_ltree; 1180 ds->d_desc.dyn_tree = ds->dyn_dtree; 1181 ds->bl_desc.dyn_tree = ds->bl_tree; 1182 1183 return Z_OK; 1184 } 1185 1186 /* =========================================================================== 1187 * Return the number of bytes of output which are immediately available 1188 * for output from the decompressor. 1189 */ 1190 int 1191 deflateOutputPending(z_streamp strm) 1192 { 1193 if (strm == Z_NULL || strm->state == Z_NULL) return 0; 1194 1195 return ((deflate_state *)(strm->state))->pending; 1196 } 1197 1198 /* =========================================================================== 1199 * Read a new buffer from the current input stream, update the adler32 1200 * and total number of bytes read. All deflate() input goes through 1201 * this function so some applications may wish to modify it to avoid 1202 * allocating a large strm->next_in buffer and copying from it. 1203 * (See also flush_pending()). 1204 */ 1205 local int 1206 read_buf(z_streamp strm, charf *buf, unsigned size) 1207 { 1208 unsigned len = strm->avail_in; 1209 1210 if (len > size) len = size; 1211 if (len == 0) return 0; 1212 1213 strm->avail_in -= len; 1214 1215 if (!((deflate_state *)(strm->state))->noheader) { 1216 strm->adler = adler32(strm->adler, strm->next_in, len); 1217 } 1218 zmemcpy(buf, strm->next_in, len); 1219 strm->next_in += len; 1220 strm->total_in += len; 1221 1222 return (int)len; 1223 } 1224 1225 /* =========================================================================== 1226 * Initialize the "longest match" routines for a new zlib stream 1227 */ 1228 local void 1229 lm_init(deflate_state *s) 1230 { 1231 s->window_size = (ulg)2L*s->w_size; 1232 1233 CLEAR_HASH(s); 1234 1235 /* Set the default configuration parameters: 1236 */ 1237 s->max_lazy_match = configuration_table[s->level].max_lazy; 1238 s->good_match = configuration_table[s->level].good_length; 1239 s->nice_match = configuration_table[s->level].nice_length; 1240 s->max_chain_length = configuration_table[s->level].max_chain; 1241 1242 s->strstart = 0; 1243 s->block_start = 0L; 1244 s->lookahead = 0; 1245 s->match_length = s->prev_length = MIN_MATCH-1; 1246 s->match_available = 0; 1247 s->ins_h = 0; 1248 #ifdef ASMV 1249 match_init(); /* initialize the asm code */ 1250 #endif 1251 } 1252 1253 /* =========================================================================== 1254 * Set match_start to the longest match starting at the given string and 1255 * return its length. Matches shorter or equal to prev_length are discarded, 1256 * in which case the result is equal to prev_length and match_start is 1257 * garbage. 1258 * IN assertions: cur_match is the head of the hash chain for the current 1259 * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1 1260 * OUT assertion: the match length is not greater than s->lookahead. 1261 * 1262 * Parameters: 1263 * cur_match: current match 1264 */ 1265 #ifndef ASMV 1266 /* For 80x86 and 680x0, an optimized version will be provided in match.asm or 1267 * match.S. The code will be functionally equivalent. 1268 */ 1269 local uInt 1270 longest_match(deflate_state *s, IPos cur_match) 1271 { 1272 unsigned chain_length = s->max_chain_length;/* max hash chain length */ 1273 Bytef *scan = s->window + s->strstart; /* current string */ 1274 Bytef *match; /* matched string */ 1275 int len; /* length of current match */ 1276 int best_len = s->prev_length; /* best match length so far */ 1277 int nice_match = s->nice_match; /* stop if match long enough */ 1278 IPos limit = s->strstart > (IPos)MAX_DIST(s) ? 1279 s->strstart - (IPos)MAX_DIST(s) : NIL; 1280 /* Stop when cur_match becomes <= limit. To simplify the code, 1281 * we prevent matches with the string of window index 0. 1282 */ 1283 Posf *prev = s->prev; 1284 uInt wmask = s->w_mask; 1285 1286 #ifdef UNALIGNED_OK 1287 /* Compare two bytes at a time. Note: this is not always beneficial. 1288 * Try with and without -DUNALIGNED_OK to check. 1289 */ 1290 Bytef *strend = s->window + s->strstart + MAX_MATCH - 1; 1291 ush scan_start = *(ushf*)scan; 1292 ush scan_end = *(ushf*)(scan+best_len-1); 1293 #else 1294 Bytef *strend = s->window + s->strstart + MAX_MATCH; 1295 Byte scan_end1 = scan[best_len-1]; 1296 Byte scan_end = scan[best_len]; 1297 #endif 1298 1299 /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. 1300 * It is easy to get rid of this optimization if necessary. 1301 */ 1302 Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever"); 1303 1304 /* Do not waste too much time if we already have a good match: */ 1305 if (s->prev_length >= s->good_match) { 1306 chain_length >>= 2; 1307 } 1308 /* Do not look for matches beyond the end of the input. This is necessary 1309 * to make deflate deterministic. 1310 */ 1311 if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead; 1312 1313 Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead"); 1314 1315 do { 1316 Assert(cur_match < s->strstart, "no future"); 1317 match = s->window + cur_match; 1318 1319 /* Skip to next match if the match length cannot increase 1320 * or if the match length is less than 2: 1321 */ 1322 #if (defined(UNALIGNED_OK) && MAX_MATCH == 258) 1323 /* This code assumes sizeof(unsigned short) == 2. Do not use 1324 * UNALIGNED_OK if your compiler uses a different size. 1325 */ 1326 if (*(ushf*)(match+best_len-1) != scan_end || 1327 *(ushf*)match != scan_start) continue; 1328 1329 /* It is not necessary to compare scan[2] and match[2] since they are 1330 * always equal when the other bytes match, given that the hash keys 1331 * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at 1332 * strstart+3, +5, ... up to strstart+257. We check for insufficient 1333 * lookahead only every 4th comparison; the 128th check will be made 1334 * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is 1335 * necessary to put more guard bytes at the end of the window, or 1336 * to check more often for insufficient lookahead. 1337 */ 1338 Assert(scan[2] == match[2], "scan[2]?"); 1339 scan++, match++; 1340 do { 1341 } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) && 1342 *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 1343 *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 1344 *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 1345 scan < strend); 1346 /* The funny "do {}" generates better code on most compilers */ 1347 1348 /* Here, scan <= window+strstart+257 */ 1349 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 1350 if (*scan == *match) scan++; 1351 1352 len = (MAX_MATCH - 1) - (int)(strend-scan); 1353 scan = strend - (MAX_MATCH-1); 1354 1355 #else /* UNALIGNED_OK */ 1356 1357 if (match[best_len] != scan_end || 1358 match[best_len-1] != scan_end1 || 1359 *match != *scan || 1360 *++match != scan[1]) continue; 1361 1362 /* The check at best_len-1 can be removed because it will be made 1363 * again later. (This heuristic is not always a win.) 1364 * It is not necessary to compare scan[2] and match[2] since they 1365 * are always equal when the other bytes match, given that 1366 * the hash keys are equal and that HASH_BITS >= 8. 1367 */ 1368 scan += 2, match++; 1369 Assert(*scan == *match, "match[2]?"); 1370 1371 /* We check for insufficient lookahead only every 8th comparison; 1372 * the 256th check will be made at strstart+258. 1373 */ 1374 do { 1375 } while (*++scan == *++match && *++scan == *++match && 1376 *++scan == *++match && *++scan == *++match && 1377 *++scan == *++match && *++scan == *++match && 1378 *++scan == *++match && *++scan == *++match && 1379 scan < strend); 1380 1381 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 1382 1383 len = MAX_MATCH - (int)(strend - scan); 1384 scan = strend - MAX_MATCH; 1385 1386 #endif /* UNALIGNED_OK */ 1387 1388 if (len > best_len) { 1389 s->match_start = cur_match; 1390 best_len = len; 1391 if (len >= nice_match) break; 1392 #ifdef UNALIGNED_OK 1393 scan_end = *(ushf*)(scan+best_len-1); 1394 #else 1395 scan_end1 = scan[best_len-1]; 1396 scan_end = scan[best_len]; 1397 #endif 1398 } 1399 } while ((cur_match = prev[cur_match & wmask]) > limit 1400 && --chain_length != 0); 1401 1402 if ((uInt)best_len <= s->lookahead) return best_len; 1403 return s->lookahead; 1404 } 1405 #endif /* ASMV */ 1406 1407 #ifdef DEBUG_ZLIB 1408 /* =========================================================================== 1409 * Check that the match at match_start is indeed a match. 1410 */ 1411 local void 1412 check_match(deflate_state *s, IPos start, IPos match, int length) 1413 { 1414 /* check that the match is indeed a match */ 1415 if (zmemcmp((charf *)s->window + match, 1416 (charf *)s->window + start, length) != EQUAL) { 1417 fprintf(stderr, " start %u, match %u, length %d\n", 1418 start, match, length); 1419 do { 1420 fprintf(stderr, "%c%c", s->window[match++], s->window[start++]); 1421 } while (--length != 0); 1422 z_error("invalid match"); 1423 } 1424 if (z_verbose > 1) { 1425 fprintf(stderr,"\\[%d,%d]", start-match, length); 1426 do { putc(s->window[start++], stderr); } while (--length != 0); 1427 } 1428 } 1429 #else 1430 # define check_match(s, start, match, length) 1431 #endif 1432 1433 /* =========================================================================== 1434 * Fill the window when the lookahead becomes insufficient. 1435 * Updates strstart and lookahead. 1436 * 1437 * IN assertion: lookahead < MIN_LOOKAHEAD 1438 * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD 1439 * At least one byte has been read, or avail_in == 0; reads are 1440 * performed for at least two bytes (required for the zip translate_eol 1441 * option -- not supported here). 1442 */ 1443 local void 1444 fill_window(deflate_state *s) 1445 { 1446 unsigned n, m; 1447 Posf *p; 1448 unsigned more; /* Amount of free space at the end of the window. */ 1449 uInt wsize = s->w_size; 1450 1451 do { 1452 more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart); 1453 1454 /* Deal with !@#$% 64K limit: */ 1455 if (more == 0 && s->strstart == 0 && s->lookahead == 0) { 1456 more = wsize; 1457 1458 } else if (more == (unsigned)(-1)) { 1459 /* Very unlikely, but possible on 16 bit machine if strstart == 0 1460 * and lookahead == 1 (input done one byte at time) 1461 */ 1462 more--; 1463 1464 /* If the window is almost full and there is insufficient lookahead, 1465 * move the upper half to the lower one to make room in the upper half. 1466 */ 1467 } else if (s->strstart >= wsize+MAX_DIST(s)) { 1468 1469 zmemcpy((charf *)s->window, (charf *)s->window+wsize, 1470 (unsigned)wsize); 1471 s->match_start -= wsize; 1472 s->strstart -= wsize; /* we now have strstart >= MAX_DIST */ 1473 s->block_start -= (long) wsize; 1474 1475 /* Slide the hash table (could be avoided with 32 bit values 1476 at the expense of memory usage). We slide even when level == 0 1477 to keep the hash table consistent if we switch back to level > 0 1478 later. (Using level 0 permanently is not an optimal usage of 1479 zlib, so we don't care about this pathological case.) 1480 */ 1481 n = s->hash_size; 1482 p = &s->head[n]; 1483 do { 1484 m = *--p; 1485 *p = (Pos)(m >= wsize ? m-wsize : NIL); 1486 } while (--n); 1487 1488 n = wsize; 1489 p = &s->prev[n]; 1490 do { 1491 m = *--p; 1492 *p = (Pos)(m >= wsize ? m-wsize : NIL); 1493 /* If n is not on any hash chain, prev[n] is garbage but 1494 * its value will never be used. 1495 */ 1496 } while (--n); 1497 more += wsize; 1498 } 1499 if (s->strm->avail_in == 0) return; 1500 1501 /* If there was no sliding: 1502 * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 && 1503 * more == window_size - lookahead - strstart 1504 * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1) 1505 * => more >= window_size - 2*WSIZE + 2 1506 * In the BIG_MEM or MMAP case (not yet supported), 1507 * window_size == input_size + MIN_LOOKAHEAD && 1508 * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD. 1509 * Otherwise, window_size == 2*WSIZE so more >= 2. 1510 * If there was sliding, more >= WSIZE. So in all cases, more >= 2. 1511 */ 1512 Assert(more >= 2, "more < 2"); 1513 1514 n = read_buf(s->strm, (charf *)s->window + s->strstart + s->lookahead, 1515 more); 1516 s->lookahead += n; 1517 1518 /* Initialize the hash value now that we have some input: */ 1519 if (s->lookahead >= MIN_MATCH) { 1520 s->ins_h = s->window[s->strstart]; 1521 UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]); 1522 #if MIN_MATCH != 3 1523 Call UPDATE_HASH() MIN_MATCH-3 more times 1524 #endif 1525 } 1526 /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage, 1527 * but this is not important since only literal bytes will be emitted. 1528 */ 1529 1530 } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0); 1531 } 1532 1533 /* =========================================================================== 1534 * Flush the current block, with given end-of-file flag. 1535 * IN assertion: strstart is set to the end of the current match. 1536 */ 1537 #define FLUSH_BLOCK_ONLY(s, eof) { \ 1538 _tr_flush_block(s, (s->block_start >= 0L ? \ 1539 (charf *)&s->window[(unsigned)s->block_start] : \ 1540 (charf *)Z_NULL), \ 1541 (ulg)((long)s->strstart - s->block_start), \ 1542 (eof)); \ 1543 s->block_start = s->strstart; \ 1544 flush_pending(s->strm); \ 1545 Tracev((stderr,"[FLUSH]")); \ 1546 } 1547 1548 /* Same but force premature exit if necessary. */ 1549 #define FLUSH_BLOCK(s, eof) { \ 1550 FLUSH_BLOCK_ONLY(s, eof); \ 1551 if (s->strm->avail_out == 0) return (eof) ? finish_started : need_more; \ 1552 } 1553 1554 /* =========================================================================== 1555 * Copy without compression as much as possible from the input stream, return 1556 * the current block state. 1557 * This function does not insert new strings in the dictionary since 1558 * uncompressible data is probably not useful. This function is used 1559 * only for the level=0 compression option. 1560 * NOTE: this function should be optimized to avoid extra copying from 1561 * window to pending_buf. 1562 */ 1563 local block_state 1564 deflate_stored(deflate_state *s, int flush) 1565 { 1566 /* Stored blocks are limited to 0xffff bytes, pending_buf is limited 1567 * to pending_buf_size, and each stored block has a 5 byte header: 1568 */ 1569 ulg max_block_size = 0xffff; 1570 ulg max_start; 1571 1572 if (max_block_size > s->pending_buf_size - 5) { 1573 max_block_size = s->pending_buf_size - 5; 1574 } 1575 1576 /* Copy as much as possible from input to output: */ 1577 for (;;) { 1578 /* Fill the window as much as possible: */ 1579 if (s->lookahead <= 1) { 1580 1581 Assert(s->strstart < s->w_size+MAX_DIST(s) || 1582 s->block_start >= (long)s->w_size, "slide too late"); 1583 1584 fill_window(s); 1585 if (s->lookahead == 0 && flush == Z_NO_FLUSH) return need_more; 1586 1587 if (s->lookahead == 0) break; /* flush the current block */ 1588 } 1589 Assert(s->block_start >= 0L, "block gone"); 1590 1591 s->strstart += s->lookahead; 1592 s->lookahead = 0; 1593 1594 /* Emit a stored block if pending_buf will be full: */ 1595 max_start = s->block_start + max_block_size; 1596 if (s->strstart == 0 || (ulg)s->strstart >= max_start) { 1597 /* strstart == 0 is possible when wraparound on 16-bit machine */ 1598 s->lookahead = (uInt)(s->strstart - max_start); 1599 s->strstart = (uInt)max_start; 1600 FLUSH_BLOCK(s, 0); 1601 } 1602 /* Flush if we may have to slide, otherwise block_start may become 1603 * negative and the data will be gone: 1604 */ 1605 if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) { 1606 FLUSH_BLOCK(s, 0); 1607 } 1608 } 1609 FLUSH_BLOCK(s, flush == Z_FINISH); 1610 return flush == Z_FINISH ? finish_done : block_done; 1611 } 1612 1613 /* =========================================================================== 1614 * Compress as much as possible from the input stream, return the current 1615 * block state. 1616 * This function does not perform lazy evaluation of matches and inserts 1617 * new strings in the dictionary only for unmatched strings or for short 1618 * matches. It is used only for the fast compression options. 1619 */ 1620 local block_state 1621 deflate_fast(deflate_state *s, int flush) 1622 { 1623 IPos hash_head = NIL; /* head of the hash chain */ 1624 int bflush; /* set if current block must be flushed */ 1625 1626 for (;;) { 1627 /* Make sure that we always have enough lookahead, except 1628 * at the end of the input file. We need MAX_MATCH bytes 1629 * for the next match, plus MIN_MATCH bytes to insert the 1630 * string following the next match. 1631 */ 1632 if (s->lookahead < MIN_LOOKAHEAD) { 1633 fill_window(s); 1634 if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { 1635 return need_more; 1636 } 1637 if (s->lookahead == 0) break; /* flush the current block */ 1638 } 1639 1640 /* Insert the string window[strstart .. strstart+2] in the 1641 * dictionary, and set hash_head to the head of the hash chain: 1642 */ 1643 if (s->lookahead >= MIN_MATCH) { 1644 INSERT_STRING(s, s->strstart, hash_head); 1645 } 1646 1647 /* Find the longest match, discarding those <= prev_length. 1648 * At this point we have always match_length < MIN_MATCH 1649 */ 1650 if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) { 1651 /* To simplify the code, we prevent matches with the string 1652 * of window index 0 (in particular we have to avoid a match 1653 * of the string with itself at the start of the input file). 1654 */ 1655 if (s->strategy != Z_HUFFMAN_ONLY) { 1656 s->match_length = longest_match (s, hash_head); 1657 } 1658 /* longest_match() sets match_start */ 1659 } 1660 if (s->match_length >= MIN_MATCH) { 1661 check_match(s, s->strstart, s->match_start, s->match_length); 1662 1663 bflush = _tr_tally(s, s->strstart - s->match_start, 1664 s->match_length - MIN_MATCH); 1665 1666 s->lookahead -= s->match_length; 1667 1668 /* Insert new strings in the hash table only if the match length 1669 * is not too large. This saves time but degrades compression. 1670 */ 1671 if (s->match_length <= s->max_insert_length && 1672 s->lookahead >= MIN_MATCH) { 1673 s->match_length--; /* string at strstart already in hash table */ 1674 do { 1675 s->strstart++; 1676 INSERT_STRING(s, s->strstart, hash_head); 1677 /* strstart never exceeds WSIZE-MAX_MATCH, so there are 1678 * always MIN_MATCH bytes ahead. 1679 */ 1680 } while (--s->match_length != 0); 1681 s->strstart++; 1682 } else { 1683 s->strstart += s->match_length; 1684 s->match_length = 0; 1685 s->ins_h = s->window[s->strstart]; 1686 UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]); 1687 #if MIN_MATCH != 3 1688 Call UPDATE_HASH() MIN_MATCH-3 more times 1689 #endif 1690 /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not 1691 * matter since it will be recomputed at next deflate call. 1692 */ 1693 } 1694 } else { 1695 /* No match, output a literal byte */ 1696 Tracevv((stderr,"%c", s->window[s->strstart])); 1697 bflush = _tr_tally (s, 0, s->window[s->strstart]); 1698 s->lookahead--; 1699 s->strstart++; 1700 } 1701 if (bflush) FLUSH_BLOCK(s, 0); 1702 } 1703 FLUSH_BLOCK(s, flush == Z_FINISH); 1704 return flush == Z_FINISH ? finish_done : block_done; 1705 } 1706 1707 /* =========================================================================== 1708 * Same as above, but achieves better compression. We use a lazy 1709 * evaluation for matches: a match is finally adopted only if there is 1710 * no better match at the next window position. 1711 */ 1712 local block_state 1713 deflate_slow(deflate_state *s, int flush) 1714 { 1715 IPos hash_head = NIL; /* head of hash chain */ 1716 int bflush; /* set if current block must be flushed */ 1717 1718 /* Process the input block. */ 1719 for (;;) { 1720 /* Make sure that we always have enough lookahead, except 1721 * at the end of the input file. We need MAX_MATCH bytes 1722 * for the next match, plus MIN_MATCH bytes to insert the 1723 * string following the next match. 1724 */ 1725 if (s->lookahead < MIN_LOOKAHEAD) { 1726 fill_window(s); 1727 if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { 1728 return need_more; 1729 } 1730 if (s->lookahead == 0) break; /* flush the current block */ 1731 } 1732 1733 /* Insert the string window[strstart .. strstart+2] in the 1734 * dictionary, and set hash_head to the head of the hash chain: 1735 */ 1736 if (s->lookahead >= MIN_MATCH) { 1737 INSERT_STRING(s, s->strstart, hash_head); 1738 } 1739 1740 /* Find the longest match, discarding those <= prev_length. 1741 */ 1742 s->prev_length = s->match_length, s->prev_match = s->match_start; 1743 s->match_length = MIN_MATCH-1; 1744 1745 if (hash_head != NIL && s->prev_length < s->max_lazy_match && 1746 s->strstart - hash_head <= MAX_DIST(s)) { 1747 /* To simplify the code, we prevent matches with the string 1748 * of window index 0 (in particular we have to avoid a match 1749 * of the string with itself at the start of the input file). 1750 */ 1751 if (s->strategy != Z_HUFFMAN_ONLY) { 1752 s->match_length = longest_match (s, hash_head); 1753 } 1754 /* longest_match() sets match_start */ 1755 1756 if (s->match_length <= 5 && (s->strategy == Z_FILTERED || 1757 (s->match_length == MIN_MATCH && 1758 s->strstart - s->match_start > TOO_FAR))) { 1759 1760 /* If prev_match is also MIN_MATCH, match_start is garbage 1761 * but we will ignore the current match anyway. 1762 */ 1763 s->match_length = MIN_MATCH-1; 1764 } 1765 } 1766 /* If there was a match at the previous step and the current 1767 * match is not better, output the previous match: 1768 */ 1769 if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) { 1770 uInt max_insert = s->strstart + s->lookahead - MIN_MATCH; 1771 /* Do not insert strings in hash table beyond this. */ 1772 1773 check_match(s, s->strstart-1, s->prev_match, s->prev_length); 1774 1775 bflush = _tr_tally(s, s->strstart -1 - s->prev_match, 1776 s->prev_length - MIN_MATCH); 1777 1778 /* Insert in hash table all strings up to the end of the match. 1779 * strstart-1 and strstart are already inserted. If there is not 1780 * enough lookahead, the last two strings are not inserted in 1781 * the hash table. 1782 */ 1783 s->lookahead -= s->prev_length-1; 1784 s->prev_length -= 2; 1785 do { 1786 if (++s->strstart <= max_insert) { 1787 INSERT_STRING(s, s->strstart, hash_head); 1788 } 1789 } while (--s->prev_length != 0); 1790 s->match_available = 0; 1791 s->match_length = MIN_MATCH-1; 1792 s->strstart++; 1793 1794 if (bflush) FLUSH_BLOCK(s, 0); 1795 1796 } else if (s->match_available) { 1797 /* If there was no match at the previous position, output a 1798 * single literal. If there was a match but the current match 1799 * is longer, truncate the previous match to a single literal. 1800 */ 1801 Tracevv((stderr,"%c", s->window[s->strstart-1])); 1802 if (_tr_tally (s, 0, s->window[s->strstart-1])) { 1803 FLUSH_BLOCK_ONLY(s, 0); 1804 } 1805 s->strstart++; 1806 s->lookahead--; 1807 if (s->strm->avail_out == 0) return need_more; 1808 } else { 1809 /* There is no previous match to compare with, wait for 1810 * the next step to decide. 1811 */ 1812 s->match_available = 1; 1813 s->strstart++; 1814 s->lookahead--; 1815 } 1816 } 1817 Assert (flush != Z_NO_FLUSH, "no flush?"); 1818 if (s->match_available) { 1819 Tracevv((stderr,"%c", s->window[s->strstart-1])); 1820 _tr_tally (s, 0, s->window[s->strstart-1]); 1821 s->match_available = 0; 1822 } 1823 FLUSH_BLOCK(s, flush == Z_FINISH); 1824 return flush == Z_FINISH ? finish_done : block_done; 1825 } 1826 /* --- deflate.c */ 1827 1828 /* +++ trees.c */ 1829 /* trees.c -- output deflated data using Huffman coding 1830 * Copyright (C) 1995-1996 Jean-loup Gailly 1831 * For conditions of distribution and use, see copyright notice in zlib.h 1832 */ 1833 1834 /* 1835 * ALGORITHM 1836 * 1837 * The "deflation" process uses several Huffman trees. The more 1838 * common source values are represented by shorter bit sequences. 1839 * 1840 * Each code tree is stored in a compressed form which is itself 1841 * a Huffman encoding of the lengths of all the code strings (in 1842 * ascending order by source values). The actual code strings are 1843 * reconstructed from the lengths in the inflate process, as described 1844 * in the deflate specification. 1845 * 1846 * REFERENCES 1847 * 1848 * Deutsch, L.P.,"'Deflate' Compressed Data Format Specification". 1849 * Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc 1850 * 1851 * Storer, James A. 1852 * Data Compression: Methods and Theory, pp. 49-50. 1853 * Computer Science Press, 1988. ISBN 0-7167-8156-5. 1854 * 1855 * Sedgewick, R. 1856 * Algorithms, p290. 1857 * Addison-Wesley, 1983. ISBN 0-201-06672-6. 1858 */ 1859 1860 /* From: trees.c,v 1.11 1996/07/24 13:41:06 me Exp $ */ 1861 1862 /* #include "deflate.h" */ 1863 1864 #ifdef DEBUG_ZLIB 1865 # include <ctype.h> 1866 #endif 1867 1868 /* =========================================================================== 1869 * Constants 1870 */ 1871 1872 #define MAX_BL_BITS 7 1873 /* Bit length codes must not exceed MAX_BL_BITS bits */ 1874 1875 #define END_BLOCK 256 1876 /* end of block literal code */ 1877 1878 #define REP_3_6 16 1879 /* repeat previous bit length 3-6 times (2 bits of repeat count) */ 1880 1881 #define REPZ_3_10 17 1882 /* repeat a zero length 3-10 times (3 bits of repeat count) */ 1883 1884 #define REPZ_11_138 18 1885 /* repeat a zero length 11-138 times (7 bits of repeat count) */ 1886 1887 local int extra_lbits[LENGTH_CODES] /* extra bits for each length code */ 1888 = {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}; 1889 1890 local int extra_dbits[D_CODES] /* extra bits for each distance code */ 1891 = {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}; 1892 1893 local int extra_blbits[BL_CODES]/* extra bits for each bit length code */ 1894 = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7}; 1895 1896 local uch bl_order[BL_CODES] 1897 = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15}; 1898 /* The lengths of the bit length codes are sent in order of decreasing 1899 * probability, to avoid transmitting the lengths for unused bit length codes. 1900 */ 1901 1902 #define Buf_size (8 * 2*sizeof(char)) 1903 /* Number of bits used within bi_buf. (bi_buf might be implemented on 1904 * more than 16 bits on some systems.) 1905 */ 1906 1907 /* =========================================================================== 1908 * Local data. These are initialized only once. 1909 */ 1910 1911 local ct_data static_ltree[L_CODES+2]; 1912 /* The static literal tree. Since the bit lengths are imposed, there is no 1913 * need for the L_CODES extra codes used during heap construction. However 1914 * The codes 286 and 287 are needed to build a canonical tree (see _tr_init 1915 * below). 1916 */ 1917 1918 local ct_data static_dtree[D_CODES]; 1919 /* The static distance tree. (Actually a trivial tree since all codes use 1920 * 5 bits.) 1921 */ 1922 1923 local uch dist_code[512]; 1924 /* distance codes. The first 256 values correspond to the distances 1925 * 3 .. 258, the last 256 values correspond to the top 8 bits of 1926 * the 15 bit distances. 1927 */ 1928 1929 local uch length_code[MAX_MATCH-MIN_MATCH+1]; 1930 /* length code for each normalized match length (0 == MIN_MATCH) */ 1931 1932 local int base_length[LENGTH_CODES]; 1933 /* First normalized length for each code (0 = MIN_MATCH) */ 1934 1935 local int base_dist[D_CODES]; 1936 /* First normalized distance for each code (0 = distance of 1) */ 1937 1938 struct static_tree_desc_s { 1939 ct_data *static_tree; /* static tree or NULL */ 1940 intf *extra_bits; /* extra bits for each code or NULL */ 1941 int extra_base; /* base index for extra_bits */ 1942 int elems; /* max number of elements in the tree */ 1943 int max_length; /* max bit length for the codes */ 1944 }; 1945 1946 local static_tree_desc static_l_desc = 1947 {static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS}; 1948 1949 local static_tree_desc static_d_desc = 1950 {static_dtree, extra_dbits, 0, D_CODES, MAX_BITS}; 1951 1952 local static_tree_desc static_bl_desc = 1953 {NULL, extra_blbits, 0, BL_CODES, MAX_BL_BITS}; 1954 1955 /* =========================================================================== 1956 * Local (static) routines in this file. 1957 */ 1958 1959 local void tr_static_init OF((void)); 1960 local void init_block OF((deflate_state *s)); 1961 local void pqdownheap OF((deflate_state *s, ct_data *tree, int k)); 1962 local void gen_bitlen OF((deflate_state *s, tree_desc *desc)); 1963 local void gen_codes OF((ct_data *tree, int max_code, ushf *bl_count)); 1964 local void build_tree OF((deflate_state *s, tree_desc *desc)); 1965 local void scan_tree OF((deflate_state *s, ct_data *tree, int max_code)); 1966 local void send_tree OF((deflate_state *s, ct_data *tree, int max_code)); 1967 local int build_bl_tree OF((deflate_state *s)); 1968 local void send_all_trees OF((deflate_state *s, int lcodes, int dcodes, 1969 int blcodes)); 1970 local void compress_block OF((deflate_state *s, ct_data *ltree, 1971 ct_data *dtree)); 1972 local void set_data_type OF((deflate_state *s)); 1973 local unsigned bi_reverse OF((unsigned value, int length)); 1974 local void bi_windup OF((deflate_state *s)); 1975 local void bi_flush OF((deflate_state *s)); 1976 local void copy_block OF((deflate_state *s, charf *buf, unsigned len, 1977 int header)); 1978 1979 #ifndef DEBUG_ZLIB 1980 # define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len) 1981 /* Send a code of the given tree. c and tree must not have side effects */ 1982 1983 #else /* DEBUG_ZLIB */ 1984 # define send_code(s, c, tree) \ 1985 { if (verbose>2) fprintf(stderr,"\ncd %3d ",(c)); \ 1986 send_bits(s, tree[c].Code, tree[c].Len); } 1987 #endif 1988 1989 #define d_code(dist) \ 1990 ((dist) < 256 ? dist_code[dist] : dist_code[256+((dist)>>7)]) 1991 /* Mapping from a distance to a distance code. dist is the distance - 1 and 1992 * must not have side effects. dist_code[256] and dist_code[257] are never 1993 * used. 1994 */ 1995 1996 /* =========================================================================== 1997 * Output a short LSB first on the stream. 1998 * IN assertion: there is enough room in pendingBuf. 1999 */ 2000 #define put_short(s, w) { \ 2001 put_byte(s, (uch)((w) & 0xff)); \ 2002 put_byte(s, (uch)((ush)(w) >> 8)); \ 2003 } 2004 2005 /* =========================================================================== 2006 * Send a value on a given number of bits. 2007 * IN assertion: length <= 16 and value fits in length bits. 2008 * 2009 * Parameters: 2010 * value: value to send 2011 * length: number of bits 2012 */ 2013 #ifdef DEBUG_ZLIB 2014 local void send_bits OF((deflate_state *s, int value, int length)); 2015 2016 local void 2017 send_bits(deflate_state *s, int value, int length) 2018 { 2019 Tracevv((stderr," l %2d v %4x ", length, value)); 2020 Assert(length > 0 && length <= 15, "invalid length"); 2021 s->bits_sent += (ulg)length; 2022 2023 /* If not enough room in bi_buf, use (valid) bits from bi_buf and 2024 * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid)) 2025 * unused bits in value. 2026 */ 2027 if (s->bi_valid > (int)Buf_size - length) { 2028 s->bi_buf |= (value << s->bi_valid); 2029 put_short(s, s->bi_buf); 2030 s->bi_buf = (ush)value >> (Buf_size - s->bi_valid); 2031 s->bi_valid += length - Buf_size; 2032 } else { 2033 s->bi_buf |= value << s->bi_valid; 2034 s->bi_valid += length; 2035 } 2036 } 2037 #else /* !DEBUG_ZLIB */ 2038 2039 #define send_bits(s, value, length) \ 2040 { int len = length;\ 2041 if (s->bi_valid > (int)Buf_size - len) {\ 2042 int val = value;\ 2043 s->bi_buf |= (val << s->bi_valid);\ 2044 put_short(s, s->bi_buf);\ 2045 s->bi_buf = (ush)val >> (Buf_size - s->bi_valid);\ 2046 s->bi_valid += len - Buf_size;\ 2047 } else {\ 2048 s->bi_buf |= (value) << s->bi_valid;\ 2049 s->bi_valid += len;\ 2050 }\ 2051 } 2052 #endif /* DEBUG_ZLIB */ 2053 2054 /* the arguments must not have side effects */ 2055 2056 /* =========================================================================== 2057 * Initialize the various 'constant' tables. In a multi-threaded environment, 2058 * this function may be called by two threads concurrently, but this is 2059 * harmless since both invocations do exactly the same thing. 2060 */ 2061 local void 2062 tr_static_init(void) 2063 { 2064 static int static_init_done = 0; 2065 int n; /* iterates over tree elements */ 2066 int bits; /* bit counter */ 2067 int length; /* length value */ 2068 int code; /* code value */ 2069 int dist; /* distance index */ 2070 ush bl_count[MAX_BITS+1]; 2071 /* number of codes at each bit length for an optimal tree */ 2072 2073 if (static_init_done) return; 2074 2075 /* Initialize the mapping length (0..255) -> length code (0..28) */ 2076 length = 0; 2077 for (code = 0; code < LENGTH_CODES-1; code++) { 2078 base_length[code] = length; 2079 for (n = 0; n < (1<<extra_lbits[code]); n++) { 2080 length_code[length++] = (uch)code; 2081 } 2082 } 2083 Assert (length == 256, "tr_static_init: length != 256"); 2084 /* Note that the length 255 (match length 258) can be represented 2085 * in two different ways: code 284 + 5 bits or code 285, so we 2086 * overwrite length_code[255] to use the best encoding: 2087 */ 2088 length_code[length-1] = (uch)code; 2089 2090 /* Initialize the mapping dist (0..32K) -> dist code (0..29) */ 2091 dist = 0; 2092 for (code = 0 ; code < 16; code++) { 2093 base_dist[code] = dist; 2094 for (n = 0; n < (1<<extra_dbits[code]); n++) { 2095 dist_code[dist++] = (uch)code; 2096 } 2097 } 2098 Assert (dist == 256, "tr_static_init: dist != 256"); 2099 dist >>= 7; /* from now on, all distances are divided by 128 */ 2100 for ( ; code < D_CODES; code++) { 2101 base_dist[code] = dist << 7; 2102 for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) { 2103 dist_code[256 + dist++] = (uch)code; 2104 } 2105 } 2106 Assert (dist == 256, "tr_static_init: 256+dist != 512"); 2107 2108 /* Construct the codes of the static literal tree */ 2109 for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0; 2110 n = 0; 2111 while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++; 2112 while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++; 2113 while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++; 2114 while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++; 2115 /* Codes 286 and 287 do not exist, but we must include them in the 2116 * tree construction to get a canonical Huffman tree (longest code 2117 * all ones) 2118 */ 2119 gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count); 2120 2121 /* The static distance tree is trivial: */ 2122 for (n = 0; n < D_CODES; n++) { 2123 static_dtree[n].Len = 5; 2124 static_dtree[n].Code = bi_reverse((unsigned)n, 5); 2125 } 2126 static_init_done = 1; 2127 } 2128 2129 /* =========================================================================== 2130 * Initialize the tree data structures for a new zlib stream. 2131 */ 2132 void 2133 _tr_init(deflate_state *s) 2134 { 2135 tr_static_init(); 2136 2137 s->compressed_len = 0L; 2138 2139 s->l_desc.dyn_tree = s->dyn_ltree; 2140 s->l_desc.stat_desc = &static_l_desc; 2141 2142 s->d_desc.dyn_tree = s->dyn_dtree; 2143 s->d_desc.stat_desc = &static_d_desc; 2144 2145 s->bl_desc.dyn_tree = s->bl_tree; 2146 s->bl_desc.stat_desc = &static_bl_desc; 2147 2148 s->bi_buf = 0; 2149 s->bi_valid = 0; 2150 s->last_eob_len = 8; /* enough lookahead for inflate */ 2151 #ifdef DEBUG_ZLIB 2152 s->bits_sent = 0L; 2153 #endif 2154 2155 /* Initialize the first block of the first file: */ 2156 init_block(s); 2157 } 2158 2159 /* =========================================================================== 2160 * Initialize a new block. 2161 */ 2162 local void 2163 init_block(deflate_state *s) 2164 { 2165 int n; /* iterates over tree elements */ 2166 2167 /* Initialize the trees. */ 2168 for (n = 0; n < L_CODES; n++) s->dyn_ltree[n].Freq = 0; 2169 for (n = 0; n < D_CODES; n++) s->dyn_dtree[n].Freq = 0; 2170 for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0; 2171 2172 s->dyn_ltree[END_BLOCK].Freq = 1; 2173 s->opt_len = s->static_len = 0L; 2174 s->last_lit = s->matches = 0; 2175 } 2176 2177 #define SMALLEST 1 2178 /* Index within the heap array of least frequent node in the Huffman tree */ 2179 2180 2181 /* =========================================================================== 2182 * Remove the smallest element from the heap and recreate the heap with 2183 * one less element. Updates heap and heap_len. 2184 */ 2185 #define pqremove(s, tree, top) \ 2186 {\ 2187 top = s->heap[SMALLEST]; \ 2188 s->heap[SMALLEST] = s->heap[s->heap_len--]; \ 2189 pqdownheap(s, tree, SMALLEST); \ 2190 } 2191 2192 /* =========================================================================== 2193 * Compares to subtrees, using the tree depth as tie breaker when 2194 * the subtrees have equal frequency. This minimizes the worst case length. 2195 */ 2196 #define smaller(tree, n, m, depth) \ 2197 (tree[n].Freq < tree[m].Freq || \ 2198 (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m])) 2199 2200 /* =========================================================================== 2201 * Restore the heap property by moving down the tree starting at node k, 2202 * exchanging a node with the smallest of its two sons if necessary, stopping 2203 * when the heap property is re-established (each father smaller than its 2204 * two sons). 2205 * 2206 * Parameters: 2207 * tree: the tree to restore 2208 * k: node to move down 2209 */ 2210 local void 2211 pqdownheap(deflate_state *s, ct_data *tree, int k) 2212 { 2213 int v = s->heap[k]; 2214 int j = k << 1; /* left son of k */ 2215 while (j <= s->heap_len) { 2216 /* Set j to the smallest of the two sons: */ 2217 if (j < s->heap_len && 2218 smaller(tree, s->heap[j+1], s->heap[j], s->depth)) { 2219 j++; 2220 } 2221 /* Exit if v is smaller than both sons */ 2222 if (smaller(tree, v, s->heap[j], s->depth)) break; 2223 2224 /* Exchange v with the smallest son */ 2225 s->heap[k] = s->heap[j]; k = j; 2226 2227 /* And continue down the tree, setting j to the left son of k */ 2228 j <<= 1; 2229 } 2230 s->heap[k] = v; 2231 } 2232 2233 /* =========================================================================== 2234 * Compute the optimal bit lengths for a tree and update the total bit length 2235 * for the current block. 2236 * IN assertion: the fields freq and dad are set, heap[heap_max] and 2237 * above are the tree nodes sorted by increasing frequency. 2238 * OUT assertions: the field len is set to the optimal bit length, the 2239 * array bl_count contains the frequencies for each bit length. 2240 * The length opt_len is updated; static_len is also updated if stree is 2241 * not null. 2242 * 2243 * Parameters: 2244 * desc: the tree descriptor 2245 */ 2246 local void 2247 gen_bitlen(deflate_state *s, tree_desc *desc) 2248 { 2249 ct_data *tree = desc->dyn_tree; 2250 int max_code = desc->max_code; 2251 ct_data *stree = desc->stat_desc->static_tree; 2252 intf *extra = desc->stat_desc->extra_bits; 2253 int base = desc->stat_desc->extra_base; 2254 int max_length = desc->stat_desc->max_length; 2255 int h; /* heap index */ 2256 int n, m; /* iterate over the tree elements */ 2257 int bits; /* bit length */ 2258 int xbits; /* extra bits */ 2259 ush f; /* frequency */ 2260 int overflow = 0; /* number of elements with bit length too large */ 2261 2262 for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0; 2263 2264 /* In a first pass, compute the optimal bit lengths (which may 2265 * overflow in the case of the bit length tree). 2266 */ 2267 tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */ 2268 2269 for (h = s->heap_max+1; h < HEAP_SIZE; h++) { 2270 n = s->heap[h]; 2271 bits = tree[tree[n].Dad].Len + 1; 2272 if (bits > max_length) bits = max_length, overflow++; 2273 tree[n].Len = (ush)bits; 2274 /* We overwrite tree[n].Dad which is no longer needed */ 2275 2276 if (n > max_code) continue; /* not a leaf node */ 2277 2278 s->bl_count[bits]++; 2279 xbits = 0; 2280 if (n >= base) xbits = extra[n-base]; 2281 f = tree[n].Freq; 2282 s->opt_len += (ulg)f * (bits + xbits); 2283 if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits); 2284 } 2285 if (overflow == 0) return; 2286 2287 Trace((stderr,"\nbit length overflow\n")); 2288 /* This happens for example on obj2 and pic of the Calgary corpus */ 2289 2290 /* Find the first bit length which could increase: */ 2291 do { 2292 bits = max_length-1; 2293 while (s->bl_count[bits] == 0) bits--; 2294 s->bl_count[bits]--; /* move one leaf down the tree */ 2295 s->bl_count[bits+1] += 2; /* move one overflow item as its brother */ 2296 s->bl_count[max_length]--; 2297 /* The brother of the overflow item also moves one step up, 2298 * but this does not affect bl_count[max_length] 2299 */ 2300 overflow -= 2; 2301 } while (overflow > 0); 2302 2303 /* Now recompute all bit lengths, scanning in increasing frequency. 2304 * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all 2305 * lengths instead of fixing only the wrong ones. This idea is taken 2306 * from 'ar' written by Haruhiko Okumura.) 2307 */ 2308 for (bits = max_length; bits != 0; bits--) { 2309 n = s->bl_count[bits]; 2310 while (n != 0) { 2311 m = s->heap[--h]; 2312 if (m > max_code) continue; 2313 if (tree[m].Len != (unsigned) bits) { 2314 Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits)); 2315 s->opt_len += ((long)bits - (long)tree[m].Len) 2316 *(long)tree[m].Freq; 2317 tree[m].Len = (ush)bits; 2318 } 2319 n--; 2320 } 2321 } 2322 } 2323 2324 /* =========================================================================== 2325 * Generate the codes for a given tree and bit counts (which need not be 2326 * optimal). 2327 * IN assertion: the array bl_count contains the bit length statistics for 2328 * the given tree and the field len is set for all tree elements. 2329 * OUT assertion: the field code is set for all tree elements of non 2330 * zero code length. 2331 * 2332 * Parameters: 2333 * tree: the tree to decorate 2334 * max_code: largest code with non zero frequency 2335 * bl_count: number of codes at each bit length 2336 */ 2337 local void 2338 gen_codes(ct_data *tree, int max_code, ushf *bl_count) 2339 { 2340 ush next_code[MAX_BITS+1]; /* next code value for each bit length */ 2341 ush code = 0; /* running code value */ 2342 int bits; /* bit index */ 2343 int n; /* code index */ 2344 2345 /* The distribution counts are first used to generate the code values 2346 * without bit reversal. 2347 */ 2348 for (bits = 1; bits <= MAX_BITS; bits++) { 2349 next_code[bits] = code = (code + bl_count[bits-1]) << 1; 2350 } 2351 /* Check that the bit counts in bl_count are consistent. The last code 2352 * must be all ones. 2353 */ 2354 Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1, 2355 "inconsistent bit counts"); 2356 Tracev((stderr,"\ngen_codes: max_code %d ", max_code)); 2357 2358 for (n = 0; n <= max_code; n++) { 2359 int len = tree[n].Len; 2360 if (len == 0) continue; 2361 /* Now reverse the bits */ 2362 tree[n].Code = bi_reverse(next_code[len]++, len); 2363 2364 Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ", 2365 n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1)); 2366 } 2367 } 2368 2369 /* =========================================================================== 2370 * Construct one Huffman tree and assigns the code bit strings and lengths. 2371 * Update the total bit length for the current block. 2372 * IN assertion: the field freq is set for all tree elements. 2373 * OUT assertions: the fields len and code are set to the optimal bit length 2374 * and corresponding code. The length opt_len is updated; static_len is 2375 * also updated if stree is not null. The field max_code is set. 2376 * 2377 * Parameters: 2378 * desc: the tree descriptor 2379 */ 2380 local void 2381 build_tree(deflate_state *s, tree_desc *desc) 2382 { 2383 ct_data *tree = desc->dyn_tree; 2384 ct_data *stree = desc->stat_desc->static_tree; 2385 int elems = desc->stat_desc->elems; 2386 int n, m; /* iterate over heap elements */ 2387 int max_code = -1; /* largest code with non zero frequency */ 2388 int node; /* new node being created */ 2389 2390 /* Construct the initial heap, with least frequent element in 2391 * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1]. 2392 * heap[0] is not used. 2393 */ 2394 s->heap_len = 0, s->heap_max = HEAP_SIZE; 2395 2396 for (n = 0; n < elems; n++) { 2397 if (tree[n].Freq != 0) { 2398 s->heap[++(s->heap_len)] = max_code = n; 2399 s->depth[n] = 0; 2400 } else { 2401 tree[n].Len = 0; 2402 } 2403 } 2404 2405 /* The pkzip format requires that at least one distance code exists, 2406 * and that at least one bit should be sent even if there is only one 2407 * possible code. So to avoid special checks later on we force at least 2408 * two codes of non zero frequency. 2409 */ 2410 while (s->heap_len < 2) { 2411 node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0); 2412 tree[node].Freq = 1; 2413 s->depth[node] = 0; 2414 s->opt_len--; if (stree) s->static_len -= stree[node].Len; 2415 /* node is 0 or 1 so it does not have extra bits */ 2416 } 2417 desc->max_code = max_code; 2418 2419 /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree, 2420 * establish sub-heaps of increasing lengths: 2421 */ 2422 for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n); 2423 2424 /* Construct the Huffman tree by repeatedly combining the least two 2425 * frequent nodes. 2426 */ 2427 node = elems; /* next internal node of the tree */ 2428 do { 2429 pqremove(s, tree, n); /* n = node of least frequency */ 2430 m = s->heap[SMALLEST]; /* m = node of next least frequency */ 2431 2432 s->heap[--(s->heap_max)] = n; /* keep the nodes sorted by frequency */ 2433 s->heap[--(s->heap_max)] = m; 2434 2435 /* Create a new node father of n and m */ 2436 tree[node].Freq = tree[n].Freq + tree[m].Freq; 2437 s->depth[node] = (uch) (MAX(s->depth[n], s->depth[m]) + 1); 2438 tree[n].Dad = tree[m].Dad = (ush)node; 2439 #ifdef DUMP_BL_TREE 2440 if (tree == s->bl_tree) { 2441 fprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)", 2442 node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq); 2443 } 2444 #endif 2445 /* and insert the new node in the heap */ 2446 s->heap[SMALLEST] = node++; 2447 pqdownheap(s, tree, SMALLEST); 2448 2449 } while (s->heap_len >= 2); 2450 2451 s->heap[--(s->heap_max)] = s->heap[SMALLEST]; 2452 2453 /* At this point, the fields freq and dad are set. We can now 2454 * generate the bit lengths. 2455 */ 2456 gen_bitlen(s, (tree_desc *)desc); 2457 2458 /* The field len is now set, we can generate the bit codes */ 2459 gen_codes ((ct_data *)tree, max_code, s->bl_count); 2460 } 2461 2462 /* =========================================================================== 2463 * Scan a literal or distance tree to determine the frequencies of the codes 2464 * in the bit length tree. 2465 * 2466 * Parameters: 2467 * tree: the tree to be scanned 2468 * max_code: and its largest code of non zero frequency 2469 */ 2470 local void 2471 scan_tree (deflate_state *s, ct_data *tree, int max_code) 2472 { 2473 int n; /* iterates over all tree elements */ 2474 int prevlen = -1; /* last emitted length */ 2475 int curlen; /* length of current code */ 2476 int nextlen = tree[0].Len; /* length of next code */ 2477 int count = 0; /* repeat count of the current code */ 2478 int max_count = 7; /* max repeat count */ 2479 int min_count = 4; /* min repeat count */ 2480 2481 if (nextlen == 0) max_count = 138, min_count = 3; 2482 tree[max_code+1].Len = (ush)0xffff; /* guard */ 2483 2484 for (n = 0; n <= max_code; n++) { 2485 curlen = nextlen; nextlen = tree[n+1].Len; 2486 if (++count < max_count && curlen == nextlen) { 2487 continue; 2488 } else if (count < min_count) { 2489 s->bl_tree[curlen].Freq += count; 2490 } else if (curlen != 0) { 2491 if (curlen != prevlen) s->bl_tree[curlen].Freq++; 2492 s->bl_tree[REP_3_6].Freq++; 2493 } else if (count <= 10) { 2494 s->bl_tree[REPZ_3_10].Freq++; 2495 } else { 2496 s->bl_tree[REPZ_11_138].Freq++; 2497 } 2498 count = 0; prevlen = curlen; 2499 if (nextlen == 0) { 2500 max_count = 138, min_count = 3; 2501 } else if (curlen == nextlen) { 2502 max_count = 6, min_count = 3; 2503 } else { 2504 max_count = 7, min_count = 4; 2505 } 2506 } 2507 } 2508 2509 /* =========================================================================== 2510 * Send a literal or distance tree in compressed form, using the codes in 2511 * bl_tree. 2512 * 2513 * Parameters: 2514 * tree: the tree to be scanned 2515 * max_code: and its largest code of non zero frequency 2516 */ 2517 local void 2518 send_tree(deflate_state *s, ct_data *tree, int max_code) 2519 { 2520 int n; /* iterates over all tree elements */ 2521 int prevlen = -1; /* last emitted length */ 2522 int curlen; /* length of current code */ 2523 int nextlen = tree[0].Len; /* length of next code */ 2524 int count = 0; /* repeat count of the current code */ 2525 int max_count = 7; /* max repeat count */ 2526 int min_count = 4; /* min repeat count */ 2527 2528 /* tree[max_code+1].Len = -1; */ /* guard already set */ 2529 if (nextlen == 0) max_count = 138, min_count = 3; 2530 2531 for (n = 0; n <= max_code; n++) { 2532 curlen = nextlen; nextlen = tree[n+1].Len; 2533 if (++count < max_count && curlen == nextlen) { 2534 continue; 2535 } else if (count < min_count) { 2536 do { send_code(s, curlen, s->bl_tree); } while (--count != 0); 2537 2538 } else if (curlen != 0) { 2539 if (curlen != prevlen) { 2540 send_code(s, curlen, s->bl_tree); count--; 2541 } 2542 Assert(count >= 3 && count <= 6, " 3_6?"); 2543 send_code(s, REP_3_6, s->bl_tree); send_bits(s, count-3, 2); 2544 2545 } else if (count <= 10) { 2546 send_code(s, REPZ_3_10, s->bl_tree); send_bits(s, count-3, 3); 2547 2548 } else { 2549 send_code(s, REPZ_11_138, s->bl_tree); send_bits(s, count-11, 7); 2550 } 2551 count = 0; prevlen = curlen; 2552 if (nextlen == 0) { 2553 max_count = 138, min_count = 3; 2554 } else if (curlen == nextlen) { 2555 max_count = 6, min_count = 3; 2556 } else { 2557 max_count = 7, min_count = 4; 2558 } 2559 } 2560 } 2561 2562 /* =========================================================================== 2563 * Construct the Huffman tree for the bit lengths and return the index in 2564 * bl_order of the last bit length code to send. 2565 */ 2566 local int 2567 build_bl_tree(deflate_state *s) 2568 { 2569 int max_blindex; /* index of last bit length code of non zero freq */ 2570 2571 /* Determine the bit length frequencies for literal and distance trees */ 2572 scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code); 2573 scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code); 2574 2575 /* Build the bit length tree: */ 2576 build_tree(s, (tree_desc *)(&(s->bl_desc))); 2577 /* opt_len now includes the length of the tree representations, except 2578 * the lengths of the bit lengths codes and the 5+5+4 bits for the counts. 2579 */ 2580 2581 /* Determine the number of bit length codes to send. The pkzip format 2582 * requires that at least 4 bit length codes be sent. (appnote.txt says 2583 * 3 but the actual value used is 4.) 2584 */ 2585 for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) { 2586 if (s->bl_tree[bl_order[max_blindex]].Len != 0) break; 2587 } 2588 /* Update opt_len to include the bit length tree and counts */ 2589 s->opt_len += 3*(max_blindex+1) + 5+5+4; 2590 Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", 2591 s->opt_len, s->static_len)); 2592 2593 return max_blindex; 2594 } 2595 2596 /* =========================================================================== 2597 * Send the header for a block using dynamic Huffman trees: the counts, the 2598 * lengths of the bit length codes, the literal tree and the distance tree. 2599 * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4. 2600 * 2601 * Parameters: 2602 * lcodes, dcodes, blcodes: number of codes for each tree 2603 */ 2604 local void 2605 send_all_trees(deflate_state *s, int lcodes, int dcodes, int blcodes) 2606 { 2607 int rank; /* index in bl_order */ 2608 2609 Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes"); 2610 Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES, 2611 "too many codes"); 2612 Tracev((stderr, "\nbl counts: ")); 2613 send_bits(s, lcodes-257, 5); /* not +255 as stated in appnote.txt */ 2614 send_bits(s, dcodes-1, 5); 2615 send_bits(s, blcodes-4, 4); /* not -3 as stated in appnote.txt */ 2616 for (rank = 0; rank < blcodes; rank++) { 2617 Tracev((stderr, "\nbl code %2d ", bl_order[rank])); 2618 send_bits(s, s->bl_tree[bl_order[rank]].Len, 3); 2619 } 2620 Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent)); 2621 2622 send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1); /* literal tree */ 2623 Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent)); 2624 2625 send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1); /* distance tree */ 2626 Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent)); 2627 } 2628 2629 /* =========================================================================== 2630 * Send a stored block 2631 * 2632 * Parameters: 2633 * buf: input block 2634 * stored_len: length of input block 2635 * eof: true if this is the last block for a file 2636 */ 2637 void 2638 _tr_stored_block(deflate_state *s, charf *buf, ulg stored_len, int eof) 2639 { 2640 send_bits(s, (STORED_BLOCK<<1)+eof, 3); /* send block type */ 2641 s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L; 2642 s->compressed_len += (stored_len + 4) << 3; 2643 2644 copy_block(s, buf, (unsigned)stored_len, 1); /* with header */ 2645 } 2646 2647 /* Send just the `stored block' type code without any length bytes or data. 2648 */ 2649 void 2650 _tr_stored_type_only(deflate_state *s) 2651 { 2652 send_bits(s, (STORED_BLOCK << 1), 3); 2653 bi_windup(s); 2654 s->compressed_len = (s->compressed_len + 3) & ~7L; 2655 } 2656 2657 2658 /* =========================================================================== 2659 * Send one empty static block to give enough lookahead for inflate. 2660 * This takes 10 bits, of which 7 may remain in the bit buffer. 2661 * The current inflate code requires 9 bits of lookahead. If the 2662 * last two codes for the previous block (real code plus EOB) were coded 2663 * on 5 bits or less, inflate may have only 5+3 bits of lookahead to decode 2664 * the last real code. In this case we send two empty static blocks instead 2665 * of one. (There are no problems if the previous block is stored or fixed.) 2666 * To simplify the code, we assume the worst case of last real code encoded 2667 * on one bit only. 2668 */ 2669 void 2670 _tr_align(deflate_state *s) 2671 { 2672 send_bits(s, STATIC_TREES<<1, 3); 2673 send_code(s, END_BLOCK, static_ltree); 2674 s->compressed_len += 10L; /* 3 for block type, 7 for EOB */ 2675 bi_flush(s); 2676 /* Of the 10 bits for the empty block, we have already sent 2677 * (10 - bi_valid) bits. The lookahead for the last real code (before 2678 * the EOB of the previous block) was thus at least one plus the length 2679 * of the EOB plus what we have just sent of the empty static block. 2680 */ 2681 if (1 + s->last_eob_len + 10 - s->bi_valid < 9) { 2682 send_bits(s, STATIC_TREES<<1, 3); 2683 send_code(s, END_BLOCK, static_ltree); 2684 s->compressed_len += 10L; 2685 bi_flush(s); 2686 } 2687 s->last_eob_len = 7; 2688 } 2689 2690 /* =========================================================================== 2691 * Determine the best encoding for the current block: dynamic trees, static 2692 * trees or store, and output the encoded block to the zip file. This function 2693 * returns the total compressed length for the file so far. 2694 * 2695 * Parameters: 2696 * buf: input block, or NULL if too old 2697 * stored_len: length of input block 2698 * eof: true if this is the last block for a file 2699 */ 2700 ulg 2701 _tr_flush_block(deflate_state *s, charf *buf, ulg stored_len, int eof) 2702 { 2703 ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */ 2704 int max_blindex = 0; /* index of last bit length code of non zero freq */ 2705 2706 /* Build the Huffman trees unless a stored block is forced */ 2707 if (s->level > 0) { 2708 2709 /* Check if the file is ascii or binary */ 2710 if (s->data_type == Z_UNKNOWN) set_data_type(s); 2711 2712 /* Construct the literal and distance trees */ 2713 build_tree(s, (tree_desc *)(&(s->l_desc))); 2714 Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len, 2715 s->static_len)); 2716 2717 build_tree(s, (tree_desc *)(&(s->d_desc))); 2718 Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len, 2719 s->static_len)); 2720 /* At this point, opt_len and static_len are the total bit lengths of 2721 * the compressed block data, excluding the tree representations. 2722 */ 2723 2724 /* Build the bit length tree for the above two trees, and get the index 2725 * in bl_order of the last bit length code to send. 2726 */ 2727 max_blindex = build_bl_tree(s); 2728 2729 /* Determine the best encoding. Compute first the block length in bytes*/ 2730 opt_lenb = (s->opt_len+3+7)>>3; 2731 static_lenb = (s->static_len+3+7)>>3; 2732 2733 Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ", 2734 opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len, 2735 s->last_lit)); 2736 2737 if (static_lenb <= opt_lenb) opt_lenb = static_lenb; 2738 2739 } else { 2740 Assert(buf != NULL, "lost buf"); 2741 opt_lenb = static_lenb = stored_len + 5; /* force a stored block */ 2742 } 2743 2744 /* If compression failed and this is the first and last block, 2745 * and if the .zip file can be seeked (to rewrite the local header), 2746 * the whole file is transformed into a stored file: 2747 */ 2748 #ifdef STORED_FILE_OK 2749 # ifdef FORCE_STORED_FILE 2750 if (eof && s->compressed_len == 0L) { /* force stored file */ 2751 # else 2752 if (stored_len <= opt_lenb && eof && s->compressed_len==0L && seekable()) { 2753 # endif 2754 /* Since LIT_BUFSIZE <= 2*WSIZE, the input data must be there: */ 2755 if (buf == NULL) error ("block vanished"); 2756 2757 copy_block(s, buf, (unsigned)stored_len, 0); /* without header */ 2758 s->compressed_len = stored_len << 3; 2759 s->method = STORED; 2760 } else 2761 #endif /* STORED_FILE_OK */ 2762 2763 #ifdef FORCE_STORED 2764 if (buf != NULL) { /* force stored block */ 2765 #else 2766 if (stored_len+4 <= opt_lenb && buf != NULL) { 2767 /* 4: two words for the lengths */ 2768 #endif 2769 /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE. 2770 * Otherwise we can't have processed more than WSIZE input bytes since 2771 * the last block flush, because compression would have been 2772 * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to 2773 * transform a block into a stored block. 2774 */ 2775 _tr_stored_block(s, buf, stored_len, eof); 2776 2777 #ifdef FORCE_STATIC 2778 } else if (static_lenb >= 0) { /* force static trees */ 2779 #else 2780 } else if (static_lenb == opt_lenb) { 2781 #endif 2782 send_bits(s, (STATIC_TREES<<1)+eof, 3); 2783 compress_block(s, (ct_data *)static_ltree, (ct_data *)static_dtree); 2784 s->compressed_len += 3 + s->static_len; 2785 } else { 2786 send_bits(s, (DYN_TREES<<1)+eof, 3); 2787 send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1, 2788 max_blindex+1); 2789 compress_block(s, (ct_data *)s->dyn_ltree, (ct_data *)s->dyn_dtree); 2790 s->compressed_len += 3 + s->opt_len; 2791 } 2792 Assert (s->compressed_len == s->bits_sent, "bad compressed size"); 2793 init_block(s); 2794 2795 if (eof) { 2796 bi_windup(s); 2797 s->compressed_len += 7; /* align on byte boundary */ 2798 } 2799 Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3, 2800 s->compressed_len-7*eof)); 2801 2802 return s->compressed_len >> 3; 2803 } 2804 2805 /* =========================================================================== 2806 * Save the match info and tally the frequency counts. Return true if 2807 * the current block must be flushed. 2808 * 2809 * Parameters: 2810 * dist: distance of matched string 2811 * lc: match length-MIN_MATCH or unmatched char (if dist==0) 2812 */ 2813 int 2814 _tr_tally(deflate_state *s, unsigned dist, unsigned lc) 2815 { 2816 s->d_buf[s->last_lit] = (ush)dist; 2817 s->l_buf[s->last_lit++] = (uch)lc; 2818 if (dist == 0) { 2819 /* lc is the unmatched char */ 2820 s->dyn_ltree[lc].Freq++; 2821 } else { 2822 s->matches++; 2823 /* Here, lc is the match length - MIN_MATCH */ 2824 dist--; /* dist = match distance - 1 */ 2825 Assert((ush)dist < (ush)MAX_DIST(s) && 2826 (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) && 2827 (ush)d_code(dist) < (ush)D_CODES, "_tr_tally: bad match"); 2828 2829 s->dyn_ltree[length_code[lc]+LITERALS+1].Freq++; 2830 s->dyn_dtree[d_code(dist)].Freq++; 2831 } 2832 2833 /* Try to guess if it is profitable to stop the current block here */ 2834 if (s->level > 2 && (s->last_lit & 0xfff) == 0) { 2835 /* Compute an upper bound for the compressed length */ 2836 ulg out_length = (ulg)s->last_lit*8L; 2837 ulg in_length = (ulg)((long)s->strstart - s->block_start); 2838 int dcode; 2839 for (dcode = 0; dcode < D_CODES; dcode++) { 2840 out_length += (ulg)s->dyn_dtree[dcode].Freq * 2841 (5L+extra_dbits[dcode]); 2842 } 2843 out_length >>= 3; 2844 Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ", 2845 s->last_lit, in_length, out_length, 2846 100L - out_length*100L/in_length)); 2847 if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1; 2848 } 2849 return (s->last_lit == s->lit_bufsize-1); 2850 /* We avoid equality with lit_bufsize because of wraparound at 64K 2851 * on 16 bit machines and because stored blocks are restricted to 2852 * 64K-1 bytes. 2853 */ 2854 } 2855 2856 /* =========================================================================== 2857 * Send the block data compressed using the given Huffman trees 2858 * 2859 * Parameters: 2860 * ltree: literal tree 2861 * dtree: distance tree 2862 */ 2863 local void 2864 compress_block(deflate_state *s, ct_data *ltree, ct_data *dtree) 2865 { 2866 unsigned dist; /* distance of matched string */ 2867 int lc; /* match length or unmatched char (if dist == 0) */ 2868 unsigned lx = 0; /* running index in l_buf */ 2869 unsigned code; /* the code to send */ 2870 int extra; /* number of extra bits to send */ 2871 2872 if (s->last_lit != 0) do { 2873 dist = s->d_buf[lx]; 2874 lc = s->l_buf[lx++]; 2875 if (dist == 0) { 2876 send_code(s, lc, ltree); /* send a literal byte */ 2877 Tracecv(isgraph(lc), (stderr," '%c' ", lc)); 2878 } else { 2879 /* Here, lc is the match length - MIN_MATCH */ 2880 code = length_code[lc]; 2881 send_code(s, code+LITERALS+1, ltree); /* send the length code */ 2882 extra = extra_lbits[code]; 2883 if (extra != 0) { 2884 lc -= base_length[code]; 2885 send_bits(s, lc, extra); /* send the extra length bits */ 2886 } 2887 dist--; /* dist is now the match distance - 1 */ 2888 code = d_code(dist); 2889 Assert (code < D_CODES, "bad d_code"); 2890 2891 send_code(s, code, dtree); /* send the distance code */ 2892 extra = extra_dbits[code]; 2893 if (extra != 0) { 2894 dist -= base_dist[code]; 2895 send_bits(s, dist, extra); /* send the extra distance bits */ 2896 } 2897 } /* literal or match pair ? */ 2898 2899 /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */ 2900 Assert(s->pending < s->lit_bufsize + 2*lx, "pendingBuf overflow"); 2901 2902 } while (lx < s->last_lit); 2903 2904 send_code(s, END_BLOCK, ltree); 2905 s->last_eob_len = ltree[END_BLOCK].Len; 2906 } 2907 2908 /* =========================================================================== 2909 * Set the data type to ASCII or BINARY, using a crude approximation: 2910 * binary if more than 20% of the bytes are <= 6 or >= 128, ascii otherwise. 2911 * IN assertion: the fields freq of dyn_ltree are set and the total of all 2912 * frequencies does not exceed 64K (to fit in an int on 16 bit machines). 2913 */ 2914 local void 2915 set_data_type(deflate_state *s) 2916 { 2917 int n = 0; 2918 unsigned ascii_freq = 0; 2919 unsigned bin_freq = 0; 2920 while (n < 7) bin_freq += s->dyn_ltree[n++].Freq; 2921 while (n < 128) ascii_freq += s->dyn_ltree[n++].Freq; 2922 while (n < LITERALS) bin_freq += s->dyn_ltree[n++].Freq; 2923 s->data_type = (Byte)(bin_freq > (ascii_freq >> 2) ? Z_BINARY : Z_ASCII); 2924 } 2925 2926 /* =========================================================================== 2927 * Reverse the first len bits of a code, using straightforward code (a faster 2928 * method would use a table) 2929 * IN assertion: 1 <= len <= 15 2930 * 2931 * Parameters: 2932 * code: the value to invert 2933 * len: its bit length 2934 */ 2935 local unsigned 2936 bi_reverse(unsigned code, int len) 2937 { 2938 unsigned res = 0; 2939 do { 2940 res |= code & 1; 2941 code >>= 1, res <<= 1; 2942 } while (--len > 0); 2943 return res >> 1; 2944 } 2945 2946 /* =========================================================================== 2947 * Flush the bit buffer, keeping at most 7 bits in it. 2948 */ 2949 local void 2950 bi_flush(deflate_state *s) 2951 { 2952 if (s->bi_valid == 16) { 2953 put_short(s, s->bi_buf); 2954 s->bi_buf = 0; 2955 s->bi_valid = 0; 2956 } else if (s->bi_valid >= 8) { 2957 put_byte(s, (Byte)s->bi_buf); 2958 s->bi_buf >>= 8; 2959 s->bi_valid -= 8; 2960 } 2961 } 2962 2963 /* =========================================================================== 2964 * Flush the bit buffer and align the output on a byte boundary 2965 */ 2966 local void 2967 bi_windup(deflate_state *s) 2968 { 2969 if (s->bi_valid > 8) { 2970 put_short(s, s->bi_buf); 2971 } else if (s->bi_valid > 0) { 2972 put_byte(s, (Byte)s->bi_buf); 2973 } 2974 s->bi_buf = 0; 2975 s->bi_valid = 0; 2976 #ifdef DEBUG_ZLIB 2977 s->bits_sent = (s->bits_sent+7) & ~7; 2978 #endif 2979 } 2980 2981 /* =========================================================================== 2982 * Copy a stored block, storing first the length and its 2983 * one's complement if requested. 2984 * 2985 * Parameters: 2986 * buf: the input data 2987 * len: its length 2988 * header: true if block header must be written 2989 */ 2990 local void 2991 copy_block(deflate_state *s, charf *buf, unsigned len, int header) 2992 { 2993 bi_windup(s); /* align on byte boundary */ 2994 s->last_eob_len = 8; /* enough lookahead for inflate */ 2995 2996 if (header) { 2997 put_short(s, (ush)len); 2998 put_short(s, (ush)~len); 2999 #ifdef DEBUG_ZLIB 3000 s->bits_sent += 2*16; 3001 #endif 3002 } 3003 #ifdef DEBUG_ZLIB 3004 s->bits_sent += (ulg)len<<3; 3005 #endif 3006 /* bundle up the put_byte(s, *buf++) calls */ 3007 zmemcpy(&s->pending_buf[s->pending], buf, len); 3008 s->pending += len; 3009 } 3010 /* --- trees.c */ 3011 3012 /* +++ inflate.c */ 3013 /* inflate.c -- zlib interface to inflate modules 3014 * Copyright (C) 1995-1996 Mark Adler 3015 * For conditions of distribution and use, see copyright notice in zlib.h 3016 */ 3017 3018 /* #include "zutil.h" */ 3019 3020 /* +++ infblock.h */ 3021 /* infblock.h -- header to use infblock.c 3022 * Copyright (C) 1995-1996 Mark Adler 3023 * For conditions of distribution and use, see copyright notice in zlib.h 3024 */ 3025 3026 /* WARNING: this file should *not* be used by applications. It is 3027 part of the implementation of the compression library and is 3028 subject to change. Applications should only use zlib.h. 3029 */ 3030 3031 struct inflate_blocks_state; 3032 typedef struct inflate_blocks_state FAR inflate_blocks_statef; 3033 3034 extern inflate_blocks_statef * inflate_blocks_new OF(( 3035 z_streamp z, 3036 check_func c, /* check function */ 3037 uInt w)); /* window size */ 3038 3039 extern int inflate_blocks OF(( 3040 inflate_blocks_statef *, 3041 z_streamp , 3042 int)); /* initial return code */ 3043 3044 extern void inflate_blocks_reset OF(( 3045 inflate_blocks_statef *, 3046 z_streamp , 3047 uLongf *)); /* check value on output */ 3048 3049 extern int inflate_blocks_free OF(( 3050 inflate_blocks_statef *, 3051 z_streamp , 3052 uLongf *)); /* check value on output */ 3053 3054 extern void inflate_set_dictionary OF(( 3055 inflate_blocks_statef *s, 3056 const Bytef *d, /* dictionary */ 3057 uInt n)); /* dictionary length */ 3058 3059 extern int inflate_addhistory OF(( 3060 inflate_blocks_statef *, 3061 z_streamp)); 3062 3063 extern int inflate_packet_flush OF(( 3064 inflate_blocks_statef *)); 3065 /* --- infblock.h */ 3066 3067 #ifndef NO_DUMMY_DECL 3068 struct inflate_blocks_state {int dummy;}; /* for buggy compilers */ 3069 #endif 3070 3071 /* inflate private state */ 3072 struct internal_state { 3073 3074 /* mode */ 3075 enum { 3076 METHOD, /* waiting for method byte */ 3077 FLAG, /* waiting for flag byte */ 3078 DICT4, /* four dictionary check bytes to go */ 3079 DICT3, /* three dictionary check bytes to go */ 3080 DICT2, /* two dictionary check bytes to go */ 3081 DICT1, /* one dictionary check byte to go */ 3082 DICT0, /* waiting for inflateSetDictionary */ 3083 BLOCKS, /* decompressing blocks */ 3084 CHECK4, /* four check bytes to go */ 3085 CHECK3, /* three check bytes to go */ 3086 CHECK2, /* two check bytes to go */ 3087 CHECK1, /* one check byte to go */ 3088 DONE, /* finished check, done */ 3089 BAD} /* got an error--stay here */ 3090 mode; /* current inflate mode */ 3091 3092 /* mode dependent information */ 3093 union { 3094 uInt method; /* if FLAGS, method byte */ 3095 struct { 3096 uLong was; /* computed check value */ 3097 uLong need; /* stream check value */ 3098 } check; /* if CHECK, check values to compare */ 3099 uInt marker; /* if BAD, inflateSync's marker bytes count */ 3100 } sub; /* submode */ 3101 3102 /* mode independent information */ 3103 int nowrap; /* flag for no wrapper */ 3104 uInt wbits; /* log2(window size) (8..15, defaults to 15) */ 3105 inflate_blocks_statef 3106 *blocks; /* current inflate_blocks state */ 3107 3108 }; 3109 3110 3111 int 3112 inflateReset(z_streamp z) 3113 { 3114 uLong c; 3115 3116 if (z == Z_NULL || z->state == Z_NULL) 3117 return Z_STREAM_ERROR; 3118 z->total_in = z->total_out = 0; 3119 z->msg = Z_NULL; 3120 z->state->mode = z->state->nowrap ? BLOCKS : METHOD; 3121 inflate_blocks_reset(z->state->blocks, z, &c); 3122 Trace((stderr, "inflate: reset\n")); 3123 return Z_OK; 3124 } 3125 3126 3127 int 3128 inflateEnd(z_streamp z) 3129 { 3130 uLong c; 3131 3132 if (z == Z_NULL || z->state == Z_NULL || z->zfree == Z_NULL) 3133 return Z_STREAM_ERROR; 3134 if (z->state->blocks != Z_NULL) 3135 inflate_blocks_free(z->state->blocks, z, &c); 3136 ZFREE(z, z->state); 3137 z->state = Z_NULL; 3138 Trace((stderr, "inflate: end\n")); 3139 return Z_OK; 3140 } 3141 3142 3143 int 3144 inflateInit2_(z_streamp z, int w, const char *version, int stream_size) 3145 { 3146 if (version == Z_NULL || version[0] != ZLIB_VERSION[0] || 3147 stream_size != sizeof(z_stream)) 3148 return Z_VERSION_ERROR; 3149 3150 /* initialize state */ 3151 if (z == Z_NULL) 3152 return Z_STREAM_ERROR; 3153 z->msg = Z_NULL; 3154 #ifndef NO_ZCFUNCS 3155 if (z->zalloc == Z_NULL) 3156 { 3157 z->zalloc = zcalloc; 3158 z->opaque = (voidpf)0; 3159 } 3160 if (z->zfree == Z_NULL) z->zfree = zcfree; 3161 #endif 3162 if ((z->state = (struct internal_state FAR *) 3163 ZALLOC(z,1,sizeof(struct internal_state))) == Z_NULL) 3164 return Z_MEM_ERROR; 3165 z->state->blocks = Z_NULL; 3166 3167 /* handle undocumented nowrap option (no zlib header or check) */ 3168 z->state->nowrap = 0; 3169 if (w < 0) 3170 { 3171 w = - w; 3172 z->state->nowrap = 1; 3173 } 3174 3175 /* set window size */ 3176 if (w < 8 || w > 15) 3177 { 3178 inflateEnd(z); 3179 return Z_STREAM_ERROR; 3180 } 3181 z->state->wbits = (uInt)w; 3182 3183 /* create inflate_blocks state */ 3184 if ((z->state->blocks = 3185 inflate_blocks_new(z, z->state->nowrap ? Z_NULL : adler32, (uInt)1 << w)) 3186 == Z_NULL) 3187 { 3188 inflateEnd(z); 3189 return Z_MEM_ERROR; 3190 } 3191 Trace((stderr, "inflate: allocated\n")); 3192 3193 /* reset state */ 3194 inflateReset(z); 3195 return Z_OK; 3196 } 3197 3198 3199 int 3200 inflateInit_(z_streamp z, const char *version, int stream_size) 3201 { 3202 return inflateInit2_(z, DEF_WBITS, version, stream_size); 3203 } 3204 3205 3206 #define NEEDBYTE {if(z->avail_in==0)goto empty;r=Z_OK;} 3207 #define NEXTBYTE (z->avail_in--,z->total_in++,*z->next_in++) 3208 3209 int 3210 inflate(z_streamp z, int f) 3211 { 3212 int r; 3213 uInt b; 3214 3215 if (z == Z_NULL || z->state == Z_NULL || z->next_in == Z_NULL || f < 0) 3216 return Z_STREAM_ERROR; 3217 r = Z_BUF_ERROR; 3218 while (1) switch (z->state->mode) 3219 { 3220 case METHOD: 3221 NEEDBYTE 3222 if (((z->state->sub.method = NEXTBYTE) & 0xf) != Z_DEFLATED) 3223 { 3224 z->state->mode = BAD; 3225 z->msg = (char*)"unknown compression method"; 3226 z->state->sub.marker = 5; /* can't try inflateSync */ 3227 break; 3228 } 3229 if ((z->state->sub.method >> 4) + 8 > z->state->wbits) 3230 { 3231 z->state->mode = BAD; 3232 z->msg = (char*)"invalid window size"; 3233 z->state->sub.marker = 5; /* can't try inflateSync */ 3234 break; 3235 } 3236 z->state->mode = FLAG; 3237 case FLAG: 3238 NEEDBYTE 3239 b = NEXTBYTE; 3240 if (((z->state->sub.method << 8) + b) % 31) 3241 { 3242 z->state->mode = BAD; 3243 z->msg = (char*)"incorrect header check"; 3244 z->state->sub.marker = 5; /* can't try inflateSync */ 3245 break; 3246 } 3247 Trace((stderr, "inflate: zlib header ok\n")); 3248 if (!(b & PRESET_DICT)) 3249 { 3250 z->state->mode = BLOCKS; 3251 break; 3252 } 3253 z->state->mode = DICT4; 3254 case DICT4: 3255 NEEDBYTE 3256 z->state->sub.check.need = (uLong)NEXTBYTE << 24; 3257 z->state->mode = DICT3; 3258 case DICT3: 3259 NEEDBYTE 3260 z->state->sub.check.need += (uLong)NEXTBYTE << 16; 3261 z->state->mode = DICT2; 3262 case DICT2: 3263 NEEDBYTE 3264 z->state->sub.check.need += (uLong)NEXTBYTE << 8; 3265 z->state->mode = DICT1; 3266 case DICT1: 3267 NEEDBYTE 3268 z->state->sub.check.need += (uLong)NEXTBYTE; 3269 z->adler = z->state->sub.check.need; 3270 z->state->mode = DICT0; 3271 return Z_NEED_DICT; 3272 case DICT0: 3273 z->state->mode = BAD; 3274 z->msg = (char*)"need dictionary"; 3275 z->state->sub.marker = 0; /* can try inflateSync */ 3276 return Z_STREAM_ERROR; 3277 case BLOCKS: 3278 r = inflate_blocks(z->state->blocks, z, r); 3279 if (f == Z_PACKET_FLUSH && z->avail_in == 0 && z->avail_out != 0) 3280 r = inflate_packet_flush(z->state->blocks); 3281 if (r == Z_DATA_ERROR) 3282 { 3283 z->state->mode = BAD; 3284 z->state->sub.marker = 0; /* can try inflateSync */ 3285 break; 3286 } 3287 if (r != Z_STREAM_END) 3288 return r; 3289 r = Z_OK; 3290 inflate_blocks_reset(z->state->blocks, z, &z->state->sub.check.was); 3291 if (z->state->nowrap) 3292 { 3293 z->state->mode = DONE; 3294 break; 3295 } 3296 z->state->mode = CHECK4; 3297 case CHECK4: 3298 NEEDBYTE 3299 z->state->sub.check.need = (uLong)NEXTBYTE << 24; 3300 z->state->mode = CHECK3; 3301 case CHECK3: 3302 NEEDBYTE 3303 z->state->sub.check.need += (uLong)NEXTBYTE << 16; 3304 z->state->mode = CHECK2; 3305 case CHECK2: 3306 NEEDBYTE 3307 z->state->sub.check.need += (uLong)NEXTBYTE << 8; 3308 z->state->mode = CHECK1; 3309 case CHECK1: 3310 NEEDBYTE 3311 z->state->sub.check.need += (uLong)NEXTBYTE; 3312 3313 if (z->state->sub.check.was != z->state->sub.check.need) 3314 { 3315 z->state->mode = BAD; 3316 z->msg = (char*)"incorrect data check"; 3317 z->state->sub.marker = 5; /* can't try inflateSync */ 3318 break; 3319 } 3320 Trace((stderr, "inflate: zlib check ok\n")); 3321 z->state->mode = DONE; 3322 case DONE: 3323 return Z_STREAM_END; 3324 case BAD: 3325 return Z_DATA_ERROR; 3326 default: 3327 return Z_STREAM_ERROR; 3328 } 3329 3330 empty: 3331 if (f != Z_PACKET_FLUSH) 3332 return r; 3333 z->state->mode = BAD; 3334 z->msg = (char *)"need more for packet flush"; 3335 z->state->sub.marker = 0; /* can try inflateSync */ 3336 return Z_DATA_ERROR; 3337 } 3338 3339 3340 int 3341 inflateSetDictionary(z_streamp z, const Bytef *dictionary, uInt dictLength) 3342 { 3343 uInt length = dictLength; 3344 3345 if (z == Z_NULL || z->state == Z_NULL || z->state->mode != DICT0) 3346 return Z_STREAM_ERROR; 3347 3348 if (adler32(1L, dictionary, dictLength) != z->adler) return Z_DATA_ERROR; 3349 z->adler = 1L; 3350 3351 if (length >= ((uInt)1<<z->state->wbits)) 3352 { 3353 length = (1<<z->state->wbits)-1; 3354 dictionary += dictLength - length; 3355 } 3356 inflate_set_dictionary(z->state->blocks, dictionary, length); 3357 z->state->mode = BLOCKS; 3358 return Z_OK; 3359 } 3360 3361 /* 3362 * This subroutine adds the data at next_in/avail_in to the output history 3363 * without performing any output. The output buffer must be "caught up"; 3364 * i.e. no pending output (hence s->read equals s->write), and the state must 3365 * be BLOCKS (i.e. we should be willing to see the start of a series of 3366 * BLOCKS). On exit, the output will also be caught up, and the checksum 3367 * will have been updated if need be. 3368 */ 3369 3370 int 3371 inflateIncomp(z_stream *z) 3372 { 3373 if (z->state->mode != BLOCKS) 3374 return Z_DATA_ERROR; 3375 return inflate_addhistory(z->state->blocks, z); 3376 } 3377 3378 3379 int 3380 inflateSync(z_streamp z) 3381 { 3382 uInt n; /* number of bytes to look at */ 3383 Bytef *p; /* pointer to bytes */ 3384 uInt m; /* number of marker bytes found in a row */ 3385 uLong r, w; /* temporaries to save total_in and total_out */ 3386 3387 /* set up */ 3388 if (z == Z_NULL || z->state == Z_NULL) 3389 return Z_STREAM_ERROR; 3390 if (z->state->mode != BAD) 3391 { 3392 z->state->mode = BAD; 3393 z->state->sub.marker = 0; 3394 } 3395 if ((n = z->avail_in) == 0) 3396 return Z_BUF_ERROR; 3397 p = z->next_in; 3398 m = z->state->sub.marker; 3399 3400 /* search */ 3401 while (n && m < 4) 3402 { 3403 if (*p == (Byte)(m < 2 ? 0 : 0xff)) 3404 m++; 3405 else if (*p) 3406 m = 0; 3407 else 3408 m = 4 - m; 3409 p++, n--; 3410 } 3411 3412 /* restore */ 3413 z->total_in += p - z->next_in; 3414 z->next_in = p; 3415 z->avail_in = n; 3416 z->state->sub.marker = m; 3417 3418 /* return no joy or set up to restart on a new block */ 3419 if (m != 4) 3420 return Z_DATA_ERROR; 3421 r = z->total_in; w = z->total_out; 3422 inflateReset(z); 3423 z->total_in = r; z->total_out = w; 3424 z->state->mode = BLOCKS; 3425 return Z_OK; 3426 } 3427 3428 #undef NEEDBYTE 3429 #undef NEXTBYTE 3430 /* --- inflate.c */ 3431 3432 /* +++ infblock.c */ 3433 /* infblock.c -- interpret and process block types to last block 3434 * Copyright (C) 1995-1996 Mark Adler 3435 * For conditions of distribution and use, see copyright notice in zlib.h 3436 */ 3437 3438 /* #include "zutil.h" */ 3439 /* #include "infblock.h" */ 3440 3441 /* +++ inftrees.h */ 3442 /* inftrees.h -- header to use inftrees.c 3443 * Copyright (C) 1995-1996 Mark Adler 3444 * For conditions of distribution and use, see copyright notice in zlib.h 3445 */ 3446 3447 /* WARNING: this file should *not* be used by applications. It is 3448 part of the implementation of the compression library and is 3449 subject to change. Applications should only use zlib.h. 3450 */ 3451 3452 /* Huffman code lookup table entry--this entry is four bytes for machines 3453 that have 16-bit pointers (e.g. PC's in the small or medium model). */ 3454 3455 typedef struct inflate_huft_s FAR inflate_huft; 3456 3457 struct inflate_huft_s { 3458 union { 3459 struct { 3460 Byte Exop; /* number of extra bits or operation */ 3461 Byte Bits; /* number of bits in this code or subcode */ 3462 } what; 3463 Bytef *pad; /* pad structure to a power of 2 (4 bytes for */ 3464 } word; /* 16-bit, 8 bytes for 32-bit machines) */ 3465 union { 3466 uInt Base; /* literal, length base, or distance base */ 3467 inflate_huft *Next; /* pointer to next level of table */ 3468 } more; 3469 }; 3470 3471 #ifdef DEBUG_ZLIB 3472 extern uInt inflate_hufts; 3473 #endif 3474 3475 extern int inflate_trees_bits OF(( 3476 uIntf *, /* 19 code lengths */ 3477 uIntf *, /* bits tree desired/actual depth */ 3478 inflate_huft * FAR *, /* bits tree result */ 3479 z_streamp )); /* for zalloc, zfree functions */ 3480 3481 extern int inflate_trees_dynamic OF(( 3482 uInt, /* number of literal/length codes */ 3483 uInt, /* number of distance codes */ 3484 uIntf *, /* that many (total) code lengths */ 3485 uIntf *, /* literal desired/actual bit depth */ 3486 uIntf *, /* distance desired/actual bit depth */ 3487 inflate_huft * FAR *, /* literal/length tree result */ 3488 inflate_huft * FAR *, /* distance tree result */ 3489 z_streamp )); /* for zalloc, zfree functions */ 3490 3491 extern int inflate_trees_fixed OF(( 3492 uIntf *, /* literal desired/actual bit depth */ 3493 uIntf *, /* distance desired/actual bit depth */ 3494 inflate_huft * FAR *, /* literal/length tree result */ 3495 inflate_huft * FAR *)); /* distance tree result */ 3496 3497 extern int inflate_trees_free OF(( 3498 inflate_huft *, /* tables to free */ 3499 z_streamp )); /* for zfree function */ 3500 3501 /* --- inftrees.h */ 3502 3503 /* +++ infcodes.h */ 3504 /* infcodes.h -- header to use infcodes.c 3505 * Copyright (C) 1995-1996 Mark Adler 3506 * For conditions of distribution and use, see copyright notice in zlib.h 3507 */ 3508 3509 /* WARNING: this file should *not* be used by applications. It is 3510 part of the implementation of the compression library and is 3511 subject to change. Applications should only use zlib.h. 3512 */ 3513 3514 struct inflate_codes_state; 3515 typedef struct inflate_codes_state FAR inflate_codes_statef; 3516 3517 extern inflate_codes_statef *inflate_codes_new OF(( 3518 uInt, uInt, 3519 inflate_huft *, inflate_huft *, 3520 z_streamp )); 3521 3522 extern int inflate_codes OF(( 3523 inflate_blocks_statef *, 3524 z_streamp , 3525 int)); 3526 3527 extern void inflate_codes_free OF(( 3528 inflate_codes_statef *, 3529 z_streamp )); 3530 3531 /* --- infcodes.h */ 3532 3533 /* +++ infutil.h */ 3534 /* infutil.h -- types and macros common to blocks and codes 3535 * Copyright (C) 1995-1996 Mark Adler 3536 * For conditions of distribution and use, see copyright notice in zlib.h 3537 */ 3538 3539 /* WARNING: this file should *not* be used by applications. It is 3540 part of the implementation of the compression library and is 3541 subject to change. Applications should only use zlib.h. 3542 */ 3543 3544 #ifndef _INFUTIL_H 3545 #define _INFUTIL_H 3546 3547 typedef enum { 3548 TYPE, /* get type bits (3, including end bit) */ 3549 LENS, /* get lengths for stored */ 3550 STORED, /* processing stored block */ 3551 TABLE, /* get table lengths */ 3552 BTREE, /* get bit lengths tree for a dynamic block */ 3553 DTREE, /* get length, distance trees for a dynamic block */ 3554 CODES, /* processing fixed or dynamic block */ 3555 DRY, /* output remaining window bytes */ 3556 DONEB, /* finished last block, done */ 3557 BADB} /* got a data error--stuck here */ 3558 inflate_block_mode; 3559 3560 /* inflate blocks semi-private state */ 3561 struct inflate_blocks_state { 3562 3563 /* mode */ 3564 inflate_block_mode mode; /* current inflate_block mode */ 3565 3566 /* mode dependent information */ 3567 union { 3568 uInt left; /* if STORED, bytes left to copy */ 3569 struct { 3570 uInt table; /* table lengths (14 bits) */ 3571 uInt index; /* index into blens (or border) */ 3572 uIntf *blens; /* bit lengths of codes */ 3573 uInt bb; /* bit length tree depth */ 3574 inflate_huft *tb; /* bit length decoding tree */ 3575 } trees; /* if DTREE, decoding info for trees */ 3576 struct { 3577 inflate_huft *tl; 3578 inflate_huft *td; /* trees to free */ 3579 inflate_codes_statef 3580 *codes; 3581 } decode; /* if CODES, current state */ 3582 } sub; /* submode */ 3583 uInt last; /* true if this block is the last block */ 3584 3585 /* mode independent information */ 3586 uInt bitk; /* bits in bit buffer */ 3587 uLong bitb; /* bit buffer */ 3588 Bytef *window; /* sliding window */ 3589 Bytef *end; /* one byte after sliding window */ 3590 Bytef *read; /* window read pointer */ 3591 Bytef *write; /* window write pointer */ 3592 check_func checkfn; /* check function */ 3593 uLong check; /* check on output */ 3594 3595 }; 3596 3597 3598 /* defines for inflate input/output */ 3599 /* update pointers and return */ 3600 #define UPDBITS {s->bitb=b;s->bitk=k;} 3601 #define UPDIN {z->avail_in=n;z->total_in+=p-z->next_in;z->next_in=p;} 3602 #define UPDOUT {s->write=q;} 3603 #define UPDATE {UPDBITS UPDIN UPDOUT} 3604 #define LEAVE {UPDATE return inflate_flush(s,z,r);} 3605 /* get bytes and bits */ 3606 #define LOADIN {p=z->next_in;n=z->avail_in;b=s->bitb;k=s->bitk;} 3607 #define NEEDBYTE {if(n)r=Z_OK;else LEAVE} 3608 #define NEXTBYTE (n--,*p++) 3609 #define NEEDBITS(j) {while(k<(j)){NEEDBYTE;b|=((uLong)NEXTBYTE)<<k;k+=8;}} 3610 #define DUMPBITS(j) {b>>=(j);k-=(j);} 3611 /* output bytes */ 3612 #define WAVAIL (uInt)(q<s->read?s->read-q-1:s->end-q) 3613 #define LOADOUT {q=s->write;m=(uInt)WAVAIL;} 3614 #define WWRAP {if(q==s->end&&s->read!=s->window){q=s->window;m=(uInt)WAVAIL;}} 3615 #define FLUSH {UPDOUT r=inflate_flush(s,z,r); LOADOUT} 3616 #define NEEDOUT {if(m==0){WWRAP if(m==0){FLUSH WWRAP if(m==0) LEAVE}}r=Z_OK;} 3617 #define OUTBYTE(a) {*q++=(Byte)(a);m--;} 3618 /* load local pointers */ 3619 #define LOAD {LOADIN LOADOUT} 3620 3621 /* masks for lower bits (size given to avoid silly warnings with Visual C++) */ 3622 extern uInt inflate_mask[17]; 3623 3624 /* copy as much as possible from the sliding window to the output area */ 3625 extern int inflate_flush OF(( 3626 inflate_blocks_statef *, 3627 z_streamp , 3628 int)); 3629 3630 #ifndef NO_DUMMY_DECL 3631 struct internal_state {int dummy;}; /* for buggy compilers */ 3632 #endif 3633 3634 #endif 3635 /* --- infutil.h */ 3636 3637 #ifndef NO_DUMMY_DECL 3638 struct inflate_codes_state {int dummy;}; /* for buggy compilers */ 3639 #endif 3640 3641 /* Table for deflate from PKZIP's appnote.txt. */ 3642 local const uInt border[] = { /* Order of the bit length code lengths */ 3643 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; 3644 3645 /* 3646 Notes beyond the 1.93a appnote.txt: 3647 3648 1. Distance pointers never point before the beginning of the output 3649 stream. 3650 2. Distance pointers can point back across blocks, up to 32k away. 3651 3. There is an implied maximum of 7 bits for the bit length table and 3652 15 bits for the actual data. 3653 4. If only one code exists, then it is encoded using one bit. (Zero 3654 would be more efficient, but perhaps a little confusing.) If two 3655 codes exist, they are coded using one bit each (0 and 1). 3656 5. There is no way of sending zero distance codes--a dummy must be 3657 sent if there are none. (History: a pre 2.0 version of PKZIP would 3658 store blocks with no distance codes, but this was discovered to be 3659 too harsh a criterion.) Valid only for 1.93a. 2.04c does allow 3660 zero distance codes, which is sent as one code of zero bits in 3661 length. 3662 6. There are up to 286 literal/length codes. Code 256 represents the 3663 end-of-block. Note however that the static length tree defines 3664 288 codes just to fill out the Huffman codes. Codes 286 and 287 3665 cannot be used though, since there is no length base or extra bits 3666 defined for them. Similarily, there are up to 30 distance codes. 3667 However, static trees define 32 codes (all 5 bits) to fill out the 3668 Huffman codes, but the last two had better not show up in the data. 3669 7. Unzip can check dynamic Huffman blocks for complete code sets. 3670 The exception is that a single code would not be complete (see #4). 3671 8. The five bits following the block type is really the number of 3672 literal codes sent minus 257. 3673 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits 3674 (1+6+6). Therefore, to output three times the length, you output 3675 three codes (1+1+1), whereas to output four times the same length, 3676 you only need two codes (1+3). Hmm. 3677 10. In the tree reconstruction algorithm, Code = Code + Increment 3678 only if BitLength(i) is not zero. (Pretty obvious.) 3679 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19) 3680 12. Note: length code 284 can represent 227-258, but length code 285 3681 really is 258. The last length deserves its own, short code 3682 since it gets used a lot in very redundant files. The length 3683 258 is special since 258 - 3 (the min match length) is 255. 3684 13. The literal/length and distance code bit lengths are read as a 3685 single stream of lengths. It is possible (and advantageous) for 3686 a repeat code (16, 17, or 18) to go across the boundary between 3687 the two sets of lengths. 3688 */ 3689 3690 3691 void 3692 inflate_blocks_reset(inflate_blocks_statef *s, z_streamp z, uLongf *c) 3693 { 3694 if (s->checkfn != Z_NULL) 3695 *c = s->check; 3696 if (s->mode == BTREE || s->mode == DTREE) 3697 ZFREE(z, s->sub.trees.blens); 3698 if (s->mode == CODES) 3699 { 3700 inflate_codes_free(s->sub.decode.codes, z); 3701 inflate_trees_free(s->sub.decode.td, z); 3702 inflate_trees_free(s->sub.decode.tl, z); 3703 } 3704 s->mode = TYPE; 3705 s->bitk = 0; 3706 s->bitb = 0; 3707 s->read = s->write = s->window; 3708 if (s->checkfn != Z_NULL) 3709 z->adler = s->check = (*s->checkfn)(0L, Z_NULL, 0); 3710 Trace((stderr, "inflate: blocks reset\n")); 3711 } 3712 3713 3714 inflate_blocks_statef * 3715 inflate_blocks_new(z_streamp z, check_func c, uInt w) 3716 { 3717 inflate_blocks_statef *s; 3718 3719 if ((s = (inflate_blocks_statef *)ZALLOC 3720 (z,1,sizeof(struct inflate_blocks_state))) == Z_NULL) 3721 return s; 3722 if ((s->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL) 3723 { 3724 ZFREE(z, s); 3725 return Z_NULL; 3726 } 3727 s->end = s->window + w; 3728 s->checkfn = c; 3729 s->mode = TYPE; 3730 Trace((stderr, "inflate: blocks allocated\n")); 3731 inflate_blocks_reset(s, z, &s->check); 3732 return s; 3733 } 3734 3735 3736 #ifdef DEBUG_ZLIB 3737 extern uInt inflate_hufts; 3738 #endif 3739 3740 int 3741 inflate_blocks(inflate_blocks_statef *s, z_streamp z, int r) 3742 { 3743 uInt t; /* temporary storage */ 3744 uLong b; /* bit buffer */ 3745 uInt k; /* bits in bit buffer */ 3746 Bytef *p; /* input data pointer */ 3747 uInt n; /* bytes available there */ 3748 Bytef *q; /* output window write pointer */ 3749 uInt m; /* bytes to end of window or read pointer */ 3750 3751 /* copy input/output information to locals (UPDATE macro restores) */ 3752 LOAD 3753 3754 /* process input based on current state */ 3755 while (1) switch (s->mode) 3756 { 3757 case TYPE: 3758 NEEDBITS(3) 3759 t = (uInt)b & 7; 3760 s->last = t & 1; 3761 switch (t >> 1) 3762 { 3763 case 0: /* stored */ 3764 Trace((stderr, "inflate: stored block%s\n", 3765 s->last ? " (last)" : "")); 3766 DUMPBITS(3) 3767 t = k & 7; /* go to byte boundary */ 3768 DUMPBITS(t) 3769 s->mode = LENS; /* get length of stored block */ 3770 break; 3771 case 1: /* fixed */ 3772 Trace((stderr, "inflate: fixed codes block%s\n", 3773 s->last ? " (last)" : "")); 3774 { 3775 uInt bl, bd; 3776 inflate_huft *tl, *td; 3777 3778 inflate_trees_fixed(&bl, &bd, &tl, &td); 3779 s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z); 3780 if (s->sub.decode.codes == Z_NULL) 3781 { 3782 r = Z_MEM_ERROR; 3783 LEAVE 3784 } 3785 s->sub.decode.tl = Z_NULL; /* don't try to free these */ 3786 s->sub.decode.td = Z_NULL; 3787 } 3788 DUMPBITS(3) 3789 s->mode = CODES; 3790 break; 3791 case 2: /* dynamic */ 3792 Trace((stderr, "inflate: dynamic codes block%s\n", 3793 s->last ? " (last)" : "")); 3794 DUMPBITS(3) 3795 s->mode = TABLE; 3796 break; 3797 case 3: /* illegal */ 3798 DUMPBITS(3) 3799 s->mode = BADB; 3800 z->msg = (char*)"invalid block type"; 3801 r = Z_DATA_ERROR; 3802 LEAVE 3803 } 3804 break; 3805 case LENS: 3806 NEEDBITS(32) 3807 if ((((~b) >> 16) & 0xffff) != (b & 0xffff)) 3808 { 3809 s->mode = BADB; 3810 z->msg = (char*)"invalid stored block lengths"; 3811 r = Z_DATA_ERROR; 3812 LEAVE 3813 } 3814 s->sub.left = (uInt)b & 0xffff; 3815 b = k = 0; /* dump bits */ 3816 Tracev((stderr, "inflate: stored length %u\n", s->sub.left)); 3817 s->mode = s->sub.left ? STORED : (s->last ? DRY : TYPE); 3818 break; 3819 case STORED: 3820 if (n == 0) 3821 LEAVE 3822 NEEDOUT 3823 t = s->sub.left; 3824 if (t > n) t = n; 3825 if (t > m) t = m; 3826 zmemcpy(q, p, t); 3827 p += t; n -= t; 3828 q += t; m -= t; 3829 if ((s->sub.left -= t) != 0) 3830 break; 3831 Tracev((stderr, "inflate: stored end, %lu total out\n", 3832 z->total_out + (q >= s->read ? q - s->read : 3833 (s->end - s->read) + (q - s->window)))); 3834 s->mode = s->last ? DRY : TYPE; 3835 break; 3836 case TABLE: 3837 NEEDBITS(14) 3838 s->sub.trees.table = t = (uInt)b & 0x3fff; 3839 #ifndef PKZIP_BUG_WORKAROUND 3840 if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29) 3841 { 3842 s->mode = BADB; 3843 z->msg = (char*)"too many length or distance symbols"; 3844 r = Z_DATA_ERROR; 3845 LEAVE 3846 } 3847 #endif 3848 t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f); 3849 if (t < 19) 3850 t = 19; 3851 if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL) 3852 { 3853 r = Z_MEM_ERROR; 3854 LEAVE 3855 } 3856 DUMPBITS(14) 3857 s->sub.trees.index = 0; 3858 Tracev((stderr, "inflate: table sizes ok\n")); 3859 s->mode = BTREE; 3860 case BTREE: 3861 while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10)) 3862 { 3863 NEEDBITS(3) 3864 s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7; 3865 DUMPBITS(3) 3866 } 3867 while (s->sub.trees.index < 19) 3868 s->sub.trees.blens[border[s->sub.trees.index++]] = 0; 3869 s->sub.trees.bb = 7; 3870 t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb, 3871 &s->sub.trees.tb, z); 3872 if (t != Z_OK) 3873 { 3874 r = t; 3875 if (r == Z_DATA_ERROR) { 3876 ZFREE(z, s->sub.trees.blens); 3877 s->mode = BADB; 3878 } 3879 LEAVE 3880 } 3881 s->sub.trees.index = 0; 3882 Tracev((stderr, "inflate: bits tree ok\n")); 3883 s->mode = DTREE; 3884 case DTREE: 3885 while (t = s->sub.trees.table, 3886 s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f)) 3887 { 3888 inflate_huft *h; 3889 uInt i, j, c; 3890 3891 t = s->sub.trees.bb; 3892 NEEDBITS(t) 3893 h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]); 3894 t = h->word.what.Bits; 3895 c = h->more.Base; 3896 if (c < 16) 3897 { 3898 DUMPBITS(t) 3899 s->sub.trees.blens[s->sub.trees.index++] = c; 3900 } 3901 else /* c == 16..18 */ 3902 { 3903 i = c == 18 ? 7 : c - 14; 3904 j = c == 18 ? 11 : 3; 3905 NEEDBITS(t + i) 3906 DUMPBITS(t) 3907 j += (uInt)b & inflate_mask[i]; 3908 DUMPBITS(i) 3909 i = s->sub.trees.index; 3910 t = s->sub.trees.table; 3911 if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) || 3912 (c == 16 && i < 1)) 3913 { 3914 inflate_trees_free(s->sub.trees.tb, z); 3915 ZFREE(z, s->sub.trees.blens); 3916 s->mode = BADB; 3917 z->msg = (char*)"invalid bit length repeat"; 3918 r = Z_DATA_ERROR; 3919 LEAVE 3920 } 3921 c = c == 16 ? s->sub.trees.blens[i - 1] : 0; 3922 do { 3923 s->sub.trees.blens[i++] = c; 3924 } while (--j); 3925 s->sub.trees.index = i; 3926 } 3927 } 3928 inflate_trees_free(s->sub.trees.tb, z); 3929 s->sub.trees.tb = Z_NULL; 3930 { 3931 uInt bl, bd; 3932 inflate_huft *tl, *td; 3933 inflate_codes_statef *c; 3934 3935 bl = 9; /* must be <= 9 for lookahead assumptions */ 3936 bd = 6; /* must be <= 9 for lookahead assumptions */ 3937 t = s->sub.trees.table; 3938 #ifdef DEBUG_ZLIB 3939 inflate_hufts = 0; 3940 #endif 3941 t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f), 3942 s->sub.trees.blens, &bl, &bd, &tl, &td, z); 3943 if (t != Z_OK) 3944 { 3945 if (t == (uInt)Z_DATA_ERROR) { 3946 ZFREE(z, s->sub.trees.blens); 3947 s->mode = BADB; 3948 } 3949 r = t; 3950 LEAVE 3951 } 3952 Tracev((stderr, "inflate: trees ok, %d * %d bytes used\n", 3953 inflate_hufts, sizeof(inflate_huft))); 3954 if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL) 3955 { 3956 inflate_trees_free(td, z); 3957 inflate_trees_free(tl, z); 3958 r = Z_MEM_ERROR; 3959 LEAVE 3960 } 3961 /* 3962 * this ZFREE must occur *BEFORE* we mess with sub.decode, because 3963 * sub.trees is union'd with sub.decode. 3964 */ 3965 ZFREE(z, s->sub.trees.blens); 3966 s->sub.decode.codes = c; 3967 s->sub.decode.tl = tl; 3968 s->sub.decode.td = td; 3969 } 3970 s->mode = CODES; 3971 case CODES: 3972 UPDATE 3973 if ((r = inflate_codes(s, z, r)) != Z_STREAM_END) 3974 return inflate_flush(s, z, r); 3975 r = Z_OK; 3976 inflate_codes_free(s->sub.decode.codes, z); 3977 inflate_trees_free(s->sub.decode.td, z); 3978 inflate_trees_free(s->sub.decode.tl, z); 3979 LOAD 3980 Tracev((stderr, "inflate: codes end, %lu total out\n", 3981 z->total_out + (q >= s->read ? q - s->read : 3982 (s->end - s->read) + (q - s->window)))); 3983 if (!s->last) 3984 { 3985 s->mode = TYPE; 3986 break; 3987 } 3988 if (k > 7) /* return unused byte, if any */ 3989 { 3990 Assert(k < 16, "inflate_codes grabbed too many bytes") 3991 k -= 8; 3992 n++; 3993 p--; /* can always return one */ 3994 } 3995 s->mode = DRY; 3996 case DRY: 3997 FLUSH 3998 if (s->read != s->write) 3999 LEAVE 4000 s->mode = DONEB; 4001 case DONEB: 4002 r = Z_STREAM_END; 4003 LEAVE 4004 case BADB: 4005 r = Z_DATA_ERROR; 4006 LEAVE 4007 default: 4008 r = Z_STREAM_ERROR; 4009 LEAVE 4010 } 4011 } 4012 4013 4014 int 4015 inflate_blocks_free(inflate_blocks_statef *s, z_streamp z, uLongf *c) 4016 { 4017 inflate_blocks_reset(s, z, c); 4018 ZFREE(z, s->window); 4019 ZFREE(z, s); 4020 Trace((stderr, "inflate: blocks freed\n")); 4021 return Z_OK; 4022 } 4023 4024 4025 void 4026 inflate_set_dictionary(inflate_blocks_statef *s, const Bytef *d, uInt n) 4027 { 4028 zmemcpy((charf *)s->window, d, n); 4029 s->read = s->write = s->window + n; 4030 } 4031 4032 /* 4033 * This subroutine adds the data at next_in/avail_in to the output history 4034 * without performing any output. The output buffer must be "caught up"; 4035 * i.e. no pending output (hence s->read equals s->write), and the state must 4036 * be BLOCKS (i.e. we should be willing to see the start of a series of 4037 * BLOCKS). On exit, the output will also be caught up, and the checksum 4038 * will have been updated if need be. 4039 */ 4040 int 4041 inflate_addhistory(inflate_blocks_statef *s, z_stream *z) 4042 { 4043 uLong b; /* bit buffer */ /* NOT USED HERE */ 4044 uInt k; /* bits in bit buffer */ /* NOT USED HERE */ 4045 uInt t; /* temporary storage */ 4046 Bytef *p; /* input data pointer */ 4047 uInt n; /* bytes available there */ 4048 Bytef *q; /* output window write pointer */ 4049 uInt m; /* bytes to end of window or read pointer */ 4050 4051 if (s->read != s->write) 4052 return Z_STREAM_ERROR; 4053 if (s->mode != TYPE) 4054 return Z_DATA_ERROR; 4055 4056 /* we're ready to rock */ 4057 LOAD 4058 /* while there is input ready, copy to output buffer, moving 4059 * pointers as needed. 4060 */ 4061 while (n) { 4062 t = n; /* how many to do */ 4063 /* is there room until end of buffer? */ 4064 if (t > m) t = m; 4065 /* update check information */ 4066 if (s->checkfn != Z_NULL) 4067 s->check = (*s->checkfn)(s->check, q, t); 4068 zmemcpy(q, p, t); 4069 q += t; 4070 p += t; 4071 n -= t; 4072 z->total_out += t; 4073 s->read = q; /* drag read pointer forward */ 4074 /* WWRAP */ /* expand WWRAP macro by hand to handle s->read */ 4075 if (q == s->end) { 4076 s->read = q = s->window; 4077 m = WAVAIL; 4078 } 4079 } 4080 UPDATE 4081 return Z_OK; 4082 } 4083 4084 4085 /* 4086 * At the end of a Deflate-compressed PPP packet, we expect to have seen 4087 * a `stored' block type value but not the (zero) length bytes. 4088 */ 4089 int 4090 inflate_packet_flush(inflate_blocks_statef *s) 4091 { 4092 if (s->mode != LENS) 4093 return Z_DATA_ERROR; 4094 s->mode = TYPE; 4095 return Z_OK; 4096 } 4097 /* --- infblock.c */ 4098 4099 /* +++ inftrees.c */ 4100 /* inftrees.c -- generate Huffman trees for efficient decoding 4101 * Copyright (C) 1995-1996 Mark Adler 4102 * For conditions of distribution and use, see copyright notice in zlib.h 4103 */ 4104 4105 /* #include "zutil.h" */ 4106 /* #include "inftrees.h" */ 4107 4108 char inflate_copyright[] = " inflate 1.0.4 Copyright 1995-1996 Mark Adler "; 4109 /* 4110 If you use the zlib library in a product, an acknowledgment is welcome 4111 in the documentation of your product. If for some reason you cannot 4112 include such an acknowledgment, I would appreciate that you keep this 4113 copyright string in the executable of your product. 4114 */ 4115 4116 #ifndef NO_DUMMY_DECL 4117 struct internal_state {int dummy;}; /* for buggy compilers */ 4118 #endif 4119 4120 /* simplify the use of the inflate_huft type with some defines */ 4121 #define base more.Base 4122 #define next more.Next 4123 #define exop word.what.Exop 4124 #define bits word.what.Bits 4125 4126 4127 local int huft_build OF(( 4128 uIntf *, /* code lengths in bits */ 4129 uInt, /* number of codes */ 4130 uInt, /* number of "simple" codes */ 4131 const uIntf *, /* list of base values for non-simple codes */ 4132 const uIntf *, /* list of extra bits for non-simple codes */ 4133 inflate_huft * FAR*,/* result: starting table */ 4134 uIntf *, /* maximum lookup bits (returns actual) */ 4135 z_streamp )); /* for zalloc function */ 4136 4137 local voidpf zfalloc OF(( 4138 voidpf, /* opaque pointer (not used) */ 4139 uInt, /* number of items */ 4140 uInt)); /* size of item */ 4141 4142 /* Tables for deflate from PKZIP's appnote.txt. */ 4143 local const uInt cplens[31] = { /* Copy lengths for literal codes 257..285 */ 4144 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 4145 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; 4146 /* see note #13 above about 258 */ 4147 local const uInt cplext[31] = { /* Extra bits for literal codes 257..285 */ 4148 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 4149 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 112, 112}; /* 112==invalid */ 4150 local const uInt cpdist[30] = { /* Copy offsets for distance codes 0..29 */ 4151 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 4152 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 4153 8193, 12289, 16385, 24577}; 4154 local const uInt cpdext[30] = { /* Extra bits for distance codes */ 4155 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 4156 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 4157 12, 12, 13, 13}; 4158 4159 /* 4160 Huffman code decoding is performed using a multi-level table lookup. 4161 The fastest way to decode is to simply build a lookup table whose 4162 size is determined by the longest code. However, the time it takes 4163 to build this table can also be a factor if the data being decoded 4164 is not very long. The most common codes are necessarily the 4165 shortest codes, so those codes dominate the decoding time, and hence 4166 the speed. The idea is you can have a shorter table that decodes the 4167 shorter, more probable codes, and then point to subsidiary tables for 4168 the longer codes. The time it costs to decode the longer codes is 4169 then traded against the time it takes to make longer tables. 4170 4171 This results of this trade are in the variables lbits and dbits 4172 below. lbits is the number of bits the first level table for literal/ 4173 length codes can decode in one step, and dbits is the same thing for 4174 the distance codes. Subsequent tables are also less than or equal to 4175 those sizes. These values may be adjusted either when all of the 4176 codes are shorter than that, in which case the longest code length in 4177 bits is used, or when the shortest code is *longer* than the requested 4178 table size, in which case the length of the shortest code in bits is 4179 used. 4180 4181 There are two different values for the two tables, since they code a 4182 different number of possibilities each. The literal/length table 4183 codes 286 possible values, or in a flat code, a little over eight 4184 bits. The distance table codes 30 possible values, or a little less 4185 than five bits, flat. The optimum values for speed end up being 4186 about one bit more than those, so lbits is 8+1 and dbits is 5+1. 4187 The optimum values may differ though from machine to machine, and 4188 possibly even between compilers. Your mileage may vary. 4189 */ 4190 4191 4192 /* If BMAX needs to be larger than 16, then h and x[] should be uLong. */ 4193 #define BMAX 15 /* maximum bit length of any code */ 4194 #define N_MAX 288 /* maximum number of codes in any set */ 4195 4196 #ifdef DEBUG_ZLIB 4197 uInt inflate_hufts; 4198 #endif 4199 4200 /* 4201 * Parameters: 4202 * b: code lengths in bits (all assumed <= BMAX) 4203 * n: number of codes (assumed <= N_MAX) 4204 * s: number of simple-valued codes (0..s-1) 4205 * d: list of base values for non-simple codes 4206 * e: list of extra bits for non-simple codes 4207 * t: result: starting table 4208 * m: maximum lookup bits, returns actual 4209 * zs: for zalloc function 4210 * 4211 * Given a list of code lengths and a maximum table size, make a set of 4212 * tables to decode that set of codes. Return Z_OK on success, Z_BUF_ERROR 4213 * if the given code set is incomplete (the tables are still built in this 4214 * case), Z_DATA_ERROR if the input is invalid (an over-subscribed set of 4215 * lengths), or Z_MEM_ERROR if not enough memory. 4216 */ 4217 local int 4218 huft_build(uIntf *b, uInt n, uInt s, const uIntf *d, const uIntf *e, 4219 inflate_huft * FAR *t, uIntf *m, z_streamp zs) 4220 { 4221 4222 uInt a; /* counter for codes of length k */ 4223 uInt c[BMAX+1]; /* bit length count table */ 4224 uInt f; /* i repeats in table every f entries */ 4225 int g; /* maximum code length */ 4226 int h; /* table level */ 4227 uInt i; /* counter, current code */ 4228 uInt j; /* counter */ 4229 int k; /* number of bits in current code */ 4230 int l; /* bits per table (returned in m) */ 4231 uIntf *p; /* pointer into c[], b[], or v[] */ 4232 inflate_huft *q; /* points to current table */ 4233 struct inflate_huft_s r; /* table entry for structure assignment */ 4234 inflate_huft *u[BMAX]; /* table stack */ 4235 uInt v[N_MAX]; /* values in order of bit length */ 4236 int w; /* bits before this table == (l * h) */ 4237 uInt x[BMAX+1]; /* bit offsets, then code stack */ 4238 uIntf *xp; /* pointer into x */ 4239 int y; /* number of dummy codes added */ 4240 uInt z; /* number of entries in current table */ 4241 4242 4243 /* Generate counts for each bit length */ 4244 p = c; 4245 #define C0 *p++ = 0; 4246 #define C2 C0 C0 C0 C0 4247 #define C4 C2 C2 C2 C2 4248 C4 /* clear c[]--assume BMAX+1 is 16 */ 4249 p = b; i = n; 4250 do { 4251 c[*p++]++; /* assume all entries <= BMAX */ 4252 } while (--i); 4253 if (c[0] == n) /* null input--all zero length codes */ 4254 { 4255 *t = (inflate_huft *)Z_NULL; 4256 *m = 0; 4257 return Z_OK; 4258 } 4259 4260 4261 /* Find minimum and maximum length, bound *m by those */ 4262 l = *m; 4263 for (j = 1; j <= BMAX; j++) 4264 if (c[j]) 4265 break; 4266 k = j; /* minimum code length */ 4267 if ((uInt)l < j) 4268 l = j; 4269 for (i = BMAX; i; i--) 4270 if (c[i]) 4271 break; 4272 g = i; /* maximum code length */ 4273 if ((uInt)l > i) 4274 l = i; 4275 *m = l; 4276 4277 4278 /* Adjust last length count to fill out codes, if needed */ 4279 for (y = 1 << j; j < i; j++, y <<= 1) 4280 if ((y -= c[j]) < 0) 4281 return Z_DATA_ERROR; 4282 if ((y -= c[i]) < 0) 4283 return Z_DATA_ERROR; 4284 c[i] += y; 4285 4286 4287 /* Generate starting offsets into the value table for each length */ 4288 x[1] = j = 0; 4289 p = c + 1; xp = x + 2; 4290 while (--i) { /* note that i == g from above */ 4291 *xp++ = (j += *p++); 4292 } 4293 4294 4295 /* Make a table of values in order of bit lengths */ 4296 p = b; i = 0; 4297 do { 4298 if ((j = *p++) != 0) 4299 v[x[j]++] = i; 4300 } while (++i < n); 4301 n = x[g]; /* set n to length of v */ 4302 4303 4304 /* Generate the Huffman codes and for each, make the table entries */ 4305 x[0] = i = 0; /* first Huffman code is zero */ 4306 p = v; /* grab values in bit order */ 4307 h = -1; /* no tables yet--level -1 */ 4308 w = -l; /* bits decoded == (l * h) */ 4309 u[0] = (inflate_huft *)Z_NULL; /* just to keep compilers happy */ 4310 q = (inflate_huft *)Z_NULL; /* ditto */ 4311 z = 0; /* ditto */ 4312 4313 /* go through the bit lengths (k already is bits in shortest code) */ 4314 for (; k <= g; k++) 4315 { 4316 a = c[k]; 4317 while (a--) 4318 { 4319 /* here i is the Huffman code of length k bits for value *p */ 4320 /* make tables up to required level */ 4321 while (k > w + l) 4322 { 4323 h++; 4324 w += l; /* previous table always l bits */ 4325 4326 /* compute minimum size table less than or equal to l bits */ 4327 z = g - w; 4328 z = z > (uInt)l ? l : z; /* table size upper limit */ 4329 if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */ 4330 { /* too few codes for k-w bit table */ 4331 f -= a + 1; /* deduct codes from patterns left */ 4332 xp = c + k; 4333 if (j < z) 4334 while (++j < z) /* try smaller tables up to z bits */ 4335 { 4336 if ((f <<= 1) <= *++xp) 4337 break; /* enough codes to use up j bits */ 4338 f -= *xp; /* else deduct codes from patterns */ 4339 } 4340 } 4341 z = 1 << j; /* table entries for j-bit table */ 4342 4343 /* allocate and link in new table */ 4344 if ((q = (inflate_huft *)ZALLOC 4345 (zs,z + 1,sizeof(inflate_huft))) == Z_NULL) 4346 { 4347 if (h) 4348 inflate_trees_free(u[0], zs); 4349 return Z_MEM_ERROR; /* not enough memory */ 4350 } 4351 #ifdef DEBUG_ZLIB 4352 inflate_hufts += z + 1; 4353 #endif 4354 *t = q + 1; /* link to list for huft_free() */ 4355 *(t = &(q->next)) = Z_NULL; 4356 u[h] = ++q; /* table starts after link */ 4357 4358 /* connect to last table, if there is one */ 4359 if (h) 4360 { 4361 x[h] = i; /* save pattern for backing up */ 4362 r.bits = (Byte)l; /* bits to dump before this table */ 4363 r.exop = (Byte)j; /* bits in this table */ 4364 r.next = q; /* pointer to this table */ 4365 j = i >> (w - l); /* (get around Turbo C bug) */ 4366 u[h-1][j] = r; /* connect to last table */ 4367 } 4368 } 4369 4370 /* set up table entry in r */ 4371 r.bits = (Byte)(k - w); 4372 if (p >= v + n) 4373 r.exop = 128 + 64; /* out of values--invalid code */ 4374 else if (*p < s) 4375 { 4376 r.exop = (Byte)(*p < 256 ? 0 : 32 + 64); /* 256 is end-of-block */ 4377 r.base = *p++; /* simple code is just the value */ 4378 } 4379 else 4380 { 4381 r.exop = (Byte)(e[*p - s] + 16 + 64);/* non-simple--look up in lists */ 4382 r.base = d[*p++ - s]; 4383 } 4384 4385 /* fill code-like entries with r */ 4386 f = 1 << (k - w); 4387 for (j = i >> w; j < z; j += f) 4388 q[j] = r; 4389 4390 /* backwards increment the k-bit code i */ 4391 for (j = 1 << (k - 1); i & j; j >>= 1) 4392 i ^= j; 4393 i ^= j; 4394 4395 /* backup over finished tables */ 4396 while ((i & ((1 << w) - 1)) != x[h]) 4397 { 4398 h--; /* don't need to update q */ 4399 w -= l; 4400 } 4401 } 4402 } 4403 4404 4405 /* Return Z_BUF_ERROR if we were given an incomplete table */ 4406 return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK; 4407 } 4408 4409 /* 4410 * Parameters: 4411 * c: 19 code lengths 4412 * bb: bits tree desired/actual depth 4413 * tb: bits tree result 4414 * z: for zfree function 4415 */ 4416 int 4417 inflate_trees_bits(uIntf *c, uIntf *bb, inflate_huft * FAR *tb, z_streamp z) 4418 { 4419 int r; 4420 4421 r = huft_build(c, 19, 19, (uIntf*)Z_NULL, (uIntf*)Z_NULL, tb, bb, z); 4422 if (r == Z_DATA_ERROR) 4423 z->msg = (char*)"oversubscribed dynamic bit lengths tree"; 4424 else if (r == Z_BUF_ERROR || *bb == 0) 4425 { 4426 inflate_trees_free(*tb, z); 4427 z->msg = (char*)"incomplete dynamic bit lengths tree"; 4428 r = Z_DATA_ERROR; 4429 } 4430 return r; 4431 } 4432 4433 /* 4434 * Parameters: 4435 * nl: number of literal/length codes 4436 * nd: number of distance codes 4437 * c: that many (total) code lengths 4438 * bl: literal desired/actual bit depth 4439 * bd: distance desired/actual bit depth 4440 * tl: literal/length tree result 4441 * td: distance tree result 4442 * z: for zfree function 4443 */ 4444 int 4445 inflate_trees_dynamic(uInt nl, uInt nd, uIntf *c, uIntf *bl, uIntf *bd, 4446 inflate_huft * FAR *tl, inflate_huft * FAR *td, 4447 z_streamp z) 4448 { 4449 int r; 4450 4451 /* build literal/length tree */ 4452 r = huft_build(c, nl, 257, cplens, cplext, tl, bl, z); 4453 if (r != Z_OK || *bl == 0) 4454 { 4455 if (r == Z_DATA_ERROR) 4456 z->msg = (char*)"oversubscribed literal/length tree"; 4457 else if (r != Z_MEM_ERROR) 4458 { 4459 inflate_trees_free(*tl, z); 4460 z->msg = (char*)"incomplete literal/length tree"; 4461 r = Z_DATA_ERROR; 4462 } 4463 return r; 4464 } 4465 4466 /* build distance tree */ 4467 r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, z); 4468 if (r != Z_OK || (*bd == 0 && nl > 257)) 4469 { 4470 if (r == Z_DATA_ERROR) 4471 z->msg = (char*)"oversubscribed distance tree"; 4472 else if (r == Z_BUF_ERROR) { 4473 #ifdef PKZIP_BUG_WORKAROUND 4474 r = Z_OK; 4475 } 4476 #else 4477 inflate_trees_free(*td, z); 4478 z->msg = (char*)"incomplete distance tree"; 4479 r = Z_DATA_ERROR; 4480 } 4481 else if (r != Z_MEM_ERROR) 4482 { 4483 z->msg = (char*)"empty distance tree with lengths"; 4484 r = Z_DATA_ERROR; 4485 } 4486 inflate_trees_free(*tl, z); 4487 return r; 4488 #endif 4489 } 4490 4491 /* done */ 4492 return Z_OK; 4493 } 4494 4495 4496 /* build fixed tables only once--keep them here */ 4497 local int fixed_built = 0; 4498 #define FIXEDH 530 /* number of hufts used by fixed tables */ 4499 local inflate_huft fixed_mem[FIXEDH]; 4500 local uInt fixed_bl; 4501 local uInt fixed_bd; 4502 local inflate_huft *fixed_tl; 4503 local inflate_huft *fixed_td; 4504 4505 /* 4506 * Parameters: 4507 * q: opaque pointer 4508 * n: number of items 4509 * s: size of item 4510 */ 4511 local voidpf 4512 zfalloc(voidpf q, uInt n, uInt s) 4513 { 4514 Assert(s == sizeof(inflate_huft) && n <= *(intf *)q, 4515 "inflate_trees zfalloc overflow"); 4516 *(intf *)q -= n+s-s; /* s-s to avoid warning */ 4517 return (voidpf)(fixed_mem + *(intf *)q); 4518 } 4519 4520 /* 4521 * Parameters: 4522 * bl: literal desired/actual bit depth 4523 * bd: distance desired/actual bit depth 4524 * tl: literal/length tree result 4525 * td: distance tree result 4526 */ 4527 int 4528 inflate_trees_fixed(uIntf *bl, uIntf *bd, inflate_huft * FAR *tl, 4529 inflate_huft * FAR *td) 4530 { 4531 /* build fixed tables if not already (multiple overlapped executions ok) */ 4532 if (!fixed_built) 4533 { 4534 int k; /* temporary variable */ 4535 unsigned c[288]; /* length list for huft_build */ 4536 z_stream z; /* for zfalloc function */ 4537 int f = FIXEDH; /* number of hufts left in fixed_mem */ 4538 4539 /* set up fake z_stream for memory routines */ 4540 z.zalloc = zfalloc; 4541 z.zfree = Z_NULL; 4542 z.opaque = (voidpf)&f; 4543 4544 /* literal table */ 4545 for (k = 0; k < 144; k++) 4546 c[k] = 8; 4547 for (; k < 256; k++) 4548 c[k] = 9; 4549 for (; k < 280; k++) 4550 c[k] = 7; 4551 for (; k < 288; k++) 4552 c[k] = 8; 4553 fixed_bl = 7; 4554 huft_build(c, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl, &z); 4555 4556 /* distance table */ 4557 for (k = 0; k < 30; k++) 4558 c[k] = 5; 4559 fixed_bd = 5; 4560 huft_build(c, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd, &z); 4561 4562 /* done */ 4563 Assert(f == 0, "invalid build of fixed tables"); 4564 fixed_built = 1; 4565 } 4566 *bl = fixed_bl; 4567 *bd = fixed_bd; 4568 *tl = fixed_tl; 4569 *td = fixed_td; 4570 return Z_OK; 4571 } 4572 4573 /* 4574 * Parameters: 4575 * t: table to free 4576 * z: for zfree function 4577 * Free the malloc'ed tables built by huft_build(), which makes a linked 4578 * list of the tables it made, with the links in a dummy first entry of 4579 * each table. 4580 */ 4581 int 4582 inflate_trees_free(inflate_huft *t, z_streamp z) 4583 { 4584 inflate_huft *p, *q, *r; 4585 4586 /* Reverse linked list */ 4587 p = Z_NULL; 4588 q = t; 4589 while (q != Z_NULL) 4590 { 4591 r = (q - 1)->next; 4592 (q - 1)->next = p; 4593 p = q; 4594 q = r; 4595 } 4596 /* Go through linked list, freeing from the malloced (t[-1]) address. */ 4597 while (p != Z_NULL) 4598 { 4599 q = (--p)->next; 4600 ZFREE(z,p); 4601 p = q; 4602 } 4603 return Z_OK; 4604 } 4605 /* --- inftrees.c */ 4606 4607 /* +++ infcodes.c */ 4608 /* infcodes.c -- process literals and length/distance pairs 4609 * Copyright (C) 1995-1996 Mark Adler 4610 * For conditions of distribution and use, see copyright notice in zlib.h 4611 */ 4612 4613 /* #include "zutil.h" */ 4614 /* #include "inftrees.h" */ 4615 /* #include "infblock.h" */ 4616 /* #include "infcodes.h" */ 4617 /* #include "infutil.h" */ 4618 4619 /* +++ inffast.h */ 4620 /* inffast.h -- header to use inffast.c 4621 * Copyright (C) 1995-1996 Mark Adler 4622 * For conditions of distribution and use, see copyright notice in zlib.h 4623 */ 4624 4625 /* WARNING: this file should *not* be used by applications. It is 4626 part of the implementation of the compression library and is 4627 subject to change. Applications should only use zlib.h. 4628 */ 4629 4630 extern int inflate_fast OF(( 4631 uInt, 4632 uInt, 4633 inflate_huft *, 4634 inflate_huft *, 4635 inflate_blocks_statef *, 4636 z_streamp )); 4637 /* --- inffast.h */ 4638 4639 /* simplify the use of the inflate_huft type with some defines */ 4640 #define base more.Base 4641 #define next more.Next 4642 #define exop word.what.Exop 4643 #define bits word.what.Bits 4644 4645 /* inflate codes private state */ 4646 struct inflate_codes_state { 4647 4648 /* mode */ 4649 enum { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */ 4650 START, /* x: set up for LEN */ 4651 LEN, /* i: get length/literal/eob next */ 4652 LENEXT, /* i: getting length extra (have base) */ 4653 DIST, /* i: get distance next */ 4654 DISTEXT, /* i: getting distance extra */ 4655 COPY, /* o: copying bytes in window, waiting for space */ 4656 LIT, /* o: got literal, waiting for output space */ 4657 WASH, /* o: got eob, possibly still output waiting */ 4658 END, /* x: got eob and all data flushed */ 4659 BADCODE} /* x: got error */ 4660 mode; /* current inflate_codes mode */ 4661 4662 /* mode dependent information */ 4663 uInt len; 4664 union { 4665 struct { 4666 inflate_huft *tree; /* pointer into tree */ 4667 uInt need; /* bits needed */ 4668 } code; /* if LEN or DIST, where in tree */ 4669 uInt lit; /* if LIT, literal */ 4670 struct { 4671 uInt get; /* bits to get for extra */ 4672 uInt dist; /* distance back to copy from */ 4673 } copy; /* if EXT or COPY, where and how much */ 4674 } sub; /* submode */ 4675 4676 /* mode independent information */ 4677 Byte lbits; /* ltree bits decoded per branch */ 4678 Byte dbits; /* dtree bits decoder per branch */ 4679 inflate_huft *ltree; /* literal/length/eob tree */ 4680 inflate_huft *dtree; /* distance tree */ 4681 4682 }; 4683 4684 /* 4685 * Parameters: 4686 * td: need separate declaration for Borland C++ 4687 */ 4688 inflate_codes_statef * 4689 inflate_codes_new(uInt bl, uInt bd, inflate_huft *tl, inflate_huft *td, 4690 z_streamp z) 4691 { 4692 inflate_codes_statef *c; 4693 4694 if ((c = (inflate_codes_statef *) 4695 ZALLOC(z,1,sizeof(struct inflate_codes_state))) != Z_NULL) 4696 { 4697 c->mode = START; 4698 c->lbits = (Byte)bl; 4699 c->dbits = (Byte)bd; 4700 c->ltree = tl; 4701 c->dtree = td; 4702 Tracev((stderr, "inflate: codes new\n")); 4703 } 4704 return c; 4705 } 4706 4707 4708 int 4709 inflate_codes(inflate_blocks_statef *s, z_streamp z, int r) 4710 { 4711 uInt j; /* temporary storage */ 4712 inflate_huft *t; /* temporary pointer */ 4713 uInt e; /* extra bits or operation */ 4714 uLong b; /* bit buffer */ 4715 uInt k; /* bits in bit buffer */ 4716 Bytef *p; /* input data pointer */ 4717 uInt n; /* bytes available there */ 4718 Bytef *q; /* output window write pointer */ 4719 uInt m; /* bytes to end of window or read pointer */ 4720 Bytef *f; /* pointer to copy strings from */ 4721 inflate_codes_statef *c = s->sub.decode.codes; /* codes state */ 4722 4723 /* copy input/output information to locals (UPDATE macro restores) */ 4724 LOAD 4725 4726 /* process input and output based on current state */ 4727 while (1) switch (c->mode) 4728 { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */ 4729 case START: /* x: set up for LEN */ 4730 #ifndef SLOW 4731 if (m >= 258 && n >= 10) 4732 { 4733 UPDATE 4734 r = inflate_fast(c->lbits, c->dbits, c->ltree, c->dtree, s, z); 4735 LOAD 4736 if (r != Z_OK) 4737 { 4738 c->mode = r == Z_STREAM_END ? WASH : BADCODE; 4739 break; 4740 } 4741 } 4742 #endif /* !SLOW */ 4743 c->sub.code.need = c->lbits; 4744 c->sub.code.tree = c->ltree; 4745 c->mode = LEN; 4746 case LEN: /* i: get length/literal/eob next */ 4747 j = c->sub.code.need; 4748 NEEDBITS(j) 4749 t = c->sub.code.tree + ((uInt)b & inflate_mask[j]); 4750 DUMPBITS(t->bits) 4751 e = (uInt)(t->exop); 4752 if (e == 0) /* literal */ 4753 { 4754 c->sub.lit = t->base; 4755 Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ? 4756 "inflate: literal '%c'\n" : 4757 "inflate: literal 0x%02x\n", t->base)); 4758 c->mode = LIT; 4759 break; 4760 } 4761 if (e & 16) /* length */ 4762 { 4763 c->sub.copy.get = e & 15; 4764 c->len = t->base; 4765 c->mode = LENEXT; 4766 break; 4767 } 4768 if ((e & 64) == 0) /* next table */ 4769 { 4770 c->sub.code.need = e; 4771 c->sub.code.tree = t->next; 4772 break; 4773 } 4774 if (e & 32) /* end of block */ 4775 { 4776 Tracevv((stderr, "inflate: end of block\n")); 4777 c->mode = WASH; 4778 break; 4779 } 4780 c->mode = BADCODE; /* invalid code */ 4781 z->msg = (char*)"invalid literal/length code"; 4782 r = Z_DATA_ERROR; 4783 LEAVE 4784 case LENEXT: /* i: getting length extra (have base) */ 4785 j = c->sub.copy.get; 4786 NEEDBITS(j) 4787 c->len += (uInt)b & inflate_mask[j]; 4788 DUMPBITS(j) 4789 c->sub.code.need = c->dbits; 4790 c->sub.code.tree = c->dtree; 4791 Tracevv((stderr, "inflate: length %u\n", c->len)); 4792 c->mode = DIST; 4793 case DIST: /* i: get distance next */ 4794 j = c->sub.code.need; 4795 NEEDBITS(j) 4796 t = c->sub.code.tree + ((uInt)b & inflate_mask[j]); 4797 DUMPBITS(t->bits) 4798 e = (uInt)(t->exop); 4799 if (e & 16) /* distance */ 4800 { 4801 c->sub.copy.get = e & 15; 4802 c->sub.copy.dist = t->base; 4803 c->mode = DISTEXT; 4804 break; 4805 } 4806 if ((e & 64) == 0) /* next table */ 4807 { 4808 c->sub.code.need = e; 4809 c->sub.code.tree = t->next; 4810 break; 4811 } 4812 c->mode = BADCODE; /* invalid code */ 4813 z->msg = (char*)"invalid distance code"; 4814 r = Z_DATA_ERROR; 4815 LEAVE 4816 case DISTEXT: /* i: getting distance extra */ 4817 j = c->sub.copy.get; 4818 NEEDBITS(j) 4819 c->sub.copy.dist += (uInt)b & inflate_mask[j]; 4820 DUMPBITS(j) 4821 Tracevv((stderr, "inflate: distance %u\n", c->sub.copy.dist)); 4822 c->mode = COPY; 4823 case COPY: /* o: copying bytes in window, waiting for space */ 4824 #ifndef __TURBOC__ /* Turbo C bug for following expression */ 4825 f = (uInt)(q - s->window) < c->sub.copy.dist ? 4826 s->end - (c->sub.copy.dist - (q - s->window)) : 4827 q - c->sub.copy.dist; 4828 #else 4829 f = q - c->sub.copy.dist; 4830 if ((uInt)(q - s->window) < c->sub.copy.dist) 4831 f = s->end - (c->sub.copy.dist - (uInt)(q - s->window)); 4832 #endif 4833 while (c->len) 4834 { 4835 NEEDOUT 4836 OUTBYTE(*f++) 4837 if (f == s->end) 4838 f = s->window; 4839 c->len--; 4840 } 4841 c->mode = START; 4842 break; 4843 case LIT: /* o: got literal, waiting for output space */ 4844 NEEDOUT 4845 OUTBYTE(c->sub.lit) 4846 c->mode = START; 4847 break; 4848 case WASH: /* o: got eob, possibly more output */ 4849 FLUSH 4850 if (s->read != s->write) 4851 LEAVE 4852 c->mode = END; 4853 case END: 4854 r = Z_STREAM_END; 4855 LEAVE 4856 case BADCODE: /* x: got error */ 4857 r = Z_DATA_ERROR; 4858 LEAVE 4859 default: 4860 r = Z_STREAM_ERROR; 4861 LEAVE 4862 } 4863 } 4864 4865 4866 void 4867 inflate_codes_free(inflate_codes_statef *c, z_streamp z) 4868 { 4869 ZFREE(z, c); 4870 Tracev((stderr, "inflate: codes free\n")); 4871 } 4872 /* --- infcodes.c */ 4873 4874 /* +++ infutil.c */ 4875 /* inflate_util.c -- data and routines common to blocks and codes 4876 * Copyright (C) 1995-1996 Mark Adler 4877 * For conditions of distribution and use, see copyright notice in zlib.h 4878 */ 4879 4880 /* #include "zutil.h" */ 4881 /* #include "infblock.h" */ 4882 /* #include "inftrees.h" */ 4883 /* #include "infcodes.h" */ 4884 /* #include "infutil.h" */ 4885 4886 #ifndef NO_DUMMY_DECL 4887 struct inflate_codes_state {int dummy;}; /* for buggy compilers */ 4888 #endif 4889 4890 /* And'ing with mask[n] masks the lower n bits */ 4891 uInt inflate_mask[17] = { 4892 0x0000, 4893 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff, 4894 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff 4895 }; 4896 4897 4898 /* copy as much as possible from the sliding window to the output area */ 4899 int 4900 inflate_flush(inflate_blocks_statef *s, z_streamp z, int r) 4901 { 4902 uInt n; 4903 Bytef *p; 4904 Bytef *q; 4905 4906 /* local copies of source and destination pointers */ 4907 p = z->next_out; 4908 q = s->read; 4909 4910 /* compute number of bytes to copy as far as end of window */ 4911 n = (uInt)((q <= s->write ? s->write : s->end) - q); 4912 if (n > z->avail_out) n = z->avail_out; 4913 if (n && r == Z_BUF_ERROR) r = Z_OK; 4914 4915 /* update counters */ 4916 z->avail_out -= n; 4917 z->total_out += n; 4918 4919 /* update check information */ 4920 if (s->checkfn != Z_NULL) 4921 z->adler = s->check = (*s->checkfn)(s->check, q, n); 4922 4923 /* copy as far as end of window */ 4924 if (p != Z_NULL) { 4925 zmemcpy(p, q, n); 4926 p += n; 4927 } 4928 q += n; 4929 4930 /* see if more to copy at beginning of window */ 4931 if (q == s->end) 4932 { 4933 /* wrap pointers */ 4934 q = s->window; 4935 if (s->write == s->end) 4936 s->write = s->window; 4937 4938 /* compute bytes to copy */ 4939 n = (uInt)(s->write - q); 4940 if (n > z->avail_out) n = z->avail_out; 4941 if (n && r == Z_BUF_ERROR) r = Z_OK; 4942 4943 /* update counters */ 4944 z->avail_out -= n; 4945 z->total_out += n; 4946 4947 /* update check information */ 4948 if (s->checkfn != Z_NULL) 4949 z->adler = s->check = (*s->checkfn)(s->check, q, n); 4950 4951 /* copy */ 4952 if (p != Z_NULL) { 4953 zmemcpy(p, q, n); 4954 p += n; 4955 } 4956 q += n; 4957 } 4958 4959 /* update pointers */ 4960 z->next_out = p; 4961 s->read = q; 4962 4963 /* done */ 4964 return r; 4965 } 4966 /* --- infutil.c */ 4967 4968 /* +++ inffast.c */ 4969 /* inffast.c -- process literals and length/distance pairs fast 4970 * Copyright (C) 1995-1996 Mark Adler 4971 * For conditions of distribution and use, see copyright notice in zlib.h 4972 */ 4973 4974 /* #include "zutil.h" */ 4975 /* #include "inftrees.h" */ 4976 /* #include "infblock.h" */ 4977 /* #include "infcodes.h" */ 4978 /* #include "infutil.h" */ 4979 /* #include "inffast.h" */ 4980 4981 #ifndef NO_DUMMY_DECL 4982 struct inflate_codes_state {int dummy;}; /* for buggy compilers */ 4983 #endif 4984 4985 /* simplify the use of the inflate_huft type with some defines */ 4986 #define base more.Base 4987 #define next more.Next 4988 #define exop word.what.Exop 4989 #define bits word.what.Bits 4990 4991 /* macros for bit input with no checking and for returning unused bytes */ 4992 #define GRABBITS(j) {while(k<(j)){b|=((uLong)NEXTBYTE)<<k;k+=8;}} 4993 #define UNGRAB {n+=(c=k>>3);p-=c;k&=7;} 4994 4995 /* Called with number of bytes left to write in window at least 258 4996 * (the maximum string length) and number of input bytes available 4997 * at least ten. The ten bytes are six bytes for the longest length/ 4998 * distance pair plus four bytes for overloading the bit buffer. 4999 * 5000 * Parameters: 5001 * td: need separate declaration for Borland C++ 5002 */ 5003 int 5004 inflate_fast(uInt bl, uInt bd, inflate_huft *tl, inflate_huft *td, 5005 inflate_blocks_statef *s, z_streamp z) 5006 { 5007 inflate_huft *t; /* temporary pointer */ 5008 uInt e; /* extra bits or operation */ 5009 uLong b; /* bit buffer */ 5010 uInt k; /* bits in bit buffer */ 5011 Bytef *p; /* input data pointer */ 5012 uInt n; /* bytes available there */ 5013 Bytef *q; /* output window write pointer */ 5014 uInt m; /* bytes to end of window or read pointer */ 5015 uInt ml; /* mask for literal/length tree */ 5016 uInt md; /* mask for distance tree */ 5017 uInt c; /* bytes to copy */ 5018 uInt d; /* distance back to copy from */ 5019 Bytef *r; /* copy source pointer */ 5020 5021 /* load input, output, bit values */ 5022 LOAD 5023 5024 /* initialize masks */ 5025 ml = inflate_mask[bl]; 5026 md = inflate_mask[bd]; 5027 5028 /* do until not enough input or output space for fast loop */ 5029 do { /* assume called with m >= 258 && n >= 10 */ 5030 /* get literal/length code */ 5031 GRABBITS(20) /* max bits for literal/length code */ 5032 if ((e = (t = tl + ((uInt)b & ml))->exop) == 0) 5033 { 5034 DUMPBITS(t->bits) 5035 Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ? 5036 "inflate: * literal '%c'\n" : 5037 "inflate: * literal 0x%02x\n", t->base)); 5038 *q++ = (Byte)t->base; 5039 m--; 5040 continue; 5041 } 5042 do { 5043 DUMPBITS(t->bits) 5044 if (e & 16) 5045 { 5046 /* get extra bits for length */ 5047 e &= 15; 5048 c = t->base + ((uInt)b & inflate_mask[e]); 5049 DUMPBITS(e) 5050 Tracevv((stderr, "inflate: * length %u\n", c)); 5051 5052 /* decode distance base of block to copy */ 5053 GRABBITS(15); /* max bits for distance code */ 5054 e = (t = td + ((uInt)b & md))->exop; 5055 do { 5056 DUMPBITS(t->bits) 5057 if (e & 16) 5058 { 5059 /* get extra bits to add to distance base */ 5060 e &= 15; 5061 GRABBITS(e) /* get extra bits (up to 13) */ 5062 d = t->base + ((uInt)b & inflate_mask[e]); 5063 DUMPBITS(e) 5064 Tracevv((stderr, "inflate: * distance %u\n", d)); 5065 5066 /* do the copy */ 5067 m -= c; 5068 if ((uInt)(q - s->window) >= d) /* offset before dest */ 5069 { /* just copy */ 5070 r = q - d; 5071 *q++ = *r++; c--; /* minimum count is three, */ 5072 *q++ = *r++; c--; /* so unroll loop a little */ 5073 } 5074 else /* else offset after destination */ 5075 { 5076 e = d - (uInt)(q - s->window); /* bytes from offset to end */ 5077 r = s->end - e; /* pointer to offset */ 5078 if (c > e) /* if source crosses, */ 5079 { 5080 c -= e; /* copy to end of window */ 5081 do { 5082 *q++ = *r++; 5083 } while (--e); 5084 r = s->window; /* copy rest from start of window */ 5085 } 5086 } 5087 do { /* copy all or what's left */ 5088 *q++ = *r++; 5089 } while (--c); 5090 break; 5091 } 5092 else if ((e & 64) == 0) 5093 e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop; 5094 else 5095 { 5096 z->msg = (char*)"invalid distance code"; 5097 UNGRAB 5098 UPDATE 5099 return Z_DATA_ERROR; 5100 } 5101 } while (1); 5102 break; 5103 } 5104 if ((e & 64) == 0) 5105 { 5106 if ((e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop) == 0) 5107 { 5108 DUMPBITS(t->bits) 5109 Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ? 5110 "inflate: * literal '%c'\n" : 5111 "inflate: * literal 0x%02x\n", t->base)); 5112 *q++ = (Byte)t->base; 5113 m--; 5114 break; 5115 } 5116 } 5117 else if (e & 32) 5118 { 5119 Tracevv((stderr, "inflate: * end of block\n")); 5120 UNGRAB 5121 UPDATE 5122 return Z_STREAM_END; 5123 } 5124 else 5125 { 5126 z->msg = (char*)"invalid literal/length code"; 5127 UNGRAB 5128 UPDATE 5129 return Z_DATA_ERROR; 5130 } 5131 } while (1); 5132 } while (m >= 258 && n >= 10); 5133 5134 /* not enough input or output--restore pointers and return */ 5135 UNGRAB 5136 UPDATE 5137 return Z_OK; 5138 } 5139 /* --- inffast.c */ 5140 5141 /* +++ zutil.c */ 5142 /* zutil.c -- target dependent utility functions for the compression library 5143 * Copyright (C) 1995-1996 Jean-loup Gailly. 5144 * For conditions of distribution and use, see copyright notice in zlib.h 5145 */ 5146 5147 /* From: zutil.c,v 1.17 1996/07/24 13:41:12 me Exp $ */ 5148 5149 #ifdef DEBUG_ZLIB 5150 #include <stdio.h> 5151 #endif 5152 5153 /* #include "zutil.h" */ 5154 5155 #ifndef NO_DUMMY_DECL 5156 struct internal_state {int dummy;}; /* for buggy compilers */ 5157 #endif 5158 5159 #ifndef STDC 5160 extern void exit OF((int)); 5161 #endif 5162 5163 const char 5164 *zlibVersion(void) 5165 { 5166 return ZLIB_VERSION; 5167 } 5168 5169 #ifdef DEBUG_ZLIB 5170 void 5171 z_error(char *m) 5172 { 5173 fprintf(stderr, "%s\n", m); 5174 exit(1); 5175 } 5176 #endif 5177 5178 #ifndef HAVE_MEMCPY 5179 5180 void 5181 zmemcpy(Bytef *dest, Bytef *source, uInt len) 5182 { 5183 if (len == 0) return; 5184 do { 5185 *dest++ = *source++; /* ??? to be unrolled */ 5186 } while (--len != 0); 5187 } 5188 5189 int 5190 zmemcmp(Bytef *s1, Bytef *s2, uInt len) 5191 { 5192 uInt j; 5193 5194 for (j = 0; j < len; j++) { 5195 if (s1[j] != s2[j]) return 2*(s1[j] > s2[j])-1; 5196 } 5197 return 0; 5198 } 5199 5200 void 5201 zmemzero(Bytef *dest, uInt len) 5202 { 5203 if (len == 0) return; 5204 do { 5205 *dest++ = 0; /* ??? to be unrolled */ 5206 } while (--len != 0); 5207 } 5208 #endif 5209 5210 #ifdef __TURBOC__ 5211 #if (defined( __BORLANDC__) || !defined(SMALL_MEDIUM)) && !defined(__32BIT__) 5212 /* Small and medium model in Turbo C are for now limited to near allocation 5213 * with reduced MAX_WBITS and MAX_MEM_LEVEL 5214 */ 5215 # define MY_ZCALLOC 5216 5217 /* Turbo C malloc() does not allow dynamic allocation of 64K bytes 5218 * and farmalloc(64K) returns a pointer with an offset of 8, so we 5219 * must fix the pointer. Warning: the pointer must be put back to its 5220 * original form in order to free it, use zcfree(). 5221 */ 5222 5223 #define MAX_PTR 10 5224 /* 10*64K = 640K */ 5225 5226 local int next_ptr = 0; 5227 5228 typedef struct ptr_table_s { 5229 voidpf org_ptr; 5230 voidpf new_ptr; 5231 } ptr_table; 5232 5233 local ptr_table table[MAX_PTR]; 5234 /* This table is used to remember the original form of pointers 5235 * to large buffers (64K). Such pointers are normalized with a zero offset. 5236 * Since MSDOS is not a preemptive multitasking OS, this table is not 5237 * protected from concurrent access. This hack doesn't work anyway on 5238 * a protected system like OS/2. Use Microsoft C instead. 5239 */ 5240 5241 voidpf 5242 zcalloc(voidpf opaque, unsigned items, unsigned size) 5243 { 5244 voidpf buf = opaque; /* just to make some compilers happy */ 5245 ulg bsize = (ulg)items*size; 5246 5247 /* If we allocate less than 65520 bytes, we assume that farmalloc 5248 * will return a usable pointer which doesn't have to be normalized. 5249 */ 5250 if (bsize < 65520L) { 5251 buf = farmalloc(bsize); 5252 if (*(ush*)&buf != 0) return buf; 5253 } else { 5254 buf = farmalloc(bsize + 16L); 5255 } 5256 if (buf == NULL || next_ptr >= MAX_PTR) return NULL; 5257 table[next_ptr].org_ptr = buf; 5258 5259 /* Normalize the pointer to seg:0 */ 5260 *((ush*)&buf+1) += ((ush)((uch*)buf-0) + 15) >> 4; 5261 *(ush*)&buf = 0; 5262 table[next_ptr++].new_ptr = buf; 5263 return buf; 5264 } 5265 5266 void 5267 zcfree(voidpf opaque, voidpf ptr) 5268 { 5269 int n; 5270 if (*(ush*)&ptr != 0) { /* object < 64K */ 5271 farfree(ptr); 5272 return; 5273 } 5274 /* Find the original pointer */ 5275 for (n = 0; n < next_ptr; n++) { 5276 if (ptr != table[n].new_ptr) continue; 5277 5278 farfree(table[n].org_ptr); 5279 while (++n < next_ptr) { 5280 table[n-1] = table[n]; 5281 } 5282 next_ptr--; 5283 return; 5284 } 5285 ptr = opaque; /* just to make some compilers happy */ 5286 Assert(0, "zcfree: ptr not found"); 5287 } 5288 #endif 5289 #endif /* __TURBOC__ */ 5290 5291 5292 #if defined(M_I86) && !defined(__32BIT__) 5293 /* Microsoft C in 16-bit mode */ 5294 5295 # define MY_ZCALLOC 5296 5297 #if (!defined(_MSC_VER) || (_MSC_VER < 600)) 5298 # define _halloc halloc 5299 # define _hfree hfree 5300 #endif 5301 5302 voidpf 5303 zcalloc(voidpf opaque, unsigned items, unsigned size) 5304 { 5305 if (opaque) opaque = 0; /* to make compiler happy */ 5306 return _halloc((long)items, size); 5307 } 5308 5309 void 5310 zcfree(voidpf opaque, voidpf ptr) 5311 { 5312 if (opaque) opaque = 0; /* to make compiler happy */ 5313 _hfree(ptr); 5314 } 5315 5316 #endif /* MSC */ 5317 5318 5319 #ifndef MY_ZCALLOC /* Any system without a special alloc function */ 5320 5321 #ifndef STDC 5322 extern voidp calloc OF((uInt items, uInt size)); 5323 extern void free OF((voidpf ptr)); 5324 #endif 5325 5326 voidpf 5327 zcalloc(voidpf opaque, unsigned items, unsigned size) 5328 { 5329 if (opaque) items += size - size; /* make compiler happy */ 5330 return (voidpf)calloc(items, size); 5331 } 5332 5333 void 5334 zcfree(voidpf opaque, voidpf ptr) 5335 { 5336 free(ptr); 5337 if (opaque) return; /* make compiler happy */ 5338 } 5339 5340 #endif /* MY_ZCALLOC */ 5341 /* --- zutil.c */ 5342 5343 /* +++ adler32.c */ 5344 /* adler32.c -- compute the Adler-32 checksum of a data stream 5345 * Copyright (C) 1995-1996 Mark Adler 5346 * For conditions of distribution and use, see copyright notice in zlib.h 5347 */ 5348 5349 /* From: adler32.c,v 1.10 1996/05/22 11:52:18 me Exp $ */ 5350 5351 /* #include "zlib.h" */ 5352 5353 #define BASE 65521L /* largest prime smaller than 65536 */ 5354 #define NMAX 5552 5355 /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */ 5356 5357 #define DO1(buf,i) {s1 += buf[i]; s2 += s1;} 5358 #define DO2(buf,i) DO1(buf,i); DO1(buf,i+1); 5359 #define DO4(buf,i) DO2(buf,i); DO2(buf,i+2); 5360 #define DO8(buf,i) DO4(buf,i); DO4(buf,i+4); 5361 #define DO16(buf) DO8(buf,0); DO8(buf,8); 5362 5363 /* ========================================================================= */ 5364 uLong 5365 adler32(uLong adler, const Bytef *buf, uInt len) 5366 { 5367 unsigned long s1 = adler & 0xffff; 5368 unsigned long s2 = (adler >> 16) & 0xffff; 5369 int k; 5370 5371 if (buf == Z_NULL) return 1L; 5372 5373 while (len > 0) { 5374 k = len < NMAX ? len : NMAX; 5375 len -= k; 5376 while (k >= 16) { 5377 DO16(buf); 5378 buf += 16; 5379 k -= 16; 5380 } 5381 if (k != 0) do { 5382 s1 += *buf++; 5383 s2 += s1; 5384 } while (--k); 5385 s1 %= BASE; 5386 s2 %= BASE; 5387 } 5388 return (s2 << 16) | s1; 5389 } 5390 /* --- adler32.c */ 5391