1/* deflate.c -- compress data using the deflation algorithm 2 * Copyright (C) 1995-1998 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 ftp://ds.internic.net/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: deflate.c,v 1.1 2001/11/09 01:48:02 mpl Exp $ */ 51 52#include "deflate.h" 53 54const char deflate_copyright[] = 55 " deflate 1.1.3 Copyright 1995-1998 Jean-loup Gailly "; 56/* 57 If you use the zlib library in a product, an acknowledgment is welcome 58 in the documentation of your product. If for some reason you cannot 59 include such an acknowledgment, I would appreciate that you keep this 60 copyright string in the executable of your product. 61 */ 62 63/* =========================================================================== 64 * Function prototypes. 65 */ 66typedef enum { 67 need_more, /* block not completed, need more input or more output */ 68 block_done, /* block flush performed */ 69 finish_started, /* finish started, need only more output at next deflate */ 70 finish_done /* finish done, accept no more input or output */ 71} block_state; 72 73typedef block_state (*compress_func) OF((deflate_state *s, int flush)); 74/* Compression function. Returns the block state after the call. */ 75 76local void fill_window OF((deflate_state *s)); 77local block_state deflate_stored OF((deflate_state *s, int flush)); 78local block_state deflate_fast OF((deflate_state *s, int flush)); 79local block_state deflate_slow OF((deflate_state *s, int flush)); 80local void lm_init OF((deflate_state *s)); 81local void putShortMSB OF((deflate_state *s, uInt b)); 82local void flush_pending OF((z_streamp strm)); 83local int read_buf OF((z_streamp strm, Bytef *buf, unsigned size)); 84#ifdef ASMV 85 void match_init OF((void)); /* asm code initialization */ 86 uInt longest_match OF((deflate_state *s, IPos cur_match)); 87#else 88local uInt longest_match OF((deflate_state *s, IPos cur_match)); 89#endif 90 91#ifdef DEBUG 92local void check_match OF((deflate_state *s, IPos start, IPos match, 93 int length)); 94#endif 95 96/* =========================================================================== 97 * Local data 98 */ 99 100#define NIL 0 101/* Tail of hash chains */ 102 103#ifndef TOO_FAR 104# define TOO_FAR 4096 105#endif 106/* Matches of length 3 are discarded if their distance exceeds TOO_FAR */ 107 108#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1) 109/* Minimum amount of lookahead, except at the end of the input file. 110 * See deflate.c for comments about the MIN_MATCH+1. 111 */ 112 113/* Values for max_lazy_match, good_match and max_chain_length, depending on 114 * the desired pack level (0..9). The values given below have been tuned to 115 * exclude worst case performance for pathological files. Better values may be 116 * found for specific files. 117 */ 118typedef struct config_s { 119 ush good_length; /* reduce lazy search above this match length */ 120 ush max_lazy; /* do not perform lazy search above this match length */ 121 ush nice_length; /* quit search above this match length */ 122 ush max_chain; 123 compress_func func; 124} config; 125 126local const config configuration_table[10] = { 127/* good lazy nice chain */ 128/* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */ 129/* 1 */ {4, 4, 8, 4, deflate_fast}, /* maximum speed, no lazy matches */ 130/* 2 */ {4, 5, 16, 8, deflate_fast}, 131/* 3 */ {4, 6, 32, 32, deflate_fast}, 132 133/* 4 */ {4, 4, 16, 16, deflate_slow}, /* lazy matches */ 134/* 5 */ {8, 16, 32, 32, deflate_slow}, 135/* 6 */ {8, 16, 128, 128, deflate_slow}, 136/* 7 */ {8, 32, 128, 256, deflate_slow}, 137/* 8 */ {32, 128, 258, 1024, deflate_slow}, 138/* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* maximum compression */ 139 140/* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4 141 * For deflate_fast() (levels <= 3) good is ignored and lazy has a different 142 * meaning. 143 */ 144 145#define EQUAL 0 146/* result of memcmp for equal strings */ 147 148struct static_tree_desc_s {int dummy;}; /* for buggy compilers */ 149 150/* =========================================================================== 151 * Update a hash value with the given input byte 152 * IN assertion: all calls to to UPDATE_HASH are made with consecutive 153 * input characters, so that a running hash key can be computed from the 154 * previous key instead of complete recalculation each time. 155 */ 156#define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask) 157 158 159/* =========================================================================== 160 * Insert string str in the dictionary and set match_head to the previous head 161 * of the hash chain (the most recent string with same hash key). Return 162 * the previous length of the hash chain. 163 * If this file is compiled with -DFASTEST, the compression level is forced 164 * to 1, and no hash chains are maintained. 165 * IN assertion: all calls to to INSERT_STRING are made with consecutive 166 * input characters and the first MIN_MATCH bytes of str are valid 167 * (except for the last MIN_MATCH-1 bytes of the input file). 168 */ 169#ifdef FASTEST 170#define INSERT_STRING(s, str, match_head) \ 171 (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \ 172 match_head = s->head[s->ins_h], \ 173 s->head[s->ins_h] = (Pos)(str)) 174#else 175#define INSERT_STRING(s, str, match_head) \ 176 (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \ 177 s->prev[(str) & s->w_mask] = match_head = s->head[s->ins_h], \ 178 s->head[s->ins_h] = (Pos)(str)) 179#endif 180 181/* =========================================================================== 182 * Initialize the hash table (avoiding 64K overflow for 16 bit systems). 183 * prev[] will be initialized on the fly. 184 */ 185#define CLEAR_HASH(s) \ 186 s->head[s->hash_size-1] = NIL; \ 187 zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head)); 188 189/* ========================================================================= */ 190int ZEXPORT deflateInit_(strm, level, version, stream_size) 191 z_streamp strm; 192 int level; 193 const char *version; 194 int stream_size; 195{ 196 return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL, 197 Z_DEFAULT_STRATEGY, version, stream_size); 198 /* To do: ignore strm->next_in if we use it as window */ 199} 200 201/* ========================================================================= */ 202int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy, 203 version, stream_size) 204 z_streamp strm; 205 int level; 206 int method; 207 int windowBits; 208 int memLevel; 209 int strategy; 210 const char *version; 211 int stream_size; 212{ 213 deflate_state *s; 214 int noheader = 0; 215 static const char* my_version = ZLIB_VERSION; 216 217 ushf *overlay; 218 /* We overlay pending_buf and d_buf+l_buf. This works since the average 219 * output size for (length,distance) codes is <= 24 bits. 220 */ 221 222 if (version == Z_NULL || version[0] != my_version[0] || 223 stream_size != sizeof(z_stream)) { 224 return Z_VERSION_ERROR; 225 } 226 if (strm == Z_NULL) return Z_STREAM_ERROR; 227 228 strm->msg = Z_NULL; 229 if (strm->zalloc == Z_NULL) { 230 strm->zalloc = zcalloc; 231 strm->opaque = (voidpf)0; 232 } 233 if (strm->zfree == Z_NULL) strm->zfree = zcfree; 234 235 if (level == Z_DEFAULT_COMPRESSION) level = 6; 236#ifdef FASTEST 237 level = 1; 238#endif 239 240 if (windowBits < 0) { /* undocumented feature: suppress zlib header */ 241 noheader = 1; 242 windowBits = -windowBits; 243 } 244 if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED || 245 windowBits < 8 || windowBits > 15 || level < 0 || level > 9 || 246 strategy < 0 || strategy > Z_HUFFMAN_ONLY) { 247 return Z_STREAM_ERROR; 248 } 249 s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state)); 250 if (s == Z_NULL) return Z_MEM_ERROR; 251 strm->state = (struct internal_state FAR *)s; 252 s->strm = strm; 253 254 s->noheader = noheader; 255 s->w_bits = windowBits; 256 s->w_size = 1 << s->w_bits; 257 s->w_mask = s->w_size - 1; 258 259 s->hash_bits = memLevel + 7; 260 s->hash_size = 1 << s->hash_bits; 261 s->hash_mask = s->hash_size - 1; 262 s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH); 263 264 s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte)); 265 s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos)); 266 s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos)); 267 268 s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */ 269 270 overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2); 271 s->pending_buf = (uchf *) overlay; 272 s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L); 273 274 if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL || 275 s->pending_buf == Z_NULL) { 276 strm->msg = (char*)ERR_MSG(Z_MEM_ERROR); 277 deflateEnd (strm); 278 return Z_MEM_ERROR; 279 } 280 s->d_buf = overlay + s->lit_bufsize/sizeof(ush); 281 s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize; 282 283 s->level = level; 284 s->strategy = strategy; 285 s->method = (Byte)method; 286 287 return deflateReset(strm); 288} 289 290/* ========================================================================= */ 291int ZEXPORT deflateSetDictionary (strm, dictionary, dictLength) 292 z_streamp strm; 293 const Bytef *dictionary; 294 uInt dictLength; 295{ 296 deflate_state *s; 297 uInt length = dictLength; 298 uInt n; 299 IPos hash_head = 0; 300 301 if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL || 302 strm->state->status != INIT_STATE) return Z_STREAM_ERROR; 303 304 s = strm->state; 305 strm->adler = adler32(strm->adler, dictionary, dictLength); 306 307 if (length < MIN_MATCH) return Z_OK; 308 if (length > MAX_DIST(s)) { 309 length = MAX_DIST(s); 310#ifndef USE_DICT_HEAD 311 dictionary += dictLength - length; /* use the tail of the dictionary */ 312#endif 313 } 314 zmemcpy(s->window, dictionary, length); 315 s->strstart = length; 316 s->block_start = (long)length; 317 318 /* Insert all strings in the hash table (except for the last two bytes). 319 * s->lookahead stays null, so s->ins_h will be recomputed at the next 320 * call of fill_window. 321 */ 322 s->ins_h = s->window[0]; 323 UPDATE_HASH(s, s->ins_h, s->window[1]); 324 for (n = 0; n <= length - MIN_MATCH; n++) { 325 INSERT_STRING(s, n, hash_head); 326 } 327 if (hash_head) hash_head = 0; /* to make compiler happy */ 328 return Z_OK; 329} 330 331/* ========================================================================= */ 332int ZEXPORT deflateReset (strm) 333 z_streamp strm; 334{ 335 deflate_state *s; 336 337 if (strm == Z_NULL || strm->state == Z_NULL || 338 strm->zalloc == Z_NULL || strm->zfree == Z_NULL) return Z_STREAM_ERROR; 339 340 strm->total_in = strm->total_out = 0; 341 strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */ 342 strm->data_type = Z_UNKNOWN; 343 344 s = (deflate_state *)strm->state; 345 s->pending = 0; 346 s->pending_out = s->pending_buf; 347 348 if (s->noheader < 0) { 349 s->noheader = 0; /* was set to -1 by deflate(..., Z_FINISH); */ 350 } 351 s->status = s->noheader ? BUSY_STATE : INIT_STATE; 352 strm->adler = 1; 353 s->last_flush = Z_NO_FLUSH; 354 355 _tr_init(s); 356 lm_init(s); 357 358 return Z_OK; 359} 360 361/* ========================================================================= */ 362int ZEXPORT deflateParams(strm, level, strategy) 363 z_streamp strm; 364 int level; 365 int strategy; 366{ 367 deflate_state *s; 368 compress_func func; 369 int err = Z_OK; 370 371 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 372 s = strm->state; 373 374 if (level == Z_DEFAULT_COMPRESSION) { 375 level = 6; 376 } 377 if (level < 0 || level > 9 || strategy < 0 || strategy > Z_HUFFMAN_ONLY) { 378 return Z_STREAM_ERROR; 379 } 380 func = configuration_table[s->level].func; 381 382 if (func != configuration_table[level].func && strm->total_in != 0) { 383 /* Flush the last buffer: */ 384 err = deflate(strm, Z_PARTIAL_FLUSH); 385 } 386 if (s->level != level) { 387 s->level = level; 388 s->max_lazy_match = configuration_table[level].max_lazy; 389 s->good_match = configuration_table[level].good_length; 390 s->nice_match = configuration_table[level].nice_length; 391 s->max_chain_length = configuration_table[level].max_chain; 392 } 393 s->strategy = strategy; 394 return err; 395} 396 397/* ========================================================================= 398 * Put a short in the pending buffer. The 16-bit value is put in MSB order. 399 * IN assertion: the stream state is correct and there is enough room in 400 * pending_buf. 401 */ 402local void putShortMSB (s, b) 403 deflate_state *s; 404 uInt b; 405{ 406 put_byte(s, (Byte)(b >> 8)); 407 put_byte(s, (Byte)(b & 0xff)); 408} 409 410/* ========================================================================= 411 * Flush as much pending output as possible. All deflate() output goes 412 * through this function so some applications may wish to modify it 413 * to avoid allocating a large strm->next_out buffer and copying into it. 414 * (See also read_buf()). 415 */ 416local void flush_pending(strm) 417 z_streamp strm; 418{ 419 unsigned len = strm->state->pending; 420 421 if (len > strm->avail_out) len = strm->avail_out; 422 if (len == 0) return; 423 424 zmemcpy(strm->next_out, strm->state->pending_out, len); 425 strm->next_out += len; 426 strm->state->pending_out += len; 427 strm->total_out += len; 428 strm->avail_out -= len; 429 strm->state->pending -= len; 430 if (strm->state->pending == 0) { 431 strm->state->pending_out = strm->state->pending_buf; 432 } 433} 434 435/* ========================================================================= */ 436int ZEXPORT deflate (strm, flush) 437 z_streamp strm; 438 int flush; 439{ 440 int old_flush; /* value of flush param for previous deflate call */ 441 deflate_state *s; 442 443 if (strm == Z_NULL || strm->state == Z_NULL || 444 flush > Z_FINISH || flush < 0) { 445 return Z_STREAM_ERROR; 446 } 447 s = strm->state; 448 449 if (strm->next_out == Z_NULL || 450 (strm->next_in == Z_NULL && strm->avail_in != 0) || 451 (s->status == FINISH_STATE && flush != Z_FINISH)) { 452 ERR_RETURN(strm, Z_STREAM_ERROR); 453 } 454 if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR); 455 456 s->strm = strm; /* just in case */ 457 old_flush = s->last_flush; 458 s->last_flush = flush; 459 460 /* Write the zlib header */ 461 if (s->status == INIT_STATE) { 462 463 uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8; 464 uInt level_flags = (s->level-1) >> 1; 465 466 if (level_flags > 3) level_flags = 3; 467 header |= (level_flags << 6); 468 if (s->strstart != 0) header |= PRESET_DICT; 469 header += 31 - (header % 31); 470 471 s->status = BUSY_STATE; 472 putShortMSB(s, header); 473 474 /* Save the adler32 of the preset dictionary: */ 475 if (s->strstart != 0) { 476 putShortMSB(s, (uInt)(strm->adler >> 16)); 477 putShortMSB(s, (uInt)(strm->adler & 0xffff)); 478 } 479 strm->adler = 1L; 480 } 481 482 /* Flush as much pending output as possible */ 483 if (s->pending != 0) { 484 flush_pending(strm); 485 if (strm->avail_out == 0) { 486 /* Since avail_out is 0, deflate will be called again with 487 * more output space, but possibly with both pending and 488 * avail_in equal to zero. There won't be anything to do, 489 * but this is not an error situation so make sure we 490 * return OK instead of BUF_ERROR at next call of deflate: 491 */ 492 s->last_flush = -1; 493 return Z_OK; 494 } 495 496 /* Make sure there is something to do and avoid duplicate consecutive 497 * flushes. For repeated and useless calls with Z_FINISH, we keep 498 * returning Z_STREAM_END instead of Z_BUFF_ERROR. 499 */ 500 } else if (strm->avail_in == 0 && flush <= old_flush && 501 flush != Z_FINISH) { 502 ERR_RETURN(strm, Z_BUF_ERROR); 503 } 504 505 /* User must not provide more input after the first FINISH: */ 506 if (s->status == FINISH_STATE && strm->avail_in != 0) { 507 ERR_RETURN(strm, Z_BUF_ERROR); 508 } 509 510 /* Start a new block or continue the current one. 511 */ 512 if (strm->avail_in != 0 || s->lookahead != 0 || 513 (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) { 514 block_state bstate; 515 516 bstate = (*(configuration_table[s->level].func))(s, flush); 517 518 if (bstate == finish_started || bstate == finish_done) { 519 s->status = FINISH_STATE; 520 } 521 if (bstate == need_more || bstate == finish_started) { 522 if (strm->avail_out == 0) { 523 s->last_flush = -1; /* avoid BUF_ERROR next call, see above */ 524 } 525 return Z_OK; 526 /* If flush != Z_NO_FLUSH && avail_out == 0, the next call 527 * of deflate should use the same flush parameter to make sure 528 * that the flush is complete. So we don't have to output an 529 * empty block here, this will be done at next call. This also 530 * ensures that for a very small output buffer, we emit at most 531 * one empty block. 532 */ 533 } 534 if (bstate == block_done) { 535 if (flush == Z_PARTIAL_FLUSH) { 536 _tr_align(s); 537 } else { /* FULL_FLUSH or SYNC_FLUSH */ 538 _tr_stored_block(s, (char*)0, 0L, 0); 539 /* For a full flush, this empty block will be recognized 540 * as a special marker by inflate_sync(). 541 */ 542 if (flush == Z_FULL_FLUSH) { 543 CLEAR_HASH(s); /* forget history */ 544 } 545 } 546 flush_pending(strm); 547 if (strm->avail_out == 0) { 548 s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */ 549 return Z_OK; 550 } 551 } 552 } 553 Assert(strm->avail_out > 0, "bug2"); 554 555 if (flush != Z_FINISH) return Z_OK; 556 if (s->noheader) return Z_STREAM_END; 557 558 /* Write the zlib trailer (adler32) */ 559 putShortMSB(s, (uInt)(strm->adler >> 16)); 560 putShortMSB(s, (uInt)(strm->adler & 0xffff)); 561 flush_pending(strm); 562 /* If avail_out is zero, the application will call deflate again 563 * to flush the rest. 564 */ 565 s->noheader = -1; /* write the trailer only once! */ 566 return s->pending != 0 ? Z_OK : Z_STREAM_END; 567} 568 569/* ========================================================================= */ 570int ZEXPORT deflateEnd (strm) 571 z_streamp strm; 572{ 573 int status; 574 575 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 576 577 status = strm->state->status; 578 if (status != INIT_STATE && status != BUSY_STATE && 579 status != FINISH_STATE) { 580 return Z_STREAM_ERROR; 581 } 582 583 /* Deallocate in reverse order of allocations: */ 584 TRY_FREE(strm, strm->state->pending_buf); 585 TRY_FREE(strm, strm->state->head); 586 TRY_FREE(strm, strm->state->prev); 587 TRY_FREE(strm, strm->state->window); 588 589 ZFREE(strm, strm->state); 590 strm->state = Z_NULL; 591 592 return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK; 593} 594 595/* ========================================================================= 596 * Copy the source state to the destination state. 597 * To simplify the source, this is not supported for 16-bit MSDOS (which 598 * doesn't have enough memory anyway to duplicate compression states). 599 */ 600int ZEXPORT deflateCopy (dest, source) 601 z_streamp dest; 602 z_streamp source; 603{ 604#ifdef MAXSEG_64K 605 return Z_STREAM_ERROR; 606#else 607 deflate_state *ds; 608 deflate_state *ss; 609 ushf *overlay; 610 611 612 if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL) { 613 return Z_STREAM_ERROR; 614 } 615 616 ss = source->state; 617 618 *dest = *source; 619 620 ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state)); 621 if (ds == Z_NULL) return Z_MEM_ERROR; 622 dest->state = (struct internal_state FAR *) ds; 623 *ds = *ss; 624 ds->strm = dest; 625 626 ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte)); 627 ds->prev = (Posf *) ZALLOC(dest, ds->w_size, sizeof(Pos)); 628 ds->head = (Posf *) ZALLOC(dest, ds->hash_size, sizeof(Pos)); 629 overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof(ush)+2); 630 ds->pending_buf = (uchf *) overlay; 631 632 if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL || 633 ds->pending_buf == Z_NULL) { 634 deflateEnd (dest); 635 return Z_MEM_ERROR; 636 } 637 /* following zmemcpy do not work for 16-bit MSDOS */ 638 zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte)); 639 zmemcpy((Bytef *) ds->prev, (const Bytef *) ss->prev, ds->w_size * sizeof(Pos)); 640 zmemcpy((Bytef *) ds->head, (const Bytef *) ss->head, ds->hash_size * sizeof(Pos)); 641 zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size); 642 643 ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf); 644 ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush); 645 ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize; 646 647 ds->l_desc.dyn_tree = ds->dyn_ltree; 648 ds->d_desc.dyn_tree = ds->dyn_dtree; 649 ds->bl_desc.dyn_tree = ds->bl_tree; 650 651 return Z_OK; 652#endif 653} 654 655/* =========================================================================== 656 * Read a new buffer from the current input stream, update the adler32 657 * and total number of bytes read. All deflate() input goes through 658 * this function so some applications may wish to modify it to avoid 659 * allocating a large strm->next_in buffer and copying from it. 660 * (See also flush_pending()). 661 */ 662local int read_buf(strm, buf, size) 663 z_streamp strm; 664 Bytef *buf; 665 unsigned size; 666{ 667 unsigned len = strm->avail_in; 668 669 if (len > size) len = size; 670 if (len == 0) return 0; 671 672 strm->avail_in -= len; 673 674 if (!strm->state->noheader) { 675 strm->adler = adler32(strm->adler, strm->next_in, len); 676 } 677 zmemcpy(buf, strm->next_in, len); 678 strm->next_in += len; 679 strm->total_in += len; 680 681 return (int)len; 682} 683 684/* =========================================================================== 685 * Initialize the "longest match" routines for a new zlib stream 686 */ 687local void lm_init (s) 688 deflate_state *s; 689{ 690 s->window_size = (ulg)2L*s->w_size; 691 692 CLEAR_HASH(s); 693 694 /* Set the default configuration parameters: 695 */ 696 s->max_lazy_match = configuration_table[s->level].max_lazy; 697 s->good_match = configuration_table[s->level].good_length; 698 s->nice_match = configuration_table[s->level].nice_length; 699 s->max_chain_length = configuration_table[s->level].max_chain; 700 701 s->strstart = 0; 702 s->block_start = 0L; 703 s->lookahead = 0; 704 s->match_length = s->prev_length = MIN_MATCH-1; 705 s->match_available = 0; 706 s->ins_h = 0; 707#ifdef ASMV 708 match_init(); /* initialize the asm code */ 709#endif 710} 711 712/* =========================================================================== 713 * Set match_start to the longest match starting at the given string and 714 * return its length. Matches shorter or equal to prev_length are discarded, 715 * in which case the result is equal to prev_length and match_start is 716 * garbage. 717 * IN assertions: cur_match is the head of the hash chain for the current 718 * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1 719 * OUT assertion: the match length is not greater than s->lookahead. 720 */ 721#ifndef ASMV 722/* For 80x86 and 680x0, an optimized version will be provided in match.asm or 723 * match.S. The code will be functionally equivalent. 724 */ 725#ifndef FASTEST 726local uInt longest_match(s, cur_match) 727 deflate_state *s; 728 IPos cur_match; /* current match */ 729{ 730 unsigned chain_length = s->max_chain_length;/* max hash chain length */ 731 register Bytef *scan = s->window + s->strstart; /* current string */ 732 register Bytef *match; /* matched string */ 733 register int len; /* length of current match */ 734 int best_len = s->prev_length; /* best match length so far */ 735 int nice_match = s->nice_match; /* stop if match long enough */ 736 IPos limit = s->strstart > (IPos)MAX_DIST(s) ? 737 s->strstart - (IPos)MAX_DIST(s) : NIL; 738 /* Stop when cur_match becomes <= limit. To simplify the code, 739 * we prevent matches with the string of window index 0. 740 */ 741 Posf *prev = s->prev; 742 uInt wmask = s->w_mask; 743 744#ifdef UNALIGNED_OK 745 /* Compare two bytes at a time. Note: this is not always beneficial. 746 * Try with and without -DUNALIGNED_OK to check. 747 */ 748 register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1; 749 register ush scan_start = *(ushf*)scan; 750 register ush scan_end = *(ushf*)(scan+best_len-1); 751#else 752 register Bytef *strend = s->window + s->strstart + MAX_MATCH; 753 register Byte scan_end1 = scan[best_len-1]; 754 register Byte scan_end = scan[best_len]; 755#endif 756 757 /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. 758 * It is easy to get rid of this optimization if necessary. 759 */ 760 Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever"); 761 762 /* Do not waste too much time if we already have a good match: */ 763 if (s->prev_length >= s->good_match) { 764 chain_length >>= 2; 765 } 766 /* Do not look for matches beyond the end of the input. This is necessary 767 * to make deflate deterministic. 768 */ 769 if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead; 770 771 Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead"); 772 773 do { 774 Assert(cur_match < s->strstart, "no future"); 775 match = s->window + cur_match; 776 777 /* Skip to next match if the match length cannot increase 778 * or if the match length is less than 2: 779 */ 780#if (defined(UNALIGNED_OK) && MAX_MATCH == 258) 781 /* This code assumes sizeof(unsigned short) == 2. Do not use 782 * UNALIGNED_OK if your compiler uses a different size. 783 */ 784 if (*(ushf*)(match+best_len-1) != scan_end || 785 *(ushf*)match != scan_start) continue; 786 787 /* It is not necessary to compare scan[2] and match[2] since they are 788 * always equal when the other bytes match, given that the hash keys 789 * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at 790 * strstart+3, +5, ... up to strstart+257. We check for insufficient 791 * lookahead only every 4th comparison; the 128th check will be made 792 * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is 793 * necessary to put more guard bytes at the end of the window, or 794 * to check more often for insufficient lookahead. 795 */ 796 Assert(scan[2] == match[2], "scan[2]?"); 797 scan++, match++; 798 do { 799 } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) && 800 *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 801 *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 802 *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 803 scan < strend); 804 /* The funny "do {}" generates better code on most compilers */ 805 806 /* Here, scan <= window+strstart+257 */ 807 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 808 if (*scan == *match) scan++; 809 810 len = (MAX_MATCH - 1) - (int)(strend-scan); 811 scan = strend - (MAX_MATCH-1); 812 813#else /* UNALIGNED_OK */ 814 815 if (match[best_len] != scan_end || 816 match[best_len-1] != scan_end1 || 817 *match != *scan || 818 *++match != scan[1]) continue; 819 820 /* The check at best_len-1 can be removed because it will be made 821 * again later. (This heuristic is not always a win.) 822 * It is not necessary to compare scan[2] and match[2] since they 823 * are always equal when the other bytes match, given that 824 * the hash keys are equal and that HASH_BITS >= 8. 825 */ 826 scan += 2, match++; 827 Assert(*scan == *match, "match[2]?"); 828 829 /* We check for insufficient lookahead only every 8th comparison; 830 * the 256th check will be made at strstart+258. 831 */ 832 do { 833 } while (*++scan == *++match && *++scan == *++match && 834 *++scan == *++match && *++scan == *++match && 835 *++scan == *++match && *++scan == *++match && 836 *++scan == *++match && *++scan == *++match && 837 scan < strend); 838 839 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 840 841 len = MAX_MATCH - (int)(strend - scan); 842 scan = strend - MAX_MATCH; 843 844#endif /* UNALIGNED_OK */ 845 846 if (len > best_len) { 847 s->match_start = cur_match; 848 best_len = len; 849 if (len >= nice_match) break; 850#ifdef UNALIGNED_OK 851 scan_end = *(ushf*)(scan+best_len-1); 852#else 853 scan_end1 = scan[best_len-1]; 854 scan_end = scan[best_len]; 855#endif 856 } 857 } while ((cur_match = prev[cur_match & wmask]) > limit 858 && --chain_length != 0); 859 860 if ((uInt)best_len <= s->lookahead) return (uInt)best_len; 861 return s->lookahead; 862} 863 864#else /* FASTEST */ 865/* --------------------------------------------------------------------------- 866 * Optimized version for level == 1 only 867 */ 868local uInt longest_match(s, cur_match) 869 deflate_state *s; 870 IPos cur_match; /* current match */ 871{ 872 register Bytef *scan = s->window + s->strstart; /* current string */ 873 register Bytef *match; /* matched string */ 874 register int len; /* length of current match */ 875 register Bytef *strend = s->window + s->strstart + MAX_MATCH; 876 877 /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. 878 * It is easy to get rid of this optimization if necessary. 879 */ 880 Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever"); 881 882 Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead"); 883 884 Assert(cur_match < s->strstart, "no future"); 885 886 match = s->window + cur_match; 887 888 /* Return failure if the match length is less than 2: 889 */ 890 if (match[0] != scan[0] || match[1] != scan[1]) return MIN_MATCH-1; 891 892 /* The check at best_len-1 can be removed because it will be made 893 * again later. (This heuristic is not always a win.) 894 * It is not necessary to compare scan[2] and match[2] since they 895 * are always equal when the other bytes match, given that 896 * the hash keys are equal and that HASH_BITS >= 8. 897 */ 898 scan += 2, match += 2; 899 Assert(*scan == *match, "match[2]?"); 900 901 /* We check for insufficient lookahead only every 8th comparison; 902 * the 256th check will be made at strstart+258. 903 */ 904 do { 905 } while (*++scan == *++match && *++scan == *++match && 906 *++scan == *++match && *++scan == *++match && 907 *++scan == *++match && *++scan == *++match && 908 *++scan == *++match && *++scan == *++match && 909 scan < strend); 910 911 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 912 913 len = MAX_MATCH - (int)(strend - scan); 914 915 if (len < MIN_MATCH) return MIN_MATCH - 1; 916 917 s->match_start = cur_match; 918 return len <= s->lookahead ? len : s->lookahead; 919} 920#endif /* FASTEST */ 921#endif /* ASMV */ 922 923#ifdef DEBUG 924/* =========================================================================== 925 * Check that the match at match_start is indeed a match. 926 */ 927local void check_match(s, start, match, length) 928 deflate_state *s; 929 IPos start, match; 930 int length; 931{ 932 /* check that the match is indeed a match */ 933 if (zmemcmp(s->window + match, 934 s->window + start, length) != EQUAL) { 935 fprintf(stderr, " start %u, match %u, length %d\n", 936 start, match, length); 937 do { 938 fprintf(stderr, "%c%c", s->window[match++], s->window[start++]); 939 } while (--length != 0); 940 z_error("invalid match"); 941 } 942 if (z_verbose > 1) { 943 fprintf(stderr,"\\[%d,%d]", start-match, length); 944 do { putc(s->window[start++], stderr); } while (--length != 0); 945 } 946} 947#else 948# define check_match(s, start, match, length) 949#endif 950 951/* =========================================================================== 952 * Fill the window when the lookahead becomes insufficient. 953 * Updates strstart and lookahead. 954 * 955 * IN assertion: lookahead < MIN_LOOKAHEAD 956 * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD 957 * At least one byte has been read, or avail_in == 0; reads are 958 * performed for at least two bytes (required for the zip translate_eol 959 * option -- not supported here). 960 */ 961local void fill_window(s) 962 deflate_state *s; 963{ 964 register unsigned n, m; 965 register Posf *p; 966 unsigned more; /* Amount of free space at the end of the window. */ 967 uInt wsize = s->w_size; 968 969 do { 970 more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart); 971 972 /* Deal with !@#$% 64K limit: */ 973 if (more == 0 && s->strstart == 0 && s->lookahead == 0) { 974 more = wsize; 975 976 } else if (more == (unsigned)(-1)) { 977 /* Very unlikely, but possible on 16 bit machine if strstart == 0 978 * and lookahead == 1 (input done one byte at time) 979 */ 980 more--; 981 982 /* If the window is almost full and there is insufficient lookahead, 983 * move the upper half to the lower one to make room in the upper half. 984 */ 985 } else if (s->strstart >= wsize+MAX_DIST(s)) { 986 987 zmemcpy(s->window, s->window+wsize, (unsigned)wsize); 988 s->match_start -= wsize; 989 s->strstart -= wsize; /* we now have strstart >= MAX_DIST */ 990 s->block_start -= (long) wsize; 991 992 /* Slide the hash table (could be avoided with 32 bit values 993 at the expense of memory usage). We slide even when level == 0 994 to keep the hash table consistent if we switch back to level > 0 995 later. (Using level 0 permanently is not an optimal usage of 996 zlib, so we don't care about this pathological case.) 997 */ 998 n = s->hash_size; 999 p = &s->head[n]; 1000 do { 1001 m = *--p; 1002 *p = (Pos)(m >= wsize ? m-wsize : NIL); 1003 } while (--n); 1004 1005 n = wsize; 1006#ifndef FASTEST 1007 p = &s->prev[n]; 1008 do { 1009 m = *--p; 1010 *p = (Pos)(m >= wsize ? m-wsize : NIL); 1011 /* If n is not on any hash chain, prev[n] is garbage but 1012 * its value will never be used. 1013 */ 1014 } while (--n); 1015#endif 1016 more += wsize; 1017 } 1018 if (s->strm->avail_in == 0) return; 1019 1020 /* If there was no sliding: 1021 * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 && 1022 * more == window_size - lookahead - strstart 1023 * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1) 1024 * => more >= window_size - 2*WSIZE + 2 1025 * In the BIG_MEM or MMAP case (not yet supported), 1026 * window_size == input_size + MIN_LOOKAHEAD && 1027 * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD. 1028 * Otherwise, window_size == 2*WSIZE so more >= 2. 1029 * If there was sliding, more >= WSIZE. So in all cases, more >= 2. 1030 */ 1031 Assert(more >= 2, "more < 2"); 1032 1033 n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more); 1034 s->lookahead += n; 1035 1036 /* Initialize the hash value now that we have some input: */ 1037 if (s->lookahead >= MIN_MATCH) { 1038 s->ins_h = s->window[s->strstart]; 1039 UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]); 1040#if MIN_MATCH != 3 1041 Call UPDATE_HASH() MIN_MATCH-3 more times 1042#endif 1043 } 1044 /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage, 1045 * but this is not important since only literal bytes will be emitted. 1046 */ 1047 1048 } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0); 1049} 1050 1051/* =========================================================================== 1052 * Flush the current block, with given end-of-file flag. 1053 * IN assertion: strstart is set to the end of the current match. 1054 */ 1055#define FLUSH_BLOCK_ONLY(s, eof) { \ 1056 _tr_flush_block(s, (s->block_start >= 0L ? \ 1057 (charf *)&s->window[(unsigned)s->block_start] : \ 1058 (charf *)Z_NULL), \ 1059 (ulg)((long)s->strstart - s->block_start), \ 1060 (eof)); \ 1061 s->block_start = s->strstart; \ 1062 flush_pending(s->strm); \ 1063 Tracev((stderr,"[FLUSH]")); \ 1064} 1065 1066/* Same but force premature exit if necessary. */ 1067#define FLUSH_BLOCK(s, eof) { \ 1068 FLUSH_BLOCK_ONLY(s, eof); \ 1069 if (s->strm->avail_out == 0) return (eof) ? finish_started : need_more; \ 1070} 1071 1072/* =========================================================================== 1073 * Copy without compression as much as possible from the input stream, return 1074 * the current block state. 1075 * This function does not insert new strings in the dictionary since 1076 * uncompressible data is probably not useful. This function is used 1077 * only for the level=0 compression option. 1078 * NOTE: this function should be optimized to avoid extra copying from 1079 * window to pending_buf. 1080 */ 1081local block_state deflate_stored(s, flush) 1082 deflate_state *s; 1083 int flush; 1084{ 1085 /* Stored blocks are limited to 0xffff bytes, pending_buf is limited 1086 * to pending_buf_size, and each stored block has a 5 byte header: 1087 */ 1088 ulg max_block_size = 0xffff; 1089 ulg max_start; 1090 1091 if (max_block_size > s->pending_buf_size - 5) { 1092 max_block_size = s->pending_buf_size - 5; 1093 } 1094 1095 /* Copy as much as possible from input to output: */ 1096 for (;;) { 1097 /* Fill the window as much as possible: */ 1098 if (s->lookahead <= 1) { 1099 1100 Assert(s->strstart < s->w_size+MAX_DIST(s) || 1101 s->block_start >= (long)s->w_size, "slide too late"); 1102 1103 fill_window(s); 1104 if (s->lookahead == 0 && flush == Z_NO_FLUSH) return need_more; 1105 1106 if (s->lookahead == 0) break; /* flush the current block */ 1107 } 1108 Assert(s->block_start >= 0L, "block gone"); 1109 1110 s->strstart += s->lookahead; 1111 s->lookahead = 0; 1112 1113 /* Emit a stored block if pending_buf will be full: */ 1114 max_start = s->block_start + max_block_size; 1115 if (s->strstart == 0 || (ulg)s->strstart >= max_start) { 1116 /* strstart == 0 is possible when wraparound on 16-bit machine */ 1117 s->lookahead = (uInt)(s->strstart - max_start); 1118 s->strstart = (uInt)max_start; 1119 FLUSH_BLOCK(s, 0); 1120 } 1121 /* Flush if we may have to slide, otherwise block_start may become 1122 * negative and the data will be gone: 1123 */ 1124 if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) { 1125 FLUSH_BLOCK(s, 0); 1126 } 1127 } 1128 FLUSH_BLOCK(s, flush == Z_FINISH); 1129 return flush == Z_FINISH ? finish_done : block_done; 1130} 1131 1132/* =========================================================================== 1133 * Compress as much as possible from the input stream, return the current 1134 * block state. 1135 * This function does not perform lazy evaluation of matches and inserts 1136 * new strings in the dictionary only for unmatched strings or for short 1137 * matches. It is used only for the fast compression options. 1138 */ 1139local block_state deflate_fast(s, flush) 1140 deflate_state *s; 1141 int flush; 1142{ 1143 IPos hash_head = NIL; /* head of the hash chain */ 1144 int bflush; /* set if current block must be flushed */ 1145 1146 for (;;) { 1147 /* Make sure that we always have enough lookahead, except 1148 * at the end of the input file. We need MAX_MATCH bytes 1149 * for the next match, plus MIN_MATCH bytes to insert the 1150 * string following the next match. 1151 */ 1152 if (s->lookahead < MIN_LOOKAHEAD) { 1153 fill_window(s); 1154 if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { 1155 return need_more; 1156 } 1157 if (s->lookahead == 0) break; /* flush the current block */ 1158 } 1159 1160 /* Insert the string window[strstart .. strstart+2] in the 1161 * dictionary, and set hash_head to the head of the hash chain: 1162 */ 1163 if (s->lookahead >= MIN_MATCH) { 1164 INSERT_STRING(s, s->strstart, hash_head); 1165 } 1166 1167 /* Find the longest match, discarding those <= prev_length. 1168 * At this point we have always match_length < MIN_MATCH 1169 */ 1170 if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) { 1171 /* To simplify the code, we prevent matches with the string 1172 * of window index 0 (in particular we have to avoid a match 1173 * of the string with itself at the start of the input file). 1174 */ 1175 if (s->strategy != Z_HUFFMAN_ONLY) { 1176 s->match_length = longest_match (s, hash_head); 1177 } 1178 /* longest_match() sets match_start */ 1179 } 1180 if (s->match_length >= MIN_MATCH) { 1181 check_match(s, s->strstart, s->match_start, s->match_length); 1182 1183 _tr_tally_dist(s, s->strstart - s->match_start, 1184 s->match_length - MIN_MATCH, bflush); 1185 1186 s->lookahead -= s->match_length; 1187 1188 /* Insert new strings in the hash table only if the match length 1189 * is not too large. This saves time but degrades compression. 1190 */ 1191#ifndef FASTEST 1192 if (s->match_length <= s->max_insert_length && 1193 s->lookahead >= MIN_MATCH) { 1194 s->match_length--; /* string at strstart already in hash table */ 1195 do { 1196 s->strstart++; 1197 INSERT_STRING(s, s->strstart, hash_head); 1198 /* strstart never exceeds WSIZE-MAX_MATCH, so there are 1199 * always MIN_MATCH bytes ahead. 1200 */ 1201 } while (--s->match_length != 0); 1202 s->strstart++; 1203 } else 1204#endif 1205 { 1206 s->strstart += s->match_length; 1207 s->match_length = 0; 1208 s->ins_h = s->window[s->strstart]; 1209 UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]); 1210#if MIN_MATCH != 3 1211 Call UPDATE_HASH() MIN_MATCH-3 more times 1212#endif 1213 /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not 1214 * matter since it will be recomputed at next deflate call. 1215 */ 1216 } 1217 } else { 1218 /* No match, output a literal byte */ 1219 Tracevv((stderr,"%c", s->window[s->strstart])); 1220 _tr_tally_lit (s, s->window[s->strstart], bflush); 1221 s->lookahead--; 1222 s->strstart++; 1223 } 1224 if (bflush) FLUSH_BLOCK(s, 0); 1225 } 1226 FLUSH_BLOCK(s, flush == Z_FINISH); 1227 return flush == Z_FINISH ? finish_done : block_done; 1228} 1229 1230/* =========================================================================== 1231 * Same as above, but achieves better compression. We use a lazy 1232 * evaluation for matches: a match is finally adopted only if there is 1233 * no better match at the next window position. 1234 */ 1235local block_state deflate_slow(s, flush) 1236 deflate_state *s; 1237 int flush; 1238{ 1239 IPos hash_head = NIL; /* head of hash chain */ 1240 int bflush; /* set if current block must be flushed */ 1241 1242 /* Process the input block. */ 1243 for (;;) { 1244 /* Make sure that we always have enough lookahead, except 1245 * at the end of the input file. We need MAX_MATCH bytes 1246 * for the next match, plus MIN_MATCH bytes to insert the 1247 * string following the next match. 1248 */ 1249 if (s->lookahead < MIN_LOOKAHEAD) { 1250 fill_window(s); 1251 if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { 1252 return need_more; 1253 } 1254 if (s->lookahead == 0) break; /* flush the current block */ 1255 } 1256 1257 /* Insert the string window[strstart .. strstart+2] in the 1258 * dictionary, and set hash_head to the head of the hash chain: 1259 */ 1260 if (s->lookahead >= MIN_MATCH) { 1261 INSERT_STRING(s, s->strstart, hash_head); 1262 } 1263 1264 /* Find the longest match, discarding those <= prev_length. 1265 */ 1266 s->prev_length = s->match_length, s->prev_match = s->match_start; 1267 s->match_length = MIN_MATCH-1; 1268 1269 if (hash_head != NIL && s->prev_length < s->max_lazy_match && 1270 s->strstart - hash_head <= MAX_DIST(s)) { 1271 /* To simplify the code, we prevent matches with the string 1272 * of window index 0 (in particular we have to avoid a match 1273 * of the string with itself at the start of the input file). 1274 */ 1275 if (s->strategy != Z_HUFFMAN_ONLY) { 1276 s->match_length = longest_match (s, hash_head); 1277 } 1278 /* longest_match() sets match_start */ 1279 1280 if (s->match_length <= 5 && (s->strategy == Z_FILTERED || 1281 (s->match_length == MIN_MATCH && 1282 s->strstart - s->match_start > TOO_FAR))) { 1283 1284 /* If prev_match is also MIN_MATCH, match_start is garbage 1285 * but we will ignore the current match anyway. 1286 */ 1287 s->match_length = MIN_MATCH-1; 1288 } 1289 } 1290 /* If there was a match at the previous step and the current 1291 * match is not better, output the previous match: 1292 */ 1293 if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) { 1294 uInt max_insert = s->strstart + s->lookahead - MIN_MATCH; 1295 /* Do not insert strings in hash table beyond this. */ 1296 1297 check_match(s, s->strstart-1, s->prev_match, s->prev_length); 1298 1299 _tr_tally_dist(s, s->strstart -1 - s->prev_match, 1300 s->prev_length - MIN_MATCH, bflush); 1301 1302 /* Insert in hash table all strings up to the end of the match. 1303 * strstart-1 and strstart are already inserted. If there is not 1304 * enough lookahead, the last two strings are not inserted in 1305 * the hash table. 1306 */ 1307 s->lookahead -= s->prev_length-1; 1308 s->prev_length -= 2; 1309 do { 1310 if (++s->strstart <= max_insert) { 1311 INSERT_STRING(s, s->strstart, hash_head); 1312 } 1313 } while (--s->prev_length != 0); 1314 s->match_available = 0; 1315 s->match_length = MIN_MATCH-1; 1316 s->strstart++; 1317 1318 if (bflush) FLUSH_BLOCK(s, 0); 1319 1320 } else if (s->match_available) { 1321 /* If there was no match at the previous position, output a 1322 * single literal. If there was a match but the current match 1323 * is longer, truncate the previous match to a single literal. 1324 */ 1325 Tracevv((stderr,"%c", s->window[s->strstart-1])); 1326 _tr_tally_lit(s, s->window[s->strstart-1], bflush); 1327 if (bflush) { 1328 FLUSH_BLOCK_ONLY(s, 0); 1329 } 1330 s->strstart++; 1331 s->lookahead--; 1332 if (s->strm->avail_out == 0) return need_more; 1333 } else { 1334 /* There is no previous match to compare with, wait for 1335 * the next step to decide. 1336 */ 1337 s->match_available = 1; 1338 s->strstart++; 1339 s->lookahead--; 1340 } 1341 } 1342 Assert (flush != Z_NO_FLUSH, "no flush?"); 1343 if (s->match_available) { 1344 Tracevv((stderr,"%c", s->window[s->strstart-1])); 1345 _tr_tally_lit(s, s->window[s->strstart-1], bflush); 1346 s->match_available = 0; 1347 } 1348 FLUSH_BLOCK(s, flush == Z_FINISH); 1349 return flush == Z_FINISH ? finish_done : block_done; 1350} 1351