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