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