1/* deflate.c -- compress data using the deflation algorithm 2 * Copyright (C) 1995-2005 Jean-loup Gailly. 3 * For conditions of distribution and use, see copyright notice in zlib.h 4 */ 5 6/* 7 * ALGORITHM 8 * 9 * The "deflation" process depends on being able to identify portions 10 * of the input text which are identical to earlier input (within a 11 * sliding window trailing behind the input currently being processed). 12 * 13 * The most straightforward technique turns out to be the fastest for 14 * most input files: try all possible matches and select the longest. 15 * The key feature of this algorithm is that insertions into the string 16 * dictionary are very simple and thus fast, and deletions are avoided 17 * completely. Insertions are performed at each input character, whereas 18 * string matches are performed only when the previous match ends. So it 19 * is preferable to spend more time in matches to allow very fast string 20 * insertions and avoid deletions. The matching algorithm for small 21 * strings is inspired from that of Rabin & Karp. A brute force approach 22 * is used to find longer strings when a small match has been found. 23 * A similar algorithm is used in comic (by Jan-Mark Wams) and freeze 24 * (by Leonid Broukhis). 25 * A previous version of this file used a more sophisticated algorithm 26 * (by Fiala and Greene) which is guaranteed to run in linear amortized 27 * time, but has a larger average cost, uses more memory and is patented. 28 * However the F&G algorithm may be faster for some highly redundant 29 * files if the parameter max_chain_length (described below) is too large. 30 * 31 * ACKNOWLEDGEMENTS 32 * 33 * The idea of lazy evaluation of matches is due to Jan-Mark Wams, and 34 * I found it in 'freeze' written by Leonid Broukhis. 35 * Thanks to many people for bug reports and testing. 36 * 37 * REFERENCES 38 * 39 * Deutsch, L.P.,"DEFLATE Compressed Data Format Specification". 40 * Available in http://www.ietf.org/rfc/rfc1951.txt 41 * 42 * A description of the Rabin and Karp algorithm is given in the book 43 * "Algorithms" by R. Sedgewick, Addison-Wesley, p252. 44 * 45 * Fiala,E.R., and Greene,D.H. 46 * Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595 47 * 48 */ 49 50/* @(#) $Id$ */ 51 52#include "deflate.h" 53 54#define read_buf dread_buf 55 56const char deflate_copyright[] = 57 " deflate 1.2.3 Copyright 1995-2005 Jean-loup Gailly "; 58/* 59 If you use the zlib library in a product, an acknowledgment is welcome 60 in the documentation of your product. If for some reason you cannot 61 include such an acknowledgment, I would appreciate that you keep this 62 copyright string in the executable of your product. 63 */ 64 65/* =========================================================================== 66 * Function prototypes. 67 */ 68typedef enum { 69 need_more, /* block not completed, need more input or more output */ 70 block_done, /* block flush performed */ 71 finish_started, /* finish started, need only more output at next deflate */ 72 finish_done /* finish done, accept no more input or output */ 73} block_state; 74 75typedef block_state (*compress_func) OF((deflate_state *s, int flush)); 76/* Compression function. Returns the block state after the call. */ 77 78local void fill_window OF((deflate_state *s)); 79local block_state deflate_stored OF((deflate_state *s, int flush)); 80local block_state deflate_fast OF((deflate_state *s, int flush)); 81#ifndef FASTEST 82local block_state deflate_slow OF((deflate_state *s, int flush)); 83#endif 84local void lm_init OF((deflate_state *s)); 85local void putShortMSB OF((deflate_state *s, uInt b)); 86local void flush_pending OF((z_streamp strm)); 87local int read_buf OF((z_streamp strm, Bytef *buf, unsigned size)); 88#ifndef FASTEST 89#ifdef ASMV 90 void match_init OF((void)); /* asm code initialization */ 91 uInt longest_match OF((deflate_state *s, IPos cur_match)); 92#else 93local uInt longest_match OF((deflate_state *s, IPos cur_match)); 94#endif 95#endif 96local uInt longest_match_fast OF((deflate_state *s, IPos cur_match)); 97 98#ifdef DEBUG 99local void check_match OF((deflate_state *s, IPos start, IPos match, 100 int length)); 101#endif 102 103/* =========================================================================== 104 * Local data 105 */ 106 107#define NIL 0 108/* Tail of hash chains */ 109 110#ifndef TOO_FAR 111# define TOO_FAR 4096 112#endif 113/* Matches of length 3 are discarded if their distance exceeds TOO_FAR */ 114 115#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1) 116/* Minimum amount of lookahead, except at the end of the input file. 117 * See deflate.c for comments about the MIN_MATCH+1. 118 */ 119 120/* Values for max_lazy_match, good_match and max_chain_length, depending on 121 * the desired pack level (0..9). The values given below have been tuned to 122 * exclude worst case performance for pathological files. Better values may be 123 * found for specific files. 124 */ 125typedef struct config_s { 126 ush good_length; /* reduce lazy search above this match length */ 127 ush max_lazy; /* do not perform lazy search above this match length */ 128 ush nice_length; /* quit search above this match length */ 129 ush max_chain; 130 compress_func func; 131} config; 132 133#ifdef FASTEST 134local const config configuration_table[2] = { 135/* good lazy nice chain */ 136/* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */ 137/* 1 */ {4, 4, 8, 4, deflate_fast}}; /* max speed, no lazy matches */ 138#else 139local const config configuration_table[10] = { 140/* good lazy nice chain */ 141/* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */ 142/* 1 */ {4, 4, 8, 4, deflate_fast}, /* max speed, no lazy matches */ 143/* 2 */ {4, 5, 16, 8, deflate_fast}, 144/* 3 */ {4, 6, 32, 32, deflate_fast}, 145 146/* 4 */ {4, 4, 16, 16, deflate_slow}, /* lazy matches */ 147/* 5 */ {8, 16, 32, 32, deflate_slow}, 148/* 6 */ {8, 16, 128, 128, deflate_slow}, 149/* 7 */ {8, 32, 128, 256, deflate_slow}, 150/* 8 */ {32, 128, 258, 1024, deflate_slow}, 151/* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* max compression */ 152#endif 153 154/* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4 155 * For deflate_fast() (levels <= 3) good is ignored and lazy has a different 156 * meaning. 157 */ 158 159#define EQUAL 0 160/* result of memcmp for equal strings */ 161 162#ifndef NO_DUMMY_DECL 163struct static_tree_desc_s {int dummy;}; /* for buggy compilers */ 164#endif 165 166/* =========================================================================== 167 * Update a hash value with the given input byte 168 * IN assertion: all calls to to UPDATE_HASH are made with consecutive 169 * input characters, so that a running hash key can be computed from the 170 * previous key instead of complete recalculation each time. 171 */ 172#define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask) 173 174 175/* =========================================================================== 176 * Insert string str in the dictionary and set match_head to the previous head 177 * of the hash chain (the most recent string with same hash key). Return 178 * the previous length of the hash chain. 179 * If this file is compiled with -DFASTEST, the compression level is forced 180 * to 1, and no hash chains are maintained. 181 * IN assertion: all calls to to INSERT_STRING are made with consecutive 182 * input characters and the first MIN_MATCH bytes of str are valid 183 * (except for the last MIN_MATCH-1 bytes of the input file). 184 */ 185#ifdef FASTEST 186#define INSERT_STRING(s, str, match_head) \ 187 (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \ 188 match_head = s->head[s->ins_h], \ 189 s->head[s->ins_h] = (Pos)(str)) 190#else 191#define INSERT_STRING(s, str, match_head) \ 192 (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \ 193 match_head = s->prev[(str) & s->w_mask] = s->head[s->ins_h], \ 194 s->head[s->ins_h] = (Pos)(str)) 195#endif 196 197/* =========================================================================== 198 * Initialize the hash table (avoiding 64K overflow for 16 bit systems). 199 * prev[] will be initialized on the fly. 200 */ 201#define CLEAR_HASH(s) \ 202 s->head[s->hash_size-1] = NIL; \ 203 zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head)); 204 205/* ========================================================================= */ 206int ZEXPORT deflateInit_(strm, level, version, stream_size) 207 z_streamp strm; 208 int level; 209 const char *version; 210 int stream_size; 211{ 212 return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL, 213 Z_DEFAULT_STRATEGY, version, stream_size); 214 /* To do: ignore strm->next_in if we use it as window */ 215} 216 217/* ========================================================================= */ 218int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy, 219 version, stream_size) 220 z_streamp strm; 221 int level; 222 int method; 223 int windowBits; 224 int memLevel; 225 int strategy; 226 const char *version; 227 int stream_size; 228{ 229 deflate_state *s; 230 int wrap = 1; 231 static const char my_version[] = ZLIB_VERSION; 232 233 ushf *overlay; 234 /* We overlay pending_buf and d_buf+l_buf. This works since the average 235 * output size for (length,distance) codes is <= 24 bits. 236 */ 237 238 if (version == Z_NULL || version[0] != my_version[0] || 239 stream_size != sizeof(z_stream)) { 240 return Z_VERSION_ERROR; 241 } 242 if (strm == Z_NULL) return Z_STREAM_ERROR; 243 244 strm->msg = Z_NULL; 245 if (strm->zalloc == (alloc_func)0) { 246 strm->zalloc = zcalloc; 247 strm->opaque = (voidpf)0; 248 } 249 if (strm->zfree == (free_func)0) strm->zfree = zcfree; 250 251#ifdef FASTEST 252 if (level != 0) level = 1; 253#else 254 if (level == Z_DEFAULT_COMPRESSION) level = 6; 255#endif 256 257 if (windowBits < 0) { /* suppress zlib wrapper */ 258 wrap = 0; 259 windowBits = -windowBits; 260 } 261#ifdef GZIP 262 else if (windowBits > 15) { 263 wrap = 2; /* write gzip wrapper instead */ 264 windowBits -= 16; 265 } 266#endif 267 if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED || 268 windowBits < 8 || windowBits > 15 || level < 0 || level > 9 || 269 strategy < 0 || strategy > Z_FIXED) { 270 return Z_STREAM_ERROR; 271 } 272 if (windowBits == 8) windowBits = 9; /* until 256-byte window bug fixed */ 273 s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state)); 274 if (s == Z_NULL) return Z_MEM_ERROR; 275 strm->state = (struct internal_state FAR *)s; 276 s->strm = strm; 277 278 s->wrap = wrap; 279 s->gzhead = Z_NULL; 280 s->w_bits = windowBits; 281 s->w_size = 1 << s->w_bits; 282 s->w_mask = s->w_size - 1; 283 284 s->hash_bits = memLevel + 7; 285 s->hash_size = 1 << s->hash_bits; 286 s->hash_mask = s->hash_size - 1; 287 s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH); 288 289 s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte)); 290 s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos)); 291 s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos)); 292 293 s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */ 294 295 overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2); 296 s->pending_buf = (uchf *) overlay; 297 s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L); 298 299 if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL || 300 s->pending_buf == Z_NULL) { 301 s->status = FINISH_STATE; 302 strm->msg = (char*)ERR_MSG(Z_MEM_ERROR); 303 deflateEnd (strm); 304 return Z_MEM_ERROR; 305 } 306 s->d_buf = overlay + s->lit_bufsize/sizeof(ush); 307 s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize; 308 309 s->level = level; 310 s->strategy = strategy; 311 s->method = (Byte)method; 312 313 return deflateReset(strm); 314} 315 316/* ========================================================================= */ 317int ZEXPORT deflateSetDictionary (strm, dictionary, dictLength) 318 z_streamp strm; 319 const Bytef *dictionary; 320 uInt dictLength; 321{ 322 deflate_state *s; 323 uInt length = dictLength; 324 uInt n; 325 IPos hash_head = 0; 326 327 if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL || 328 strm->state->wrap == 2 || 329 (strm->state->wrap == 1 && strm->state->status != INIT_STATE)) 330 return Z_STREAM_ERROR; 331 332 s = strm->state; 333 if (s->wrap) 334 strm->adler = adler32(strm->adler, dictionary, dictLength); 335 336 if (length < MIN_MATCH) return Z_OK; 337 if (length > MAX_DIST(s)) { 338 length = MAX_DIST(s); 339 dictionary += dictLength - length; /* use the tail of the dictionary */ 340 } 341 zmemcpy(s->window, dictionary, length); 342 s->strstart = length; 343 s->block_start = (long)length; 344 345 /* Insert all strings in the hash table (except for the last two bytes). 346 * s->lookahead stays null, so s->ins_h will be recomputed at the next 347 * call of fill_window. 348 */ 349 s->ins_h = s->window[0]; 350 UPDATE_HASH(s, s->ins_h, s->window[1]); 351 for (n = 0; n <= length - MIN_MATCH; n++) { 352 INSERT_STRING(s, n, hash_head); 353 } 354 if (hash_head) hash_head = 0; /* to make compiler happy */ 355 return Z_OK; 356} 357 358/* ========================================================================= */ 359int ZEXPORT deflateReset (strm) 360 z_streamp strm; 361{ 362 deflate_state *s; 363 364 if (strm == Z_NULL || strm->state == Z_NULL || 365 strm->zalloc == (alloc_func)0 || strm->zfree == (free_func)0) { 366 return Z_STREAM_ERROR; 367 } 368 369 strm->total_in = strm->total_out = 0; 370 strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */ 371 strm->data_type = Z_UNKNOWN; 372 373 s = (deflate_state *)strm->state; 374 s->pending = 0; 375 s->pending_out = s->pending_buf; 376 377 if (s->wrap < 0) { 378 s->wrap = -s->wrap; /* was made negative by deflate(..., Z_FINISH); */ 379 } 380 s->status = s->wrap ? INIT_STATE : BUSY_STATE; 381 strm->adler = 382#ifdef GZIP 383 s->wrap == 2 ? crc32(0L, Z_NULL, 0) : 384#endif 385 adler32(0L, Z_NULL, 0); 386 s->last_flush = Z_NO_FLUSH; 387 388 _tr_init(s); 389 lm_init(s); 390 391 return Z_OK; 392} 393 394/* ========================================================================= */ 395int ZEXPORT deflateSetHeader (strm, head) 396 z_streamp strm; 397 gz_headerp head; 398{ 399 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 400 if (strm->state->wrap != 2) return Z_STREAM_ERROR; 401 strm->state->gzhead = head; 402 return Z_OK; 403} 404 405/* ========================================================================= */ 406int ZEXPORT deflatePrime (strm, bits, value) 407 z_streamp strm; 408 int bits; 409 int value; 410{ 411 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 412 strm->state->bi_valid = bits; 413 strm->state->bi_buf = (ush)(value & ((1 << bits) - 1)); 414 return Z_OK; 415} 416 417/* ========================================================================= */ 418int ZEXPORT deflateParams(strm, level, strategy) 419 z_streamp strm; 420 int level; 421 int strategy; 422{ 423 deflate_state *s; 424 compress_func func; 425 int err = Z_OK; 426 427 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 428 s = strm->state; 429 430#ifdef FASTEST 431 if (level != 0) level = 1; 432#else 433 if (level == Z_DEFAULT_COMPRESSION) level = 6; 434#endif 435 if (level < 0 || level > 9 || strategy < 0 || strategy > Z_FIXED) { 436 return Z_STREAM_ERROR; 437 } 438 func = configuration_table[s->level].func; 439 440 if (func != configuration_table[level].func && strm->total_in != 0) { 441 /* Flush the last buffer: */ 442 err = deflate(strm, Z_PARTIAL_FLUSH); 443 } 444 if (s->level != level) { 445 s->level = level; 446 s->max_lazy_match = configuration_table[level].max_lazy; 447 s->good_match = configuration_table[level].good_length; 448 s->nice_match = configuration_table[level].nice_length; 449 s->max_chain_length = configuration_table[level].max_chain; 450 } 451 s->strategy = strategy; 452 return err; 453} 454 455/* ========================================================================= */ 456int ZEXPORT deflateTune(strm, good_length, max_lazy, nice_length, max_chain) 457 z_streamp strm; 458 int good_length; 459 int max_lazy; 460 int nice_length; 461 int max_chain; 462{ 463 deflate_state *s; 464 465 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 466 s = strm->state; 467 s->good_match = good_length; 468 s->max_lazy_match = max_lazy; 469 s->nice_match = nice_length; 470 s->max_chain_length = max_chain; 471 return Z_OK; 472} 473 474/* ========================================================================= 475 * For the default windowBits of 15 and memLevel of 8, this function returns 476 * a close to exact, as well as small, upper bound on the compressed size. 477 * They are coded as constants here for a reason--if the #define's are 478 * changed, then this function needs to be changed as well. The return 479 * value for 15 and 8 only works for those exact settings. 480 * 481 * For any setting other than those defaults for windowBits and memLevel, 482 * the value returned is a conservative worst case for the maximum expansion 483 * resulting from using fixed blocks instead of stored blocks, which deflate 484 * can emit on compressed data for some combinations of the parameters. 485 * 486 * This function could be more sophisticated to provide closer upper bounds 487 * for every combination of windowBits and memLevel, as well as wrap. 488 * But even the conservative upper bound of about 14% expansion does not 489 * seem onerous for output buffer allocation. 490 */ 491uLong ZEXPORT deflateBound(strm, sourceLen) 492 z_streamp strm; 493 uLong sourceLen; 494{ 495 deflate_state *s; 496 uLong destLen; 497 498 /* conservative upper bound */ 499 destLen = sourceLen + 500 ((sourceLen + 7) >> 3) + ((sourceLen + 63) >> 6) + 11; 501 502 /* if can't get parameters, return conservative bound */ 503 if (strm == Z_NULL || strm->state == Z_NULL) 504 return destLen; 505 506 /* if not default parameters, return conservative bound */ 507 s = strm->state; 508 if (s->w_bits != 15 || s->hash_bits != 8 + 7) 509 return destLen; 510 511 /* default settings: return tight bound for that case */ 512 return compressBound(sourceLen); 513} 514 515/* ========================================================================= 516 * Put a short in the pending buffer. The 16-bit value is put in MSB order. 517 * IN assertion: the stream state is correct and there is enough room in 518 * pending_buf. 519 */ 520local void putShortMSB (s, b) 521 deflate_state *s; 522 uInt b; 523{ 524 put_byte(s, (Byte)(b >> 8)); 525 put_byte(s, (Byte)(b & 0xff)); 526} 527 528/* ========================================================================= 529 * Flush as much pending output as possible. All deflate() output goes 530 * through this function so some applications may wish to modify it 531 * to avoid allocating a large strm->next_out buffer and copying into it. 532 * (See also read_buf()). 533 */ 534local void flush_pending(strm) 535 z_streamp strm; 536{ 537 unsigned len = strm->state->pending; 538 539 if (len > strm->avail_out) len = strm->avail_out; 540 if (len == 0) return; 541 542 zmemcpy(strm->next_out, strm->state->pending_out, len); 543 strm->next_out += len; 544 strm->state->pending_out += len; 545 strm->total_out += len; 546 strm->avail_out -= len; 547 strm->state->pending -= len; 548 if (strm->state->pending == 0) { 549 strm->state->pending_out = strm->state->pending_buf; 550 } 551} 552 553/* ========================================================================= */ 554int ZEXPORT deflate (strm, flush) 555 z_streamp strm; 556 int flush; 557{ 558 int old_flush; /* value of flush param for previous deflate call */ 559 deflate_state *s; 560 561 if (strm == Z_NULL || strm->state == Z_NULL || 562 flush > Z_INSERT_ONLY || flush < 0) { 563 return Z_STREAM_ERROR; 564 } 565 s = strm->state; 566 567 if (strm->next_out == Z_NULL || 568 (strm->next_in == Z_NULL && strm->avail_in != 0) || 569 (s->status == FINISH_STATE && flush != Z_FINISH)) { 570 ERR_RETURN(strm, Z_STREAM_ERROR); 571 } 572 if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR); 573 574 s->strm = strm; /* just in case */ 575 old_flush = s->last_flush; 576 s->last_flush = flush; 577 578 /* Write the header */ 579 if (s->status == INIT_STATE) { 580#ifdef GZIP 581 if (s->wrap == 2) { 582 strm->adler = crc32(0L, Z_NULL, 0); 583 put_byte(s, 31); 584 put_byte(s, 139); 585 put_byte(s, 8); 586 if (s->gzhead == NULL) { 587 put_byte(s, 0); 588 put_byte(s, 0); 589 put_byte(s, 0); 590 put_byte(s, 0); 591 put_byte(s, 0); 592 put_byte(s, s->level == 9 ? 2 : 593 (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ? 594 4 : 0)); 595 put_byte(s, OS_CODE); 596 s->status = BUSY_STATE; 597 } 598 else { 599 put_byte(s, (s->gzhead->text ? 1 : 0) + 600 (s->gzhead->hcrc ? 2 : 0) + 601 (s->gzhead->extra == Z_NULL ? 0 : 4) + 602 (s->gzhead->name == Z_NULL ? 0 : 8) + 603 (s->gzhead->comment == Z_NULL ? 0 : 16) 604 ); 605 put_byte(s, (Byte)(s->gzhead->time & 0xff)); 606 put_byte(s, (Byte)((s->gzhead->time >> 8) & 0xff)); 607 put_byte(s, (Byte)((s->gzhead->time >> 16) & 0xff)); 608 put_byte(s, (Byte)((s->gzhead->time >> 24) & 0xff)); 609 put_byte(s, s->level == 9 ? 2 : 610 (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ? 611 4 : 0)); 612 put_byte(s, s->gzhead->os & 0xff); 613 if (s->gzhead->extra != NULL) { 614 put_byte(s, s->gzhead->extra_len & 0xff); 615 put_byte(s, (s->gzhead->extra_len >> 8) & 0xff); 616 } 617 if (s->gzhead->hcrc) 618 strm->adler = crc32(strm->adler, s->pending_buf, 619 s->pending); 620 s->gzindex = 0; 621 s->status = EXTRA_STATE; 622 } 623 } 624 else 625#endif 626 { 627 uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8; 628 uInt level_flags; 629 630 if (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2) 631 level_flags = 0; 632 else if (s->level < 6) 633 level_flags = 1; 634 else if (s->level == 6) 635 level_flags = 2; 636 else 637 level_flags = 3; 638 header |= (level_flags << 6); 639 if (s->strstart != 0) header |= PRESET_DICT; 640 header += 31 - (header % 31); 641 642 s->status = BUSY_STATE; 643 putShortMSB(s, header); 644 645 /* Save the adler32 of the preset dictionary: */ 646 if (s->strstart != 0) { 647 putShortMSB(s, (uInt)(strm->adler >> 16)); 648 putShortMSB(s, (uInt)(strm->adler & 0xffff)); 649 } 650 strm->adler = adler32(0L, Z_NULL, 0); 651 } 652 } 653#ifdef GZIP 654 if (s->status == EXTRA_STATE) { 655 if (s->gzhead->extra != NULL) { 656 uInt beg = s->pending; /* start of bytes to update crc */ 657 658 while (s->gzindex < (s->gzhead->extra_len & 0xffff)) { 659 if (s->pending == s->pending_buf_size) { 660 if (s->gzhead->hcrc && s->pending > beg) 661 strm->adler = crc32(strm->adler, s->pending_buf + beg, 662 s->pending - beg); 663 flush_pending(strm); 664 beg = s->pending; 665 if (s->pending == s->pending_buf_size) 666 break; 667 } 668 put_byte(s, s->gzhead->extra[s->gzindex]); 669 s->gzindex++; 670 } 671 if (s->gzhead->hcrc && s->pending > beg) 672 strm->adler = crc32(strm->adler, s->pending_buf + beg, 673 s->pending - beg); 674 if (s->gzindex == s->gzhead->extra_len) { 675 s->gzindex = 0; 676 s->status = NAME_STATE; 677 } 678 } 679 else 680 s->status = NAME_STATE; 681 } 682 if (s->status == NAME_STATE) { 683 if (s->gzhead->name != NULL) { 684 uInt beg = s->pending; /* start of bytes to update crc */ 685 int val; 686 687 do { 688 if (s->pending == s->pending_buf_size) { 689 if (s->gzhead->hcrc && s->pending > beg) 690 strm->adler = crc32(strm->adler, s->pending_buf + beg, 691 s->pending - beg); 692 flush_pending(strm); 693 beg = s->pending; 694 if (s->pending == s->pending_buf_size) { 695 val = 1; 696 break; 697 } 698 } 699 val = s->gzhead->name[s->gzindex++]; 700 put_byte(s, val); 701 } while (val != 0); 702 if (s->gzhead->hcrc && s->pending > beg) 703 strm->adler = crc32(strm->adler, s->pending_buf + beg, 704 s->pending - beg); 705 if (val == 0) { 706 s->gzindex = 0; 707 s->status = COMMENT_STATE; 708 } 709 } 710 else 711 s->status = COMMENT_STATE; 712 } 713 if (s->status == COMMENT_STATE) { 714 if (s->gzhead->comment != NULL) { 715 uInt beg = s->pending; /* start of bytes to update crc */ 716 int val; 717 718 do { 719 if (s->pending == s->pending_buf_size) { 720 if (s->gzhead->hcrc && s->pending > beg) 721 strm->adler = crc32(strm->adler, s->pending_buf + beg, 722 s->pending - beg); 723 flush_pending(strm); 724 beg = s->pending; 725 if (s->pending == s->pending_buf_size) { 726 val = 1; 727 break; 728 } 729 } 730 val = s->gzhead->comment[s->gzindex++]; 731 put_byte(s, val); 732 } while (val != 0); 733 if (s->gzhead->hcrc && s->pending > beg) 734 strm->adler = crc32(strm->adler, s->pending_buf + beg, 735 s->pending - beg); 736 if (val == 0) 737 s->status = HCRC_STATE; 738 } 739 else 740 s->status = HCRC_STATE; 741 } 742 if (s->status == HCRC_STATE) { 743 if (s->gzhead->hcrc) { 744 if (s->pending + 2 > s->pending_buf_size) 745 flush_pending(strm); 746 if (s->pending + 2 <= s->pending_buf_size) { 747 put_byte(s, (Byte)(strm->adler & 0xff)); 748 put_byte(s, (Byte)((strm->adler >> 8) & 0xff)); 749 strm->adler = crc32(0L, Z_NULL, 0); 750 s->status = BUSY_STATE; 751 } 752 } 753 else 754 s->status = BUSY_STATE; 755 } 756#endif 757 758 /* Flush as much pending output as possible */ 759 if (s->pending != 0) { 760 flush_pending(strm); 761 if (strm->avail_out == 0) { 762 /* Since avail_out is 0, deflate will be called again with 763 * more output space, but possibly with both pending and 764 * avail_in equal to zero. There won't be anything to do, 765 * but this is not an error situation so make sure we 766 * return OK instead of BUF_ERROR at next call of deflate: 767 */ 768 s->last_flush = -1; 769 return Z_OK; 770 } 771 772 /* Make sure there is something to do and avoid duplicate consecutive 773 * flushes. For repeated and useless calls with Z_FINISH, we keep 774 * returning Z_STREAM_END instead of Z_BUF_ERROR. 775 */ 776 } else if (strm->avail_in == 0 && flush <= old_flush && 777 flush != Z_FINISH) { 778 ERR_RETURN(strm, Z_BUF_ERROR); 779 } 780 781 /* User must not provide more input after the first FINISH: */ 782 if (s->status == FINISH_STATE && strm->avail_in != 0) { 783 ERR_RETURN(strm, Z_BUF_ERROR); 784 } 785 786 /* Start a new block or continue the current one. 787 */ 788 if (strm->avail_in != 0 || s->lookahead != 0 || 789 (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) { 790 block_state bstate; 791 792 bstate = (*(configuration_table[s->level].func))(s, flush); 793 794 if (bstate == finish_started || bstate == finish_done) { 795 s->status = FINISH_STATE; 796 } 797 if (bstate == need_more || bstate == finish_started) { 798 if (strm->avail_out == 0) { 799 s->last_flush = -1; /* avoid BUF_ERROR next call, see above */ 800 } 801 return Z_OK; 802 /* If flush != Z_NO_FLUSH && avail_out == 0, the next call 803 * of deflate should use the same flush parameter to make sure 804 * that the flush is complete. So we don't have to output an 805 * empty block here, this will be done at next call. This also 806 * ensures that for a very small output buffer, we emit at most 807 * one empty block. 808 */ 809 } 810 if (bstate == block_done) { 811 if (flush == Z_PARTIAL_FLUSH) { 812 _tr_align(s); 813 } else { /* FULL_FLUSH or SYNC_FLUSH */ 814 _tr_stored_block(s, (char*)0, 0L, 0); 815 /* For a full flush, this empty block will be recognized 816 * as a special marker by inflate_sync(). 817 */ 818 if (flush == Z_FULL_FLUSH) { 819 CLEAR_HASH(s); /* forget history */ 820 } 821 } 822 flush_pending(strm); 823 if (strm->avail_out == 0) { 824 s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */ 825 return Z_OK; 826 } 827 } 828 } 829 Assert(strm->avail_out > 0, "bug2"); 830 831 if (flush != Z_FINISH) return Z_OK; 832 if (s->wrap <= 0) return Z_STREAM_END; 833 834 /* Write the trailer */ 835#ifdef GZIP 836 if (s->wrap == 2) { 837 put_byte(s, (Byte)(strm->adler & 0xff)); 838 put_byte(s, (Byte)((strm->adler >> 8) & 0xff)); 839 put_byte(s, (Byte)((strm->adler >> 16) & 0xff)); 840 put_byte(s, (Byte)((strm->adler >> 24) & 0xff)); 841 put_byte(s, (Byte)(strm->total_in & 0xff)); 842 put_byte(s, (Byte)((strm->total_in >> 8) & 0xff)); 843 put_byte(s, (Byte)((strm->total_in >> 16) & 0xff)); 844 put_byte(s, (Byte)((strm->total_in >> 24) & 0xff)); 845 } 846 else 847#endif 848 { 849 putShortMSB(s, (uInt)(strm->adler >> 16)); 850 putShortMSB(s, (uInt)(strm->adler & 0xffff)); 851 } 852 flush_pending(strm); 853 /* If avail_out is zero, the application will call deflate again 854 * to flush the rest. 855 */ 856 if (s->wrap > 0) s->wrap = -s->wrap; /* write the trailer only once! */ 857 return s->pending != 0 ? Z_OK : Z_STREAM_END; 858} 859 860/* ========================================================================= */ 861int ZEXPORT deflateEnd (strm) 862 z_streamp strm; 863{ 864 int status; 865 866 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 867 868 status = strm->state->status; 869 if (status != INIT_STATE && 870 status != EXTRA_STATE && 871 status != NAME_STATE && 872 status != COMMENT_STATE && 873 status != HCRC_STATE && 874 status != BUSY_STATE && 875 status != FINISH_STATE) { 876 return Z_STREAM_ERROR; 877 } 878 879 /* Deallocate in reverse order of allocations: */ 880 TRY_FREE(strm, strm->state->pending_buf); 881 TRY_FREE(strm, strm->state->head); 882 TRY_FREE(strm, strm->state->prev); 883 TRY_FREE(strm, strm->state->window); 884 885 ZFREE(strm, strm->state); 886 strm->state = Z_NULL; 887 888 return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK; 889} 890 891/* ========================================================================= 892 * Copy the source state to the destination state. 893 * To simplify the source, this is not supported for 16-bit MSDOS (which 894 * doesn't have enough memory anyway to duplicate compression states). 895 */ 896int ZEXPORT deflateCopy (dest, source) 897 z_streamp dest; 898 z_streamp source; 899{ 900#ifdef MAXSEG_64K 901 return Z_STREAM_ERROR; 902#else 903 deflate_state *ds; 904 deflate_state *ss; 905 ushf *overlay; 906 907 908 if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL) { 909 return Z_STREAM_ERROR; 910 } 911 912 ss = source->state; 913 914 zmemcpy(dest, source, sizeof(z_stream)); 915 916 ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state)); 917 if (ds == Z_NULL) return Z_MEM_ERROR; 918 dest->state = (struct internal_state FAR *) ds; 919 zmemcpy(ds, ss, sizeof(deflate_state)); 920 ds->strm = dest; 921 922 ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte)); 923 ds->prev = (Posf *) ZALLOC(dest, ds->w_size, sizeof(Pos)); 924 ds->head = (Posf *) ZALLOC(dest, ds->hash_size, sizeof(Pos)); 925 overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof(ush)+2); 926 ds->pending_buf = (uchf *) overlay; 927 928 if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL || 929 ds->pending_buf == Z_NULL) { 930 deflateEnd (dest); 931 return Z_MEM_ERROR; 932 } 933 /* following zmemcpy do not work for 16-bit MSDOS */ 934 zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte)); 935 zmemcpy(ds->prev, ss->prev, ds->w_size * sizeof(Pos)); 936 zmemcpy(ds->head, ss->head, ds->hash_size * sizeof(Pos)); 937 zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size); 938 939 ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf); 940 ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush); 941 ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize; 942 943 ds->l_desc.dyn_tree = ds->dyn_ltree; 944 ds->d_desc.dyn_tree = ds->dyn_dtree; 945 ds->bl_desc.dyn_tree = ds->bl_tree; 946 947 return Z_OK; 948#endif /* MAXSEG_64K */ 949} 950 951/* =========================================================================== 952 * Read a new buffer from the current input stream, update the adler32 953 * and total number of bytes read. All deflate() input goes through 954 * this function so some applications may wish to modify it to avoid 955 * allocating a large strm->next_in buffer and copying from it. 956 * (See also flush_pending()). 957 */ 958local int read_buf(strm, buf, size) 959 z_streamp strm; 960 Bytef *buf; 961 unsigned size; 962{ 963 unsigned len = strm->avail_in; 964 965 if (len > size) len = size; 966 if (len == 0) return 0; 967 968 strm->avail_in -= len; 969 970 if (strm->state->wrap == 1) { 971 strm->adler = adler32(strm->adler, strm->next_in, len); 972 } 973#ifdef GZIP 974 else if (strm->state->wrap == 2) { 975 strm->adler = crc32(strm->adler, strm->next_in, len); 976 } 977#endif 978 zmemcpy(buf, strm->next_in, len); 979 strm->next_in += len; 980 strm->total_in += len; 981 982 return (int)len; 983} 984 985/* =========================================================================== 986 * Initialize the "longest match" routines for a new zlib stream 987 */ 988local void lm_init (s) 989 deflate_state *s; 990{ 991 s->window_size = (ulg)2L*s->w_size; 992 993 CLEAR_HASH(s); 994 995 /* Set the default configuration parameters: 996 */ 997 s->max_lazy_match = configuration_table[s->level].max_lazy; 998 s->good_match = configuration_table[s->level].good_length; 999 s->nice_match = configuration_table[s->level].nice_length; 1000 s->max_chain_length = configuration_table[s->level].max_chain; 1001 1002 s->strstart = 0; 1003 s->block_start = 0L; 1004 s->lookahead = 0; 1005 s->match_length = s->prev_length = MIN_MATCH-1; 1006 s->match_available = 0; 1007 s->ins_h = 0; 1008#ifndef FASTEST 1009#ifdef ASMV 1010 match_init(); /* initialize the asm code */ 1011#endif 1012#endif 1013} 1014 1015#ifndef FASTEST 1016/* =========================================================================== 1017 * Set match_start to the longest match starting at the given string and 1018 * return its length. Matches shorter or equal to prev_length are discarded, 1019 * in which case the result is equal to prev_length and match_start is 1020 * garbage. 1021 * IN assertions: cur_match is the head of the hash chain for the current 1022 * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1 1023 * OUT assertion: the match length is not greater than s->lookahead. 1024 */ 1025#ifndef ASMV 1026/* For 80x86 and 680x0, an optimized version will be provided in match.asm or 1027 * match.S. The code will be functionally equivalent. 1028 */ 1029local uInt longest_match(s, cur_match) 1030 deflate_state *s; 1031 IPos cur_match; /* current match */ 1032{ 1033 unsigned chain_length = s->max_chain_length;/* max hash chain length */ 1034 register Bytef *scan = s->window + s->strstart; /* current string */ 1035 register Bytef *match; /* matched string */ 1036 register int len; /* length of current match */ 1037 int best_len = s->prev_length; /* best match length so far */ 1038 int nice_match = s->nice_match; /* stop if match long enough */ 1039 IPos limit = s->strstart > (IPos)MAX_DIST(s) ? 1040 s->strstart - (IPos)MAX_DIST(s) : NIL; 1041 /* Stop when cur_match becomes <= limit. To simplify the code, 1042 * we prevent matches with the string of window index 0. 1043 */ 1044 Posf *prev = s->prev; 1045 uInt wmask = s->w_mask; 1046 1047#ifdef UNALIGNED_OK 1048 /* Compare two bytes at a time. Note: this is not always beneficial. 1049 * Try with and without -DUNALIGNED_OK to check. 1050 */ 1051 register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1; 1052 register ush scan_start = *(ushf*)scan; 1053 register ush scan_end = *(ushf*)(scan+best_len-1); 1054#else 1055 register Bytef *strend = s->window + s->strstart + MAX_MATCH; 1056 register Byte scan_end1 = scan[best_len-1]; 1057 register Byte scan_end = scan[best_len]; 1058#endif 1059 1060 /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. 1061 * It is easy to get rid of this optimization if necessary. 1062 */ 1063 Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever"); 1064 1065 /* Do not waste too much time if we already have a good match: */ 1066 if (s->prev_length >= s->good_match) { 1067 chain_length >>= 2; 1068 } 1069 /* Do not look for matches beyond the end of the input. This is necessary 1070 * to make deflate deterministic. 1071 */ 1072 if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead; 1073 1074 Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead"); 1075 1076 do { 1077 Assert(cur_match < s->strstart, "no future"); 1078 match = s->window + cur_match; 1079 1080 /* Skip to next match if the match length cannot increase 1081 * or if the match length is less than 2. Note that the checks below 1082 * for insufficient lookahead only occur occasionally for performance 1083 * reasons. Therefore uninitialized memory will be accessed, and 1084 * conditional jumps will be made that depend on those values. 1085 * However the length of the match is limited to the lookahead, so 1086 * the output of deflate is not affected by the uninitialized values. 1087 */ 1088#if (defined(UNALIGNED_OK) && MAX_MATCH == 258) 1089 /* This code assumes sizeof(unsigned short) == 2. Do not use 1090 * UNALIGNED_OK if your compiler uses a different size. 1091 */ 1092 if (*(ushf*)(match+best_len-1) != scan_end || 1093 *(ushf*)match != scan_start) continue; 1094 1095 /* It is not necessary to compare scan[2] and match[2] since they are 1096 * always equal when the other bytes match, given that the hash keys 1097 * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at 1098 * strstart+3, +5, ... up to strstart+257. We check for insufficient 1099 * lookahead only every 4th comparison; the 128th check will be made 1100 * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is 1101 * necessary to put more guard bytes at the end of the window, or 1102 * to check more often for insufficient lookahead. 1103 */ 1104 Assert(scan[2] == match[2], "scan[2]?"); 1105 scan++, match++; 1106 do { 1107 } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) && 1108 *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 1109 *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 1110 *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 1111 scan < strend); 1112 /* The funny "do {}" generates better code on most compilers */ 1113 1114 /* Here, scan <= window+strstart+257 */ 1115 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 1116 if (*scan == *match) scan++; 1117 1118 len = (MAX_MATCH - 1) - (int)(strend-scan); 1119 scan = strend - (MAX_MATCH-1); 1120 1121#else /* UNALIGNED_OK */ 1122 1123 if (match[best_len] != scan_end || 1124 match[best_len-1] != scan_end1 || 1125 *match != *scan || 1126 *++match != scan[1]) continue; 1127 1128 /* The check at best_len-1 can be removed because it will be made 1129 * again later. (This heuristic is not always a win.) 1130 * It is not necessary to compare scan[2] and match[2] since they 1131 * are always equal when the other bytes match, given that 1132 * the hash keys are equal and that HASH_BITS >= 8. 1133 */ 1134 scan += 2, match++; 1135 Assert(*scan == *match, "match[2]?"); 1136 1137 /* We check for insufficient lookahead only every 8th comparison; 1138 * the 256th check will be made at strstart+258. 1139 */ 1140 do { 1141 } while (*++scan == *++match && *++scan == *++match && 1142 *++scan == *++match && *++scan == *++match && 1143 *++scan == *++match && *++scan == *++match && 1144 *++scan == *++match && *++scan == *++match && 1145 scan < strend); 1146 1147 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 1148 1149 len = MAX_MATCH - (int)(strend - scan); 1150 scan = strend - MAX_MATCH; 1151 1152#endif /* UNALIGNED_OK */ 1153 1154 if (len > best_len) { 1155 s->match_start = cur_match; 1156 best_len = len; 1157 if (len >= nice_match) break; 1158#ifdef UNALIGNED_OK 1159 scan_end = *(ushf*)(scan+best_len-1); 1160#else 1161 scan_end1 = scan[best_len-1]; 1162 scan_end = scan[best_len]; 1163#endif 1164 } 1165 } while ((cur_match = prev[cur_match & wmask]) > limit 1166 && --chain_length != 0); 1167 1168 if ((uInt)best_len <= s->lookahead) return (uInt)best_len; 1169 return s->lookahead; 1170} 1171#endif /* ASMV */ 1172#endif /* FASTEST */ 1173 1174/* --------------------------------------------------------------------------- 1175 * Optimized version for level == 1 or strategy == Z_RLE only 1176 */ 1177local uInt longest_match_fast(s, cur_match) 1178 deflate_state *s; 1179 IPos cur_match; /* current match */ 1180{ 1181 register Bytef *scan = s->window + s->strstart; /* current string */ 1182 register Bytef *match; /* matched string */ 1183 register int len; /* length of current match */ 1184 register Bytef *strend = s->window + s->strstart + MAX_MATCH; 1185 1186 /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. 1187 * It is easy to get rid of this optimization if necessary. 1188 */ 1189 Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever"); 1190 1191 Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead"); 1192 1193 Assert(cur_match < s->strstart, "no future"); 1194 1195 match = s->window + cur_match; 1196 1197 /* Return failure if the match length is less than 2: 1198 */ 1199 if (match[0] != scan[0] || match[1] != scan[1]) return MIN_MATCH-1; 1200 1201 /* The check at best_len-1 can be removed because it will be made 1202 * again later. (This heuristic is not always a win.) 1203 * It is not necessary to compare scan[2] and match[2] since they 1204 * are always equal when the other bytes match, given that 1205 * the hash keys are equal and that HASH_BITS >= 8. 1206 */ 1207 scan += 2, match += 2; 1208 Assert(*scan == *match, "match[2]?"); 1209 1210 /* We check for insufficient lookahead only every 8th comparison; 1211 * the 256th check will be made at strstart+258. 1212 */ 1213 do { 1214 } while (*++scan == *++match && *++scan == *++match && 1215 *++scan == *++match && *++scan == *++match && 1216 *++scan == *++match && *++scan == *++match && 1217 *++scan == *++match && *++scan == *++match && 1218 scan < strend); 1219 1220 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 1221 1222 len = MAX_MATCH - (int)(strend - scan); 1223 1224 if (len < MIN_MATCH) return MIN_MATCH - 1; 1225 1226 s->match_start = cur_match; 1227 return (uInt)len <= s->lookahead ? (uInt)len : s->lookahead; 1228} 1229 1230#ifdef DEBUG 1231/* =========================================================================== 1232 * Check that the match at match_start is indeed a match. 1233 */ 1234local void check_match(s, start, match, length) 1235 deflate_state *s; 1236 IPos start, match; 1237 int length; 1238{ 1239 /* check that the match is indeed a match */ 1240 if (zmemcmp(s->window + match, 1241 s->window + start, length) != EQUAL) { 1242 fprintf(stderr, " start %u, match %u, length %d\n", 1243 start, match, length); 1244 do { 1245 fprintf(stderr, "%c%c", s->window[match++], s->window[start++]); 1246 } while (--length != 0); 1247 z_error("invalid match"); 1248 } 1249 if (z_verbose > 1) { 1250 fprintf(stderr,"\\[%d,%d]", start-match, length); 1251 do { putc(s->window[start++], stderr); } while (--length != 0); 1252 } 1253} 1254#else 1255# define check_match(s, start, match, length) 1256#endif /* DEBUG */ 1257 1258/* =========================================================================== 1259 * Fill the window when the lookahead becomes insufficient. 1260 * Updates strstart and lookahead. 1261 * 1262 * IN assertion: lookahead < MIN_LOOKAHEAD 1263 * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD 1264 * At least one byte has been read, or avail_in == 0; reads are 1265 * performed for at least two bytes (required for the zip translate_eol 1266 * option -- not supported here). 1267 */ 1268local void fill_window(s) 1269 deflate_state *s; 1270{ 1271 register unsigned n, m; 1272 register Posf *p; 1273 unsigned more; /* Amount of free space at the end of the window. */ 1274 uInt wsize = s->w_size; 1275 1276 do { 1277 more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart); 1278 1279 /* Deal with !@#$% 64K limit: */ 1280 if (sizeof(int) <= 2) { 1281 if (more == 0 && s->strstart == 0 && s->lookahead == 0) { 1282 more = wsize; 1283 1284 } else if (more == (unsigned)(-1)) { 1285 /* Very unlikely, but possible on 16 bit machine if 1286 * strstart == 0 && lookahead == 1 (input done a byte at time) 1287 */ 1288 more--; 1289 } 1290 } 1291 1292 /* If the window is almost full and there is insufficient lookahead, 1293 * move the upper half to the lower one to make room in the upper half. 1294 */ 1295 if (s->strstart >= wsize+MAX_DIST(s)) { 1296 1297 zmemcpy(s->window, s->window+wsize, (unsigned)wsize); 1298 s->match_start -= wsize; 1299 s->strstart -= wsize; /* we now have strstart >= MAX_DIST */ 1300 s->block_start -= (long) wsize; 1301 1302 /* Slide the hash table (could be avoided with 32 bit values 1303 at the expense of memory usage). We slide even when level == 0 1304 to keep the hash table consistent if we switch back to level > 0 1305 later. (Using level 0 permanently is not an optimal usage of 1306 zlib, so we don't care about this pathological case.) 1307 */ 1308 /* %%% avoid this when Z_RLE */ 1309 n = s->hash_size; 1310 p = &s->head[n]; 1311 do { 1312 m = *--p; 1313 *p = (Pos)(m >= wsize ? m-wsize : NIL); 1314 } while (--n); 1315 1316 n = wsize; 1317#ifndef FASTEST 1318 p = &s->prev[n]; 1319 do { 1320 m = *--p; 1321 *p = (Pos)(m >= wsize ? m-wsize : NIL); 1322 /* If n is not on any hash chain, prev[n] is garbage but 1323 * its value will never be used. 1324 */ 1325 } while (--n); 1326#endif 1327 more += wsize; 1328 } 1329 if (s->strm->avail_in == 0) return; 1330 1331 /* If there was no sliding: 1332 * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 && 1333 * more == window_size - lookahead - strstart 1334 * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1) 1335 * => more >= window_size - 2*WSIZE + 2 1336 * In the BIG_MEM or MMAP case (not yet supported), 1337 * window_size == input_size + MIN_LOOKAHEAD && 1338 * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD. 1339 * Otherwise, window_size == 2*WSIZE so more >= 2. 1340 * If there was sliding, more >= WSIZE. So in all cases, more >= 2. 1341 */ 1342 Assert(more >= 2, "more < 2"); 1343 1344 n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more); 1345 s->lookahead += n; 1346 1347 /* Initialize the hash value now that we have some input: */ 1348 if (s->lookahead >= MIN_MATCH) { 1349 s->ins_h = s->window[s->strstart]; 1350 UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]); 1351#if MIN_MATCH != 3 1352 Call UPDATE_HASH() MIN_MATCH-3 more times 1353#endif 1354 } 1355 /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage, 1356 * but this is not important since only literal bytes will be emitted. 1357 */ 1358 1359 } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0); 1360} 1361 1362/* =========================================================================== 1363 * Flush the current block, with given end-of-file flag. 1364 * IN assertion: strstart is set to the end of the current match. 1365 */ 1366#define FLUSH_BLOCK_ONLY(s, eof) { \ 1367 _tr_flush_block(s, (s->block_start >= 0L ? \ 1368 (charf *)&s->window[(unsigned)s->block_start] : \ 1369 (charf *)Z_NULL), \ 1370 (ulg)((long)s->strstart - s->block_start), \ 1371 (eof)); \ 1372 s->block_start = s->strstart; \ 1373 flush_pending(s->strm); \ 1374 Tracev((stderr,"[FLUSH]")); \ 1375} 1376 1377/* Same but force premature exit if necessary. */ 1378#define FLUSH_BLOCK(s, eof) { \ 1379 FLUSH_BLOCK_ONLY(s, eof); \ 1380 if (s->strm->avail_out == 0) return (eof) ? finish_started : need_more; \ 1381} 1382 1383/* =========================================================================== 1384 * Copy without compression as much as possible from the input stream, return 1385 * the current block state. 1386 * This function does not insert new strings in the dictionary since 1387 * uncompressible data is probably not useful. This function is used 1388 * only for the level=0 compression option. 1389 * NOTE: this function should be optimized to avoid extra copying from 1390 * window to pending_buf. 1391 */ 1392local block_state deflate_stored(s, flush) 1393 deflate_state *s; 1394 int flush; 1395{ 1396 /* Stored blocks are limited to 0xffff bytes, pending_buf is limited 1397 * to pending_buf_size, and each stored block has a 5 byte header: 1398 */ 1399 ulg max_block_size = 0xffff; 1400 ulg max_start; 1401 1402 if (max_block_size > s->pending_buf_size - 5) { 1403 max_block_size = s->pending_buf_size - 5; 1404 } 1405 1406 /* Copy as much as possible from input to output: */ 1407 for (;;) { 1408 /* Fill the window as much as possible: */ 1409 if (s->lookahead <= 1) { 1410 1411 Assert(s->strstart < s->w_size+MAX_DIST(s) || 1412 s->block_start >= (long)s->w_size, "slide too late"); 1413 1414 fill_window(s); 1415 if (s->lookahead == 0 && flush == Z_NO_FLUSH) return need_more; 1416 1417 if (s->lookahead == 0) break; /* flush the current block */ 1418 } 1419 Assert(s->block_start >= 0L, "block gone"); 1420 1421 s->strstart += s->lookahead; 1422 s->lookahead = 0; 1423 1424 if (flush == Z_INSERT_ONLY) { 1425 s->block_start = s->strstart; 1426 continue; 1427 } 1428 1429 /* Emit a stored block if pending_buf will be full: */ 1430 max_start = s->block_start + max_block_size; 1431 if (s->strstart == 0 || (ulg)s->strstart >= max_start) { 1432 /* strstart == 0 is possible when wraparound on 16-bit machine */ 1433 s->lookahead = (uInt)(s->strstart - max_start); 1434 s->strstart = (uInt)max_start; 1435 FLUSH_BLOCK(s, 0); 1436 } 1437 /* Flush if we may have to slide, otherwise block_start may become 1438 * negative and the data will be gone: 1439 */ 1440 if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) { 1441 FLUSH_BLOCK(s, 0); 1442 } 1443 } 1444 if (flush == Z_INSERT_ONLY) { 1445 s->block_start = s->strstart; 1446 return need_more; 1447 } 1448 1449 FLUSH_BLOCK(s, flush == Z_FINISH); 1450 return flush == Z_FINISH ? finish_done : block_done; 1451} 1452 1453/* =========================================================================== 1454 * Compress as much as possible from the input stream, return the current 1455 * block state. 1456 * This function does not perform lazy evaluation of matches and inserts 1457 * new strings in the dictionary only for unmatched strings or for short 1458 * matches. It is used only for the fast compression options. 1459 */ 1460local block_state deflate_fast(s, flush) 1461 deflate_state *s; 1462 int flush; 1463{ 1464 IPos hash_head = NIL; /* head of the hash chain */ 1465 int bflush; /* set if current block must be flushed */ 1466 1467 for (;;) { 1468 /* Make sure that we always have enough lookahead, except 1469 * at the end of the input file. We need MAX_MATCH bytes 1470 * for the next match, plus MIN_MATCH bytes to insert the 1471 * string following the next match. 1472 */ 1473 if (s->lookahead < MIN_LOOKAHEAD) { 1474 fill_window(s); 1475 if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { 1476 return need_more; 1477 } 1478 if (s->lookahead == 0) break; /* flush the current block */ 1479 } 1480 1481 /* Insert the string window[strstart .. strstart+2] in the 1482 * dictionary, and set hash_head to the head of the hash chain: 1483 */ 1484 if (s->lookahead >= MIN_MATCH) { 1485 INSERT_STRING(s, s->strstart, hash_head); 1486 } 1487 1488 if (flush == Z_INSERT_ONLY) { 1489 s->strstart++; 1490 s->lookahead--; 1491 continue; 1492 } 1493 1494 /* Find the longest match, discarding those <= prev_length. 1495 * At this point we have always match_length < MIN_MATCH 1496 */ 1497 if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) { 1498 /* To simplify the code, we prevent matches with the string 1499 * of window index 0 (in particular we have to avoid a match 1500 * of the string with itself at the start of the input file). 1501 */ 1502#ifdef FASTEST 1503 if ((s->strategy != Z_HUFFMAN_ONLY && s->strategy != Z_RLE) || 1504 (s->strategy == Z_RLE && s->strstart - hash_head == 1)) { 1505 s->match_length = longest_match_fast (s, hash_head); 1506 } 1507#else 1508 if (s->strategy != Z_HUFFMAN_ONLY && s->strategy != Z_RLE) { 1509 s->match_length = longest_match (s, hash_head); 1510 } else if (s->strategy == Z_RLE && s->strstart - hash_head == 1) { 1511 s->match_length = longest_match_fast (s, hash_head); 1512 } 1513#endif 1514 /* longest_match() or longest_match_fast() sets match_start */ 1515 } 1516 if (s->match_length >= MIN_MATCH) { 1517 check_match(s, s->strstart, s->match_start, s->match_length); 1518 1519 _tr_tally_dist(s, s->strstart - s->match_start, 1520 s->match_length - MIN_MATCH, bflush); 1521 1522 s->lookahead -= s->match_length; 1523 1524 /* Insert new strings in the hash table only if the match length 1525 * is not too large. This saves time but degrades compression. 1526 */ 1527#ifndef FASTEST 1528 if (s->match_length <= s->max_insert_length && 1529 s->lookahead >= MIN_MATCH) { 1530 s->match_length--; /* string at strstart already in table */ 1531 do { 1532 s->strstart++; 1533 INSERT_STRING(s, s->strstart, hash_head); 1534 /* strstart never exceeds WSIZE-MAX_MATCH, so there are 1535 * always MIN_MATCH bytes ahead. 1536 */ 1537 } while (--s->match_length != 0); 1538 s->strstart++; 1539 } else 1540#endif 1541 { 1542 s->strstart += s->match_length; 1543 s->match_length = 0; 1544 s->ins_h = s->window[s->strstart]; 1545 UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]); 1546#if MIN_MATCH != 3 1547 Call UPDATE_HASH() MIN_MATCH-3 more times 1548#endif 1549 /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not 1550 * matter since it will be recomputed at next deflate call. 1551 */ 1552 } 1553 } else { 1554 /* No match, output a literal byte */ 1555 Tracevv((stderr,"%c", s->window[s->strstart])); 1556 _tr_tally_lit (s, s->window[s->strstart], bflush); 1557 s->lookahead--; 1558 s->strstart++; 1559 } 1560 if (bflush) FLUSH_BLOCK(s, 0); 1561 } 1562 if (flush == Z_INSERT_ONLY) { 1563 s->block_start = s->strstart; 1564 return need_more; 1565 } 1566 FLUSH_BLOCK(s, flush == Z_FINISH); 1567 return flush == Z_FINISH ? finish_done : block_done; 1568} 1569 1570#ifndef FASTEST 1571/* =========================================================================== 1572 * Same as above, but achieves better compression. We use a lazy 1573 * evaluation for matches: a match is finally adopted only if there is 1574 * no better match at the next window position. 1575 */ 1576local block_state deflate_slow(s, flush) 1577 deflate_state *s; 1578 int flush; 1579{ 1580 IPos hash_head = NIL; /* head of hash chain */ 1581 int bflush; /* set if current block must be flushed */ 1582 1583 /* Process the input block. */ 1584 for (;;) { 1585 /* Make sure that we always have enough lookahead, except 1586 * at the end of the input file. We need MAX_MATCH bytes 1587 * for the next match, plus MIN_MATCH bytes to insert the 1588 * string following the next match. 1589 */ 1590 if (s->lookahead < MIN_LOOKAHEAD) { 1591 fill_window(s); 1592 if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { 1593 return need_more; 1594 } 1595 if (s->lookahead == 0) break; /* flush the current block */ 1596 } 1597 1598 /* Insert the string window[strstart .. strstart+2] in the 1599 * dictionary, and set hash_head to the head of the hash chain: 1600 */ 1601 if (s->lookahead >= MIN_MATCH) { 1602 INSERT_STRING(s, s->strstart, hash_head); 1603 } 1604 1605 if (flush == Z_INSERT_ONLY) { 1606 s->strstart++; 1607 s->lookahead--; 1608 continue; 1609 } 1610 1611 /* Find the longest match, discarding those <= prev_length. 1612 */ 1613 s->prev_length = s->match_length, s->prev_match = s->match_start; 1614 s->match_length = MIN_MATCH-1; 1615 1616 if (hash_head != NIL && s->prev_length < s->max_lazy_match && 1617 s->strstart - hash_head <= MAX_DIST(s)) { 1618 /* To simplify the code, we prevent matches with the string 1619 * of window index 0 (in particular we have to avoid a match 1620 * of the string with itself at the start of the input file). 1621 */ 1622 if (s->strategy != Z_HUFFMAN_ONLY && s->strategy != Z_RLE) { 1623 s->match_length = longest_match (s, hash_head); 1624 } else if (s->strategy == Z_RLE && s->strstart - hash_head == 1) { 1625 s->match_length = longest_match_fast (s, hash_head); 1626 } 1627 /* longest_match() or longest_match_fast() sets match_start */ 1628 1629 if (s->match_length <= 5 && (s->strategy == Z_FILTERED 1630#if TOO_FAR <= 32767 1631 || (s->match_length == MIN_MATCH && 1632 s->strstart - s->match_start > TOO_FAR) 1633#endif 1634 )) { 1635 1636 /* If prev_match is also MIN_MATCH, match_start is garbage 1637 * but we will ignore the current match anyway. 1638 */ 1639 s->match_length = MIN_MATCH-1; 1640 } 1641 } 1642 /* If there was a match at the previous step and the current 1643 * match is not better, output the previous match: 1644 */ 1645 if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) { 1646 uInt max_insert = s->strstart + s->lookahead - MIN_MATCH; 1647 /* Do not insert strings in hash table beyond this. */ 1648 1649 check_match(s, s->strstart-1, s->prev_match, s->prev_length); 1650 1651 _tr_tally_dist(s, s->strstart -1 - s->prev_match, 1652 s->prev_length - MIN_MATCH, bflush); 1653 1654 /* Insert in hash table all strings up to the end of the match. 1655 * strstart-1 and strstart are already inserted. If there is not 1656 * enough lookahead, the last two strings are not inserted in 1657 * the hash table. 1658 */ 1659 s->lookahead -= s->prev_length-1; 1660 s->prev_length -= 2; 1661 do { 1662 if (++s->strstart <= max_insert) { 1663 INSERT_STRING(s, s->strstart, hash_head); 1664 } 1665 } while (--s->prev_length != 0); 1666 s->match_available = 0; 1667 s->match_length = MIN_MATCH-1; 1668 s->strstart++; 1669 1670 if (bflush) FLUSH_BLOCK(s, 0); 1671 1672 } else if (s->match_available) { 1673 /* If there was no match at the previous position, output a 1674 * single literal. If there was a match but the current match 1675 * is longer, truncate the previous match to a single literal. 1676 */ 1677 Tracevv((stderr,"%c", s->window[s->strstart-1])); 1678 _tr_tally_lit(s, s->window[s->strstart-1], bflush); 1679 if (bflush) { 1680 FLUSH_BLOCK_ONLY(s, 0); 1681 } 1682 s->strstart++; 1683 s->lookahead--; 1684 if (s->strm->avail_out == 0) return need_more; 1685 } else { 1686 /* There is no previous match to compare with, wait for 1687 * the next step to decide. 1688 */ 1689 s->match_available = 1; 1690 s->strstart++; 1691 s->lookahead--; 1692 } 1693 } 1694 if (flush == Z_INSERT_ONLY) { 1695 s->block_start = s->strstart; 1696 return need_more; 1697 } 1698 Assert (flush != Z_NO_FLUSH, "no flush?"); 1699 if (s->match_available) { 1700 Tracevv((stderr,"%c", s->window[s->strstart-1])); 1701 _tr_tally_lit(s, s->window[s->strstart-1], bflush); 1702 s->match_available = 0; 1703 } 1704 FLUSH_BLOCK(s, flush == Z_FINISH); 1705 return flush == Z_FINISH ? finish_done : block_done; 1706} 1707#endif /* FASTEST */ 1708 1709#if 0 1710/* =========================================================================== 1711 * For Z_RLE, simply look for runs of bytes, generate matches only of distance 1712 * one. Do not maintain a hash table. (It will be regenerated if this run of 1713 * deflate switches away from Z_RLE.) 1714 */ 1715local block_state deflate_rle(s, flush) 1716 deflate_state *s; 1717 int flush; 1718{ 1719 int bflush; /* set if current block must be flushed */ 1720 uInt run; /* length of run */ 1721 uInt max; /* maximum length of run */ 1722 uInt prev; /* byte at distance one to match */ 1723 Bytef *scan; /* scan for end of run */ 1724 1725 for (;;) { 1726 /* Make sure that we always have enough lookahead, except 1727 * at the end of the input file. We need MAX_MATCH bytes 1728 * for the longest encodable run. 1729 */ 1730 if (s->lookahead < MAX_MATCH) { 1731 fill_window(s); 1732 if (s->lookahead < MAX_MATCH && flush == Z_NO_FLUSH) { 1733 return need_more; 1734 } 1735 if (s->lookahead == 0) break; /* flush the current block */ 1736 } 1737 1738 /* See how many times the previous byte repeats */ 1739 run = 0; 1740 if (s->strstart > 0) { /* if there is a previous byte, that is */ 1741 max = s->lookahead < MAX_MATCH ? s->lookahead : MAX_MATCH; 1742 scan = s->window + s->strstart - 1; 1743 prev = *scan++; 1744 do { 1745 if (*scan++ != prev) 1746 break; 1747 } while (++run < max); 1748 } 1749 1750 /* Emit match if have run of MIN_MATCH or longer, else emit literal */ 1751 if (run >= MIN_MATCH) { 1752 check_match(s, s->strstart, s->strstart - 1, run); 1753 _tr_tally_dist(s, 1, run - MIN_MATCH, bflush); 1754 s->lookahead -= run; 1755 s->strstart += run; 1756 } else { 1757 /* No match, output a literal byte */ 1758 Tracevv((stderr,"%c", s->window[s->strstart])); 1759 _tr_tally_lit (s, s->window[s->strstart], bflush); 1760 s->lookahead--; 1761 s->strstart++; 1762 } 1763 if (bflush) FLUSH_BLOCK(s, 0); 1764 } 1765 FLUSH_BLOCK(s, flush == Z_FINISH); 1766 return flush == Z_FINISH ? finish_done : block_done; 1767} 1768#endif 1769