deflate.c revision 146081
117651Speter/* deflate.c -- compress data using the deflation algorithm 2146081Skientzle * Copyright (C) 1995-2004 Jean-loup Gailly. 3131380Stjr * For conditions of distribution and use, see copyright notice in zlib.h 417651Speter */ 517651Speter 617651Speter/* 717651Speter * ALGORITHM 817651Speter * 917651Speter * The "deflation" process depends on being able to identify portions 1017651Speter * of the input text which are identical to earlier input (within a 1117651Speter * sliding window trailing behind the input currently being processed). 1217651Speter * 1317651Speter * The most straightforward technique turns out to be the fastest for 1417651Speter * most input files: try all possible matches and select the longest. 1517651Speter * The key feature of this algorithm is that insertions into the string 1617651Speter * dictionary are very simple and thus fast, and deletions are avoided 1717651Speter * completely. Insertions are performed at each input character, whereas 1817651Speter * string matches are performed only when the previous match ends. So it 1917651Speter * is preferable to spend more time in matches to allow very fast string 2017651Speter * insertions and avoid deletions. The matching algorithm for small 2117651Speter * strings is inspired from that of Rabin & Karp. A brute force approach 2217651Speter * is used to find longer strings when a small match has been found. 2317651Speter * A similar algorithm is used in comic (by Jan-Mark Wams) and freeze 2417651Speter * (by Leonid Broukhis). 2517651Speter * A previous version of this file used a more sophisticated algorithm 2617651Speter * (by Fiala and Greene) which is guaranteed to run in linear amortized 2717651Speter * time, but has a larger average cost, uses more memory and is patented. 2817651Speter * However the F&G algorithm may be faster for some highly redundant 2917651Speter * files if the parameter max_chain_length (described below) is too large. 3017651Speter * 3117651Speter * ACKNOWLEDGEMENTS 3217651Speter * 3317651Speter * The idea of lazy evaluation of matches is due to Jan-Mark Wams, and 3417651Speter * I found it in 'freeze' written by Leonid Broukhis. 3517651Speter * Thanks to many people for bug reports and testing. 3617651Speter * 3717651Speter * REFERENCES 3817651Speter * 3933908Ssteve * Deutsch, L.P.,"DEFLATE Compressed Data Format Specification". 40131380Stjr * Available in http://www.ietf.org/rfc/rfc1951.txt 4117651Speter * 4217651Speter * A description of the Rabin and Karp algorithm is given in the book 4317651Speter * "Algorithms" by R. Sedgewick, Addison-Wesley, p252. 4417651Speter * 4517651Speter * Fiala,E.R., and Greene,D.H. 4617651Speter * Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595 4717651Speter * 4817651Speter */ 4917651Speter 50146081Skientzle/* @(#) $Id$ */ 5117651Speter 5217651Speter#include "deflate.h" 5317651Speter 5433908Ssteveconst char deflate_copyright[] = 55146081Skientzle " deflate 1.2.2 Copyright 1995-2004 Jean-loup Gailly "; 5617651Speter/* 5717651Speter If you use the zlib library in a product, an acknowledgment is welcome 5817651Speter in the documentation of your product. If for some reason you cannot 5917651Speter include such an acknowledgment, I would appreciate that you keep this 6017651Speter copyright string in the executable of your product. 6117651Speter */ 6217651Speter 6317651Speter/* =========================================================================== 6417651Speter * Function prototypes. 6517651Speter */ 6617651Spetertypedef enum { 6717651Speter need_more, /* block not completed, need more input or more output */ 6817651Speter block_done, /* block flush performed */ 6917651Speter finish_started, /* finish started, need only more output at next deflate */ 7017651Speter finish_done /* finish done, accept no more input or output */ 7117651Speter} block_state; 7217651Speter 7317651Spetertypedef block_state (*compress_func) OF((deflate_state *s, int flush)); 7417651Speter/* Compression function. Returns the block state after the call. */ 7517651Speter 7617651Speterlocal void fill_window OF((deflate_state *s)); 7717651Speterlocal block_state deflate_stored OF((deflate_state *s, int flush)); 7817651Speterlocal block_state deflate_fast OF((deflate_state *s, int flush)); 79131380Stjr#ifndef FASTEST 8017651Speterlocal block_state deflate_slow OF((deflate_state *s, int flush)); 81131380Stjr#endif 8217651Speterlocal void lm_init OF((deflate_state *s)); 8317651Speterlocal void putShortMSB OF((deflate_state *s, uInt b)); 8417651Speterlocal void flush_pending OF((z_streamp strm)); 8533908Sstevelocal int read_buf OF((z_streamp strm, Bytef *buf, unsigned size)); 86131380Stjr#ifndef FASTEST 8717651Speter#ifdef ASMV 8817651Speter void match_init OF((void)); /* asm code initialization */ 8933908Ssteve uInt longest_match OF((deflate_state *s, IPos cur_match)); 9033908Ssteve#else 9133908Sstevelocal uInt longest_match OF((deflate_state *s, IPos cur_match)); 9217651Speter#endif 93131380Stjr#endif 94131380Stjrlocal uInt longest_match_fast OF((deflate_state *s, IPos cur_match)); 9517651Speter 9617651Speter#ifdef DEBUG 9717651Speterlocal void check_match OF((deflate_state *s, IPos start, IPos match, 9817651Speter int length)); 9917651Speter#endif 10017651Speter 10117651Speter/* =========================================================================== 10217651Speter * Local data 10317651Speter */ 10417651Speter 10517651Speter#define NIL 0 10617651Speter/* Tail of hash chains */ 10717651Speter 10817651Speter#ifndef TOO_FAR 10917651Speter# define TOO_FAR 4096 11017651Speter#endif 11117651Speter/* Matches of length 3 are discarded if their distance exceeds TOO_FAR */ 11217651Speter 11317651Speter#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1) 11417651Speter/* Minimum amount of lookahead, except at the end of the input file. 11517651Speter * See deflate.c for comments about the MIN_MATCH+1. 11617651Speter */ 11717651Speter 11817651Speter/* Values for max_lazy_match, good_match and max_chain_length, depending on 11917651Speter * the desired pack level (0..9). The values given below have been tuned to 12017651Speter * exclude worst case performance for pathological files. Better values may be 12117651Speter * found for specific files. 12217651Speter */ 12317651Spetertypedef struct config_s { 12417651Speter ush good_length; /* reduce lazy search above this match length */ 12517651Speter ush max_lazy; /* do not perform lazy search above this match length */ 12617651Speter ush nice_length; /* quit search above this match length */ 12717651Speter ush max_chain; 12817651Speter compress_func func; 12917651Speter} config; 13017651Speter 131131380Stjr#ifdef FASTEST 132131380Stjrlocal const config configuration_table[2] = { 133131380Stjr/* good lazy nice chain */ 134131380Stjr/* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */ 135131380Stjr/* 1 */ {4, 4, 8, 4, deflate_fast}}; /* max speed, no lazy matches */ 136131380Stjr#else 13733908Sstevelocal const config configuration_table[10] = { 13817651Speter/* good lazy nice chain */ 13917651Speter/* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */ 140131380Stjr/* 1 */ {4, 4, 8, 4, deflate_fast}, /* max speed, no lazy matches */ 14117651Speter/* 2 */ {4, 5, 16, 8, deflate_fast}, 14217651Speter/* 3 */ {4, 6, 32, 32, deflate_fast}, 14317651Speter 14417651Speter/* 4 */ {4, 4, 16, 16, deflate_slow}, /* lazy matches */ 14517651Speter/* 5 */ {8, 16, 32, 32, deflate_slow}, 14617651Speter/* 6 */ {8, 16, 128, 128, deflate_slow}, 14717651Speter/* 7 */ {8, 32, 128, 256, deflate_slow}, 14817651Speter/* 8 */ {32, 128, 258, 1024, deflate_slow}, 149131380Stjr/* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* max compression */ 150131380Stjr#endif 15117651Speter 15217651Speter/* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4 15317651Speter * For deflate_fast() (levels <= 3) good is ignored and lazy has a different 15417651Speter * meaning. 15517651Speter */ 15617651Speter 15717651Speter#define EQUAL 0 15817651Speter/* result of memcmp for equal strings */ 15917651Speter 160131380Stjr#ifndef NO_DUMMY_DECL 16117651Speterstruct static_tree_desc_s {int dummy;}; /* for buggy compilers */ 162131380Stjr#endif 16317651Speter 16417651Speter/* =========================================================================== 16517651Speter * Update a hash value with the given input byte 16617651Speter * IN assertion: all calls to to UPDATE_HASH are made with consecutive 16717651Speter * input characters, so that a running hash key can be computed from the 16817651Speter * previous key instead of complete recalculation each time. 16917651Speter */ 17017651Speter#define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask) 17117651Speter 17217651Speter 17317651Speter/* =========================================================================== 17417651Speter * Insert string str in the dictionary and set match_head to the previous head 17517651Speter * of the hash chain (the most recent string with same hash key). Return 17617651Speter * the previous length of the hash chain. 17733908Ssteve * If this file is compiled with -DFASTEST, the compression level is forced 17833908Ssteve * to 1, and no hash chains are maintained. 17917651Speter * IN assertion: all calls to to INSERT_STRING are made with consecutive 18017651Speter * input characters and the first MIN_MATCH bytes of str are valid 18117651Speter * (except for the last MIN_MATCH-1 bytes of the input file). 18217651Speter */ 18333908Ssteve#ifdef FASTEST 18417651Speter#define INSERT_STRING(s, str, match_head) \ 18517651Speter (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \ 18633908Ssteve match_head = s->head[s->ins_h], \ 18733908Ssteve s->head[s->ins_h] = (Pos)(str)) 18833908Ssteve#else 18933908Ssteve#define INSERT_STRING(s, str, match_head) \ 19033908Ssteve (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \ 191131380Stjr match_head = s->prev[(str) & s->w_mask] = s->head[s->ins_h], \ 19217651Speter s->head[s->ins_h] = (Pos)(str)) 19333908Ssteve#endif 19417651Speter 19517651Speter/* =========================================================================== 19617651Speter * Initialize the hash table (avoiding 64K overflow for 16 bit systems). 19717651Speter * prev[] will be initialized on the fly. 19817651Speter */ 19917651Speter#define CLEAR_HASH(s) \ 20017651Speter s->head[s->hash_size-1] = NIL; \ 20133908Ssteve zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head)); 20217651Speter 20317651Speter/* ========================================================================= */ 20433908Ssteveint ZEXPORT deflateInit_(strm, level, version, stream_size) 20517651Speter z_streamp strm; 20617651Speter int level; 20717651Speter const char *version; 20817651Speter int stream_size; 20917651Speter{ 21017651Speter return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL, 211131380Stjr Z_DEFAULT_STRATEGY, version, stream_size); 21217651Speter /* To do: ignore strm->next_in if we use it as window */ 21317651Speter} 21417651Speter 21517651Speter/* ========================================================================= */ 21633908Ssteveint ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy, 217131380Stjr version, stream_size) 21817651Speter z_streamp strm; 21917651Speter int level; 22017651Speter int method; 22117651Speter int windowBits; 22217651Speter int memLevel; 22317651Speter int strategy; 22417651Speter const char *version; 22517651Speter int stream_size; 22617651Speter{ 22717651Speter deflate_state *s; 228131380Stjr int wrap = 1; 229131380Stjr static const char my_version[] = ZLIB_VERSION; 23017651Speter 23117651Speter ushf *overlay; 23217651Speter /* We overlay pending_buf and d_buf+l_buf. This works since the average 23317651Speter * output size for (length,distance) codes is <= 24 bits. 23417651Speter */ 23517651Speter 23633908Ssteve if (version == Z_NULL || version[0] != my_version[0] || 23717651Speter stream_size != sizeof(z_stream)) { 238131380Stjr return Z_VERSION_ERROR; 23917651Speter } 24017651Speter if (strm == Z_NULL) return Z_STREAM_ERROR; 24117651Speter 24217651Speter strm->msg = Z_NULL; 243131380Stjr if (strm->zalloc == (alloc_func)0) { 244131380Stjr strm->zalloc = zcalloc; 245131380Stjr strm->opaque = (voidpf)0; 24617651Speter } 247131380Stjr if (strm->zfree == (free_func)0) strm->zfree = zcfree; 24817651Speter 249131380Stjr#ifdef FASTEST 250131380Stjr if (level != 0) level = 1; 251131380Stjr#else 25217651Speter if (level == Z_DEFAULT_COMPRESSION) level = 6; 25333908Ssteve#endif 25417651Speter 255131380Stjr if (windowBits < 0) { /* suppress zlib wrapper */ 256131380Stjr wrap = 0; 25717651Speter windowBits = -windowBits; 25817651Speter } 259131380Stjr#ifdef GZIP 260131380Stjr else if (windowBits > 15) { 261131380Stjr wrap = 2; /* write gzip wrapper instead */ 262131380Stjr windowBits -= 16; 263131380Stjr } 264131380Stjr#endif 26517651Speter if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED || 266131380Stjr windowBits < 8 || windowBits > 15 || level < 0 || level > 9 || 267131380Stjr strategy < 0 || strategy > Z_RLE) { 26817651Speter return Z_STREAM_ERROR; 26917651Speter } 270131380Stjr if (windowBits == 8) windowBits = 9; /* until 256-byte window bug fixed */ 27117651Speter s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state)); 27217651Speter if (s == Z_NULL) return Z_MEM_ERROR; 27317651Speter strm->state = (struct internal_state FAR *)s; 27417651Speter s->strm = strm; 27517651Speter 276131380Stjr s->wrap = wrap; 27717651Speter s->w_bits = windowBits; 27817651Speter s->w_size = 1 << s->w_bits; 27917651Speter s->w_mask = s->w_size - 1; 28017651Speter 28117651Speter s->hash_bits = memLevel + 7; 28217651Speter s->hash_size = 1 << s->hash_bits; 28317651Speter s->hash_mask = s->hash_size - 1; 28417651Speter s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH); 28517651Speter 28617651Speter s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte)); 28717651Speter s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos)); 28817651Speter s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos)); 28917651Speter 29017651Speter s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */ 29117651Speter 29217651Speter overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2); 29317651Speter s->pending_buf = (uchf *) overlay; 29433908Ssteve s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L); 29517651Speter 29617651Speter if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL || 29717651Speter s->pending_buf == Z_NULL) { 298131380Stjr s->status = FINISH_STATE; 29917651Speter strm->msg = (char*)ERR_MSG(Z_MEM_ERROR); 30017651Speter deflateEnd (strm); 30117651Speter return Z_MEM_ERROR; 30217651Speter } 30317651Speter s->d_buf = overlay + s->lit_bufsize/sizeof(ush); 30417651Speter s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize; 30517651Speter 30617651Speter s->level = level; 30717651Speter s->strategy = strategy; 30817651Speter s->method = (Byte)method; 30917651Speter 31017651Speter return deflateReset(strm); 31117651Speter} 31217651Speter 31317651Speter/* ========================================================================= */ 31433908Ssteveint ZEXPORT deflateSetDictionary (strm, dictionary, dictLength) 31517651Speter z_streamp strm; 31617651Speter const Bytef *dictionary; 31717651Speter uInt dictLength; 31817651Speter{ 31917651Speter deflate_state *s; 32017651Speter uInt length = dictLength; 32117651Speter uInt n; 32217651Speter IPos hash_head = 0; 32317651Speter 32417651Speter if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL || 325131380Stjr strm->state->wrap == 2 || 326131380Stjr (strm->state->wrap == 1 && strm->state->status != INIT_STATE)) 327131380Stjr return Z_STREAM_ERROR; 32817651Speter 32917651Speter s = strm->state; 330131380Stjr if (s->wrap) 331131380Stjr strm->adler = adler32(strm->adler, dictionary, dictLength); 33217651Speter 33317651Speter if (length < MIN_MATCH) return Z_OK; 33417651Speter if (length > MAX_DIST(s)) { 335131380Stjr length = MAX_DIST(s); 33633908Ssteve#ifndef USE_DICT_HEAD 337131380Stjr dictionary += dictLength - length; /* use the tail of the dictionary */ 33833908Ssteve#endif 33917651Speter } 34033908Ssteve zmemcpy(s->window, dictionary, length); 34117651Speter s->strstart = length; 34217651Speter s->block_start = (long)length; 34317651Speter 34417651Speter /* Insert all strings in the hash table (except for the last two bytes). 34517651Speter * s->lookahead stays null, so s->ins_h will be recomputed at the next 34617651Speter * call of fill_window. 34717651Speter */ 34817651Speter s->ins_h = s->window[0]; 34917651Speter UPDATE_HASH(s, s->ins_h, s->window[1]); 35017651Speter for (n = 0; n <= length - MIN_MATCH; n++) { 351131380Stjr INSERT_STRING(s, n, hash_head); 35217651Speter } 35317651Speter if (hash_head) hash_head = 0; /* to make compiler happy */ 35417651Speter return Z_OK; 35517651Speter} 35617651Speter 35717651Speter/* ========================================================================= */ 35833908Ssteveint ZEXPORT deflateReset (strm) 35917651Speter z_streamp strm; 36017651Speter{ 36117651Speter deflate_state *s; 362131380Stjr 36317651Speter if (strm == Z_NULL || strm->state == Z_NULL || 364131380Stjr strm->zalloc == (alloc_func)0 || strm->zfree == (free_func)0) { 365131380Stjr return Z_STREAM_ERROR; 366131380Stjr } 36717651Speter 36817651Speter strm->total_in = strm->total_out = 0; 36917651Speter strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */ 37017651Speter strm->data_type = Z_UNKNOWN; 37117651Speter 37217651Speter s = (deflate_state *)strm->state; 37317651Speter s->pending = 0; 37417651Speter s->pending_out = s->pending_buf; 37517651Speter 376131380Stjr if (s->wrap < 0) { 377131380Stjr s->wrap = -s->wrap; /* was made negative by deflate(..., Z_FINISH); */ 37817651Speter } 379131380Stjr s->status = s->wrap ? INIT_STATE : BUSY_STATE; 380131380Stjr strm->adler = 381131380Stjr#ifdef GZIP 382131380Stjr s->wrap == 2 ? crc32(0L, Z_NULL, 0) : 383131380Stjr#endif 384131380Stjr adler32(0L, Z_NULL, 0); 38517651Speter s->last_flush = Z_NO_FLUSH; 38617651Speter 38717651Speter _tr_init(s); 38817651Speter lm_init(s); 38917651Speter 39017651Speter return Z_OK; 39117651Speter} 39217651Speter 39317651Speter/* ========================================================================= */ 394131380Stjrint ZEXPORT deflatePrime (strm, bits, value) 395131380Stjr z_streamp strm; 396131380Stjr int bits; 397131380Stjr int value; 398131380Stjr{ 399131380Stjr if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 400131380Stjr strm->state->bi_valid = bits; 401131380Stjr strm->state->bi_buf = (ush)(value & ((1 << bits) - 1)); 402131380Stjr return Z_OK; 403131380Stjr} 404131380Stjr 405131380Stjr/* ========================================================================= */ 40633908Ssteveint ZEXPORT deflateParams(strm, level, strategy) 40717651Speter z_streamp strm; 40817651Speter int level; 40917651Speter int strategy; 41017651Speter{ 41117651Speter deflate_state *s; 41217651Speter compress_func func; 41317651Speter int err = Z_OK; 41417651Speter 41517651Speter if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 41617651Speter s = strm->state; 41717651Speter 418131380Stjr#ifdef FASTEST 419131380Stjr if (level != 0) level = 1; 420131380Stjr#else 421131380Stjr if (level == Z_DEFAULT_COMPRESSION) level = 6; 422131380Stjr#endif 423131380Stjr if (level < 0 || level > 9 || strategy < 0 || strategy > Z_RLE) { 424131380Stjr return Z_STREAM_ERROR; 42517651Speter } 42617651Speter func = configuration_table[s->level].func; 42717651Speter 42817651Speter if (func != configuration_table[level].func && strm->total_in != 0) { 429131380Stjr /* Flush the last buffer: */ 430131380Stjr err = deflate(strm, Z_PARTIAL_FLUSH); 43117651Speter } 43217651Speter if (s->level != level) { 433131380Stjr s->level = level; 434131380Stjr s->max_lazy_match = configuration_table[level].max_lazy; 435131380Stjr s->good_match = configuration_table[level].good_length; 436131380Stjr s->nice_match = configuration_table[level].nice_length; 437131380Stjr s->max_chain_length = configuration_table[level].max_chain; 43817651Speter } 43917651Speter s->strategy = strategy; 44017651Speter return err; 44117651Speter} 44217651Speter 44317651Speter/* ========================================================================= 444131380Stjr * For the default windowBits of 15 and memLevel of 8, this function returns 445131380Stjr * a close to exact, as well as small, upper bound on the compressed size. 446131380Stjr * They are coded as constants here for a reason--if the #define's are 447131380Stjr * changed, then this function needs to be changed as well. The return 448131380Stjr * value for 15 and 8 only works for those exact settings. 449131380Stjr * 450131380Stjr * For any setting other than those defaults for windowBits and memLevel, 451131380Stjr * the value returned is a conservative worst case for the maximum expansion 452131380Stjr * resulting from using fixed blocks instead of stored blocks, which deflate 453131380Stjr * can emit on compressed data for some combinations of the parameters. 454131380Stjr * 455131380Stjr * This function could be more sophisticated to provide closer upper bounds 456131380Stjr * for every combination of windowBits and memLevel, as well as wrap. 457131380Stjr * But even the conservative upper bound of about 14% expansion does not 458131380Stjr * seem onerous for output buffer allocation. 459131380Stjr */ 460131380StjruLong ZEXPORT deflateBound(strm, sourceLen) 461131380Stjr z_streamp strm; 462131380Stjr uLong sourceLen; 463131380Stjr{ 464131380Stjr deflate_state *s; 465131380Stjr uLong destLen; 466131380Stjr 467131380Stjr /* conservative upper bound */ 468131380Stjr destLen = sourceLen + 469131380Stjr ((sourceLen + 7) >> 3) + ((sourceLen + 63) >> 6) + 11; 470131380Stjr 471131380Stjr /* if can't get parameters, return conservative bound */ 472131380Stjr if (strm == Z_NULL || strm->state == Z_NULL) 473131380Stjr return destLen; 474131380Stjr 475131380Stjr /* if not default parameters, return conservative bound */ 476131380Stjr s = strm->state; 477131380Stjr if (s->w_bits != 15 || s->hash_bits != 8 + 7) 478131380Stjr return destLen; 479131380Stjr 480131380Stjr /* default settings: return tight bound for that case */ 481131380Stjr return compressBound(sourceLen); 482131380Stjr} 483131380Stjr 484131380Stjr/* ========================================================================= 48517651Speter * Put a short in the pending buffer. The 16-bit value is put in MSB order. 48617651Speter * IN assertion: the stream state is correct and there is enough room in 48717651Speter * pending_buf. 48817651Speter */ 48917651Speterlocal void putShortMSB (s, b) 49017651Speter deflate_state *s; 49117651Speter uInt b; 49217651Speter{ 49317651Speter put_byte(s, (Byte)(b >> 8)); 49417651Speter put_byte(s, (Byte)(b & 0xff)); 495131380Stjr} 49617651Speter 49717651Speter/* ========================================================================= 49817651Speter * Flush as much pending output as possible. All deflate() output goes 49917651Speter * through this function so some applications may wish to modify it 50017651Speter * to avoid allocating a large strm->next_out buffer and copying into it. 50117651Speter * (See also read_buf()). 50217651Speter */ 50317651Speterlocal void flush_pending(strm) 50417651Speter z_streamp strm; 50517651Speter{ 50617651Speter unsigned len = strm->state->pending; 50717651Speter 50817651Speter if (len > strm->avail_out) len = strm->avail_out; 50917651Speter if (len == 0) return; 51017651Speter 51117651Speter zmemcpy(strm->next_out, strm->state->pending_out, len); 51217651Speter strm->next_out += len; 51317651Speter strm->state->pending_out += len; 51417651Speter strm->total_out += len; 51517651Speter strm->avail_out -= len; 51617651Speter strm->state->pending -= len; 51717651Speter if (strm->state->pending == 0) { 51817651Speter strm->state->pending_out = strm->state->pending_buf; 51917651Speter } 52017651Speter} 52117651Speter 52217651Speter/* ========================================================================= */ 52333908Ssteveint ZEXPORT deflate (strm, flush) 52417651Speter z_streamp strm; 52517651Speter int flush; 52617651Speter{ 52717651Speter int old_flush; /* value of flush param for previous deflate call */ 52817651Speter deflate_state *s; 52917651Speter 53017651Speter if (strm == Z_NULL || strm->state == Z_NULL || 531131380Stjr flush > Z_FINISH || flush < 0) { 53217651Speter return Z_STREAM_ERROR; 53317651Speter } 53417651Speter s = strm->state; 53517651Speter 53617651Speter if (strm->next_out == Z_NULL || 53717651Speter (strm->next_in == Z_NULL && strm->avail_in != 0) || 538131380Stjr (s->status == FINISH_STATE && flush != Z_FINISH)) { 53917651Speter ERR_RETURN(strm, Z_STREAM_ERROR); 54017651Speter } 54117651Speter if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR); 54217651Speter 54317651Speter s->strm = strm; /* just in case */ 54417651Speter old_flush = s->last_flush; 54517651Speter s->last_flush = flush; 54617651Speter 547131380Stjr /* Write the header */ 54817651Speter if (s->status == INIT_STATE) { 549131380Stjr#ifdef GZIP 550131380Stjr if (s->wrap == 2) { 551131380Stjr put_byte(s, 31); 552131380Stjr put_byte(s, 139); 553131380Stjr put_byte(s, 8); 554131380Stjr put_byte(s, 0); 555131380Stjr put_byte(s, 0); 556131380Stjr put_byte(s, 0); 557131380Stjr put_byte(s, 0); 558131380Stjr put_byte(s, 0); 559131380Stjr put_byte(s, s->level == 9 ? 2 : 560131380Stjr (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ? 561131380Stjr 4 : 0)); 562131380Stjr put_byte(s, 255); 563131380Stjr s->status = BUSY_STATE; 564131380Stjr strm->adler = crc32(0L, Z_NULL, 0); 565131380Stjr } 566131380Stjr else 567131380Stjr#endif 568131380Stjr { 569131380Stjr uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8; 570131380Stjr uInt level_flags; 57117651Speter 572131380Stjr if (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2) 573131380Stjr level_flags = 0; 574131380Stjr else if (s->level < 6) 575131380Stjr level_flags = 1; 576131380Stjr else if (s->level == 6) 577131380Stjr level_flags = 2; 578131380Stjr else 579131380Stjr level_flags = 3; 580131380Stjr header |= (level_flags << 6); 581131380Stjr if (s->strstart != 0) header |= PRESET_DICT; 582131380Stjr header += 31 - (header % 31); 58317651Speter 584131380Stjr s->status = BUSY_STATE; 585131380Stjr putShortMSB(s, header); 58617651Speter 587131380Stjr /* Save the adler32 of the preset dictionary: */ 588131380Stjr if (s->strstart != 0) { 589131380Stjr putShortMSB(s, (uInt)(strm->adler >> 16)); 590131380Stjr putShortMSB(s, (uInt)(strm->adler & 0xffff)); 591131380Stjr } 592131380Stjr strm->adler = adler32(0L, Z_NULL, 0); 593131380Stjr } 59417651Speter } 59517651Speter 59617651Speter /* Flush as much pending output as possible */ 59717651Speter if (s->pending != 0) { 59817651Speter flush_pending(strm); 59917651Speter if (strm->avail_out == 0) { 600131380Stjr /* Since avail_out is 0, deflate will be called again with 601131380Stjr * more output space, but possibly with both pending and 602131380Stjr * avail_in equal to zero. There won't be anything to do, 603131380Stjr * but this is not an error situation so make sure we 604131380Stjr * return OK instead of BUF_ERROR at next call of deflate: 60517651Speter */ 606131380Stjr s->last_flush = -1; 607131380Stjr return Z_OK; 608131380Stjr } 60917651Speter 61017651Speter /* Make sure there is something to do and avoid duplicate consecutive 61117651Speter * flushes. For repeated and useless calls with Z_FINISH, we keep 612131380Stjr * returning Z_STREAM_END instead of Z_BUF_ERROR. 61317651Speter */ 61417651Speter } else if (strm->avail_in == 0 && flush <= old_flush && 615131380Stjr flush != Z_FINISH) { 61617651Speter ERR_RETURN(strm, Z_BUF_ERROR); 61717651Speter } 61817651Speter 61917651Speter /* User must not provide more input after the first FINISH: */ 62017651Speter if (s->status == FINISH_STATE && strm->avail_in != 0) { 62117651Speter ERR_RETURN(strm, Z_BUF_ERROR); 62217651Speter } 62317651Speter 62417651Speter /* Start a new block or continue the current one. 62517651Speter */ 62617651Speter if (strm->avail_in != 0 || s->lookahead != 0 || 62717651Speter (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) { 62817651Speter block_state bstate; 62917651Speter 630131380Stjr bstate = (*(configuration_table[s->level].func))(s, flush); 63117651Speter 63217651Speter if (bstate == finish_started || bstate == finish_done) { 63317651Speter s->status = FINISH_STATE; 63417651Speter } 63517651Speter if (bstate == need_more || bstate == finish_started) { 636131380Stjr if (strm->avail_out == 0) { 637131380Stjr s->last_flush = -1; /* avoid BUF_ERROR next call, see above */ 638131380Stjr } 639131380Stjr return Z_OK; 640131380Stjr /* If flush != Z_NO_FLUSH && avail_out == 0, the next call 641131380Stjr * of deflate should use the same flush parameter to make sure 642131380Stjr * that the flush is complete. So we don't have to output an 643131380Stjr * empty block here, this will be done at next call. This also 644131380Stjr * ensures that for a very small output buffer, we emit at most 645131380Stjr * one empty block. 646131380Stjr */ 647131380Stjr } 64817651Speter if (bstate == block_done) { 64917651Speter if (flush == Z_PARTIAL_FLUSH) { 65017651Speter _tr_align(s); 65117651Speter } else { /* FULL_FLUSH or SYNC_FLUSH */ 65217651Speter _tr_stored_block(s, (char*)0, 0L, 0); 65317651Speter /* For a full flush, this empty block will be recognized 65417651Speter * as a special marker by inflate_sync(). 65517651Speter */ 65617651Speter if (flush == Z_FULL_FLUSH) { 65717651Speter CLEAR_HASH(s); /* forget history */ 65817651Speter } 65917651Speter } 66017651Speter flush_pending(strm); 661131380Stjr if (strm->avail_out == 0) { 662131380Stjr s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */ 663131380Stjr return Z_OK; 664131380Stjr } 66517651Speter } 66617651Speter } 66717651Speter Assert(strm->avail_out > 0, "bug2"); 66817651Speter 66917651Speter if (flush != Z_FINISH) return Z_OK; 670131380Stjr if (s->wrap <= 0) return Z_STREAM_END; 67117651Speter 672131380Stjr /* Write the trailer */ 673131380Stjr#ifdef GZIP 674131380Stjr if (s->wrap == 2) { 675131380Stjr put_byte(s, (Byte)(strm->adler & 0xff)); 676131380Stjr put_byte(s, (Byte)((strm->adler >> 8) & 0xff)); 677131380Stjr put_byte(s, (Byte)((strm->adler >> 16) & 0xff)); 678131380Stjr put_byte(s, (Byte)((strm->adler >> 24) & 0xff)); 679131380Stjr put_byte(s, (Byte)(strm->total_in & 0xff)); 680131380Stjr put_byte(s, (Byte)((strm->total_in >> 8) & 0xff)); 681131380Stjr put_byte(s, (Byte)((strm->total_in >> 16) & 0xff)); 682131380Stjr put_byte(s, (Byte)((strm->total_in >> 24) & 0xff)); 683131380Stjr } 684131380Stjr else 685131380Stjr#endif 686131380Stjr { 687131380Stjr putShortMSB(s, (uInt)(strm->adler >> 16)); 688131380Stjr putShortMSB(s, (uInt)(strm->adler & 0xffff)); 689131380Stjr } 69017651Speter flush_pending(strm); 69117651Speter /* If avail_out is zero, the application will call deflate again 69217651Speter * to flush the rest. 69317651Speter */ 694131380Stjr if (s->wrap > 0) s->wrap = -s->wrap; /* write the trailer only once! */ 69517651Speter return s->pending != 0 ? Z_OK : Z_STREAM_END; 69617651Speter} 69717651Speter 69817651Speter/* ========================================================================= */ 69933908Ssteveint ZEXPORT deflateEnd (strm) 70017651Speter z_streamp strm; 70117651Speter{ 70217651Speter int status; 70317651Speter 70417651Speter if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 70517651Speter 70633908Ssteve status = strm->state->status; 70733908Ssteve if (status != INIT_STATE && status != BUSY_STATE && 708131380Stjr status != FINISH_STATE) { 70933908Ssteve return Z_STREAM_ERROR; 71033908Ssteve } 71133908Ssteve 71217651Speter /* Deallocate in reverse order of allocations: */ 71317651Speter TRY_FREE(strm, strm->state->pending_buf); 71417651Speter TRY_FREE(strm, strm->state->head); 71517651Speter TRY_FREE(strm, strm->state->prev); 71617651Speter TRY_FREE(strm, strm->state->window); 71717651Speter 71817651Speter ZFREE(strm, strm->state); 71917651Speter strm->state = Z_NULL; 72017651Speter 72117651Speter return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK; 72217651Speter} 72317651Speter 72433908Ssteve/* ========================================================================= 72533908Ssteve * Copy the source state to the destination state. 72633908Ssteve * To simplify the source, this is not supported for 16-bit MSDOS (which 72733908Ssteve * doesn't have enough memory anyway to duplicate compression states). 72833908Ssteve */ 72933908Ssteveint ZEXPORT deflateCopy (dest, source) 73017651Speter z_streamp dest; 73117651Speter z_streamp source; 73217651Speter{ 73333908Ssteve#ifdef MAXSEG_64K 73433908Ssteve return Z_STREAM_ERROR; 73533908Ssteve#else 73633908Ssteve deflate_state *ds; 73733908Ssteve deflate_state *ss; 73833908Ssteve ushf *overlay; 73933908Ssteve 74033908Ssteve 74142471Speter if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL) { 74217651Speter return Z_STREAM_ERROR; 74317651Speter } 74442471Speter 74542471Speter ss = source->state; 74642471Speter 74717651Speter *dest = *source; 74817651Speter 74933908Ssteve ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state)); 75033908Ssteve if (ds == Z_NULL) return Z_MEM_ERROR; 75133908Ssteve dest->state = (struct internal_state FAR *) ds; 75233908Ssteve *ds = *ss; 75333908Ssteve ds->strm = dest; 75433908Ssteve 75533908Ssteve ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte)); 75633908Ssteve ds->prev = (Posf *) ZALLOC(dest, ds->w_size, sizeof(Pos)); 75733908Ssteve ds->head = (Posf *) ZALLOC(dest, ds->hash_size, sizeof(Pos)); 75833908Ssteve overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof(ush)+2); 75933908Ssteve ds->pending_buf = (uchf *) overlay; 76033908Ssteve 76133908Ssteve if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL || 76233908Ssteve ds->pending_buf == Z_NULL) { 76333908Ssteve deflateEnd (dest); 76433908Ssteve return Z_MEM_ERROR; 76533908Ssteve } 76633908Ssteve /* following zmemcpy do not work for 16-bit MSDOS */ 76733908Ssteve zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte)); 76833908Ssteve zmemcpy(ds->prev, ss->prev, ds->w_size * sizeof(Pos)); 76933908Ssteve zmemcpy(ds->head, ss->head, ds->hash_size * sizeof(Pos)); 77033908Ssteve zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size); 77133908Ssteve 77233908Ssteve ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf); 77333908Ssteve ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush); 77433908Ssteve ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize; 77533908Ssteve 77633908Ssteve ds->l_desc.dyn_tree = ds->dyn_ltree; 77733908Ssteve ds->d_desc.dyn_tree = ds->dyn_dtree; 77833908Ssteve ds->bl_desc.dyn_tree = ds->bl_tree; 77933908Ssteve 78017651Speter return Z_OK; 781131380Stjr#endif /* MAXSEG_64K */ 78217651Speter} 78317651Speter 78417651Speter/* =========================================================================== 78517651Speter * Read a new buffer from the current input stream, update the adler32 78617651Speter * and total number of bytes read. All deflate() input goes through 78717651Speter * this function so some applications may wish to modify it to avoid 78817651Speter * allocating a large strm->next_in buffer and copying from it. 78917651Speter * (See also flush_pending()). 79017651Speter */ 79117651Speterlocal int read_buf(strm, buf, size) 79217651Speter z_streamp strm; 79333908Ssteve Bytef *buf; 79417651Speter unsigned size; 79517651Speter{ 79617651Speter unsigned len = strm->avail_in; 79717651Speter 79817651Speter if (len > size) len = size; 79917651Speter if (len == 0) return 0; 80017651Speter 80117651Speter strm->avail_in -= len; 80217651Speter 803131380Stjr if (strm->state->wrap == 1) { 80417651Speter strm->adler = adler32(strm->adler, strm->next_in, len); 80517651Speter } 806131380Stjr#ifdef GZIP 807131380Stjr else if (strm->state->wrap == 2) { 808131380Stjr strm->adler = crc32(strm->adler, strm->next_in, len); 809131380Stjr } 810131380Stjr#endif 81117651Speter zmemcpy(buf, strm->next_in, len); 81217651Speter strm->next_in += len; 81317651Speter strm->total_in += len; 81417651Speter 81517651Speter return (int)len; 81617651Speter} 81717651Speter 81817651Speter/* =========================================================================== 81917651Speter * Initialize the "longest match" routines for a new zlib stream 82017651Speter */ 82117651Speterlocal void lm_init (s) 82217651Speter deflate_state *s; 82317651Speter{ 82417651Speter s->window_size = (ulg)2L*s->w_size; 82517651Speter 82617651Speter CLEAR_HASH(s); 82717651Speter 82817651Speter /* Set the default configuration parameters: 82917651Speter */ 83017651Speter s->max_lazy_match = configuration_table[s->level].max_lazy; 83117651Speter s->good_match = configuration_table[s->level].good_length; 83217651Speter s->nice_match = configuration_table[s->level].nice_length; 83317651Speter s->max_chain_length = configuration_table[s->level].max_chain; 83417651Speter 83517651Speter s->strstart = 0; 83617651Speter s->block_start = 0L; 83717651Speter s->lookahead = 0; 83817651Speter s->match_length = s->prev_length = MIN_MATCH-1; 83917651Speter s->match_available = 0; 84017651Speter s->ins_h = 0; 84117651Speter#ifdef ASMV 84217651Speter match_init(); /* initialize the asm code */ 84317651Speter#endif 84417651Speter} 84517651Speter 846131380Stjr#ifndef FASTEST 84717651Speter/* =========================================================================== 84817651Speter * Set match_start to the longest match starting at the given string and 84917651Speter * return its length. Matches shorter or equal to prev_length are discarded, 85017651Speter * in which case the result is equal to prev_length and match_start is 85117651Speter * garbage. 85217651Speter * IN assertions: cur_match is the head of the hash chain for the current 85317651Speter * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1 85417651Speter * OUT assertion: the match length is not greater than s->lookahead. 85517651Speter */ 85617651Speter#ifndef ASMV 85717651Speter/* For 80x86 and 680x0, an optimized version will be provided in match.asm or 85817651Speter * match.S. The code will be functionally equivalent. 85917651Speter */ 86017651Speterlocal uInt longest_match(s, cur_match) 86117651Speter deflate_state *s; 86217651Speter IPos cur_match; /* current match */ 86317651Speter{ 86417651Speter unsigned chain_length = s->max_chain_length;/* max hash chain length */ 86517651Speter register Bytef *scan = s->window + s->strstart; /* current string */ 86617651Speter register Bytef *match; /* matched string */ 86717651Speter register int len; /* length of current match */ 86817651Speter int best_len = s->prev_length; /* best match length so far */ 86917651Speter int nice_match = s->nice_match; /* stop if match long enough */ 87017651Speter IPos limit = s->strstart > (IPos)MAX_DIST(s) ? 87117651Speter s->strstart - (IPos)MAX_DIST(s) : NIL; 87217651Speter /* Stop when cur_match becomes <= limit. To simplify the code, 87317651Speter * we prevent matches with the string of window index 0. 87417651Speter */ 87517651Speter Posf *prev = s->prev; 87617651Speter uInt wmask = s->w_mask; 87717651Speter 87817651Speter#ifdef UNALIGNED_OK 87917651Speter /* Compare two bytes at a time. Note: this is not always beneficial. 88017651Speter * Try with and without -DUNALIGNED_OK to check. 88117651Speter */ 88217651Speter register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1; 88317651Speter register ush scan_start = *(ushf*)scan; 88417651Speter register ush scan_end = *(ushf*)(scan+best_len-1); 88517651Speter#else 88617651Speter register Bytef *strend = s->window + s->strstart + MAX_MATCH; 88717651Speter register Byte scan_end1 = scan[best_len-1]; 88817651Speter register Byte scan_end = scan[best_len]; 88917651Speter#endif 89017651Speter 89117651Speter /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. 89217651Speter * It is easy to get rid of this optimization if necessary. 89317651Speter */ 89417651Speter Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever"); 89517651Speter 89617651Speter /* Do not waste too much time if we already have a good match: */ 89717651Speter if (s->prev_length >= s->good_match) { 89817651Speter chain_length >>= 2; 89917651Speter } 90017651Speter /* Do not look for matches beyond the end of the input. This is necessary 90117651Speter * to make deflate deterministic. 90217651Speter */ 90317651Speter if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead; 90417651Speter 90517651Speter Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead"); 90617651Speter 90717651Speter do { 90817651Speter Assert(cur_match < s->strstart, "no future"); 90917651Speter match = s->window + cur_match; 91017651Speter 91117651Speter /* Skip to next match if the match length cannot increase 91217651Speter * or if the match length is less than 2: 91317651Speter */ 91417651Speter#if (defined(UNALIGNED_OK) && MAX_MATCH == 258) 91517651Speter /* This code assumes sizeof(unsigned short) == 2. Do not use 91617651Speter * UNALIGNED_OK if your compiler uses a different size. 91717651Speter */ 91817651Speter if (*(ushf*)(match+best_len-1) != scan_end || 91917651Speter *(ushf*)match != scan_start) continue; 92017651Speter 92117651Speter /* It is not necessary to compare scan[2] and match[2] since they are 92217651Speter * always equal when the other bytes match, given that the hash keys 92317651Speter * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at 92417651Speter * strstart+3, +5, ... up to strstart+257. We check for insufficient 92517651Speter * lookahead only every 4th comparison; the 128th check will be made 92617651Speter * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is 92717651Speter * necessary to put more guard bytes at the end of the window, or 92817651Speter * to check more often for insufficient lookahead. 92917651Speter */ 93017651Speter Assert(scan[2] == match[2], "scan[2]?"); 93117651Speter scan++, match++; 93217651Speter do { 93317651Speter } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) && 93417651Speter *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 93517651Speter *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 93617651Speter *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 93717651Speter scan < strend); 93817651Speter /* The funny "do {}" generates better code on most compilers */ 93917651Speter 94017651Speter /* Here, scan <= window+strstart+257 */ 94117651Speter Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 94217651Speter if (*scan == *match) scan++; 94317651Speter 94417651Speter len = (MAX_MATCH - 1) - (int)(strend-scan); 94517651Speter scan = strend - (MAX_MATCH-1); 94617651Speter 94717651Speter#else /* UNALIGNED_OK */ 94817651Speter 94917651Speter if (match[best_len] != scan_end || 95017651Speter match[best_len-1] != scan_end1 || 95117651Speter *match != *scan || 95217651Speter *++match != scan[1]) continue; 95317651Speter 95417651Speter /* The check at best_len-1 can be removed because it will be made 95517651Speter * again later. (This heuristic is not always a win.) 95617651Speter * It is not necessary to compare scan[2] and match[2] since they 95717651Speter * are always equal when the other bytes match, given that 95817651Speter * the hash keys are equal and that HASH_BITS >= 8. 95917651Speter */ 96017651Speter scan += 2, match++; 96117651Speter Assert(*scan == *match, "match[2]?"); 96217651Speter 96317651Speter /* We check for insufficient lookahead only every 8th comparison; 96417651Speter * the 256th check will be made at strstart+258. 96517651Speter */ 96617651Speter do { 96717651Speter } while (*++scan == *++match && *++scan == *++match && 96817651Speter *++scan == *++match && *++scan == *++match && 96917651Speter *++scan == *++match && *++scan == *++match && 97017651Speter *++scan == *++match && *++scan == *++match && 97117651Speter scan < strend); 97217651Speter 97317651Speter Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 97417651Speter 97517651Speter len = MAX_MATCH - (int)(strend - scan); 97617651Speter scan = strend - MAX_MATCH; 97717651Speter 97817651Speter#endif /* UNALIGNED_OK */ 97917651Speter 98017651Speter if (len > best_len) { 98117651Speter s->match_start = cur_match; 98217651Speter best_len = len; 98317651Speter if (len >= nice_match) break; 98417651Speter#ifdef UNALIGNED_OK 98517651Speter scan_end = *(ushf*)(scan+best_len-1); 98617651Speter#else 98717651Speter scan_end1 = scan[best_len-1]; 98817651Speter scan_end = scan[best_len]; 98917651Speter#endif 99017651Speter } 99117651Speter } while ((cur_match = prev[cur_match & wmask]) > limit 99217651Speter && --chain_length != 0); 99317651Speter 99433908Ssteve if ((uInt)best_len <= s->lookahead) return (uInt)best_len; 99517651Speter return s->lookahead; 99617651Speter} 997131380Stjr#endif /* ASMV */ 998131380Stjr#endif /* FASTEST */ 99933908Ssteve 100033908Ssteve/* --------------------------------------------------------------------------- 1001131380Stjr * Optimized version for level == 1 or strategy == Z_RLE only 100233908Ssteve */ 1003131380Stjrlocal uInt longest_match_fast(s, cur_match) 100433908Ssteve deflate_state *s; 100533908Ssteve IPos cur_match; /* current match */ 100633908Ssteve{ 100733908Ssteve register Bytef *scan = s->window + s->strstart; /* current string */ 100833908Ssteve register Bytef *match; /* matched string */ 100933908Ssteve register int len; /* length of current match */ 101033908Ssteve register Bytef *strend = s->window + s->strstart + MAX_MATCH; 101133908Ssteve 101233908Ssteve /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. 101333908Ssteve * It is easy to get rid of this optimization if necessary. 101433908Ssteve */ 101533908Ssteve Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever"); 101633908Ssteve 101733908Ssteve Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead"); 101833908Ssteve 101933908Ssteve Assert(cur_match < s->strstart, "no future"); 102033908Ssteve 102133908Ssteve match = s->window + cur_match; 102233908Ssteve 102333908Ssteve /* Return failure if the match length is less than 2: 102433908Ssteve */ 102533908Ssteve if (match[0] != scan[0] || match[1] != scan[1]) return MIN_MATCH-1; 102633908Ssteve 102733908Ssteve /* The check at best_len-1 can be removed because it will be made 102833908Ssteve * again later. (This heuristic is not always a win.) 102933908Ssteve * It is not necessary to compare scan[2] and match[2] since they 103033908Ssteve * are always equal when the other bytes match, given that 103133908Ssteve * the hash keys are equal and that HASH_BITS >= 8. 103233908Ssteve */ 103333908Ssteve scan += 2, match += 2; 103433908Ssteve Assert(*scan == *match, "match[2]?"); 103533908Ssteve 103633908Ssteve /* We check for insufficient lookahead only every 8th comparison; 103733908Ssteve * the 256th check will be made at strstart+258. 103833908Ssteve */ 103933908Ssteve do { 104033908Ssteve } while (*++scan == *++match && *++scan == *++match && 1041131380Stjr *++scan == *++match && *++scan == *++match && 1042131380Stjr *++scan == *++match && *++scan == *++match && 1043131380Stjr *++scan == *++match && *++scan == *++match && 1044131380Stjr scan < strend); 104533908Ssteve 104633908Ssteve Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 104733908Ssteve 104833908Ssteve len = MAX_MATCH - (int)(strend - scan); 104933908Ssteve 105033908Ssteve if (len < MIN_MATCH) return MIN_MATCH - 1; 105133908Ssteve 105233908Ssteve s->match_start = cur_match; 1053131380Stjr return (uInt)len <= s->lookahead ? (uInt)len : s->lookahead; 105433908Ssteve} 105517651Speter 105617651Speter#ifdef DEBUG 105717651Speter/* =========================================================================== 105817651Speter * Check that the match at match_start is indeed a match. 105917651Speter */ 106017651Speterlocal void check_match(s, start, match, length) 106117651Speter deflate_state *s; 106217651Speter IPos start, match; 106317651Speter int length; 106417651Speter{ 106517651Speter /* check that the match is indeed a match */ 106633908Ssteve if (zmemcmp(s->window + match, 106733908Ssteve s->window + start, length) != EQUAL) { 106817651Speter fprintf(stderr, " start %u, match %u, length %d\n", 1069131380Stjr start, match, length); 107017651Speter do { 1071131380Stjr fprintf(stderr, "%c%c", s->window[match++], s->window[start++]); 1072131380Stjr } while (--length != 0); 107317651Speter z_error("invalid match"); 107417651Speter } 107533908Ssteve if (z_verbose > 1) { 107617651Speter fprintf(stderr,"\\[%d,%d]", start-match, length); 107717651Speter do { putc(s->window[start++], stderr); } while (--length != 0); 107817651Speter } 107917651Speter} 108017651Speter#else 108117651Speter# define check_match(s, start, match, length) 1082131380Stjr#endif /* DEBUG */ 108317651Speter 108417651Speter/* =========================================================================== 108517651Speter * Fill the window when the lookahead becomes insufficient. 108617651Speter * Updates strstart and lookahead. 108717651Speter * 108817651Speter * IN assertion: lookahead < MIN_LOOKAHEAD 108917651Speter * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD 109017651Speter * At least one byte has been read, or avail_in == 0; reads are 109117651Speter * performed for at least two bytes (required for the zip translate_eol 109217651Speter * option -- not supported here). 109317651Speter */ 109417651Speterlocal void fill_window(s) 109517651Speter deflate_state *s; 109617651Speter{ 109717651Speter register unsigned n, m; 109817651Speter register Posf *p; 109917651Speter unsigned more; /* Amount of free space at the end of the window. */ 110017651Speter uInt wsize = s->w_size; 110117651Speter 110217651Speter do { 110317651Speter more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart); 110417651Speter 110517651Speter /* Deal with !@#$% 64K limit: */ 1106131380Stjr if (sizeof(int) <= 2) { 1107131380Stjr if (more == 0 && s->strstart == 0 && s->lookahead == 0) { 1108131380Stjr more = wsize; 110917651Speter 1110131380Stjr } else if (more == (unsigned)(-1)) { 1111131380Stjr /* Very unlikely, but possible on 16 bit machine if 1112131380Stjr * strstart == 0 && lookahead == 1 (input done a byte at time) 1113131380Stjr */ 1114131380Stjr more--; 1115131380Stjr } 1116131380Stjr } 111717651Speter 111817651Speter /* If the window is almost full and there is insufficient lookahead, 111917651Speter * move the upper half to the lower one to make room in the upper half. 112017651Speter */ 1121131380Stjr if (s->strstart >= wsize+MAX_DIST(s)) { 112217651Speter 112333908Ssteve zmemcpy(s->window, s->window+wsize, (unsigned)wsize); 112417651Speter s->match_start -= wsize; 112517651Speter s->strstart -= wsize; /* we now have strstart >= MAX_DIST */ 112617651Speter s->block_start -= (long) wsize; 112717651Speter 112817651Speter /* Slide the hash table (could be avoided with 32 bit values 112933908Ssteve at the expense of memory usage). We slide even when level == 0 113033908Ssteve to keep the hash table consistent if we switch back to level > 0 113133908Ssteve later. (Using level 0 permanently is not an optimal usage of 113233908Ssteve zlib, so we don't care about this pathological case.) 113317651Speter */ 1134131380Stjr n = s->hash_size; 1135131380Stjr p = &s->head[n]; 1136131380Stjr do { 1137131380Stjr m = *--p; 1138131380Stjr *p = (Pos)(m >= wsize ? m-wsize : NIL); 1139131380Stjr } while (--n); 114017651Speter 1141131380Stjr n = wsize; 114233908Ssteve#ifndef FASTEST 1143131380Stjr p = &s->prev[n]; 1144131380Stjr do { 1145131380Stjr m = *--p; 1146131380Stjr *p = (Pos)(m >= wsize ? m-wsize : NIL); 1147131380Stjr /* If n is not on any hash chain, prev[n] is garbage but 1148131380Stjr * its value will never be used. 1149131380Stjr */ 1150131380Stjr } while (--n); 115133908Ssteve#endif 115217651Speter more += wsize; 115317651Speter } 115417651Speter if (s->strm->avail_in == 0) return; 115517651Speter 115617651Speter /* If there was no sliding: 115717651Speter * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 && 115817651Speter * more == window_size - lookahead - strstart 115917651Speter * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1) 116017651Speter * => more >= window_size - 2*WSIZE + 2 116117651Speter * In the BIG_MEM or MMAP case (not yet supported), 116217651Speter * window_size == input_size + MIN_LOOKAHEAD && 116317651Speter * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD. 116417651Speter * Otherwise, window_size == 2*WSIZE so more >= 2. 116517651Speter * If there was sliding, more >= WSIZE. So in all cases, more >= 2. 116617651Speter */ 116717651Speter Assert(more >= 2, "more < 2"); 116817651Speter 116933908Ssteve n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more); 117017651Speter s->lookahead += n; 117117651Speter 117217651Speter /* Initialize the hash value now that we have some input: */ 117317651Speter if (s->lookahead >= MIN_MATCH) { 117417651Speter s->ins_h = s->window[s->strstart]; 117517651Speter UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]); 117617651Speter#if MIN_MATCH != 3 117717651Speter Call UPDATE_HASH() MIN_MATCH-3 more times 117817651Speter#endif 117917651Speter } 118017651Speter /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage, 118117651Speter * but this is not important since only literal bytes will be emitted. 118217651Speter */ 118317651Speter 118417651Speter } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0); 118517651Speter} 118617651Speter 118717651Speter/* =========================================================================== 118817651Speter * Flush the current block, with given end-of-file flag. 118917651Speter * IN assertion: strstart is set to the end of the current match. 119017651Speter */ 119117651Speter#define FLUSH_BLOCK_ONLY(s, eof) { \ 119217651Speter _tr_flush_block(s, (s->block_start >= 0L ? \ 119317651Speter (charf *)&s->window[(unsigned)s->block_start] : \ 119417651Speter (charf *)Z_NULL), \ 1195131380Stjr (ulg)((long)s->strstart - s->block_start), \ 1196131380Stjr (eof)); \ 119717651Speter s->block_start = s->strstart; \ 119817651Speter flush_pending(s->strm); \ 119917651Speter Tracev((stderr,"[FLUSH]")); \ 120017651Speter} 120117651Speter 120217651Speter/* Same but force premature exit if necessary. */ 120317651Speter#define FLUSH_BLOCK(s, eof) { \ 120417651Speter FLUSH_BLOCK_ONLY(s, eof); \ 120517651Speter if (s->strm->avail_out == 0) return (eof) ? finish_started : need_more; \ 120617651Speter} 120717651Speter 120817651Speter/* =========================================================================== 120917651Speter * Copy without compression as much as possible from the input stream, return 121017651Speter * the current block state. 121117651Speter * This function does not insert new strings in the dictionary since 121217651Speter * uncompressible data is probably not useful. This function is used 121317651Speter * only for the level=0 compression option. 121433908Ssteve * NOTE: this function should be optimized to avoid extra copying from 121533908Ssteve * window to pending_buf. 121617651Speter */ 121717651Speterlocal block_state deflate_stored(s, flush) 121817651Speter deflate_state *s; 121917651Speter int flush; 122017651Speter{ 122133908Ssteve /* Stored blocks are limited to 0xffff bytes, pending_buf is limited 122233908Ssteve * to pending_buf_size, and each stored block has a 5 byte header: 122333908Ssteve */ 122433908Ssteve ulg max_block_size = 0xffff; 122533908Ssteve ulg max_start; 122633908Ssteve 122733908Ssteve if (max_block_size > s->pending_buf_size - 5) { 122833908Ssteve max_block_size = s->pending_buf_size - 5; 122933908Ssteve } 123033908Ssteve 123133908Ssteve /* Copy as much as possible from input to output: */ 123217651Speter for (;;) { 123317651Speter /* Fill the window as much as possible: */ 123417651Speter if (s->lookahead <= 1) { 123517651Speter 123617651Speter Assert(s->strstart < s->w_size+MAX_DIST(s) || 1237131380Stjr s->block_start >= (long)s->w_size, "slide too late"); 123817651Speter 123917651Speter fill_window(s); 124017651Speter if (s->lookahead == 0 && flush == Z_NO_FLUSH) return need_more; 124117651Speter 124217651Speter if (s->lookahead == 0) break; /* flush the current block */ 124317651Speter } 1244131380Stjr Assert(s->block_start >= 0L, "block gone"); 124517651Speter 1246131380Stjr s->strstart += s->lookahead; 1247131380Stjr s->lookahead = 0; 124817651Speter 1249131380Stjr /* Emit a stored block if pending_buf will be full: */ 1250131380Stjr max_start = s->block_start + max_block_size; 125133908Ssteve if (s->strstart == 0 || (ulg)s->strstart >= max_start) { 1252131380Stjr /* strstart == 0 is possible when wraparound on 16-bit machine */ 1253131380Stjr s->lookahead = (uInt)(s->strstart - max_start); 1254131380Stjr s->strstart = (uInt)max_start; 125533908Ssteve FLUSH_BLOCK(s, 0); 1256131380Stjr } 1257131380Stjr /* Flush if we may have to slide, otherwise block_start may become 125833908Ssteve * negative and the data will be gone: 125933908Ssteve */ 126017651Speter if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) { 126117651Speter FLUSH_BLOCK(s, 0); 1262131380Stjr } 126317651Speter } 126417651Speter FLUSH_BLOCK(s, flush == Z_FINISH); 126517651Speter return flush == Z_FINISH ? finish_done : block_done; 126617651Speter} 126717651Speter 126817651Speter/* =========================================================================== 126917651Speter * Compress as much as possible from the input stream, return the current 127017651Speter * block state. 127117651Speter * This function does not perform lazy evaluation of matches and inserts 127217651Speter * new strings in the dictionary only for unmatched strings or for short 127317651Speter * matches. It is used only for the fast compression options. 127417651Speter */ 127517651Speterlocal block_state deflate_fast(s, flush) 127617651Speter deflate_state *s; 127717651Speter int flush; 127817651Speter{ 127917651Speter IPos hash_head = NIL; /* head of the hash chain */ 128017651Speter int bflush; /* set if current block must be flushed */ 128117651Speter 128217651Speter for (;;) { 128317651Speter /* Make sure that we always have enough lookahead, except 128417651Speter * at the end of the input file. We need MAX_MATCH bytes 128517651Speter * for the next match, plus MIN_MATCH bytes to insert the 128617651Speter * string following the next match. 128717651Speter */ 128817651Speter if (s->lookahead < MIN_LOOKAHEAD) { 128917651Speter fill_window(s); 129017651Speter if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { 1291131380Stjr return need_more; 1292131380Stjr } 129317651Speter if (s->lookahead == 0) break; /* flush the current block */ 129417651Speter } 129517651Speter 129617651Speter /* Insert the string window[strstart .. strstart+2] in the 129717651Speter * dictionary, and set hash_head to the head of the hash chain: 129817651Speter */ 129917651Speter if (s->lookahead >= MIN_MATCH) { 130017651Speter INSERT_STRING(s, s->strstart, hash_head); 130117651Speter } 130217651Speter 130317651Speter /* Find the longest match, discarding those <= prev_length. 130417651Speter * At this point we have always match_length < MIN_MATCH 130517651Speter */ 130617651Speter if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) { 130717651Speter /* To simplify the code, we prevent matches with the string 130817651Speter * of window index 0 (in particular we have to avoid a match 130917651Speter * of the string with itself at the start of the input file). 131017651Speter */ 1311131380Stjr#ifdef FASTEST 1312131380Stjr if ((s->strategy < Z_HUFFMAN_ONLY) || 1313131380Stjr (s->strategy == Z_RLE && s->strstart - hash_head == 1)) { 1314131380Stjr s->match_length = longest_match_fast (s, hash_head); 1315131380Stjr } 1316131380Stjr#else 1317131380Stjr if (s->strategy < Z_HUFFMAN_ONLY) { 131817651Speter s->match_length = longest_match (s, hash_head); 1319131380Stjr } else if (s->strategy == Z_RLE && s->strstart - hash_head == 1) { 1320131380Stjr s->match_length = longest_match_fast (s, hash_head); 132117651Speter } 1322131380Stjr#endif 1323131380Stjr /* longest_match() or longest_match_fast() sets match_start */ 132417651Speter } 132517651Speter if (s->match_length >= MIN_MATCH) { 132617651Speter check_match(s, s->strstart, s->match_start, s->match_length); 132717651Speter 132833908Ssteve _tr_tally_dist(s, s->strstart - s->match_start, 132933908Ssteve s->match_length - MIN_MATCH, bflush); 133017651Speter 133117651Speter s->lookahead -= s->match_length; 133217651Speter 133317651Speter /* Insert new strings in the hash table only if the match length 133417651Speter * is not too large. This saves time but degrades compression. 133517651Speter */ 133633908Ssteve#ifndef FASTEST 133717651Speter if (s->match_length <= s->max_insert_length && 133817651Speter s->lookahead >= MIN_MATCH) { 1339131380Stjr s->match_length--; /* string at strstart already in table */ 134017651Speter do { 134117651Speter s->strstart++; 134217651Speter INSERT_STRING(s, s->strstart, hash_head); 134317651Speter /* strstart never exceeds WSIZE-MAX_MATCH, so there are 134417651Speter * always MIN_MATCH bytes ahead. 134517651Speter */ 134617651Speter } while (--s->match_length != 0); 1347131380Stjr s->strstart++; 134833908Ssteve } else 134933908Ssteve#endif 1350131380Stjr { 135117651Speter s->strstart += s->match_length; 135217651Speter s->match_length = 0; 135317651Speter s->ins_h = s->window[s->strstart]; 135417651Speter UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]); 135517651Speter#if MIN_MATCH != 3 135617651Speter Call UPDATE_HASH() MIN_MATCH-3 more times 135717651Speter#endif 135817651Speter /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not 135917651Speter * matter since it will be recomputed at next deflate call. 136017651Speter */ 136117651Speter } 136217651Speter } else { 136317651Speter /* No match, output a literal byte */ 136417651Speter Tracevv((stderr,"%c", s->window[s->strstart])); 136533908Ssteve _tr_tally_lit (s, s->window[s->strstart], bflush); 136617651Speter s->lookahead--; 1367131380Stjr s->strstart++; 136817651Speter } 136917651Speter if (bflush) FLUSH_BLOCK(s, 0); 137017651Speter } 137117651Speter FLUSH_BLOCK(s, flush == Z_FINISH); 137217651Speter return flush == Z_FINISH ? finish_done : block_done; 137317651Speter} 137417651Speter 1375131380Stjr#ifndef FASTEST 137617651Speter/* =========================================================================== 137717651Speter * Same as above, but achieves better compression. We use a lazy 137817651Speter * evaluation for matches: a match is finally adopted only if there is 137917651Speter * no better match at the next window position. 138017651Speter */ 138117651Speterlocal block_state deflate_slow(s, flush) 138217651Speter deflate_state *s; 138317651Speter int flush; 138417651Speter{ 138517651Speter IPos hash_head = NIL; /* head of hash chain */ 138617651Speter int bflush; /* set if current block must be flushed */ 138717651Speter 138817651Speter /* Process the input block. */ 138917651Speter for (;;) { 139017651Speter /* Make sure that we always have enough lookahead, except 139117651Speter * at the end of the input file. We need MAX_MATCH bytes 139217651Speter * for the next match, plus MIN_MATCH bytes to insert the 139317651Speter * string following the next match. 139417651Speter */ 139517651Speter if (s->lookahead < MIN_LOOKAHEAD) { 139617651Speter fill_window(s); 139717651Speter if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { 1398131380Stjr return need_more; 1399131380Stjr } 140017651Speter if (s->lookahead == 0) break; /* flush the current block */ 140117651Speter } 140217651Speter 140317651Speter /* Insert the string window[strstart .. strstart+2] in the 140417651Speter * dictionary, and set hash_head to the head of the hash chain: 140517651Speter */ 140617651Speter if (s->lookahead >= MIN_MATCH) { 140717651Speter INSERT_STRING(s, s->strstart, hash_head); 140817651Speter } 140917651Speter 141017651Speter /* Find the longest match, discarding those <= prev_length. 141117651Speter */ 141217651Speter s->prev_length = s->match_length, s->prev_match = s->match_start; 141317651Speter s->match_length = MIN_MATCH-1; 141417651Speter 141517651Speter if (hash_head != NIL && s->prev_length < s->max_lazy_match && 141617651Speter s->strstart - hash_head <= MAX_DIST(s)) { 141717651Speter /* To simplify the code, we prevent matches with the string 141817651Speter * of window index 0 (in particular we have to avoid a match 141917651Speter * of the string with itself at the start of the input file). 142017651Speter */ 1421131380Stjr if (s->strategy < Z_HUFFMAN_ONLY) { 142217651Speter s->match_length = longest_match (s, hash_head); 1423131380Stjr } else if (s->strategy == Z_RLE && s->strstart - hash_head == 1) { 1424131380Stjr s->match_length = longest_match_fast (s, hash_head); 142517651Speter } 1426131380Stjr /* longest_match() or longest_match_fast() sets match_start */ 142717651Speter 1428131380Stjr if (s->match_length <= 5 && (s->strategy == Z_FILTERED 1429131380Stjr#if TOO_FAR <= 32767 1430131380Stjr || (s->match_length == MIN_MATCH && 1431131380Stjr s->strstart - s->match_start > TOO_FAR) 1432131380Stjr#endif 1433131380Stjr )) { 143417651Speter 143517651Speter /* If prev_match is also MIN_MATCH, match_start is garbage 143617651Speter * but we will ignore the current match anyway. 143717651Speter */ 143817651Speter s->match_length = MIN_MATCH-1; 143917651Speter } 144017651Speter } 144117651Speter /* If there was a match at the previous step and the current 144217651Speter * match is not better, output the previous match: 144317651Speter */ 144417651Speter if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) { 144517651Speter uInt max_insert = s->strstart + s->lookahead - MIN_MATCH; 144617651Speter /* Do not insert strings in hash table beyond this. */ 144717651Speter 144817651Speter check_match(s, s->strstart-1, s->prev_match, s->prev_length); 144917651Speter 145033908Ssteve _tr_tally_dist(s, s->strstart -1 - s->prev_match, 1451131380Stjr s->prev_length - MIN_MATCH, bflush); 145217651Speter 145317651Speter /* Insert in hash table all strings up to the end of the match. 145417651Speter * strstart-1 and strstart are already inserted. If there is not 145517651Speter * enough lookahead, the last two strings are not inserted in 145617651Speter * the hash table. 145717651Speter */ 145817651Speter s->lookahead -= s->prev_length-1; 145917651Speter s->prev_length -= 2; 146017651Speter do { 146117651Speter if (++s->strstart <= max_insert) { 146217651Speter INSERT_STRING(s, s->strstart, hash_head); 146317651Speter } 146417651Speter } while (--s->prev_length != 0); 146517651Speter s->match_available = 0; 146617651Speter s->match_length = MIN_MATCH-1; 146717651Speter s->strstart++; 146817651Speter 146917651Speter if (bflush) FLUSH_BLOCK(s, 0); 147017651Speter 147117651Speter } else if (s->match_available) { 147217651Speter /* If there was no match at the previous position, output a 147317651Speter * single literal. If there was a match but the current match 147417651Speter * is longer, truncate the previous match to a single literal. 147517651Speter */ 147617651Speter Tracevv((stderr,"%c", s->window[s->strstart-1])); 1477131380Stjr _tr_tally_lit(s, s->window[s->strstart-1], bflush); 1478131380Stjr if (bflush) { 147917651Speter FLUSH_BLOCK_ONLY(s, 0); 148017651Speter } 148117651Speter s->strstart++; 148217651Speter s->lookahead--; 148317651Speter if (s->strm->avail_out == 0) return need_more; 148417651Speter } else { 148517651Speter /* There is no previous match to compare with, wait for 148617651Speter * the next step to decide. 148717651Speter */ 148817651Speter s->match_available = 1; 148917651Speter s->strstart++; 149017651Speter s->lookahead--; 149117651Speter } 149217651Speter } 149317651Speter Assert (flush != Z_NO_FLUSH, "no flush?"); 149417651Speter if (s->match_available) { 149517651Speter Tracevv((stderr,"%c", s->window[s->strstart-1])); 149633908Ssteve _tr_tally_lit(s, s->window[s->strstart-1], bflush); 149717651Speter s->match_available = 0; 149817651Speter } 149917651Speter FLUSH_BLOCK(s, flush == Z_FINISH); 150017651Speter return flush == Z_FINISH ? finish_done : block_done; 150117651Speter} 1502131380Stjr#endif /* FASTEST */ 1503