Geant4 Cross Reference |
1 /* deflate.c -- compress data using the deflat 1 2 * Copyright (C) 1995-2022 Jean-loup Gailly an 3 * For conditions of distribution and use, see 4 */ 5 6 /* 7 * ALGORITHM 8 * 9 * The "deflation" process depends on bei 10 * of the input text which are identical 11 * sliding window trailing behind the inp 12 * 13 * The most straightforward technique tur 14 * most input files: try all possible mat 15 * The key feature of this algorithm is t 16 * dictionary are very simple and thus fa 17 * completely. Insertions are performed a 18 * string matches are performed only when 19 * is preferable to spend more time in ma 20 * insertions and avoid deletions. The ma 21 * strings is inspired from that of Rabin 22 * is used to find longer strings when a 23 * A similar algorithm is used in comic ( 24 * (by Leonid Broukhis). 25 * A previous version of this file use 26 * (by Fiala and Greene) which is guarant 27 * time, but has a larger average cost, u 28 * However the F&G algorithm may be faste 29 * files if the parameter max_chain_lengt 30 * 31 * ACKNOWLEDGEMENTS 32 * 33 * The idea of lazy evaluation of matches 34 * I found it in 'freeze' written by Leon 35 * Thanks to many people for bug reports 36 * 37 * REFERENCES 38 * 39 * Deutsch, L.P.,"DEFLATE Compressed Data 40 * Available in http://tools.ietf.org/htm 41 * 42 * A description of the Rabin and Karp al 43 * "Algorithms" by R. Sedgewick, Addis 44 * 45 * Fiala,E.R., and Greene,D.H. 46 * Data Compression with Finite Window 47 * 48 */ 49 50 /* @(#) $Id$ */ 51 52 #include "deflate.h" 53 54 const char deflate_copyright[] = 55 " deflate 1.2.13 Copyright 1995-2022 Jean-l 56 /* 57 If you use the zlib library in a product, an 58 in the documentation of your product. If for 59 include such an acknowledgment, I would appr 60 copyright string in the executable of your p 61 */ 62 63 /* =========================================== 64 * Function prototypes. 65 */ 66 typedef enum { 67 need_more, /* block not completed, ne 68 block_done, /* block flush performed * 69 finish_started, /* finish started, need on 70 finish_done /* finish done, accept no 71 } block_state; 72 73 typedef block_state (*compress_func) OF((defla 74 /* Compression function. Returns the block sta 75 76 local int deflateStateCheck OF((z_streamp 77 local void slide_hash OF((deflate_state *s 78 local void fill_window OF((deflate_state *s 79 local block_state deflate_stored OF((deflate_s 80 local block_state deflate_fast OF((deflate_s 81 #ifndef FASTEST 82 local block_state deflate_slow OF((deflate_s 83 #endif 84 local block_state deflate_rle OF((deflate_s 85 local block_state deflate_huff OF((deflate_s 86 local void lm_init OF((deflate_state *s 87 local void putShortMSB OF((deflate_state *s 88 local void flush_pending OF((z_streamp strm)) 89 local unsigned read_buf OF((z_streamp strm, 90 local uInt longest_match OF((deflate_state *s 91 92 #ifdef ZLIB_DEBUG 93 local void check_match OF((deflate_state *s, 94 int length)); 95 #endif 96 97 /* =========================================== 98 * Local data 99 */ 100 101 #define NIL 0 102 /* Tail of hash chains */ 103 104 #ifndef TOO_FAR 105 # define TOO_FAR 4096 106 #endif 107 /* Matches of length 3 are discarded if their 108 109 /* Values for max_lazy_match, good_match and m 110 * the desired pack level (0..9). The values g 111 * exclude worst case performance for patholog 112 * found for specific files. 113 */ 114 typedef struct config_s { 115 ush good_length; /* reduce lazy search abov 116 ush max_lazy; /* do not perform lazy sea 117 ush nice_length; /* quit search above this 118 ush max_chain; 119 compress_func func; 120 } config; 121 122 #ifdef FASTEST 123 local const config configuration_table[2] = { 124 /* good lazy nice chain */ 125 /* 0 */ {0, 0, 0, 0, deflate_stored}, 126 /* 1 */ {4, 4, 8, 4, deflate_fast}}; /* 127 #else 128 local const config configuration_table[10] = { 129 /* good lazy nice chain */ 130 /* 0 */ {0, 0, 0, 0, deflate_stored}, 131 /* 1 */ {4, 4, 8, 4, deflate_fast}, /* 132 /* 2 */ {4, 5, 16, 8, deflate_fast}, 133 /* 3 */ {4, 6, 32, 32, deflate_fast}, 134 135 /* 4 */ {4, 4, 16, 16, deflate_slow}, /* 136 /* 5 */ {8, 16, 32, 32, deflate_slow}, 137 /* 6 */ {8, 16, 128, 128, deflate_slow}, 138 /* 7 */ {8, 32, 128, 256, deflate_slow}, 139 /* 8 */ {32, 128, 258, 1024, deflate_slow}, 140 /* 9 */ {32, 258, 258, 4096, deflate_slow}}; / 141 #endif 142 143 /* Note: the deflate() code requires max_lazy 144 * For deflate_fast() (levels <= 3) good is ig 145 * meaning. 146 */ 147 148 /* rank Z_BLOCK between Z_NO_FLUSH and Z_PARTI 149 #define RANK(f) (((f) * 2) - ((f) > 4 ? 9 : 0) 150 151 /* =========================================== 152 * Update a hash value with the given input by 153 * IN assertion: all calls to UPDATE_HASH are 154 * characters, so that a running hash key c 155 * key instead of complete recalculation ea 156 */ 157 #define UPDATE_HASH(s,h,c) (h = (((h) << s->ha 158 159 160 /* =========================================== 161 * Insert string str in the dictionary and set 162 * of the hash chain (the most recent string w 163 * the previous length of the hash chain. 164 * If this file is compiled with -DFASTEST, th 165 * to 1, and no hash chains are maintained. 166 * IN assertion: all calls to INSERT_STRING a 167 * characters and the first MIN_MATCH bytes 168 * the last MIN_MATCH-1 bytes of the input 169 */ 170 #ifdef FASTEST 171 #define INSERT_STRING(s, str, match_head) \ 172 (UPDATE_HASH(s, s->ins_h, s->window[(str) + 173 match_head = s->head[s->ins_h], \ 174 s->head[s->ins_h] = (Pos)(str)) 175 #else 176 #define INSERT_STRING(s, str, match_head) \ 177 (UPDATE_HASH(s, s->ins_h, s->window[(str) + 178 match_head = s->prev[(str) & s->w_mask] = 179 s->head[s->ins_h] = (Pos)(str)) 180 #endif 181 182 /* =========================================== 183 * Initialize the hash table (avoiding 64K ove 184 * prev[] will be initialized on the fly. 185 */ 186 #define CLEAR_HASH(s) \ 187 do { \ 188 s->head[s->hash_size - 1] = NIL; \ 189 zmemzero((Bytef *)s->head, \ 190 (unsigned)(s->hash_size - 1)* 191 } while (0) 192 193 /* =========================================== 194 * Slide the hash table when sliding the windo 195 * bit values at the expense of memory usage). 196 * keep the hash table consistent if we switch 197 */ 198 local void slide_hash(s) 199 deflate_state *s; 200 { 201 unsigned n, m; 202 Posf *p; 203 uInt wsize = s->w_size; 204 205 n = s->hash_size; 206 p = &s->head[n]; 207 do { 208 m = *--p; 209 *p = (Pos)(m >= wsize ? m - wsize : NI 210 } while (--n); 211 n = wsize; 212 #ifndef FASTEST 213 p = &s->prev[n]; 214 do { 215 m = *--p; 216 *p = (Pos)(m >= wsize ? m - wsize : NI 217 /* If n is not on any hash chain, prev 218 * its value will never be used. 219 */ 220 } while (--n); 221 #endif 222 } 223 224 /* =========================================== 225 int ZEXPORT deflateInit_(strm, level, version, 226 z_streamp strm; 227 int level; 228 const char *version; 229 int stream_size; 230 { 231 return deflateInit2_(strm, level, Z_DEFLAT 232 Z_DEFAULT_STRATEGY, v 233 /* To do: ignore strm->next_in if we use i 234 } 235 236 /* =========================================== 237 int ZEXPORT deflateInit2_(strm, level, method, 238 version, stream_size) 239 z_streamp strm; 240 int level; 241 int method; 242 int windowBits; 243 int memLevel; 244 int strategy; 245 const char *version; 246 int stream_size; 247 { 248 deflate_state *s; 249 int wrap = 1; 250 static const char my_version[] = ZLIB_VERS 251 252 if (version == Z_NULL || version[0] != my_ 253 stream_size != sizeof(z_stream)) { 254 return Z_VERSION_ERROR; 255 } 256 if (strm == Z_NULL) return Z_STREAM_ERROR; 257 258 strm->msg = Z_NULL; 259 if (strm->zalloc == (alloc_func)0) { 260 #ifdef Z_SOLO 261 return Z_STREAM_ERROR; 262 #else 263 strm->zalloc = zcalloc; 264 strm->opaque = (voidpf)0; 265 #endif 266 } 267 if (strm->zfree == (free_func)0) 268 #ifdef Z_SOLO 269 return Z_STREAM_ERROR; 270 #else 271 strm->zfree = zcfree; 272 #endif 273 274 #ifdef FASTEST 275 if (level != 0) level = 1; 276 #else 277 if (level == Z_DEFAULT_COMPRESSION) level 278 #endif 279 280 if (windowBits < 0) { /* suppress zlib wra 281 wrap = 0; 282 if (windowBits < -15) 283 return Z_STREAM_ERROR; 284 windowBits = -windowBits; 285 } 286 #ifdef GZIP 287 else if (windowBits > 15) { 288 wrap = 2; /* write gzip wrapper 289 windowBits -= 16; 290 } 291 #endif 292 if (memLevel < 1 || memLevel > MAX_MEM_LEV 293 windowBits < 8 || windowBits > 15 || l 294 strategy < 0 || strategy > Z_FIXED || 295 return Z_STREAM_ERROR; 296 } 297 if (windowBits == 8) windowBits = 9; /* u 298 s = (deflate_state *) ZALLOC(strm, 1, size 299 if (s == Z_NULL) return Z_MEM_ERROR; 300 strm->state = (struct internal_state FAR * 301 s->strm = strm; 302 s->status = INIT_STATE; /* to pass sta 303 304 s->wrap = wrap; 305 s->gzhead = Z_NULL; 306 s->w_bits = (uInt)windowBits; 307 s->w_size = 1 << s->w_bits; 308 s->w_mask = s->w_size - 1; 309 310 s->hash_bits = (uInt)memLevel + 7; 311 s->hash_size = 1 << s->hash_bits; 312 s->hash_mask = s->hash_size - 1; 313 s->hash_shift = ((s->hash_bits + MIN_MATC 314 315 s->window = (Bytef *) ZALLOC(strm, s->w_si 316 s->prev = (Posf *) ZALLOC(strm, s->w_si 317 /* Avoid use of uninitialized value, see: 318 * https://bugs.chromium.org/p/oss-fuzz/is 319 */ 320 zmemzero(s->prev, s->w_size * sizeof(Pos)) 321 s->head = (Posf *) ZALLOC(strm, s->hash 322 323 s->high_water = 0; /* nothing written 324 325 s->lit_bufsize = 1 << (memLevel + 6); /* 1 326 327 /* We overlay pending_buf and sym_buf. Thi 328 * for length/distance pairs over any comp 329 * bits or less. 330 * 331 * Analysis: The longest fixed codes are a 332 * extra bits, for lengths 131 to 257. The 333 * 5 bits plus 13 extra bits, for distance 334 * possible fixed-codes length/distance pa 335 * 336 * sym_buf starts one-fourth of the way in 337 * three bytes in sym_buf for every four b 338 * in sym_buf is three bytes -- two for th 339 * literal/length. As each symbol is consu 340 * sym_buf value to read moves forward thr 341 * 31 bits are written to pending_buf. The 342 * bits gets to the next sym_buf symbol to 343 * code is written. At that time, 31*(n - 344 * after 24*(n - 2) bits have been consume 345 * 8*n bits into pending_buf. (Note that t 346 * symbols are written.) The closest the w 347 * then n + 14 bits. Here n is lit_bufsize 348 * can range from 128 to 32768. 349 * 350 * Therefore, at a minimum, there are 142 351 * written and what is read in the overlai 352 * be overwritten by the compressed data. 353 * due to the three-bit fixed-code block h 354 * 355 * That covers the case where either Z_FIX 356 * codes, or when the use of fixed codes i 357 * results in a smaller compressed block t 358 * condition then assures that the above a 359 * blocks. A dynamic-code block will only 360 * fewer bits than a fixed-code block woul 361 * Therefore its average symbol length is 362 * the compressed data for a dynamic block 363 * symbols from which it is being construc 364 */ 365 366 s->pending_buf = (uchf *) ZALLOC(strm, s-> 367 s->pending_buf_size = (ulg)s->lit_bufsize 368 369 if (s->window == Z_NULL || s->prev == Z_NU 370 s->pending_buf == Z_NULL) { 371 s->status = FINISH_STATE; 372 strm->msg = ERR_MSG(Z_MEM_ERROR); 373 deflateEnd (strm); 374 return Z_MEM_ERROR; 375 } 376 s->sym_buf = s->pending_buf + s->lit_bufsi 377 s->sym_end = (s->lit_bufsize - 1) * 3; 378 /* We avoid equality with lit_bufsize*3 be 379 * on 16 bit machines and because stored b 380 * 64K-1 bytes. 381 */ 382 383 s->level = level; 384 s->strategy = strategy; 385 s->method = (Byte)method; 386 387 return deflateReset(strm); 388 } 389 390 /* =========================================== 391 * Check for a valid deflate stream state. Ret 392 */ 393 local int deflateStateCheck(strm) 394 z_streamp strm; 395 { 396 deflate_state *s; 397 if (strm == Z_NULL || 398 strm->zalloc == (alloc_func)0 || strm- 399 return 1; 400 s = strm->state; 401 if (s == Z_NULL || s->strm != strm || (s-> 402 #ifdef GZIP 403 s-> 404 #endif 405 s-> 406 s-> 407 s-> 408 s-> 409 s-> 410 s-> 411 return 1; 412 return 0; 413 } 414 415 /* =========================================== 416 int ZEXPORT deflateSetDictionary(strm, diction 417 z_streamp strm; 418 const Bytef *dictionary; 419 uInt dictLength; 420 { 421 deflate_state *s; 422 uInt str, n; 423 int wrap; 424 unsigned avail; 425 z_const unsigned char *next; 426 427 if (deflateStateCheck(strm) || dictionary 428 return Z_STREAM_ERROR; 429 s = strm->state; 430 wrap = s->wrap; 431 if (wrap == 2 || (wrap == 1 && s->status ! 432 return Z_STREAM_ERROR; 433 434 /* when using zlib wrappers, compute Adler 435 if (wrap == 1) 436 strm->adler = adler32(strm->adler, dic 437 s->wrap = 0; /* avoid c 438 439 /* if dictionary would fill window, just r 440 if (dictLength >= s->w_size) { 441 if (wrap == 0) { /* already 442 CLEAR_HASH(s); 443 s->strstart = 0; 444 s->block_start = 0L; 445 s->insert = 0; 446 } 447 dictionary += dictLength - s->w_size; 448 dictLength = s->w_size; 449 } 450 451 /* insert dictionary into window and hash 452 avail = strm->avail_in; 453 next = strm->next_in; 454 strm->avail_in = dictLength; 455 strm->next_in = (z_const Bytef *)dictionar 456 fill_window(s); 457 while (s->lookahead >= MIN_MATCH) { 458 str = s->strstart; 459 n = s->lookahead - (MIN_MATCH-1); 460 do { 461 UPDATE_HASH(s, s->ins_h, s->window 462 #ifndef FASTEST 463 s->prev[str & s->w_mask] = s->head 464 #endif 465 s->head[s->ins_h] = (Pos)str; 466 str++; 467 } while (--n); 468 s->strstart = str; 469 s->lookahead = MIN_MATCH-1; 470 fill_window(s); 471 } 472 s->strstart += s->lookahead; 473 s->block_start = (long)s->strstart; 474 s->insert = s->lookahead; 475 s->lookahead = 0; 476 s->match_length = s->prev_length = MIN_MAT 477 s->match_available = 0; 478 strm->next_in = next; 479 strm->avail_in = avail; 480 s->wrap = wrap; 481 return Z_OK; 482 } 483 484 /* =========================================== 485 int ZEXPORT deflateGetDictionary(strm, diction 486 z_streamp strm; 487 Bytef *dictionary; 488 uInt *dictLength; 489 { 490 deflate_state *s; 491 uInt len; 492 493 if (deflateStateCheck(strm)) 494 return Z_STREAM_ERROR; 495 s = strm->state; 496 len = s->strstart + s->lookahead; 497 if (len > s->w_size) 498 len = s->w_size; 499 if (dictionary != Z_NULL && len) 500 zmemcpy(dictionary, s->window + s->str 501 if (dictLength != Z_NULL) 502 *dictLength = len; 503 return Z_OK; 504 } 505 506 /* =========================================== 507 int ZEXPORT deflateResetKeep(strm) 508 z_streamp strm; 509 { 510 deflate_state *s; 511 512 if (deflateStateCheck(strm)) { 513 return Z_STREAM_ERROR; 514 } 515 516 strm->total_in = strm->total_out = 0; 517 strm->msg = Z_NULL; /* use zfree if we eve 518 strm->data_type = Z_UNKNOWN; 519 520 s = (deflate_state *)strm->state; 521 s->pending = 0; 522 s->pending_out = s->pending_buf; 523 524 if (s->wrap < 0) { 525 s->wrap = -s->wrap; /* was made negati 526 } 527 s->status = 528 #ifdef GZIP 529 s->wrap == 2 ? GZIP_STATE : 530 #endif 531 INIT_STATE; 532 strm->adler = 533 #ifdef GZIP 534 s->wrap == 2 ? crc32(0L, Z_NULL, 0) : 535 #endif 536 adler32(0L, Z_NULL, 0); 537 s->last_flush = -2; 538 539 _tr_init(s); 540 541 return Z_OK; 542 } 543 544 /* =========================================== 545 int ZEXPORT deflateReset(strm) 546 z_streamp strm; 547 { 548 int ret; 549 550 ret = deflateResetKeep(strm); 551 if (ret == Z_OK) 552 lm_init(strm->state); 553 return ret; 554 } 555 556 /* =========================================== 557 int ZEXPORT deflateSetHeader(strm, head) 558 z_streamp strm; 559 gz_headerp head; 560 { 561 if (deflateStateCheck(strm) || strm->state 562 return Z_STREAM_ERROR; 563 strm->state->gzhead = head; 564 return Z_OK; 565 } 566 567 /* =========================================== 568 int ZEXPORT deflatePending(strm, pending, bits 569 unsigned *pending; 570 int *bits; 571 z_streamp strm; 572 { 573 if (deflateStateCheck(strm)) return Z_STRE 574 if (pending != Z_NULL) 575 *pending = strm->state->pending; 576 if (bits != Z_NULL) 577 *bits = strm->state->bi_valid; 578 return Z_OK; 579 } 580 581 /* =========================================== 582 int ZEXPORT deflatePrime(strm, bits, value) 583 z_streamp strm; 584 int bits; 585 int value; 586 { 587 deflate_state *s; 588 int put; 589 590 if (deflateStateCheck(strm)) return Z_STRE 591 s = strm->state; 592 if (bits < 0 || bits > 16 || 593 s->sym_buf < s->pending_out + ((Buf_si 594 return Z_BUF_ERROR; 595 do { 596 put = Buf_size - s->bi_valid; 597 if (put > bits) 598 put = bits; 599 s->bi_buf |= (ush)((value & ((1 << put 600 s->bi_valid += put; 601 _tr_flush_bits(s); 602 value >>= put; 603 bits -= put; 604 } while (bits); 605 return Z_OK; 606 } 607 608 /* =========================================== 609 int ZEXPORT deflateParams(strm, level, strateg 610 z_streamp strm; 611 int level; 612 int strategy; 613 { 614 deflate_state *s; 615 compress_func func; 616 617 if (deflateStateCheck(strm)) return Z_STRE 618 s = strm->state; 619 620 #ifdef FASTEST 621 if (level != 0) level = 1; 622 #else 623 if (level == Z_DEFAULT_COMPRESSION) level 624 #endif 625 if (level < 0 || level > 9 || strategy < 0 626 return Z_STREAM_ERROR; 627 } 628 func = configuration_table[s->level].func; 629 630 if ((strategy != s->strategy || func != co 631 s->last_flush != -2) { 632 /* Flush the last buffer: */ 633 int err = deflate(strm, Z_BLOCK); 634 if (err == Z_STREAM_ERROR) 635 return err; 636 if (strm->avail_in || (s->strstart - s 637 return Z_BUF_ERROR; 638 } 639 if (s->level != level) { 640 if (s->level == 0 && s->matches != 0) 641 if (s->matches == 1) 642 slide_hash(s); 643 else 644 CLEAR_HASH(s); 645 s->matches = 0; 646 } 647 s->level = level; 648 s->max_lazy_match = configuration_ta 649 s->good_match = configuration_ta 650 s->nice_match = configuration_ta 651 s->max_chain_length = configuration_ta 652 } 653 s->strategy = strategy; 654 return Z_OK; 655 } 656 657 /* =========================================== 658 int ZEXPORT deflateTune(strm, good_length, max 659 z_streamp strm; 660 int good_length; 661 int max_lazy; 662 int nice_length; 663 int max_chain; 664 { 665 deflate_state *s; 666 667 if (deflateStateCheck(strm)) return Z_STRE 668 s = strm->state; 669 s->good_match = (uInt)good_length; 670 s->max_lazy_match = (uInt)max_lazy; 671 s->nice_match = nice_length; 672 s->max_chain_length = (uInt)max_chain; 673 return Z_OK; 674 } 675 676 /* =========================================== 677 * For the default windowBits of 15 and memLev 678 * close to exact, as well as small, upper bou 679 * is an expansion of ~0.03%, plus a small con 680 * 681 * For any setting other than those defaults f 682 * of two worst case bounds is returned. This 683 * ~13%, plus a small constant. 684 * 685 * Both the 0.03% and 4% derive from the overh 686 * one is for stored blocks of 16383 bytes (me 687 * is for stored blocks of 127 bytes (the wors 688 * expansion results from five bytes of header 689 * 690 * The larger expansion of 13% results from a 691 * the symbols buffer size (windowBits <= memL 692 * the data being compressed may have slid out 693 * a stored block from being emitted. Then the 694 * dynamic block, where a fixed block limits t 695 * per 8-bit byte, plus 10 bits for every bloc 696 * which this can occur is 255 (memLevel == 2) 697 * 698 * Shifts are used to approximate divisions, f 699 */ 700 uLong ZEXPORT deflateBound(strm, sourceLen) 701 z_streamp strm; 702 uLong sourceLen; 703 { 704 deflate_state *s; 705 uLong fixedlen, storelen, wraplen; 706 707 /* upper bound for fixed blocks with 9-bit 708 (memLevel == 2, which is the lowest tha 709 ~13% overhead plus a small constant */ 710 fixedlen = sourceLen + (sourceLen >> 3) + 711 (sourceLen >> 9) + 4; 712 713 /* upper bound for stored blocks with leng 714 ~4% overhead plus a small constant */ 715 storelen = sourceLen + (sourceLen >> 5) + 716 (sourceLen >> 11) + 7; 717 718 /* if can't get parameters, return larger 719 if (deflateStateCheck(strm)) 720 return (fixedlen > storelen ? fixedlen 721 722 /* compute wrapper length */ 723 s = strm->state; 724 switch (s->wrap) { 725 case 0: /* 726 wraplen = 0; 727 break; 728 case 1: /* 729 wraplen = 6 + (s->strstart ? 4 : 0); 730 break; 731 #ifdef GZIP 732 case 2: /* 733 wraplen = 18; 734 if (s->gzhead != Z_NULL) { /* 735 Bytef *str; 736 if (s->gzhead->extra != Z_NULL) 737 wraplen += 2 + s->gzhead->extr 738 str = s->gzhead->name; 739 if (str != Z_NULL) 740 do { 741 wraplen++; 742 } while (*str++); 743 str = s->gzhead->comment; 744 if (str != Z_NULL) 745 do { 746 wraplen++; 747 } while (*str++); 748 if (s->gzhead->hcrc) 749 wraplen += 2; 750 } 751 break; 752 #endif 753 default: /* 754 wraplen = 6; 755 } 756 757 /* if not default parameters, return one o 758 if (s->w_bits != 15 || s->hash_bits != 8 + 759 return (s->w_bits <= s->hash_bits ? fi 760 761 /* default settings: return tight bound fo 762 plus a small constant */ 763 return sourceLen + (sourceLen >> 12) + (so 764 (sourceLen >> 25) + 13 - 6 + wraple 765 } 766 767 /* =========================================== 768 * Put a short in the pending buffer. The 16-b 769 * IN assertion: the stream state is correct a 770 * pending_buf. 771 */ 772 local void putShortMSB(s, b) 773 deflate_state *s; 774 uInt b; 775 { 776 put_byte(s, (Byte)(b >> 8)); 777 put_byte(s, (Byte)(b & 0xff)); 778 } 779 780 /* =========================================== 781 * Flush as much pending output as possible. A 782 * some deflate_stored() output, goes through 783 * applications may wish to modify it to avoid 784 * strm->next_out buffer and copying into it. 785 */ 786 local void flush_pending(strm) 787 z_streamp strm; 788 { 789 unsigned len; 790 deflate_state *s = strm->state; 791 792 _tr_flush_bits(s); 793 len = s->pending; 794 if (len > strm->avail_out) len = strm->ava 795 if (len == 0) return; 796 797 zmemcpy(strm->next_out, s->pending_out, le 798 strm->next_out += len; 799 s->pending_out += len; 800 strm->total_out += len; 801 strm->avail_out -= len; 802 s->pending -= len; 803 if (s->pending == 0) { 804 s->pending_out = s->pending_buf; 805 } 806 } 807 808 /* =========================================== 809 * Update the header CRC with the bytes s->pen 810 */ 811 #define HCRC_UPDATE(beg) \ 812 do { \ 813 if (s->gzhead->hcrc && s->pending > (b 814 strm->adler = crc32(strm->adler, s 815 s->pending - ( 816 } while (0) 817 818 /* =========================================== 819 int ZEXPORT deflate(strm, flush) 820 z_streamp strm; 821 int flush; 822 { 823 int old_flush; /* value of flush param for 824 deflate_state *s; 825 826 if (deflateStateCheck(strm) || flush > Z_B 827 return Z_STREAM_ERROR; 828 } 829 s = strm->state; 830 831 if (strm->next_out == Z_NULL || 832 (strm->avail_in != 0 && strm->next_in 833 (s->status == FINISH_STATE && flush != 834 ERR_RETURN(strm, Z_STREAM_ERROR); 835 } 836 if (strm->avail_out == 0) ERR_RETURN(strm, 837 838 old_flush = s->last_flush; 839 s->last_flush = flush; 840 841 /* Flush as much pending output as possibl 842 if (s->pending != 0) { 843 flush_pending(strm); 844 if (strm->avail_out == 0) { 845 /* Since avail_out is 0, deflate w 846 * more output space, but possibly 847 * avail_in equal to zero. There w 848 * but this is not an error situat 849 * return OK instead of BUF_ERROR 850 */ 851 s->last_flush = -1; 852 return Z_OK; 853 } 854 855 /* Make sure there is something to do and 856 * flushes. For repeated and useless calls 857 * returning Z_STREAM_END instead of Z_BUF 858 */ 859 } else if (strm->avail_in == 0 && RANK(flu 860 flush != Z_FINISH) { 861 ERR_RETURN(strm, Z_BUF_ERROR); 862 } 863 864 /* User must not provide more input after 865 if (s->status == FINISH_STATE && strm->ava 866 ERR_RETURN(strm, Z_BUF_ERROR); 867 } 868 869 /* Write the header */ 870 if (s->status == INIT_STATE && s->wrap == 871 s->status = BUSY_STATE; 872 if (s->status == INIT_STATE) { 873 /* zlib header */ 874 uInt header = (Z_DEFLATED + ((s->w_bit 875 uInt level_flags; 876 877 if (s->strategy >= Z_HUFFMAN_ONLY || s 878 level_flags = 0; 879 else if (s->level < 6) 880 level_flags = 1; 881 else if (s->level == 6) 882 level_flags = 2; 883 else 884 level_flags = 3; 885 header |= (level_flags << 6); 886 if (s->strstart != 0) header |= PRESET 887 header += 31 - (header % 31); 888 889 putShortMSB(s, header); 890 891 /* Save the adler32 of the preset dict 892 if (s->strstart != 0) { 893 putShortMSB(s, (uInt)(strm->adler 894 putShortMSB(s, (uInt)(strm->adler 895 } 896 strm->adler = adler32(0L, Z_NULL, 0); 897 s->status = BUSY_STATE; 898 899 /* Compression must start with an empt 900 flush_pending(strm); 901 if (s->pending != 0) { 902 s->last_flush = -1; 903 return Z_OK; 904 } 905 } 906 #ifdef GZIP 907 if (s->status == GZIP_STATE) { 908 /* gzip header */ 909 strm->adler = crc32(0L, Z_NULL, 0); 910 put_byte(s, 31); 911 put_byte(s, 139); 912 put_byte(s, 8); 913 if (s->gzhead == Z_NULL) { 914 put_byte(s, 0); 915 put_byte(s, 0); 916 put_byte(s, 0); 917 put_byte(s, 0); 918 put_byte(s, 0); 919 put_byte(s, s->level == 9 ? 2 : 920 (s->strategy >= Z_HUFFMAN 921 4 : 0)); 922 put_byte(s, OS_CODE); 923 s->status = BUSY_STATE; 924 925 /* Compression must start with an 926 flush_pending(strm); 927 if (s->pending != 0) { 928 s->last_flush = -1; 929 return Z_OK; 930 } 931 } 932 else { 933 put_byte(s, (s->gzhead->text ? 1 : 934 (s->gzhead->hcrc ? 2 : 0) 935 (s->gzhead->extra == Z_NU 936 (s->gzhead->name == Z_NUL 937 (s->gzhead->comment == Z_ 938 ); 939 put_byte(s, (Byte)(s->gzhead->time 940 put_byte(s, (Byte)((s->gzhead->tim 941 put_byte(s, (Byte)((s->gzhead->tim 942 put_byte(s, (Byte)((s->gzhead->tim 943 put_byte(s, s->level == 9 ? 2 : 944 (s->strategy >= Z_HUFFMAN 945 4 : 0)); 946 put_byte(s, s->gzhead->os & 0xff); 947 if (s->gzhead->extra != Z_NULL) { 948 put_byte(s, s->gzhead->extra_l 949 put_byte(s, (s->gzhead->extra_ 950 } 951 if (s->gzhead->hcrc) 952 strm->adler = crc32(strm->adle 953 s->pending 954 s->gzindex = 0; 955 s->status = EXTRA_STATE; 956 } 957 } 958 if (s->status == EXTRA_STATE) { 959 if (s->gzhead->extra != Z_NULL) { 960 ulg beg = s->pending; /* start o 961 uInt left = (s->gzhead->extra_len 962 while (s->pending + left > s->pend 963 uInt copy = s->pending_buf_siz 964 zmemcpy(s->pending_buf + s->pe 965 s->gzhead->extra + s-> 966 s->pending = s->pending_buf_si 967 HCRC_UPDATE(beg); 968 s->gzindex += copy; 969 flush_pending(strm); 970 if (s->pending != 0) { 971 s->last_flush = -1; 972 return Z_OK; 973 } 974 beg = 0; 975 left -= copy; 976 } 977 zmemcpy(s->pending_buf + s->pendin 978 s->gzhead->extra + s->gzin 979 s->pending += left; 980 HCRC_UPDATE(beg); 981 s->gzindex = 0; 982 } 983 s->status = NAME_STATE; 984 } 985 if (s->status == NAME_STATE) { 986 if (s->gzhead->name != Z_NULL) { 987 ulg beg = s->pending; /* start o 988 int val; 989 do { 990 if (s->pending == s->pending_b 991 HCRC_UPDATE(beg); 992 flush_pending(strm); 993 if (s->pending != 0) { 994 s->last_flush = -1; 995 return Z_OK; 996 } 997 beg = 0; 998 } 999 val = s->gzhead->name[s->gzind 1000 put_byte(s, val); 1001 } while (val != 0); 1002 HCRC_UPDATE(beg); 1003 s->gzindex = 0; 1004 } 1005 s->status = COMMENT_STATE; 1006 } 1007 if (s->status == COMMENT_STATE) { 1008 if (s->gzhead->comment != Z_NULL) { 1009 ulg beg = s->pending; /* start 1010 int val; 1011 do { 1012 if (s->pending == s->pending_ 1013 HCRC_UPDATE(beg); 1014 flush_pending(strm); 1015 if (s->pending != 0) { 1016 s->last_flush = -1; 1017 return Z_OK; 1018 } 1019 beg = 0; 1020 } 1021 val = s->gzhead->comment[s->g 1022 put_byte(s, val); 1023 } while (val != 0); 1024 HCRC_UPDATE(beg); 1025 } 1026 s->status = HCRC_STATE; 1027 } 1028 if (s->status == HCRC_STATE) { 1029 if (s->gzhead->hcrc) { 1030 if (s->pending + 2 > s->pending_b 1031 flush_pending(strm); 1032 if (s->pending != 0) { 1033 s->last_flush = -1; 1034 return Z_OK; 1035 } 1036 } 1037 put_byte(s, (Byte)(strm->adler & 1038 put_byte(s, (Byte)((strm->adler > 1039 strm->adler = crc32(0L, Z_NULL, 0 1040 } 1041 s->status = BUSY_STATE; 1042 1043 /* Compression must start with an emp 1044 flush_pending(strm); 1045 if (s->pending != 0) { 1046 s->last_flush = -1; 1047 return Z_OK; 1048 } 1049 } 1050 #endif 1051 1052 /* Start a new block or continue the curr 1053 */ 1054 if (strm->avail_in != 0 || s->lookahead ! 1055 (flush != Z_NO_FLUSH && s->status != 1056 block_state bstate; 1057 1058 bstate = s->level == 0 ? deflate_stor 1059 s->strategy == Z_HUFFMAN_ONL 1060 s->strategy == Z_RLE ? defla 1061 (*(configuration_table[s->le 1062 1063 if (bstate == finish_started || bstat 1064 s->status = FINISH_STATE; 1065 } 1066 if (bstate == need_more || bstate == 1067 if (strm->avail_out == 0) { 1068 s->last_flush = -1; /* avoid 1069 } 1070 return Z_OK; 1071 /* If flush != Z_NO_FLUSH && avai 1072 * of deflate should use the same 1073 * that the flush is complete. So 1074 * empty block here, this will be 1075 * ensures that for a very small 1076 * one empty block. 1077 */ 1078 } 1079 if (bstate == block_done) { 1080 if (flush == Z_PARTIAL_FLUSH) { 1081 _tr_align(s); 1082 } else if (flush != Z_BLOCK) { /* 1083 _tr_stored_block(s, (char*)0, 1084 /* For a full flush, this emp 1085 * as a special marker by inf 1086 */ 1087 if (flush == Z_FULL_FLUSH) { 1088 CLEAR_HASH(s); 1089 if (s->lookahead == 0) { 1090 s->strstart = 0; 1091 s->block_start = 0L; 1092 s->insert = 0; 1093 } 1094 } 1095 } 1096 flush_pending(strm); 1097 if (strm->avail_out == 0) { 1098 s->last_flush = -1; /* avoid BU 1099 return Z_OK; 1100 } 1101 } 1102 } 1103 1104 if (flush != Z_FINISH) return Z_OK; 1105 if (s->wrap <= 0) return Z_STREAM_END; 1106 1107 /* Write the trailer */ 1108 #ifdef GZIP 1109 if (s->wrap == 2) { 1110 put_byte(s, (Byte)(strm->adler & 0xff 1111 put_byte(s, (Byte)((strm->adler >> 8) 1112 put_byte(s, (Byte)((strm->adler >> 16 1113 put_byte(s, (Byte)((strm->adler >> 24 1114 put_byte(s, (Byte)(strm->total_in & 0 1115 put_byte(s, (Byte)((strm->total_in >> 1116 put_byte(s, (Byte)((strm->total_in >> 1117 put_byte(s, (Byte)((strm->total_in >> 1118 } 1119 else 1120 #endif 1121 { 1122 putShortMSB(s, (uInt)(strm->adler >> 1123 putShortMSB(s, (uInt)(strm->adler & 0 1124 } 1125 flush_pending(strm); 1126 /* If avail_out is zero, the application 1127 * to flush the rest. 1128 */ 1129 if (s->wrap > 0) s->wrap = -s->wrap; /* w 1130 return s->pending != 0 ? Z_OK : Z_STREAM_ 1131 } 1132 1133 /* ========================================== 1134 int ZEXPORT deflateEnd(strm) 1135 z_streamp strm; 1136 { 1137 int status; 1138 1139 if (deflateStateCheck(strm)) return Z_STR 1140 1141 status = strm->state->status; 1142 1143 /* Deallocate in reverse order of allocat 1144 TRY_FREE(strm, strm->state->pending_buf); 1145 TRY_FREE(strm, strm->state->head); 1146 TRY_FREE(strm, strm->state->prev); 1147 TRY_FREE(strm, strm->state->window); 1148 1149 ZFREE(strm, strm->state); 1150 strm->state = Z_NULL; 1151 1152 return status == BUSY_STATE ? Z_DATA_ERRO 1153 } 1154 1155 /* ========================================== 1156 * Copy the source state to the destination s 1157 * To simplify the source, this is not suppor 1158 * doesn't have enough memory anyway to dupli 1159 */ 1160 int ZEXPORT deflateCopy(dest, source) 1161 z_streamp dest; 1162 z_streamp source; 1163 { 1164 #ifdef MAXSEG_64K 1165 return Z_STREAM_ERROR; 1166 #else 1167 deflate_state *ds; 1168 deflate_state *ss; 1169 1170 1171 if (deflateStateCheck(source) || dest == 1172 return Z_STREAM_ERROR; 1173 } 1174 1175 ss = source->state; 1176 1177 zmemcpy((voidpf)dest, (voidpf)source, siz 1178 1179 ds = (deflate_state *) ZALLOC(dest, 1, si 1180 if (ds == Z_NULL) return Z_MEM_ERROR; 1181 dest->state = (struct internal_state FAR 1182 zmemcpy((voidpf)ds, (voidpf)ss, sizeof(de 1183 ds->strm = dest; 1184 1185 ds->window = (Bytef *) ZALLOC(dest, ds->w 1186 ds->prev = (Posf *) ZALLOC(dest, ds->w 1187 ds->head = (Posf *) ZALLOC(dest, ds->h 1188 ds->pending_buf = (uchf *) ZALLOC(dest, d 1189 1190 if (ds->window == Z_NULL || ds->prev == Z 1191 ds->pending_buf == Z_NULL) { 1192 deflateEnd (dest); 1193 return Z_MEM_ERROR; 1194 } 1195 /* following zmemcpy do not work for 16-b 1196 zmemcpy(ds->window, ss->window, ds->w_siz 1197 zmemcpy((voidpf)ds->prev, (voidpf)ss->pre 1198 zmemcpy((voidpf)ds->head, (voidpf)ss->hea 1199 zmemcpy(ds->pending_buf, ss->pending_buf, 1200 1201 ds->pending_out = ds->pending_buf + (ss-> 1202 ds->sym_buf = ds->pending_buf + ds->lit_b 1203 1204 ds->l_desc.dyn_tree = ds->dyn_ltree; 1205 ds->d_desc.dyn_tree = ds->dyn_dtree; 1206 ds->bl_desc.dyn_tree = ds->bl_tree; 1207 1208 return Z_OK; 1209 #endif /* MAXSEG_64K */ 1210 } 1211 1212 /* ========================================== 1213 * Read a new buffer from the current input s 1214 * and total number of bytes read. All defla 1215 * this function so some applications may wis 1216 * allocating a large strm->next_in buffer an 1217 * (See also flush_pending()). 1218 */ 1219 local unsigned read_buf(strm, buf, size) 1220 z_streamp strm; 1221 Bytef *buf; 1222 unsigned size; 1223 { 1224 unsigned len = strm->avail_in; 1225 1226 if (len > size) len = size; 1227 if (len == 0) return 0; 1228 1229 strm->avail_in -= len; 1230 1231 zmemcpy(buf, strm->next_in, len); 1232 if (strm->state->wrap == 1) { 1233 strm->adler = adler32(strm->adler, bu 1234 } 1235 #ifdef GZIP 1236 else if (strm->state->wrap == 2) { 1237 strm->adler = crc32(strm->adler, buf, 1238 } 1239 #endif 1240 strm->next_in += len; 1241 strm->total_in += len; 1242 1243 return len; 1244 } 1245 1246 /* ========================================== 1247 * Initialize the "longest match" routines fo 1248 */ 1249 local void lm_init(s) 1250 deflate_state *s; 1251 { 1252 s->window_size = (ulg)2L*s->w_size; 1253 1254 CLEAR_HASH(s); 1255 1256 /* Set the default configuration paramete 1257 */ 1258 s->max_lazy_match = configuration_table 1259 s->good_match = configuration_table 1260 s->nice_match = configuration_table 1261 s->max_chain_length = configuration_table 1262 1263 s->strstart = 0; 1264 s->block_start = 0L; 1265 s->lookahead = 0; 1266 s->insert = 0; 1267 s->match_length = s->prev_length = MIN_MA 1268 s->match_available = 0; 1269 s->ins_h = 0; 1270 } 1271 1272 #ifndef FASTEST 1273 /* ========================================== 1274 * Set match_start to the longest match start 1275 * return its length. Matches shorter or equa 1276 * in which case the result is equal to prev_ 1277 * garbage. 1278 * IN assertions: cur_match is the head of th 1279 * string (strstart) and its distance is <= 1280 * OUT assertion: the match length is not gre 1281 */ 1282 local uInt longest_match(s, cur_match) 1283 deflate_state *s; 1284 IPos cur_match; 1285 { 1286 unsigned chain_length = s->max_chain_leng 1287 register Bytef *scan = s->window + s->str 1288 register Bytef *match; 1289 register int len; 1290 int best_len = (int)s->prev_length; 1291 int nice_match = s->nice_match; 1292 IPos limit = s->strstart > (IPos)MAX_DIST 1293 s->strstart - (IPos)MAX_DIST(s) : NIL 1294 /* Stop when cur_match becomes <= limit. 1295 * we prevent matches with the string of 1296 */ 1297 Posf *prev = s->prev; 1298 uInt wmask = s->w_mask; 1299 1300 #ifdef UNALIGNED_OK 1301 /* Compare two bytes at a time. Note: thi 1302 * Try with and without -DUNALIGNED_OK to 1303 */ 1304 register Bytef *strend = s->window + s->s 1305 register ush scan_start = *(ushf*)scan; 1306 register ush scan_end = *(ushf*)(scan + 1307 #else 1308 register Bytef *strend = s->window + s->s 1309 register Byte scan_end1 = scan[best_len 1310 register Byte scan_end = scan[best_len] 1311 #endif 1312 1313 /* The code is optimized for HASH_BITS >= 1314 * It is easy to get rid of this optimiza 1315 */ 1316 Assert(s->hash_bits >= 8 && MAX_MATCH == 1317 1318 /* Do not waste too much time if we alrea 1319 if (s->prev_length >= s->good_match) { 1320 chain_length >>= 2; 1321 } 1322 /* Do not look for matches beyond the end 1323 * to make deflate deterministic. 1324 */ 1325 if ((uInt)nice_match > s->lookahead) nice 1326 1327 Assert((ulg)s->strstart <= s->window_size 1328 "need lookahead"); 1329 1330 do { 1331 Assert(cur_match < s->strstart, "no f 1332 match = s->window + cur_match; 1333 1334 /* Skip to next match if the match le 1335 * or if the match length is less tha 1336 * for insufficient lookahead only oc 1337 * reasons. Therefore uninitialized 1338 * conditional jumps will be made tha 1339 * However the length of the match is 1340 * the output of deflate is not affec 1341 */ 1342 #if (defined(UNALIGNED_OK) && MAX_MATCH == 25 1343 /* This code assumes sizeof(unsigned 1344 * UNALIGNED_OK if your compiler uses 1345 */ 1346 if (*(ushf*)(match + best_len - 1) != 1347 *(ushf*)match != scan_start) cont 1348 1349 /* It is not necessary to compare sca 1350 * always equal when the other bytes 1351 * are equal and that HASH_BITS >= 8. 1352 * strstart + 3, + 5, up to strstart 1353 * lookahead only every 4th compariso 1354 * at strstart + 257. If MAX_MATCH-2 1355 * necessary to put more guard bytes 1356 * to check more often for insufficie 1357 */ 1358 Assert(scan[2] == match[2], "scan[2]? 1359 scan++, match++; 1360 do { 1361 } while (*(ushf*)(scan += 2) == *(ush 1362 *(ushf*)(scan += 2) == *(ush 1363 *(ushf*)(scan += 2) == *(ush 1364 *(ushf*)(scan += 2) == *(ush 1365 scan < strend); 1366 /* The funny "do {}" generates better 1367 1368 /* Here, scan <= window + strstart + 1369 Assert(scan <= s->window + (unsigned) 1370 "wild scan"); 1371 if (*scan == *match) scan++; 1372 1373 len = (MAX_MATCH - 1) - (int)(strend 1374 scan = strend - (MAX_MATCH-1); 1375 1376 #else /* UNALIGNED_OK */ 1377 1378 if (match[best_len] != scan_end 1379 match[best_len - 1] != scan_end1 1380 *match != *scan 1381 *++match != scan[1]) 1382 1383 /* The check at best_len - 1 can be r 1384 * again later. (This heuristic is no 1385 * It is not necessary to compare sca 1386 * are always equal when the other by 1387 * the hash keys are equal and that H 1388 */ 1389 scan += 2, match++; 1390 Assert(*scan == *match, "match[2]?"); 1391 1392 /* We check for insufficient lookahea 1393 * the 256th check will be made at st 1394 */ 1395 do { 1396 } while (*++scan == *++match && *++sc 1397 *++scan == *++match && *++sc 1398 *++scan == *++match && *++sc 1399 *++scan == *++match && *++sc 1400 scan < strend); 1401 1402 Assert(scan <= s->window + (unsigned) 1403 "wild scan"); 1404 1405 len = MAX_MATCH - (int)(strend - scan 1406 scan = strend - MAX_MATCH; 1407 1408 #endif /* UNALIGNED_OK */ 1409 1410 if (len > best_len) { 1411 s->match_start = cur_match; 1412 best_len = len; 1413 if (len >= nice_match) break; 1414 #ifdef UNALIGNED_OK 1415 scan_end = *(ushf*)(scan + best_l 1416 #else 1417 scan_end1 = scan[best_len - 1]; 1418 scan_end = scan[best_len]; 1419 #endif 1420 } 1421 } while ((cur_match = prev[cur_match & wm 1422 && --chain_length != 0); 1423 1424 if ((uInt)best_len <= s->lookahead) retur 1425 return s->lookahead; 1426 } 1427 1428 #else /* FASTEST */ 1429 1430 /* ------------------------------------------ 1431 * Optimized version for FASTEST only 1432 */ 1433 local uInt longest_match(s, cur_match) 1434 deflate_state *s; 1435 IPos cur_match; 1436 { 1437 register Bytef *scan = s->window + s->str 1438 register Bytef *match; 1439 register int len; 1440 register Bytef *strend = s->window + s->s 1441 1442 /* The code is optimized for HASH_BITS >= 1443 * It is easy to get rid of this optimiza 1444 */ 1445 Assert(s->hash_bits >= 8 && MAX_MATCH == 1446 1447 Assert((ulg)s->strstart <= s->window_size 1448 "need lookahead"); 1449 1450 Assert(cur_match < s->strstart, "no futur 1451 1452 match = s->window + cur_match; 1453 1454 /* Return failure if the match length is 1455 */ 1456 if (match[0] != scan[0] || match[1] != sc 1457 1458 /* The check at best_len - 1 can be remov 1459 * again later. (This heuristic is not al 1460 * It is not necessary to compare scan[2] 1461 * are always equal when the other bytes 1462 * the hash keys are equal and that HASH_ 1463 */ 1464 scan += 2, match += 2; 1465 Assert(*scan == *match, "match[2]?"); 1466 1467 /* We check for insufficient lookahead on 1468 * the 256th check will be made at strsta 1469 */ 1470 do { 1471 } while (*++scan == *++match && *++scan = 1472 *++scan == *++match && *++scan = 1473 *++scan == *++match && *++scan = 1474 *++scan == *++match && *++scan = 1475 scan < strend); 1476 1477 Assert(scan <= s->window + (unsigned)(s-> 1478 1479 len = MAX_MATCH - (int)(strend - scan); 1480 1481 if (len < MIN_MATCH) return MIN_MATCH - 1 1482 1483 s->match_start = cur_match; 1484 return (uInt)len <= s->lookahead ? (uInt) 1485 } 1486 1487 #endif /* FASTEST */ 1488 1489 #ifdef ZLIB_DEBUG 1490 1491 #define EQUAL 0 1492 /* result of memcmp for equal strings */ 1493 1494 /* ========================================== 1495 * Check that the match at match_start is ind 1496 */ 1497 local void check_match(s, start, match, lengt 1498 deflate_state *s; 1499 IPos start, match; 1500 int length; 1501 { 1502 /* check that the match is indeed a match 1503 if (zmemcmp(s->window + match, 1504 s->window + start, length) != 1505 fprintf(stderr, " start %u, match %u, 1506 start, match, length); 1507 do { 1508 fprintf(stderr, "%c%c", s->window 1509 } while (--length != 0); 1510 z_error("invalid match"); 1511 } 1512 if (z_verbose > 1) { 1513 fprintf(stderr,"\\[%d,%d]", start - m 1514 do { putc(s->window[start++], stderr) 1515 } 1516 } 1517 #else 1518 # define check_match(s, start, match, length 1519 #endif /* ZLIB_DEBUG */ 1520 1521 /* ========================================== 1522 * Fill the window when the lookahead becomes 1523 * Updates strstart and lookahead. 1524 * 1525 * IN assertion: lookahead < MIN_LOOKAHEAD 1526 * OUT assertions: strstart <= window_size-MI 1527 * At least one byte has been read, or ava 1528 * performed for at least two bytes (requi 1529 * option -- not supported here). 1530 */ 1531 local void fill_window(s) 1532 deflate_state *s; 1533 { 1534 unsigned n; 1535 unsigned more; /* Amount of free space 1536 uInt wsize = s->w_size; 1537 1538 Assert(s->lookahead < MIN_LOOKAHEAD, "alr 1539 1540 do { 1541 more = (unsigned)(s->window_size -(ul 1542 1543 /* Deal with !@#$% 64K limit: */ 1544 if (sizeof(int) <= 2) { 1545 if (more == 0 && s->strstart == 0 1546 more = wsize; 1547 1548 } else if (more == (unsigned)(-1) 1549 /* Very unlikely, but possibl 1550 * strstart == 0 && lookahead 1551 */ 1552 more--; 1553 } 1554 } 1555 1556 /* If the window is almost full and t 1557 * move the upper half to the lower o 1558 */ 1559 if (s->strstart >= wsize + MAX_DIST(s 1560 1561 zmemcpy(s->window, s->window + ws 1562 s->match_start -= wsize; 1563 s->strstart -= wsize; /* we no 1564 s->block_start -= (long) wsize; 1565 if (s->insert > s->strstart) 1566 s->insert = s->strstart; 1567 slide_hash(s); 1568 more += wsize; 1569 } 1570 if (s->strm->avail_in == 0) break; 1571 1572 /* If there was no sliding: 1573 * strstart <= WSIZE+MAX_DIST-1 && 1574 * more == window_size - lookahead 1575 * => more >= window_size - (MIN_LOOK 1576 * => more >= window_size - 2*WSIZE + 1577 * In the BIG_MEM or MMAP case (not y 1578 * window_size == input_size + MIN_ 1579 * strstart + s->lookahead <= input 1580 * Otherwise, window_size == 2*WSIZE 1581 * If there was sliding, more >= WSIZ 1582 */ 1583 Assert(more >= 2, "more < 2"); 1584 1585 n = read_buf(s->strm, s->window + s-> 1586 s->lookahead += n; 1587 1588 /* Initialize the hash value now that 1589 if (s->lookahead + s->insert >= MIN_M 1590 uInt str = s->strstart - s->inser 1591 s->ins_h = s->window[str]; 1592 UPDATE_HASH(s, s->ins_h, s->windo 1593 #if MIN_MATCH != 3 1594 Call UPDATE_HASH() MIN_MATCH-3 mo 1595 #endif 1596 while (s->insert) { 1597 UPDATE_HASH(s, s->ins_h, s->w 1598 #ifndef FASTEST 1599 s->prev[str & s->w_mask] = s- 1600 #endif 1601 s->head[s->ins_h] = (Pos)str; 1602 str++; 1603 s->insert--; 1604 if (s->lookahead + s->insert 1605 break; 1606 } 1607 } 1608 /* If the whole input has less than M 1609 * but this is not important since on 1610 */ 1611 1612 } while (s->lookahead < MIN_LOOKAHEAD && 1613 1614 /* If the WIN_INIT bytes after the end of 1615 * written, then zero those bytes in orde 1616 * the use of uninitialized (or uninitial 1617 * the longest match routines. Update th 1618 * time through here. WIN_INIT is set to 1619 * routines allow scanning to strstart + 1620 */ 1621 if (s->high_water < s->window_size) { 1622 ulg curr = s->strstart + (ulg)(s->loo 1623 ulg init; 1624 1625 if (s->high_water < curr) { 1626 /* Previous high water mark below 1627 * bytes or up to end of window, 1628 */ 1629 init = s->window_size - curr; 1630 if (init > WIN_INIT) 1631 init = WIN_INIT; 1632 zmemzero(s->window + curr, (unsig 1633 s->high_water = curr + init; 1634 } 1635 else if (s->high_water < (ulg)curr + 1636 /* High water mark at or above cu 1637 * plus WIN_INIT -- zero out to c 1638 * to end of window, whichever is 1639 */ 1640 init = (ulg)curr + WIN_INIT - s-> 1641 if (init > s->window_size - s->hi 1642 init = s->window_size - s->hi 1643 zmemzero(s->window + s->high_wate 1644 s->high_water += init; 1645 } 1646 } 1647 1648 Assert((ulg)s->strstart <= s->window_size 1649 "not enough room for search"); 1650 } 1651 1652 /* ========================================== 1653 * Flush the current block, with given end-of 1654 * IN assertion: strstart is set to the end o 1655 */ 1656 #define FLUSH_BLOCK_ONLY(s, last) { \ 1657 _tr_flush_block(s, (s->block_start >= 0L ? 1658 (charf *)&s->window[(unsig 1659 (charf *)Z_NULL), \ 1660 (ulg)((long)s->strstart - s-> 1661 (last)); \ 1662 s->block_start = s->strstart; \ 1663 flush_pending(s->strm); \ 1664 Tracev((stderr,"[FLUSH]")); \ 1665 } 1666 1667 /* Same but force premature exit if necessary 1668 #define FLUSH_BLOCK(s, last) { \ 1669 FLUSH_BLOCK_ONLY(s, last); \ 1670 if (s->strm->avail_out == 0) return (last) 1671 } 1672 1673 /* Maximum stored block length in deflate for 1674 #define MAX_STORED 65535 1675 1676 /* Minimum of a and b. */ 1677 #define MIN(a, b) ((a) > (b) ? (b) : (a)) 1678 1679 /* ========================================== 1680 * Copy without compression as much as possib 1681 * the current block state. 1682 * 1683 * In case deflateParams() is used to later s 1684 * level, s->matches (otherwise unused when s 1685 * of hash table slides to perform. If s->mat 1686 * slide will be done when switching. If s->m 1687 * allowed here, then the hash table will be 1688 * is the same as a clear. 1689 * 1690 * deflate_stored() is written to minimize th 1691 * copied. It is most efficient with large in 1692 * maximizes the opportunities to have a sing 1693 */ 1694 local block_state deflate_stored(s, flush) 1695 deflate_state *s; 1696 int flush; 1697 { 1698 /* Smallest worthy block size when not fl 1699 * this is 32K. This can be as small as 5 1700 * large input and output buffers, the st 1701 */ 1702 unsigned min_block = MIN(s->pending_buf_s 1703 1704 /* Copy as many min_block or larger store 1705 * possible. If flushing, copy the remain 1706 * stored blocks, if there is enough spac 1707 */ 1708 unsigned len, left, have, last = 0; 1709 unsigned used = s->strm->avail_in; 1710 do { 1711 /* Set len to the maximum size block 1712 * available input data and output sp 1713 * would be copied from what's left i 1714 */ 1715 len = MAX_STORED; /* maximum de 1716 have = (s->bi_valid + 42) >> 3; 1717 if (s->strm->avail_out < have) 1718 break; 1719 /* maximum stored block length th 1720 have = s->strm->avail_out - have; 1721 left = s->strstart - s->block_start; 1722 if (len > (ulg)left + s->strm->avail_ 1723 len = left + s->strm->avail_in; 1724 if (len > have) 1725 len = have; 1726 1727 /* If the stored block would be less 1728 * unable to copy all of the availabl 1729 * copying to the window and the pend 1730 * write an empty block when flushing 1731 */ 1732 if (len < min_block && ((len == 0 && 1733 flush == Z_NO 1734 len != left + 1735 break; 1736 1737 /* Make a dummy stored block in pendi 1738 * including any pending bits. This a 1739 */ 1740 last = flush == Z_FINISH && len == le 1741 _tr_stored_block(s, (char *)0, 0L, la 1742 1743 /* Replace the lengths in the dummy s 1744 s->pending_buf[s->pending - 4] = len; 1745 s->pending_buf[s->pending - 3] = len 1746 s->pending_buf[s->pending - 2] = ~len 1747 s->pending_buf[s->pending - 1] = ~len 1748 1749 /* Write the stored block header byte 1750 flush_pending(s->strm); 1751 1752 #ifdef ZLIB_DEBUG 1753 /* Update debugging counts for the da 1754 s->compressed_len += len << 3; 1755 s->bits_sent += len << 3; 1756 #endif 1757 1758 /* Copy uncompressed bytes from the w 1759 if (left) { 1760 if (left > len) 1761 left = len; 1762 zmemcpy(s->strm->next_out, s->win 1763 s->strm->next_out += left; 1764 s->strm->avail_out -= left; 1765 s->strm->total_out += left; 1766 s->block_start += left; 1767 len -= left; 1768 } 1769 1770 /* Copy uncompressed bytes directly f 1771 * the check value. 1772 */ 1773 if (len) { 1774 read_buf(s->strm, s->strm->next_o 1775 s->strm->next_out += len; 1776 s->strm->avail_out -= len; 1777 s->strm->total_out += len; 1778 } 1779 } while (last == 0); 1780 1781 /* Update the sliding window with the las 1782 * data, or append all of the copied data 1783 * than s->w_size bytes were copied. Also 1784 * insert in the hash tables, in the even 1785 * a non-zero compression level. 1786 */ 1787 used -= s->strm->avail_in; /* number 1788 if (used) { 1789 /* If any input was used, then no unu 1790 * therefore s->block_start == s->str 1791 */ 1792 if (used >= s->w_size) { /* suppla 1793 s->matches = 2; /* clear 1794 zmemcpy(s->window, s->strm->next_ 1795 s->strstart = s->w_size; 1796 s->insert = s->strstart; 1797 } 1798 else { 1799 if (s->window_size - s->strstart 1800 /* Slide the window down. */ 1801 s->strstart -= s->w_size; 1802 zmemcpy(s->window, s->window 1803 if (s->matches < 2) 1804 s->matches++; /* add a 1805 if (s->insert > s->strstart) 1806 s->insert = s->strstart; 1807 } 1808 zmemcpy(s->window + s->strstart, 1809 s->strstart += used; 1810 s->insert += MIN(used, s->w_size 1811 } 1812 s->block_start = s->strstart; 1813 } 1814 if (s->high_water < s->strstart) 1815 s->high_water = s->strstart; 1816 1817 /* If the last block was written to next_ 1818 if (last) 1819 return finish_done; 1820 1821 /* If flushing and all input has been con 1822 if (flush != Z_NO_FLUSH && flush != Z_FIN 1823 s->strm->avail_in == 0 && (long)s->st 1824 return block_done; 1825 1826 /* Fill the window with any remaining inp 1827 have = s->window_size - s->strstart; 1828 if (s->strm->avail_in > have && s->block_ 1829 /* Slide the window down. */ 1830 s->block_start -= s->w_size; 1831 s->strstart -= s->w_size; 1832 zmemcpy(s->window, s->window + s->w_s 1833 if (s->matches < 2) 1834 s->matches++; /* add a 1835 have += s->w_size; /* more s 1836 if (s->insert > s->strstart) 1837 s->insert = s->strstart; 1838 } 1839 if (have > s->strm->avail_in) 1840 have = s->strm->avail_in; 1841 if (have) { 1842 read_buf(s->strm, s->window + s->strs 1843 s->strstart += have; 1844 s->insert += MIN(have, s->w_size - s- 1845 } 1846 if (s->high_water < s->strstart) 1847 s->high_water = s->strstart; 1848 1849 /* There was not enough avail_out to writ 1850 * stored block to next_out. Write a stor 1851 * have enough input for a worthy block, 1852 * room for the remaining input as a stor 1853 */ 1854 have = (s->bi_valid + 42) >> 3; / 1855 /* maximum stored block length that w 1856 have = MIN(s->pending_buf_size - have, MA 1857 min_block = MIN(have, s->w_size); 1858 left = s->strstart - s->block_start; 1859 if (left >= min_block || 1860 ((left || flush == Z_FINISH) && flush 1861 s->strm->avail_in == 0 && left <= ha 1862 len = MIN(left, have); 1863 last = flush == Z_FINISH && s->strm-> 1864 len == left ? 1 : 0; 1865 _tr_stored_block(s, (charf *)s->windo 1866 s->block_start += len; 1867 flush_pending(s->strm); 1868 } 1869 1870 /* We've done all we can with the availab 1871 return last ? finish_started : need_more; 1872 } 1873 1874 /* ========================================== 1875 * Compress as much as possible from the inpu 1876 * block state. 1877 * This function does not perform lazy evalua 1878 * new strings in the dictionary only for unm 1879 * matches. It is used only for the fast comp 1880 */ 1881 local block_state deflate_fast(s, flush) 1882 deflate_state *s; 1883 int flush; 1884 { 1885 IPos hash_head; /* head of the hash 1886 int bflush; /* set if current b 1887 1888 for (;;) { 1889 /* Make sure that we always have enou 1890 * at the end of the input file. We n 1891 * for the next match, plus MIN_MATCH 1892 * string following the next match. 1893 */ 1894 if (s->lookahead < MIN_LOOKAHEAD) { 1895 fill_window(s); 1896 if (s->lookahead < MIN_LOOKAHEAD 1897 return need_more; 1898 } 1899 if (s->lookahead == 0) break; /* 1900 } 1901 1902 /* Insert the string window[strstart 1903 * dictionary, and set hash_head to t 1904 */ 1905 hash_head = NIL; 1906 if (s->lookahead >= MIN_MATCH) { 1907 INSERT_STRING(s, s->strstart, has 1908 } 1909 1910 /* Find the longest match, discarding 1911 * At this point we have always match 1912 */ 1913 if (hash_head != NIL && s->strstart - 1914 /* To simplify the code, we preve 1915 * of window index 0 (in particul 1916 * of the string with itself at t 1917 */ 1918 s->match_length = longest_match ( 1919 /* longest_match() sets match_sta 1920 } 1921 if (s->match_length >= MIN_MATCH) { 1922 check_match(s, s->strstart, s->ma 1923 1924 _tr_tally_dist(s, s->strstart - s 1925 s->match_length - 1926 1927 s->lookahead -= s->match_length; 1928 1929 /* Insert new strings in the hash 1930 * is not too large. This saves t 1931 */ 1932 #ifndef FASTEST 1933 if (s->match_length <= s->max_ins 1934 s->lookahead >= MIN_MATCH) { 1935 s->match_length--; /* string 1936 do { 1937 s->strstart++; 1938 INSERT_STRING(s, s->strst 1939 /* strstart never exceeds 1940 * always MIN_MATCH bytes 1941 */ 1942 } while (--s->match_length != 1943 s->strstart++; 1944 } else 1945 #endif 1946 { 1947 s->strstart += s->match_lengt 1948 s->match_length = 0; 1949 s->ins_h = s->window[s->strst 1950 UPDATE_HASH(s, s->ins_h, s->w 1951 #if MIN_MATCH != 3 1952 Call UPDATE_HASH() MIN_MATCH- 1953 #endif 1954 /* If lookahead < MIN_MATCH, 1955 * matter since it will be re 1956 */ 1957 } 1958 } else { 1959 /* No match, output a literal byt 1960 Tracevv((stderr,"%c", s->window[s 1961 _tr_tally_lit(s, s->window[s->str 1962 s->lookahead--; 1963 s->strstart++; 1964 } 1965 if (bflush) FLUSH_BLOCK(s, 0); 1966 } 1967 s->insert = s->strstart < MIN_MATCH-1 ? s 1968 if (flush == Z_FINISH) { 1969 FLUSH_BLOCK(s, 1); 1970 return finish_done; 1971 } 1972 if (s->sym_next) 1973 FLUSH_BLOCK(s, 0); 1974 return block_done; 1975 } 1976 1977 #ifndef FASTEST 1978 /* ========================================== 1979 * Same as above, but achieves better compres 1980 * evaluation for matches: a match is finally 1981 * no better match at the next window positio 1982 */ 1983 local block_state deflate_slow(s, flush) 1984 deflate_state *s; 1985 int flush; 1986 { 1987 IPos hash_head; /* head of hash 1988 int bflush; /* set if curren 1989 1990 /* Process the input block. */ 1991 for (;;) { 1992 /* Make sure that we always have enou 1993 * at the end of the input file. We n 1994 * for the next match, plus MIN_MATCH 1995 * string following the next match. 1996 */ 1997 if (s->lookahead < MIN_LOOKAHEAD) { 1998 fill_window(s); 1999 if (s->lookahead < MIN_LOOKAHEAD 2000 return need_more; 2001 } 2002 if (s->lookahead == 0) break; /* 2003 } 2004 2005 /* Insert the string window[strstart 2006 * dictionary, and set hash_head to t 2007 */ 2008 hash_head = NIL; 2009 if (s->lookahead >= MIN_MATCH) { 2010 INSERT_STRING(s, s->strstart, has 2011 } 2012 2013 /* Find the longest match, discarding 2014 */ 2015 s->prev_length = s->match_length, s-> 2016 s->match_length = MIN_MATCH-1; 2017 2018 if (hash_head != NIL && s->prev_lengt 2019 s->strstart - hash_head <= MAX_DI 2020 /* To simplify the code, we preve 2021 * of window index 0 (in particul 2022 * of the string with itself at t 2023 */ 2024 s->match_length = longest_match ( 2025 /* longest_match() sets match_sta 2026 2027 if (s->match_length <= 5 && (s->s 2028 #if TOO_FAR <= 32767 2029 || (s->match_length == MIN_MA 2030 s->strstart - s->match_st 2031 #endif 2032 )) { 2033 2034 /* If prev_match is also MIN_ 2035 * but we will ignore the cur 2036 */ 2037 s->match_length = MIN_MATCH-1 2038 } 2039 } 2040 /* If there was a match at the previo 2041 * match is not better, output the pr 2042 */ 2043 if (s->prev_length >= MIN_MATCH && s- 2044 uInt max_insert = s->strstart + s 2045 /* Do not insert strings in hash 2046 2047 check_match(s, s->strstart - 1, s 2048 2049 _tr_tally_dist(s, s->strstart - 1 2050 s->prev_length - M 2051 2052 /* Insert in hash table all strin 2053 * strstart - 1 and strstart are 2054 * enough lookahead, the last two 2055 * the hash table. 2056 */ 2057 s->lookahead -= s->prev_length - 2058 s->prev_length -= 2; 2059 do { 2060 if (++s->strstart <= max_inse 2061 INSERT_STRING(s, s->strst 2062 } 2063 } while (--s->prev_length != 0); 2064 s->match_available = 0; 2065 s->match_length = MIN_MATCH-1; 2066 s->strstart++; 2067 2068 if (bflush) FLUSH_BLOCK(s, 0); 2069 2070 } else if (s->match_available) { 2071 /* If there was no match at the p 2072 * single literal. If there was a 2073 * is longer, truncate the previo 2074 */ 2075 Tracevv((stderr,"%c", s->window[s 2076 _tr_tally_lit(s, s->window[s->str 2077 if (bflush) { 2078 FLUSH_BLOCK_ONLY(s, 0); 2079 } 2080 s->strstart++; 2081 s->lookahead--; 2082 if (s->strm->avail_out == 0) retu 2083 } else { 2084 /* There is no previous match to 2085 * the next step to decide. 2086 */ 2087 s->match_available = 1; 2088 s->strstart++; 2089 s->lookahead--; 2090 } 2091 } 2092 Assert (flush != Z_NO_FLUSH, "no flush?") 2093 if (s->match_available) { 2094 Tracevv((stderr,"%c", s->window[s->st 2095 _tr_tally_lit(s, s->window[s->strstar 2096 s->match_available = 0; 2097 } 2098 s->insert = s->strstart < MIN_MATCH-1 ? s 2099 if (flush == Z_FINISH) { 2100 FLUSH_BLOCK(s, 1); 2101 return finish_done; 2102 } 2103 if (s->sym_next) 2104 FLUSH_BLOCK(s, 0); 2105 return block_done; 2106 } 2107 #endif /* FASTEST */ 2108 2109 /* ========================================== 2110 * For Z_RLE, simply look for runs of bytes, 2111 * one. Do not maintain a hash table. (It w 2112 * deflate switches away from Z_RLE.) 2113 */ 2114 local block_state deflate_rle(s, flush) 2115 deflate_state *s; 2116 int flush; 2117 { 2118 int bflush; /* set if current 2119 uInt prev; /* byte at distan 2120 Bytef *scan, *strend; /* scan goes up t 2121 2122 for (;;) { 2123 /* Make sure that we always have enou 2124 * at the end of the input file. We n 2125 * for the longest run, plus one for 2126 */ 2127 if (s->lookahead <= MAX_MATCH) { 2128 fill_window(s); 2129 if (s->lookahead <= MAX_MATCH && 2130 return need_more; 2131 } 2132 if (s->lookahead == 0) break; /* 2133 } 2134 2135 /* See how many times the previous by 2136 s->match_length = 0; 2137 if (s->lookahead >= MIN_MATCH && s->s 2138 scan = s->window + s->strstart - 2139 prev = *scan; 2140 if (prev == *++scan && prev == *+ 2141 strend = s->window + s->strst 2142 do { 2143 } while (prev == *++scan && p 2144 prev == *++scan && p 2145 prev == *++scan && p 2146 prev == *++scan && p 2147 scan < strend); 2148 s->match_length = MAX_MATCH - 2149 if (s->match_length > s->look 2150 s->match_length = s->look 2151 } 2152 Assert(scan <= s->window + (uInt) 2153 "wild scan"); 2154 } 2155 2156 /* Emit match if have run of MIN_MATC 2157 if (s->match_length >= MIN_MATCH) { 2158 check_match(s, s->strstart, s->st 2159 2160 _tr_tally_dist(s, 1, s->match_len 2161 2162 s->lookahead -= s->match_length; 2163 s->strstart += s->match_length; 2164 s->match_length = 0; 2165 } else { 2166 /* No match, output a literal byt 2167 Tracevv((stderr,"%c", s->window[s 2168 _tr_tally_lit(s, s->window[s->str 2169 s->lookahead--; 2170 s->strstart++; 2171 } 2172 if (bflush) FLUSH_BLOCK(s, 0); 2173 } 2174 s->insert = 0; 2175 if (flush == Z_FINISH) { 2176 FLUSH_BLOCK(s, 1); 2177 return finish_done; 2178 } 2179 if (s->sym_next) 2180 FLUSH_BLOCK(s, 0); 2181 return block_done; 2182 } 2183 2184 /* ========================================== 2185 * For Z_HUFFMAN_ONLY, do not look for matche 2186 * (It will be regenerated if this run of def 2187 */ 2188 local block_state deflate_huff(s, flush) 2189 deflate_state *s; 2190 int flush; 2191 { 2192 int bflush; /* set if current 2193 2194 for (;;) { 2195 /* Make sure that we have a literal t 2196 if (s->lookahead == 0) { 2197 fill_window(s); 2198 if (s->lookahead == 0) { 2199 if (flush == Z_NO_FLUSH) 2200 return need_more; 2201 break; /* flush the curr 2202 } 2203 } 2204 2205 /* Output a literal byte */ 2206 s->match_length = 0; 2207 Tracevv((stderr,"%c", s->window[s->st 2208 _tr_tally_lit(s, s->window[s->strstar 2209 s->lookahead--; 2210 s->strstart++; 2211 if (bflush) FLUSH_BLOCK(s, 0); 2212 } 2213 s->insert = 0; 2214 if (flush == Z_FINISH) { 2215 FLUSH_BLOCK(s, 1); 2216 return finish_done; 2217 } 2218 if (s->sym_next) 2219 FLUSH_BLOCK(s, 0); 2220 return block_done; 2221 } 2222