117651Speter/* deflate.c -- compress data using the deflation algorithm 2313796Sdelphij * Copyright (C) 1995-2017 Jean-loup Gailly and Mark Adler 3131377Stjr * 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 * 3933904Ssteve * Deutsch, L.P.,"DEFLATE Compressed Data Format Specification". 40230837Sdelphij * 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 5033904Ssteve/* @(#) $Id$ */ 5117651Speter 5217651Speter#include "deflate.h" 5317651Speter 5433904Ssteveconst char deflate_copyright[] = 55313796Sdelphij " deflate 1.2.11 Copyright 1995-2017 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 76313796Sdelphijlocal int deflateStateCheck OF((z_streamp strm)); 77313796Sdelphijlocal void slide_hash OF((deflate_state *s)); 7817651Speterlocal void fill_window OF((deflate_state *s)); 7917651Speterlocal block_state deflate_stored OF((deflate_state *s, int flush)); 8017651Speterlocal block_state deflate_fast OF((deflate_state *s, int flush)); 81131377Stjr#ifndef FASTEST 8217651Speterlocal block_state deflate_slow OF((deflate_state *s, int flush)); 83131377Stjr#endif 84205194Sdelphijlocal block_state deflate_rle OF((deflate_state *s, int flush)); 85205194Sdelphijlocal block_state deflate_huff OF((deflate_state *s, int flush)); 8617651Speterlocal void lm_init OF((deflate_state *s)); 8717651Speterlocal void putShortMSB OF((deflate_state *s, uInt b)); 8817651Speterlocal void flush_pending OF((z_streamp strm)); 89313796Sdelphijlocal unsigned read_buf OF((z_streamp strm, Bytef *buf, unsigned size)); 9017651Speter#ifdef ASMV 91313796Sdelphij# pragma message("Assembler code may have bugs -- use at your own risk") 9217651Speter void match_init OF((void)); /* asm code initialization */ 9333904Ssteve uInt longest_match OF((deflate_state *s, IPos cur_match)); 9433904Ssteve#else 9533904Sstevelocal uInt longest_match OF((deflate_state *s, IPos cur_match)); 9617651Speter#endif 9717651Speter 98313796Sdelphij#ifdef ZLIB_DEBUG 9917651Speterlocal void check_match OF((deflate_state *s, IPos start, IPos match, 10017651Speter int length)); 10117651Speter#endif 10217651Speter 10317651Speter/* =========================================================================== 10417651Speter * Local data 10517651Speter */ 10617651Speter 10717651Speter#define NIL 0 10817651Speter/* Tail of hash chains */ 10917651Speter 11017651Speter#ifndef TOO_FAR 11117651Speter# define TOO_FAR 4096 11217651Speter#endif 11317651Speter/* Matches of length 3 are discarded if their distance exceeds TOO_FAR */ 11417651Speter 11517651Speter/* Values for max_lazy_match, good_match and max_chain_length, depending on 11617651Speter * the desired pack level (0..9). The values given below have been tuned to 11717651Speter * exclude worst case performance for pathological files. Better values may be 11817651Speter * found for specific files. 11917651Speter */ 12017651Spetertypedef struct config_s { 12117651Speter ush good_length; /* reduce lazy search above this match length */ 12217651Speter ush max_lazy; /* do not perform lazy search above this match length */ 12317651Speter ush nice_length; /* quit search above this match length */ 12417651Speter ush max_chain; 12517651Speter compress_func func; 12617651Speter} config; 12717651Speter 128131377Stjr#ifdef FASTEST 129131377Stjrlocal const config configuration_table[2] = { 130131377Stjr/* good lazy nice chain */ 131131377Stjr/* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */ 132131377Stjr/* 1 */ {4, 4, 8, 4, deflate_fast}}; /* max speed, no lazy matches */ 133131377Stjr#else 13433904Sstevelocal const config configuration_table[10] = { 13517651Speter/* good lazy nice chain */ 13617651Speter/* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */ 137131377Stjr/* 1 */ {4, 4, 8, 4, deflate_fast}, /* max speed, no lazy matches */ 13817651Speter/* 2 */ {4, 5, 16, 8, deflate_fast}, 13917651Speter/* 3 */ {4, 6, 32, 32, deflate_fast}, 14017651Speter 14117651Speter/* 4 */ {4, 4, 16, 16, deflate_slow}, /* lazy matches */ 14217651Speter/* 5 */ {8, 16, 32, 32, deflate_slow}, 14317651Speter/* 6 */ {8, 16, 128, 128, deflate_slow}, 14417651Speter/* 7 */ {8, 32, 128, 256, deflate_slow}, 14517651Speter/* 8 */ {32, 128, 258, 1024, deflate_slow}, 146131377Stjr/* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* max compression */ 147131377Stjr#endif 14817651Speter 14917651Speter/* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4 15017651Speter * For deflate_fast() (levels <= 3) good is ignored and lazy has a different 15117651Speter * meaning. 15217651Speter */ 15317651Speter 154230837Sdelphij/* rank Z_BLOCK between Z_NO_FLUSH and Z_PARTIAL_FLUSH */ 155313796Sdelphij#define RANK(f) (((f) * 2) - ((f) > 4 ? 9 : 0)) 156230837Sdelphij 15717651Speter/* =========================================================================== 15817651Speter * Update a hash value with the given input byte 159313796Sdelphij * IN assertion: all calls to UPDATE_HASH are made with consecutive input 160313796Sdelphij * characters, so that a running hash key can be computed from the previous 161313796Sdelphij * key instead of complete recalculation each time. 16217651Speter */ 16317651Speter#define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask) 16417651Speter 16517651Speter 16617651Speter/* =========================================================================== 16717651Speter * Insert string str in the dictionary and set match_head to the previous head 16817651Speter * of the hash chain (the most recent string with same hash key). Return 16917651Speter * the previous length of the hash chain. 17033904Ssteve * If this file is compiled with -DFASTEST, the compression level is forced 17133904Ssteve * to 1, and no hash chains are maintained. 172313796Sdelphij * IN assertion: all calls to INSERT_STRING are made with consecutive input 173313796Sdelphij * characters and the first MIN_MATCH bytes of str are valid (except for 174313796Sdelphij * the last MIN_MATCH-1 bytes of the input file). 17517651Speter */ 17633904Ssteve#ifdef FASTEST 17717651Speter#define INSERT_STRING(s, str, match_head) \ 17817651Speter (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \ 17933904Ssteve match_head = s->head[s->ins_h], \ 18033904Ssteve s->head[s->ins_h] = (Pos)(str)) 18133904Ssteve#else 18233904Ssteve#define INSERT_STRING(s, str, match_head) \ 18333904Ssteve (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \ 184131377Stjr match_head = s->prev[(str) & s->w_mask] = s->head[s->ins_h], \ 18517651Speter s->head[s->ins_h] = (Pos)(str)) 18633904Ssteve#endif 18717651Speter 18817651Speter/* =========================================================================== 18917651Speter * Initialize the hash table (avoiding 64K overflow for 16 bit systems). 19017651Speter * prev[] will be initialized on the fly. 19117651Speter */ 19217651Speter#define CLEAR_HASH(s) \ 19317651Speter s->head[s->hash_size-1] = NIL; \ 19433904Ssteve zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head)); 19517651Speter 196313796Sdelphij/* =========================================================================== 197313796Sdelphij * Slide the hash table when sliding the window down (could be avoided with 32 198313796Sdelphij * bit values at the expense of memory usage). We slide even when level == 0 to 199313796Sdelphij * keep the hash table consistent if we switch back to level > 0 later. 200313796Sdelphij */ 201313796Sdelphijlocal void slide_hash(s) 202313796Sdelphij deflate_state *s; 203313796Sdelphij{ 204313796Sdelphij unsigned n, m; 205313796Sdelphij Posf *p; 206313796Sdelphij uInt wsize = s->w_size; 207313796Sdelphij 208313796Sdelphij n = s->hash_size; 209313796Sdelphij p = &s->head[n]; 210313796Sdelphij do { 211313796Sdelphij m = *--p; 212313796Sdelphij *p = (Pos)(m >= wsize ? m - wsize : NIL); 213313796Sdelphij } while (--n); 214313796Sdelphij n = wsize; 215313796Sdelphij#ifndef FASTEST 216313796Sdelphij p = &s->prev[n]; 217313796Sdelphij do { 218313796Sdelphij m = *--p; 219313796Sdelphij *p = (Pos)(m >= wsize ? m - wsize : NIL); 220313796Sdelphij /* If n is not on any hash chain, prev[n] is garbage but 221313796Sdelphij * its value will never be used. 222313796Sdelphij */ 223313796Sdelphij } while (--n); 224313796Sdelphij#endif 225313796Sdelphij} 226313796Sdelphij 22717651Speter/* ========================================================================= */ 22833904Ssteveint ZEXPORT deflateInit_(strm, level, version, stream_size) 22917651Speter z_streamp strm; 23017651Speter int level; 23117651Speter const char *version; 23217651Speter int stream_size; 23317651Speter{ 23417651Speter return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL, 235131377Stjr Z_DEFAULT_STRATEGY, version, stream_size); 23617651Speter /* To do: ignore strm->next_in if we use it as window */ 23717651Speter} 23817651Speter 23917651Speter/* ========================================================================= */ 24033904Ssteveint ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy, 241131377Stjr version, stream_size) 24217651Speter z_streamp strm; 24317651Speter int level; 24417651Speter int method; 24517651Speter int windowBits; 24617651Speter int memLevel; 24717651Speter int strategy; 24817651Speter const char *version; 24917651Speter int stream_size; 25017651Speter{ 25117651Speter deflate_state *s; 252131377Stjr int wrap = 1; 253131377Stjr static const char my_version[] = ZLIB_VERSION; 25417651Speter 25517651Speter ushf *overlay; 25617651Speter /* We overlay pending_buf and d_buf+l_buf. This works since the average 25717651Speter * output size for (length,distance) codes is <= 24 bits. 25817651Speter */ 25917651Speter 26033904Ssteve if (version == Z_NULL || version[0] != my_version[0] || 26117651Speter stream_size != sizeof(z_stream)) { 262131377Stjr return Z_VERSION_ERROR; 26317651Speter } 26417651Speter if (strm == Z_NULL) return Z_STREAM_ERROR; 26517651Speter 26617651Speter strm->msg = Z_NULL; 267131377Stjr if (strm->zalloc == (alloc_func)0) { 268230837Sdelphij#ifdef Z_SOLO 269230837Sdelphij return Z_STREAM_ERROR; 270230837Sdelphij#else 271131377Stjr strm->zalloc = zcalloc; 272131377Stjr strm->opaque = (voidpf)0; 273230837Sdelphij#endif 27417651Speter } 275230837Sdelphij if (strm->zfree == (free_func)0) 276230837Sdelphij#ifdef Z_SOLO 277230837Sdelphij return Z_STREAM_ERROR; 278230837Sdelphij#else 279230837Sdelphij strm->zfree = zcfree; 280230837Sdelphij#endif 28117651Speter 282131377Stjr#ifdef FASTEST 283131377Stjr if (level != 0) level = 1; 284131377Stjr#else 28517651Speter if (level == Z_DEFAULT_COMPRESSION) level = 6; 28633904Ssteve#endif 28717651Speter 288131377Stjr if (windowBits < 0) { /* suppress zlib wrapper */ 289131377Stjr wrap = 0; 29017651Speter windowBits = -windowBits; 29117651Speter } 292131377Stjr#ifdef GZIP 293131377Stjr else if (windowBits > 15) { 294131377Stjr wrap = 2; /* write gzip wrapper instead */ 295131377Stjr windowBits -= 16; 296131377Stjr } 297131377Stjr#endif 29817651Speter if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED || 299131377Stjr windowBits < 8 || windowBits > 15 || level < 0 || level > 9 || 300313796Sdelphij strategy < 0 || strategy > Z_FIXED || (windowBits == 8 && wrap != 1)) { 30117651Speter return Z_STREAM_ERROR; 30217651Speter } 303131377Stjr if (windowBits == 8) windowBits = 9; /* until 256-byte window bug fixed */ 30417651Speter s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state)); 30517651Speter if (s == Z_NULL) return Z_MEM_ERROR; 30617651Speter strm->state = (struct internal_state FAR *)s; 30717651Speter s->strm = strm; 308313796Sdelphij s->status = INIT_STATE; /* to pass state test in deflateReset() */ 30917651Speter 310131377Stjr s->wrap = wrap; 311157043Sdes s->gzhead = Z_NULL; 312313796Sdelphij s->w_bits = (uInt)windowBits; 31317651Speter s->w_size = 1 << s->w_bits; 31417651Speter s->w_mask = s->w_size - 1; 31517651Speter 316313796Sdelphij s->hash_bits = (uInt)memLevel + 7; 31717651Speter s->hash_size = 1 << s->hash_bits; 31817651Speter s->hash_mask = s->hash_size - 1; 31917651Speter s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH); 32017651Speter 32117651Speter s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte)); 32217651Speter s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos)); 32317651Speter s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos)); 32417651Speter 325205194Sdelphij s->high_water = 0; /* nothing written to s->window yet */ 326205194Sdelphij 32717651Speter s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */ 32817651Speter 32917651Speter overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2); 33017651Speter s->pending_buf = (uchf *) overlay; 33133904Ssteve s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L); 33217651Speter 33317651Speter if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL || 33417651Speter s->pending_buf == Z_NULL) { 335131377Stjr s->status = FINISH_STATE; 336250224Sdelphij strm->msg = ERR_MSG(Z_MEM_ERROR); 33717651Speter deflateEnd (strm); 33817651Speter return Z_MEM_ERROR; 33917651Speter } 34017651Speter s->d_buf = overlay + s->lit_bufsize/sizeof(ush); 34117651Speter s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize; 34217651Speter 34317651Speter s->level = level; 34417651Speter s->strategy = strategy; 34517651Speter s->method = (Byte)method; 34617651Speter 34717651Speter return deflateReset(strm); 34817651Speter} 34917651Speter 350313796Sdelphij/* ========================================================================= 351313796Sdelphij * Check for a valid deflate stream state. Return 0 if ok, 1 if not. 352313796Sdelphij */ 353313796Sdelphijlocal int deflateStateCheck (strm) 354313796Sdelphij z_streamp strm; 355313796Sdelphij{ 356313796Sdelphij deflate_state *s; 357313796Sdelphij if (strm == Z_NULL || 358313796Sdelphij strm->zalloc == (alloc_func)0 || strm->zfree == (free_func)0) 359313796Sdelphij return 1; 360313796Sdelphij s = strm->state; 361313796Sdelphij if (s == Z_NULL || s->strm != strm || (s->status != INIT_STATE && 362313796Sdelphij#ifdef GZIP 363313796Sdelphij s->status != GZIP_STATE && 364313796Sdelphij#endif 365313796Sdelphij s->status != EXTRA_STATE && 366313796Sdelphij s->status != NAME_STATE && 367313796Sdelphij s->status != COMMENT_STATE && 368313796Sdelphij s->status != HCRC_STATE && 369313796Sdelphij s->status != BUSY_STATE && 370313796Sdelphij s->status != FINISH_STATE)) 371313796Sdelphij return 1; 372313796Sdelphij return 0; 373313796Sdelphij} 374313796Sdelphij 37517651Speter/* ========================================================================= */ 37633904Ssteveint ZEXPORT deflateSetDictionary (strm, dictionary, dictLength) 37717651Speter z_streamp strm; 37817651Speter const Bytef *dictionary; 37917651Speter uInt dictLength; 38017651Speter{ 38117651Speter deflate_state *s; 382230837Sdelphij uInt str, n; 383230837Sdelphij int wrap; 384230837Sdelphij unsigned avail; 385250224Sdelphij z_const unsigned char *next; 38617651Speter 387313796Sdelphij if (deflateStateCheck(strm) || dictionary == Z_NULL) 388131377Stjr return Z_STREAM_ERROR; 389230837Sdelphij s = strm->state; 390230837Sdelphij wrap = s->wrap; 391230837Sdelphij if (wrap == 2 || (wrap == 1 && s->status != INIT_STATE) || s->lookahead) 392230837Sdelphij return Z_STREAM_ERROR; 39317651Speter 394230837Sdelphij /* when using zlib wrappers, compute Adler-32 for provided dictionary */ 395230837Sdelphij if (wrap == 1) 396131377Stjr strm->adler = adler32(strm->adler, dictionary, dictLength); 397230837Sdelphij s->wrap = 0; /* avoid computing Adler-32 in read_buf */ 39817651Speter 399230837Sdelphij /* if dictionary would fill window, just replace the history */ 400230837Sdelphij if (dictLength >= s->w_size) { 401230837Sdelphij if (wrap == 0) { /* already empty otherwise */ 402230837Sdelphij CLEAR_HASH(s); 403230837Sdelphij s->strstart = 0; 404230837Sdelphij s->block_start = 0L; 405230837Sdelphij s->insert = 0; 406230837Sdelphij } 407230837Sdelphij dictionary += dictLength - s->w_size; /* use the tail */ 408230837Sdelphij dictLength = s->w_size; 40917651Speter } 41017651Speter 411230837Sdelphij /* insert dictionary into window and hash */ 412230837Sdelphij avail = strm->avail_in; 413230837Sdelphij next = strm->next_in; 414230837Sdelphij strm->avail_in = dictLength; 415250224Sdelphij strm->next_in = (z_const Bytef *)dictionary; 416230837Sdelphij fill_window(s); 417230837Sdelphij while (s->lookahead >= MIN_MATCH) { 418230837Sdelphij str = s->strstart; 419230837Sdelphij n = s->lookahead - (MIN_MATCH-1); 420230837Sdelphij do { 421230837Sdelphij UPDATE_HASH(s, s->ins_h, s->window[str + MIN_MATCH-1]); 422230837Sdelphij#ifndef FASTEST 423230837Sdelphij s->prev[str & s->w_mask] = s->head[s->ins_h]; 424230837Sdelphij#endif 425230837Sdelphij s->head[s->ins_h] = (Pos)str; 426230837Sdelphij str++; 427230837Sdelphij } while (--n); 428230837Sdelphij s->strstart = str; 429230837Sdelphij s->lookahead = MIN_MATCH-1; 430230837Sdelphij fill_window(s); 43117651Speter } 432230837Sdelphij s->strstart += s->lookahead; 433230837Sdelphij s->block_start = (long)s->strstart; 434230837Sdelphij s->insert = s->lookahead; 435230837Sdelphij s->lookahead = 0; 436230837Sdelphij s->match_length = s->prev_length = MIN_MATCH-1; 437230837Sdelphij s->match_available = 0; 438230837Sdelphij strm->next_in = next; 439230837Sdelphij strm->avail_in = avail; 440230837Sdelphij s->wrap = wrap; 44117651Speter return Z_OK; 44217651Speter} 44317651Speter 44417651Speter/* ========================================================================= */ 445313796Sdelphijint ZEXPORT deflateGetDictionary (strm, dictionary, dictLength) 446313796Sdelphij z_streamp strm; 447313796Sdelphij Bytef *dictionary; 448313796Sdelphij uInt *dictLength; 449313796Sdelphij{ 450313796Sdelphij deflate_state *s; 451313796Sdelphij uInt len; 452313796Sdelphij 453313796Sdelphij if (deflateStateCheck(strm)) 454313796Sdelphij return Z_STREAM_ERROR; 455313796Sdelphij s = strm->state; 456313796Sdelphij len = s->strstart + s->lookahead; 457313796Sdelphij if (len > s->w_size) 458313796Sdelphij len = s->w_size; 459313796Sdelphij if (dictionary != Z_NULL && len) 460313796Sdelphij zmemcpy(dictionary, s->window + s->strstart + s->lookahead - len, len); 461313796Sdelphij if (dictLength != Z_NULL) 462313796Sdelphij *dictLength = len; 463313796Sdelphij return Z_OK; 464313796Sdelphij} 465313796Sdelphij 466313796Sdelphij/* ========================================================================= */ 467230837Sdelphijint ZEXPORT deflateResetKeep (strm) 46817651Speter z_streamp strm; 46917651Speter{ 47017651Speter deflate_state *s; 471131377Stjr 472313796Sdelphij if (deflateStateCheck(strm)) { 473131377Stjr return Z_STREAM_ERROR; 474131377Stjr } 47517651Speter 47617651Speter strm->total_in = strm->total_out = 0; 47717651Speter strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */ 47817651Speter strm->data_type = Z_UNKNOWN; 47917651Speter 48017651Speter s = (deflate_state *)strm->state; 48117651Speter s->pending = 0; 48217651Speter s->pending_out = s->pending_buf; 48317651Speter 484131377Stjr if (s->wrap < 0) { 485131377Stjr s->wrap = -s->wrap; /* was made negative by deflate(..., Z_FINISH); */ 48617651Speter } 487313796Sdelphij s->status = 488313796Sdelphij#ifdef GZIP 489313796Sdelphij s->wrap == 2 ? GZIP_STATE : 490313796Sdelphij#endif 491313796Sdelphij s->wrap ? INIT_STATE : BUSY_STATE; 492131377Stjr strm->adler = 493131377Stjr#ifdef GZIP 494131377Stjr s->wrap == 2 ? crc32(0L, Z_NULL, 0) : 495131377Stjr#endif 496131377Stjr adler32(0L, Z_NULL, 0); 497323565Smarius s->last_flush = -2; 49817651Speter 49917651Speter _tr_init(s); 50017651Speter 50117651Speter return Z_OK; 50217651Speter} 50317651Speter 50417651Speter/* ========================================================================= */ 505230837Sdelphijint ZEXPORT deflateReset (strm) 506230837Sdelphij z_streamp strm; 507230837Sdelphij{ 508230837Sdelphij int ret; 509230837Sdelphij 510230837Sdelphij ret = deflateResetKeep(strm); 511230837Sdelphij if (ret == Z_OK) 512230837Sdelphij lm_init(strm->state); 513230837Sdelphij return ret; 514230837Sdelphij} 515230837Sdelphij 516230837Sdelphij/* ========================================================================= */ 517157043Sdesint ZEXPORT deflateSetHeader (strm, head) 518157043Sdes z_streamp strm; 519157043Sdes gz_headerp head; 520157043Sdes{ 521313796Sdelphij if (deflateStateCheck(strm) || strm->state->wrap != 2) 522313796Sdelphij return Z_STREAM_ERROR; 523157043Sdes strm->state->gzhead = head; 524157043Sdes return Z_OK; 525157043Sdes} 526157043Sdes 527157043Sdes/* ========================================================================= */ 528230837Sdelphijint ZEXPORT deflatePending (strm, pending, bits) 529230837Sdelphij unsigned *pending; 530230837Sdelphij int *bits; 531230837Sdelphij z_streamp strm; 532230837Sdelphij{ 533313796Sdelphij if (deflateStateCheck(strm)) return Z_STREAM_ERROR; 534230837Sdelphij if (pending != Z_NULL) 535230837Sdelphij *pending = strm->state->pending; 536230837Sdelphij if (bits != Z_NULL) 537230837Sdelphij *bits = strm->state->bi_valid; 538230837Sdelphij return Z_OK; 539230837Sdelphij} 540230837Sdelphij 541230837Sdelphij/* ========================================================================= */ 542131377Stjrint ZEXPORT deflatePrime (strm, bits, value) 543131377Stjr z_streamp strm; 544131377Stjr int bits; 545131377Stjr int value; 546131377Stjr{ 547230837Sdelphij deflate_state *s; 548230837Sdelphij int put; 549230837Sdelphij 550313796Sdelphij if (deflateStateCheck(strm)) return Z_STREAM_ERROR; 551230837Sdelphij s = strm->state; 552230837Sdelphij if ((Bytef *)(s->d_buf) < s->pending_out + ((Buf_size + 7) >> 3)) 553230837Sdelphij return Z_BUF_ERROR; 554230837Sdelphij do { 555230837Sdelphij put = Buf_size - s->bi_valid; 556230837Sdelphij if (put > bits) 557230837Sdelphij put = bits; 558230837Sdelphij s->bi_buf |= (ush)((value & ((1 << put) - 1)) << s->bi_valid); 559230837Sdelphij s->bi_valid += put; 560230837Sdelphij _tr_flush_bits(s); 561230837Sdelphij value >>= put; 562230837Sdelphij bits -= put; 563230837Sdelphij } while (bits); 564131377Stjr return Z_OK; 565131377Stjr} 566131377Stjr 567131377Stjr/* ========================================================================= */ 56833904Ssteveint ZEXPORT deflateParams(strm, level, strategy) 56917651Speter z_streamp strm; 57017651Speter int level; 57117651Speter int strategy; 57217651Speter{ 57317651Speter deflate_state *s; 57417651Speter compress_func func; 57517651Speter 576313796Sdelphij if (deflateStateCheck(strm)) return Z_STREAM_ERROR; 57717651Speter s = strm->state; 57817651Speter 579131377Stjr#ifdef FASTEST 580131377Stjr if (level != 0) level = 1; 581131377Stjr#else 582131377Stjr if (level == Z_DEFAULT_COMPRESSION) level = 6; 583131377Stjr#endif 584157043Sdes if (level < 0 || level > 9 || strategy < 0 || strategy > Z_FIXED) { 585131377Stjr return Z_STREAM_ERROR; 58617651Speter } 58717651Speter func = configuration_table[s->level].func; 58817651Speter 589205194Sdelphij if ((strategy != s->strategy || func != configuration_table[level].func) && 590323565Smarius s->last_flush != -2) { 591131377Stjr /* Flush the last buffer: */ 592313796Sdelphij int err = deflate(strm, Z_BLOCK); 593313796Sdelphij if (err == Z_STREAM_ERROR) 594313796Sdelphij return err; 595323565Smarius if (strm->avail_in || (s->strstart - s->block_start) + s->lookahead) 596313796Sdelphij return Z_BUF_ERROR; 59717651Speter } 59817651Speter if (s->level != level) { 599313796Sdelphij if (s->level == 0 && s->matches != 0) { 600313796Sdelphij if (s->matches == 1) 601313796Sdelphij slide_hash(s); 602313796Sdelphij else 603313796Sdelphij CLEAR_HASH(s); 604313796Sdelphij s->matches = 0; 605313796Sdelphij } 606131377Stjr s->level = level; 607131377Stjr s->max_lazy_match = configuration_table[level].max_lazy; 608131377Stjr s->good_match = configuration_table[level].good_length; 609131377Stjr s->nice_match = configuration_table[level].nice_length; 610131377Stjr s->max_chain_length = configuration_table[level].max_chain; 61117651Speter } 61217651Speter s->strategy = strategy; 613313796Sdelphij return Z_OK; 61417651Speter} 61517651Speter 616157043Sdes/* ========================================================================= */ 617157043Sdesint ZEXPORT deflateTune(strm, good_length, max_lazy, nice_length, max_chain) 618157043Sdes z_streamp strm; 619157043Sdes int good_length; 620157043Sdes int max_lazy; 621157043Sdes int nice_length; 622157043Sdes int max_chain; 623157043Sdes{ 624157043Sdes deflate_state *s; 625157043Sdes 626313796Sdelphij if (deflateStateCheck(strm)) return Z_STREAM_ERROR; 627157043Sdes s = strm->state; 628313796Sdelphij s->good_match = (uInt)good_length; 629313796Sdelphij s->max_lazy_match = (uInt)max_lazy; 630157043Sdes s->nice_match = nice_length; 631313796Sdelphij s->max_chain_length = (uInt)max_chain; 632157043Sdes return Z_OK; 633157043Sdes} 634157043Sdes 63517651Speter/* ========================================================================= 636131377Stjr * For the default windowBits of 15 and memLevel of 8, this function returns 637131377Stjr * a close to exact, as well as small, upper bound on the compressed size. 638131377Stjr * They are coded as constants here for a reason--if the #define's are 639131377Stjr * changed, then this function needs to be changed as well. The return 640131377Stjr * value for 15 and 8 only works for those exact settings. 641131377Stjr * 642131377Stjr * For any setting other than those defaults for windowBits and memLevel, 643131377Stjr * the value returned is a conservative worst case for the maximum expansion 644131377Stjr * resulting from using fixed blocks instead of stored blocks, which deflate 645131377Stjr * can emit on compressed data for some combinations of the parameters. 646131377Stjr * 647205194Sdelphij * This function could be more sophisticated to provide closer upper bounds for 648205194Sdelphij * every combination of windowBits and memLevel. But even the conservative 649205194Sdelphij * upper bound of about 14% expansion does not seem onerous for output buffer 650205194Sdelphij * allocation. 651131377Stjr */ 652131377StjruLong ZEXPORT deflateBound(strm, sourceLen) 653131377Stjr z_streamp strm; 654131377Stjr uLong sourceLen; 655131377Stjr{ 656131377Stjr deflate_state *s; 657205194Sdelphij uLong complen, wraplen; 658131377Stjr 659205194Sdelphij /* conservative upper bound for compressed data */ 660205194Sdelphij complen = sourceLen + 661205194Sdelphij ((sourceLen + 7) >> 3) + ((sourceLen + 63) >> 6) + 5; 662131377Stjr 663205194Sdelphij /* if can't get parameters, return conservative bound plus zlib wrapper */ 664313796Sdelphij if (deflateStateCheck(strm)) 665205194Sdelphij return complen + 6; 666131377Stjr 667205194Sdelphij /* compute wrapper length */ 668205194Sdelphij s = strm->state; 669205194Sdelphij switch (s->wrap) { 670205194Sdelphij case 0: /* raw deflate */ 671205194Sdelphij wraplen = 0; 672205194Sdelphij break; 673205194Sdelphij case 1: /* zlib wrapper */ 674205194Sdelphij wraplen = 6 + (s->strstart ? 4 : 0); 675205194Sdelphij break; 676313796Sdelphij#ifdef GZIP 677205194Sdelphij case 2: /* gzip wrapper */ 678205194Sdelphij wraplen = 18; 679205194Sdelphij if (s->gzhead != Z_NULL) { /* user-supplied gzip header */ 680313796Sdelphij Bytef *str; 681205194Sdelphij if (s->gzhead->extra != Z_NULL) 682205194Sdelphij wraplen += 2 + s->gzhead->extra_len; 683205194Sdelphij str = s->gzhead->name; 684205194Sdelphij if (str != Z_NULL) 685205194Sdelphij do { 686205194Sdelphij wraplen++; 687205194Sdelphij } while (*str++); 688205194Sdelphij str = s->gzhead->comment; 689205194Sdelphij if (str != Z_NULL) 690205194Sdelphij do { 691205194Sdelphij wraplen++; 692205194Sdelphij } while (*str++); 693205194Sdelphij if (s->gzhead->hcrc) 694205194Sdelphij wraplen += 2; 695205194Sdelphij } 696205194Sdelphij break; 697313796Sdelphij#endif 698205194Sdelphij default: /* for compiler happiness */ 699205194Sdelphij wraplen = 6; 700205194Sdelphij } 701205194Sdelphij 702131377Stjr /* if not default parameters, return conservative bound */ 703131377Stjr if (s->w_bits != 15 || s->hash_bits != 8 + 7) 704205194Sdelphij return complen + wraplen; 705131377Stjr 706131377Stjr /* default settings: return tight bound for that case */ 707205194Sdelphij return sourceLen + (sourceLen >> 12) + (sourceLen >> 14) + 708205194Sdelphij (sourceLen >> 25) + 13 - 6 + wraplen; 709131377Stjr} 710131377Stjr 711131377Stjr/* ========================================================================= 71217651Speter * Put a short in the pending buffer. The 16-bit value is put in MSB order. 71317651Speter * IN assertion: the stream state is correct and there is enough room in 71417651Speter * pending_buf. 71517651Speter */ 71617651Speterlocal void putShortMSB (s, b) 71717651Speter deflate_state *s; 71817651Speter uInt b; 71917651Speter{ 72017651Speter put_byte(s, (Byte)(b >> 8)); 72117651Speter put_byte(s, (Byte)(b & 0xff)); 722131377Stjr} 72317651Speter 72417651Speter/* ========================================================================= 725313796Sdelphij * Flush as much pending output as possible. All deflate() output, except for 726313796Sdelphij * some deflate_stored() output, goes through this function so some 727313796Sdelphij * applications may wish to modify it to avoid allocating a large 728313796Sdelphij * strm->next_out buffer and copying into it. (See also read_buf()). 72917651Speter */ 73017651Speterlocal void flush_pending(strm) 73117651Speter z_streamp strm; 73217651Speter{ 733230837Sdelphij unsigned len; 734230837Sdelphij deflate_state *s = strm->state; 73517651Speter 736230837Sdelphij _tr_flush_bits(s); 737230837Sdelphij len = s->pending; 73817651Speter if (len > strm->avail_out) len = strm->avail_out; 73917651Speter if (len == 0) return; 74017651Speter 741230837Sdelphij zmemcpy(strm->next_out, s->pending_out, len); 74217651Speter strm->next_out += len; 743230837Sdelphij s->pending_out += len; 74417651Speter strm->total_out += len; 745313796Sdelphij strm->avail_out -= len; 746313796Sdelphij s->pending -= len; 747230837Sdelphij if (s->pending == 0) { 748230837Sdelphij s->pending_out = s->pending_buf; 74917651Speter } 75017651Speter} 75117651Speter 752313796Sdelphij/* =========================================================================== 753313796Sdelphij * Update the header CRC with the bytes s->pending_buf[beg..s->pending - 1]. 754313796Sdelphij */ 755313796Sdelphij#define HCRC_UPDATE(beg) \ 756313796Sdelphij do { \ 757313796Sdelphij if (s->gzhead->hcrc && s->pending > (beg)) \ 758313796Sdelphij strm->adler = crc32(strm->adler, s->pending_buf + (beg), \ 759313796Sdelphij s->pending - (beg)); \ 760313796Sdelphij } while (0) 761313796Sdelphij 76217651Speter/* ========================================================================= */ 76333904Ssteveint ZEXPORT deflate (strm, flush) 76417651Speter z_streamp strm; 76517651Speter int flush; 76617651Speter{ 76717651Speter int old_flush; /* value of flush param for previous deflate call */ 76817651Speter deflate_state *s; 76917651Speter 770313796Sdelphij if (deflateStateCheck(strm) || flush > Z_BLOCK || flush < 0) { 77117651Speter return Z_STREAM_ERROR; 77217651Speter } 77317651Speter s = strm->state; 77417651Speter 77517651Speter if (strm->next_out == Z_NULL || 776313796Sdelphij (strm->avail_in != 0 && strm->next_in == Z_NULL) || 777131377Stjr (s->status == FINISH_STATE && flush != Z_FINISH)) { 77817651Speter ERR_RETURN(strm, Z_STREAM_ERROR); 77917651Speter } 78017651Speter if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR); 78117651Speter 78217651Speter old_flush = s->last_flush; 78317651Speter s->last_flush = flush; 78417651Speter 785313796Sdelphij /* Flush as much pending output as possible */ 786313796Sdelphij if (s->pending != 0) { 787313796Sdelphij flush_pending(strm); 788313796Sdelphij if (strm->avail_out == 0) { 789313796Sdelphij /* Since avail_out is 0, deflate will be called again with 790313796Sdelphij * more output space, but possibly with both pending and 791313796Sdelphij * avail_in equal to zero. There won't be anything to do, 792313796Sdelphij * but this is not an error situation so make sure we 793313796Sdelphij * return OK instead of BUF_ERROR at next call of deflate: 794313796Sdelphij */ 795313796Sdelphij s->last_flush = -1; 796313796Sdelphij return Z_OK; 797313796Sdelphij } 798313796Sdelphij 799313796Sdelphij /* Make sure there is something to do and avoid duplicate consecutive 800313796Sdelphij * flushes. For repeated and useless calls with Z_FINISH, we keep 801313796Sdelphij * returning Z_STREAM_END instead of Z_BUF_ERROR. 802313796Sdelphij */ 803313796Sdelphij } else if (strm->avail_in == 0 && RANK(flush) <= RANK(old_flush) && 804313796Sdelphij flush != Z_FINISH) { 805313796Sdelphij ERR_RETURN(strm, Z_BUF_ERROR); 806313796Sdelphij } 807313796Sdelphij 808313796Sdelphij /* User must not provide more input after the first FINISH: */ 809313796Sdelphij if (s->status == FINISH_STATE && strm->avail_in != 0) { 810313796Sdelphij ERR_RETURN(strm, Z_BUF_ERROR); 811313796Sdelphij } 812313796Sdelphij 813131377Stjr /* Write the header */ 81417651Speter if (s->status == INIT_STATE) { 815313796Sdelphij /* zlib header */ 816313796Sdelphij uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8; 817313796Sdelphij uInt level_flags; 818313796Sdelphij 819313796Sdelphij if (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2) 820313796Sdelphij level_flags = 0; 821313796Sdelphij else if (s->level < 6) 822313796Sdelphij level_flags = 1; 823313796Sdelphij else if (s->level == 6) 824313796Sdelphij level_flags = 2; 825131377Stjr else 826313796Sdelphij level_flags = 3; 827313796Sdelphij header |= (level_flags << 6); 828313796Sdelphij if (s->strstart != 0) header |= PRESET_DICT; 829313796Sdelphij header += 31 - (header % 31); 83017651Speter 831313796Sdelphij putShortMSB(s, header); 83217651Speter 833313796Sdelphij /* Save the adler32 of the preset dictionary: */ 834313796Sdelphij if (s->strstart != 0) { 835313796Sdelphij putShortMSB(s, (uInt)(strm->adler >> 16)); 836313796Sdelphij putShortMSB(s, (uInt)(strm->adler & 0xffff)); 837313796Sdelphij } 838313796Sdelphij strm->adler = adler32(0L, Z_NULL, 0); 839313796Sdelphij s->status = BUSY_STATE; 840313796Sdelphij 841313796Sdelphij /* Compression must start with an empty pending buffer */ 842313796Sdelphij flush_pending(strm); 843313796Sdelphij if (s->pending != 0) { 844313796Sdelphij s->last_flush = -1; 845313796Sdelphij return Z_OK; 846313796Sdelphij } 847313796Sdelphij } 848313796Sdelphij#ifdef GZIP 849313796Sdelphij if (s->status == GZIP_STATE) { 850313796Sdelphij /* gzip header */ 851313796Sdelphij strm->adler = crc32(0L, Z_NULL, 0); 852313796Sdelphij put_byte(s, 31); 853313796Sdelphij put_byte(s, 139); 854313796Sdelphij put_byte(s, 8); 855313796Sdelphij if (s->gzhead == Z_NULL) { 856313796Sdelphij put_byte(s, 0); 857313796Sdelphij put_byte(s, 0); 858313796Sdelphij put_byte(s, 0); 859313796Sdelphij put_byte(s, 0); 860313796Sdelphij put_byte(s, 0); 861313796Sdelphij put_byte(s, s->level == 9 ? 2 : 862313796Sdelphij (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ? 863313796Sdelphij 4 : 0)); 864313796Sdelphij put_byte(s, OS_CODE); 865131377Stjr s->status = BUSY_STATE; 86617651Speter 867313796Sdelphij /* Compression must start with an empty pending buffer */ 868313796Sdelphij flush_pending(strm); 869313796Sdelphij if (s->pending != 0) { 870313796Sdelphij s->last_flush = -1; 871313796Sdelphij return Z_OK; 872131377Stjr } 873131377Stjr } 874313796Sdelphij else { 875313796Sdelphij put_byte(s, (s->gzhead->text ? 1 : 0) + 876313796Sdelphij (s->gzhead->hcrc ? 2 : 0) + 877313796Sdelphij (s->gzhead->extra == Z_NULL ? 0 : 4) + 878313796Sdelphij (s->gzhead->name == Z_NULL ? 0 : 8) + 879313796Sdelphij (s->gzhead->comment == Z_NULL ? 0 : 16) 880313796Sdelphij ); 881313796Sdelphij put_byte(s, (Byte)(s->gzhead->time & 0xff)); 882313796Sdelphij put_byte(s, (Byte)((s->gzhead->time >> 8) & 0xff)); 883313796Sdelphij put_byte(s, (Byte)((s->gzhead->time >> 16) & 0xff)); 884313796Sdelphij put_byte(s, (Byte)((s->gzhead->time >> 24) & 0xff)); 885313796Sdelphij put_byte(s, s->level == 9 ? 2 : 886313796Sdelphij (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ? 887313796Sdelphij 4 : 0)); 888313796Sdelphij put_byte(s, s->gzhead->os & 0xff); 889313796Sdelphij if (s->gzhead->extra != Z_NULL) { 890313796Sdelphij put_byte(s, s->gzhead->extra_len & 0xff); 891313796Sdelphij put_byte(s, (s->gzhead->extra_len >> 8) & 0xff); 892313796Sdelphij } 893313796Sdelphij if (s->gzhead->hcrc) 894313796Sdelphij strm->adler = crc32(strm->adler, s->pending_buf, 895313796Sdelphij s->pending); 896313796Sdelphij s->gzindex = 0; 897313796Sdelphij s->status = EXTRA_STATE; 898313796Sdelphij } 89917651Speter } 900157043Sdes if (s->status == EXTRA_STATE) { 901205194Sdelphij if (s->gzhead->extra != Z_NULL) { 902313796Sdelphij ulg beg = s->pending; /* start of bytes to update crc */ 903313796Sdelphij uInt left = (s->gzhead->extra_len & 0xffff) - s->gzindex; 904313796Sdelphij while (s->pending + left > s->pending_buf_size) { 905313796Sdelphij uInt copy = s->pending_buf_size - s->pending; 906313796Sdelphij zmemcpy(s->pending_buf + s->pending, 907313796Sdelphij s->gzhead->extra + s->gzindex, copy); 908313796Sdelphij s->pending = s->pending_buf_size; 909313796Sdelphij HCRC_UPDATE(beg); 910313796Sdelphij s->gzindex += copy; 911313796Sdelphij flush_pending(strm); 912313796Sdelphij if (s->pending != 0) { 913313796Sdelphij s->last_flush = -1; 914313796Sdelphij return Z_OK; 915157043Sdes } 916313796Sdelphij beg = 0; 917313796Sdelphij left -= copy; 918157043Sdes } 919313796Sdelphij zmemcpy(s->pending_buf + s->pending, 920313796Sdelphij s->gzhead->extra + s->gzindex, left); 921313796Sdelphij s->pending += left; 922313796Sdelphij HCRC_UPDATE(beg); 923313796Sdelphij s->gzindex = 0; 924157043Sdes } 925313796Sdelphij s->status = NAME_STATE; 926157043Sdes } 927157043Sdes if (s->status == NAME_STATE) { 928205194Sdelphij if (s->gzhead->name != Z_NULL) { 929313796Sdelphij ulg beg = s->pending; /* start of bytes to update crc */ 930157043Sdes int val; 931157043Sdes do { 932157043Sdes if (s->pending == s->pending_buf_size) { 933313796Sdelphij HCRC_UPDATE(beg); 934157043Sdes flush_pending(strm); 935313796Sdelphij if (s->pending != 0) { 936313796Sdelphij s->last_flush = -1; 937313796Sdelphij return Z_OK; 938157043Sdes } 939313796Sdelphij beg = 0; 940157043Sdes } 941157043Sdes val = s->gzhead->name[s->gzindex++]; 942157043Sdes put_byte(s, val); 943157043Sdes } while (val != 0); 944313796Sdelphij HCRC_UPDATE(beg); 945313796Sdelphij s->gzindex = 0; 946157043Sdes } 947313796Sdelphij s->status = COMMENT_STATE; 948157043Sdes } 949157043Sdes if (s->status == COMMENT_STATE) { 950205194Sdelphij if (s->gzhead->comment != Z_NULL) { 951313796Sdelphij ulg beg = s->pending; /* start of bytes to update crc */ 952157043Sdes int val; 953157043Sdes do { 954157043Sdes if (s->pending == s->pending_buf_size) { 955313796Sdelphij HCRC_UPDATE(beg); 956157043Sdes flush_pending(strm); 957313796Sdelphij if (s->pending != 0) { 958313796Sdelphij s->last_flush = -1; 959313796Sdelphij return Z_OK; 960157043Sdes } 961313796Sdelphij beg = 0; 962157043Sdes } 963157043Sdes val = s->gzhead->comment[s->gzindex++]; 964157043Sdes put_byte(s, val); 965157043Sdes } while (val != 0); 966313796Sdelphij HCRC_UPDATE(beg); 967157043Sdes } 968313796Sdelphij s->status = HCRC_STATE; 969157043Sdes } 970157043Sdes if (s->status == HCRC_STATE) { 971157043Sdes if (s->gzhead->hcrc) { 972313796Sdelphij if (s->pending + 2 > s->pending_buf_size) { 973157043Sdes flush_pending(strm); 974313796Sdelphij if (s->pending != 0) { 975313796Sdelphij s->last_flush = -1; 976313796Sdelphij return Z_OK; 977313796Sdelphij } 978157043Sdes } 979313796Sdelphij put_byte(s, (Byte)(strm->adler & 0xff)); 980313796Sdelphij put_byte(s, (Byte)((strm->adler >> 8) & 0xff)); 981313796Sdelphij strm->adler = crc32(0L, Z_NULL, 0); 982157043Sdes } 983313796Sdelphij s->status = BUSY_STATE; 984157043Sdes 985313796Sdelphij /* Compression must start with an empty pending buffer */ 98617651Speter flush_pending(strm); 987313796Sdelphij if (s->pending != 0) { 988131377Stjr s->last_flush = -1; 989131377Stjr return Z_OK; 990131377Stjr } 99117651Speter } 992313796Sdelphij#endif 99317651Speter 99417651Speter /* Start a new block or continue the current one. 99517651Speter */ 99617651Speter if (strm->avail_in != 0 || s->lookahead != 0 || 99717651Speter (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) { 99817651Speter block_state bstate; 99917651Speter 1000313796Sdelphij bstate = s->level == 0 ? deflate_stored(s, flush) : 1001313796Sdelphij s->strategy == Z_HUFFMAN_ONLY ? deflate_huff(s, flush) : 1002313796Sdelphij s->strategy == Z_RLE ? deflate_rle(s, flush) : 1003313796Sdelphij (*(configuration_table[s->level].func))(s, flush); 100417651Speter 100517651Speter if (bstate == finish_started || bstate == finish_done) { 100617651Speter s->status = FINISH_STATE; 100717651Speter } 100817651Speter if (bstate == need_more || bstate == finish_started) { 1009131377Stjr if (strm->avail_out == 0) { 1010131377Stjr s->last_flush = -1; /* avoid BUF_ERROR next call, see above */ 1011131377Stjr } 1012131377Stjr return Z_OK; 1013131377Stjr /* If flush != Z_NO_FLUSH && avail_out == 0, the next call 1014131377Stjr * of deflate should use the same flush parameter to make sure 1015131377Stjr * that the flush is complete. So we don't have to output an 1016131377Stjr * empty block here, this will be done at next call. This also 1017131377Stjr * ensures that for a very small output buffer, we emit at most 1018131377Stjr * one empty block. 1019131377Stjr */ 1020131377Stjr } 102117651Speter if (bstate == block_done) { 102217651Speter if (flush == Z_PARTIAL_FLUSH) { 102317651Speter _tr_align(s); 1024205194Sdelphij } else if (flush != Z_BLOCK) { /* FULL_FLUSH or SYNC_FLUSH */ 102517651Speter _tr_stored_block(s, (char*)0, 0L, 0); 102617651Speter /* For a full flush, this empty block will be recognized 102717651Speter * as a special marker by inflate_sync(). 102817651Speter */ 102917651Speter if (flush == Z_FULL_FLUSH) { 103017651Speter CLEAR_HASH(s); /* forget history */ 1031205194Sdelphij if (s->lookahead == 0) { 1032205194Sdelphij s->strstart = 0; 1033205194Sdelphij s->block_start = 0L; 1034230837Sdelphij s->insert = 0; 1035205194Sdelphij } 103617651Speter } 103717651Speter } 103817651Speter flush_pending(strm); 1039131377Stjr if (strm->avail_out == 0) { 1040131377Stjr s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */ 1041131377Stjr return Z_OK; 1042131377Stjr } 104317651Speter } 104417651Speter } 104517651Speter 104617651Speter if (flush != Z_FINISH) return Z_OK; 1047131377Stjr if (s->wrap <= 0) return Z_STREAM_END; 104817651Speter 1049131377Stjr /* Write the trailer */ 1050131377Stjr#ifdef GZIP 1051131377Stjr if (s->wrap == 2) { 1052131377Stjr put_byte(s, (Byte)(strm->adler & 0xff)); 1053131377Stjr put_byte(s, (Byte)((strm->adler >> 8) & 0xff)); 1054131377Stjr put_byte(s, (Byte)((strm->adler >> 16) & 0xff)); 1055131377Stjr put_byte(s, (Byte)((strm->adler >> 24) & 0xff)); 1056131377Stjr put_byte(s, (Byte)(strm->total_in & 0xff)); 1057131377Stjr put_byte(s, (Byte)((strm->total_in >> 8) & 0xff)); 1058131377Stjr put_byte(s, (Byte)((strm->total_in >> 16) & 0xff)); 1059131377Stjr put_byte(s, (Byte)((strm->total_in >> 24) & 0xff)); 1060131377Stjr } 1061131377Stjr else 1062131377Stjr#endif 1063131377Stjr { 1064131377Stjr putShortMSB(s, (uInt)(strm->adler >> 16)); 1065131377Stjr putShortMSB(s, (uInt)(strm->adler & 0xffff)); 1066131377Stjr } 106717651Speter flush_pending(strm); 106817651Speter /* If avail_out is zero, the application will call deflate again 106917651Speter * to flush the rest. 107017651Speter */ 1071131377Stjr if (s->wrap > 0) s->wrap = -s->wrap; /* write the trailer only once! */ 107217651Speter return s->pending != 0 ? Z_OK : Z_STREAM_END; 107317651Speter} 107417651Speter 107517651Speter/* ========================================================================= */ 107633904Ssteveint ZEXPORT deflateEnd (strm) 107717651Speter z_streamp strm; 107817651Speter{ 107917651Speter int status; 108017651Speter 1081313796Sdelphij if (deflateStateCheck(strm)) return Z_STREAM_ERROR; 108217651Speter 108333904Ssteve status = strm->state->status; 108433904Ssteve 108517651Speter /* Deallocate in reverse order of allocations: */ 108617651Speter TRY_FREE(strm, strm->state->pending_buf); 108717651Speter TRY_FREE(strm, strm->state->head); 108817651Speter TRY_FREE(strm, strm->state->prev); 108917651Speter TRY_FREE(strm, strm->state->window); 109017651Speter 109117651Speter ZFREE(strm, strm->state); 109217651Speter strm->state = Z_NULL; 109317651Speter 109417651Speter return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK; 109517651Speter} 109617651Speter 109733904Ssteve/* ========================================================================= 109833904Ssteve * Copy the source state to the destination state. 109933904Ssteve * To simplify the source, this is not supported for 16-bit MSDOS (which 110033904Ssteve * doesn't have enough memory anyway to duplicate compression states). 110133904Ssteve */ 110233904Ssteveint ZEXPORT deflateCopy (dest, source) 110317651Speter z_streamp dest; 110417651Speter z_streamp source; 110517651Speter{ 110633904Ssteve#ifdef MAXSEG_64K 110733904Ssteve return Z_STREAM_ERROR; 110833904Ssteve#else 110933904Ssteve deflate_state *ds; 111033904Ssteve deflate_state *ss; 111133904Ssteve ushf *overlay; 111233904Ssteve 111333904Ssteve 1114313796Sdelphij if (deflateStateCheck(source) || dest == Z_NULL) { 111517651Speter return Z_STREAM_ERROR; 111617651Speter } 111742468Speter 111842468Speter ss = source->state; 111942468Speter 1120230837Sdelphij zmemcpy((voidpf)dest, (voidpf)source, sizeof(z_stream)); 112117651Speter 112233904Ssteve ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state)); 112333904Ssteve if (ds == Z_NULL) return Z_MEM_ERROR; 112433904Ssteve dest->state = (struct internal_state FAR *) ds; 1125230837Sdelphij zmemcpy((voidpf)ds, (voidpf)ss, sizeof(deflate_state)); 112633904Ssteve ds->strm = dest; 112733904Ssteve 112833904Ssteve ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte)); 112933904Ssteve ds->prev = (Posf *) ZALLOC(dest, ds->w_size, sizeof(Pos)); 113033904Ssteve ds->head = (Posf *) ZALLOC(dest, ds->hash_size, sizeof(Pos)); 113133904Ssteve overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof(ush)+2); 113233904Ssteve ds->pending_buf = (uchf *) overlay; 113333904Ssteve 113433904Ssteve if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL || 113533904Ssteve ds->pending_buf == Z_NULL) { 113633904Ssteve deflateEnd (dest); 113733904Ssteve return Z_MEM_ERROR; 113833904Ssteve } 113933904Ssteve /* following zmemcpy do not work for 16-bit MSDOS */ 114033904Ssteve zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte)); 1141230837Sdelphij zmemcpy((voidpf)ds->prev, (voidpf)ss->prev, ds->w_size * sizeof(Pos)); 1142230837Sdelphij zmemcpy((voidpf)ds->head, (voidpf)ss->head, ds->hash_size * sizeof(Pos)); 114333904Ssteve zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size); 114433904Ssteve 114533904Ssteve ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf); 114633904Ssteve ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush); 114733904Ssteve ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize; 114833904Ssteve 114933904Ssteve ds->l_desc.dyn_tree = ds->dyn_ltree; 115033904Ssteve ds->d_desc.dyn_tree = ds->dyn_dtree; 115133904Ssteve ds->bl_desc.dyn_tree = ds->bl_tree; 115233904Ssteve 115317651Speter return Z_OK; 1154131377Stjr#endif /* MAXSEG_64K */ 115517651Speter} 115617651Speter 115717651Speter/* =========================================================================== 115817651Speter * Read a new buffer from the current input stream, update the adler32 115917651Speter * and total number of bytes read. All deflate() input goes through 116017651Speter * this function so some applications may wish to modify it to avoid 116117651Speter * allocating a large strm->next_in buffer and copying from it. 116217651Speter * (See also flush_pending()). 116317651Speter */ 1164313796Sdelphijlocal unsigned read_buf(strm, buf, size) 116517651Speter z_streamp strm; 116633904Ssteve Bytef *buf; 116717651Speter unsigned size; 116817651Speter{ 116917651Speter unsigned len = strm->avail_in; 117017651Speter 117117651Speter if (len > size) len = size; 117217651Speter if (len == 0) return 0; 117317651Speter 117417651Speter strm->avail_in -= len; 117517651Speter 1176230837Sdelphij zmemcpy(buf, strm->next_in, len); 1177131377Stjr if (strm->state->wrap == 1) { 1178230837Sdelphij strm->adler = adler32(strm->adler, buf, len); 117917651Speter } 1180131377Stjr#ifdef GZIP 1181131377Stjr else if (strm->state->wrap == 2) { 1182230837Sdelphij strm->adler = crc32(strm->adler, buf, len); 1183131377Stjr } 1184131377Stjr#endif 118517651Speter strm->next_in += len; 118617651Speter strm->total_in += len; 118717651Speter 1188313796Sdelphij return len; 118917651Speter} 119017651Speter 119117651Speter/* =========================================================================== 119217651Speter * Initialize the "longest match" routines for a new zlib stream 119317651Speter */ 119417651Speterlocal void lm_init (s) 119517651Speter deflate_state *s; 119617651Speter{ 119717651Speter s->window_size = (ulg)2L*s->w_size; 119817651Speter 119917651Speter CLEAR_HASH(s); 120017651Speter 120117651Speter /* Set the default configuration parameters: 120217651Speter */ 120317651Speter s->max_lazy_match = configuration_table[s->level].max_lazy; 120417651Speter s->good_match = configuration_table[s->level].good_length; 120517651Speter s->nice_match = configuration_table[s->level].nice_length; 120617651Speter s->max_chain_length = configuration_table[s->level].max_chain; 120717651Speter 120817651Speter s->strstart = 0; 120917651Speter s->block_start = 0L; 121017651Speter s->lookahead = 0; 1211230837Sdelphij s->insert = 0; 121217651Speter s->match_length = s->prev_length = MIN_MATCH-1; 121317651Speter s->match_available = 0; 121417651Speter s->ins_h = 0; 1215157043Sdes#ifndef FASTEST 121617651Speter#ifdef ASMV 121717651Speter match_init(); /* initialize the asm code */ 121817651Speter#endif 1219157043Sdes#endif 122017651Speter} 122117651Speter 1222131377Stjr#ifndef FASTEST 122317651Speter/* =========================================================================== 122417651Speter * Set match_start to the longest match starting at the given string and 122517651Speter * return its length. Matches shorter or equal to prev_length are discarded, 122617651Speter * in which case the result is equal to prev_length and match_start is 122717651Speter * garbage. 122817651Speter * IN assertions: cur_match is the head of the hash chain for the current 122917651Speter * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1 123017651Speter * OUT assertion: the match length is not greater than s->lookahead. 123117651Speter */ 123217651Speter#ifndef ASMV 123317651Speter/* For 80x86 and 680x0, an optimized version will be provided in match.asm or 123417651Speter * match.S. The code will be functionally equivalent. 123517651Speter */ 123617651Speterlocal uInt longest_match(s, cur_match) 123717651Speter deflate_state *s; 123817651Speter IPos cur_match; /* current match */ 123917651Speter{ 124017651Speter unsigned chain_length = s->max_chain_length;/* max hash chain length */ 124117651Speter register Bytef *scan = s->window + s->strstart; /* current string */ 1242313796Sdelphij register Bytef *match; /* matched string */ 124317651Speter register int len; /* length of current match */ 1244313796Sdelphij int best_len = (int)s->prev_length; /* best match length so far */ 124517651Speter int nice_match = s->nice_match; /* stop if match long enough */ 124617651Speter IPos limit = s->strstart > (IPos)MAX_DIST(s) ? 124717651Speter s->strstart - (IPos)MAX_DIST(s) : NIL; 124817651Speter /* Stop when cur_match becomes <= limit. To simplify the code, 124917651Speter * we prevent matches with the string of window index 0. 125017651Speter */ 125117651Speter Posf *prev = s->prev; 125217651Speter uInt wmask = s->w_mask; 125317651Speter 125417651Speter#ifdef UNALIGNED_OK 125517651Speter /* Compare two bytes at a time. Note: this is not always beneficial. 125617651Speter * Try with and without -DUNALIGNED_OK to check. 125717651Speter */ 125817651Speter register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1; 125917651Speter register ush scan_start = *(ushf*)scan; 126017651Speter register ush scan_end = *(ushf*)(scan+best_len-1); 126117651Speter#else 126217651Speter register Bytef *strend = s->window + s->strstart + MAX_MATCH; 126317651Speter register Byte scan_end1 = scan[best_len-1]; 126417651Speter register Byte scan_end = scan[best_len]; 126517651Speter#endif 126617651Speter 126717651Speter /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. 126817651Speter * It is easy to get rid of this optimization if necessary. 126917651Speter */ 127017651Speter Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever"); 127117651Speter 127217651Speter /* Do not waste too much time if we already have a good match: */ 127317651Speter if (s->prev_length >= s->good_match) { 127417651Speter chain_length >>= 2; 127517651Speter } 127617651Speter /* Do not look for matches beyond the end of the input. This is necessary 127717651Speter * to make deflate deterministic. 127817651Speter */ 1279313796Sdelphij if ((uInt)nice_match > s->lookahead) nice_match = (int)s->lookahead; 128017651Speter 128117651Speter Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead"); 128217651Speter 128317651Speter do { 128417651Speter Assert(cur_match < s->strstart, "no future"); 128517651Speter match = s->window + cur_match; 128617651Speter 128717651Speter /* Skip to next match if the match length cannot increase 1288157043Sdes * or if the match length is less than 2. Note that the checks below 1289157043Sdes * for insufficient lookahead only occur occasionally for performance 1290157043Sdes * reasons. Therefore uninitialized memory will be accessed, and 1291157043Sdes * conditional jumps will be made that depend on those values. 1292157043Sdes * However the length of the match is limited to the lookahead, so 1293157043Sdes * the output of deflate is not affected by the uninitialized values. 129417651Speter */ 129517651Speter#if (defined(UNALIGNED_OK) && MAX_MATCH == 258) 129617651Speter /* This code assumes sizeof(unsigned short) == 2. Do not use 129717651Speter * UNALIGNED_OK if your compiler uses a different size. 129817651Speter */ 129917651Speter if (*(ushf*)(match+best_len-1) != scan_end || 130017651Speter *(ushf*)match != scan_start) continue; 130117651Speter 130217651Speter /* It is not necessary to compare scan[2] and match[2] since they are 130317651Speter * always equal when the other bytes match, given that the hash keys 130417651Speter * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at 130517651Speter * strstart+3, +5, ... up to strstart+257. We check for insufficient 130617651Speter * lookahead only every 4th comparison; the 128th check will be made 130717651Speter * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is 130817651Speter * necessary to put more guard bytes at the end of the window, or 130917651Speter * to check more often for insufficient lookahead. 131017651Speter */ 131117651Speter Assert(scan[2] == match[2], "scan[2]?"); 131217651Speter scan++, match++; 131317651Speter do { 131417651Speter } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) && 131517651Speter *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 131617651Speter *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 131717651Speter *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 131817651Speter scan < strend); 131917651Speter /* The funny "do {}" generates better code on most compilers */ 132017651Speter 132117651Speter /* Here, scan <= window+strstart+257 */ 132217651Speter Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 132317651Speter if (*scan == *match) scan++; 132417651Speter 132517651Speter len = (MAX_MATCH - 1) - (int)(strend-scan); 132617651Speter scan = strend - (MAX_MATCH-1); 132717651Speter 132817651Speter#else /* UNALIGNED_OK */ 132917651Speter 133017651Speter if (match[best_len] != scan_end || 133117651Speter match[best_len-1] != scan_end1 || 133217651Speter *match != *scan || 133317651Speter *++match != scan[1]) continue; 133417651Speter 133517651Speter /* The check at best_len-1 can be removed because it will be made 133617651Speter * again later. (This heuristic is not always a win.) 133717651Speter * It is not necessary to compare scan[2] and match[2] since they 133817651Speter * are always equal when the other bytes match, given that 133917651Speter * the hash keys are equal and that HASH_BITS >= 8. 134017651Speter */ 134117651Speter scan += 2, match++; 134217651Speter Assert(*scan == *match, "match[2]?"); 134317651Speter 134417651Speter /* We check for insufficient lookahead only every 8th comparison; 134517651Speter * the 256th check will be made at strstart+258. 134617651Speter */ 134717651Speter do { 134817651Speter } while (*++scan == *++match && *++scan == *++match && 134917651Speter *++scan == *++match && *++scan == *++match && 135017651Speter *++scan == *++match && *++scan == *++match && 135117651Speter *++scan == *++match && *++scan == *++match && 135217651Speter scan < strend); 135317651Speter 135417651Speter Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 135517651Speter 135617651Speter len = MAX_MATCH - (int)(strend - scan); 135717651Speter scan = strend - MAX_MATCH; 135817651Speter 135917651Speter#endif /* UNALIGNED_OK */ 136017651Speter 136117651Speter if (len > best_len) { 136217651Speter s->match_start = cur_match; 136317651Speter best_len = len; 136417651Speter if (len >= nice_match) break; 136517651Speter#ifdef UNALIGNED_OK 136617651Speter scan_end = *(ushf*)(scan+best_len-1); 136717651Speter#else 136817651Speter scan_end1 = scan[best_len-1]; 136917651Speter scan_end = scan[best_len]; 137017651Speter#endif 137117651Speter } 137217651Speter } while ((cur_match = prev[cur_match & wmask]) > limit 137317651Speter && --chain_length != 0); 137417651Speter 137533904Ssteve if ((uInt)best_len <= s->lookahead) return (uInt)best_len; 137617651Speter return s->lookahead; 137717651Speter} 1378131377Stjr#endif /* ASMV */ 137933904Ssteve 1380205194Sdelphij#else /* FASTEST */ 1381205194Sdelphij 138233904Ssteve/* --------------------------------------------------------------------------- 1383205194Sdelphij * Optimized version for FASTEST only 138433904Ssteve */ 1385205194Sdelphijlocal uInt longest_match(s, cur_match) 138633904Ssteve deflate_state *s; 138733904Ssteve IPos cur_match; /* current match */ 138833904Ssteve{ 138933904Ssteve register Bytef *scan = s->window + s->strstart; /* current string */ 139033904Ssteve register Bytef *match; /* matched string */ 139133904Ssteve register int len; /* length of current match */ 139233904Ssteve register Bytef *strend = s->window + s->strstart + MAX_MATCH; 139333904Ssteve 139433904Ssteve /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. 139533904Ssteve * It is easy to get rid of this optimization if necessary. 139633904Ssteve */ 139733904Ssteve Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever"); 139833904Ssteve 139933904Ssteve Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead"); 140033904Ssteve 140133904Ssteve Assert(cur_match < s->strstart, "no future"); 140233904Ssteve 140333904Ssteve match = s->window + cur_match; 140433904Ssteve 140533904Ssteve /* Return failure if the match length is less than 2: 140633904Ssteve */ 140733904Ssteve if (match[0] != scan[0] || match[1] != scan[1]) return MIN_MATCH-1; 140833904Ssteve 140933904Ssteve /* The check at best_len-1 can be removed because it will be made 141033904Ssteve * again later. (This heuristic is not always a win.) 141133904Ssteve * It is not necessary to compare scan[2] and match[2] since they 141233904Ssteve * are always equal when the other bytes match, given that 141333904Ssteve * the hash keys are equal and that HASH_BITS >= 8. 141433904Ssteve */ 141533904Ssteve scan += 2, match += 2; 141633904Ssteve Assert(*scan == *match, "match[2]?"); 141733904Ssteve 141833904Ssteve /* We check for insufficient lookahead only every 8th comparison; 141933904Ssteve * the 256th check will be made at strstart+258. 142033904Ssteve */ 142133904Ssteve do { 142233904Ssteve } while (*++scan == *++match && *++scan == *++match && 1423131377Stjr *++scan == *++match && *++scan == *++match && 1424131377Stjr *++scan == *++match && *++scan == *++match && 1425131377Stjr *++scan == *++match && *++scan == *++match && 1426131377Stjr scan < strend); 142733904Ssteve 142833904Ssteve Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 142933904Ssteve 143033904Ssteve len = MAX_MATCH - (int)(strend - scan); 143133904Ssteve 143233904Ssteve if (len < MIN_MATCH) return MIN_MATCH - 1; 143333904Ssteve 143433904Ssteve s->match_start = cur_match; 1435131377Stjr return (uInt)len <= s->lookahead ? (uInt)len : s->lookahead; 143633904Ssteve} 143717651Speter 1438205194Sdelphij#endif /* FASTEST */ 1439205194Sdelphij 1440313796Sdelphij#ifdef ZLIB_DEBUG 1441313796Sdelphij 1442313796Sdelphij#define EQUAL 0 1443313796Sdelphij/* result of memcmp for equal strings */ 1444313796Sdelphij 144517651Speter/* =========================================================================== 144617651Speter * Check that the match at match_start is indeed a match. 144717651Speter */ 144817651Speterlocal void check_match(s, start, match, length) 144917651Speter deflate_state *s; 145017651Speter IPos start, match; 145117651Speter int length; 145217651Speter{ 145317651Speter /* check that the match is indeed a match */ 145433904Ssteve if (zmemcmp(s->window + match, 145533904Ssteve s->window + start, length) != EQUAL) { 145617651Speter fprintf(stderr, " start %u, match %u, length %d\n", 1457131377Stjr start, match, length); 145817651Speter do { 1459131377Stjr fprintf(stderr, "%c%c", s->window[match++], s->window[start++]); 1460131377Stjr } while (--length != 0); 146117651Speter z_error("invalid match"); 146217651Speter } 146333904Ssteve if (z_verbose > 1) { 146417651Speter fprintf(stderr,"\\[%d,%d]", start-match, length); 146517651Speter do { putc(s->window[start++], stderr); } while (--length != 0); 146617651Speter } 146717651Speter} 146817651Speter#else 146917651Speter# define check_match(s, start, match, length) 1470313796Sdelphij#endif /* ZLIB_DEBUG */ 147117651Speter 147217651Speter/* =========================================================================== 147317651Speter * Fill the window when the lookahead becomes insufficient. 147417651Speter * Updates strstart and lookahead. 147517651Speter * 147617651Speter * IN assertion: lookahead < MIN_LOOKAHEAD 147717651Speter * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD 147817651Speter * At least one byte has been read, or avail_in == 0; reads are 147917651Speter * performed for at least two bytes (required for the zip translate_eol 148017651Speter * option -- not supported here). 148117651Speter */ 148217651Speterlocal void fill_window(s) 148317651Speter deflate_state *s; 148417651Speter{ 1485313796Sdelphij unsigned n; 148617651Speter unsigned more; /* Amount of free space at the end of the window. */ 148717651Speter uInt wsize = s->w_size; 148817651Speter 1489230837Sdelphij Assert(s->lookahead < MIN_LOOKAHEAD, "already enough lookahead"); 1490230837Sdelphij 149117651Speter do { 149217651Speter more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart); 149317651Speter 149417651Speter /* Deal with !@#$% 64K limit: */ 1495131377Stjr if (sizeof(int) <= 2) { 1496131377Stjr if (more == 0 && s->strstart == 0 && s->lookahead == 0) { 1497131377Stjr more = wsize; 149817651Speter 1499131377Stjr } else if (more == (unsigned)(-1)) { 1500131377Stjr /* Very unlikely, but possible on 16 bit machine if 1501131377Stjr * strstart == 0 && lookahead == 1 (input done a byte at time) 1502131377Stjr */ 1503131377Stjr more--; 1504131377Stjr } 1505131377Stjr } 150617651Speter 150717651Speter /* If the window is almost full and there is insufficient lookahead, 150817651Speter * move the upper half to the lower one to make room in the upper half. 150917651Speter */ 1510131377Stjr if (s->strstart >= wsize+MAX_DIST(s)) { 151117651Speter 1512313796Sdelphij zmemcpy(s->window, s->window+wsize, (unsigned)wsize - more); 151317651Speter s->match_start -= wsize; 151417651Speter s->strstart -= wsize; /* we now have strstart >= MAX_DIST */ 151517651Speter s->block_start -= (long) wsize; 1516313796Sdelphij slide_hash(s); 151717651Speter more += wsize; 151817651Speter } 1519230837Sdelphij if (s->strm->avail_in == 0) break; 152017651Speter 152117651Speter /* If there was no sliding: 152217651Speter * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 && 152317651Speter * more == window_size - lookahead - strstart 152417651Speter * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1) 152517651Speter * => more >= window_size - 2*WSIZE + 2 152617651Speter * In the BIG_MEM or MMAP case (not yet supported), 152717651Speter * window_size == input_size + MIN_LOOKAHEAD && 152817651Speter * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD. 152917651Speter * Otherwise, window_size == 2*WSIZE so more >= 2. 153017651Speter * If there was sliding, more >= WSIZE. So in all cases, more >= 2. 153117651Speter */ 153217651Speter Assert(more >= 2, "more < 2"); 153317651Speter 153433904Ssteve n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more); 153517651Speter s->lookahead += n; 153617651Speter 153717651Speter /* Initialize the hash value now that we have some input: */ 1538230837Sdelphij if (s->lookahead + s->insert >= MIN_MATCH) { 1539230837Sdelphij uInt str = s->strstart - s->insert; 1540230837Sdelphij s->ins_h = s->window[str]; 1541230837Sdelphij UPDATE_HASH(s, s->ins_h, s->window[str + 1]); 154217651Speter#if MIN_MATCH != 3 154317651Speter Call UPDATE_HASH() MIN_MATCH-3 more times 154417651Speter#endif 1545230837Sdelphij while (s->insert) { 1546230837Sdelphij UPDATE_HASH(s, s->ins_h, s->window[str + MIN_MATCH-1]); 1547230837Sdelphij#ifndef FASTEST 1548230837Sdelphij s->prev[str & s->w_mask] = s->head[s->ins_h]; 1549230837Sdelphij#endif 1550230837Sdelphij s->head[s->ins_h] = (Pos)str; 1551230837Sdelphij str++; 1552230837Sdelphij s->insert--; 1553230837Sdelphij if (s->lookahead + s->insert < MIN_MATCH) 1554230837Sdelphij break; 1555230837Sdelphij } 155617651Speter } 155717651Speter /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage, 155817651Speter * but this is not important since only literal bytes will be emitted. 155917651Speter */ 156017651Speter 156117651Speter } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0); 1562205194Sdelphij 1563205194Sdelphij /* If the WIN_INIT bytes after the end of the current data have never been 1564205194Sdelphij * written, then zero those bytes in order to avoid memory check reports of 1565205194Sdelphij * the use of uninitialized (or uninitialised as Julian writes) bytes by 1566205194Sdelphij * the longest match routines. Update the high water mark for the next 1567205194Sdelphij * time through here. WIN_INIT is set to MAX_MATCH since the longest match 1568205194Sdelphij * routines allow scanning to strstart + MAX_MATCH, ignoring lookahead. 1569205194Sdelphij */ 1570205194Sdelphij if (s->high_water < s->window_size) { 1571205194Sdelphij ulg curr = s->strstart + (ulg)(s->lookahead); 1572205194Sdelphij ulg init; 1573205194Sdelphij 1574205194Sdelphij if (s->high_water < curr) { 1575205194Sdelphij /* Previous high water mark below current data -- zero WIN_INIT 1576205194Sdelphij * bytes or up to end of window, whichever is less. 1577205194Sdelphij */ 1578205194Sdelphij init = s->window_size - curr; 1579205194Sdelphij if (init > WIN_INIT) 1580205194Sdelphij init = WIN_INIT; 1581205194Sdelphij zmemzero(s->window + curr, (unsigned)init); 1582205194Sdelphij s->high_water = curr + init; 1583205194Sdelphij } 1584205194Sdelphij else if (s->high_water < (ulg)curr + WIN_INIT) { 1585205194Sdelphij /* High water mark at or above current data, but below current data 1586205194Sdelphij * plus WIN_INIT -- zero out to current data plus WIN_INIT, or up 1587205194Sdelphij * to end of window, whichever is less. 1588205194Sdelphij */ 1589205194Sdelphij init = (ulg)curr + WIN_INIT - s->high_water; 1590205194Sdelphij if (init > s->window_size - s->high_water) 1591205194Sdelphij init = s->window_size - s->high_water; 1592205194Sdelphij zmemzero(s->window + s->high_water, (unsigned)init); 1593205194Sdelphij s->high_water += init; 1594205194Sdelphij } 1595205194Sdelphij } 1596230837Sdelphij 1597230837Sdelphij Assert((ulg)s->strstart <= s->window_size - MIN_LOOKAHEAD, 1598230837Sdelphij "not enough room for search"); 159917651Speter} 160017651Speter 160117651Speter/* =========================================================================== 160217651Speter * Flush the current block, with given end-of-file flag. 160317651Speter * IN assertion: strstart is set to the end of the current match. 160417651Speter */ 1605205194Sdelphij#define FLUSH_BLOCK_ONLY(s, last) { \ 160617651Speter _tr_flush_block(s, (s->block_start >= 0L ? \ 160717651Speter (charf *)&s->window[(unsigned)s->block_start] : \ 160817651Speter (charf *)Z_NULL), \ 1609131377Stjr (ulg)((long)s->strstart - s->block_start), \ 1610205194Sdelphij (last)); \ 161117651Speter s->block_start = s->strstart; \ 161217651Speter flush_pending(s->strm); \ 161317651Speter Tracev((stderr,"[FLUSH]")); \ 161417651Speter} 161517651Speter 161617651Speter/* Same but force premature exit if necessary. */ 1617205194Sdelphij#define FLUSH_BLOCK(s, last) { \ 1618205194Sdelphij FLUSH_BLOCK_ONLY(s, last); \ 1619205194Sdelphij if (s->strm->avail_out == 0) return (last) ? finish_started : need_more; \ 162017651Speter} 162117651Speter 1622313796Sdelphij/* Maximum stored block length in deflate format (not including header). */ 1623313796Sdelphij#define MAX_STORED 65535 1624313796Sdelphij 1625313796Sdelphij/* Minimum of a and b. */ 1626313796Sdelphij#define MIN(a, b) ((a) > (b) ? (b) : (a)) 1627313796Sdelphij 162817651Speter/* =========================================================================== 162917651Speter * Copy without compression as much as possible from the input stream, return 163017651Speter * the current block state. 1631313796Sdelphij * 1632313796Sdelphij * In case deflateParams() is used to later switch to a non-zero compression 1633313796Sdelphij * level, s->matches (otherwise unused when storing) keeps track of the number 1634313796Sdelphij * of hash table slides to perform. If s->matches is 1, then one hash table 1635313796Sdelphij * slide will be done when switching. If s->matches is 2, the maximum value 1636313796Sdelphij * allowed here, then the hash table will be cleared, since two or more slides 1637313796Sdelphij * is the same as a clear. 1638313796Sdelphij * 1639313796Sdelphij * deflate_stored() is written to minimize the number of times an input byte is 1640313796Sdelphij * copied. It is most efficient with large input and output buffers, which 1641313796Sdelphij * maximizes the opportunites to have a single copy from next_in to next_out. 164217651Speter */ 164317651Speterlocal block_state deflate_stored(s, flush) 164417651Speter deflate_state *s; 164517651Speter int flush; 164617651Speter{ 1647313796Sdelphij /* Smallest worthy block size when not flushing or finishing. By default 1648313796Sdelphij * this is 32K. This can be as small as 507 bytes for memLevel == 1. For 1649313796Sdelphij * large input and output buffers, the stored block size will be larger. 165033904Ssteve */ 1651313796Sdelphij unsigned min_block = MIN(s->pending_buf_size - 5, s->w_size); 165233904Ssteve 1653313796Sdelphij /* Copy as many min_block or larger stored blocks directly to next_out as 1654313796Sdelphij * possible. If flushing, copy the remaining available input to next_out as 1655313796Sdelphij * stored blocks, if there is enough space. 1656313796Sdelphij */ 1657313796Sdelphij unsigned len, left, have, last = 0; 1658313796Sdelphij unsigned used = s->strm->avail_in; 1659313796Sdelphij do { 1660313796Sdelphij /* Set len to the maximum size block that we can copy directly with the 1661313796Sdelphij * available input data and output space. Set left to how much of that 1662313796Sdelphij * would be copied from what's left in the window. 1663313796Sdelphij */ 1664313796Sdelphij len = MAX_STORED; /* maximum deflate stored block length */ 1665313796Sdelphij have = (s->bi_valid + 42) >> 3; /* number of header bytes */ 1666313796Sdelphij if (s->strm->avail_out < have) /* need room for header */ 1667313796Sdelphij break; 1668313796Sdelphij /* maximum stored block length that will fit in avail_out: */ 1669313796Sdelphij have = s->strm->avail_out - have; 1670313796Sdelphij left = s->strstart - s->block_start; /* bytes left in window */ 1671313796Sdelphij if (len > (ulg)left + s->strm->avail_in) 1672313796Sdelphij len = left + s->strm->avail_in; /* limit len to the input */ 1673313796Sdelphij if (len > have) 1674313796Sdelphij len = have; /* limit len to the output */ 167533904Ssteve 1676313796Sdelphij /* If the stored block would be less than min_block in length, or if 1677313796Sdelphij * unable to copy all of the available input when flushing, then try 1678313796Sdelphij * copying to the window and the pending buffer instead. Also don't 1679313796Sdelphij * write an empty block when flushing -- deflate() does that. 1680313796Sdelphij */ 1681313796Sdelphij if (len < min_block && ((len == 0 && flush != Z_FINISH) || 1682313796Sdelphij flush == Z_NO_FLUSH || 1683313796Sdelphij len != left + s->strm->avail_in)) 1684313796Sdelphij break; 168517651Speter 1686313796Sdelphij /* Make a dummy stored block in pending to get the header bytes, 1687313796Sdelphij * including any pending bits. This also updates the debugging counts. 1688313796Sdelphij */ 1689313796Sdelphij last = flush == Z_FINISH && len == left + s->strm->avail_in ? 1 : 0; 1690313796Sdelphij _tr_stored_block(s, (char *)0, 0L, last); 169117651Speter 1692313796Sdelphij /* Replace the lengths in the dummy stored block with len. */ 1693313796Sdelphij s->pending_buf[s->pending - 4] = len; 1694313796Sdelphij s->pending_buf[s->pending - 3] = len >> 8; 1695313796Sdelphij s->pending_buf[s->pending - 2] = ~len; 1696313796Sdelphij s->pending_buf[s->pending - 1] = ~len >> 8; 169717651Speter 1698313796Sdelphij /* Write the stored block header bytes. */ 1699313796Sdelphij flush_pending(s->strm); 170017651Speter 1701313796Sdelphij#ifdef ZLIB_DEBUG 1702313796Sdelphij /* Update debugging counts for the data about to be copied. */ 1703313796Sdelphij s->compressed_len += len << 3; 1704313796Sdelphij s->bits_sent += len << 3; 1705313796Sdelphij#endif 170617651Speter 1707313796Sdelphij /* Copy uncompressed bytes from the window to next_out. */ 1708313796Sdelphij if (left) { 1709313796Sdelphij if (left > len) 1710313796Sdelphij left = len; 1711313796Sdelphij zmemcpy(s->strm->next_out, s->window + s->block_start, left); 1712313796Sdelphij s->strm->next_out += left; 1713313796Sdelphij s->strm->avail_out -= left; 1714313796Sdelphij s->strm->total_out += left; 1715313796Sdelphij s->block_start += left; 1716313796Sdelphij len -= left; 1717131377Stjr } 1718313796Sdelphij 1719313796Sdelphij /* Copy uncompressed bytes directly from next_in to next_out, updating 1720313796Sdelphij * the check value. 172133904Ssteve */ 1722313796Sdelphij if (len) { 1723313796Sdelphij read_buf(s->strm, s->strm->next_out, len); 1724313796Sdelphij s->strm->next_out += len; 1725313796Sdelphij s->strm->avail_out -= len; 1726313796Sdelphij s->strm->total_out += len; 1727131377Stjr } 1728313796Sdelphij } while (last == 0); 1729313796Sdelphij 1730313796Sdelphij /* Update the sliding window with the last s->w_size bytes of the copied 1731313796Sdelphij * data, or append all of the copied data to the existing window if less 1732313796Sdelphij * than s->w_size bytes were copied. Also update the number of bytes to 1733313796Sdelphij * insert in the hash tables, in the event that deflateParams() switches to 1734313796Sdelphij * a non-zero compression level. 1735313796Sdelphij */ 1736313796Sdelphij used -= s->strm->avail_in; /* number of input bytes directly copied */ 1737313796Sdelphij if (used) { 1738313796Sdelphij /* If any input was used, then no unused input remains in the window, 1739313796Sdelphij * therefore s->block_start == s->strstart. 1740313796Sdelphij */ 1741313796Sdelphij if (used >= s->w_size) { /* supplant the previous history */ 1742313796Sdelphij s->matches = 2; /* clear hash */ 1743313796Sdelphij zmemcpy(s->window, s->strm->next_in - s->w_size, s->w_size); 1744313796Sdelphij s->strstart = s->w_size; 1745313796Sdelphij } 1746313796Sdelphij else { 1747313796Sdelphij if (s->window_size - s->strstart <= used) { 1748313796Sdelphij /* Slide the window down. */ 1749313796Sdelphij s->strstart -= s->w_size; 1750313796Sdelphij zmemcpy(s->window, s->window + s->w_size, s->strstart); 1751313796Sdelphij if (s->matches < 2) 1752313796Sdelphij s->matches++; /* add a pending slide_hash() */ 1753313796Sdelphij } 1754313796Sdelphij zmemcpy(s->window + s->strstart, s->strm->next_in - used, used); 1755313796Sdelphij s->strstart += used; 1756313796Sdelphij } 1757313796Sdelphij s->block_start = s->strstart; 1758313796Sdelphij s->insert += MIN(used, s->w_size - s->insert); 175917651Speter } 1760313796Sdelphij if (s->high_water < s->strstart) 1761313796Sdelphij s->high_water = s->strstart; 1762313796Sdelphij 1763313796Sdelphij /* If the last block was written to next_out, then done. */ 1764313796Sdelphij if (last) 1765230837Sdelphij return finish_done; 1766313796Sdelphij 1767313796Sdelphij /* If flushing and all input has been consumed, then done. */ 1768313796Sdelphij if (flush != Z_NO_FLUSH && flush != Z_FINISH && 1769313796Sdelphij s->strm->avail_in == 0 && (long)s->strstart == s->block_start) 1770313796Sdelphij return block_done; 1771313796Sdelphij 1772313796Sdelphij /* Fill the window with any remaining input. */ 1773313796Sdelphij have = s->window_size - s->strstart - 1; 1774313796Sdelphij if (s->strm->avail_in > have && s->block_start >= (long)s->w_size) { 1775313796Sdelphij /* Slide the window down. */ 1776313796Sdelphij s->block_start -= s->w_size; 1777313796Sdelphij s->strstart -= s->w_size; 1778313796Sdelphij zmemcpy(s->window, s->window + s->w_size, s->strstart); 1779313796Sdelphij if (s->matches < 2) 1780313796Sdelphij s->matches++; /* add a pending slide_hash() */ 1781313796Sdelphij have += s->w_size; /* more space now */ 1782230837Sdelphij } 1783313796Sdelphij if (have > s->strm->avail_in) 1784313796Sdelphij have = s->strm->avail_in; 1785313796Sdelphij if (have) { 1786313796Sdelphij read_buf(s->strm, s->window + s->strstart, have); 1787313796Sdelphij s->strstart += have; 1788313796Sdelphij } 1789313796Sdelphij if (s->high_water < s->strstart) 1790313796Sdelphij s->high_water = s->strstart; 1791313796Sdelphij 1792313796Sdelphij /* There was not enough avail_out to write a complete worthy or flushed 1793313796Sdelphij * stored block to next_out. Write a stored block to pending instead, if we 1794313796Sdelphij * have enough input for a worthy block, or if flushing and there is enough 1795313796Sdelphij * room for the remaining input as a stored block in the pending buffer. 1796313796Sdelphij */ 1797313796Sdelphij have = (s->bi_valid + 42) >> 3; /* number of header bytes */ 1798313796Sdelphij /* maximum stored block length that will fit in pending: */ 1799313796Sdelphij have = MIN(s->pending_buf_size - have, MAX_STORED); 1800313796Sdelphij min_block = MIN(have, s->w_size); 1801313796Sdelphij left = s->strstart - s->block_start; 1802313796Sdelphij if (left >= min_block || 1803313796Sdelphij ((left || flush == Z_FINISH) && flush != Z_NO_FLUSH && 1804313796Sdelphij s->strm->avail_in == 0 && left <= have)) { 1805313796Sdelphij len = MIN(left, have); 1806313796Sdelphij last = flush == Z_FINISH && s->strm->avail_in == 0 && 1807313796Sdelphij len == left ? 1 : 0; 1808313796Sdelphij _tr_stored_block(s, (charf *)s->window + s->block_start, len, last); 1809313796Sdelphij s->block_start += len; 1810313796Sdelphij flush_pending(s->strm); 1811313796Sdelphij } 1812313796Sdelphij 1813313796Sdelphij /* We've done all we can with the available input and output. */ 1814313796Sdelphij return last ? finish_started : need_more; 181517651Speter} 181617651Speter 181717651Speter/* =========================================================================== 181817651Speter * Compress as much as possible from the input stream, return the current 181917651Speter * block state. 182017651Speter * This function does not perform lazy evaluation of matches and inserts 182117651Speter * new strings in the dictionary only for unmatched strings or for short 182217651Speter * matches. It is used only for the fast compression options. 182317651Speter */ 182417651Speterlocal block_state deflate_fast(s, flush) 182517651Speter deflate_state *s; 182617651Speter int flush; 182717651Speter{ 1828205194Sdelphij IPos hash_head; /* head of the hash chain */ 182917651Speter int bflush; /* set if current block must be flushed */ 183017651Speter 183117651Speter for (;;) { 183217651Speter /* Make sure that we always have enough lookahead, except 183317651Speter * at the end of the input file. We need MAX_MATCH bytes 183417651Speter * for the next match, plus MIN_MATCH bytes to insert the 183517651Speter * string following the next match. 183617651Speter */ 183717651Speter if (s->lookahead < MIN_LOOKAHEAD) { 183817651Speter fill_window(s); 183917651Speter if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { 1840131377Stjr return need_more; 1841131377Stjr } 184217651Speter if (s->lookahead == 0) break; /* flush the current block */ 184317651Speter } 184417651Speter 184517651Speter /* Insert the string window[strstart .. strstart+2] in the 184617651Speter * dictionary, and set hash_head to the head of the hash chain: 184717651Speter */ 1848205194Sdelphij hash_head = NIL; 184917651Speter if (s->lookahead >= MIN_MATCH) { 185017651Speter INSERT_STRING(s, s->strstart, hash_head); 185117651Speter } 185217651Speter 185317651Speter /* Find the longest match, discarding those <= prev_length. 185417651Speter * At this point we have always match_length < MIN_MATCH 185517651Speter */ 185617651Speter if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) { 185717651Speter /* To simplify the code, we prevent matches with the string 185817651Speter * of window index 0 (in particular we have to avoid a match 185917651Speter * of the string with itself at the start of the input file). 186017651Speter */ 1861205194Sdelphij s->match_length = longest_match (s, hash_head); 1862205194Sdelphij /* longest_match() sets match_start */ 186317651Speter } 186417651Speter if (s->match_length >= MIN_MATCH) { 186517651Speter check_match(s, s->strstart, s->match_start, s->match_length); 186617651Speter 186733904Ssteve _tr_tally_dist(s, s->strstart - s->match_start, 186833904Ssteve s->match_length - MIN_MATCH, bflush); 186917651Speter 187017651Speter s->lookahead -= s->match_length; 187117651Speter 187217651Speter /* Insert new strings in the hash table only if the match length 187317651Speter * is not too large. This saves time but degrades compression. 187417651Speter */ 187533904Ssteve#ifndef FASTEST 187617651Speter if (s->match_length <= s->max_insert_length && 187717651Speter s->lookahead >= MIN_MATCH) { 1878131377Stjr s->match_length--; /* string at strstart already in table */ 187917651Speter do { 188017651Speter s->strstart++; 188117651Speter INSERT_STRING(s, s->strstart, hash_head); 188217651Speter /* strstart never exceeds WSIZE-MAX_MATCH, so there are 188317651Speter * always MIN_MATCH bytes ahead. 188417651Speter */ 188517651Speter } while (--s->match_length != 0); 1886131377Stjr s->strstart++; 188733904Ssteve } else 188833904Ssteve#endif 1889131377Stjr { 189017651Speter s->strstart += s->match_length; 189117651Speter s->match_length = 0; 189217651Speter s->ins_h = s->window[s->strstart]; 189317651Speter UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]); 189417651Speter#if MIN_MATCH != 3 189517651Speter Call UPDATE_HASH() MIN_MATCH-3 more times 189617651Speter#endif 189717651Speter /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not 189817651Speter * matter since it will be recomputed at next deflate call. 189917651Speter */ 190017651Speter } 190117651Speter } else { 190217651Speter /* No match, output a literal byte */ 190317651Speter Tracevv((stderr,"%c", s->window[s->strstart])); 190433904Ssteve _tr_tally_lit (s, s->window[s->strstart], bflush); 190517651Speter s->lookahead--; 1906131377Stjr s->strstart++; 190717651Speter } 190817651Speter if (bflush) FLUSH_BLOCK(s, 0); 190917651Speter } 1910230837Sdelphij s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1; 1911230837Sdelphij if (flush == Z_FINISH) { 1912230837Sdelphij FLUSH_BLOCK(s, 1); 1913230837Sdelphij return finish_done; 1914230837Sdelphij } 1915230837Sdelphij if (s->last_lit) 1916230837Sdelphij FLUSH_BLOCK(s, 0); 1917230837Sdelphij return block_done; 191817651Speter} 191917651Speter 1920131377Stjr#ifndef FASTEST 192117651Speter/* =========================================================================== 192217651Speter * Same as above, but achieves better compression. We use a lazy 192317651Speter * evaluation for matches: a match is finally adopted only if there is 192417651Speter * no better match at the next window position. 192517651Speter */ 192617651Speterlocal block_state deflate_slow(s, flush) 192717651Speter deflate_state *s; 192817651Speter int flush; 192917651Speter{ 1930205194Sdelphij IPos hash_head; /* head of hash chain */ 193117651Speter int bflush; /* set if current block must be flushed */ 193217651Speter 193317651Speter /* Process the input block. */ 193417651Speter for (;;) { 193517651Speter /* Make sure that we always have enough lookahead, except 193617651Speter * at the end of the input file. We need MAX_MATCH bytes 193717651Speter * for the next match, plus MIN_MATCH bytes to insert the 193817651Speter * string following the next match. 193917651Speter */ 194017651Speter if (s->lookahead < MIN_LOOKAHEAD) { 194117651Speter fill_window(s); 194217651Speter if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { 1943131377Stjr return need_more; 1944131377Stjr } 194517651Speter if (s->lookahead == 0) break; /* flush the current block */ 194617651Speter } 194717651Speter 194817651Speter /* Insert the string window[strstart .. strstart+2] in the 194917651Speter * dictionary, and set hash_head to the head of the hash chain: 195017651Speter */ 1951205194Sdelphij hash_head = NIL; 195217651Speter if (s->lookahead >= MIN_MATCH) { 195317651Speter INSERT_STRING(s, s->strstart, hash_head); 195417651Speter } 195517651Speter 195617651Speter /* Find the longest match, discarding those <= prev_length. 195717651Speter */ 195817651Speter s->prev_length = s->match_length, s->prev_match = s->match_start; 195917651Speter s->match_length = MIN_MATCH-1; 196017651Speter 196117651Speter if (hash_head != NIL && s->prev_length < s->max_lazy_match && 196217651Speter s->strstart - hash_head <= MAX_DIST(s)) { 196317651Speter /* To simplify the code, we prevent matches with the string 196417651Speter * of window index 0 (in particular we have to avoid a match 196517651Speter * of the string with itself at the start of the input file). 196617651Speter */ 1967205194Sdelphij s->match_length = longest_match (s, hash_head); 1968205194Sdelphij /* longest_match() sets match_start */ 196917651Speter 1970131377Stjr if (s->match_length <= 5 && (s->strategy == Z_FILTERED 1971131377Stjr#if TOO_FAR <= 32767 1972131377Stjr || (s->match_length == MIN_MATCH && 1973131377Stjr s->strstart - s->match_start > TOO_FAR) 1974131377Stjr#endif 1975131377Stjr )) { 197617651Speter 197717651Speter /* If prev_match is also MIN_MATCH, match_start is garbage 197817651Speter * but we will ignore the current match anyway. 197917651Speter */ 198017651Speter s->match_length = MIN_MATCH-1; 198117651Speter } 198217651Speter } 198317651Speter /* If there was a match at the previous step and the current 198417651Speter * match is not better, output the previous match: 198517651Speter */ 198617651Speter if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) { 198717651Speter uInt max_insert = s->strstart + s->lookahead - MIN_MATCH; 198817651Speter /* Do not insert strings in hash table beyond this. */ 198917651Speter 199017651Speter check_match(s, s->strstart-1, s->prev_match, s->prev_length); 199117651Speter 199233904Ssteve _tr_tally_dist(s, s->strstart -1 - s->prev_match, 1993131377Stjr s->prev_length - MIN_MATCH, bflush); 199417651Speter 199517651Speter /* Insert in hash table all strings up to the end of the match. 199617651Speter * strstart-1 and strstart are already inserted. If there is not 199717651Speter * enough lookahead, the last two strings are not inserted in 199817651Speter * the hash table. 199917651Speter */ 200017651Speter s->lookahead -= s->prev_length-1; 200117651Speter s->prev_length -= 2; 200217651Speter do { 200317651Speter if (++s->strstart <= max_insert) { 200417651Speter INSERT_STRING(s, s->strstart, hash_head); 200517651Speter } 200617651Speter } while (--s->prev_length != 0); 200717651Speter s->match_available = 0; 200817651Speter s->match_length = MIN_MATCH-1; 200917651Speter s->strstart++; 201017651Speter 201117651Speter if (bflush) FLUSH_BLOCK(s, 0); 201217651Speter 201317651Speter } else if (s->match_available) { 201417651Speter /* If there was no match at the previous position, output a 201517651Speter * single literal. If there was a match but the current match 201617651Speter * is longer, truncate the previous match to a single literal. 201717651Speter */ 201817651Speter Tracevv((stderr,"%c", s->window[s->strstart-1])); 2019131377Stjr _tr_tally_lit(s, s->window[s->strstart-1], bflush); 2020131377Stjr if (bflush) { 202117651Speter FLUSH_BLOCK_ONLY(s, 0); 202217651Speter } 202317651Speter s->strstart++; 202417651Speter s->lookahead--; 202517651Speter if (s->strm->avail_out == 0) return need_more; 202617651Speter } else { 202717651Speter /* There is no previous match to compare with, wait for 202817651Speter * the next step to decide. 202917651Speter */ 203017651Speter s->match_available = 1; 203117651Speter s->strstart++; 203217651Speter s->lookahead--; 203317651Speter } 203417651Speter } 203517651Speter Assert (flush != Z_NO_FLUSH, "no flush?"); 203617651Speter if (s->match_available) { 203717651Speter Tracevv((stderr,"%c", s->window[s->strstart-1])); 203833904Ssteve _tr_tally_lit(s, s->window[s->strstart-1], bflush); 203917651Speter s->match_available = 0; 204017651Speter } 2041230837Sdelphij s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1; 2042230837Sdelphij if (flush == Z_FINISH) { 2043230837Sdelphij FLUSH_BLOCK(s, 1); 2044230837Sdelphij return finish_done; 2045230837Sdelphij } 2046230837Sdelphij if (s->last_lit) 2047230837Sdelphij FLUSH_BLOCK(s, 0); 2048230837Sdelphij return block_done; 204917651Speter} 2050131377Stjr#endif /* FASTEST */ 2051157043Sdes 2052157043Sdes/* =========================================================================== 2053157043Sdes * For Z_RLE, simply look for runs of bytes, generate matches only of distance 2054157043Sdes * one. Do not maintain a hash table. (It will be regenerated if this run of 2055157043Sdes * deflate switches away from Z_RLE.) 2056157043Sdes */ 2057157043Sdeslocal block_state deflate_rle(s, flush) 2058157043Sdes deflate_state *s; 2059157043Sdes int flush; 2060157043Sdes{ 2061205194Sdelphij int bflush; /* set if current block must be flushed */ 2062205194Sdelphij uInt prev; /* byte at distance one to match */ 2063205194Sdelphij Bytef *scan, *strend; /* scan goes up to strend for length of run */ 2064157043Sdes 2065157043Sdes for (;;) { 2066157043Sdes /* Make sure that we always have enough lookahead, except 2067157043Sdes * at the end of the input file. We need MAX_MATCH bytes 2068230837Sdelphij * for the longest run, plus one for the unrolled loop. 2069157043Sdes */ 2070230837Sdelphij if (s->lookahead <= MAX_MATCH) { 2071157043Sdes fill_window(s); 2072230837Sdelphij if (s->lookahead <= MAX_MATCH && flush == Z_NO_FLUSH) { 2073157043Sdes return need_more; 2074157043Sdes } 2075157043Sdes if (s->lookahead == 0) break; /* flush the current block */ 2076157043Sdes } 2077157043Sdes 2078157043Sdes /* See how many times the previous byte repeats */ 2079205194Sdelphij s->match_length = 0; 2080205194Sdelphij if (s->lookahead >= MIN_MATCH && s->strstart > 0) { 2081157043Sdes scan = s->window + s->strstart - 1; 2082205194Sdelphij prev = *scan; 2083205194Sdelphij if (prev == *++scan && prev == *++scan && prev == *++scan) { 2084205194Sdelphij strend = s->window + s->strstart + MAX_MATCH; 2085205194Sdelphij do { 2086205194Sdelphij } while (prev == *++scan && prev == *++scan && 2087205194Sdelphij prev == *++scan && prev == *++scan && 2088205194Sdelphij prev == *++scan && prev == *++scan && 2089205194Sdelphij prev == *++scan && prev == *++scan && 2090205194Sdelphij scan < strend); 2091313796Sdelphij s->match_length = MAX_MATCH - (uInt)(strend - scan); 2092205194Sdelphij if (s->match_length > s->lookahead) 2093205194Sdelphij s->match_length = s->lookahead; 2094205194Sdelphij } 2095230837Sdelphij Assert(scan <= s->window+(uInt)(s->window_size-1), "wild scan"); 2096157043Sdes } 2097157043Sdes 2098157043Sdes /* Emit match if have run of MIN_MATCH or longer, else emit literal */ 2099205194Sdelphij if (s->match_length >= MIN_MATCH) { 2100205194Sdelphij check_match(s, s->strstart, s->strstart - 1, s->match_length); 2101205194Sdelphij 2102205194Sdelphij _tr_tally_dist(s, 1, s->match_length - MIN_MATCH, bflush); 2103205194Sdelphij 2104205194Sdelphij s->lookahead -= s->match_length; 2105205194Sdelphij s->strstart += s->match_length; 2106205194Sdelphij s->match_length = 0; 2107157043Sdes } else { 2108157043Sdes /* No match, output a literal byte */ 2109157043Sdes Tracevv((stderr,"%c", s->window[s->strstart])); 2110157043Sdes _tr_tally_lit (s, s->window[s->strstart], bflush); 2111157043Sdes s->lookahead--; 2112157043Sdes s->strstart++; 2113157043Sdes } 2114157043Sdes if (bflush) FLUSH_BLOCK(s, 0); 2115157043Sdes } 2116230837Sdelphij s->insert = 0; 2117230837Sdelphij if (flush == Z_FINISH) { 2118230837Sdelphij FLUSH_BLOCK(s, 1); 2119230837Sdelphij return finish_done; 2120230837Sdelphij } 2121230837Sdelphij if (s->last_lit) 2122230837Sdelphij FLUSH_BLOCK(s, 0); 2123230837Sdelphij return block_done; 2124157043Sdes} 2125205194Sdelphij 2126205194Sdelphij/* =========================================================================== 2127205194Sdelphij * For Z_HUFFMAN_ONLY, do not look for matches. Do not maintain a hash table. 2128205194Sdelphij * (It will be regenerated if this run of deflate switches away from Huffman.) 2129205194Sdelphij */ 2130205194Sdelphijlocal block_state deflate_huff(s, flush) 2131205194Sdelphij deflate_state *s; 2132205194Sdelphij int flush; 2133205194Sdelphij{ 2134205194Sdelphij int bflush; /* set if current block must be flushed */ 2135205194Sdelphij 2136205194Sdelphij for (;;) { 2137205194Sdelphij /* Make sure that we have a literal to write. */ 2138205194Sdelphij if (s->lookahead == 0) { 2139205194Sdelphij fill_window(s); 2140205194Sdelphij if (s->lookahead == 0) { 2141205194Sdelphij if (flush == Z_NO_FLUSH) 2142205194Sdelphij return need_more; 2143205194Sdelphij break; /* flush the current block */ 2144205194Sdelphij } 2145205194Sdelphij } 2146205194Sdelphij 2147205194Sdelphij /* Output a literal byte */ 2148205194Sdelphij s->match_length = 0; 2149205194Sdelphij Tracevv((stderr,"%c", s->window[s->strstart])); 2150205194Sdelphij _tr_tally_lit (s, s->window[s->strstart], bflush); 2151205194Sdelphij s->lookahead--; 2152205194Sdelphij s->strstart++; 2153205194Sdelphij if (bflush) FLUSH_BLOCK(s, 0); 2154205194Sdelphij } 2155230837Sdelphij s->insert = 0; 2156230837Sdelphij if (flush == Z_FINISH) { 2157230837Sdelphij FLUSH_BLOCK(s, 1); 2158230837Sdelphij return finish_done; 2159230837Sdelphij } 2160230837Sdelphij if (s->last_lit) 2161230837Sdelphij FLUSH_BLOCK(s, 0); 2162230837Sdelphij return block_done; 2163205194Sdelphij} 2164