deflate.c revision 237410
117651Speter/* deflate.c -- compress data using the deflation algorithm 2237410Sdelphij * Copyright (C) 1995-2012 Jean-loup Gailly and Mark Adler 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". 40237410Sdelphij * Available in http://tools.ietf.org/html/rfc1951 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[] = 55237410Sdelphij " deflate 1.2.7 Copyright 1995-2012 Jean-loup Gailly and Mark Adler "; 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 82205471Sdelphijlocal block_state deflate_rle OF((deflate_state *s, int flush)); 83205471Sdelphijlocal block_state deflate_huff OF((deflate_state *s, int flush)); 8417651Speterlocal void lm_init OF((deflate_state *s)); 8517651Speterlocal void putShortMSB OF((deflate_state *s, uInt b)); 8617651Speterlocal void flush_pending OF((z_streamp strm)); 8733908Sstevelocal int read_buf OF((z_streamp strm, Bytef *buf, unsigned size)); 8817651Speter#ifdef ASMV 8917651Speter void match_init OF((void)); /* asm code initialization */ 9033908Ssteve uInt longest_match OF((deflate_state *s, IPos cur_match)); 9133908Ssteve#else 9233908Sstevelocal uInt longest_match OF((deflate_state *s, IPos cur_match)); 9317651Speter#endif 9417651Speter 9517651Speter#ifdef DEBUG 9617651Speterlocal void check_match OF((deflate_state *s, IPos start, IPos match, 9717651Speter int length)); 9817651Speter#endif 9917651Speter 10017651Speter/* =========================================================================== 10117651Speter * Local data 10217651Speter */ 10317651Speter 10417651Speter#define NIL 0 10517651Speter/* Tail of hash chains */ 10617651Speter 10717651Speter#ifndef TOO_FAR 10817651Speter# define TOO_FAR 4096 10917651Speter#endif 11017651Speter/* Matches of length 3 are discarded if their distance exceeds TOO_FAR */ 11117651Speter 11217651Speter/* Values for max_lazy_match, good_match and max_chain_length, depending on 11317651Speter * the desired pack level (0..9). The values given below have been tuned to 11417651Speter * exclude worst case performance for pathological files. Better values may be 11517651Speter * found for specific files. 11617651Speter */ 11717651Spetertypedef struct config_s { 11817651Speter ush good_length; /* reduce lazy search above this match length */ 11917651Speter ush max_lazy; /* do not perform lazy search above this match length */ 12017651Speter ush nice_length; /* quit search above this match length */ 12117651Speter ush max_chain; 12217651Speter compress_func func; 12317651Speter} config; 12417651Speter 125131380Stjr#ifdef FASTEST 126131380Stjrlocal const config configuration_table[2] = { 127131380Stjr/* good lazy nice chain */ 128131380Stjr/* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */ 129131380Stjr/* 1 */ {4, 4, 8, 4, deflate_fast}}; /* max speed, no lazy matches */ 130131380Stjr#else 13133908Sstevelocal const config configuration_table[10] = { 13217651Speter/* good lazy nice chain */ 13317651Speter/* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */ 134131380Stjr/* 1 */ {4, 4, 8, 4, deflate_fast}, /* max speed, no lazy matches */ 13517651Speter/* 2 */ {4, 5, 16, 8, deflate_fast}, 13617651Speter/* 3 */ {4, 6, 32, 32, deflate_fast}, 13717651Speter 13817651Speter/* 4 */ {4, 4, 16, 16, deflate_slow}, /* lazy matches */ 13917651Speter/* 5 */ {8, 16, 32, 32, deflate_slow}, 14017651Speter/* 6 */ {8, 16, 128, 128, deflate_slow}, 14117651Speter/* 7 */ {8, 32, 128, 256, deflate_slow}, 14217651Speter/* 8 */ {32, 128, 258, 1024, deflate_slow}, 143131380Stjr/* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* max compression */ 144131380Stjr#endif 14517651Speter 14617651Speter/* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4 14717651Speter * For deflate_fast() (levels <= 3) good is ignored and lazy has a different 14817651Speter * meaning. 14917651Speter */ 15017651Speter 15117651Speter#define EQUAL 0 15217651Speter/* result of memcmp for equal strings */ 15317651Speter 154131380Stjr#ifndef NO_DUMMY_DECL 15517651Speterstruct static_tree_desc_s {int dummy;}; /* for buggy compilers */ 156131380Stjr#endif 15717651Speter 158237410Sdelphij/* rank Z_BLOCK between Z_NO_FLUSH and Z_PARTIAL_FLUSH */ 159237410Sdelphij#define RANK(f) (((f) << 1) - ((f) > 4 ? 9 : 0)) 160237410Sdelphij 16117651Speter/* =========================================================================== 16217651Speter * Update a hash value with the given input byte 16317651Speter * IN assertion: all calls to to UPDATE_HASH are made with consecutive 16417651Speter * input characters, so that a running hash key can be computed from the 16517651Speter * previous key instead of complete recalculation each time. 16617651Speter */ 16717651Speter#define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask) 16817651Speter 16917651Speter 17017651Speter/* =========================================================================== 17117651Speter * Insert string str in the dictionary and set match_head to the previous head 17217651Speter * of the hash chain (the most recent string with same hash key). Return 17317651Speter * the previous length of the hash chain. 17433908Ssteve * If this file is compiled with -DFASTEST, the compression level is forced 17533908Ssteve * to 1, and no hash chains are maintained. 17617651Speter * IN assertion: all calls to to INSERT_STRING are made with consecutive 17717651Speter * input characters and the first MIN_MATCH bytes of str are valid 17817651Speter * (except for the last MIN_MATCH-1 bytes of the input file). 17917651Speter */ 18033908Ssteve#ifdef FASTEST 18117651Speter#define INSERT_STRING(s, str, match_head) \ 18217651Speter (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \ 18333908Ssteve match_head = s->head[s->ins_h], \ 18433908Ssteve s->head[s->ins_h] = (Pos)(str)) 18533908Ssteve#else 18633908Ssteve#define INSERT_STRING(s, str, match_head) \ 18733908Ssteve (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \ 188131380Stjr match_head = s->prev[(str) & s->w_mask] = s->head[s->ins_h], \ 18917651Speter s->head[s->ins_h] = (Pos)(str)) 19033908Ssteve#endif 19117651Speter 19217651Speter/* =========================================================================== 19317651Speter * Initialize the hash table (avoiding 64K overflow for 16 bit systems). 19417651Speter * prev[] will be initialized on the fly. 19517651Speter */ 19617651Speter#define CLEAR_HASH(s) \ 19717651Speter s->head[s->hash_size-1] = NIL; \ 19833908Ssteve zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head)); 19917651Speter 20017651Speter/* ========================================================================= */ 20133908Ssteveint ZEXPORT deflateInit_(strm, level, version, stream_size) 20217651Speter z_streamp strm; 20317651Speter int level; 20417651Speter const char *version; 20517651Speter int stream_size; 20617651Speter{ 20717651Speter return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL, 208131380Stjr Z_DEFAULT_STRATEGY, version, stream_size); 20917651Speter /* To do: ignore strm->next_in if we use it as window */ 21017651Speter} 21117651Speter 21217651Speter/* ========================================================================= */ 21333908Ssteveint ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy, 214131380Stjr version, stream_size) 21517651Speter z_streamp strm; 21617651Speter int level; 21717651Speter int method; 21817651Speter int windowBits; 21917651Speter int memLevel; 22017651Speter int strategy; 22117651Speter const char *version; 22217651Speter int stream_size; 22317651Speter{ 22417651Speter deflate_state *s; 225131380Stjr int wrap = 1; 226131380Stjr static const char my_version[] = ZLIB_VERSION; 22717651Speter 22817651Speter ushf *overlay; 22917651Speter /* We overlay pending_buf and d_buf+l_buf. This works since the average 23017651Speter * output size for (length,distance) codes is <= 24 bits. 23117651Speter */ 23217651Speter 23333908Ssteve if (version == Z_NULL || version[0] != my_version[0] || 23417651Speter stream_size != sizeof(z_stream)) { 235131380Stjr return Z_VERSION_ERROR; 23617651Speter } 23717651Speter if (strm == Z_NULL) return Z_STREAM_ERROR; 23817651Speter 23917651Speter strm->msg = Z_NULL; 240131380Stjr if (strm->zalloc == (alloc_func)0) { 241237410Sdelphij#ifdef Z_SOLO 242237410Sdelphij return Z_STREAM_ERROR; 243237410Sdelphij#else 244131380Stjr strm->zalloc = zcalloc; 245131380Stjr strm->opaque = (voidpf)0; 246237410Sdelphij#endif 24717651Speter } 248237410Sdelphij if (strm->zfree == (free_func)0) 249237410Sdelphij#ifdef Z_SOLO 250237410Sdelphij return Z_STREAM_ERROR; 251237410Sdelphij#else 252237410Sdelphij strm->zfree = zcfree; 253237410Sdelphij#endif 25417651Speter 255131380Stjr#ifdef FASTEST 256131380Stjr if (level != 0) level = 1; 257131380Stjr#else 25817651Speter if (level == Z_DEFAULT_COMPRESSION) level = 6; 25933908Ssteve#endif 26017651Speter 261131380Stjr if (windowBits < 0) { /* suppress zlib wrapper */ 262131380Stjr wrap = 0; 26317651Speter windowBits = -windowBits; 26417651Speter } 265131380Stjr#ifdef GZIP 266131380Stjr else if (windowBits > 15) { 267131380Stjr wrap = 2; /* write gzip wrapper instead */ 268131380Stjr windowBits -= 16; 269131380Stjr } 270131380Stjr#endif 27117651Speter if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED || 272131380Stjr windowBits < 8 || windowBits > 15 || level < 0 || level > 9 || 273157046Sdes strategy < 0 || strategy > Z_FIXED) { 27417651Speter return Z_STREAM_ERROR; 27517651Speter } 276131380Stjr if (windowBits == 8) windowBits = 9; /* until 256-byte window bug fixed */ 27717651Speter s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state)); 27817651Speter if (s == Z_NULL) return Z_MEM_ERROR; 27917651Speter strm->state = (struct internal_state FAR *)s; 28017651Speter s->strm = strm; 28117651Speter 282131380Stjr s->wrap = wrap; 283157046Sdes s->gzhead = Z_NULL; 28417651Speter s->w_bits = windowBits; 28517651Speter s->w_size = 1 << s->w_bits; 28617651Speter s->w_mask = s->w_size - 1; 28717651Speter 28817651Speter s->hash_bits = memLevel + 7; 28917651Speter s->hash_size = 1 << s->hash_bits; 29017651Speter s->hash_mask = s->hash_size - 1; 29117651Speter s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH); 29217651Speter 29317651Speter s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte)); 29417651Speter s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos)); 29517651Speter s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos)); 29617651Speter 297205471Sdelphij s->high_water = 0; /* nothing written to s->window yet */ 298205471Sdelphij 29917651Speter s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */ 30017651Speter 30117651Speter overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2); 30217651Speter s->pending_buf = (uchf *) overlay; 30333908Ssteve s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L); 30417651Speter 30517651Speter if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL || 30617651Speter s->pending_buf == Z_NULL) { 307131380Stjr s->status = FINISH_STATE; 30817651Speter strm->msg = (char*)ERR_MSG(Z_MEM_ERROR); 30917651Speter deflateEnd (strm); 31017651Speter return Z_MEM_ERROR; 31117651Speter } 31217651Speter s->d_buf = overlay + s->lit_bufsize/sizeof(ush); 31317651Speter s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize; 31417651Speter 31517651Speter s->level = level; 31617651Speter s->strategy = strategy; 31717651Speter s->method = (Byte)method; 31817651Speter 31917651Speter return deflateReset(strm); 32017651Speter} 32117651Speter 32217651Speter/* ========================================================================= */ 32333908Ssteveint ZEXPORT deflateSetDictionary (strm, dictionary, dictLength) 32417651Speter z_streamp strm; 32517651Speter const Bytef *dictionary; 32617651Speter uInt dictLength; 32717651Speter{ 32817651Speter deflate_state *s; 329237410Sdelphij uInt str, n; 330237410Sdelphij int wrap; 331237410Sdelphij unsigned avail; 332237410Sdelphij unsigned char *next; 33317651Speter 334237410Sdelphij if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL) 335131380Stjr return Z_STREAM_ERROR; 336237410Sdelphij s = strm->state; 337237410Sdelphij wrap = s->wrap; 338237410Sdelphij if (wrap == 2 || (wrap == 1 && s->status != INIT_STATE) || s->lookahead) 339237410Sdelphij return Z_STREAM_ERROR; 34017651Speter 341237410Sdelphij /* when using zlib wrappers, compute Adler-32 for provided dictionary */ 342237410Sdelphij if (wrap == 1) 343131380Stjr strm->adler = adler32(strm->adler, dictionary, dictLength); 344237410Sdelphij s->wrap = 0; /* avoid computing Adler-32 in read_buf */ 34517651Speter 346237410Sdelphij /* if dictionary would fill window, just replace the history */ 347237410Sdelphij if (dictLength >= s->w_size) { 348237410Sdelphij if (wrap == 0) { /* already empty otherwise */ 349237410Sdelphij CLEAR_HASH(s); 350237410Sdelphij s->strstart = 0; 351237410Sdelphij s->block_start = 0L; 352237410Sdelphij s->insert = 0; 353237410Sdelphij } 354237410Sdelphij dictionary += dictLength - s->w_size; /* use the tail */ 355237410Sdelphij dictLength = s->w_size; 35617651Speter } 35717651Speter 358237410Sdelphij /* insert dictionary into window and hash */ 359237410Sdelphij avail = strm->avail_in; 360237410Sdelphij next = strm->next_in; 361237410Sdelphij strm->avail_in = dictLength; 362237410Sdelphij strm->next_in = (Bytef *)dictionary; 363237410Sdelphij fill_window(s); 364237410Sdelphij while (s->lookahead >= MIN_MATCH) { 365237410Sdelphij str = s->strstart; 366237410Sdelphij n = s->lookahead - (MIN_MATCH-1); 367237410Sdelphij do { 368237410Sdelphij UPDATE_HASH(s, s->ins_h, s->window[str + MIN_MATCH-1]); 369237410Sdelphij#ifndef FASTEST 370237410Sdelphij s->prev[str & s->w_mask] = s->head[s->ins_h]; 371237410Sdelphij#endif 372237410Sdelphij s->head[s->ins_h] = (Pos)str; 373237410Sdelphij str++; 374237410Sdelphij } while (--n); 375237410Sdelphij s->strstart = str; 376237410Sdelphij s->lookahead = MIN_MATCH-1; 377237410Sdelphij fill_window(s); 37817651Speter } 379237410Sdelphij s->strstart += s->lookahead; 380237410Sdelphij s->block_start = (long)s->strstart; 381237410Sdelphij s->insert = s->lookahead; 382237410Sdelphij s->lookahead = 0; 383237410Sdelphij s->match_length = s->prev_length = MIN_MATCH-1; 384237410Sdelphij s->match_available = 0; 385237410Sdelphij strm->next_in = next; 386237410Sdelphij strm->avail_in = avail; 387237410Sdelphij s->wrap = wrap; 38817651Speter return Z_OK; 38917651Speter} 39017651Speter 39117651Speter/* ========================================================================= */ 392237410Sdelphijint ZEXPORT deflateResetKeep (strm) 39317651Speter z_streamp strm; 39417651Speter{ 39517651Speter deflate_state *s; 396131380Stjr 39717651Speter if (strm == Z_NULL || strm->state == Z_NULL || 398131380Stjr strm->zalloc == (alloc_func)0 || strm->zfree == (free_func)0) { 399131380Stjr return Z_STREAM_ERROR; 400131380Stjr } 40117651Speter 40217651Speter strm->total_in = strm->total_out = 0; 40317651Speter strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */ 40417651Speter strm->data_type = Z_UNKNOWN; 40517651Speter 40617651Speter s = (deflate_state *)strm->state; 40717651Speter s->pending = 0; 40817651Speter s->pending_out = s->pending_buf; 40917651Speter 410131380Stjr if (s->wrap < 0) { 411131380Stjr s->wrap = -s->wrap; /* was made negative by deflate(..., Z_FINISH); */ 41217651Speter } 413131380Stjr s->status = s->wrap ? INIT_STATE : BUSY_STATE; 414131380Stjr strm->adler = 415131380Stjr#ifdef GZIP 416131380Stjr s->wrap == 2 ? crc32(0L, Z_NULL, 0) : 417131380Stjr#endif 418131380Stjr adler32(0L, Z_NULL, 0); 41917651Speter s->last_flush = Z_NO_FLUSH; 42017651Speter 42117651Speter _tr_init(s); 42217651Speter 42317651Speter return Z_OK; 42417651Speter} 42517651Speter 42617651Speter/* ========================================================================= */ 427237410Sdelphijint ZEXPORT deflateReset (strm) 428237410Sdelphij z_streamp strm; 429237410Sdelphij{ 430237410Sdelphij int ret; 431237410Sdelphij 432237410Sdelphij ret = deflateResetKeep(strm); 433237410Sdelphij if (ret == Z_OK) 434237410Sdelphij lm_init(strm->state); 435237410Sdelphij return ret; 436237410Sdelphij} 437237410Sdelphij 438237410Sdelphij/* ========================================================================= */ 439157046Sdesint ZEXPORT deflateSetHeader (strm, head) 440157046Sdes z_streamp strm; 441157046Sdes gz_headerp head; 442157046Sdes{ 443157046Sdes if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 444157046Sdes if (strm->state->wrap != 2) return Z_STREAM_ERROR; 445157046Sdes strm->state->gzhead = head; 446157046Sdes return Z_OK; 447157046Sdes} 448157046Sdes 449157046Sdes/* ========================================================================= */ 450237410Sdelphijint ZEXPORT deflatePending (strm, pending, bits) 451237410Sdelphij unsigned *pending; 452237410Sdelphij int *bits; 453237410Sdelphij z_streamp strm; 454237410Sdelphij{ 455237410Sdelphij if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 456237410Sdelphij if (pending != Z_NULL) 457237410Sdelphij *pending = strm->state->pending; 458237410Sdelphij if (bits != Z_NULL) 459237410Sdelphij *bits = strm->state->bi_valid; 460237410Sdelphij return Z_OK; 461237410Sdelphij} 462237410Sdelphij 463237410Sdelphij/* ========================================================================= */ 464131380Stjrint ZEXPORT deflatePrime (strm, bits, value) 465131380Stjr z_streamp strm; 466131380Stjr int bits; 467131380Stjr int value; 468131380Stjr{ 469237410Sdelphij deflate_state *s; 470237410Sdelphij int put; 471237410Sdelphij 472131380Stjr if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 473237410Sdelphij s = strm->state; 474237410Sdelphij if ((Bytef *)(s->d_buf) < s->pending_out + ((Buf_size + 7) >> 3)) 475237410Sdelphij return Z_BUF_ERROR; 476237410Sdelphij do { 477237410Sdelphij put = Buf_size - s->bi_valid; 478237410Sdelphij if (put > bits) 479237410Sdelphij put = bits; 480237410Sdelphij s->bi_buf |= (ush)((value & ((1 << put) - 1)) << s->bi_valid); 481237410Sdelphij s->bi_valid += put; 482237410Sdelphij _tr_flush_bits(s); 483237410Sdelphij value >>= put; 484237410Sdelphij bits -= put; 485237410Sdelphij } while (bits); 486131380Stjr return Z_OK; 487131380Stjr} 488131380Stjr 489131380Stjr/* ========================================================================= */ 49033908Ssteveint ZEXPORT deflateParams(strm, level, strategy) 49117651Speter z_streamp strm; 49217651Speter int level; 49317651Speter int strategy; 49417651Speter{ 49517651Speter deflate_state *s; 49617651Speter compress_func func; 49717651Speter int err = Z_OK; 49817651Speter 49917651Speter if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 50017651Speter s = strm->state; 50117651Speter 502131380Stjr#ifdef FASTEST 503131380Stjr if (level != 0) level = 1; 504131380Stjr#else 505131380Stjr if (level == Z_DEFAULT_COMPRESSION) level = 6; 506131380Stjr#endif 507157046Sdes if (level < 0 || level > 9 || strategy < 0 || strategy > Z_FIXED) { 508131380Stjr return Z_STREAM_ERROR; 50917651Speter } 51017651Speter func = configuration_table[s->level].func; 51117651Speter 512205471Sdelphij if ((strategy != s->strategy || func != configuration_table[level].func) && 513205471Sdelphij strm->total_in != 0) { 514131380Stjr /* Flush the last buffer: */ 515205471Sdelphij err = deflate(strm, Z_BLOCK); 51617651Speter } 51717651Speter if (s->level != level) { 518131380Stjr s->level = level; 519131380Stjr s->max_lazy_match = configuration_table[level].max_lazy; 520131380Stjr s->good_match = configuration_table[level].good_length; 521131380Stjr s->nice_match = configuration_table[level].nice_length; 522131380Stjr s->max_chain_length = configuration_table[level].max_chain; 52317651Speter } 52417651Speter s->strategy = strategy; 52517651Speter return err; 52617651Speter} 52717651Speter 528157046Sdes/* ========================================================================= */ 529157046Sdesint ZEXPORT deflateTune(strm, good_length, max_lazy, nice_length, max_chain) 530157046Sdes z_streamp strm; 531157046Sdes int good_length; 532157046Sdes int max_lazy; 533157046Sdes int nice_length; 534157046Sdes int max_chain; 535157046Sdes{ 536157046Sdes deflate_state *s; 537157046Sdes 538157046Sdes if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 539157046Sdes s = strm->state; 540157046Sdes s->good_match = good_length; 541157046Sdes s->max_lazy_match = max_lazy; 542157046Sdes s->nice_match = nice_length; 543157046Sdes s->max_chain_length = max_chain; 544157046Sdes return Z_OK; 545157046Sdes} 546157046Sdes 54717651Speter/* ========================================================================= 548131380Stjr * For the default windowBits of 15 and memLevel of 8, this function returns 549131380Stjr * a close to exact, as well as small, upper bound on the compressed size. 550131380Stjr * They are coded as constants here for a reason--if the #define's are 551131380Stjr * changed, then this function needs to be changed as well. The return 552131380Stjr * value for 15 and 8 only works for those exact settings. 553131380Stjr * 554131380Stjr * For any setting other than those defaults for windowBits and memLevel, 555131380Stjr * the value returned is a conservative worst case for the maximum expansion 556131380Stjr * resulting from using fixed blocks instead of stored blocks, which deflate 557131380Stjr * can emit on compressed data for some combinations of the parameters. 558131380Stjr * 559205471Sdelphij * This function could be more sophisticated to provide closer upper bounds for 560205471Sdelphij * every combination of windowBits and memLevel. But even the conservative 561205471Sdelphij * upper bound of about 14% expansion does not seem onerous for output buffer 562205471Sdelphij * allocation. 563131380Stjr */ 564131380StjruLong ZEXPORT deflateBound(strm, sourceLen) 565131380Stjr z_streamp strm; 566131380Stjr uLong sourceLen; 567131380Stjr{ 568131380Stjr deflate_state *s; 569205471Sdelphij uLong complen, wraplen; 570205471Sdelphij Bytef *str; 571131380Stjr 572205471Sdelphij /* conservative upper bound for compressed data */ 573205471Sdelphij complen = sourceLen + 574205471Sdelphij ((sourceLen + 7) >> 3) + ((sourceLen + 63) >> 6) + 5; 575131380Stjr 576205471Sdelphij /* if can't get parameters, return conservative bound plus zlib wrapper */ 577131380Stjr if (strm == Z_NULL || strm->state == Z_NULL) 578205471Sdelphij return complen + 6; 579131380Stjr 580205471Sdelphij /* compute wrapper length */ 581205471Sdelphij s = strm->state; 582205471Sdelphij switch (s->wrap) { 583205471Sdelphij case 0: /* raw deflate */ 584205471Sdelphij wraplen = 0; 585205471Sdelphij break; 586205471Sdelphij case 1: /* zlib wrapper */ 587205471Sdelphij wraplen = 6 + (s->strstart ? 4 : 0); 588205471Sdelphij break; 589205471Sdelphij case 2: /* gzip wrapper */ 590205471Sdelphij wraplen = 18; 591205471Sdelphij if (s->gzhead != Z_NULL) { /* user-supplied gzip header */ 592205471Sdelphij if (s->gzhead->extra != Z_NULL) 593205471Sdelphij wraplen += 2 + s->gzhead->extra_len; 594205471Sdelphij str = s->gzhead->name; 595205471Sdelphij if (str != Z_NULL) 596205471Sdelphij do { 597205471Sdelphij wraplen++; 598205471Sdelphij } while (*str++); 599205471Sdelphij str = s->gzhead->comment; 600205471Sdelphij if (str != Z_NULL) 601205471Sdelphij do { 602205471Sdelphij wraplen++; 603205471Sdelphij } while (*str++); 604205471Sdelphij if (s->gzhead->hcrc) 605205471Sdelphij wraplen += 2; 606205471Sdelphij } 607205471Sdelphij break; 608205471Sdelphij default: /* for compiler happiness */ 609205471Sdelphij wraplen = 6; 610205471Sdelphij } 611205471Sdelphij 612131380Stjr /* if not default parameters, return conservative bound */ 613131380Stjr if (s->w_bits != 15 || s->hash_bits != 8 + 7) 614205471Sdelphij return complen + wraplen; 615131380Stjr 616131380Stjr /* default settings: return tight bound for that case */ 617205471Sdelphij return sourceLen + (sourceLen >> 12) + (sourceLen >> 14) + 618205471Sdelphij (sourceLen >> 25) + 13 - 6 + wraplen; 619131380Stjr} 620131380Stjr 621131380Stjr/* ========================================================================= 62217651Speter * Put a short in the pending buffer. The 16-bit value is put in MSB order. 62317651Speter * IN assertion: the stream state is correct and there is enough room in 62417651Speter * pending_buf. 62517651Speter */ 62617651Speterlocal void putShortMSB (s, b) 62717651Speter deflate_state *s; 62817651Speter uInt b; 62917651Speter{ 63017651Speter put_byte(s, (Byte)(b >> 8)); 63117651Speter put_byte(s, (Byte)(b & 0xff)); 632131380Stjr} 63317651Speter 63417651Speter/* ========================================================================= 63517651Speter * Flush as much pending output as possible. All deflate() output goes 63617651Speter * through this function so some applications may wish to modify it 63717651Speter * to avoid allocating a large strm->next_out buffer and copying into it. 63817651Speter * (See also read_buf()). 63917651Speter */ 64017651Speterlocal void flush_pending(strm) 64117651Speter z_streamp strm; 64217651Speter{ 643237410Sdelphij unsigned len; 644237410Sdelphij deflate_state *s = strm->state; 64517651Speter 646237410Sdelphij _tr_flush_bits(s); 647237410Sdelphij len = s->pending; 64817651Speter if (len > strm->avail_out) len = strm->avail_out; 64917651Speter if (len == 0) return; 65017651Speter 651237410Sdelphij zmemcpy(strm->next_out, s->pending_out, len); 65217651Speter strm->next_out += len; 653237410Sdelphij s->pending_out += len; 65417651Speter strm->total_out += len; 65517651Speter strm->avail_out -= len; 656237410Sdelphij s->pending -= len; 657237410Sdelphij if (s->pending == 0) { 658237410Sdelphij s->pending_out = s->pending_buf; 65917651Speter } 66017651Speter} 66117651Speter 66217651Speter/* ========================================================================= */ 66333908Ssteveint ZEXPORT deflate (strm, flush) 66417651Speter z_streamp strm; 66517651Speter int flush; 66617651Speter{ 66717651Speter int old_flush; /* value of flush param for previous deflate call */ 66817651Speter deflate_state *s; 66917651Speter 67017651Speter if (strm == Z_NULL || strm->state == Z_NULL || 671205471Sdelphij flush > Z_BLOCK || flush < 0) { 67217651Speter return Z_STREAM_ERROR; 67317651Speter } 67417651Speter s = strm->state; 67517651Speter 67617651Speter if (strm->next_out == Z_NULL || 67717651Speter (strm->next_in == Z_NULL && strm->avail_in != 0) || 678131380Stjr (s->status == FINISH_STATE && flush != Z_FINISH)) { 67917651Speter ERR_RETURN(strm, Z_STREAM_ERROR); 68017651Speter } 68117651Speter if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR); 68217651Speter 68317651Speter s->strm = strm; /* just in case */ 68417651Speter old_flush = s->last_flush; 68517651Speter s->last_flush = flush; 68617651Speter 687131380Stjr /* Write the header */ 68817651Speter if (s->status == INIT_STATE) { 689131380Stjr#ifdef GZIP 690131380Stjr if (s->wrap == 2) { 691157046Sdes strm->adler = crc32(0L, Z_NULL, 0); 692131380Stjr put_byte(s, 31); 693131380Stjr put_byte(s, 139); 694131380Stjr put_byte(s, 8); 695205471Sdelphij if (s->gzhead == Z_NULL) { 696157046Sdes put_byte(s, 0); 697157046Sdes put_byte(s, 0); 698157046Sdes put_byte(s, 0); 699157046Sdes put_byte(s, 0); 700157046Sdes put_byte(s, 0); 701157046Sdes put_byte(s, s->level == 9 ? 2 : 702157046Sdes (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ? 703157046Sdes 4 : 0)); 704157046Sdes put_byte(s, OS_CODE); 705157046Sdes s->status = BUSY_STATE; 706157046Sdes } 707157046Sdes else { 708157046Sdes put_byte(s, (s->gzhead->text ? 1 : 0) + 709157046Sdes (s->gzhead->hcrc ? 2 : 0) + 710157046Sdes (s->gzhead->extra == Z_NULL ? 0 : 4) + 711157046Sdes (s->gzhead->name == Z_NULL ? 0 : 8) + 712157046Sdes (s->gzhead->comment == Z_NULL ? 0 : 16) 713157046Sdes ); 714157046Sdes put_byte(s, (Byte)(s->gzhead->time & 0xff)); 715157046Sdes put_byte(s, (Byte)((s->gzhead->time >> 8) & 0xff)); 716157046Sdes put_byte(s, (Byte)((s->gzhead->time >> 16) & 0xff)); 717157046Sdes put_byte(s, (Byte)((s->gzhead->time >> 24) & 0xff)); 718157046Sdes put_byte(s, s->level == 9 ? 2 : 719157046Sdes (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ? 720157046Sdes 4 : 0)); 721157046Sdes put_byte(s, s->gzhead->os & 0xff); 722205471Sdelphij if (s->gzhead->extra != Z_NULL) { 723157046Sdes put_byte(s, s->gzhead->extra_len & 0xff); 724157046Sdes put_byte(s, (s->gzhead->extra_len >> 8) & 0xff); 725157046Sdes } 726157046Sdes if (s->gzhead->hcrc) 727157046Sdes strm->adler = crc32(strm->adler, s->pending_buf, 728157046Sdes s->pending); 729157046Sdes s->gzindex = 0; 730157046Sdes s->status = EXTRA_STATE; 731157046Sdes } 732131380Stjr } 733131380Stjr else 734131380Stjr#endif 735131380Stjr { 736131380Stjr uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8; 737131380Stjr uInt level_flags; 73817651Speter 739131380Stjr if (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2) 740131380Stjr level_flags = 0; 741131380Stjr else if (s->level < 6) 742131380Stjr level_flags = 1; 743131380Stjr else if (s->level == 6) 744131380Stjr level_flags = 2; 745131380Stjr else 746131380Stjr level_flags = 3; 747131380Stjr header |= (level_flags << 6); 748131380Stjr if (s->strstart != 0) header |= PRESET_DICT; 749131380Stjr header += 31 - (header % 31); 75017651Speter 751131380Stjr s->status = BUSY_STATE; 752131380Stjr putShortMSB(s, header); 75317651Speter 754131380Stjr /* Save the adler32 of the preset dictionary: */ 755131380Stjr if (s->strstart != 0) { 756131380Stjr putShortMSB(s, (uInt)(strm->adler >> 16)); 757131380Stjr putShortMSB(s, (uInt)(strm->adler & 0xffff)); 758131380Stjr } 759131380Stjr strm->adler = adler32(0L, Z_NULL, 0); 760131380Stjr } 76117651Speter } 762157046Sdes#ifdef GZIP 763157046Sdes if (s->status == EXTRA_STATE) { 764205471Sdelphij if (s->gzhead->extra != Z_NULL) { 765157046Sdes uInt beg = s->pending; /* start of bytes to update crc */ 76617651Speter 767157046Sdes while (s->gzindex < (s->gzhead->extra_len & 0xffff)) { 768157046Sdes if (s->pending == s->pending_buf_size) { 769157046Sdes if (s->gzhead->hcrc && s->pending > beg) 770157046Sdes strm->adler = crc32(strm->adler, s->pending_buf + beg, 771157046Sdes s->pending - beg); 772157046Sdes flush_pending(strm); 773157046Sdes beg = s->pending; 774157046Sdes if (s->pending == s->pending_buf_size) 775157046Sdes break; 776157046Sdes } 777157046Sdes put_byte(s, s->gzhead->extra[s->gzindex]); 778157046Sdes s->gzindex++; 779157046Sdes } 780157046Sdes if (s->gzhead->hcrc && s->pending > beg) 781157046Sdes strm->adler = crc32(strm->adler, s->pending_buf + beg, 782157046Sdes s->pending - beg); 783157046Sdes if (s->gzindex == s->gzhead->extra_len) { 784157046Sdes s->gzindex = 0; 785157046Sdes s->status = NAME_STATE; 786157046Sdes } 787157046Sdes } 788157046Sdes else 789157046Sdes s->status = NAME_STATE; 790157046Sdes } 791157046Sdes if (s->status == NAME_STATE) { 792205471Sdelphij if (s->gzhead->name != Z_NULL) { 793157046Sdes uInt beg = s->pending; /* start of bytes to update crc */ 794157046Sdes int val; 795157046Sdes 796157046Sdes do { 797157046Sdes if (s->pending == s->pending_buf_size) { 798157046Sdes if (s->gzhead->hcrc && s->pending > beg) 799157046Sdes strm->adler = crc32(strm->adler, s->pending_buf + beg, 800157046Sdes s->pending - beg); 801157046Sdes flush_pending(strm); 802157046Sdes beg = s->pending; 803157046Sdes if (s->pending == s->pending_buf_size) { 804157046Sdes val = 1; 805157046Sdes break; 806157046Sdes } 807157046Sdes } 808157046Sdes val = s->gzhead->name[s->gzindex++]; 809157046Sdes put_byte(s, val); 810157046Sdes } while (val != 0); 811157046Sdes if (s->gzhead->hcrc && s->pending > beg) 812157046Sdes strm->adler = crc32(strm->adler, s->pending_buf + beg, 813157046Sdes s->pending - beg); 814157046Sdes if (val == 0) { 815157046Sdes s->gzindex = 0; 816157046Sdes s->status = COMMENT_STATE; 817157046Sdes } 818157046Sdes } 819157046Sdes else 820157046Sdes s->status = COMMENT_STATE; 821157046Sdes } 822157046Sdes if (s->status == COMMENT_STATE) { 823205471Sdelphij if (s->gzhead->comment != Z_NULL) { 824157046Sdes uInt beg = s->pending; /* start of bytes to update crc */ 825157046Sdes int val; 826157046Sdes 827157046Sdes do { 828157046Sdes if (s->pending == s->pending_buf_size) { 829157046Sdes if (s->gzhead->hcrc && s->pending > beg) 830157046Sdes strm->adler = crc32(strm->adler, s->pending_buf + beg, 831157046Sdes s->pending - beg); 832157046Sdes flush_pending(strm); 833157046Sdes beg = s->pending; 834157046Sdes if (s->pending == s->pending_buf_size) { 835157046Sdes val = 1; 836157046Sdes break; 837157046Sdes } 838157046Sdes } 839157046Sdes val = s->gzhead->comment[s->gzindex++]; 840157046Sdes put_byte(s, val); 841157046Sdes } while (val != 0); 842157046Sdes if (s->gzhead->hcrc && s->pending > beg) 843157046Sdes strm->adler = crc32(strm->adler, s->pending_buf + beg, 844157046Sdes s->pending - beg); 845157046Sdes if (val == 0) 846157046Sdes s->status = HCRC_STATE; 847157046Sdes } 848157046Sdes else 849157046Sdes s->status = HCRC_STATE; 850157046Sdes } 851157046Sdes if (s->status == HCRC_STATE) { 852157046Sdes if (s->gzhead->hcrc) { 853157046Sdes if (s->pending + 2 > s->pending_buf_size) 854157046Sdes flush_pending(strm); 855157046Sdes if (s->pending + 2 <= s->pending_buf_size) { 856157046Sdes put_byte(s, (Byte)(strm->adler & 0xff)); 857157046Sdes put_byte(s, (Byte)((strm->adler >> 8) & 0xff)); 858157046Sdes strm->adler = crc32(0L, Z_NULL, 0); 859157046Sdes s->status = BUSY_STATE; 860157046Sdes } 861157046Sdes } 862157046Sdes else 863157046Sdes s->status = BUSY_STATE; 864157046Sdes } 865157046Sdes#endif 866157046Sdes 86717651Speter /* Flush as much pending output as possible */ 86817651Speter if (s->pending != 0) { 86917651Speter flush_pending(strm); 87017651Speter if (strm->avail_out == 0) { 871131380Stjr /* Since avail_out is 0, deflate will be called again with 872131380Stjr * more output space, but possibly with both pending and 873131380Stjr * avail_in equal to zero. There won't be anything to do, 874131380Stjr * but this is not an error situation so make sure we 875131380Stjr * return OK instead of BUF_ERROR at next call of deflate: 87617651Speter */ 877131380Stjr s->last_flush = -1; 878131380Stjr return Z_OK; 879131380Stjr } 88017651Speter 88117651Speter /* Make sure there is something to do and avoid duplicate consecutive 88217651Speter * flushes. For repeated and useless calls with Z_FINISH, we keep 883131380Stjr * returning Z_STREAM_END instead of Z_BUF_ERROR. 88417651Speter */ 885237410Sdelphij } else if (strm->avail_in == 0 && RANK(flush) <= RANK(old_flush) && 886131380Stjr flush != Z_FINISH) { 88717651Speter ERR_RETURN(strm, Z_BUF_ERROR); 88817651Speter } 88917651Speter 89017651Speter /* User must not provide more input after the first FINISH: */ 89117651Speter if (s->status == FINISH_STATE && strm->avail_in != 0) { 89217651Speter ERR_RETURN(strm, Z_BUF_ERROR); 89317651Speter } 89417651Speter 89517651Speter /* Start a new block or continue the current one. 89617651Speter */ 89717651Speter if (strm->avail_in != 0 || s->lookahead != 0 || 89817651Speter (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) { 89917651Speter block_state bstate; 90017651Speter 901205471Sdelphij bstate = s->strategy == Z_HUFFMAN_ONLY ? deflate_huff(s, flush) : 902205471Sdelphij (s->strategy == Z_RLE ? deflate_rle(s, flush) : 903205471Sdelphij (*(configuration_table[s->level].func))(s, flush)); 90417651Speter 90517651Speter if (bstate == finish_started || bstate == finish_done) { 90617651Speter s->status = FINISH_STATE; 90717651Speter } 90817651Speter if (bstate == need_more || bstate == finish_started) { 909131380Stjr if (strm->avail_out == 0) { 910131380Stjr s->last_flush = -1; /* avoid BUF_ERROR next call, see above */ 911131380Stjr } 912131380Stjr return Z_OK; 913131380Stjr /* If flush != Z_NO_FLUSH && avail_out == 0, the next call 914131380Stjr * of deflate should use the same flush parameter to make sure 915131380Stjr * that the flush is complete. So we don't have to output an 916131380Stjr * empty block here, this will be done at next call. This also 917131380Stjr * ensures that for a very small output buffer, we emit at most 918131380Stjr * one empty block. 919131380Stjr */ 920131380Stjr } 92117651Speter if (bstate == block_done) { 92217651Speter if (flush == Z_PARTIAL_FLUSH) { 92317651Speter _tr_align(s); 924205471Sdelphij } else if (flush != Z_BLOCK) { /* FULL_FLUSH or SYNC_FLUSH */ 92517651Speter _tr_stored_block(s, (char*)0, 0L, 0); 92617651Speter /* For a full flush, this empty block will be recognized 92717651Speter * as a special marker by inflate_sync(). 92817651Speter */ 92917651Speter if (flush == Z_FULL_FLUSH) { 93017651Speter CLEAR_HASH(s); /* forget history */ 931205471Sdelphij if (s->lookahead == 0) { 932205471Sdelphij s->strstart = 0; 933205471Sdelphij s->block_start = 0L; 934237410Sdelphij s->insert = 0; 935205471Sdelphij } 93617651Speter } 93717651Speter } 93817651Speter flush_pending(strm); 939131380Stjr if (strm->avail_out == 0) { 940131380Stjr s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */ 941131380Stjr return Z_OK; 942131380Stjr } 94317651Speter } 94417651Speter } 94517651Speter Assert(strm->avail_out > 0, "bug2"); 94617651Speter 94717651Speter if (flush != Z_FINISH) return Z_OK; 948131380Stjr if (s->wrap <= 0) return Z_STREAM_END; 94917651Speter 950131380Stjr /* Write the trailer */ 951131380Stjr#ifdef GZIP 952131380Stjr if (s->wrap == 2) { 953131380Stjr put_byte(s, (Byte)(strm->adler & 0xff)); 954131380Stjr put_byte(s, (Byte)((strm->adler >> 8) & 0xff)); 955131380Stjr put_byte(s, (Byte)((strm->adler >> 16) & 0xff)); 956131380Stjr put_byte(s, (Byte)((strm->adler >> 24) & 0xff)); 957131380Stjr put_byte(s, (Byte)(strm->total_in & 0xff)); 958131380Stjr put_byte(s, (Byte)((strm->total_in >> 8) & 0xff)); 959131380Stjr put_byte(s, (Byte)((strm->total_in >> 16) & 0xff)); 960131380Stjr put_byte(s, (Byte)((strm->total_in >> 24) & 0xff)); 961131380Stjr } 962131380Stjr else 963131380Stjr#endif 964131380Stjr { 965131380Stjr putShortMSB(s, (uInt)(strm->adler >> 16)); 966131380Stjr putShortMSB(s, (uInt)(strm->adler & 0xffff)); 967131380Stjr } 96817651Speter flush_pending(strm); 96917651Speter /* If avail_out is zero, the application will call deflate again 97017651Speter * to flush the rest. 97117651Speter */ 972131380Stjr if (s->wrap > 0) s->wrap = -s->wrap; /* write the trailer only once! */ 97317651Speter return s->pending != 0 ? Z_OK : Z_STREAM_END; 97417651Speter} 97517651Speter 97617651Speter/* ========================================================================= */ 97733908Ssteveint ZEXPORT deflateEnd (strm) 97817651Speter z_streamp strm; 97917651Speter{ 98017651Speter int status; 98117651Speter 98217651Speter if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 98317651Speter 98433908Ssteve status = strm->state->status; 985157046Sdes if (status != INIT_STATE && 986157046Sdes status != EXTRA_STATE && 987157046Sdes status != NAME_STATE && 988157046Sdes status != COMMENT_STATE && 989157046Sdes status != HCRC_STATE && 990157046Sdes status != BUSY_STATE && 991131380Stjr status != FINISH_STATE) { 99233908Ssteve return Z_STREAM_ERROR; 99333908Ssteve } 99433908Ssteve 99517651Speter /* Deallocate in reverse order of allocations: */ 99617651Speter TRY_FREE(strm, strm->state->pending_buf); 99717651Speter TRY_FREE(strm, strm->state->head); 99817651Speter TRY_FREE(strm, strm->state->prev); 99917651Speter TRY_FREE(strm, strm->state->window); 100017651Speter 100117651Speter ZFREE(strm, strm->state); 100217651Speter strm->state = Z_NULL; 100317651Speter 100417651Speter return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK; 100517651Speter} 100617651Speter 100733908Ssteve/* ========================================================================= 100833908Ssteve * Copy the source state to the destination state. 100933908Ssteve * To simplify the source, this is not supported for 16-bit MSDOS (which 101033908Ssteve * doesn't have enough memory anyway to duplicate compression states). 101133908Ssteve */ 101233908Ssteveint ZEXPORT deflateCopy (dest, source) 101317651Speter z_streamp dest; 101417651Speter z_streamp source; 101517651Speter{ 101633908Ssteve#ifdef MAXSEG_64K 101733908Ssteve return Z_STREAM_ERROR; 101833908Ssteve#else 101933908Ssteve deflate_state *ds; 102033908Ssteve deflate_state *ss; 102133908Ssteve ushf *overlay; 102233908Ssteve 102333908Ssteve 102442471Speter if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL) { 102517651Speter return Z_STREAM_ERROR; 102617651Speter } 102742471Speter 102842471Speter ss = source->state; 102942471Speter 1030237410Sdelphij zmemcpy((voidpf)dest, (voidpf)source, sizeof(z_stream)); 103117651Speter 103233908Ssteve ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state)); 103333908Ssteve if (ds == Z_NULL) return Z_MEM_ERROR; 103433908Ssteve dest->state = (struct internal_state FAR *) ds; 1035237410Sdelphij zmemcpy((voidpf)ds, (voidpf)ss, sizeof(deflate_state)); 103633908Ssteve ds->strm = dest; 103733908Ssteve 103833908Ssteve ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte)); 103933908Ssteve ds->prev = (Posf *) ZALLOC(dest, ds->w_size, sizeof(Pos)); 104033908Ssteve ds->head = (Posf *) ZALLOC(dest, ds->hash_size, sizeof(Pos)); 104133908Ssteve overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof(ush)+2); 104233908Ssteve ds->pending_buf = (uchf *) overlay; 104333908Ssteve 104433908Ssteve if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL || 104533908Ssteve ds->pending_buf == Z_NULL) { 104633908Ssteve deflateEnd (dest); 104733908Ssteve return Z_MEM_ERROR; 104833908Ssteve } 104933908Ssteve /* following zmemcpy do not work for 16-bit MSDOS */ 105033908Ssteve zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte)); 1051237410Sdelphij zmemcpy((voidpf)ds->prev, (voidpf)ss->prev, ds->w_size * sizeof(Pos)); 1052237410Sdelphij zmemcpy((voidpf)ds->head, (voidpf)ss->head, ds->hash_size * sizeof(Pos)); 105333908Ssteve zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size); 105433908Ssteve 105533908Ssteve ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf); 105633908Ssteve ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush); 105733908Ssteve ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize; 105833908Ssteve 105933908Ssteve ds->l_desc.dyn_tree = ds->dyn_ltree; 106033908Ssteve ds->d_desc.dyn_tree = ds->dyn_dtree; 106133908Ssteve ds->bl_desc.dyn_tree = ds->bl_tree; 106233908Ssteve 106317651Speter return Z_OK; 1064131380Stjr#endif /* MAXSEG_64K */ 106517651Speter} 106617651Speter 106717651Speter/* =========================================================================== 106817651Speter * Read a new buffer from the current input stream, update the adler32 106917651Speter * and total number of bytes read. All deflate() input goes through 107017651Speter * this function so some applications may wish to modify it to avoid 107117651Speter * allocating a large strm->next_in buffer and copying from it. 107217651Speter * (See also flush_pending()). 107317651Speter */ 107417651Speterlocal int read_buf(strm, buf, size) 107517651Speter z_streamp strm; 107633908Ssteve Bytef *buf; 107717651Speter unsigned size; 107817651Speter{ 107917651Speter unsigned len = strm->avail_in; 108017651Speter 108117651Speter if (len > size) len = size; 108217651Speter if (len == 0) return 0; 108317651Speter 108417651Speter strm->avail_in -= len; 108517651Speter 1086237410Sdelphij zmemcpy(buf, strm->next_in, len); 1087131380Stjr if (strm->state->wrap == 1) { 1088237410Sdelphij strm->adler = adler32(strm->adler, buf, len); 108917651Speter } 1090131380Stjr#ifdef GZIP 1091131380Stjr else if (strm->state->wrap == 2) { 1092237410Sdelphij strm->adler = crc32(strm->adler, buf, len); 1093131380Stjr } 1094131380Stjr#endif 109517651Speter strm->next_in += len; 109617651Speter strm->total_in += len; 109717651Speter 109817651Speter return (int)len; 109917651Speter} 110017651Speter 110117651Speter/* =========================================================================== 110217651Speter * Initialize the "longest match" routines for a new zlib stream 110317651Speter */ 110417651Speterlocal void lm_init (s) 110517651Speter deflate_state *s; 110617651Speter{ 110717651Speter s->window_size = (ulg)2L*s->w_size; 110817651Speter 110917651Speter CLEAR_HASH(s); 111017651Speter 111117651Speter /* Set the default configuration parameters: 111217651Speter */ 111317651Speter s->max_lazy_match = configuration_table[s->level].max_lazy; 111417651Speter s->good_match = configuration_table[s->level].good_length; 111517651Speter s->nice_match = configuration_table[s->level].nice_length; 111617651Speter s->max_chain_length = configuration_table[s->level].max_chain; 111717651Speter 111817651Speter s->strstart = 0; 111917651Speter s->block_start = 0L; 112017651Speter s->lookahead = 0; 1121237410Sdelphij s->insert = 0; 112217651Speter s->match_length = s->prev_length = MIN_MATCH-1; 112317651Speter s->match_available = 0; 112417651Speter s->ins_h = 0; 1125157046Sdes#ifndef FASTEST 112617651Speter#ifdef ASMV 112717651Speter match_init(); /* initialize the asm code */ 112817651Speter#endif 1129157046Sdes#endif 113017651Speter} 113117651Speter 1132131380Stjr#ifndef FASTEST 113317651Speter/* =========================================================================== 113417651Speter * Set match_start to the longest match starting at the given string and 113517651Speter * return its length. Matches shorter or equal to prev_length are discarded, 113617651Speter * in which case the result is equal to prev_length and match_start is 113717651Speter * garbage. 113817651Speter * IN assertions: cur_match is the head of the hash chain for the current 113917651Speter * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1 114017651Speter * OUT assertion: the match length is not greater than s->lookahead. 114117651Speter */ 114217651Speter#ifndef ASMV 114317651Speter/* For 80x86 and 680x0, an optimized version will be provided in match.asm or 114417651Speter * match.S. The code will be functionally equivalent. 114517651Speter */ 114617651Speterlocal uInt longest_match(s, cur_match) 114717651Speter deflate_state *s; 114817651Speter IPos cur_match; /* current match */ 114917651Speter{ 115017651Speter unsigned chain_length = s->max_chain_length;/* max hash chain length */ 115117651Speter register Bytef *scan = s->window + s->strstart; /* current string */ 115217651Speter register Bytef *match; /* matched string */ 115317651Speter register int len; /* length of current match */ 115417651Speter int best_len = s->prev_length; /* best match length so far */ 115517651Speter int nice_match = s->nice_match; /* stop if match long enough */ 115617651Speter IPos limit = s->strstart > (IPos)MAX_DIST(s) ? 115717651Speter s->strstart - (IPos)MAX_DIST(s) : NIL; 115817651Speter /* Stop when cur_match becomes <= limit. To simplify the code, 115917651Speter * we prevent matches with the string of window index 0. 116017651Speter */ 116117651Speter Posf *prev = s->prev; 116217651Speter uInt wmask = s->w_mask; 116317651Speter 116417651Speter#ifdef UNALIGNED_OK 116517651Speter /* Compare two bytes at a time. Note: this is not always beneficial. 116617651Speter * Try with and without -DUNALIGNED_OK to check. 116717651Speter */ 116817651Speter register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1; 116917651Speter register ush scan_start = *(ushf*)scan; 117017651Speter register ush scan_end = *(ushf*)(scan+best_len-1); 117117651Speter#else 117217651Speter register Bytef *strend = s->window + s->strstart + MAX_MATCH; 117317651Speter register Byte scan_end1 = scan[best_len-1]; 117417651Speter register Byte scan_end = scan[best_len]; 117517651Speter#endif 117617651Speter 117717651Speter /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. 117817651Speter * It is easy to get rid of this optimization if necessary. 117917651Speter */ 118017651Speter Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever"); 118117651Speter 118217651Speter /* Do not waste too much time if we already have a good match: */ 118317651Speter if (s->prev_length >= s->good_match) { 118417651Speter chain_length >>= 2; 118517651Speter } 118617651Speter /* Do not look for matches beyond the end of the input. This is necessary 118717651Speter * to make deflate deterministic. 118817651Speter */ 118917651Speter if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead; 119017651Speter 119117651Speter Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead"); 119217651Speter 119317651Speter do { 119417651Speter Assert(cur_match < s->strstart, "no future"); 119517651Speter match = s->window + cur_match; 119617651Speter 119717651Speter /* Skip to next match if the match length cannot increase 1198157046Sdes * or if the match length is less than 2. Note that the checks below 1199157046Sdes * for insufficient lookahead only occur occasionally for performance 1200157046Sdes * reasons. Therefore uninitialized memory will be accessed, and 1201157046Sdes * conditional jumps will be made that depend on those values. 1202157046Sdes * However the length of the match is limited to the lookahead, so 1203157046Sdes * the output of deflate is not affected by the uninitialized values. 120417651Speter */ 120517651Speter#if (defined(UNALIGNED_OK) && MAX_MATCH == 258) 120617651Speter /* This code assumes sizeof(unsigned short) == 2. Do not use 120717651Speter * UNALIGNED_OK if your compiler uses a different size. 120817651Speter */ 120917651Speter if (*(ushf*)(match+best_len-1) != scan_end || 121017651Speter *(ushf*)match != scan_start) continue; 121117651Speter 121217651Speter /* It is not necessary to compare scan[2] and match[2] since they are 121317651Speter * always equal when the other bytes match, given that the hash keys 121417651Speter * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at 121517651Speter * strstart+3, +5, ... up to strstart+257. We check for insufficient 121617651Speter * lookahead only every 4th comparison; the 128th check will be made 121717651Speter * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is 121817651Speter * necessary to put more guard bytes at the end of the window, or 121917651Speter * to check more often for insufficient lookahead. 122017651Speter */ 122117651Speter Assert(scan[2] == match[2], "scan[2]?"); 122217651Speter scan++, match++; 122317651Speter do { 122417651Speter } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) && 122517651Speter *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 122617651Speter *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 122717651Speter *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 122817651Speter scan < strend); 122917651Speter /* The funny "do {}" generates better code on most compilers */ 123017651Speter 123117651Speter /* Here, scan <= window+strstart+257 */ 123217651Speter Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 123317651Speter if (*scan == *match) scan++; 123417651Speter 123517651Speter len = (MAX_MATCH - 1) - (int)(strend-scan); 123617651Speter scan = strend - (MAX_MATCH-1); 123717651Speter 123817651Speter#else /* UNALIGNED_OK */ 123917651Speter 124017651Speter if (match[best_len] != scan_end || 124117651Speter match[best_len-1] != scan_end1 || 124217651Speter *match != *scan || 124317651Speter *++match != scan[1]) continue; 124417651Speter 124517651Speter /* The check at best_len-1 can be removed because it will be made 124617651Speter * again later. (This heuristic is not always a win.) 124717651Speter * It is not necessary to compare scan[2] and match[2] since they 124817651Speter * are always equal when the other bytes match, given that 124917651Speter * the hash keys are equal and that HASH_BITS >= 8. 125017651Speter */ 125117651Speter scan += 2, match++; 125217651Speter Assert(*scan == *match, "match[2]?"); 125317651Speter 125417651Speter /* We check for insufficient lookahead only every 8th comparison; 125517651Speter * the 256th check will be made at strstart+258. 125617651Speter */ 125717651Speter do { 125817651Speter } while (*++scan == *++match && *++scan == *++match && 125917651Speter *++scan == *++match && *++scan == *++match && 126017651Speter *++scan == *++match && *++scan == *++match && 126117651Speter *++scan == *++match && *++scan == *++match && 126217651Speter scan < strend); 126317651Speter 126417651Speter Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 126517651Speter 126617651Speter len = MAX_MATCH - (int)(strend - scan); 126717651Speter scan = strend - MAX_MATCH; 126817651Speter 126917651Speter#endif /* UNALIGNED_OK */ 127017651Speter 127117651Speter if (len > best_len) { 127217651Speter s->match_start = cur_match; 127317651Speter best_len = len; 127417651Speter if (len >= nice_match) break; 127517651Speter#ifdef UNALIGNED_OK 127617651Speter scan_end = *(ushf*)(scan+best_len-1); 127717651Speter#else 127817651Speter scan_end1 = scan[best_len-1]; 127917651Speter scan_end = scan[best_len]; 128017651Speter#endif 128117651Speter } 128217651Speter } while ((cur_match = prev[cur_match & wmask]) > limit 128317651Speter && --chain_length != 0); 128417651Speter 128533908Ssteve if ((uInt)best_len <= s->lookahead) return (uInt)best_len; 128617651Speter return s->lookahead; 128717651Speter} 1288131380Stjr#endif /* ASMV */ 128933908Ssteve 1290205471Sdelphij#else /* FASTEST */ 1291205471Sdelphij 129233908Ssteve/* --------------------------------------------------------------------------- 1293205471Sdelphij * Optimized version for FASTEST only 129433908Ssteve */ 1295205471Sdelphijlocal uInt longest_match(s, cur_match) 129633908Ssteve deflate_state *s; 129733908Ssteve IPos cur_match; /* current match */ 129833908Ssteve{ 129933908Ssteve register Bytef *scan = s->window + s->strstart; /* current string */ 130033908Ssteve register Bytef *match; /* matched string */ 130133908Ssteve register int len; /* length of current match */ 130233908Ssteve register Bytef *strend = s->window + s->strstart + MAX_MATCH; 130333908Ssteve 130433908Ssteve /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. 130533908Ssteve * It is easy to get rid of this optimization if necessary. 130633908Ssteve */ 130733908Ssteve Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever"); 130833908Ssteve 130933908Ssteve Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead"); 131033908Ssteve 131133908Ssteve Assert(cur_match < s->strstart, "no future"); 131233908Ssteve 131333908Ssteve match = s->window + cur_match; 131433908Ssteve 131533908Ssteve /* Return failure if the match length is less than 2: 131633908Ssteve */ 131733908Ssteve if (match[0] != scan[0] || match[1] != scan[1]) return MIN_MATCH-1; 131833908Ssteve 131933908Ssteve /* The check at best_len-1 can be removed because it will be made 132033908Ssteve * again later. (This heuristic is not always a win.) 132133908Ssteve * It is not necessary to compare scan[2] and match[2] since they 132233908Ssteve * are always equal when the other bytes match, given that 132333908Ssteve * the hash keys are equal and that HASH_BITS >= 8. 132433908Ssteve */ 132533908Ssteve scan += 2, match += 2; 132633908Ssteve Assert(*scan == *match, "match[2]?"); 132733908Ssteve 132833908Ssteve /* We check for insufficient lookahead only every 8th comparison; 132933908Ssteve * the 256th check will be made at strstart+258. 133033908Ssteve */ 133133908Ssteve do { 133233908Ssteve } while (*++scan == *++match && *++scan == *++match && 1333131380Stjr *++scan == *++match && *++scan == *++match && 1334131380Stjr *++scan == *++match && *++scan == *++match && 1335131380Stjr *++scan == *++match && *++scan == *++match && 1336131380Stjr scan < strend); 133733908Ssteve 133833908Ssteve Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 133933908Ssteve 134033908Ssteve len = MAX_MATCH - (int)(strend - scan); 134133908Ssteve 134233908Ssteve if (len < MIN_MATCH) return MIN_MATCH - 1; 134333908Ssteve 134433908Ssteve s->match_start = cur_match; 1345131380Stjr return (uInt)len <= s->lookahead ? (uInt)len : s->lookahead; 134633908Ssteve} 134717651Speter 1348205471Sdelphij#endif /* FASTEST */ 1349205471Sdelphij 135017651Speter#ifdef DEBUG 135117651Speter/* =========================================================================== 135217651Speter * Check that the match at match_start is indeed a match. 135317651Speter */ 135417651Speterlocal void check_match(s, start, match, length) 135517651Speter deflate_state *s; 135617651Speter IPos start, match; 135717651Speter int length; 135817651Speter{ 135917651Speter /* check that the match is indeed a match */ 136033908Ssteve if (zmemcmp(s->window + match, 136133908Ssteve s->window + start, length) != EQUAL) { 136217651Speter fprintf(stderr, " start %u, match %u, length %d\n", 1363131380Stjr start, match, length); 136417651Speter do { 1365131380Stjr fprintf(stderr, "%c%c", s->window[match++], s->window[start++]); 1366131380Stjr } while (--length != 0); 136717651Speter z_error("invalid match"); 136817651Speter } 136933908Ssteve if (z_verbose > 1) { 137017651Speter fprintf(stderr,"\\[%d,%d]", start-match, length); 137117651Speter do { putc(s->window[start++], stderr); } while (--length != 0); 137217651Speter } 137317651Speter} 137417651Speter#else 137517651Speter# define check_match(s, start, match, length) 1376131380Stjr#endif /* DEBUG */ 137717651Speter 137817651Speter/* =========================================================================== 137917651Speter * Fill the window when the lookahead becomes insufficient. 138017651Speter * Updates strstart and lookahead. 138117651Speter * 138217651Speter * IN assertion: lookahead < MIN_LOOKAHEAD 138317651Speter * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD 138417651Speter * At least one byte has been read, or avail_in == 0; reads are 138517651Speter * performed for at least two bytes (required for the zip translate_eol 138617651Speter * option -- not supported here). 138717651Speter */ 138817651Speterlocal void fill_window(s) 138917651Speter deflate_state *s; 139017651Speter{ 139117651Speter register unsigned n, m; 139217651Speter register Posf *p; 139317651Speter unsigned more; /* Amount of free space at the end of the window. */ 139417651Speter uInt wsize = s->w_size; 139517651Speter 1396237410Sdelphij Assert(s->lookahead < MIN_LOOKAHEAD, "already enough lookahead"); 1397237410Sdelphij 139817651Speter do { 139917651Speter more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart); 140017651Speter 140117651Speter /* Deal with !@#$% 64K limit: */ 1402131380Stjr if (sizeof(int) <= 2) { 1403131380Stjr if (more == 0 && s->strstart == 0 && s->lookahead == 0) { 1404131380Stjr more = wsize; 140517651Speter 1406131380Stjr } else if (more == (unsigned)(-1)) { 1407131380Stjr /* Very unlikely, but possible on 16 bit machine if 1408131380Stjr * strstart == 0 && lookahead == 1 (input done a byte at time) 1409131380Stjr */ 1410131380Stjr more--; 1411131380Stjr } 1412131380Stjr } 141317651Speter 141417651Speter /* If the window is almost full and there is insufficient lookahead, 141517651Speter * move the upper half to the lower one to make room in the upper half. 141617651Speter */ 1417131380Stjr if (s->strstart >= wsize+MAX_DIST(s)) { 141817651Speter 141933908Ssteve zmemcpy(s->window, s->window+wsize, (unsigned)wsize); 142017651Speter s->match_start -= wsize; 142117651Speter s->strstart -= wsize; /* we now have strstart >= MAX_DIST */ 142217651Speter s->block_start -= (long) wsize; 142317651Speter 142417651Speter /* Slide the hash table (could be avoided with 32 bit values 142533908Ssteve at the expense of memory usage). We slide even when level == 0 142633908Ssteve to keep the hash table consistent if we switch back to level > 0 142733908Ssteve later. (Using level 0 permanently is not an optimal usage of 142833908Ssteve zlib, so we don't care about this pathological case.) 142917651Speter */ 1430131380Stjr n = s->hash_size; 1431131380Stjr p = &s->head[n]; 1432131380Stjr do { 1433131380Stjr m = *--p; 1434131380Stjr *p = (Pos)(m >= wsize ? m-wsize : NIL); 1435131380Stjr } while (--n); 143617651Speter 1437131380Stjr n = wsize; 143833908Ssteve#ifndef FASTEST 1439131380Stjr p = &s->prev[n]; 1440131380Stjr do { 1441131380Stjr m = *--p; 1442131380Stjr *p = (Pos)(m >= wsize ? m-wsize : NIL); 1443131380Stjr /* If n is not on any hash chain, prev[n] is garbage but 1444131380Stjr * its value will never be used. 1445131380Stjr */ 1446131380Stjr } while (--n); 144733908Ssteve#endif 144817651Speter more += wsize; 144917651Speter } 1450237410Sdelphij if (s->strm->avail_in == 0) break; 145117651Speter 145217651Speter /* If there was no sliding: 145317651Speter * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 && 145417651Speter * more == window_size - lookahead - strstart 145517651Speter * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1) 145617651Speter * => more >= window_size - 2*WSIZE + 2 145717651Speter * In the BIG_MEM or MMAP case (not yet supported), 145817651Speter * window_size == input_size + MIN_LOOKAHEAD && 145917651Speter * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD. 146017651Speter * Otherwise, window_size == 2*WSIZE so more >= 2. 146117651Speter * If there was sliding, more >= WSIZE. So in all cases, more >= 2. 146217651Speter */ 146317651Speter Assert(more >= 2, "more < 2"); 146417651Speter 146533908Ssteve n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more); 146617651Speter s->lookahead += n; 146717651Speter 146817651Speter /* Initialize the hash value now that we have some input: */ 1469237410Sdelphij if (s->lookahead + s->insert >= MIN_MATCH) { 1470237410Sdelphij uInt str = s->strstart - s->insert; 1471237410Sdelphij s->ins_h = s->window[str]; 1472237410Sdelphij UPDATE_HASH(s, s->ins_h, s->window[str + 1]); 147317651Speter#if MIN_MATCH != 3 147417651Speter Call UPDATE_HASH() MIN_MATCH-3 more times 147517651Speter#endif 1476237410Sdelphij while (s->insert) { 1477237410Sdelphij UPDATE_HASH(s, s->ins_h, s->window[str + MIN_MATCH-1]); 1478237410Sdelphij#ifndef FASTEST 1479237410Sdelphij s->prev[str & s->w_mask] = s->head[s->ins_h]; 1480237410Sdelphij#endif 1481237410Sdelphij s->head[s->ins_h] = (Pos)str; 1482237410Sdelphij str++; 1483237410Sdelphij s->insert--; 1484237410Sdelphij if (s->lookahead + s->insert < MIN_MATCH) 1485237410Sdelphij break; 1486237410Sdelphij } 148717651Speter } 148817651Speter /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage, 148917651Speter * but this is not important since only literal bytes will be emitted. 149017651Speter */ 149117651Speter 149217651Speter } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0); 1493205471Sdelphij 1494205471Sdelphij /* If the WIN_INIT bytes after the end of the current data have never been 1495205471Sdelphij * written, then zero those bytes in order to avoid memory check reports of 1496205471Sdelphij * the use of uninitialized (or uninitialised as Julian writes) bytes by 1497205471Sdelphij * the longest match routines. Update the high water mark for the next 1498205471Sdelphij * time through here. WIN_INIT is set to MAX_MATCH since the longest match 1499205471Sdelphij * routines allow scanning to strstart + MAX_MATCH, ignoring lookahead. 1500205471Sdelphij */ 1501205471Sdelphij if (s->high_water < s->window_size) { 1502205471Sdelphij ulg curr = s->strstart + (ulg)(s->lookahead); 1503205471Sdelphij ulg init; 1504205471Sdelphij 1505205471Sdelphij if (s->high_water < curr) { 1506205471Sdelphij /* Previous high water mark below current data -- zero WIN_INIT 1507205471Sdelphij * bytes or up to end of window, whichever is less. 1508205471Sdelphij */ 1509205471Sdelphij init = s->window_size - curr; 1510205471Sdelphij if (init > WIN_INIT) 1511205471Sdelphij init = WIN_INIT; 1512205471Sdelphij zmemzero(s->window + curr, (unsigned)init); 1513205471Sdelphij s->high_water = curr + init; 1514205471Sdelphij } 1515205471Sdelphij else if (s->high_water < (ulg)curr + WIN_INIT) { 1516205471Sdelphij /* High water mark at or above current data, but below current data 1517205471Sdelphij * plus WIN_INIT -- zero out to current data plus WIN_INIT, or up 1518205471Sdelphij * to end of window, whichever is less. 1519205471Sdelphij */ 1520205471Sdelphij init = (ulg)curr + WIN_INIT - s->high_water; 1521205471Sdelphij if (init > s->window_size - s->high_water) 1522205471Sdelphij init = s->window_size - s->high_water; 1523205471Sdelphij zmemzero(s->window + s->high_water, (unsigned)init); 1524205471Sdelphij s->high_water += init; 1525205471Sdelphij } 1526205471Sdelphij } 1527237410Sdelphij 1528237410Sdelphij Assert((ulg)s->strstart <= s->window_size - MIN_LOOKAHEAD, 1529237410Sdelphij "not enough room for search"); 153017651Speter} 153117651Speter 153217651Speter/* =========================================================================== 153317651Speter * Flush the current block, with given end-of-file flag. 153417651Speter * IN assertion: strstart is set to the end of the current match. 153517651Speter */ 1536205471Sdelphij#define FLUSH_BLOCK_ONLY(s, last) { \ 153717651Speter _tr_flush_block(s, (s->block_start >= 0L ? \ 153817651Speter (charf *)&s->window[(unsigned)s->block_start] : \ 153917651Speter (charf *)Z_NULL), \ 1540131380Stjr (ulg)((long)s->strstart - s->block_start), \ 1541205471Sdelphij (last)); \ 154217651Speter s->block_start = s->strstart; \ 154317651Speter flush_pending(s->strm); \ 154417651Speter Tracev((stderr,"[FLUSH]")); \ 154517651Speter} 154617651Speter 154717651Speter/* Same but force premature exit if necessary. */ 1548205471Sdelphij#define FLUSH_BLOCK(s, last) { \ 1549205471Sdelphij FLUSH_BLOCK_ONLY(s, last); \ 1550205471Sdelphij if (s->strm->avail_out == 0) return (last) ? finish_started : need_more; \ 155117651Speter} 155217651Speter 155317651Speter/* =========================================================================== 155417651Speter * Copy without compression as much as possible from the input stream, return 155517651Speter * the current block state. 155617651Speter * This function does not insert new strings in the dictionary since 155717651Speter * uncompressible data is probably not useful. This function is used 155817651Speter * only for the level=0 compression option. 155933908Ssteve * NOTE: this function should be optimized to avoid extra copying from 156033908Ssteve * window to pending_buf. 156117651Speter */ 156217651Speterlocal block_state deflate_stored(s, flush) 156317651Speter deflate_state *s; 156417651Speter int flush; 156517651Speter{ 156633908Ssteve /* Stored blocks are limited to 0xffff bytes, pending_buf is limited 156733908Ssteve * to pending_buf_size, and each stored block has a 5 byte header: 156833908Ssteve */ 156933908Ssteve ulg max_block_size = 0xffff; 157033908Ssteve ulg max_start; 157133908Ssteve 157233908Ssteve if (max_block_size > s->pending_buf_size - 5) { 157333908Ssteve max_block_size = s->pending_buf_size - 5; 157433908Ssteve } 157533908Ssteve 157633908Ssteve /* Copy as much as possible from input to output: */ 157717651Speter for (;;) { 157817651Speter /* Fill the window as much as possible: */ 157917651Speter if (s->lookahead <= 1) { 158017651Speter 158117651Speter Assert(s->strstart < s->w_size+MAX_DIST(s) || 1582131380Stjr s->block_start >= (long)s->w_size, "slide too late"); 158317651Speter 158417651Speter fill_window(s); 158517651Speter if (s->lookahead == 0 && flush == Z_NO_FLUSH) return need_more; 158617651Speter 158717651Speter if (s->lookahead == 0) break; /* flush the current block */ 158817651Speter } 1589131380Stjr Assert(s->block_start >= 0L, "block gone"); 159017651Speter 1591131380Stjr s->strstart += s->lookahead; 1592131380Stjr s->lookahead = 0; 159317651Speter 1594131380Stjr /* Emit a stored block if pending_buf will be full: */ 1595131380Stjr max_start = s->block_start + max_block_size; 159633908Ssteve if (s->strstart == 0 || (ulg)s->strstart >= max_start) { 1597131380Stjr /* strstart == 0 is possible when wraparound on 16-bit machine */ 1598131380Stjr s->lookahead = (uInt)(s->strstart - max_start); 1599131380Stjr s->strstart = (uInt)max_start; 160033908Ssteve FLUSH_BLOCK(s, 0); 1601131380Stjr } 1602131380Stjr /* Flush if we may have to slide, otherwise block_start may become 160333908Ssteve * negative and the data will be gone: 160433908Ssteve */ 160517651Speter if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) { 160617651Speter FLUSH_BLOCK(s, 0); 1607131380Stjr } 160817651Speter } 1609237410Sdelphij s->insert = 0; 1610237410Sdelphij if (flush == Z_FINISH) { 1611237410Sdelphij FLUSH_BLOCK(s, 1); 1612237410Sdelphij return finish_done; 1613237410Sdelphij } 1614237410Sdelphij if ((long)s->strstart > s->block_start) 1615237410Sdelphij FLUSH_BLOCK(s, 0); 1616237410Sdelphij return block_done; 161717651Speter} 161817651Speter 161917651Speter/* =========================================================================== 162017651Speter * Compress as much as possible from the input stream, return the current 162117651Speter * block state. 162217651Speter * This function does not perform lazy evaluation of matches and inserts 162317651Speter * new strings in the dictionary only for unmatched strings or for short 162417651Speter * matches. It is used only for the fast compression options. 162517651Speter */ 162617651Speterlocal block_state deflate_fast(s, flush) 162717651Speter deflate_state *s; 162817651Speter int flush; 162917651Speter{ 1630205471Sdelphij IPos hash_head; /* head of the hash chain */ 163117651Speter int bflush; /* set if current block must be flushed */ 163217651Speter 163317651Speter for (;;) { 163417651Speter /* Make sure that we always have enough lookahead, except 163517651Speter * at the end of the input file. We need MAX_MATCH bytes 163617651Speter * for the next match, plus MIN_MATCH bytes to insert the 163717651Speter * string following the next match. 163817651Speter */ 163917651Speter if (s->lookahead < MIN_LOOKAHEAD) { 164017651Speter fill_window(s); 164117651Speter if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { 1642131380Stjr return need_more; 1643131380Stjr } 164417651Speter if (s->lookahead == 0) break; /* flush the current block */ 164517651Speter } 164617651Speter 164717651Speter /* Insert the string window[strstart .. strstart+2] in the 164817651Speter * dictionary, and set hash_head to the head of the hash chain: 164917651Speter */ 1650205471Sdelphij hash_head = NIL; 165117651Speter if (s->lookahead >= MIN_MATCH) { 165217651Speter INSERT_STRING(s, s->strstart, hash_head); 165317651Speter } 165417651Speter 165517651Speter /* Find the longest match, discarding those <= prev_length. 165617651Speter * At this point we have always match_length < MIN_MATCH 165717651Speter */ 165817651Speter if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) { 165917651Speter /* To simplify the code, we prevent matches with the string 166017651Speter * of window index 0 (in particular we have to avoid a match 166117651Speter * of the string with itself at the start of the input file). 166217651Speter */ 1663205471Sdelphij s->match_length = longest_match (s, hash_head); 1664205471Sdelphij /* longest_match() sets match_start */ 166517651Speter } 166617651Speter if (s->match_length >= MIN_MATCH) { 166717651Speter check_match(s, s->strstart, s->match_start, s->match_length); 166817651Speter 166933908Ssteve _tr_tally_dist(s, s->strstart - s->match_start, 167033908Ssteve s->match_length - MIN_MATCH, bflush); 167117651Speter 167217651Speter s->lookahead -= s->match_length; 167317651Speter 167417651Speter /* Insert new strings in the hash table only if the match length 167517651Speter * is not too large. This saves time but degrades compression. 167617651Speter */ 167733908Ssteve#ifndef FASTEST 167817651Speter if (s->match_length <= s->max_insert_length && 167917651Speter s->lookahead >= MIN_MATCH) { 1680131380Stjr s->match_length--; /* string at strstart already in table */ 168117651Speter do { 168217651Speter s->strstart++; 168317651Speter INSERT_STRING(s, s->strstart, hash_head); 168417651Speter /* strstart never exceeds WSIZE-MAX_MATCH, so there are 168517651Speter * always MIN_MATCH bytes ahead. 168617651Speter */ 168717651Speter } while (--s->match_length != 0); 1688131380Stjr s->strstart++; 168933908Ssteve } else 169033908Ssteve#endif 1691131380Stjr { 169217651Speter s->strstart += s->match_length; 169317651Speter s->match_length = 0; 169417651Speter s->ins_h = s->window[s->strstart]; 169517651Speter UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]); 169617651Speter#if MIN_MATCH != 3 169717651Speter Call UPDATE_HASH() MIN_MATCH-3 more times 169817651Speter#endif 169917651Speter /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not 170017651Speter * matter since it will be recomputed at next deflate call. 170117651Speter */ 170217651Speter } 170317651Speter } else { 170417651Speter /* No match, output a literal byte */ 170517651Speter Tracevv((stderr,"%c", s->window[s->strstart])); 170633908Ssteve _tr_tally_lit (s, s->window[s->strstart], bflush); 170717651Speter s->lookahead--; 1708131380Stjr s->strstart++; 170917651Speter } 171017651Speter if (bflush) FLUSH_BLOCK(s, 0); 171117651Speter } 1712237410Sdelphij s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1; 1713237410Sdelphij if (flush == Z_FINISH) { 1714237410Sdelphij FLUSH_BLOCK(s, 1); 1715237410Sdelphij return finish_done; 1716237410Sdelphij } 1717237410Sdelphij if (s->last_lit) 1718237410Sdelphij FLUSH_BLOCK(s, 0); 1719237410Sdelphij return block_done; 172017651Speter} 172117651Speter 1722131380Stjr#ifndef FASTEST 172317651Speter/* =========================================================================== 172417651Speter * Same as above, but achieves better compression. We use a lazy 172517651Speter * evaluation for matches: a match is finally adopted only if there is 172617651Speter * no better match at the next window position. 172717651Speter */ 172817651Speterlocal block_state deflate_slow(s, flush) 172917651Speter deflate_state *s; 173017651Speter int flush; 173117651Speter{ 1732205471Sdelphij IPos hash_head; /* head of hash chain */ 173317651Speter int bflush; /* set if current block must be flushed */ 173417651Speter 173517651Speter /* Process the input block. */ 173617651Speter for (;;) { 173717651Speter /* Make sure that we always have enough lookahead, except 173817651Speter * at the end of the input file. We need MAX_MATCH bytes 173917651Speter * for the next match, plus MIN_MATCH bytes to insert the 174017651Speter * string following the next match. 174117651Speter */ 174217651Speter if (s->lookahead < MIN_LOOKAHEAD) { 174317651Speter fill_window(s); 174417651Speter if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { 1745131380Stjr return need_more; 1746131380Stjr } 174717651Speter if (s->lookahead == 0) break; /* flush the current block */ 174817651Speter } 174917651Speter 175017651Speter /* Insert the string window[strstart .. strstart+2] in the 175117651Speter * dictionary, and set hash_head to the head of the hash chain: 175217651Speter */ 1753205471Sdelphij hash_head = NIL; 175417651Speter if (s->lookahead >= MIN_MATCH) { 175517651Speter INSERT_STRING(s, s->strstart, hash_head); 175617651Speter } 175717651Speter 175817651Speter /* Find the longest match, discarding those <= prev_length. 175917651Speter */ 176017651Speter s->prev_length = s->match_length, s->prev_match = s->match_start; 176117651Speter s->match_length = MIN_MATCH-1; 176217651Speter 176317651Speter if (hash_head != NIL && s->prev_length < s->max_lazy_match && 176417651Speter s->strstart - hash_head <= MAX_DIST(s)) { 176517651Speter /* To simplify the code, we prevent matches with the string 176617651Speter * of window index 0 (in particular we have to avoid a match 176717651Speter * of the string with itself at the start of the input file). 176817651Speter */ 1769205471Sdelphij s->match_length = longest_match (s, hash_head); 1770205471Sdelphij /* longest_match() sets match_start */ 177117651Speter 1772131380Stjr if (s->match_length <= 5 && (s->strategy == Z_FILTERED 1773131380Stjr#if TOO_FAR <= 32767 1774131380Stjr || (s->match_length == MIN_MATCH && 1775131380Stjr s->strstart - s->match_start > TOO_FAR) 1776131380Stjr#endif 1777131380Stjr )) { 177817651Speter 177917651Speter /* If prev_match is also MIN_MATCH, match_start is garbage 178017651Speter * but we will ignore the current match anyway. 178117651Speter */ 178217651Speter s->match_length = MIN_MATCH-1; 178317651Speter } 178417651Speter } 178517651Speter /* If there was a match at the previous step and the current 178617651Speter * match is not better, output the previous match: 178717651Speter */ 178817651Speter if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) { 178917651Speter uInt max_insert = s->strstart + s->lookahead - MIN_MATCH; 179017651Speter /* Do not insert strings in hash table beyond this. */ 179117651Speter 179217651Speter check_match(s, s->strstart-1, s->prev_match, s->prev_length); 179317651Speter 179433908Ssteve _tr_tally_dist(s, s->strstart -1 - s->prev_match, 1795131380Stjr s->prev_length - MIN_MATCH, bflush); 179617651Speter 179717651Speter /* Insert in hash table all strings up to the end of the match. 179817651Speter * strstart-1 and strstart are already inserted. If there is not 179917651Speter * enough lookahead, the last two strings are not inserted in 180017651Speter * the hash table. 180117651Speter */ 180217651Speter s->lookahead -= s->prev_length-1; 180317651Speter s->prev_length -= 2; 180417651Speter do { 180517651Speter if (++s->strstart <= max_insert) { 180617651Speter INSERT_STRING(s, s->strstart, hash_head); 180717651Speter } 180817651Speter } while (--s->prev_length != 0); 180917651Speter s->match_available = 0; 181017651Speter s->match_length = MIN_MATCH-1; 181117651Speter s->strstart++; 181217651Speter 181317651Speter if (bflush) FLUSH_BLOCK(s, 0); 181417651Speter 181517651Speter } else if (s->match_available) { 181617651Speter /* If there was no match at the previous position, output a 181717651Speter * single literal. If there was a match but the current match 181817651Speter * is longer, truncate the previous match to a single literal. 181917651Speter */ 182017651Speter Tracevv((stderr,"%c", s->window[s->strstart-1])); 1821131380Stjr _tr_tally_lit(s, s->window[s->strstart-1], bflush); 1822131380Stjr if (bflush) { 182317651Speter FLUSH_BLOCK_ONLY(s, 0); 182417651Speter } 182517651Speter s->strstart++; 182617651Speter s->lookahead--; 182717651Speter if (s->strm->avail_out == 0) return need_more; 182817651Speter } else { 182917651Speter /* There is no previous match to compare with, wait for 183017651Speter * the next step to decide. 183117651Speter */ 183217651Speter s->match_available = 1; 183317651Speter s->strstart++; 183417651Speter s->lookahead--; 183517651Speter } 183617651Speter } 183717651Speter Assert (flush != Z_NO_FLUSH, "no flush?"); 183817651Speter if (s->match_available) { 183917651Speter Tracevv((stderr,"%c", s->window[s->strstart-1])); 184033908Ssteve _tr_tally_lit(s, s->window[s->strstart-1], bflush); 184117651Speter s->match_available = 0; 184217651Speter } 1843237410Sdelphij s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1; 1844237410Sdelphij if (flush == Z_FINISH) { 1845237410Sdelphij FLUSH_BLOCK(s, 1); 1846237410Sdelphij return finish_done; 1847237410Sdelphij } 1848237410Sdelphij if (s->last_lit) 1849237410Sdelphij FLUSH_BLOCK(s, 0); 1850237410Sdelphij return block_done; 185117651Speter} 1852131380Stjr#endif /* FASTEST */ 1853157046Sdes 1854157046Sdes/* =========================================================================== 1855157046Sdes * For Z_RLE, simply look for runs of bytes, generate matches only of distance 1856157046Sdes * one. Do not maintain a hash table. (It will be regenerated if this run of 1857157046Sdes * deflate switches away from Z_RLE.) 1858157046Sdes */ 1859157046Sdeslocal block_state deflate_rle(s, flush) 1860157046Sdes deflate_state *s; 1861157046Sdes int flush; 1862157046Sdes{ 1863205471Sdelphij int bflush; /* set if current block must be flushed */ 1864205471Sdelphij uInt prev; /* byte at distance one to match */ 1865205471Sdelphij Bytef *scan, *strend; /* scan goes up to strend for length of run */ 1866157046Sdes 1867157046Sdes for (;;) { 1868157046Sdes /* Make sure that we always have enough lookahead, except 1869157046Sdes * at the end of the input file. We need MAX_MATCH bytes 1870237410Sdelphij * for the longest run, plus one for the unrolled loop. 1871157046Sdes */ 1872237410Sdelphij if (s->lookahead <= MAX_MATCH) { 1873157046Sdes fill_window(s); 1874237410Sdelphij if (s->lookahead <= MAX_MATCH && flush == Z_NO_FLUSH) { 1875157046Sdes return need_more; 1876157046Sdes } 1877157046Sdes if (s->lookahead == 0) break; /* flush the current block */ 1878157046Sdes } 1879157046Sdes 1880157046Sdes /* See how many times the previous byte repeats */ 1881205471Sdelphij s->match_length = 0; 1882205471Sdelphij if (s->lookahead >= MIN_MATCH && s->strstart > 0) { 1883157046Sdes scan = s->window + s->strstart - 1; 1884205471Sdelphij prev = *scan; 1885205471Sdelphij if (prev == *++scan && prev == *++scan && prev == *++scan) { 1886205471Sdelphij strend = s->window + s->strstart + MAX_MATCH; 1887205471Sdelphij do { 1888205471Sdelphij } while (prev == *++scan && prev == *++scan && 1889205471Sdelphij prev == *++scan && prev == *++scan && 1890205471Sdelphij prev == *++scan && prev == *++scan && 1891205471Sdelphij prev == *++scan && prev == *++scan && 1892205471Sdelphij scan < strend); 1893205471Sdelphij s->match_length = MAX_MATCH - (int)(strend - scan); 1894205471Sdelphij if (s->match_length > s->lookahead) 1895205471Sdelphij s->match_length = s->lookahead; 1896205471Sdelphij } 1897237410Sdelphij Assert(scan <= s->window+(uInt)(s->window_size-1), "wild scan"); 1898157046Sdes } 1899157046Sdes 1900157046Sdes /* Emit match if have run of MIN_MATCH or longer, else emit literal */ 1901205471Sdelphij if (s->match_length >= MIN_MATCH) { 1902205471Sdelphij check_match(s, s->strstart, s->strstart - 1, s->match_length); 1903205471Sdelphij 1904205471Sdelphij _tr_tally_dist(s, 1, s->match_length - MIN_MATCH, bflush); 1905205471Sdelphij 1906205471Sdelphij s->lookahead -= s->match_length; 1907205471Sdelphij s->strstart += s->match_length; 1908205471Sdelphij s->match_length = 0; 1909157046Sdes } else { 1910157046Sdes /* No match, output a literal byte */ 1911157046Sdes Tracevv((stderr,"%c", s->window[s->strstart])); 1912157046Sdes _tr_tally_lit (s, s->window[s->strstart], bflush); 1913157046Sdes s->lookahead--; 1914157046Sdes s->strstart++; 1915157046Sdes } 1916157046Sdes if (bflush) FLUSH_BLOCK(s, 0); 1917157046Sdes } 1918237410Sdelphij s->insert = 0; 1919237410Sdelphij if (flush == Z_FINISH) { 1920237410Sdelphij FLUSH_BLOCK(s, 1); 1921237410Sdelphij return finish_done; 1922237410Sdelphij } 1923237410Sdelphij if (s->last_lit) 1924237410Sdelphij FLUSH_BLOCK(s, 0); 1925237410Sdelphij return block_done; 1926157046Sdes} 1927205471Sdelphij 1928205471Sdelphij/* =========================================================================== 1929205471Sdelphij * For Z_HUFFMAN_ONLY, do not look for matches. Do not maintain a hash table. 1930205471Sdelphij * (It will be regenerated if this run of deflate switches away from Huffman.) 1931205471Sdelphij */ 1932205471Sdelphijlocal block_state deflate_huff(s, flush) 1933205471Sdelphij deflate_state *s; 1934205471Sdelphij int flush; 1935205471Sdelphij{ 1936205471Sdelphij int bflush; /* set if current block must be flushed */ 1937205471Sdelphij 1938205471Sdelphij for (;;) { 1939205471Sdelphij /* Make sure that we have a literal to write. */ 1940205471Sdelphij if (s->lookahead == 0) { 1941205471Sdelphij fill_window(s); 1942205471Sdelphij if (s->lookahead == 0) { 1943205471Sdelphij if (flush == Z_NO_FLUSH) 1944205471Sdelphij return need_more; 1945205471Sdelphij break; /* flush the current block */ 1946205471Sdelphij } 1947205471Sdelphij } 1948205471Sdelphij 1949205471Sdelphij /* Output a literal byte */ 1950205471Sdelphij s->match_length = 0; 1951205471Sdelphij Tracevv((stderr,"%c", s->window[s->strstart])); 1952205471Sdelphij _tr_tally_lit (s, s->window[s->strstart], bflush); 1953205471Sdelphij s->lookahead--; 1954205471Sdelphij s->strstart++; 1955205471Sdelphij if (bflush) FLUSH_BLOCK(s, 0); 1956205471Sdelphij } 1957237410Sdelphij s->insert = 0; 1958237410Sdelphij if (flush == Z_FINISH) { 1959237410Sdelphij FLUSH_BLOCK(s, 1); 1960237410Sdelphij return finish_done; 1961237410Sdelphij } 1962237410Sdelphij if (s->last_lit) 1963237410Sdelphij FLUSH_BLOCK(s, 0); 1964237410Sdelphij return block_done; 1965205471Sdelphij} 1966