deflate.c revision 33908
117651Speter/* deflate.c -- compress data using the deflation algorithm 233908Ssteve * Copyright (C) 1995-1998 Jean-loup Gailly. 317651Speter * For conditions of distribution and use, see copyright notice in zlib.h 417651Speter */ 517651Speter 617651Speter/* 717651Speter * ALGORITHM 817651Speter * 917651Speter * The "deflation" process depends on being able to identify portions 1017651Speter * of the input text which are identical to earlier input (within a 1117651Speter * sliding window trailing behind the input currently being processed). 1217651Speter * 1317651Speter * The most straightforward technique turns out to be the fastest for 1417651Speter * most input files: try all possible matches and select the longest. 1517651Speter * The key feature of this algorithm is that insertions into the string 1617651Speter * dictionary are very simple and thus fast, and deletions are avoided 1717651Speter * completely. Insertions are performed at each input character, whereas 1817651Speter * string matches are performed only when the previous match ends. So it 1917651Speter * is preferable to spend more time in matches to allow very fast string 2017651Speter * insertions and avoid deletions. The matching algorithm for small 2117651Speter * strings is inspired from that of Rabin & Karp. A brute force approach 2217651Speter * is used to find longer strings when a small match has been found. 2317651Speter * A similar algorithm is used in comic (by Jan-Mark Wams) and freeze 2417651Speter * (by Leonid Broukhis). 2517651Speter * A previous version of this file used a more sophisticated algorithm 2617651Speter * (by Fiala and Greene) which is guaranteed to run in linear amortized 2717651Speter * time, but has a larger average cost, uses more memory and is patented. 2817651Speter * However the F&G algorithm may be faster for some highly redundant 2917651Speter * files if the parameter max_chain_length (described below) is too large. 3017651Speter * 3117651Speter * ACKNOWLEDGEMENTS 3217651Speter * 3317651Speter * The idea of lazy evaluation of matches is due to Jan-Mark Wams, and 3417651Speter * I found it in 'freeze' written by Leonid Broukhis. 3517651Speter * Thanks to many people for bug reports and testing. 3617651Speter * 3717651Speter * REFERENCES 3817651Speter * 3933908Ssteve * Deutsch, L.P.,"DEFLATE Compressed Data Format Specification". 4033908Ssteve * Available in ftp://ds.internic.net/rfc/rfc1951.txt 4117651Speter * 4217651Speter * A description of the Rabin and Karp algorithm is given in the book 4317651Speter * "Algorithms" by R. Sedgewick, Addison-Wesley, p252. 4417651Speter * 4517651Speter * Fiala,E.R., and Greene,D.H. 4617651Speter * Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595 4717651Speter * 4817651Speter */ 4917651Speter 5021673Sjkh/* $FreeBSD: head/lib/libz/deflate.c 33908 1998-02-28 06:08:17Z steve $ */ 5117651Speter 5217651Speter#include "deflate.h" 5317651Speter 5433908Ssteveconst char deflate_copyright[] = 5533908Ssteve " deflate 1.1.1 Copyright 1995-1998 Jean-loup Gailly "; 5617651Speter/* 5717651Speter If you use the zlib library in a product, an acknowledgment is welcome 5817651Speter in the documentation of your product. If for some reason you cannot 5917651Speter include such an acknowledgment, I would appreciate that you keep this 6017651Speter copyright string in the executable of your product. 6117651Speter */ 6217651Speter 6317651Speter/* =========================================================================== 6417651Speter * Function prototypes. 6517651Speter */ 6617651Spetertypedef enum { 6717651Speter need_more, /* block not completed, need more input or more output */ 6817651Speter block_done, /* block flush performed */ 6917651Speter finish_started, /* finish started, need only more output at next deflate */ 7017651Speter finish_done /* finish done, accept no more input or output */ 7117651Speter} block_state; 7217651Speter 7317651Spetertypedef block_state (*compress_func) OF((deflate_state *s, int flush)); 7417651Speter/* Compression function. Returns the block state after the call. */ 7517651Speter 7617651Speterlocal void fill_window OF((deflate_state *s)); 7717651Speterlocal block_state deflate_stored OF((deflate_state *s, int flush)); 7817651Speterlocal block_state deflate_fast OF((deflate_state *s, int flush)); 7917651Speterlocal block_state deflate_slow OF((deflate_state *s, int flush)); 8017651Speterlocal void lm_init OF((deflate_state *s)); 8117651Speterlocal void putShortMSB OF((deflate_state *s, uInt b)); 8217651Speterlocal void flush_pending OF((z_streamp strm)); 8333908Sstevelocal int read_buf OF((z_streamp strm, Bytef *buf, unsigned size)); 8417651Speter#ifdef ASMV 8517651Speter void match_init OF((void)); /* asm code initialization */ 8633908Ssteve uInt longest_match OF((deflate_state *s, IPos cur_match)); 8733908Ssteve#else 8833908Sstevelocal uInt longest_match OF((deflate_state *s, IPos cur_match)); 8917651Speter#endif 9017651Speter 9117651Speter#ifdef DEBUG 9217651Speterlocal void check_match OF((deflate_state *s, IPos start, IPos match, 9317651Speter int length)); 9417651Speter#endif 9517651Speter 9617651Speter/* =========================================================================== 9717651Speter * Local data 9817651Speter */ 9917651Speter 10017651Speter#define NIL 0 10117651Speter/* Tail of hash chains */ 10217651Speter 10317651Speter#ifndef TOO_FAR 10417651Speter# define TOO_FAR 4096 10517651Speter#endif 10617651Speter/* Matches of length 3 are discarded if their distance exceeds TOO_FAR */ 10717651Speter 10817651Speter#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1) 10917651Speter/* Minimum amount of lookahead, except at the end of the input file. 11017651Speter * See deflate.c for comments about the MIN_MATCH+1. 11117651Speter */ 11217651Speter 11317651Speter/* Values for max_lazy_match, good_match and max_chain_length, depending on 11417651Speter * the desired pack level (0..9). The values given below have been tuned to 11517651Speter * exclude worst case performance for pathological files. Better values may be 11617651Speter * found for specific files. 11717651Speter */ 11817651Spetertypedef struct config_s { 11917651Speter ush good_length; /* reduce lazy search above this match length */ 12017651Speter ush max_lazy; /* do not perform lazy search above this match length */ 12117651Speter ush nice_length; /* quit search above this match length */ 12217651Speter ush max_chain; 12317651Speter compress_func func; 12417651Speter} config; 12517651Speter 12633908Sstevelocal const config configuration_table[10] = { 12717651Speter/* good lazy nice chain */ 12817651Speter/* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */ 12917651Speter/* 1 */ {4, 4, 8, 4, deflate_fast}, /* maximum speed, no lazy matches */ 13017651Speter/* 2 */ {4, 5, 16, 8, deflate_fast}, 13117651Speter/* 3 */ {4, 6, 32, 32, deflate_fast}, 13217651Speter 13317651Speter/* 4 */ {4, 4, 16, 16, deflate_slow}, /* lazy matches */ 13417651Speter/* 5 */ {8, 16, 32, 32, deflate_slow}, 13517651Speter/* 6 */ {8, 16, 128, 128, deflate_slow}, 13617651Speter/* 7 */ {8, 32, 128, 256, deflate_slow}, 13717651Speter/* 8 */ {32, 128, 258, 1024, deflate_slow}, 13817651Speter/* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* maximum compression */ 13917651Speter 14017651Speter/* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4 14117651Speter * For deflate_fast() (levels <= 3) good is ignored and lazy has a different 14217651Speter * meaning. 14317651Speter */ 14417651Speter 14517651Speter#define EQUAL 0 14617651Speter/* result of memcmp for equal strings */ 14717651Speter 14817651Speterstruct static_tree_desc_s {int dummy;}; /* for buggy compilers */ 14917651Speter 15017651Speter/* =========================================================================== 15117651Speter * Update a hash value with the given input byte 15217651Speter * IN assertion: all calls to to UPDATE_HASH are made with consecutive 15317651Speter * input characters, so that a running hash key can be computed from the 15417651Speter * previous key instead of complete recalculation each time. 15517651Speter */ 15617651Speter#define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask) 15717651Speter 15817651Speter 15917651Speter/* =========================================================================== 16017651Speter * Insert string str in the dictionary and set match_head to the previous head 16117651Speter * of the hash chain (the most recent string with same hash key). Return 16217651Speter * the previous length of the hash chain. 16333908Ssteve * If this file is compiled with -DFASTEST, the compression level is forced 16433908Ssteve * to 1, and no hash chains are maintained. 16517651Speter * IN assertion: all calls to to INSERT_STRING are made with consecutive 16617651Speter * input characters and the first MIN_MATCH bytes of str are valid 16717651Speter * (except for the last MIN_MATCH-1 bytes of the input file). 16817651Speter */ 16933908Ssteve#ifdef FASTEST 17017651Speter#define INSERT_STRING(s, str, match_head) \ 17117651Speter (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \ 17233908Ssteve match_head = s->head[s->ins_h], \ 17333908Ssteve s->head[s->ins_h] = (Pos)(str)) 17433908Ssteve#else 17533908Ssteve#define INSERT_STRING(s, str, match_head) \ 17633908Ssteve (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \ 17717651Speter s->prev[(str) & s->w_mask] = match_head = s->head[s->ins_h], \ 17817651Speter s->head[s->ins_h] = (Pos)(str)) 17933908Ssteve#endif 18017651Speter 18117651Speter/* =========================================================================== 18217651Speter * Initialize the hash table (avoiding 64K overflow for 16 bit systems). 18317651Speter * prev[] will be initialized on the fly. 18417651Speter */ 18517651Speter#define CLEAR_HASH(s) \ 18617651Speter s->head[s->hash_size-1] = NIL; \ 18733908Ssteve zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head)); 18817651Speter 18917651Speter/* ========================================================================= */ 19033908Ssteveint ZEXPORT deflateInit_(strm, level, version, stream_size) 19117651Speter z_streamp strm; 19217651Speter int level; 19317651Speter const char *version; 19417651Speter int stream_size; 19517651Speter{ 19617651Speter return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL, 19717651Speter Z_DEFAULT_STRATEGY, version, stream_size); 19817651Speter /* To do: ignore strm->next_in if we use it as window */ 19917651Speter} 20017651Speter 20117651Speter/* ========================================================================= */ 20233908Ssteveint ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy, 20317651Speter version, stream_size) 20417651Speter z_streamp strm; 20517651Speter int level; 20617651Speter int method; 20717651Speter int windowBits; 20817651Speter int memLevel; 20917651Speter int strategy; 21017651Speter const char *version; 21117651Speter int stream_size; 21217651Speter{ 21317651Speter deflate_state *s; 21417651Speter int noheader = 0; 21533908Ssteve static const char* my_version = ZLIB_VERSION; 21617651Speter 21717651Speter ushf *overlay; 21817651Speter /* We overlay pending_buf and d_buf+l_buf. This works since the average 21917651Speter * output size for (length,distance) codes is <= 24 bits. 22017651Speter */ 22117651Speter 22233908Ssteve if (version == Z_NULL || version[0] != my_version[0] || 22317651Speter stream_size != sizeof(z_stream)) { 22417651Speter return Z_VERSION_ERROR; 22517651Speter } 22617651Speter if (strm == Z_NULL) return Z_STREAM_ERROR; 22717651Speter 22817651Speter strm->msg = Z_NULL; 22917651Speter if (strm->zalloc == Z_NULL) { 23017651Speter strm->zalloc = zcalloc; 23117651Speter strm->opaque = (voidpf)0; 23217651Speter } 23317651Speter if (strm->zfree == Z_NULL) strm->zfree = zcfree; 23417651Speter 23517651Speter if (level == Z_DEFAULT_COMPRESSION) level = 6; 23633908Ssteve#ifdef FASTEST 23733908Ssteve level = 1; 23833908Ssteve#endif 23917651Speter 24017651Speter if (windowBits < 0) { /* undocumented feature: suppress zlib header */ 24117651Speter noheader = 1; 24217651Speter windowBits = -windowBits; 24317651Speter } 24417651Speter if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED || 24517651Speter windowBits < 8 || windowBits > 15 || level < 0 || level > 9 || 24617651Speter strategy < 0 || strategy > Z_HUFFMAN_ONLY) { 24717651Speter return Z_STREAM_ERROR; 24817651Speter } 24917651Speter s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state)); 25017651Speter if (s == Z_NULL) return Z_MEM_ERROR; 25117651Speter strm->state = (struct internal_state FAR *)s; 25217651Speter s->strm = strm; 25317651Speter 25417651Speter s->noheader = noheader; 25517651Speter s->w_bits = windowBits; 25617651Speter s->w_size = 1 << s->w_bits; 25717651Speter s->w_mask = s->w_size - 1; 25817651Speter 25917651Speter s->hash_bits = memLevel + 7; 26017651Speter s->hash_size = 1 << s->hash_bits; 26117651Speter s->hash_mask = s->hash_size - 1; 26217651Speter s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH); 26317651Speter 26417651Speter s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte)); 26517651Speter s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos)); 26617651Speter s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos)); 26717651Speter 26817651Speter s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */ 26917651Speter 27017651Speter overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2); 27117651Speter s->pending_buf = (uchf *) overlay; 27233908Ssteve s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L); 27317651Speter 27417651Speter if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL || 27517651Speter s->pending_buf == Z_NULL) { 27617651Speter strm->msg = (char*)ERR_MSG(Z_MEM_ERROR); 27717651Speter deflateEnd (strm); 27817651Speter return Z_MEM_ERROR; 27917651Speter } 28017651Speter s->d_buf = overlay + s->lit_bufsize/sizeof(ush); 28117651Speter s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize; 28217651Speter 28317651Speter s->level = level; 28417651Speter s->strategy = strategy; 28517651Speter s->method = (Byte)method; 28617651Speter 28717651Speter return deflateReset(strm); 28817651Speter} 28917651Speter 29017651Speter/* ========================================================================= */ 29133908Ssteveint ZEXPORT deflateSetDictionary (strm, dictionary, dictLength) 29217651Speter z_streamp strm; 29317651Speter const Bytef *dictionary; 29417651Speter uInt dictLength; 29517651Speter{ 29617651Speter deflate_state *s; 29717651Speter uInt length = dictLength; 29817651Speter uInt n; 29917651Speter IPos hash_head = 0; 30017651Speter 30117651Speter if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL || 30217651Speter strm->state->status != INIT_STATE) return Z_STREAM_ERROR; 30317651Speter 30417651Speter s = strm->state; 30517651Speter strm->adler = adler32(strm->adler, dictionary, dictLength); 30617651Speter 30717651Speter if (length < MIN_MATCH) return Z_OK; 30817651Speter if (length > MAX_DIST(s)) { 30917651Speter length = MAX_DIST(s); 31033908Ssteve#ifndef USE_DICT_HEAD 31133908Ssteve dictionary += dictLength - length; /* use the tail of the dictionary */ 31233908Ssteve#endif 31317651Speter } 31433908Ssteve zmemcpy(s->window, dictionary, length); 31517651Speter s->strstart = length; 31617651Speter s->block_start = (long)length; 31717651Speter 31817651Speter /* Insert all strings in the hash table (except for the last two bytes). 31917651Speter * s->lookahead stays null, so s->ins_h will be recomputed at the next 32017651Speter * call of fill_window. 32117651Speter */ 32217651Speter s->ins_h = s->window[0]; 32317651Speter UPDATE_HASH(s, s->ins_h, s->window[1]); 32417651Speter for (n = 0; n <= length - MIN_MATCH; n++) { 32517651Speter INSERT_STRING(s, n, hash_head); 32617651Speter } 32717651Speter if (hash_head) hash_head = 0; /* to make compiler happy */ 32817651Speter return Z_OK; 32917651Speter} 33017651Speter 33117651Speter/* ========================================================================= */ 33233908Ssteveint ZEXPORT deflateReset (strm) 33317651Speter z_streamp strm; 33417651Speter{ 33517651Speter deflate_state *s; 33617651Speter 33717651Speter if (strm == Z_NULL || strm->state == Z_NULL || 33817651Speter strm->zalloc == Z_NULL || strm->zfree == Z_NULL) return Z_STREAM_ERROR; 33917651Speter 34017651Speter strm->total_in = strm->total_out = 0; 34117651Speter strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */ 34217651Speter strm->data_type = Z_UNKNOWN; 34317651Speter 34417651Speter s = (deflate_state *)strm->state; 34517651Speter s->pending = 0; 34617651Speter s->pending_out = s->pending_buf; 34717651Speter 34817651Speter if (s->noheader < 0) { 34917651Speter s->noheader = 0; /* was set to -1 by deflate(..., Z_FINISH); */ 35017651Speter } 35117651Speter s->status = s->noheader ? BUSY_STATE : INIT_STATE; 35217651Speter strm->adler = 1; 35317651Speter s->last_flush = Z_NO_FLUSH; 35417651Speter 35517651Speter _tr_init(s); 35617651Speter lm_init(s); 35717651Speter 35817651Speter return Z_OK; 35917651Speter} 36017651Speter 36117651Speter/* ========================================================================= */ 36233908Ssteveint ZEXPORT deflateParams(strm, level, strategy) 36317651Speter z_streamp strm; 36417651Speter int level; 36517651Speter int strategy; 36617651Speter{ 36717651Speter deflate_state *s; 36817651Speter compress_func func; 36917651Speter int err = Z_OK; 37017651Speter 37117651Speter if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 37217651Speter s = strm->state; 37317651Speter 37417651Speter if (level == Z_DEFAULT_COMPRESSION) { 37517651Speter level = 6; 37617651Speter } 37717651Speter if (level < 0 || level > 9 || strategy < 0 || strategy > Z_HUFFMAN_ONLY) { 37817651Speter return Z_STREAM_ERROR; 37917651Speter } 38017651Speter func = configuration_table[s->level].func; 38117651Speter 38217651Speter if (func != configuration_table[level].func && strm->total_in != 0) { 38317651Speter /* Flush the last buffer: */ 38417651Speter err = deflate(strm, Z_PARTIAL_FLUSH); 38517651Speter } 38617651Speter if (s->level != level) { 38717651Speter s->level = level; 38817651Speter s->max_lazy_match = configuration_table[level].max_lazy; 38917651Speter s->good_match = configuration_table[level].good_length; 39017651Speter s->nice_match = configuration_table[level].nice_length; 39117651Speter s->max_chain_length = configuration_table[level].max_chain; 39217651Speter } 39317651Speter s->strategy = strategy; 39417651Speter return err; 39517651Speter} 39617651Speter 39717651Speter/* ========================================================================= 39817651Speter * Put a short in the pending buffer. The 16-bit value is put in MSB order. 39917651Speter * IN assertion: the stream state is correct and there is enough room in 40017651Speter * pending_buf. 40117651Speter */ 40217651Speterlocal void putShortMSB (s, b) 40317651Speter deflate_state *s; 40417651Speter uInt b; 40517651Speter{ 40617651Speter put_byte(s, (Byte)(b >> 8)); 40717651Speter put_byte(s, (Byte)(b & 0xff)); 40817651Speter} 40917651Speter 41017651Speter/* ========================================================================= 41117651Speter * Flush as much pending output as possible. All deflate() output goes 41217651Speter * through this function so some applications may wish to modify it 41317651Speter * to avoid allocating a large strm->next_out buffer and copying into it. 41417651Speter * (See also read_buf()). 41517651Speter */ 41617651Speterlocal void flush_pending(strm) 41717651Speter z_streamp strm; 41817651Speter{ 41917651Speter unsigned len = strm->state->pending; 42017651Speter 42117651Speter if (len > strm->avail_out) len = strm->avail_out; 42217651Speter if (len == 0) return; 42317651Speter 42417651Speter zmemcpy(strm->next_out, strm->state->pending_out, len); 42517651Speter strm->next_out += len; 42617651Speter strm->state->pending_out += len; 42717651Speter strm->total_out += len; 42817651Speter strm->avail_out -= len; 42917651Speter strm->state->pending -= len; 43017651Speter if (strm->state->pending == 0) { 43117651Speter strm->state->pending_out = strm->state->pending_buf; 43217651Speter } 43317651Speter} 43417651Speter 43517651Speter/* ========================================================================= */ 43633908Ssteveint ZEXPORT deflate (strm, flush) 43717651Speter z_streamp strm; 43817651Speter int flush; 43917651Speter{ 44017651Speter int old_flush; /* value of flush param for previous deflate call */ 44117651Speter deflate_state *s; 44217651Speter 44317651Speter if (strm == Z_NULL || strm->state == Z_NULL || 44417651Speter flush > Z_FINISH || flush < 0) { 44517651Speter return Z_STREAM_ERROR; 44617651Speter } 44717651Speter s = strm->state; 44817651Speter 44917651Speter if (strm->next_out == Z_NULL || 45017651Speter (strm->next_in == Z_NULL && strm->avail_in != 0) || 45117651Speter (s->status == FINISH_STATE && flush != Z_FINISH)) { 45217651Speter ERR_RETURN(strm, Z_STREAM_ERROR); 45317651Speter } 45417651Speter if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR); 45517651Speter 45617651Speter s->strm = strm; /* just in case */ 45717651Speter old_flush = s->last_flush; 45817651Speter s->last_flush = flush; 45917651Speter 46017651Speter /* Write the zlib header */ 46117651Speter if (s->status == INIT_STATE) { 46217651Speter 46317651Speter uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8; 46417651Speter uInt level_flags = (s->level-1) >> 1; 46517651Speter 46617651Speter if (level_flags > 3) level_flags = 3; 46717651Speter header |= (level_flags << 6); 46817651Speter if (s->strstart != 0) header |= PRESET_DICT; 46917651Speter header += 31 - (header % 31); 47017651Speter 47117651Speter s->status = BUSY_STATE; 47217651Speter putShortMSB(s, header); 47317651Speter 47417651Speter /* Save the adler32 of the preset dictionary: */ 47517651Speter if (s->strstart != 0) { 47617651Speter putShortMSB(s, (uInt)(strm->adler >> 16)); 47717651Speter putShortMSB(s, (uInt)(strm->adler & 0xffff)); 47817651Speter } 47917651Speter strm->adler = 1L; 48017651Speter } 48117651Speter 48217651Speter /* Flush as much pending output as possible */ 48317651Speter if (s->pending != 0) { 48417651Speter flush_pending(strm); 48517651Speter if (strm->avail_out == 0) { 48617651Speter /* Since avail_out is 0, deflate will be called again with 48717651Speter * more output space, but possibly with both pending and 48817651Speter * avail_in equal to zero. There won't be anything to do, 48917651Speter * but this is not an error situation so make sure we 49017651Speter * return OK instead of BUF_ERROR at next call of deflate: 49117651Speter */ 49217651Speter s->last_flush = -1; 49317651Speter return Z_OK; 49417651Speter } 49517651Speter 49617651Speter /* Make sure there is something to do and avoid duplicate consecutive 49717651Speter * flushes. For repeated and useless calls with Z_FINISH, we keep 49817651Speter * returning Z_STREAM_END instead of Z_BUFF_ERROR. 49917651Speter */ 50017651Speter } else if (strm->avail_in == 0 && flush <= old_flush && 50117651Speter flush != Z_FINISH) { 50217651Speter ERR_RETURN(strm, Z_BUF_ERROR); 50317651Speter } 50417651Speter 50517651Speter /* User must not provide more input after the first FINISH: */ 50617651Speter if (s->status == FINISH_STATE && strm->avail_in != 0) { 50717651Speter ERR_RETURN(strm, Z_BUF_ERROR); 50817651Speter } 50917651Speter 51017651Speter /* Start a new block or continue the current one. 51117651Speter */ 51217651Speter if (strm->avail_in != 0 || s->lookahead != 0 || 51317651Speter (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) { 51417651Speter block_state bstate; 51517651Speter 51617651Speter bstate = (*(configuration_table[s->level].func))(s, flush); 51717651Speter 51817651Speter if (bstate == finish_started || bstate == finish_done) { 51917651Speter s->status = FINISH_STATE; 52017651Speter } 52117651Speter if (bstate == need_more || bstate == finish_started) { 52217651Speter if (strm->avail_out == 0) { 52317651Speter s->last_flush = -1; /* avoid BUF_ERROR next call, see above */ 52417651Speter } 52517651Speter return Z_OK; 52617651Speter /* If flush != Z_NO_FLUSH && avail_out == 0, the next call 52717651Speter * of deflate should use the same flush parameter to make sure 52817651Speter * that the flush is complete. So we don't have to output an 52917651Speter * empty block here, this will be done at next call. This also 53017651Speter * ensures that for a very small output buffer, we emit at most 53117651Speter * one empty block. 53217651Speter */ 53317651Speter } 53417651Speter if (bstate == block_done) { 53517651Speter if (flush == Z_PARTIAL_FLUSH) { 53617651Speter _tr_align(s); 53717651Speter } else { /* FULL_FLUSH or SYNC_FLUSH */ 53817651Speter _tr_stored_block(s, (char*)0, 0L, 0); 53917651Speter /* For a full flush, this empty block will be recognized 54017651Speter * as a special marker by inflate_sync(). 54117651Speter */ 54217651Speter if (flush == Z_FULL_FLUSH) { 54317651Speter CLEAR_HASH(s); /* forget history */ 54417651Speter } 54517651Speter } 54617651Speter flush_pending(strm); 54717651Speter if (strm->avail_out == 0) { 54817651Speter s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */ 54917651Speter return Z_OK; 55017651Speter } 55117651Speter } 55217651Speter } 55317651Speter Assert(strm->avail_out > 0, "bug2"); 55417651Speter 55517651Speter if (flush != Z_FINISH) return Z_OK; 55617651Speter if (s->noheader) return Z_STREAM_END; 55717651Speter 55817651Speter /* Write the zlib trailer (adler32) */ 55917651Speter putShortMSB(s, (uInt)(strm->adler >> 16)); 56017651Speter putShortMSB(s, (uInt)(strm->adler & 0xffff)); 56117651Speter flush_pending(strm); 56217651Speter /* If avail_out is zero, the application will call deflate again 56317651Speter * to flush the rest. 56417651Speter */ 56517651Speter s->noheader = -1; /* write the trailer only once! */ 56617651Speter return s->pending != 0 ? Z_OK : Z_STREAM_END; 56717651Speter} 56817651Speter 56917651Speter/* ========================================================================= */ 57033908Ssteveint ZEXPORT deflateEnd (strm) 57117651Speter z_streamp strm; 57217651Speter{ 57317651Speter int status; 57417651Speter 57517651Speter if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 57617651Speter 57733908Ssteve status = strm->state->status; 57833908Ssteve if (status != INIT_STATE && status != BUSY_STATE && 57933908Ssteve status != FINISH_STATE) { 58033908Ssteve return Z_STREAM_ERROR; 58133908Ssteve } 58233908Ssteve 58317651Speter /* Deallocate in reverse order of allocations: */ 58417651Speter TRY_FREE(strm, strm->state->pending_buf); 58517651Speter TRY_FREE(strm, strm->state->head); 58617651Speter TRY_FREE(strm, strm->state->prev); 58717651Speter TRY_FREE(strm, strm->state->window); 58817651Speter 58917651Speter ZFREE(strm, strm->state); 59017651Speter strm->state = Z_NULL; 59117651Speter 59217651Speter return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK; 59317651Speter} 59417651Speter 59533908Ssteve/* ========================================================================= 59633908Ssteve * Copy the source state to the destination state. 59733908Ssteve * To simplify the source, this is not supported for 16-bit MSDOS (which 59833908Ssteve * doesn't have enough memory anyway to duplicate compression states). 59933908Ssteve */ 60033908Ssteveint ZEXPORT deflateCopy (dest, source) 60117651Speter z_streamp dest; 60217651Speter z_streamp source; 60317651Speter{ 60433908Ssteve#ifdef MAXSEG_64K 60533908Ssteve return Z_STREAM_ERROR; 60633908Ssteve#else 60733908Ssteve deflate_state *ds; 60833908Ssteve deflate_state *ss; 60933908Ssteve ushf *overlay; 61033908Ssteve 61133908Ssteve ss = source->state; 61233908Ssteve 61333908Ssteve if (source == Z_NULL || dest == Z_NULL || ss == Z_NULL) { 61417651Speter return Z_STREAM_ERROR; 61517651Speter } 61617651Speter *dest = *source; 61717651Speter 61833908Ssteve ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state)); 61933908Ssteve if (ds == Z_NULL) return Z_MEM_ERROR; 62033908Ssteve dest->state = (struct internal_state FAR *) ds; 62133908Ssteve *ds = *ss; 62233908Ssteve ds->strm = dest; 62333908Ssteve 62433908Ssteve ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte)); 62533908Ssteve ds->prev = (Posf *) ZALLOC(dest, ds->w_size, sizeof(Pos)); 62633908Ssteve ds->head = (Posf *) ZALLOC(dest, ds->hash_size, sizeof(Pos)); 62733908Ssteve overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof(ush)+2); 62833908Ssteve ds->pending_buf = (uchf *) overlay; 62933908Ssteve 63033908Ssteve if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL || 63133908Ssteve ds->pending_buf == Z_NULL) { 63233908Ssteve deflateEnd (dest); 63333908Ssteve return Z_MEM_ERROR; 63433908Ssteve } 63533908Ssteve /* following zmemcpy do not work for 16-bit MSDOS */ 63633908Ssteve zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte)); 63733908Ssteve zmemcpy(ds->prev, ss->prev, ds->w_size * sizeof(Pos)); 63833908Ssteve zmemcpy(ds->head, ss->head, ds->hash_size * sizeof(Pos)); 63933908Ssteve zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size); 64033908Ssteve 64133908Ssteve ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf); 64233908Ssteve ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush); 64333908Ssteve ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize; 64433908Ssteve 64533908Ssteve ds->l_desc.dyn_tree = ds->dyn_ltree; 64633908Ssteve ds->d_desc.dyn_tree = ds->dyn_dtree; 64733908Ssteve ds->bl_desc.dyn_tree = ds->bl_tree; 64833908Ssteve 64917651Speter return Z_OK; 65017651Speter#endif 65117651Speter} 65217651Speter 65317651Speter/* =========================================================================== 65417651Speter * Read a new buffer from the current input stream, update the adler32 65517651Speter * and total number of bytes read. All deflate() input goes through 65617651Speter * this function so some applications may wish to modify it to avoid 65717651Speter * allocating a large strm->next_in buffer and copying from it. 65817651Speter * (See also flush_pending()). 65917651Speter */ 66017651Speterlocal int read_buf(strm, buf, size) 66117651Speter z_streamp strm; 66233908Ssteve Bytef *buf; 66317651Speter unsigned size; 66417651Speter{ 66517651Speter unsigned len = strm->avail_in; 66617651Speter 66717651Speter if (len > size) len = size; 66817651Speter if (len == 0) return 0; 66917651Speter 67017651Speter strm->avail_in -= len; 67117651Speter 67217651Speter if (!strm->state->noheader) { 67317651Speter strm->adler = adler32(strm->adler, strm->next_in, len); 67417651Speter } 67517651Speter zmemcpy(buf, strm->next_in, len); 67617651Speter strm->next_in += len; 67717651Speter strm->total_in += len; 67817651Speter 67917651Speter return (int)len; 68017651Speter} 68117651Speter 68217651Speter/* =========================================================================== 68317651Speter * Initialize the "longest match" routines for a new zlib stream 68417651Speter */ 68517651Speterlocal void lm_init (s) 68617651Speter deflate_state *s; 68717651Speter{ 68817651Speter s->window_size = (ulg)2L*s->w_size; 68917651Speter 69017651Speter CLEAR_HASH(s); 69117651Speter 69217651Speter /* Set the default configuration parameters: 69317651Speter */ 69417651Speter s->max_lazy_match = configuration_table[s->level].max_lazy; 69517651Speter s->good_match = configuration_table[s->level].good_length; 69617651Speter s->nice_match = configuration_table[s->level].nice_length; 69717651Speter s->max_chain_length = configuration_table[s->level].max_chain; 69817651Speter 69917651Speter s->strstart = 0; 70017651Speter s->block_start = 0L; 70117651Speter s->lookahead = 0; 70217651Speter s->match_length = s->prev_length = MIN_MATCH-1; 70317651Speter s->match_available = 0; 70417651Speter s->ins_h = 0; 70517651Speter#ifdef ASMV 70617651Speter match_init(); /* initialize the asm code */ 70717651Speter#endif 70817651Speter} 70917651Speter 71017651Speter/* =========================================================================== 71117651Speter * Set match_start to the longest match starting at the given string and 71217651Speter * return its length. Matches shorter or equal to prev_length are discarded, 71317651Speter * in which case the result is equal to prev_length and match_start is 71417651Speter * garbage. 71517651Speter * IN assertions: cur_match is the head of the hash chain for the current 71617651Speter * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1 71717651Speter * OUT assertion: the match length is not greater than s->lookahead. 71817651Speter */ 71917651Speter#ifndef ASMV 72017651Speter/* For 80x86 and 680x0, an optimized version will be provided in match.asm or 72117651Speter * match.S. The code will be functionally equivalent. 72217651Speter */ 72333908Ssteve#ifndef FASTEST 72417651Speterlocal uInt longest_match(s, cur_match) 72517651Speter deflate_state *s; 72617651Speter IPos cur_match; /* current match */ 72717651Speter{ 72817651Speter unsigned chain_length = s->max_chain_length;/* max hash chain length */ 72917651Speter register Bytef *scan = s->window + s->strstart; /* current string */ 73017651Speter register Bytef *match; /* matched string */ 73117651Speter register int len; /* length of current match */ 73217651Speter int best_len = s->prev_length; /* best match length so far */ 73317651Speter int nice_match = s->nice_match; /* stop if match long enough */ 73417651Speter IPos limit = s->strstart > (IPos)MAX_DIST(s) ? 73517651Speter s->strstart - (IPos)MAX_DIST(s) : NIL; 73617651Speter /* Stop when cur_match becomes <= limit. To simplify the code, 73717651Speter * we prevent matches with the string of window index 0. 73817651Speter */ 73917651Speter Posf *prev = s->prev; 74017651Speter uInt wmask = s->w_mask; 74117651Speter 74217651Speter#ifdef UNALIGNED_OK 74317651Speter /* Compare two bytes at a time. Note: this is not always beneficial. 74417651Speter * Try with and without -DUNALIGNED_OK to check. 74517651Speter */ 74617651Speter register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1; 74717651Speter register ush scan_start = *(ushf*)scan; 74817651Speter register ush scan_end = *(ushf*)(scan+best_len-1); 74917651Speter#else 75017651Speter register Bytef *strend = s->window + s->strstart + MAX_MATCH; 75117651Speter register Byte scan_end1 = scan[best_len-1]; 75217651Speter register Byte scan_end = scan[best_len]; 75317651Speter#endif 75417651Speter 75517651Speter /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. 75617651Speter * It is easy to get rid of this optimization if necessary. 75717651Speter */ 75817651Speter Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever"); 75917651Speter 76017651Speter /* Do not waste too much time if we already have a good match: */ 76117651Speter if (s->prev_length >= s->good_match) { 76217651Speter chain_length >>= 2; 76317651Speter } 76417651Speter /* Do not look for matches beyond the end of the input. This is necessary 76517651Speter * to make deflate deterministic. 76617651Speter */ 76717651Speter if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead; 76817651Speter 76917651Speter Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead"); 77017651Speter 77117651Speter do { 77217651Speter Assert(cur_match < s->strstart, "no future"); 77317651Speter match = s->window + cur_match; 77417651Speter 77517651Speter /* Skip to next match if the match length cannot increase 77617651Speter * or if the match length is less than 2: 77717651Speter */ 77817651Speter#if (defined(UNALIGNED_OK) && MAX_MATCH == 258) 77917651Speter /* This code assumes sizeof(unsigned short) == 2. Do not use 78017651Speter * UNALIGNED_OK if your compiler uses a different size. 78117651Speter */ 78217651Speter if (*(ushf*)(match+best_len-1) != scan_end || 78317651Speter *(ushf*)match != scan_start) continue; 78417651Speter 78517651Speter /* It is not necessary to compare scan[2] and match[2] since they are 78617651Speter * always equal when the other bytes match, given that the hash keys 78717651Speter * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at 78817651Speter * strstart+3, +5, ... up to strstart+257. We check for insufficient 78917651Speter * lookahead only every 4th comparison; the 128th check will be made 79017651Speter * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is 79117651Speter * necessary to put more guard bytes at the end of the window, or 79217651Speter * to check more often for insufficient lookahead. 79317651Speter */ 79417651Speter Assert(scan[2] == match[2], "scan[2]?"); 79517651Speter scan++, match++; 79617651Speter do { 79717651Speter } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) && 79817651Speter *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 79917651Speter *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 80017651Speter *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 80117651Speter scan < strend); 80217651Speter /* The funny "do {}" generates better code on most compilers */ 80317651Speter 80417651Speter /* Here, scan <= window+strstart+257 */ 80517651Speter Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 80617651Speter if (*scan == *match) scan++; 80717651Speter 80817651Speter len = (MAX_MATCH - 1) - (int)(strend-scan); 80917651Speter scan = strend - (MAX_MATCH-1); 81017651Speter 81117651Speter#else /* UNALIGNED_OK */ 81217651Speter 81317651Speter if (match[best_len] != scan_end || 81417651Speter match[best_len-1] != scan_end1 || 81517651Speter *match != *scan || 81617651Speter *++match != scan[1]) continue; 81717651Speter 81817651Speter /* The check at best_len-1 can be removed because it will be made 81917651Speter * again later. (This heuristic is not always a win.) 82017651Speter * It is not necessary to compare scan[2] and match[2] since they 82117651Speter * are always equal when the other bytes match, given that 82217651Speter * the hash keys are equal and that HASH_BITS >= 8. 82317651Speter */ 82417651Speter scan += 2, match++; 82517651Speter Assert(*scan == *match, "match[2]?"); 82617651Speter 82717651Speter /* We check for insufficient lookahead only every 8th comparison; 82817651Speter * the 256th check will be made at strstart+258. 82917651Speter */ 83017651Speter do { 83117651Speter } while (*++scan == *++match && *++scan == *++match && 83217651Speter *++scan == *++match && *++scan == *++match && 83317651Speter *++scan == *++match && *++scan == *++match && 83417651Speter *++scan == *++match && *++scan == *++match && 83517651Speter scan < strend); 83617651Speter 83717651Speter Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 83817651Speter 83917651Speter len = MAX_MATCH - (int)(strend - scan); 84017651Speter scan = strend - MAX_MATCH; 84117651Speter 84217651Speter#endif /* UNALIGNED_OK */ 84317651Speter 84417651Speter if (len > best_len) { 84517651Speter s->match_start = cur_match; 84617651Speter best_len = len; 84717651Speter if (len >= nice_match) break; 84817651Speter#ifdef UNALIGNED_OK 84917651Speter scan_end = *(ushf*)(scan+best_len-1); 85017651Speter#else 85117651Speter scan_end1 = scan[best_len-1]; 85217651Speter scan_end = scan[best_len]; 85317651Speter#endif 85417651Speter } 85517651Speter } while ((cur_match = prev[cur_match & wmask]) > limit 85617651Speter && --chain_length != 0); 85717651Speter 85833908Ssteve if ((uInt)best_len <= s->lookahead) return (uInt)best_len; 85917651Speter return s->lookahead; 86017651Speter} 86133908Ssteve 86233908Ssteve#else /* FASTEST */ 86333908Ssteve/* --------------------------------------------------------------------------- 86433908Ssteve * Optimized version for level == 1 only 86533908Ssteve */ 86633908Sstevelocal uInt longest_match(s, cur_match) 86733908Ssteve deflate_state *s; 86833908Ssteve IPos cur_match; /* current match */ 86933908Ssteve{ 87033908Ssteve register Bytef *scan = s->window + s->strstart; /* current string */ 87133908Ssteve register Bytef *match; /* matched string */ 87233908Ssteve register int len; /* length of current match */ 87333908Ssteve register Bytef *strend = s->window + s->strstart + MAX_MATCH; 87433908Ssteve 87533908Ssteve /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. 87633908Ssteve * It is easy to get rid of this optimization if necessary. 87733908Ssteve */ 87833908Ssteve Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever"); 87933908Ssteve 88033908Ssteve Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead"); 88133908Ssteve 88233908Ssteve Assert(cur_match < s->strstart, "no future"); 88333908Ssteve 88433908Ssteve match = s->window + cur_match; 88533908Ssteve 88633908Ssteve /* Return failure if the match length is less than 2: 88733908Ssteve */ 88833908Ssteve if (match[0] != scan[0] || match[1] != scan[1]) return MIN_MATCH-1; 88933908Ssteve 89033908Ssteve /* The check at best_len-1 can be removed because it will be made 89133908Ssteve * again later. (This heuristic is not always a win.) 89233908Ssteve * It is not necessary to compare scan[2] and match[2] since they 89333908Ssteve * are always equal when the other bytes match, given that 89433908Ssteve * the hash keys are equal and that HASH_BITS >= 8. 89533908Ssteve */ 89633908Ssteve scan += 2, match += 2; 89733908Ssteve Assert(*scan == *match, "match[2]?"); 89833908Ssteve 89933908Ssteve /* We check for insufficient lookahead only every 8th comparison; 90033908Ssteve * the 256th check will be made at strstart+258. 90133908Ssteve */ 90233908Ssteve do { 90333908Ssteve } while (*++scan == *++match && *++scan == *++match && 90433908Ssteve *++scan == *++match && *++scan == *++match && 90533908Ssteve *++scan == *++match && *++scan == *++match && 90633908Ssteve *++scan == *++match && *++scan == *++match && 90733908Ssteve scan < strend); 90833908Ssteve 90933908Ssteve Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 91033908Ssteve 91133908Ssteve len = MAX_MATCH - (int)(strend - scan); 91233908Ssteve 91333908Ssteve if (len < MIN_MATCH) return MIN_MATCH - 1; 91433908Ssteve 91533908Ssteve s->match_start = cur_match; 91633908Ssteve return len <= s->lookahead ? len : s->lookahead; 91733908Ssteve} 91833908Ssteve#endif /* FASTEST */ 91917651Speter#endif /* ASMV */ 92017651Speter 92117651Speter#ifdef DEBUG 92217651Speter/* =========================================================================== 92317651Speter * Check that the match at match_start is indeed a match. 92417651Speter */ 92517651Speterlocal void check_match(s, start, match, length) 92617651Speter deflate_state *s; 92717651Speter IPos start, match; 92817651Speter int length; 92917651Speter{ 93017651Speter /* check that the match is indeed a match */ 93133908Ssteve if (zmemcmp(s->window + match, 93233908Ssteve s->window + start, length) != EQUAL) { 93317651Speter fprintf(stderr, " start %u, match %u, length %d\n", 93417651Speter start, match, length); 93517651Speter do { 93617651Speter fprintf(stderr, "%c%c", s->window[match++], s->window[start++]); 93717651Speter } while (--length != 0); 93817651Speter z_error("invalid match"); 93917651Speter } 94033908Ssteve if (z_verbose > 1) { 94117651Speter fprintf(stderr,"\\[%d,%d]", start-match, length); 94217651Speter do { putc(s->window[start++], stderr); } while (--length != 0); 94317651Speter } 94417651Speter} 94517651Speter#else 94617651Speter# define check_match(s, start, match, length) 94717651Speter#endif 94817651Speter 94917651Speter/* =========================================================================== 95017651Speter * Fill the window when the lookahead becomes insufficient. 95117651Speter * Updates strstart and lookahead. 95217651Speter * 95317651Speter * IN assertion: lookahead < MIN_LOOKAHEAD 95417651Speter * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD 95517651Speter * At least one byte has been read, or avail_in == 0; reads are 95617651Speter * performed for at least two bytes (required for the zip translate_eol 95717651Speter * option -- not supported here). 95817651Speter */ 95917651Speterlocal void fill_window(s) 96017651Speter deflate_state *s; 96117651Speter{ 96217651Speter register unsigned n, m; 96317651Speter register Posf *p; 96417651Speter unsigned more; /* Amount of free space at the end of the window. */ 96517651Speter uInt wsize = s->w_size; 96617651Speter 96717651Speter do { 96817651Speter more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart); 96917651Speter 97017651Speter /* Deal with !@#$% 64K limit: */ 97117651Speter if (more == 0 && s->strstart == 0 && s->lookahead == 0) { 97217651Speter more = wsize; 97317651Speter 97417651Speter } else if (more == (unsigned)(-1)) { 97517651Speter /* Very unlikely, but possible on 16 bit machine if strstart == 0 97617651Speter * and lookahead == 1 (input done one byte at time) 97717651Speter */ 97817651Speter more--; 97917651Speter 98017651Speter /* If the window is almost full and there is insufficient lookahead, 98117651Speter * move the upper half to the lower one to make room in the upper half. 98217651Speter */ 98317651Speter } else if (s->strstart >= wsize+MAX_DIST(s)) { 98417651Speter 98533908Ssteve zmemcpy(s->window, s->window+wsize, (unsigned)wsize); 98617651Speter s->match_start -= wsize; 98717651Speter s->strstart -= wsize; /* we now have strstart >= MAX_DIST */ 98817651Speter s->block_start -= (long) wsize; 98917651Speter 99017651Speter /* Slide the hash table (could be avoided with 32 bit values 99133908Ssteve at the expense of memory usage). We slide even when level == 0 99233908Ssteve to keep the hash table consistent if we switch back to level > 0 99333908Ssteve later. (Using level 0 permanently is not an optimal usage of 99433908Ssteve zlib, so we don't care about this pathological case.) 99517651Speter */ 99633908Ssteve n = s->hash_size; 99733908Ssteve p = &s->head[n]; 99833908Ssteve do { 99933908Ssteve m = *--p; 100033908Ssteve *p = (Pos)(m >= wsize ? m-wsize : NIL); 100133908Ssteve } while (--n); 100217651Speter 100333908Ssteve n = wsize; 100433908Ssteve#ifndef FASTEST 100533908Ssteve p = &s->prev[n]; 100633908Ssteve do { 100733908Ssteve m = *--p; 100833908Ssteve *p = (Pos)(m >= wsize ? m-wsize : NIL); 100933908Ssteve /* If n is not on any hash chain, prev[n] is garbage but 101033908Ssteve * its value will never be used. 101133908Ssteve */ 101233908Ssteve } while (--n); 101333908Ssteve#endif 101417651Speter more += wsize; 101517651Speter } 101617651Speter if (s->strm->avail_in == 0) return; 101717651Speter 101817651Speter /* If there was no sliding: 101917651Speter * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 && 102017651Speter * more == window_size - lookahead - strstart 102117651Speter * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1) 102217651Speter * => more >= window_size - 2*WSIZE + 2 102317651Speter * In the BIG_MEM or MMAP case (not yet supported), 102417651Speter * window_size == input_size + MIN_LOOKAHEAD && 102517651Speter * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD. 102617651Speter * Otherwise, window_size == 2*WSIZE so more >= 2. 102717651Speter * If there was sliding, more >= WSIZE. So in all cases, more >= 2. 102817651Speter */ 102917651Speter Assert(more >= 2, "more < 2"); 103017651Speter 103133908Ssteve n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more); 103217651Speter s->lookahead += n; 103317651Speter 103417651Speter /* Initialize the hash value now that we have some input: */ 103517651Speter if (s->lookahead >= MIN_MATCH) { 103617651Speter s->ins_h = s->window[s->strstart]; 103717651Speter UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]); 103817651Speter#if MIN_MATCH != 3 103917651Speter Call UPDATE_HASH() MIN_MATCH-3 more times 104017651Speter#endif 104117651Speter } 104217651Speter /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage, 104317651Speter * but this is not important since only literal bytes will be emitted. 104417651Speter */ 104517651Speter 104617651Speter } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0); 104717651Speter} 104817651Speter 104917651Speter/* =========================================================================== 105017651Speter * Flush the current block, with given end-of-file flag. 105117651Speter * IN assertion: strstart is set to the end of the current match. 105217651Speter */ 105317651Speter#define FLUSH_BLOCK_ONLY(s, eof) { \ 105417651Speter _tr_flush_block(s, (s->block_start >= 0L ? \ 105517651Speter (charf *)&s->window[(unsigned)s->block_start] : \ 105617651Speter (charf *)Z_NULL), \ 105717651Speter (ulg)((long)s->strstart - s->block_start), \ 105817651Speter (eof)); \ 105917651Speter s->block_start = s->strstart; \ 106017651Speter flush_pending(s->strm); \ 106117651Speter Tracev((stderr,"[FLUSH]")); \ 106217651Speter} 106317651Speter 106417651Speter/* Same but force premature exit if necessary. */ 106517651Speter#define FLUSH_BLOCK(s, eof) { \ 106617651Speter FLUSH_BLOCK_ONLY(s, eof); \ 106717651Speter if (s->strm->avail_out == 0) return (eof) ? finish_started : need_more; \ 106817651Speter} 106917651Speter 107017651Speter/* =========================================================================== 107117651Speter * Copy without compression as much as possible from the input stream, return 107217651Speter * the current block state. 107317651Speter * This function does not insert new strings in the dictionary since 107417651Speter * uncompressible data is probably not useful. This function is used 107517651Speter * only for the level=0 compression option. 107633908Ssteve * NOTE: this function should be optimized to avoid extra copying from 107733908Ssteve * window to pending_buf. 107817651Speter */ 107917651Speterlocal block_state deflate_stored(s, flush) 108017651Speter deflate_state *s; 108117651Speter int flush; 108217651Speter{ 108333908Ssteve /* Stored blocks are limited to 0xffff bytes, pending_buf is limited 108433908Ssteve * to pending_buf_size, and each stored block has a 5 byte header: 108533908Ssteve */ 108633908Ssteve ulg max_block_size = 0xffff; 108733908Ssteve ulg max_start; 108833908Ssteve 108933908Ssteve if (max_block_size > s->pending_buf_size - 5) { 109033908Ssteve max_block_size = s->pending_buf_size - 5; 109133908Ssteve } 109233908Ssteve 109333908Ssteve /* Copy as much as possible from input to output: */ 109417651Speter for (;;) { 109517651Speter /* Fill the window as much as possible: */ 109617651Speter if (s->lookahead <= 1) { 109717651Speter 109817651Speter Assert(s->strstart < s->w_size+MAX_DIST(s) || 109917651Speter s->block_start >= (long)s->w_size, "slide too late"); 110017651Speter 110117651Speter fill_window(s); 110217651Speter if (s->lookahead == 0 && flush == Z_NO_FLUSH) return need_more; 110317651Speter 110417651Speter if (s->lookahead == 0) break; /* flush the current block */ 110517651Speter } 110617651Speter Assert(s->block_start >= 0L, "block gone"); 110717651Speter 110817651Speter s->strstart += s->lookahead; 110917651Speter s->lookahead = 0; 111017651Speter 111133908Ssteve /* Emit a stored block if pending_buf will be full: */ 111233908Ssteve max_start = s->block_start + max_block_size; 111333908Ssteve if (s->strstart == 0 || (ulg)s->strstart >= max_start) { 111417651Speter /* strstart == 0 is possible when wraparound on 16-bit machine */ 111533908Ssteve s->lookahead = (uInt)(s->strstart - max_start); 111633908Ssteve s->strstart = (uInt)max_start; 111733908Ssteve FLUSH_BLOCK(s, 0); 111817651Speter } 111933908Ssteve /* Flush if we may have to slide, otherwise block_start may become 112033908Ssteve * negative and the data will be gone: 112133908Ssteve */ 112217651Speter if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) { 112317651Speter FLUSH_BLOCK(s, 0); 112417651Speter } 112517651Speter } 112617651Speter FLUSH_BLOCK(s, flush == Z_FINISH); 112717651Speter return flush == Z_FINISH ? finish_done : block_done; 112817651Speter} 112917651Speter 113017651Speter/* =========================================================================== 113117651Speter * Compress as much as possible from the input stream, return the current 113217651Speter * block state. 113317651Speter * This function does not perform lazy evaluation of matches and inserts 113417651Speter * new strings in the dictionary only for unmatched strings or for short 113517651Speter * matches. It is used only for the fast compression options. 113617651Speter */ 113717651Speterlocal block_state deflate_fast(s, flush) 113817651Speter deflate_state *s; 113917651Speter int flush; 114017651Speter{ 114117651Speter IPos hash_head = NIL; /* head of the hash chain */ 114217651Speter int bflush; /* set if current block must be flushed */ 114317651Speter 114417651Speter for (;;) { 114517651Speter /* Make sure that we always have enough lookahead, except 114617651Speter * at the end of the input file. We need MAX_MATCH bytes 114717651Speter * for the next match, plus MIN_MATCH bytes to insert the 114817651Speter * string following the next match. 114917651Speter */ 115017651Speter if (s->lookahead < MIN_LOOKAHEAD) { 115117651Speter fill_window(s); 115217651Speter if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { 115317651Speter return need_more; 115417651Speter } 115517651Speter if (s->lookahead == 0) break; /* flush the current block */ 115617651Speter } 115717651Speter 115817651Speter /* Insert the string window[strstart .. strstart+2] in the 115917651Speter * dictionary, and set hash_head to the head of the hash chain: 116017651Speter */ 116117651Speter if (s->lookahead >= MIN_MATCH) { 116217651Speter INSERT_STRING(s, s->strstart, hash_head); 116317651Speter } 116417651Speter 116517651Speter /* Find the longest match, discarding those <= prev_length. 116617651Speter * At this point we have always match_length < MIN_MATCH 116717651Speter */ 116817651Speter if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) { 116917651Speter /* To simplify the code, we prevent matches with the string 117017651Speter * of window index 0 (in particular we have to avoid a match 117117651Speter * of the string with itself at the start of the input file). 117217651Speter */ 117317651Speter if (s->strategy != Z_HUFFMAN_ONLY) { 117417651Speter s->match_length = longest_match (s, hash_head); 117517651Speter } 117617651Speter /* longest_match() sets match_start */ 117717651Speter } 117817651Speter if (s->match_length >= MIN_MATCH) { 117917651Speter check_match(s, s->strstart, s->match_start, s->match_length); 118017651Speter 118133908Ssteve _tr_tally_dist(s, s->strstart - s->match_start, 118233908Ssteve s->match_length - MIN_MATCH, bflush); 118317651Speter 118417651Speter s->lookahead -= s->match_length; 118517651Speter 118617651Speter /* Insert new strings in the hash table only if the match length 118717651Speter * is not too large. This saves time but degrades compression. 118817651Speter */ 118933908Ssteve#ifndef FASTEST 119017651Speter if (s->match_length <= s->max_insert_length && 119117651Speter s->lookahead >= MIN_MATCH) { 119217651Speter s->match_length--; /* string at strstart already in hash table */ 119317651Speter do { 119417651Speter s->strstart++; 119517651Speter INSERT_STRING(s, s->strstart, hash_head); 119617651Speter /* strstart never exceeds WSIZE-MAX_MATCH, so there are 119717651Speter * always MIN_MATCH bytes ahead. 119817651Speter */ 119917651Speter } while (--s->match_length != 0); 120017651Speter s->strstart++; 120133908Ssteve } else 120233908Ssteve#endif 120333908Ssteve { 120417651Speter s->strstart += s->match_length; 120517651Speter s->match_length = 0; 120617651Speter s->ins_h = s->window[s->strstart]; 120717651Speter UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]); 120817651Speter#if MIN_MATCH != 3 120917651Speter Call UPDATE_HASH() MIN_MATCH-3 more times 121017651Speter#endif 121117651Speter /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not 121217651Speter * matter since it will be recomputed at next deflate call. 121317651Speter */ 121417651Speter } 121517651Speter } else { 121617651Speter /* No match, output a literal byte */ 121717651Speter Tracevv((stderr,"%c", s->window[s->strstart])); 121833908Ssteve _tr_tally_lit (s, s->window[s->strstart], bflush); 121917651Speter s->lookahead--; 122017651Speter s->strstart++; 122117651Speter } 122217651Speter if (bflush) FLUSH_BLOCK(s, 0); 122317651Speter } 122417651Speter FLUSH_BLOCK(s, flush == Z_FINISH); 122517651Speter return flush == Z_FINISH ? finish_done : block_done; 122617651Speter} 122717651Speter 122817651Speter/* =========================================================================== 122917651Speter * Same as above, but achieves better compression. We use a lazy 123017651Speter * evaluation for matches: a match is finally adopted only if there is 123117651Speter * no better match at the next window position. 123217651Speter */ 123317651Speterlocal block_state deflate_slow(s, flush) 123417651Speter deflate_state *s; 123517651Speter int flush; 123617651Speter{ 123717651Speter IPos hash_head = NIL; /* head of hash chain */ 123817651Speter int bflush; /* set if current block must be flushed */ 123917651Speter 124017651Speter /* Process the input block. */ 124117651Speter for (;;) { 124217651Speter /* Make sure that we always have enough lookahead, except 124317651Speter * at the end of the input file. We need MAX_MATCH bytes 124417651Speter * for the next match, plus MIN_MATCH bytes to insert the 124517651Speter * string following the next match. 124617651Speter */ 124717651Speter if (s->lookahead < MIN_LOOKAHEAD) { 124817651Speter fill_window(s); 124917651Speter if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { 125017651Speter return need_more; 125117651Speter } 125217651Speter if (s->lookahead == 0) break; /* flush the current block */ 125317651Speter } 125417651Speter 125517651Speter /* Insert the string window[strstart .. strstart+2] in the 125617651Speter * dictionary, and set hash_head to the head of the hash chain: 125717651Speter */ 125817651Speter if (s->lookahead >= MIN_MATCH) { 125917651Speter INSERT_STRING(s, s->strstart, hash_head); 126017651Speter } 126117651Speter 126217651Speter /* Find the longest match, discarding those <= prev_length. 126317651Speter */ 126417651Speter s->prev_length = s->match_length, s->prev_match = s->match_start; 126517651Speter s->match_length = MIN_MATCH-1; 126617651Speter 126717651Speter if (hash_head != NIL && s->prev_length < s->max_lazy_match && 126817651Speter s->strstart - hash_head <= MAX_DIST(s)) { 126917651Speter /* To simplify the code, we prevent matches with the string 127017651Speter * of window index 0 (in particular we have to avoid a match 127117651Speter * of the string with itself at the start of the input file). 127217651Speter */ 127317651Speter if (s->strategy != Z_HUFFMAN_ONLY) { 127417651Speter s->match_length = longest_match (s, hash_head); 127517651Speter } 127617651Speter /* longest_match() sets match_start */ 127717651Speter 127817651Speter if (s->match_length <= 5 && (s->strategy == Z_FILTERED || 127917651Speter (s->match_length == MIN_MATCH && 128017651Speter s->strstart - s->match_start > TOO_FAR))) { 128117651Speter 128217651Speter /* If prev_match is also MIN_MATCH, match_start is garbage 128317651Speter * but we will ignore the current match anyway. 128417651Speter */ 128517651Speter s->match_length = MIN_MATCH-1; 128617651Speter } 128717651Speter } 128817651Speter /* If there was a match at the previous step and the current 128917651Speter * match is not better, output the previous match: 129017651Speter */ 129117651Speter if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) { 129217651Speter uInt max_insert = s->strstart + s->lookahead - MIN_MATCH; 129317651Speter /* Do not insert strings in hash table beyond this. */ 129417651Speter 129517651Speter check_match(s, s->strstart-1, s->prev_match, s->prev_length); 129617651Speter 129733908Ssteve _tr_tally_dist(s, s->strstart -1 - s->prev_match, 129833908Ssteve s->prev_length - MIN_MATCH, bflush); 129917651Speter 130017651Speter /* Insert in hash table all strings up to the end of the match. 130117651Speter * strstart-1 and strstart are already inserted. If there is not 130217651Speter * enough lookahead, the last two strings are not inserted in 130317651Speter * the hash table. 130417651Speter */ 130517651Speter s->lookahead -= s->prev_length-1; 130617651Speter s->prev_length -= 2; 130717651Speter do { 130817651Speter if (++s->strstart <= max_insert) { 130917651Speter INSERT_STRING(s, s->strstart, hash_head); 131017651Speter } 131117651Speter } while (--s->prev_length != 0); 131217651Speter s->match_available = 0; 131317651Speter s->match_length = MIN_MATCH-1; 131417651Speter s->strstart++; 131517651Speter 131617651Speter if (bflush) FLUSH_BLOCK(s, 0); 131717651Speter 131817651Speter } else if (s->match_available) { 131917651Speter /* If there was no match at the previous position, output a 132017651Speter * single literal. If there was a match but the current match 132117651Speter * is longer, truncate the previous match to a single literal. 132217651Speter */ 132317651Speter Tracevv((stderr,"%c", s->window[s->strstart-1])); 132433908Ssteve _tr_tally_lit(s, s->window[s->strstart-1], bflush); 132533908Ssteve if (bflush) { 132617651Speter FLUSH_BLOCK_ONLY(s, 0); 132717651Speter } 132817651Speter s->strstart++; 132917651Speter s->lookahead--; 133017651Speter if (s->strm->avail_out == 0) return need_more; 133117651Speter } else { 133217651Speter /* There is no previous match to compare with, wait for 133317651Speter * the next step to decide. 133417651Speter */ 133517651Speter s->match_available = 1; 133617651Speter s->strstart++; 133717651Speter s->lookahead--; 133817651Speter } 133917651Speter } 134017651Speter Assert (flush != Z_NO_FLUSH, "no flush?"); 134117651Speter if (s->match_available) { 134217651Speter Tracevv((stderr,"%c", s->window[s->strstart-1])); 134333908Ssteve _tr_tally_lit(s, s->window[s->strstart-1], bflush); 134417651Speter s->match_available = 0; 134517651Speter } 134617651Speter FLUSH_BLOCK(s, flush == Z_FINISH); 134717651Speter return flush == Z_FINISH ? finish_done : block_done; 134817651Speter} 1349