1 /* 2 * Copyright 2007 Sun Microsystems, Inc. All rights reserved. 3 * Use is subject to license terms. 4 */ 5 6 /* 7 * Updated from zlib-1.0.4 to zlib-1.1.3 by James Carlson. 8 * 9 * This file is derived from various .h and .c files from the zlib-1.0.4 10 * distribution by Jean-loup Gailly and Mark Adler, with some additions 11 * by Paul Mackerras to aid in implementing Deflate compression and 12 * decompression for PPP packets. See zlib.h for conditions of 13 * distribution and use. 14 * 15 * Changes that have been made include: 16 * - added Z_PACKET_FLUSH (see zlib.h for details) 17 * - added inflateIncomp and deflateOutputPending 18 * - allow strm->next_out to be NULL, meaning discard the output 19 * 20 * $Id: zlib.c,v 1.11 1998/09/13 23:37:12 paulus Exp $ 21 */ 22 23 #pragma ident "%Z%%M% %I% %E% SMI" 24 25 /* 26 * ==FILEVERSION 971210== 27 * 28 * This marker is used by the Linux installation script to determine 29 * whether an up-to-date version of this file is already installed. 30 */ 31 32 #define NO_DUMMY_DECL 33 #define NO_ZCFUNCS 34 #define MY_ZCALLOC 35 36 #if defined(__FreeBSD__) && (defined(KERNEL) || defined(_KERNEL)) 37 #define inflate inflate_ppp /* FreeBSD already has an inflate :-( */ 38 #endif 39 40 41 /* +++ zutil.h */ 42 /* 43 * 44 * zutil.h -- internal interface and configuration of the compression library 45 * Copyright (C) 1995-1998 Jean-loup Gailly. 46 * For conditions of distribution and use, see copyright notice in zlib.h 47 */ 48 49 /* 50 * WARNING: this file should *not* be used by applications. It is part 51 * of the implementation of the compression library and is subject to 52 * change. Applications should only use zlib.h. 53 */ 54 55 /* From: zutil.h,v 1.16 1996/07/24 13:41:13 me Exp $ */ 56 57 #ifndef _Z_UTIL_H 58 #define _Z_UTIL_H 59 60 #include "zlib.h" 61 62 #if defined(KERNEL) || defined(_KERNEL) 63 /* Assume this is a *BSD or SVR4 kernel */ 64 #include <sys/types.h> 65 #include <sys/time.h> 66 #include <sys/systm.h> 67 #ifdef SOL2 68 #include <sys/cmn_err.h> 69 #endif 70 #define HAVE_MEMCPY 71 #define memcmp bcmp 72 73 #else 74 #if defined(__KERNEL__) 75 /* Assume this is a Linux kernel */ 76 #include <linux/string.h> 77 #define HAVE_MEMCPY 78 79 #else /* not kernel */ 80 81 #include <stddef.h> 82 #ifdef NO_ERRNO_H 83 extern int errno; 84 #else 85 #include <errno.h> 86 #endif 87 #ifdef STDC 88 #include <string.h> 89 #include <stdlib.h> 90 #endif 91 #endif /* __KERNEL__ */ 92 #endif /* _KERNEL || KERNEL */ 93 94 #ifndef local 95 #define local static 96 #endif 97 /* compile with -Dlocal if your debugger can't find static symbols */ 98 99 typedef unsigned char uch; 100 typedef uch FAR uchf; 101 typedef unsigned short ush; 102 typedef ush FAR ushf; 103 typedef unsigned long ulg; 104 105 static const char *z_errmsg[10]; /* indexed by 2-zlib_error */ 106 /* (size given to avoid silly warnings with Visual C++) */ 107 108 #define ERR_MSG(err) z_errmsg[Z_NEED_DICT-(err)] 109 110 #define ERR_RETURN(strm, err) \ 111 return (strm->msg = ERR_MSG(err), (err)) 112 /* To be used only when the state is known to be valid */ 113 114 /* common constants */ 115 116 #ifndef DEF_WBITS 117 #define DEF_WBITS MAX_WBITS 118 #endif 119 /* default windowBits for decompression. MAX_WBITS is for compression only */ 120 121 #if MAX_MEM_LEVEL >= 8 122 #define DEF_MEM_LEVEL 8 123 #else 124 #define DEF_MEM_LEVEL MAX_MEM_LEVEL 125 #endif 126 /* default memLevel */ 127 128 #define STORED_BLOCK 0 129 #define STATIC_TREES 1 130 #define DYN_TREES 2 131 /* The three kinds of block type */ 132 133 #define MIN_MATCH 3 134 #define MAX_MATCH 258 135 /* The minimum and maximum match lengths */ 136 137 #define PRESET_DICT 0x20 /* preset dictionary flag in zlib header */ 138 139 /* target dependencies */ 140 141 #ifdef MSDOS 142 #define OS_CODE 0x00 143 #ifdef __TURBOC__ 144 #include <alloc.h> 145 #else /* MSC or DJGPP */ 146 #include <malloc.h> 147 #endif 148 #endif 149 150 #ifdef OS2 151 #define OS_CODE 0x06 152 #endif 153 154 #ifdef WIN32 /* Window 95 & Windows NT */ 155 #define OS_CODE 0x0b 156 #endif 157 158 #if defined(VAXC) || defined(VMS) 159 #define OS_CODE 0x02 160 #define F_OPEN(name, mode) \ 161 fopen((name), (mode), "mbc=60", "ctx=stm", "rfm=fix", "mrs=512") 162 #endif 163 164 #ifdef AMIGA 165 #define OS_CODE 0x01 166 #endif 167 168 #if defined(ATARI) || defined(atarist) 169 #define OS_CODE 0x05 170 #endif 171 172 #ifdef MACOS 173 #define OS_CODE 0x07 174 #endif 175 176 #ifdef __50SERIES /* Prime/PRIMOS */ 177 #define OS_CODE 0x0F 178 #endif 179 180 #ifdef TOPS20 181 #define OS_CODE 0x0a 182 #endif 183 184 #if defined(_BEOS_) || defined(RISCOS) 185 #define fdopen(fd, mode) NULL /* No fdopen() */ 186 #endif 187 188 /* Common defaults */ 189 190 #ifndef OS_CODE 191 #define OS_CODE 0x03 /* assume Unix */ 192 #endif 193 194 #ifndef F_OPEN 195 #define F_OPEN(name, mode) fopen((name), (mode)) 196 #endif 197 198 /* functions */ 199 200 #ifdef HAVE_STRERROR 201 extern char *strerror OF((int)); 202 #define zstrerror(errnum) strerror(errnum) 203 #else 204 #define zstrerror(errnum) "" 205 #endif 206 207 #if defined(pyr) 208 #define NO_MEMCPY 209 #endif 210 #if (defined(M_I86SM) || defined(M_I86MM)) && !defined(_MSC_VER) 211 /* 212 * Use our own functions for small and medium model with MSC <= 5.0. 213 * You may have to use the same strategy for Borland C (untested). 214 */ 215 #define NO_MEMCPY 216 #endif 217 #if defined(STDC) && !defined(HAVE_MEMCPY) && !defined(NO_MEMCPY) 218 #define HAVE_MEMCPY 219 #endif 220 #ifdef HAVE_MEMCPY 221 #ifdef SMALL_MEDIUM /* MSDOS small or medium model */ 222 #define zmemcpy _fmemcpy 223 #define zmemcmp _fmemcmp 224 #define zmemzero(dest, len) _fmemset(dest, 0, len) 225 #else 226 #define zmemcpy (void) memcpy 227 #define zmemcmp memcmp 228 #define zmemzero(dest, len) (void) memset(dest, 0, len) 229 #endif 230 #else 231 extern void zmemcpy OF((Bytef* dest, const Bytef* source, uInt len)); 232 extern int zmemcmp OF((const Bytef* s1, const Bytef* s2, uInt len)); 233 extern void zmemzero OF((Bytef* dest, uInt len)); 234 #endif 235 236 /* Diagnostic functions */ 237 #ifdef DEBUG_ZLIB 238 #include <stdio.h> 239 #ifndef verbose 240 #define verbose 0 241 #endif 242 extern void z_error OF((char *m)); 243 #define Assert(cond, msg) { if (!(cond)) z_error(msg); } 244 #define Trace(x) {if (z_verbose >= 0) fprintf x; } 245 #define Tracev(x) {if (z_verbose > 0) fprintf x; } 246 #define Tracevv(x) {if (z_verbose > 1) fprintf x; } 247 #define Tracec(c, x) {if (z_verbose > 0 && (c)) fprintf x; } 248 #define Tracecv(c, x) {if (z_verbose > 1 && (c)) fprintf x; } 249 #else 250 #if defined(SOL2) && defined(DEBUG) 251 #define Assert(cond, msg) ((cond) ? ((void)0) : panic(msg)) 252 #else 253 #define Assert(cond, msg) ((void)0) 254 #endif 255 #define Trace(x) ((void)0) 256 #define Tracev(x) ((void)0) 257 #define Tracevv(x) ((void)0) 258 #define Tracec(c, x) ((void)0) 259 #define Tracecv(c, x) ((void)0) 260 #endif 261 262 263 typedef uLong (*check_func) OF((uLong check, const Bytef *buf, uInt len)); 264 265 /* voidpf zcalloc OF((voidpf opaque, unsigned items, unsigned size)); */ 266 /* void zcfree OF((voidpf opaque, voidpf ptr)); */ 267 268 #define ZALLOC(strm, items, size) \ 269 (*((strm)->zalloc))((strm)->opaque, (items), (size)) 270 #define ZFREE(strm, addr) (*((strm)->zfree))((strm)->opaque, (voidpf)(addr)) 271 #define TRY_FREE(s, p) {if (p) ZFREE(s, p); } 272 273 #endif /* _Z_UTIL_H */ 274 /* --- zutil.h */ 275 276 /* +++ deflate.h */ 277 /* 278 * deflate.h -- internal compression state 279 * Copyright (C) 1995-1998 Jean-loup Gailly 280 * For conditions of distribution and use, see copyright notice in zlib.h 281 */ 282 283 /* 284 * WARNING: this file should *not* be used by applications. It is part 285 * of the implementation of the compression library and is subject to 286 * change. Applications should only use zlib.h. 287 */ 288 289 /* From: deflate.h,v 1.10 1996/07/02 12:41:00 me Exp $ */ 290 291 #ifndef _DEFLATE_H 292 #define _DEFLATE_H 293 294 /* #include "zutil.h" */ 295 296 /* 297 * =========================================================================== 298 * Internal compression state. 299 */ 300 301 #define LENGTH_CODES 29 302 /* number of length codes, not counting the special END_BLOCK code */ 303 304 #define LITERALS 256 305 /* number of literal bytes 0..255 */ 306 307 #define L_CODES (LITERALS+1+LENGTH_CODES) 308 /* number of Literal or Length codes, including the END_BLOCK code */ 309 310 #define D_CODES 30 311 /* number of distance codes */ 312 313 #define BL_CODES 19 314 /* number of codes used to transfer the bit lengths */ 315 316 #define HEAP_SIZE (2*L_CODES+1) 317 /* maximum heap size */ 318 319 #define MAX_BITS 15 320 /* All codes must not exceed MAX_BITS bits */ 321 322 #define INIT_STATE 42 323 #define BUSY_STATE 113 324 #define FINISH_STATE 666 325 /* Stream status */ 326 327 328 /* Data structure describing a single value and its code string. */ 329 typedef struct ct_data_s { 330 union { 331 ush freq; /* frequency count */ 332 ush code; /* bit string */ 333 } fc; 334 union { 335 ush dad; /* father node in Huffman tree */ 336 ush len; /* length of bit string */ 337 } dl; 338 } FAR ct_data; 339 340 #define Freq fc.freq 341 #define Code fc.code 342 #define Dad dl.dad 343 #define Len dl.len 344 345 typedef struct static_tree_desc_s static_tree_desc; 346 347 typedef struct tree_desc_s { 348 ct_data *dyn_tree; /* the dynamic tree */ 349 int max_code; /* largest code with non zero frequency */ 350 static_tree_desc *stat_desc; /* the corresponding static tree */ 351 } FAR tree_desc; 352 353 typedef ush Pos; 354 typedef Pos FAR Posf; 355 typedef unsigned IPos; 356 357 /* 358 * A Pos is an index in the character window. We use short instead of 359 * int to save space in the various tables. IPos is used only for 360 * parameter passing. 361 */ 362 363 typedef struct deflate_state { 364 z_streamp strm; /* pointer back to this zlib stream */ 365 int status; /* as the name implies */ 366 Bytef *pending_buf; /* output still pending */ 367 ulg pending_buf_size; /* size of pending_buf */ 368 Bytef *pending_out; /* next pending byte to output to the stream */ 369 int pending; /* nb of bytes in the pending buffer */ 370 int noheader; /* suppress zlib header and adler32 */ 371 Byte data_type; /* UNKNOWN, BINARY or ASCII */ 372 Byte method; /* STORED (for zip only) or DEFLATED */ 373 /* value of flush param for previous deflate call */ 374 int last_flush; 375 376 /* used by deflate.c: */ 377 378 uInt w_size; /* LZ77 window size (32K by default) */ 379 uInt w_bits; /* log2(w_size) (8..16) */ 380 uInt w_mask; /* w_size - 1 */ 381 382 Bytef *window; 383 /* 384 * Sliding window. Input bytes are read into the second half 385 * of the window, and move to the first half later to keep a 386 * dictionary of at least wSize bytes. With this organization, 387 * matches are limited to a distance of wSize-MAX_MATCH bytes, 388 * but this ensures that IO is always performed with a length 389 * multiple of the block size. Also, it limits the window size 390 * to 64K, which is quite useful on MSDOS. To do: use the 391 * user input buffer as sliding window. 392 */ 393 394 ulg window_size; 395 /* 396 * Actual size of window: 2*wSize, except when the user input 397 * buffer is directly used as sliding window. 398 */ 399 400 Posf *prev; 401 /* 402 * Link to older string with same hash index. To limit the 403 * size of this array to 64K, this link is maintained only for 404 * the last 32K strings. An index in this array is thus a 405 * window index modulo 32K. 406 */ 407 408 Posf *head; /* Heads of the hash chains or NIL. */ 409 410 uInt ins_h; /* hash index of string to be inserted */ 411 uInt hash_size; /* number of elements in hash table */ 412 uInt hash_bits; /* log2(hash_size) */ 413 uInt hash_mask; /* hash_size-1 */ 414 415 uInt hash_shift; 416 /* 417 * Number of bits by which ins_h must be shifted at each input 418 * step. It must be such that after MIN_MATCH steps, the 419 * oldest byte no longer takes part in the hash key, that is: 420 * hash_shift * MIN_MATCH >= hash_bits 421 */ 422 423 long block_start; 424 /* 425 * Window position at the beginning of the current output 426 * block. Gets negative when the window is moved backwards. 427 */ 428 429 uInt match_length; /* length of best match */ 430 IPos prev_match; /* previous match */ 431 int match_available; /* set if previous match exists */ 432 uInt strstart; /* start of string to insert */ 433 uInt match_start; /* start of matching string */ 434 uInt lookahead; /* number of valid bytes ahead in window */ 435 436 uInt prev_length; 437 /* 438 * Length of the best match at previous step. Matches not 439 * greater than this are discarded. This is used in the lazy 440 * match evaluation. 441 */ 442 443 uInt max_chain_length; 444 /* 445 * To speed up deflation, hash chains are never searched 446 * beyond *this length. A higher limit improves compression 447 * ratio but *degrades the speed. 448 */ 449 450 uInt max_lazy_match; 451 /* 452 * Attempt to find a better match only when the current match 453 * is strictly smaller than this value. This mechanism is used 454 * only for compression levels >= 4. 455 */ 456 #define max_insert_length max_lazy_match 457 /* 458 * Insert new strings in the hash table only if the match 459 * length is not greater than this length. This saves time but 460 * degrades compression. max_insert_length is used only for 461 * compression levels <= 3. 462 */ 463 464 int level; /* compression level (1..9) */ 465 int strategy; /* favor or force Huffman coding */ 466 467 uInt good_match; 468 /* Use a faster search when the previous match is longer than this */ 469 470 int nice_match; /* Stop searching when current match exceeds this */ 471 472 /* used by trees.c: */ 473 /* Didn't use ct_data typedef below to supress compiler warning */ 474 struct ct_data_s dyn_ltree[HEAP_SIZE]; /* literal and length tree */ 475 struct ct_data_s dyn_dtree[2*D_CODES+1]; /* distance tree */ 476 /* Huffman tree for bit lengths */ 477 struct ct_data_s bl_tree[2*BL_CODES+1]; 478 479 struct tree_desc_s l_desc; /* desc. for literal tree */ 480 struct tree_desc_s d_desc; /* desc. for distance tree */ 481 struct tree_desc_s bl_desc; /* desc. for bit length tree */ 482 483 ush bl_count[MAX_BITS+1]; 484 /* number of codes at each bit length for an optimal tree */ 485 486 int heap[2*L_CODES+1]; /* heap used to build the Huffman trees */ 487 int heap_len; /* number of elements in the heap */ 488 int heap_max; /* element of largest frequency */ 489 /* 490 * The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] 491 * is not used. The same heap array is used to build all 492 * trees. 493 */ 494 495 uch depth[2*L_CODES+1]; 496 /* 497 * Depth of each subtree used as tie breaker for trees of 498 * equal frequency 499 */ 500 501 uchf *l_buf; /* buffer for literals or lengths */ 502 503 uInt lit_bufsize; 504 /* 505 * Size of match buffer for literals/lengths. There are 4 506 * reasons for limiting lit_bufsize to 64K: 507 * 508 * - frequencies can be kept in 16 bit counters 509 * 510 * - if compression is not successful for the first block, 511 * all input data is still in the window so we can still 512 * emit a stored block even when input comes from standard 513 * input. (This can also be done for all blocks if 514 * lit_bufsize is not greater than 32K.) 515 * 516 * - if compression is not successful for a file smaller 517 * than 64K, we can even emit a stored file instead of a 518 * stored block (saving 5 bytes). This is applicable only 519 * for zip (not gzip or zlib). 520 * 521 * - creating new Huffman trees less frequently may not 522 * provide fast adaptation to changes in the input data 523 * statistics. (Take for example a binary file with poorly 524 * compressible code followed by a highly compressible 525 * string table.) Smaller buffer sizes give fast adaptation 526 * but have of course the overhead of transmitting trees 527 * more frequently. 528 * 529 * - I can't count above 4 530 */ 531 532 uInt last_lit; /* running index in l_buf */ 533 534 ushf *d_buf; 535 /* 536 * Buffer for distances. To simplify the code, d_buf and l_buf 537 * have the same number of elements. To use different lengths, 538 * an extra flag array would be necessary. 539 */ 540 541 ulg opt_len; /* bit length of current block with optimal trees */ 542 ulg static_len; /* bit length of current block with static trees */ 543 uInt matches; /* number of string matches in current block */ 544 int last_eob_len; /* bit length of EOB code for last block */ 545 546 ulg compressed_len; /* total bit length of compressed file PPP */ 547 #ifdef DEBUG_ZLIB 548 ulg bits_sent; /* bit length of the compressed data */ 549 #endif 550 551 ush bi_buf; 552 /* 553 * Output buffer. bits are inserted starting at the bottom 554 * (least significant bits). 555 */ 556 int bi_valid; 557 /* 558 * Number of valid bits in bi_buf. All bits above the last 559 * valid bit are always zero. 560 */ 561 562 } FAR deflate_state; 563 564 /* 565 * Output a byte on the stream. IN assertion: there is enough room in 566 * pending_buf. 567 */ 568 #define put_byte(s, c) {s->pending_buf[s->pending++] = (c); } 569 570 571 #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1) 572 /* 573 * Minimum amount of lookahead, except at the end of the input file. 574 * See deflate.c for comments about the MIN_MATCH+1. 575 */ 576 577 #define MAX_DIST(s) ((s)->w_size-MIN_LOOKAHEAD) 578 /* 579 * In order to simplify the code, particularly on 16 bit machines, 580 * match distances are limited to MAX_DIST instead of WSIZE. 581 */ 582 583 /* in trees.c */ 584 void _tr_init OF((deflate_state *s)); 585 int _tr_tally OF((deflate_state *s, unsigned dist, unsigned lc)); 586 void _tr_flush_block OF((deflate_state *s, charf *buf, ulg stored_len, 587 int eof)); 588 void _tr_align OF((deflate_state *s)); 589 void _tr_stored_block OF((deflate_state *s, charf *buf, ulg stored_len, 590 int eof)); 591 void _tr_stored_type_only OF((deflate_state *)); /* PPP */ 592 593 #define d_code(dist) \ 594 ((dist) < 256 ? _dist_code[dist] : _dist_code[256+((dist)>>7)]) 595 /* 596 * Mapping from a distance to a distance code. dist is the distance - 1 and 597 * must not have side effects. _dist_code[256] and _dist_code[257] are never 598 * used. 599 */ 600 601 #ifndef DEBUG_ZLIB 602 /* Inline versions of _tr_tally for speed: */ 603 604 local uch _length_code[]; 605 local uch _dist_code[]; 606 607 #define _tr_tally_lit(s, c, flush) \ 608 { uch cc = (c); \ 609 s->d_buf[s->last_lit] = 0; \ 610 s->l_buf[s->last_lit++] = cc; \ 611 s->dyn_ltree[cc].Freq++; \ 612 flush = (s->last_lit == s->lit_bufsize-1); \ 613 } 614 #define _tr_tally_dist(s, distance, length, flush) \ 615 { uch len = (length); \ 616 ush dist = (distance); \ 617 s->d_buf[s->last_lit] = dist; \ 618 s->l_buf[s->last_lit++] = len; \ 619 dist--; \ 620 s->dyn_ltree[_length_code[len]+LITERALS+1].Freq++; \ 621 s->dyn_dtree[d_code(dist)].Freq++; \ 622 flush = (s->last_lit == s->lit_bufsize-1); \ 623 } 624 #else 625 #define _tr_tally_lit(s, c, flush) flush = _tr_tally(s, 0, c) 626 #define _tr_tally_dist(s, distance, length, flush) \ 627 flush = _tr_tally(s, distance, length) 628 #endif 629 630 #endif 631 /* --- deflate.h */ 632 633 /* +++ deflate.c */ 634 /* 635 * deflate.c -- compress data using the deflation algorithm 636 * Copyright (C) 1995-1998 Jean-loup Gailly. 637 * For conditions of distribution and use, see copyright notice in zlib.h 638 */ 639 640 /* 641 * ALGORITHM 642 * 643 * The "deflation" process depends on being able to identify portions 644 * of the input text which are identical to earlier input (within a 645 * sliding window trailing behind the input currently being processed). 646 * 647 * The most straightforward technique turns out to be the fastest for 648 * most input files: try all possible matches and select the longest. 649 * The key feature of this algorithm is that insertions into the string 650 * dictionary are very simple and thus fast, and deletions are avoided 651 * completely. Insertions are performed at each input character, whereas 652 * string matches are performed only when the previous match ends. So it 653 * is preferable to spend more time in matches to allow very fast string 654 * insertions and avoid deletions. The matching algorithm for small 655 * strings is inspired from that of Rabin & Karp. A brute force approach 656 * is used to find longer strings when a small match has been found. 657 * A similar algorithm is used in comic (by Jan-Mark Wams) and freeze 658 * (by Leonid Broukhis). 659 * A previous version of this file used a more sophisticated algorithm 660 * (by Fiala and Greene) which is guaranteed to run in linear amortized 661 * time, but has a larger average cost, uses more memory and is patented. 662 * However the F&G algorithm may be faster for some highly redundant 663 * files if the parameter max_chain_length (described below) is too large. 664 * 665 * ACKNOWLEDGEMENTS 666 * 667 * The idea of lazy evaluation of matches is due to Jan-Mark Wams, and 668 * I found it in 'freeze' written by Leonid Broukhis. 669 * Thanks to many people for bug reports and testing. 670 * 671 * REFERENCES 672 * 673 * Deutsch, L.P.,"DEFLATE Compressed Data Format Specification". 674 * Available in ftp://ds.internic.net/rfc/rfc1951.txt 675 * 676 * A description of the Rabin and Karp algorithm is given in the book 677 * "Algorithms" by R. Sedgewick, Addison-Wesley, p252. 678 * 679 * Fiala,E.R., and Greene,D.H. 680 * Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595 681 * 682 */ 683 684 /* From: deflate.c,v 1.15 1996/07/24 13:40:58 me Exp $ */ 685 686 /* #include "deflate.h" */ 687 688 const char deflate_copyright[] = 689 " deflate 1.1.3 Copyright 1995-1998 Jean-loup Gailly "; 690 /* 691 * If you use the zlib library in a product, an acknowledgment is 692 * welcome in the documentation of your product. If for some reason 693 * you cannot include such an acknowledgment, I would appreciate that 694 * you keep this copyright string in the executable of your product. 695 */ 696 697 /* 698 * =========================================================================== 699 * Function prototypes. 700 */ 701 typedef enum { 702 /* block not completed, need more input or more output */ 703 need_more, 704 block_done, /* block flush performed */ 705 /* finish started, need only more output at next deflate */ 706 finish_started, 707 finish_done /* finish done, accept no more input or output */ 708 } block_state; 709 710 typedef block_state (*compress_func) OF((deflate_state *s, int flush)); 711 /* Compression function. Returns the block state after the call. */ 712 713 local void fill_window OF((deflate_state *s)); 714 local block_state deflate_stored OF((deflate_state *s, int flush)); 715 local block_state deflate_fast OF((deflate_state *s, int flush)); 716 local block_state deflate_slow OF((deflate_state *s, int flush)); 717 local void lm_init OF((deflate_state *s)); 718 local void putShortMSB OF((deflate_state *s, uInt b)); 719 local void flush_pending OF((z_streamp strm)); 720 local int read_buf OF((z_streamp strm, Bytef *buf, unsigned size)); 721 #ifdef ASMV 722 void match_init OF((void)); /* asm code initialization */ 723 uInt longest_match OF((deflate_state *s, IPos cur_match)); 724 #else 725 local uInt longest_match OF((deflate_state *s, IPos cur_match)); 726 #endif 727 728 #ifdef DEBUG_ZLIB 729 local void check_match OF((deflate_state *s, IPos start, IPos match, 730 int length)); 731 #endif 732 733 /* 734 * =========================================================================== 735 * Local data 736 */ 737 738 #define NIL 0 739 /* Tail of hash chains */ 740 741 #ifndef TOO_FAR 742 #define TOO_FAR 4096 743 #endif 744 /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */ 745 746 #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1) 747 /* 748 * Minimum amount of lookahead, except at the end of the input file. 749 * See deflate.c for comments about the MIN_MATCH+1. 750 */ 751 752 /* 753 * Values for max_lazy_match, good_match and max_chain_length, 754 * depending on the desired pack level (0..9). The values given below 755 * have been tuned to exclude worst case performance for pathological 756 * files. Better values may be found for specific files. 757 */ 758 typedef struct config_s { 759 ush good_length; /* reduce lazy search above this match length */ 760 ush max_lazy; /* do not perform lazy search above this match length */ 761 ush nice_length; /* quit search above this match length */ 762 ush max_chain; 763 compress_func func; 764 } config; 765 766 local const config configuration_table[10] = { 767 /* good lazy nice chain */ 768 /* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */ 769 /* 1 */ {4, 4, 8, 4, deflate_fast}, /* maximum speed, no lazy matches */ 770 /* 2 */ {4, 5, 16, 8, deflate_fast}, 771 /* 3 */ {4, 6, 32, 32, deflate_fast}, 772 773 /* 4 */ {4, 4, 16, 16, deflate_slow}, /* lazy matches */ 774 /* 5 */ {8, 16, 32, 32, deflate_slow}, 775 /* 6 */ {8, 16, 128, 128, deflate_slow}, 776 /* 7 */ {8, 32, 128, 256, deflate_slow}, 777 /* 8 */ {32, 128, 258, 1024, deflate_slow}, 778 /* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* maximum compression */ 779 780 /* 781 * Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4 782 * For deflate_fast() (levels <= 3) good is ignored and lazy has a different 783 * meaning. 784 */ 785 786 #define EQUAL 0 787 /* result of memcmp for equal strings */ 788 789 #ifndef NO_DUMMY_DECL 790 struct static_tree_desc_s {int dummy; }; /* for buggy compilers */ 791 #endif 792 793 /* 794 * =========================================================================== 795 * Update a hash value with the given input byte 796 * IN assertion: all calls to to UPDATE_HASH are made with consecutive 797 * input characters, so that a running hash key can be computed from the 798 * previous key instead of complete recalculation each time. 799 */ 800 #define UPDATE_HASH(s, h, c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask) 801 802 803 /* 804 * =========================================================================== 805 * Insert string str in the dictionary and set match_head to the previous head 806 * of the hash chain (the most recent string with same hash key). Return 807 * the previous length of the hash chain. 808 * If this file is compiled with -DFASTEST, the compression level is forced 809 * to 1, and no hash chains are maintained. 810 * IN assertion: all calls to to INSERT_STRING are made with consecutive 811 * input characters and the first MIN_MATCH bytes of str are valid 812 * (except for the last MIN_MATCH-1 bytes of the input file). 813 */ 814 #ifdef FASTEST 815 #define INSERT_STRING(s, str, match_head) \ 816 (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \ 817 match_head = s->head[s->ins_h], \ 818 s->head[s->ins_h] = (Pos)(str)) 819 #else 820 #define INSERT_STRING(s, str, match_head) \ 821 (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \ 822 s->prev[(str) & s->w_mask] = match_head = s->head[s->ins_h], \ 823 s->head[s->ins_h] = (Pos)(str)) 824 #endif 825 826 /* 827 * =========================================================================== 828 * Initialize the hash table (avoiding 64K overflow for 16 bit systems). 829 * prev[] will be initialized on the fly. 830 */ 831 #define CLEAR_HASH(s) \ 832 s->head[s->hash_size-1] = NIL; \ 833 zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof (*s->head)); 834 835 /* ========================================================================= */ 836 int 837 deflateInit_(strm, level, version, stream_size) 838 z_streamp strm; 839 int level; 840 const char *version; 841 int stream_size; 842 { 843 (void) deflate_copyright; 844 return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL, 845 Z_DEFAULT_STRATEGY, version, stream_size); 846 /* To do: ignore strm->next_in if we use it as window */ 847 } 848 849 /* ========================================================================= */ 850 int deflateInit2_(strm, level, method, windowBits, memLevel, strategy, 851 version, stream_size) 852 z_streamp strm; 853 int level; 854 int method; 855 int windowBits; 856 int memLevel; 857 int strategy; 858 const char *version; 859 int stream_size; 860 { 861 deflate_state *s; 862 int noheader = 0; 863 static const char *my_version = ZLIB_VERSION; 864 865 ushf *overlay; 866 /* 867 * We overlay pending_buf and d_buf+l_buf. This works since 868 * the average output size for (length, distance) codes is <= 869 * 24 bits. 870 */ 871 872 if (version == Z_NULL || version[0] != my_version[0] || 873 stream_size != sizeof (z_stream)) { 874 return (Z_VERSION_ERROR); 875 } 876 if (strm == Z_NULL) 877 return (Z_STREAM_ERROR); 878 879 strm->msg = Z_NULL; 880 #ifndef NO_ZCFUNCS 881 if (strm->zalloc == Z_NULL) { 882 strm->zalloc = zcalloc; 883 strm->opaque = (voidpf)0; 884 } 885 if (strm->zfree == Z_NULL) strm->zfree = zcfree; 886 #endif 887 888 if (level == Z_DEFAULT_COMPRESSION) level = 6; 889 #ifdef FASTEST 890 level = 1; 891 #endif 892 893 if (windowBits < 0) { /* undocumented feature: suppress zlib header */ 894 noheader = 1; 895 windowBits = -windowBits; 896 } 897 if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED || 898 windowBits <= 8 || windowBits > 15 || level < 0 || level > 9 || 899 strategy < 0 || strategy > Z_HUFFMAN_ONLY) { 900 return (Z_STREAM_ERROR); 901 } 902 s = (deflate_state *) ZALLOC(strm, 1, sizeof (deflate_state)); 903 if (s == Z_NULL) 904 return (Z_MEM_ERROR); 905 strm->state = (struct internal_state FAR *)s; 906 s->strm = strm; 907 908 s->noheader = noheader; 909 s->w_bits = windowBits; 910 s->w_size = 1 << s->w_bits; 911 s->w_mask = s->w_size - 1; 912 913 s->hash_bits = memLevel + 7; 914 s->hash_size = 1 << s->hash_bits; 915 s->hash_mask = s->hash_size - 1; 916 s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH); 917 918 s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof (Byte)); 919 s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof (Pos)); 920 s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof (Pos)); 921 922 s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */ 923 924 overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof (ush)+2); 925 s->pending_buf = (uchf *) overlay; 926 s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof (ush)+2L); 927 928 if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL || 929 s->pending_buf == Z_NULL) { 930 strm->msg = ERR_MSG(Z_MEM_ERROR); 931 s->status = INIT_STATE; 932 (void) deflateEnd(strm); 933 return (Z_MEM_ERROR); 934 } 935 s->d_buf = overlay + s->lit_bufsize/sizeof (ush); 936 s->l_buf = s->pending_buf + (1+sizeof (ush))*s->lit_bufsize; 937 938 s->level = level; 939 s->strategy = strategy; 940 s->method = (Byte)method; 941 942 return (deflateReset(strm)); 943 } 944 945 /* ========================================================================= */ 946 int 947 deflateSetDictionary(strm, dictionary, dictLength) 948 z_streamp strm; 949 const Bytef *dictionary; 950 uInt dictLength; 951 { 952 deflate_state *s; 953 uInt length = dictLength; 954 uInt n; 955 IPos hash_head = 0; 956 957 if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL) 958 return (Z_STREAM_ERROR); 959 960 s = (deflate_state *) strm->state; 961 if (s->status != INIT_STATE) 962 return (Z_STREAM_ERROR); 963 964 strm->adler = adler32(strm->adler, dictionary, dictLength); 965 966 if (length < MIN_MATCH) 967 return (Z_OK); 968 if (length > MAX_DIST(s)) { 969 length = MAX_DIST(s); 970 #ifndef USE_DICT_HEAD 971 /* use the tail of the dictionary */ 972 dictionary += dictLength - length; 973 #endif 974 } 975 Assert(length <= s->window_size, "dict copy"); 976 zmemcpy(s->window, dictionary, length); 977 s->strstart = length; 978 s->block_start = (long)length; 979 980 /* 981 * Insert all strings in the hash table (except for the last 982 * two bytes). s->lookahead stays null, so s->ins_h will be 983 * recomputed at the next call of fill_window. 984 */ 985 s->ins_h = s->window[0]; 986 UPDATE_HASH(s, s->ins_h, s->window[1]); 987 for (n = 0; n <= length - MIN_MATCH; n++) { 988 INSERT_STRING(s, n, hash_head); 989 } 990 if (hash_head) hash_head = 0; /* to make compiler happy */ 991 return (Z_OK); 992 } 993 994 /* ========================================================================= */ 995 int 996 deflateReset(strm) 997 z_streamp strm; 998 { 999 deflate_state *s; 1000 1001 if (strm == Z_NULL || strm->state == Z_NULL || 1002 strm->zalloc == Z_NULL || strm->zfree == Z_NULL) 1003 return (Z_STREAM_ERROR); 1004 1005 strm->total_in = strm->total_out = 0; 1006 /* use zfree if we ever allocate msg dynamically */ 1007 strm->msg = Z_NULL; 1008 strm->data_type = Z_UNKNOWN; 1009 1010 s = (deflate_state *)strm->state; 1011 s->pending = 0; 1012 s->pending_out = s->pending_buf; 1013 1014 if (s->noheader < 0) { 1015 /* was set to -1 by deflate(..., Z_FINISH); */ 1016 s->noheader = 0; 1017 } 1018 s->status = s->noheader ? BUSY_STATE : INIT_STATE; 1019 strm->adler = 1; 1020 s->last_flush = Z_NO_FLUSH; 1021 1022 _tr_init(s); 1023 lm_init(s); 1024 1025 return (Z_OK); 1026 } 1027 1028 /* ========================================================================= */ 1029 int 1030 deflateParams(strm, level, strategy) 1031 z_streamp strm; 1032 int level; 1033 int strategy; 1034 { 1035 deflate_state *s; 1036 compress_func func; 1037 int err = Z_OK; 1038 1039 if (strm == Z_NULL || strm->state == Z_NULL) 1040 return (Z_STREAM_ERROR); 1041 s = (deflate_state *) strm->state; 1042 1043 if (level == Z_DEFAULT_COMPRESSION) { 1044 level = 6; 1045 } 1046 if (level < 0 || level > 9 || strategy < 0 || 1047 strategy > Z_HUFFMAN_ONLY) { 1048 return (Z_STREAM_ERROR); 1049 } 1050 func = configuration_table[s->level].func; 1051 1052 if (func != configuration_table[level].func && strm->total_in != 0) { 1053 /* Flush the last buffer: */ 1054 err = deflate(strm, Z_PARTIAL_FLUSH); 1055 } 1056 if (s->level != level) { 1057 s->level = level; 1058 s->max_lazy_match = configuration_table[level].max_lazy; 1059 s->good_match = configuration_table[level].good_length; 1060 s->nice_match = configuration_table[level].nice_length; 1061 s->