117651Speter/* deflate.c -- compress data using the deflation algorithm 2250261Sdelphij * Copyright (C) 1995-2013 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[] = 55250261Sdelphij " deflate 1.2.8 Copyright 1995-2013 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; 308250261Sdelphij strm->msg = 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; 332250261Sdelphij z_const 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; 362250261Sdelphij strm->next_in = (z_const 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); 516250261Sdelphij if (err == Z_BUF_ERROR && s->pending == 0) 517250261Sdelphij err = Z_OK; 51817651Speter } 51917651Speter if (s->level != level) { 520131380Stjr s->level = level; 521131380Stjr s->max_lazy_match = configuration_table[level].max_lazy; 522131380Stjr s->good_match = configuration_table[level].good_length; 523131380Stjr s->nice_match = configuration_table[level].nice_length; 524131380Stjr s->max_chain_length = configuration_table[level].max_chain; 52517651Speter } 52617651Speter s->strategy = strategy; 52717651Speter return err; 52817651Speter} 52917651Speter 530157046Sdes/* ========================================================================= */ 531157046Sdesint ZEXPORT deflateTune(strm, good_length, max_lazy, nice_length, max_chain) 532157046Sdes z_streamp strm; 533157046Sdes int good_length; 534157046Sdes int max_lazy; 535157046Sdes int nice_length; 536157046Sdes int max_chain; 537157046Sdes{ 538157046Sdes deflate_state *s; 539157046Sdes 540157046Sdes if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 541157046Sdes s = strm->state; 542157046Sdes s->good_match = good_length; 543157046Sdes s->max_lazy_match = max_lazy; 544157046Sdes s->nice_match = nice_length; 545157046Sdes s->max_chain_length = max_chain; 546157046Sdes return Z_OK; 547157046Sdes} 548157046Sdes 54917651Speter/* ========================================================================= 550131380Stjr * For the default windowBits of 15 and memLevel of 8, this function returns 551131380Stjr * a close to exact, as well as small, upper bound on the compressed size. 552131380Stjr * They are coded as constants here for a reason--if the #define's are 553131380Stjr * changed, then this function needs to be changed as well. The return 554131380Stjr * value for 15 and 8 only works for those exact settings. 555131380Stjr * 556131380Stjr * For any setting other than those defaults for windowBits and memLevel, 557131380Stjr * the value returned is a conservative worst case for the maximum expansion 558131380Stjr * resulting from using fixed blocks instead of stored blocks, which deflate 559131380Stjr * can emit on compressed data for some combinations of the parameters. 560131380Stjr * 561205471Sdelphij * This function could be more sophisticated to provide closer upper bounds for 562205471Sdelphij * every combination of windowBits and memLevel. But even the conservative 563205471Sdelphij * upper bound of about 14% expansion does not seem onerous for output buffer 564205471Sdelphij * allocation. 565131380Stjr */ 566131380StjruLong ZEXPORT deflateBound(strm, sourceLen) 567131380Stjr z_streamp strm; 568131380Stjr uLong sourceLen; 569131380Stjr{ 570131380Stjr deflate_state *s; 571205471Sdelphij uLong complen, wraplen; 572205471Sdelphij Bytef *str; 573131380Stjr 574205471Sdelphij /* conservative upper bound for compressed data */ 575205471Sdelphij complen = sourceLen + 576205471Sdelphij ((sourceLen + 7) >> 3) + ((sourceLen + 63) >> 6) + 5; 577131380Stjr 578205471Sdelphij /* if can't get parameters, return conservative bound plus zlib wrapper */ 579131380Stjr if (strm == Z_NULL || strm->state == Z_NULL) 580205471Sdelphij return complen + 6; 581131380Stjr 582205471Sdelphij /* compute wrapper length */ 583205471Sdelphij s = strm->state; 584205471Sdelphij switch (s->wrap) { 585205471Sdelphij case 0: /* raw deflate */ 586205471Sdelphij wraplen = 0; 587205471Sdelphij break; 588205471Sdelphij case 1: /* zlib wrapper */ 589205471Sdelphij wraplen = 6 + (s->strstart ? 4 : 0); 590205471Sdelphij break; 591205471Sdelphij case 2: /* gzip wrapper */ 592205471Sdelphij wraplen = 18; 593205471Sdelphij if (s->gzhead != Z_NULL) { /* user-supplied gzip header */ 594205471Sdelphij if (s->gzhead->extra != Z_NULL) 595205471Sdelphij wraplen += 2 + s->gzhead->extra_len; 596205471Sdelphij str = s->gzhead->name; 597205471Sdelphij if (str != Z_NULL) 598205471Sdelphij do { 599205471Sdelphij wraplen++; 600205471Sdelphij } while (*str++); 601205471Sdelphij str = s->gzhead->comment; 602205471Sdelphij if (str != Z_NULL) 603205471Sdelphij do { 604205471Sdelphij wraplen++; 605205471Sdelphij } while (*str++); 606205471Sdelphij if (s->gzhead->hcrc) 607205471Sdelphij wraplen += 2; 608205471Sdelphij } 609205471Sdelphij break; 610205471Sdelphij default: /* for compiler happiness */ 611205471Sdelphij wraplen = 6; 612205471Sdelphij } 613205471Sdelphij 614131380Stjr /* if not default parameters, return conservative bound */ 615131380Stjr if (s->w_bits != 15 || s->hash_bits != 8 + 7) 616205471Sdelphij return complen + wraplen; 617131380Stjr 618131380Stjr /* default settings: return tight bound for that case */ 619205471Sdelphij return sourceLen + (sourceLen >> 12) + (sourceLen >> 14) + 620205471Sdelphij (sourceLen >> 25) + 13 - 6 + wraplen; 621131380Stjr} 622131380Stjr 623131380Stjr/* ========================================================================= 62417651Speter * Put a short in the pending buffer. The 16-bit value is put in MSB order. 62517651Speter * IN assertion: the stream state is correct and there is enough room in 62617651Speter * pending_buf. 62717651Speter */ 62817651Speterlocal void putShortMSB (s, b) 62917651Speter deflate_state *s; 63017651Speter uInt b; 63117651Speter{ 63217651Speter put_byte(s, (Byte)(b >> 8)); 63317651Speter put_byte(s, (Byte)(b & 0xff)); 634131380Stjr} 63517651Speter 63617651Speter/* ========================================================================= 63717651Speter * Flush as much pending output as possible. All deflate() output goes 63817651Speter * through this function so some applications may wish to modify it 63917651Speter * to avoid allocating a large strm->next_out buffer and copying into it. 64017651Speter * (See also read_buf()). 64117651Speter */ 64217651Speterlocal void flush_pending(strm) 64317651Speter z_streamp strm; 64417651Speter{ 645237410Sdelphij unsigned len; 646237410Sdelphij deflate_state *s = strm->state; 64717651Speter 648237410Sdelphij _tr_flush_bits(s); 649237410Sdelphij len = s->pending; 65017651Speter if (len > strm->avail_out) len = strm->avail_out; 65117651Speter if (len == 0) return; 65217651Speter 653237410Sdelphij zmemcpy(strm->next_out, s->pending_out, len); 65417651Speter strm->next_out += len; 655237410Sdelphij s->pending_out += len; 65617651Speter strm->total_out += len; 65717651Speter strm->avail_out -= len; 658237410Sdelphij s->pending -= len; 659237410Sdelphij if (s->pending == 0) { 660237410Sdelphij s->pending_out = s->pending_buf; 66117651Speter } 66217651Speter} 66317651Speter 66417651Speter/* ========================================================================= */ 66533908Ssteveint ZEXPORT deflate (strm, flush) 66617651Speter z_streamp strm; 66717651Speter int flush; 66817651Speter{ 66917651Speter int old_flush; /* value of flush param for previous deflate call */ 67017651Speter deflate_state *s; 67117651Speter 67217651Speter if (strm == Z_NULL || strm->state == Z_NULL || 673205471Sdelphij flush > Z_BLOCK || flush < 0) { 67417651Speter return Z_STREAM_ERROR; 67517651Speter } 67617651Speter s = strm->state; 67717651Speter 67817651Speter if (strm->next_out == Z_NULL || 67917651Speter (strm->next_in == Z_NULL && strm->avail_in != 0) || 680131380Stjr (s->status == FINISH_STATE && flush != Z_FINISH)) { 68117651Speter ERR_RETURN(strm, Z_STREAM_ERROR); 68217651Speter } 68317651Speter if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR); 68417651Speter 68517651Speter s->strm = strm; /* just in case */ 68617651Speter old_flush = s->last_flush; 68717651Speter s->last_flush = flush; 68817651Speter 689131380Stjr /* Write the header */ 69017651Speter if (s->status == INIT_STATE) { 691131380Stjr#ifdef GZIP 692131380Stjr if (s->wrap == 2) { 693157046Sdes strm->adler = crc32(0L, Z_NULL, 0); 694131380Stjr put_byte(s, 31); 695131380Stjr put_byte(s, 139); 696131380Stjr put_byte(s, 8); 697205471Sdelphij if (s->gzhead == Z_NULL) { 698157046Sdes put_byte(s, 0); 699157046Sdes put_byte(s, 0); 700157046Sdes put_byte(s, 0); 701157046Sdes put_byte(s, 0); 702157046Sdes put_byte(s, 0); 703157046Sdes put_byte(s, s->level == 9 ? 2 : 704157046Sdes (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ? 705157046Sdes 4 : 0)); 706157046Sdes put_byte(s, OS_CODE); 707157046Sdes s->status = BUSY_STATE; 708157046Sdes } 709157046Sdes else { 710157046Sdes put_byte(s, (s->gzhead->text ? 1 : 0) + 711157046Sdes (s->gzhead->hcrc ? 2 : 0) + 712157046Sdes (s->gzhead->extra == Z_NULL ? 0 : 4) + 713157046Sdes (s->gzhead->name == Z_NULL ? 0 : 8) + 714157046Sdes (s->gzhead->comment == Z_NULL ? 0 : 16) 715157046Sdes ); 716157046Sdes put_byte(s, (Byte)(s->gzhead->time & 0xff)); 717157046Sdes put_byte(s, (Byte)((s->gzhead->time >> 8) & 0xff)); 718157046Sdes put_byte(s, (Byte)((s->gzhead->time >> 16) & 0xff)); 719157046Sdes put_byte(s, (Byte)((s->gzhead->time >> 24) & 0xff)); 720157046Sdes put_byte(s, s->level == 9 ? 2 : 721157046Sdes (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ? 722157046Sdes 4 : 0)); 723157046Sdes put_byte(s, s->gzhead->os & 0xff); 724205471Sdelphij if (s->gzhead->extra != Z_NULL) { 725157046Sdes put_byte(s, s->gzhead->extra_len & 0xff); 726157046Sdes put_byte(s, (s->gzhead->extra_len >> 8) & 0xff); 727157046Sdes } 728157046Sdes if (s->gzhead->hcrc) 729157046Sdes strm->adler = crc32(strm->adler, s->pending_buf, 730157046Sdes s->pending); 731157046Sdes s->gzindex = 0; 732157046Sdes s->status = EXTRA_STATE; 733157046Sdes } 734131380Stjr } 735131380Stjr else 736131380Stjr#endif 737131380Stjr { 738131380Stjr uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8; 739131380Stjr uInt level_flags; 74017651Speter 741131380Stjr if (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2) 742131380Stjr level_flags = 0; 743131380Stjr else if (s->level < 6) 744131380Stjr level_flags = 1; 745131380Stjr else if (s->level == 6) 746131380Stjr level_flags = 2; 747131380Stjr else 748131380Stjr level_flags = 3; 749131380Stjr header |= (level_flags << 6); 750131380Stjr if (s->strstart != 0) header |= PRESET_DICT; 751131380Stjr header += 31 - (header % 31); 75217651Speter 753131380Stjr s->status = BUSY_STATE; 754131380Stjr putShortMSB(s, header); 75517651Speter 756131380Stjr /* Save the adler32 of the preset dictionary: */ 757131380Stjr if (s->strstart != 0) { 758131380Stjr putShortMSB(s, (uInt)(strm->adler >> 16)); 759131380Stjr putShortMSB(s, (uInt)(strm->adler & 0xffff)); 760131380Stjr } 761131380Stjr strm->adler = adler32(0L, Z_NULL, 0); 762131380Stjr } 76317651Speter } 764157046Sdes#ifdef GZIP 765157046Sdes if (s->status == EXTRA_STATE) { 766205471Sdelphij if (s->gzhead->extra != Z_NULL) { 767157046Sdes uInt beg = s->pending; /* start of bytes to update crc */ 76817651Speter 769157046Sdes while (s->gzindex < (s->gzhead->extra_len & 0xffff)) { 770157046Sdes if (s->pending == s->pending_buf_size) { 771157046Sdes if (s->gzhead->hcrc && s->pending > beg) 772157046Sdes strm->adler = crc32(strm->adler, s->pending_buf + beg, 773157046Sdes s->pending - beg); 774157046Sdes flush_pending(strm); 775157046Sdes beg = s->pending; 776157046Sdes if (s->pending == s->pending_buf_size) 777157046Sdes break; 778157046Sdes } 779157046Sdes put_byte(s, s->gzhead->extra[s->gzindex]); 780157046Sdes s->gzindex++; 781157046Sdes } 782157046Sdes if (s->gzhead->hcrc && s->pending > beg) 783157046Sdes strm->adler = crc32(strm->adler, s->pending_buf + beg, 784157046Sdes s->pending - beg); 785157046Sdes if (s->gzindex == s->gzhead->extra_len) { 786157046Sdes s->gzindex = 0; 787157046Sdes s->status = NAME_STATE; 788157046Sdes } 789157046Sdes } 790157046Sdes else 791157046Sdes s->status = NAME_STATE; 792157046Sdes } 793157046Sdes if (s->status == NAME_STATE) { 794205471Sdelphij if (s->gzhead->name != Z_NULL) { 795157046Sdes uInt beg = s->pending; /* start of bytes to update crc */ 796157046Sdes int val; 797157046Sdes 798157046Sdes do { 799157046Sdes if (s->pending == s->pending_buf_size) { 800157046Sdes if (s->gzhead->hcrc && s->pending > beg) 801157046Sdes strm->adler = crc32(strm->adler, s->pending_buf + beg, 802157046Sdes s->pending - beg); 803157046Sdes flush_pending(strm); 804157046Sdes beg = s->pending; 805157046Sdes if (s->pending == s->pending_buf_size) { 806157046Sdes val = 1; 807157046Sdes break; 808157046Sdes } 809157046Sdes } 810157046Sdes val = s->gzhead->name[s->gzindex++]; 811157046Sdes put_byte(s, val); 812157046Sdes } while (val != 0); 813157046Sdes if (s->gzhead->hcrc && s->pending > beg) 814157046Sdes strm->adler = crc32(strm->adler, s->pending_buf + beg, 815157046Sdes s->pending - beg); 816157046Sdes if (val == 0) { 817157046Sdes s->gzindex = 0; 818157046Sdes s->status = COMMENT_STATE; 819157046Sdes } 820157046Sdes } 821157046Sdes else 822157046Sdes s->status = COMMENT_STATE; 823157046Sdes } 824157046Sdes if (s->status == COMMENT_STATE) { 825205471Sdelphij if (s->gzhead->comment != Z_NULL) { 826157046Sdes uInt beg = s->pending; /* start of bytes to update crc */ 827157046Sdes int val; 828157046Sdes 829157046Sdes do { 830157046Sdes if (s->pending == s->pending_buf_size) { 831157046Sdes if (s->gzhead->hcrc && s->pending > beg) 832157046Sdes strm->adler = crc32(strm->adler, s->pending_buf + beg, 833157046Sdes s->pending - beg); 834157046Sdes flush_pending(strm); 835157046Sdes beg = s->pending; 836157046Sdes if (s->pending == s->pending_buf_size) { 837157046Sdes val = 1; 838157046Sdes break; 839157046Sdes } 840157046Sdes } 841157046Sdes val = s->gzhead->comment[s->gzindex++]; 842157046Sdes put_byte(s, val); 843157046Sdes } while (val != 0); 844157046Sdes if (s->gzhead->hcrc && s->pending > beg) 845157046Sdes strm->adler = crc32(strm->adler, s->pending_buf + beg, 846157046Sdes s->pending - beg); 847157046Sdes if (val == 0) 848157046Sdes s->status = HCRC_STATE; 849157046Sdes } 850157046Sdes else 851157046Sdes s->status = HCRC_STATE; 852157046Sdes } 853157046Sdes if (s->status == HCRC_STATE) { 854157046Sdes if (s->gzhead->hcrc) { 855157046Sdes if (s->pending + 2 > s->pending_buf_size) 856157046Sdes flush_pending(strm); 857157046Sdes if (s->pending + 2 <= s->pending_buf_size) { 858157046Sdes put_byte(s, (Byte)(strm->adler & 0xff)); 859157046Sdes put_byte(s, (Byte)((strm->adler >> 8) & 0xff)); 860157046Sdes strm->adler = crc32(0L, Z_NULL, 0); 861157046Sdes s->status = BUSY_STATE; 862157046Sdes } 863157046Sdes } 864157046Sdes else 865157046Sdes s->status = BUSY_STATE; 866157046Sdes } 867157046Sdes#endif 868157046Sdes 86917651Speter /* Flush as much pending output as possible */ 87017651Speter if (s->pending != 0) { 87117651Speter flush_pending(strm); 87217651Speter if (strm->avail_out == 0) { 873131380Stjr /* Since avail_out is 0, deflate will be called again with 874131380Stjr * more output space, but possibly with both pending and 875131380Stjr * avail_in equal to zero. There won't be anything to do, 876131380Stjr * but this is not an error situation so make sure we 877131380Stjr * return OK instead of BUF_ERROR at next call of deflate: 87817651Speter */ 879131380Stjr s->last_flush = -1; 880131380Stjr return Z_OK; 881131380Stjr } 88217651Speter 88317651Speter /* Make sure there is something to do and avoid duplicate consecutive 88417651Speter * flushes. For repeated and useless calls with Z_FINISH, we keep 885131380Stjr * returning Z_STREAM_END instead of Z_BUF_ERROR. 88617651Speter */ 887237410Sdelphij } else if (strm->avail_in == 0 && RANK(flush) <= RANK(old_flush) && 888131380Stjr flush != Z_FINISH) { 88917651Speter ERR_RETURN(strm, Z_BUF_ERROR); 89017651Speter } 89117651Speter 89217651Speter /* User must not provide more input after the first FINISH: */ 89317651Speter if (s->status == FINISH_STATE && strm->avail_in != 0) { 89417651Speter ERR_RETURN(strm, Z_BUF_ERROR); 89517651Speter } 89617651Speter 89717651Speter /* Start a new block or continue the current one. 89817651Speter */ 89917651Speter if (strm->avail_in != 0 || s->lookahead != 0 || 90017651Speter (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) { 90117651Speter block_state bstate; 90217651Speter 903205471Sdelphij bstate = s->strategy == Z_HUFFMAN_ONLY ? deflate_huff(s, flush) : 904205471Sdelphij (s->strategy == Z_RLE ? deflate_rle(s, flush) : 905205471Sdelphij (*(configuration_table[s->level].func))(s, flush)); 90617651Speter 90717651Speter if (bstate == finish_started || bstate == finish_done) { 90817651Speter s->status = FINISH_STATE; 90917651Speter } 91017651Speter if (bstate == need_more || bstate == finish_started) { 911131380Stjr if (strm->avail_out == 0) { 912131380Stjr s->last_flush = -1; /* avoid BUF_ERROR next call, see above */ 913131380Stjr } 914131380Stjr return Z_OK; 915131380Stjr /* If flush != Z_NO_FLUSH && avail_out == 0, the next call 916131380Stjr * of deflate should use the same flush parameter to make sure 917131380Stjr * that the flush is complete. So we don't have to output an 918131380Stjr * empty block here, this will be done at next call. This also 919131380Stjr * ensures that for a very small output buffer, we emit at most 920131380Stjr * one empty block. 921131380Stjr */ 922131380Stjr } 92317651Speter if (bstate == block_done) { 92417651Speter if (flush == Z_PARTIAL_FLUSH) { 92517651Speter _tr_align(s); 926205471Sdelphij } else if (flush != Z_BLOCK) { /* FULL_FLUSH or SYNC_FLUSH */ 92717651Speter _tr_stored_block(s, (char*)0, 0L, 0); 92817651Speter /* For a full flush, this empty block will be recognized 92917651Speter * as a special marker by inflate_sync(). 93017651Speter */ 93117651Speter if (flush == Z_FULL_FLUSH) { 93217651Speter CLEAR_HASH(s); /* forget history */ 933205471Sdelphij if (s->lookahead == 0) { 934205471Sdelphij s->strstart = 0; 935205471Sdelphij s->block_start = 0L; 936237410Sdelphij s->insert = 0; 937205471Sdelphij } 93817651Speter } 93917651Speter } 94017651Speter flush_pending(strm); 941131380Stjr if (strm->avail_out == 0) { 942131380Stjr s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */ 943131380Stjr return Z_OK; 944131380Stjr } 94517651Speter } 94617651Speter } 94717651Speter Assert(strm->avail_out > 0, "bug2"); 94817651Speter 94917651Speter if (flush != Z_FINISH) return Z_OK; 950131380Stjr if (s->wrap <= 0) return Z_STREAM_END; 95117651Speter 952131380Stjr /* Write the trailer */ 953131380Stjr#ifdef GZIP 954131380Stjr if (s->wrap == 2) { 955131380Stjr put_byte(s, (Byte)(strm->adler & 0xff)); 956131380Stjr put_byte(s, (Byte)((strm->adler >> 8) & 0xff)); 957131380Stjr put_byte(s, (Byte)((strm->adler >> 16) & 0xff)); 958131380Stjr put_byte(s, (Byte)((strm->adler >> 24) & 0xff)); 959131380Stjr put_byte(s, (Byte)(strm->total_in & 0xff)); 960131380Stjr put_byte(s, (Byte)((strm->total_in >> 8) & 0xff)); 961131380Stjr put_byte(s, (Byte)((strm->total_in >> 16) & 0xff)); 962131380Stjr put_byte(s, (Byte)((strm->total_in >> 24) & 0xff)); 963131380Stjr } 964131380Stjr else 965131380Stjr#endif 966131380Stjr { 967131380Stjr putShortMSB(s, (uInt)(strm->adler >> 16)); 968131380Stjr putShortMSB(s, (uInt)(strm->adler & 0xffff)); 969131380Stjr } 97017651Speter flush_pending(strm); 97117651Speter /* If avail_out is zero, the application will call deflate again 97217651Speter * to flush the rest. 97317651Speter */ 974131380Stjr if (s->wrap > 0) s->wrap = -s->wrap; /* write the trailer only once! */ 97517651Speter return s->pending != 0 ? Z_OK : Z_STREAM_END; 97617651Speter} 97717651Speter 97817651Speter/* ========================================================================= */ 97933908Ssteveint ZEXPORT deflateEnd (strm) 98017651Speter z_streamp strm; 98117651Speter{ 98217651Speter int status; 98317651Speter 98417651Speter if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 98517651Speter 98633908Ssteve status = strm->state->status; 987157046Sdes if (status != INIT_STATE && 988157046Sdes status != EXTRA_STATE && 989157046Sdes status != NAME_STATE && 990157046Sdes status != COMMENT_STATE && 991157046Sdes status != HCRC_STATE && 992157046Sdes status != BUSY_STATE && 993131380Stjr status != FINISH_STATE) { 99433908Ssteve return Z_STREAM_ERROR; 99533908Ssteve } 99633908Ssteve 99717651Speter /* Deallocate in reverse order of allocations: */ 99817651Speter TRY_FREE(strm, strm->state->pending_buf); 99917651Speter TRY_FREE(strm, strm->state->head); 100017651Speter TRY_FREE(strm, strm->state->prev); 100117651Speter TRY_FREE(strm, strm->state->window); 100217651Speter 100317651Speter ZFREE(strm, strm->state); 100417651Speter strm->state = Z_NULL; 100517651Speter 100617651Speter return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK; 100717651Speter} 100817651Speter 100933908Ssteve/* ========================================================================= 101033908Ssteve * Copy the source state to the destination state. 101133908Ssteve * To simplify the source, this is not supported for 16-bit MSDOS (which 101233908Ssteve * doesn't have enough memory anyway to duplicate compression states). 101333908Ssteve */ 101433908Ssteveint ZEXPORT deflateCopy (dest, source) 101517651Speter z_streamp dest; 101617651Speter z_streamp source; 101717651Speter{ 101833908Ssteve#ifdef MAXSEG_64K 101933908Ssteve return Z_STREAM_ERROR; 102033908Ssteve#else 102133908Ssteve deflate_state *ds; 102233908Ssteve deflate_state *ss; 102333908Ssteve ushf *overlay; 102433908Ssteve 102533908Ssteve 102642471Speter if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL) { 102717651Speter return Z_STREAM_ERROR; 102817651Speter } 102942471Speter 103042471Speter ss = source->state; 103142471Speter 1032237410Sdelphij zmemcpy((voidpf)dest, (voidpf)source, sizeof(z_stream)); 103317651Speter 103433908Ssteve ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state)); 103533908Ssteve if (ds == Z_NULL) return Z_MEM_ERROR; 103633908Ssteve dest->state = (struct internal_state FAR *) ds; 1037237410Sdelphij zmemcpy((voidpf)ds, (voidpf)ss, sizeof(deflate_state)); 103833908Ssteve ds->strm = dest; 103933908Ssteve 104033908Ssteve ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte)); 104133908Ssteve ds->prev = (Posf *) ZALLOC(dest, ds->w_size, sizeof(Pos)); 104233908Ssteve ds->head = (Posf *) ZALLOC(dest, ds->hash_size, sizeof(Pos)); 104333908Ssteve overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof(ush)+2); 104433908Ssteve ds->pending_buf = (uchf *) overlay; 104533908Ssteve 104633908Ssteve if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL || 104733908Ssteve ds->pending_buf == Z_NULL) { 104833908Ssteve deflateEnd (dest); 104933908Ssteve return Z_MEM_ERROR; 105033908Ssteve } 105133908Ssteve /* following zmemcpy do not work for 16-bit MSDOS */ 105233908Ssteve zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte)); 1053237410Sdelphij zmemcpy((voidpf)ds->prev, (voidpf)ss->prev, ds->w_size * sizeof(Pos)); 1054237410Sdelphij zmemcpy((voidpf)ds->head, (voidpf)ss->head, ds->hash_size * sizeof(Pos)); 105533908Ssteve zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size); 105633908Ssteve 105733908Ssteve ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf); 105833908Ssteve ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush); 105933908Ssteve ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize; 106033908Ssteve 106133908Ssteve ds->l_desc.dyn_tree = ds->dyn_ltree; 106233908Ssteve ds->d_desc.dyn_tree = ds->dyn_dtree; 106333908Ssteve ds->bl_desc.dyn_tree = ds->bl_tree; 106433908Ssteve 106517651Speter return Z_OK; 1066131380Stjr#endif /* MAXSEG_64K */ 106717651Speter} 106817651Speter 106917651Speter/* =========================================================================== 107017651Speter * Read a new buffer from the current input stream, update the adler32 107117651Speter * and total number of bytes read. All deflate() input goes through 107217651Speter * this function so some applications may wish to modify it to avoid 107317651Speter * allocating a large strm->next_in buffer and copying from it. 107417651Speter * (See also flush_pending()). 107517651Speter */ 107617651Speterlocal int read_buf(strm, buf, size) 107717651Speter z_streamp strm; 107833908Ssteve Bytef *buf; 107917651Speter unsigned size; 108017651Speter{ 108117651Speter unsigned len = strm->avail_in; 108217651Speter 108317651Speter if (len > size) len = size; 108417651Speter if (len == 0) return 0; 108517651Speter 108617651Speter strm->avail_in -= len; 108717651Speter 1088237410Sdelphij zmemcpy(buf, strm->next_in, len); 1089131380Stjr if (strm->state->wrap == 1) { 1090237410Sdelphij strm->adler = adler32(strm->adler, buf, len); 109117651Speter } 1092131380Stjr#ifdef GZIP 1093131380Stjr else if (strm->state->wrap == 2) { 1094237410Sdelphij strm->adler = crc32(strm->adler, buf, len); 1095131380Stjr } 1096131380Stjr#endif 109717651Speter strm->next_in += len; 109817651Speter strm->total_in += len; 109917651Speter 110017651Speter return (int)len; 110117651Speter} 110217651Speter 110317651Speter/* =========================================================================== 110417651Speter * Initialize the "longest match" routines for a new zlib stream 110517651Speter */ 110617651Speterlocal void lm_init (s) 110717651Speter deflate_state *s; 110817651Speter{ 110917651Speter s->window_size = (ulg)2L*s->w_size; 111017651Speter 111117651Speter CLEAR_HASH(s); 111217651Speter 111317651Speter /* Set the default configuration parameters: 111417651Speter */ 111517651Speter s->max_lazy_match = configuration_table[s->level].max_lazy; 111617651Speter s->good_match = configuration_table[s->level].good_length; 111717651Speter s->nice_match = configuration_table[s->level].nice_length; 111817651Speter s->max_chain_length = configuration_table[s->level].max_chain; 111917651Speter 112017651Speter s->strstart = 0; 112117651Speter s->block_start = 0L; 112217651Speter s->lookahead = 0; 1123237410Sdelphij s->insert = 0; 112417651Speter s->match_length = s->prev_length = MIN_MATCH-1; 112517651Speter s->match_available = 0; 112617651Speter s->ins_h = 0; 1127157046Sdes#ifndef FASTEST 112817651Speter#ifdef ASMV 112917651Speter match_init(); /* initialize the asm code */ 113017651Speter#endif 1131157046Sdes#endif 113217651Speter} 113317651Speter 1134131380Stjr#ifndef FASTEST 113517651Speter/* =========================================================================== 113617651Speter * Set match_start to the longest match starting at the given string and 113717651Speter * return its length. Matches shorter or equal to prev_length are discarded, 113817651Speter * in which case the result is equal to prev_length and match_start is 113917651Speter * garbage. 114017651Speter * IN assertions: cur_match is the head of the hash chain for the current 114117651Speter * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1 114217651Speter * OUT assertion: the match length is not greater than s->lookahead. 114317651Speter */ 114417651Speter#ifndef ASMV 114517651Speter/* For 80x86 and 680x0, an optimized version will be provided in match.asm or 114617651Speter * match.S. The code will be functionally equivalent. 114717651Speter */ 114817651Speterlocal uInt longest_match(s, cur_match) 114917651Speter deflate_state *s; 115017651Speter IPos cur_match; /* current match */ 115117651Speter{ 115217651Speter unsigned chain_length = s->max_chain_length;/* max hash chain length */ 115317651Speter register Bytef *scan = s->window + s->strstart; /* current string */ 115417651Speter register Bytef *match; /* matched string */ 115517651Speter register int len; /* length of current match */ 115617651Speter int best_len = s->prev_length; /* best match length so far */ 115717651Speter int nice_match = s->nice_match; /* stop if match long enough */ 115817651Speter IPos limit = s->strstart > (IPos)MAX_DIST(s) ? 115917651Speter s->strstart - (IPos)MAX_DIST(s) : NIL; 116017651Speter /* Stop when cur_match becomes <= limit. To simplify the code, 116117651Speter * we prevent matches with the string of window index 0. 116217651Speter */ 116317651Speter Posf *prev = s->prev; 116417651Speter uInt wmask = s->w_mask; 116517651Speter 116617651Speter#ifdef UNALIGNED_OK 116717651Speter /* Compare two bytes at a time. Note: this is not always beneficial. 116817651Speter * Try with and without -DUNALIGNED_OK to check. 116917651Speter */ 117017651Speter register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1; 117117651Speter register ush scan_start = *(ushf*)scan; 117217651Speter register ush scan_end = *(ushf*)(scan+best_len-1); 117317651Speter#else 117417651Speter register Bytef *strend = s->window + s->strstart + MAX_MATCH; 117517651Speter register Byte scan_end1 = scan[best_len-1]; 117617651Speter register Byte scan_end = scan[best_len]; 117717651Speter#endif 117817651Speter 117917651Speter /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. 118017651Speter * It is easy to get rid of this optimization if necessary. 118117651Speter */ 118217651Speter Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever"); 118317651Speter 118417651Speter /* Do not waste too much time if we already have a good match: */ 118517651Speter if (s->prev_length >= s->good_match) { 118617651Speter chain_length >>= 2; 118717651Speter } 118817651Speter /* Do not look for matches beyond the end of the input. This is necessary 118917651Speter * to make deflate deterministic. 119017651Speter */ 119117651Speter if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead; 119217651Speter 119317651Speter Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead"); 119417651Speter 119517651Speter do { 119617651Speter Assert(cur_match < s->strstart, "no future"); 119717651Speter match = s->window + cur_match; 119817651Speter 119917651Speter /* Skip to next match if the match length cannot increase 1200157046Sdes * or if the match length is less than 2. Note that the checks below 1201157046Sdes * for insufficient lookahead only occur occasionally for performance 1202157046Sdes * reasons. Therefore uninitialized memory will be accessed, and 1203157046Sdes * conditional jumps will be made that depend on those values. 1204157046Sdes * However the length of the match is limited to the lookahead, so 1205157046Sdes * the output of deflate is not affected by the uninitialized values. 120617651Speter */ 120717651Speter#if (defined(UNALIGNED_OK) && MAX_MATCH == 258) 120817651Speter /* This code assumes sizeof(unsigned short) == 2. Do not use 120917651Speter * UNALIGNED_OK if your compiler uses a different size. 121017651Speter */ 121117651Speter if (*(ushf*)(match+best_len-1) != scan_end || 121217651Speter *(ushf*)match != scan_start) continue; 121317651Speter 121417651Speter /* It is not necessary to compare scan[2] and match[2] since they are 121517651Speter * always equal when the other bytes match, given that the hash keys 121617651Speter * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at 121717651Speter * strstart+3, +5, ... up to strstart+257. We check for insufficient 121817651Speter * lookahead only every 4th comparison; the 128th check will be made 121917651Speter * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is 122017651Speter * necessary to put more guard bytes at the end of the window, or 122117651Speter * to check more often for insufficient lookahead. 122217651Speter */ 122317651Speter Assert(scan[2] == match[2], "scan[2]?"); 122417651Speter scan++, match++; 122517651Speter do { 122617651Speter } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) && 122717651Speter *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 122817651Speter *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 122917651Speter *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 123017651Speter scan < strend); 123117651Speter /* The funny "do {}" generates better code on most compilers */ 123217651Speter 123317651Speter /* Here, scan <= window+strstart+257 */ 123417651Speter Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 123517651Speter if (*scan == *match) scan++; 123617651Speter 123717651Speter len = (MAX_MATCH - 1) - (int)(strend-scan); 123817651Speter scan = strend - (MAX_MATCH-1); 123917651Speter 124017651Speter#else /* UNALIGNED_OK */ 124117651Speter 124217651Speter if (match[best_len] != scan_end || 124317651Speter match[best_len-1] != scan_end1 || 124417651Speter *match != *scan || 124517651Speter *++match != scan[1]) continue; 124617651Speter 124717651Speter /* The check at best_len-1 can be removed because it will be made 124817651Speter * again later. (This heuristic is not always a win.) 124917651Speter * It is not necessary to compare scan[2] and match[2] since they 125017651Speter * are always equal when the other bytes match, given that 125117651Speter * the hash keys are equal and that HASH_BITS >= 8. 125217651Speter */ 125317651Speter scan += 2, match++; 125417651Speter Assert(*scan == *match, "match[2]?"); 125517651Speter 125617651Speter /* We check for insufficient lookahead only every 8th comparison; 125717651Speter * the 256th check will be made at strstart+258. 125817651Speter */ 125917651Speter do { 126017651Speter } while (*++scan == *++match && *++scan == *++match && 126117651Speter *++scan == *++match && *++scan == *++match && 126217651Speter *++scan == *++match && *++scan == *++match && 126317651Speter *++scan == *++match && *++scan == *++match && 126417651Speter scan < strend); 126517651Speter 126617651Speter Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 126717651Speter 126817651Speter len = MAX_MATCH - (int)(strend - scan); 126917651Speter scan = strend - MAX_MATCH; 127017651Speter 127117651Speter#endif /* UNALIGNED_OK */ 127217651Speter 127317651Speter if (len > best_len) { 127417651Speter s->match_start = cur_match; 127517651Speter best_len = len; 127617651Speter if (len >= nice_match) break; 127717651Speter#ifdef UNALIGNED_OK 127817651Speter scan_end = *(ushf*)(scan+best_len-1); 127917651Speter#else 128017651Speter scan_end1 = scan[best_len-1]; 128117651Speter scan_end = scan[best_len]; 128217651Speter#endif 128317651Speter } 128417651Speter } while ((cur_match = prev[cur_match & wmask]) > limit 128517651Speter && --chain_length != 0); 128617651Speter 128733908Ssteve if ((uInt)best_len <= s->lookahead) return (uInt)best_len; 128817651Speter return s->lookahead; 128917651Speter} 1290131380Stjr#endif /* ASMV */ 129133908Ssteve 1292205471Sdelphij#else /* FASTEST */ 1293205471Sdelphij 129433908Ssteve/* --------------------------------------------------------------------------- 1295205471Sdelphij * Optimized version for FASTEST only 129633908Ssteve */ 1297205471Sdelphijlocal uInt longest_match(s, cur_match) 129833908Ssteve deflate_state *s; 129933908Ssteve IPos cur_match; /* current match */ 130033908Ssteve{ 130133908Ssteve register Bytef *scan = s->window + s->strstart; /* current string */ 130233908Ssteve register Bytef *match; /* matched string */ 130333908Ssteve register int len; /* length of current match */ 130433908Ssteve register Bytef *strend = s->window + s->strstart + MAX_MATCH; 130533908Ssteve 130633908Ssteve /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. 130733908Ssteve * It is easy to get rid of this optimization if necessary. 130833908Ssteve */ 130933908Ssteve Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever"); 131033908Ssteve 131133908Ssteve Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead"); 131233908Ssteve 131333908Ssteve Assert(cur_match < s->strstart, "no future"); 131433908Ssteve 131533908Ssteve match = s->window + cur_match; 131633908Ssteve 131733908Ssteve /* Return failure if the match length is less than 2: 131833908Ssteve */ 131933908Ssteve if (match[0] != scan[0] || match[1] != scan[1]) return MIN_MATCH-1; 132033908Ssteve 132133908Ssteve /* The check at best_len-1 can be removed because it will be made 132233908Ssteve * again later. (This heuristic is not always a win.) 132333908Ssteve * It is not necessary to compare scan[2] and match[2] since they 132433908Ssteve * are always equal when the other bytes match, given that 132533908Ssteve * the hash keys are equal and that HASH_BITS >= 8. 132633908Ssteve */ 132733908Ssteve scan += 2, match += 2; 132833908Ssteve Assert(*scan == *match, "match[2]?"); 132933908Ssteve 133033908Ssteve /* We check for insufficient lookahead only every 8th comparison; 133133908Ssteve * the 256th check will be made at strstart+258. 133233908Ssteve */ 133333908Ssteve do { 133433908Ssteve } while (*++scan == *++match && *++scan == *++match && 1335131380Stjr *++scan == *++match && *++scan == *++match && 1336131380Stjr *++scan == *++match && *++scan == *++match && 1337131380Stjr *++scan == *++match && *++scan == *++match && 1338131380Stjr scan < strend); 133933908Ssteve 134033908Ssteve Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 134133908Ssteve 134233908Ssteve len = MAX_MATCH - (int)(strend - scan); 134333908Ssteve 134433908Ssteve if (len < MIN_MATCH) return MIN_MATCH - 1; 134533908Ssteve 134633908Ssteve s->match_start = cur_match; 1347131380Stjr return (uInt)len <= s->lookahead ? (uInt)len : s->lookahead; 134833908Ssteve} 134917651Speter 1350205471Sdelphij#endif /* FASTEST */ 1351205471Sdelphij 135217651Speter#ifdef DEBUG 135317651Speter/* =========================================================================== 135417651Speter * Check that the match at match_start is indeed a match. 135517651Speter */ 135617651Speterlocal void check_match(s, start, match, length) 135717651Speter deflate_state *s; 135817651Speter IPos start, match; 135917651Speter int length; 136017651Speter{ 136117651Speter /* check that the match is indeed a match */ 136233908Ssteve if (zmemcmp(s->window + match, 136333908Ssteve s->window + start, length) != EQUAL) { 136417651Speter fprintf(stderr, " start %u, match %u, length %d\n", 1365131380Stjr start, match, length); 136617651Speter do { 1367131380Stjr fprintf(stderr, "%c%c", s->window[match++], s->window[start++]); 1368131380Stjr } while (--length != 0); 136917651Speter z_error("invalid match"); 137017651Speter } 137133908Ssteve if (z_verbose > 1) { 137217651Speter fprintf(stderr,"\\[%d,%d]", start-match, length); 137317651Speter do { putc(s->window[start++], stderr); } while (--length != 0); 137417651Speter } 137517651Speter} 137617651Speter#else 137717651Speter# define check_match(s, start, match, length) 1378131380Stjr#endif /* DEBUG */ 137917651Speter 138017651Speter/* =========================================================================== 138117651Speter * Fill the window when the lookahead becomes insufficient. 138217651Speter * Updates strstart and lookahead. 138317651Speter * 138417651Speter * IN assertion: lookahead < MIN_LOOKAHEAD 138517651Speter * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD 138617651Speter * At least one byte has been read, or avail_in == 0; reads are 138717651Speter * performed for at least two bytes (required for the zip translate_eol 138817651Speter * option -- not supported here). 138917651Speter */ 139017651Speterlocal void fill_window(s) 139117651Speter deflate_state *s; 139217651Speter{ 139317651Speter register unsigned n, m; 139417651Speter register Posf *p; 139517651Speter unsigned more; /* Amount of free space at the end of the window. */ 139617651Speter uInt wsize = s->w_size; 139717651Speter 1398237410Sdelphij Assert(s->lookahead < MIN_LOOKAHEAD, "already enough lookahead"); 1399237410Sdelphij 140017651Speter do { 140117651Speter more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart); 140217651Speter 140317651Speter /* Deal with !@#$% 64K limit: */ 1404131380Stjr if (sizeof(int) <= 2) { 1405131380Stjr if (more == 0 && s->strstart == 0 && s->lookahead == 0) { 1406131380Stjr more = wsize; 140717651Speter 1408131380Stjr } else if (more == (unsigned)(-1)) { 1409131380Stjr /* Very unlikely, but possible on 16 bit machine if 1410131380Stjr * strstart == 0 && lookahead == 1 (input done a byte at time) 1411131380Stjr */ 1412131380Stjr more--; 1413131380Stjr } 1414131380Stjr } 141517651Speter 141617651Speter /* If the window is almost full and there is insufficient lookahead, 141717651Speter * move the upper half to the lower one to make room in the upper half. 141817651Speter */ 1419131380Stjr if (s->strstart >= wsize+MAX_DIST(s)) { 142017651Speter 142133908Ssteve zmemcpy(s->window, s->window+wsize, (unsigned)wsize); 142217651Speter s->match_start -= wsize; 142317651Speter s->strstart -= wsize; /* we now have strstart >= MAX_DIST */ 142417651Speter s->block_start -= (long) wsize; 142517651Speter 142617651Speter /* Slide the hash table (could be avoided with 32 bit values 142733908Ssteve at the expense of memory usage). We slide even when level == 0 142833908Ssteve to keep the hash table consistent if we switch back to level > 0 142933908Ssteve later. (Using level 0 permanently is not an optimal usage of 143033908Ssteve zlib, so we don't care about this pathological case.) 143117651Speter */ 1432131380Stjr n = s->hash_size; 1433131380Stjr p = &s->head[n]; 1434131380Stjr do { 1435131380Stjr m = *--p; 1436131380Stjr *p = (Pos)(m >= wsize ? m-wsize : NIL); 1437131380Stjr } while (--n); 143817651Speter 1439131380Stjr n = wsize; 144033908Ssteve#ifndef FASTEST 1441131380Stjr p = &s->prev[n]; 1442131380Stjr do { 1443131380Stjr m = *--p; 1444131380Stjr *p = (Pos)(m >= wsize ? m-wsize : NIL); 1445131380Stjr /* If n is not on any hash chain, prev[n] is garbage but 1446131380Stjr * its value will never be used. 1447131380Stjr */ 1448131380Stjr } while (--n); 144933908Ssteve#endif 145017651Speter more += wsize; 145117651Speter } 1452237410Sdelphij if (s->strm->avail_in == 0) break; 145317651Speter 145417651Speter /* If there was no sliding: 145517651Speter * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 && 145617651Speter * more == window_size - lookahead - strstart 145717651Speter * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1) 145817651Speter * => more >= window_size - 2*WSIZE + 2 145917651Speter * In the BIG_MEM or MMAP case (not yet supported), 146017651Speter * window_size == input_size + MIN_LOOKAHEAD && 146117651Speter * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD. 146217651Speter * Otherwise, window_size == 2*WSIZE so more >= 2. 146317651Speter * If there was sliding, more >= WSIZE. So in all cases, more >= 2. 146417651Speter */ 146517651Speter Assert(more >= 2, "more < 2"); 146617651Speter 146733908Ssteve n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more); 146817651Speter s->lookahead += n; 146917651Speter 147017651Speter /* Initialize the hash value now that we have some input: */ 1471237410Sdelphij if (s->lookahead + s->insert >= MIN_MATCH) { 1472237410Sdelphij uInt str = s->strstart - s->insert; 1473237410Sdelphij s->ins_h = s->window[str]; 1474237410Sdelphij UPDATE_HASH(s, s->ins_h, s->window[str + 1]); 147517651Speter#if MIN_MATCH != 3 147617651Speter Call UPDATE_HASH() MIN_MATCH-3 more times 147717651Speter#endif 1478237410Sdelphij while (s->insert) { 1479237410Sdelphij UPDATE_HASH(s, s->ins_h, s->window[str + MIN_MATCH-1]); 1480237410Sdelphij#ifndef FASTEST 1481237410Sdelphij s->prev[str & s->w_mask] = s->head[s->ins_h]; 1482237410Sdelphij#endif 1483237410Sdelphij s->head[s->ins_h] = (Pos)str; 1484237410Sdelphij str++; 1485237410Sdelphij s->insert--; 1486237410Sdelphij if (s->lookahead + s->insert < MIN_MATCH) 1487237410Sdelphij break; 1488237410Sdelphij } 148917651Speter } 149017651Speter /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage, 149117651Speter * but this is not important since only literal bytes will be emitted. 149217651Speter */ 149317651Speter 149417651Speter } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0); 1495205471Sdelphij 1496205471Sdelphij /* If the WIN_INIT bytes after the end of the current data have never been 1497205471Sdelphij * written, then zero those bytes in order to avoid memory check reports of 1498205471Sdelphij * the use of uninitialized (or uninitialised as Julian writes) bytes by 1499205471Sdelphij * the longest match routines. Update the high water mark for the next 1500205471Sdelphij * time through here. WIN_INIT is set to MAX_MATCH since the longest match 1501205471Sdelphij * routines allow scanning to strstart + MAX_MATCH, ignoring lookahead. 1502205471Sdelphij */ 1503205471Sdelphij if (s->high_water < s->window_size) { 1504205471Sdelphij ulg curr = s->strstart + (ulg)(s->lookahead); 1505205471Sdelphij ulg init; 1506205471Sdelphij 1507205471Sdelphij if (s->high_water < curr) { 1508205471Sdelphij /* Previous high water mark below current data -- zero WIN_INIT 1509205471Sdelphij * bytes or up to end of window, whichever is less. 1510205471Sdelphij */ 1511205471Sdelphij init = s->window_size - curr; 1512205471Sdelphij if (init > WIN_INIT) 1513205471Sdelphij init = WIN_INIT; 1514205471Sdelphij zmemzero(s->window + curr, (unsigned)init); 1515205471Sdelphij s->high_water = curr + init; 1516205471Sdelphij } 1517205471Sdelphij else if (s->high_water < (ulg)curr + WIN_INIT) { 1518205471Sdelphij /* High water mark at or above current data, but below current data 1519205471Sdelphij * plus WIN_INIT -- zero out to current data plus WIN_INIT, or up 1520205471Sdelphij * to end of window, whichever is less. 1521205471Sdelphij */ 1522205471Sdelphij init = (ulg)curr + WIN_INIT - s->high_water; 1523205471Sdelphij if (init > s->window_size - s->high_water) 1524205471Sdelphij init = s->window_size - s->high_water; 1525205471Sdelphij zmemzero(s->window + s->high_water, (unsigned)init); 1526205471Sdelphij s->high_water += init; 1527205471Sdelphij } 1528205471Sdelphij } 1529237410Sdelphij 1530237410Sdelphij Assert((ulg)s->strstart <= s->window_size - MIN_LOOKAHEAD, 1531237410Sdelphij "not enough room for search"); 153217651Speter} 153317651Speter 153417651Speter/* =========================================================================== 153517651Speter * Flush the current block, with given end-of-file flag. 153617651Speter * IN assertion: strstart is set to the end of the current match. 153717651Speter */ 1538205471Sdelphij#define FLUSH_BLOCK_ONLY(s, last) { \ 153917651Speter _tr_flush_block(s, (s->block_start >= 0L ? \ 154017651Speter (charf *)&s->window[(unsigned)s->block_start] : \ 154117651Speter (charf *)Z_NULL), \ 1542131380Stjr (ulg)((long)s->strstart - s->block_start), \ 1543205471Sdelphij (last)); \ 154417651Speter s->block_start = s->strstart; \ 154517651Speter flush_pending(s->strm); \ 154617651Speter Tracev((stderr,"[FLUSH]")); \ 154717651Speter} 154817651Speter 154917651Speter/* Same but force premature exit if necessary. */ 1550205471Sdelphij#define FLUSH_BLOCK(s, last) { \ 1551205471Sdelphij FLUSH_BLOCK_ONLY(s, last); \ 1552205471Sdelphij if (s->strm->avail_out == 0) return (last) ? finish_started : need_more; \ 155317651Speter} 155417651Speter 155517651Speter/* =========================================================================== 155617651Speter * Copy without compression as much as possible from the input stream, return 155717651Speter * the current block state. 155817651Speter * This function does not insert new strings in the dictionary since 155917651Speter * uncompressible data is probably not useful. This function is used 156017651Speter * only for the level=0 compression option. 156133908Ssteve * NOTE: this function should be optimized to avoid extra copying from 156233908Ssteve * window to pending_buf. 156317651Speter */ 156417651Speterlocal block_state deflate_stored(s, flush) 156517651Speter deflate_state *s; 156617651Speter int flush; 156717651Speter{ 156833908Ssteve /* Stored blocks are limited to 0xffff bytes, pending_buf is limited 156933908Ssteve * to pending_buf_size, and each stored block has a 5 byte header: 157033908Ssteve */ 157133908Ssteve ulg max_block_size = 0xffff; 157233908Ssteve ulg max_start; 157333908Ssteve 157433908Ssteve if (max_block_size > s->pending_buf_size - 5) { 157533908Ssteve max_block_size = s->pending_buf_size - 5; 157633908Ssteve } 157733908Ssteve 157833908Ssteve /* Copy as much as possible from input to output: */ 157917651Speter for (;;) { 158017651Speter /* Fill the window as much as possible: */ 158117651Speter if (s->lookahead <= 1) { 158217651Speter 158317651Speter Assert(s->strstart < s->w_size+MAX_DIST(s) || 1584131380Stjr s->block_start >= (long)s->w_size, "slide too late"); 158517651Speter 158617651Speter fill_window(s); 158717651Speter if (s->lookahead == 0 && flush == Z_NO_FLUSH) return need_more; 158817651Speter 158917651Speter if (s->lookahead == 0) break; /* flush the current block */ 159017651Speter } 1591131380Stjr Assert(s->block_start >= 0L, "block gone"); 159217651Speter 1593131380Stjr s->strstart += s->lookahead; 1594131380Stjr s->lookahead = 0; 159517651Speter 1596131380Stjr /* Emit a stored block if pending_buf will be full: */ 1597131380Stjr max_start = s->block_start + max_block_size; 159833908Ssteve if (s->strstart == 0 || (ulg)s->strstart >= max_start) { 1599131380Stjr /* strstart == 0 is possible when wraparound on 16-bit machine */ 1600131380Stjr s->lookahead = (uInt)(s->strstart - max_start); 1601131380Stjr s->strstart = (uInt)max_start; 160233908Ssteve FLUSH_BLOCK(s, 0); 1603131380Stjr } 1604131380Stjr /* Flush if we may have to slide, otherwise block_start may become 160533908Ssteve * negative and the data will be gone: 160633908Ssteve */ 160717651Speter if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) { 160817651Speter FLUSH_BLOCK(s, 0); 1609131380Stjr } 161017651Speter } 1611237410Sdelphij s->insert = 0; 1612237410Sdelphij if (flush == Z_FINISH) { 1613237410Sdelphij FLUSH_BLOCK(s, 1); 1614237410Sdelphij return finish_done; 1615237410Sdelphij } 1616237410Sdelphij if ((long)s->strstart > s->block_start) 1617237410Sdelphij FLUSH_BLOCK(s, 0); 1618237410Sdelphij return block_done; 161917651Speter} 162017651Speter 162117651Speter/* =========================================================================== 162217651Speter * Compress as much as possible from the input stream, return the current 162317651Speter * block state. 162417651Speter * This function does not perform lazy evaluation of matches and inserts 162517651Speter * new strings in the dictionary only for unmatched strings or for short 162617651Speter * matches. It is used only for the fast compression options. 162717651Speter */ 162817651Speterlocal block_state deflate_fast(s, flush) 162917651Speter deflate_state *s; 163017651Speter int flush; 163117651Speter{ 1632205471Sdelphij IPos hash_head; /* head of the hash chain */ 163317651Speter int bflush; /* set if current block must be flushed */ 163417651Speter 163517651Speter for (;;) { 163617651Speter /* Make sure that we always have enough lookahead, except 163717651Speter * at the end of the input file. We need MAX_MATCH bytes 163817651Speter * for the next match, plus MIN_MATCH bytes to insert the 163917651Speter * string following the next match. 164017651Speter */ 164117651Speter if (s->lookahead < MIN_LOOKAHEAD) { 164217651Speter fill_window(s); 164317651Speter if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { 1644131380Stjr return need_more; 1645131380Stjr } 164617651Speter if (s->lookahead == 0) break; /* flush the current block */ 164717651Speter } 164817651Speter 164917651Speter /* Insert the string window[strstart .. strstart+2] in the 165017651Speter * dictionary, and set hash_head to the head of the hash chain: 165117651Speter */ 1652205471Sdelphij hash_head = NIL; 165317651Speter if (s->lookahead >= MIN_MATCH) { 165417651Speter INSERT_STRING(s, s->strstart, hash_head); 165517651Speter } 165617651Speter 165717651Speter /* Find the longest match, discarding those <= prev_length. 165817651Speter * At this point we have always match_length < MIN_MATCH 165917651Speter */ 166017651Speter if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) { 166117651Speter /* To simplify the code, we prevent matches with the string 166217651Speter * of window index 0 (in particular we have to avoid a match 166317651Speter * of the string with itself at the start of the input file). 166417651Speter */ 1665205471Sdelphij s->match_length = longest_match (s, hash_head); 1666205471Sdelphij /* longest_match() sets match_start */ 166717651Speter } 166817651Speter if (s->match_length >= MIN_MATCH) { 166917651Speter check_match(s, s->strstart, s->match_start, s->match_length); 167017651Speter 167133908Ssteve _tr_tally_dist(s, s->strstart - s->match_start, 167233908Ssteve s->match_length - MIN_MATCH, bflush); 167317651Speter 167417651Speter s->lookahead -= s->match_length; 167517651Speter 167617651Speter /* Insert new strings in the hash table only if the match length 167717651Speter * is not too large. This saves time but degrades compression. 167817651Speter */ 167933908Ssteve#ifndef FASTEST 168017651Speter if (s->match_length <= s->max_insert_length && 168117651Speter s->lookahead >= MIN_MATCH) { 1682131380Stjr s->match_length--; /* string at strstart already in table */ 168317651Speter do { 168417651Speter s->strstart++; 168517651Speter INSERT_STRING(s, s->strstart, hash_head); 168617651Speter /* strstart never exceeds WSIZE-MAX_MATCH, so there are 168717651Speter * always MIN_MATCH bytes ahead. 168817651Speter */ 168917651Speter } while (--s->match_length != 0); 1690131380Stjr s->strstart++; 169133908Ssteve } else 169233908Ssteve#endif 1693131380Stjr { 169417651Speter s->strstart += s->match_length; 169517651Speter s->match_length = 0; 169617651Speter s->ins_h = s->window[s->strstart]; 169717651Speter UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]); 169817651Speter#if MIN_MATCH != 3 169917651Speter Call UPDATE_HASH() MIN_MATCH-3 more times 170017651Speter#endif 170117651Speter /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not 170217651Speter * matter since it will be recomputed at next deflate call. 170317651Speter */ 170417651Speter } 170517651Speter } else { 170617651Speter /* No match, output a literal byte */ 170717651Speter Tracevv((stderr,"%c", s->window[s->strstart])); 170833908Ssteve _tr_tally_lit (s, s->window[s->strstart], bflush); 170917651Speter s->lookahead--; 1710131380Stjr s->strstart++; 171117651Speter } 171217651Speter if (bflush) FLUSH_BLOCK(s, 0); 171317651Speter } 1714237410Sdelphij s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1; 1715237410Sdelphij if (flush == Z_FINISH) { 1716237410Sdelphij FLUSH_BLOCK(s, 1); 1717237410Sdelphij return finish_done; 1718237410Sdelphij } 1719237410Sdelphij if (s->last_lit) 1720237410Sdelphij FLUSH_BLOCK(s, 0); 1721237410Sdelphij return block_done; 172217651Speter} 172317651Speter 1724131380Stjr#ifndef FASTEST 172517651Speter/* =========================================================================== 172617651Speter * Same as above, but achieves better compression. We use a lazy 172717651Speter * evaluation for matches: a match is finally adopted only if there is 172817651Speter * no better match at the next window position. 172917651Speter */ 173017651Speterlocal block_state deflate_slow(s, flush) 173117651Speter deflate_state *s; 173217651Speter int flush; 173317651Speter{ 1734205471Sdelphij IPos hash_head; /* head of hash chain */ 173517651Speter int bflush; /* set if current block must be flushed */ 173617651Speter 173717651Speter /* Process the input block. */ 173817651Speter for (;;) { 173917651Speter /* Make sure that we always have enough lookahead, except 174017651Speter * at the end of the input file. We need MAX_MATCH bytes 174117651Speter * for the next match, plus MIN_MATCH bytes to insert the 174217651Speter * string following the next match. 174317651Speter */ 174417651Speter if (s->lookahead < MIN_LOOKAHEAD) { 174517651Speter fill_window(s); 174617651Speter if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { 1747131380Stjr return need_more; 1748131380Stjr } 174917651Speter if (s->lookahead == 0) break; /* flush the current block */ 175017651Speter } 175117651Speter 175217651Speter /* Insert the string window[strstart .. strstart+2] in the 175317651Speter * dictionary, and set hash_head to the head of the hash chain: 175417651Speter */ 1755205471Sdelphij hash_head = NIL; 175617651Speter if (s->lookahead >= MIN_MATCH) { 175717651Speter INSERT_STRING(s, s->strstart, hash_head); 175817651Speter } 175917651Speter 176017651Speter /* Find the longest match, discarding those <= prev_length. 176117651Speter */ 176217651Speter s->prev_length = s->match_length, s->prev_match = s->match_start; 176317651Speter s->match_length = MIN_MATCH-1; 176417651Speter 176517651Speter if (hash_head != NIL && s->prev_length < s->max_lazy_match && 176617651Speter s->strstart - hash_head <= MAX_DIST(s)) { 176717651Speter /* To simplify the code, we prevent matches with the string 176817651Speter * of window index 0 (in particular we have to avoid a match 176917651Speter * of the string with itself at the start of the input file). 177017651Speter */ 1771205471Sdelphij s->match_length = longest_match (s, hash_head); 1772205471Sdelphij /* longest_match() sets match_start */ 177317651Speter 1774131380Stjr if (s->match_length <= 5 && (s->strategy == Z_FILTERED 1775131380Stjr#if TOO_FAR <= 32767 1776131380Stjr || (s->match_length == MIN_MATCH && 1777131380Stjr s->strstart - s->match_start > TOO_FAR) 1778131380Stjr#endif 1779131380Stjr )) { 178017651Speter 178117651Speter /* If prev_match is also MIN_MATCH, match_start is garbage 178217651Speter * but we will ignore the current match anyway. 178317651Speter */ 178417651Speter s->match_length = MIN_MATCH-1; 178517651Speter } 178617651Speter } 178717651Speter /* If there was a match at the previous step and the current 178817651Speter * match is not better, output the previous match: 178917651Speter */ 179017651Speter if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) { 179117651Speter uInt max_insert = s->strstart + s->lookahead - MIN_MATCH; 179217651Speter /* Do not insert strings in hash table beyond this. */ 179317651Speter 179417651Speter check_match(s, s->strstart-1, s->prev_match, s->prev_length); 179517651Speter 179633908Ssteve _tr_tally_dist(s, s->strstart -1 - s->prev_match, 1797131380Stjr s->prev_length - MIN_MATCH, bflush); 179817651Speter 179917651Speter /* Insert in hash table all strings up to the end of the match. 180017651Speter * strstart-1 and strstart are already inserted. If there is not 180117651Speter * enough lookahead, the last two strings are not inserted in 180217651Speter * the hash table. 180317651Speter */ 180417651Speter s->lookahead -= s->prev_length-1; 180517651Speter s->prev_length -= 2; 180617651Speter do { 180717651Speter if (++s->strstart <= max_insert) { 180817651Speter INSERT_STRING(s, s->strstart, hash_head); 180917651Speter } 181017651Speter } while (--s->prev_length != 0); 181117651Speter s->match_available = 0; 181217651Speter s->match_length = MIN_MATCH-1; 181317651Speter s->strstart++; 181417651Speter 181517651Speter if (bflush) FLUSH_BLOCK(s, 0); 181617651Speter 181717651Speter } else if (s->match_available) { 181817651Speter /* If there was no match at the previous position, output a 181917651Speter * single literal. If there was a match but the current match 182017651Speter * is longer, truncate the previous match to a single literal. 182117651Speter */ 182217651Speter Tracevv((stderr,"%c", s->window[s->strstart-1])); 1823131380Stjr _tr_tally_lit(s, s->window[s->strstart-1], bflush); 1824131380Stjr if (bflush) { 182517651Speter FLUSH_BLOCK_ONLY(s, 0); 182617651Speter } 182717651Speter s->strstart++; 182817651Speter s->lookahead--; 182917651Speter if (s->strm->avail_out == 0) return need_more; 183017651Speter } else { 183117651Speter /* There is no previous match to compare with, wait for 183217651Speter * the next step to decide. 183317651Speter */ 183417651Speter s->match_available = 1; 183517651Speter s->strstart++; 183617651Speter s->lookahead--; 183717651Speter } 183817651Speter } 183917651Speter Assert (flush != Z_NO_FLUSH, "no flush?"); 184017651Speter if (s->match_available) { 184117651Speter Tracevv((stderr,"%c", s->window[s->strstart-1])); 184233908Ssteve _tr_tally_lit(s, s->window[s->strstart-1], bflush); 184317651Speter s->match_available = 0; 184417651Speter } 1845237410Sdelphij s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1; 1846237410Sdelphij if (flush == Z_FINISH) { 1847237410Sdelphij FLUSH_BLOCK(s, 1); 1848237410Sdelphij return finish_done; 1849237410Sdelphij } 1850237410Sdelphij if (s->last_lit) 1851237410Sdelphij FLUSH_BLOCK(s, 0); 1852237410Sdelphij return block_done; 185317651Speter} 1854131380Stjr#endif /* FASTEST */ 1855157046Sdes 1856157046Sdes/* =========================================================================== 1857157046Sdes * For Z_RLE, simply look for runs of bytes, generate matches only of distance 1858157046Sdes * one. Do not maintain a hash table. (It will be regenerated if this run of 1859157046Sdes * deflate switches away from Z_RLE.) 1860157046Sdes */ 1861157046Sdeslocal block_state deflate_rle(s, flush) 1862157046Sdes deflate_state *s; 1863157046Sdes int flush; 1864157046Sdes{ 1865205471Sdelphij int bflush; /* set if current block must be flushed */ 1866205471Sdelphij uInt prev; /* byte at distance one to match */ 1867205471Sdelphij Bytef *scan, *strend; /* scan goes up to strend for length of run */ 1868157046Sdes 1869157046Sdes for (;;) { 1870157046Sdes /* Make sure that we always have enough lookahead, except 1871157046Sdes * at the end of the input file. We need MAX_MATCH bytes 1872237410Sdelphij * for the longest run, plus one for the unrolled loop. 1873157046Sdes */ 1874237410Sdelphij if (s->lookahead <= MAX_MATCH) { 1875157046Sdes fill_window(s); 1876237410Sdelphij if (s->lookahead <= MAX_MATCH && flush == Z_NO_FLUSH) { 1877157046Sdes return need_more; 1878157046Sdes } 1879157046Sdes if (s->lookahead == 0) break; /* flush the current block */ 1880157046Sdes } 1881157046Sdes 1882157046Sdes /* See how many times the previous byte repeats */ 1883205471Sdelphij s->match_length = 0; 1884205471Sdelphij if (s->lookahead >= MIN_MATCH && s->strstart > 0) { 1885157046Sdes scan = s->window + s->strstart - 1; 1886205471Sdelphij prev = *scan; 1887205471Sdelphij if (prev == *++scan && prev == *++scan && prev == *++scan) { 1888205471Sdelphij strend = s->window + s->strstart + MAX_MATCH; 1889205471Sdelphij do { 1890205471Sdelphij } while (prev == *++scan && prev == *++scan && 1891205471Sdelphij prev == *++scan && prev == *++scan && 1892205471Sdelphij prev == *++scan && prev == *++scan && 1893205471Sdelphij prev == *++scan && prev == *++scan && 1894205471Sdelphij scan < strend); 1895205471Sdelphij s->match_length = MAX_MATCH - (int)(strend - scan); 1896205471Sdelphij if (s->match_length > s->lookahead) 1897205471Sdelphij s->match_length = s->lookahead; 1898205471Sdelphij } 1899237410Sdelphij Assert(scan <= s->window+(uInt)(s->window_size-1), "wild scan"); 1900157046Sdes } 1901157046Sdes 1902157046Sdes /* Emit match if have run of MIN_MATCH or longer, else emit literal */ 1903205471Sdelphij if (s->match_length >= MIN_MATCH) { 1904205471Sdelphij check_match(s, s->strstart, s->strstart - 1, s->match_length); 1905205471Sdelphij 1906205471Sdelphij _tr_tally_dist(s, 1, s->match_length - MIN_MATCH, bflush); 1907205471Sdelphij 1908205471Sdelphij s->lookahead -= s->match_length; 1909205471Sdelphij s->strstart += s->match_length; 1910205471Sdelphij s->match_length = 0; 1911157046Sdes } else { 1912157046Sdes /* No match, output a literal byte */ 1913157046Sdes Tracevv((stderr,"%c", s->window[s->strstart])); 1914157046Sdes _tr_tally_lit (s, s->window[s->strstart], bflush); 1915157046Sdes s->lookahead--; 1916157046Sdes s->strstart++; 1917157046Sdes } 1918157046Sdes if (bflush) FLUSH_BLOCK(s, 0); 1919157046Sdes } 1920237410Sdelphij s->insert = 0; 1921237410Sdelphij if (flush == Z_FINISH) { 1922237410Sdelphij FLUSH_BLOCK(s, 1); 1923237410Sdelphij return finish_done; 1924237410Sdelphij } 1925237410Sdelphij if (s->last_lit) 1926237410Sdelphij FLUSH_BLOCK(s, 0); 1927237410Sdelphij return block_done; 1928157046Sdes} 1929205471Sdelphij 1930205471Sdelphij/* =========================================================================== 1931205471Sdelphij * For Z_HUFFMAN_ONLY, do not look for matches. Do not maintain a hash table. 1932205471Sdelphij * (It will be regenerated if this run of deflate switches away from Huffman.) 1933205471Sdelphij */ 1934205471Sdelphijlocal block_state deflate_huff(s, flush) 1935205471Sdelphij deflate_state *s; 1936205471Sdelphij int flush; 1937205471Sdelphij{ 1938205471Sdelphij int bflush; /* set if current block must be flushed */ 1939205471Sdelphij 1940205471Sdelphij for (;;) { 1941205471Sdelphij /* Make sure that we have a literal to write. */ 1942205471Sdelphij if (s->lookahead == 0) { 1943205471Sdelphij fill_window(s); 1944205471Sdelphij if (s->lookahead == 0) { 1945205471Sdelphij if (flush == Z_NO_FLUSH) 1946205471Sdelphij return need_more; 1947205471Sdelphij break; /* flush the current block */ 1948205471Sdelphij } 1949205471Sdelphij } 1950205471Sdelphij 1951205471Sdelphij /* Output a literal byte */ 1952205471Sdelphij s->match_length = 0; 1953205471Sdelphij Tracevv((stderr,"%c", s->window[s->strstart])); 1954205471Sdelphij _tr_tally_lit (s, s->window[s->strstart], bflush); 1955205471Sdelphij s->lookahead--; 1956205471Sdelphij s->strstart++; 1957205471Sdelphij if (bflush) FLUSH_BLOCK(s, 0); 1958205471Sdelphij } 1959237410Sdelphij s->insert = 0; 1960237410Sdelphij if (flush == Z_FINISH) { 1961237410Sdelphij FLUSH_BLOCK(s, 1); 1962237410Sdelphij return finish_done; 1963237410Sdelphij } 1964237410Sdelphij if (s->last_lit) 1965237410Sdelphij FLUSH_BLOCK(s, 0); 1966237410Sdelphij return block_done; 1967205471Sdelphij} 1968