1c9083b85SXin LI /* deflate.c -- compress data using the deflation algorithm 24717628eSXin LI * Copyright (C) 1995-2023 Jean-loup Gailly and Mark Adler 3c9083b85SXin LI * For conditions of distribution and use, see copyright notice in zlib.h 4c9083b85SXin LI */ 5c9083b85SXin LI 6c9083b85SXin LI /* 7c9083b85SXin LI * ALGORITHM 8c9083b85SXin LI * 9c9083b85SXin LI * The "deflation" process depends on being able to identify portions 10c9083b85SXin LI * of the input text which are identical to earlier input (within a 11c9083b85SXin LI * sliding window trailing behind the input currently being processed). 12c9083b85SXin LI * 13c9083b85SXin LI * The most straightforward technique turns out to be the fastest for 14c9083b85SXin LI * most input files: try all possible matches and select the longest. 15c9083b85SXin LI * The key feature of this algorithm is that insertions into the string 16c9083b85SXin LI * dictionary are very simple and thus fast, and deletions are avoided 17c9083b85SXin LI * completely. Insertions are performed at each input character, whereas 18c9083b85SXin LI * string matches are performed only when the previous match ends. So it 19c9083b85SXin LI * is preferable to spend more time in matches to allow very fast string 20c9083b85SXin LI * insertions and avoid deletions. The matching algorithm for small 21c9083b85SXin LI * strings is inspired from that of Rabin & Karp. A brute force approach 22c9083b85SXin LI * is used to find longer strings when a small match has been found. 23c9083b85SXin LI * A similar algorithm is used in comic (by Jan-Mark Wams) and freeze 24c9083b85SXin LI * (by Leonid Broukhis). 25c9083b85SXin LI * A previous version of this file used a more sophisticated algorithm 26c9083b85SXin LI * (by Fiala and Greene) which is guaranteed to run in linear amortized 27c9083b85SXin LI * time, but has a larger average cost, uses more memory and is patented. 28c9083b85SXin LI * However the F&G algorithm may be faster for some highly redundant 29c9083b85SXin LI * files if the parameter max_chain_length (described below) is too large. 30c9083b85SXin LI * 31c9083b85SXin LI * ACKNOWLEDGEMENTS 32c9083b85SXin LI * 33c9083b85SXin LI * The idea of lazy evaluation of matches is due to Jan-Mark Wams, and 34c9083b85SXin LI * I found it in 'freeze' written by Leonid Broukhis. 35c9083b85SXin LI * Thanks to many people for bug reports and testing. 36c9083b85SXin LI * 37c9083b85SXin LI * REFERENCES 38c9083b85SXin LI * 39c9083b85SXin LI * Deutsch, L.P.,"DEFLATE Compressed Data Format Specification". 40c9083b85SXin LI * Available in http://tools.ietf.org/html/rfc1951 41c9083b85SXin LI * 42c9083b85SXin LI * A description of the Rabin and Karp algorithm is given in the book 43c9083b85SXin LI * "Algorithms" by R. Sedgewick, Addison-Wesley, p252. 44c9083b85SXin LI * 45c9083b85SXin LI * Fiala,E.R., and Greene,D.H. 46c9083b85SXin LI * Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595 47c9083b85SXin LI * 48c9083b85SXin LI */ 49c9083b85SXin LI 50c9083b85SXin LI /* @(#) $Id$ */ 51c9083b85SXin LI 52c9083b85SXin LI #include "deflate.h" 53c9083b85SXin LI 54c9083b85SXin LI const char deflate_copyright[] = 554717628eSXin LI " deflate 1.3 Copyright 1995-2023 Jean-loup Gailly and Mark Adler "; 56c9083b85SXin LI /* 57c9083b85SXin LI If you use the zlib library in a product, an acknowledgment is welcome 58c9083b85SXin LI in the documentation of your product. If for some reason you cannot 59c9083b85SXin LI include such an acknowledgment, I would appreciate that you keep this 60c9083b85SXin LI copyright string in the executable of your product. 61c9083b85SXin LI */ 62c9083b85SXin LI 63c9083b85SXin LI typedef enum { 64c9083b85SXin LI need_more, /* block not completed, need more input or more output */ 65c9083b85SXin LI block_done, /* block flush performed */ 66c9083b85SXin LI finish_started, /* finish started, need only more output at next deflate */ 67c9083b85SXin LI finish_done /* finish done, accept no more input or output */ 68c9083b85SXin LI } block_state; 69c9083b85SXin LI 704717628eSXin LI typedef block_state (*compress_func)(deflate_state *s, int flush); 71c9083b85SXin LI /* Compression function. Returns the block state after the call. */ 72c9083b85SXin LI 734717628eSXin LI local block_state deflate_stored(deflate_state *s, int flush); 744717628eSXin LI local block_state deflate_fast(deflate_state *s, int flush); 75c9083b85SXin LI #ifndef FASTEST 764717628eSXin LI local block_state deflate_slow(deflate_state *s, int flush); 77c9083b85SXin LI #endif 784717628eSXin LI local block_state deflate_rle(deflate_state *s, int flush); 794717628eSXin LI local block_state deflate_huff(deflate_state *s, int flush); 80c9083b85SXin LI 81c9083b85SXin LI /* =========================================================================== 82c9083b85SXin LI * Local data 83c9083b85SXin LI */ 84c9083b85SXin LI 85c9083b85SXin LI #define NIL 0 86c9083b85SXin LI /* Tail of hash chains */ 87c9083b85SXin LI 88c9083b85SXin LI #ifndef TOO_FAR 89c9083b85SXin LI # define TOO_FAR 4096 90c9083b85SXin LI #endif 91c9083b85SXin LI /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */ 92c9083b85SXin LI 93c9083b85SXin LI /* Values for max_lazy_match, good_match and max_chain_length, depending on 94c9083b85SXin LI * the desired pack level (0..9). The values given below have been tuned to 95c9083b85SXin LI * exclude worst case performance for pathological files. Better values may be 96c9083b85SXin LI * found for specific files. 97c9083b85SXin LI */ 98c9083b85SXin LI typedef struct config_s { 99c9083b85SXin LI ush good_length; /* reduce lazy search above this match length */ 100c9083b85SXin LI ush max_lazy; /* do not perform lazy search above this match length */ 101c9083b85SXin LI ush nice_length; /* quit search above this match length */ 102c9083b85SXin LI ush max_chain; 103c9083b85SXin LI compress_func func; 104c9083b85SXin LI } config; 105c9083b85SXin LI 106c9083b85SXin LI #ifdef FASTEST 107c9083b85SXin LI local const config configuration_table[2] = { 108c9083b85SXin LI /* good lazy nice chain */ 109c9083b85SXin LI /* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */ 110c9083b85SXin LI /* 1 */ {4, 4, 8, 4, deflate_fast}}; /* max speed, no lazy matches */ 111c9083b85SXin LI #else 112c9083b85SXin LI local const config configuration_table[10] = { 113c9083b85SXin LI /* good lazy nice chain */ 114c9083b85SXin LI /* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */ 115c9083b85SXin LI /* 1 */ {4, 4, 8, 4, deflate_fast}, /* max speed, no lazy matches */ 116c9083b85SXin LI /* 2 */ {4, 5, 16, 8, deflate_fast}, 117c9083b85SXin LI /* 3 */ {4, 6, 32, 32, deflate_fast}, 118c9083b85SXin LI 119c9083b85SXin LI /* 4 */ {4, 4, 16, 16, deflate_slow}, /* lazy matches */ 120c9083b85SXin LI /* 5 */ {8, 16, 32, 32, deflate_slow}, 121c9083b85SXin LI /* 6 */ {8, 16, 128, 128, deflate_slow}, 122c9083b85SXin LI /* 7 */ {8, 32, 128, 256, deflate_slow}, 123c9083b85SXin LI /* 8 */ {32, 128, 258, 1024, deflate_slow}, 124c9083b85SXin LI /* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* max compression */ 125c9083b85SXin LI #endif 126c9083b85SXin LI 127c9083b85SXin LI /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4 128c9083b85SXin LI * For deflate_fast() (levels <= 3) good is ignored and lazy has a different 129c9083b85SXin LI * meaning. 130c9083b85SXin LI */ 131c9083b85SXin LI 132c9083b85SXin LI /* rank Z_BLOCK between Z_NO_FLUSH and Z_PARTIAL_FLUSH */ 133c9083b85SXin LI #define RANK(f) (((f) * 2) - ((f) > 4 ? 9 : 0)) 134c9083b85SXin LI 135c9083b85SXin LI /* =========================================================================== 136c9083b85SXin LI * Update a hash value with the given input byte 137c9083b85SXin LI * IN assertion: all calls to UPDATE_HASH are made with consecutive input 138c9083b85SXin LI * characters, so that a running hash key can be computed from the previous 139c9083b85SXin LI * key instead of complete recalculation each time. 140c9083b85SXin LI */ 141c9083b85SXin LI #define UPDATE_HASH(s,h,c) (h = (((h) << s->hash_shift) ^ (c)) & s->hash_mask) 142c9083b85SXin LI 143c9083b85SXin LI 144c9083b85SXin LI /* =========================================================================== 145c9083b85SXin LI * Insert string str in the dictionary and set match_head to the previous head 146c9083b85SXin LI * of the hash chain (the most recent string with same hash key). Return 147c9083b85SXin LI * the previous length of the hash chain. 148c9083b85SXin LI * If this file is compiled with -DFASTEST, the compression level is forced 149c9083b85SXin LI * to 1, and no hash chains are maintained. 150c9083b85SXin LI * IN assertion: all calls to INSERT_STRING are made with consecutive input 151c9083b85SXin LI * characters and the first MIN_MATCH bytes of str are valid (except for 152c9083b85SXin LI * the last MIN_MATCH-1 bytes of the input file). 153c9083b85SXin LI */ 154c9083b85SXin LI #ifdef FASTEST 155c9083b85SXin LI #define INSERT_STRING(s, str, match_head) \ 156c9083b85SXin LI (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \ 157c9083b85SXin LI match_head = s->head[s->ins_h], \ 158c9083b85SXin LI s->head[s->ins_h] = (Pos)(str)) 159c9083b85SXin LI #else 160c9083b85SXin LI #define INSERT_STRING(s, str, match_head) \ 161c9083b85SXin LI (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \ 162c9083b85SXin LI match_head = s->prev[(str) & s->w_mask] = s->head[s->ins_h], \ 163c9083b85SXin LI s->head[s->ins_h] = (Pos)(str)) 164c9083b85SXin LI #endif 165c9083b85SXin LI 166c9083b85SXin LI /* =========================================================================== 167c9083b85SXin LI * Initialize the hash table (avoiding 64K overflow for 16 bit systems). 168c9083b85SXin LI * prev[] will be initialized on the fly. 169c9083b85SXin LI */ 170110f2297SXin LI #define CLEAR_HASH(s) \ 171110f2297SXin LI do { \ 172c9083b85SXin LI s->head[s->hash_size - 1] = NIL; \ 173110f2297SXin LI zmemzero((Bytef *)s->head, \ 174110f2297SXin LI (unsigned)(s->hash_size - 1)*sizeof(*s->head)); \ 1750ed1d6fbSXin LI } while (0) 176c9083b85SXin LI 177c9083b85SXin LI /* =========================================================================== 178c9083b85SXin LI * Slide the hash table when sliding the window down (could be avoided with 32 179c9083b85SXin LI * bit values at the expense of memory usage). We slide even when level == 0 to 180c9083b85SXin LI * keep the hash table consistent if we switch back to level > 0 later. 181c9083b85SXin LI */ 1824717628eSXin LI #if defined(__has_feature) 1834717628eSXin LI # if __has_feature(memory_sanitizer) 1844717628eSXin LI __attribute__((no_sanitize("memory"))) 1854717628eSXin LI # endif 1864717628eSXin LI #endif 1874717628eSXin LI local void slide_hash(deflate_state *s) { 188c9083b85SXin LI unsigned n, m; 189c9083b85SXin LI Posf *p; 190c9083b85SXin LI uInt wsize = s->w_size; 191c9083b85SXin LI 192c9083b85SXin LI n = s->hash_size; 193c9083b85SXin LI p = &s->head[n]; 194c9083b85SXin LI do { 195c9083b85SXin LI m = *--p; 196c9083b85SXin LI *p = (Pos)(m >= wsize ? m - wsize : NIL); 197c9083b85SXin LI } while (--n); 198c9083b85SXin LI n = wsize; 199c9083b85SXin LI #ifndef FASTEST 200c9083b85SXin LI p = &s->prev[n]; 201c9083b85SXin LI do { 202c9083b85SXin LI m = *--p; 203c9083b85SXin LI *p = (Pos)(m >= wsize ? m - wsize : NIL); 204c9083b85SXin LI /* If n is not on any hash chain, prev[n] is garbage but 205c9083b85SXin LI * its value will never be used. 206c9083b85SXin LI */ 207c9083b85SXin LI } while (--n); 208c9083b85SXin LI #endif 209c9083b85SXin LI } 210c9083b85SXin LI 2114717628eSXin LI /* =========================================================================== 2124717628eSXin LI * Read a new buffer from the current input stream, update the adler32 2134717628eSXin LI * and total number of bytes read. All deflate() input goes through 2144717628eSXin LI * this function so some applications may wish to modify it to avoid 2154717628eSXin LI * allocating a large strm->next_in buffer and copying from it. 2164717628eSXin LI * (See also flush_pending()). 2174717628eSXin LI */ 2184717628eSXin LI local unsigned read_buf(z_streamp strm, Bytef *buf, unsigned size) { 2194717628eSXin LI unsigned len = strm->avail_in; 2204717628eSXin LI 2214717628eSXin LI if (len > size) len = size; 2224717628eSXin LI if (len == 0) return 0; 2234717628eSXin LI 2244717628eSXin LI strm->avail_in -= len; 2254717628eSXin LI 2264717628eSXin LI zmemcpy(buf, strm->next_in, len); 2274717628eSXin LI if (strm->state->wrap == 1) { 2284717628eSXin LI strm->adler = adler32(strm->adler, buf, len); 2294717628eSXin LI } 2304717628eSXin LI #ifdef GZIP 2314717628eSXin LI else if (strm->state->wrap == 2) { 2324717628eSXin LI strm->adler = crc32(strm->adler, buf, len); 2334717628eSXin LI } 2344717628eSXin LI #endif 2354717628eSXin LI strm->next_in += len; 2364717628eSXin LI strm->total_in += len; 2374717628eSXin LI 2384717628eSXin LI return len; 2394717628eSXin LI } 2404717628eSXin LI 2414717628eSXin LI /* =========================================================================== 2424717628eSXin LI * Fill the window when the lookahead becomes insufficient. 2434717628eSXin LI * Updates strstart and lookahead. 2444717628eSXin LI * 2454717628eSXin LI * IN assertion: lookahead < MIN_LOOKAHEAD 2464717628eSXin LI * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD 2474717628eSXin LI * At least one byte has been read, or avail_in == 0; reads are 2484717628eSXin LI * performed for at least two bytes (required for the zip translate_eol 2494717628eSXin LI * option -- not supported here). 2504717628eSXin LI */ 2514717628eSXin LI local void fill_window(deflate_state *s) { 2524717628eSXin LI unsigned n; 2534717628eSXin LI unsigned more; /* Amount of free space at the end of the window. */ 2544717628eSXin LI uInt wsize = s->w_size; 2554717628eSXin LI 2564717628eSXin LI Assert(s->lookahead < MIN_LOOKAHEAD, "already enough lookahead"); 2574717628eSXin LI 2584717628eSXin LI do { 2594717628eSXin LI more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart); 2604717628eSXin LI 2614717628eSXin LI /* Deal with !@#$% 64K limit: */ 2624717628eSXin LI if (sizeof(int) <= 2) { 2634717628eSXin LI if (more == 0 && s->strstart == 0 && s->lookahead == 0) { 2644717628eSXin LI more = wsize; 2654717628eSXin LI 2664717628eSXin LI } else if (more == (unsigned)(-1)) { 2674717628eSXin LI /* Very unlikely, but possible on 16 bit machine if 2684717628eSXin LI * strstart == 0 && lookahead == 1 (input done a byte at time) 2694717628eSXin LI */ 2704717628eSXin LI more--; 2714717628eSXin LI } 2724717628eSXin LI } 2734717628eSXin LI 2744717628eSXin LI /* If the window is almost full and there is insufficient lookahead, 2754717628eSXin LI * move the upper half to the lower one to make room in the upper half. 2764717628eSXin LI */ 2774717628eSXin LI if (s->strstart >= wsize + MAX_DIST(s)) { 2784717628eSXin LI 2794717628eSXin LI zmemcpy(s->window, s->window + wsize, (unsigned)wsize - more); 2804717628eSXin LI s->match_start -= wsize; 2814717628eSXin LI s->strstart -= wsize; /* we now have strstart >= MAX_DIST */ 2824717628eSXin LI s->block_start -= (long) wsize; 2834717628eSXin LI if (s->insert > s->strstart) 2844717628eSXin LI s->insert = s->strstart; 2854717628eSXin LI slide_hash(s); 2864717628eSXin LI more += wsize; 2874717628eSXin LI } 2884717628eSXin LI if (s->strm->avail_in == 0) break; 2894717628eSXin LI 2904717628eSXin LI /* If there was no sliding: 2914717628eSXin LI * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 && 2924717628eSXin LI * more == window_size - lookahead - strstart 2934717628eSXin LI * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1) 2944717628eSXin LI * => more >= window_size - 2*WSIZE + 2 2954717628eSXin LI * In the BIG_MEM or MMAP case (not yet supported), 2964717628eSXin LI * window_size == input_size + MIN_LOOKAHEAD && 2974717628eSXin LI * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD. 2984717628eSXin LI * Otherwise, window_size == 2*WSIZE so more >= 2. 2994717628eSXin LI * If there was sliding, more >= WSIZE. So in all cases, more >= 2. 3004717628eSXin LI */ 3014717628eSXin LI Assert(more >= 2, "more < 2"); 3024717628eSXin LI 3034717628eSXin LI n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more); 3044717628eSXin LI s->lookahead += n; 3054717628eSXin LI 3064717628eSXin LI /* Initialize the hash value now that we have some input: */ 3074717628eSXin LI if (s->lookahead + s->insert >= MIN_MATCH) { 3084717628eSXin LI uInt str = s->strstart - s->insert; 3094717628eSXin LI s->ins_h = s->window[str]; 3104717628eSXin LI UPDATE_HASH(s, s->ins_h, s->window[str + 1]); 3114717628eSXin LI #if MIN_MATCH != 3 3124717628eSXin LI Call UPDATE_HASH() MIN_MATCH-3 more times 3134717628eSXin LI #endif 3144717628eSXin LI while (s->insert) { 3154717628eSXin LI UPDATE_HASH(s, s->ins_h, s->window[str + MIN_MATCH-1]); 3164717628eSXin LI #ifndef FASTEST 3174717628eSXin LI s->prev[str & s->w_mask] = s->head[s->ins_h]; 3184717628eSXin LI #endif 3194717628eSXin LI s->head[s->ins_h] = (Pos)str; 3204717628eSXin LI str++; 3214717628eSXin LI s->insert--; 3224717628eSXin LI if (s->lookahead + s->insert < MIN_MATCH) 3234717628eSXin LI break; 3244717628eSXin LI } 3254717628eSXin LI } 3264717628eSXin LI /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage, 3274717628eSXin LI * but this is not important since only literal bytes will be emitted. 3284717628eSXin LI */ 3294717628eSXin LI 3304717628eSXin LI } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0); 3314717628eSXin LI 3324717628eSXin LI /* If the WIN_INIT bytes after the end of the current data have never been 3334717628eSXin LI * written, then zero those bytes in order to avoid memory check reports of 3344717628eSXin LI * the use of uninitialized (or uninitialised as Julian writes) bytes by 3354717628eSXin LI * the longest match routines. Update the high water mark for the next 3364717628eSXin LI * time through here. WIN_INIT is set to MAX_MATCH since the longest match 3374717628eSXin LI * routines allow scanning to strstart + MAX_MATCH, ignoring lookahead. 3384717628eSXin LI */ 3394717628eSXin LI if (s->high_water < s->window_size) { 3404717628eSXin LI ulg curr = s->strstart + (ulg)(s->lookahead); 3414717628eSXin LI ulg init; 3424717628eSXin LI 3434717628eSXin LI if (s->high_water < curr) { 3444717628eSXin LI /* Previous high water mark below current data -- zero WIN_INIT 3454717628eSXin LI * bytes or up to end of window, whichever is less. 3464717628eSXin LI */ 3474717628eSXin LI init = s->window_size - curr; 3484717628eSXin LI if (init > WIN_INIT) 3494717628eSXin LI init = WIN_INIT; 3504717628eSXin LI zmemzero(s->window + curr, (unsigned)init); 3514717628eSXin LI s->high_water = curr + init; 3524717628eSXin LI } 3534717628eSXin LI else if (s->high_water < (ulg)curr + WIN_INIT) { 3544717628eSXin LI /* High water mark at or above current data, but below current data 3554717628eSXin LI * plus WIN_INIT -- zero out to current data plus WIN_INIT, or up 3564717628eSXin LI * to end of window, whichever is less. 3574717628eSXin LI */ 3584717628eSXin LI init = (ulg)curr + WIN_INIT - s->high_water; 3594717628eSXin LI if (init > s->window_size - s->high_water) 3604717628eSXin LI init = s->window_size - s->high_water; 3614717628eSXin LI zmemzero(s->window + s->high_water, (unsigned)init); 3624717628eSXin LI s->high_water += init; 3634717628eSXin LI } 3644717628eSXin LI } 3654717628eSXin LI 3664717628eSXin LI Assert((ulg)s->strstart <= s->window_size - MIN_LOOKAHEAD, 3674717628eSXin LI "not enough room for search"); 3684717628eSXin LI } 3694717628eSXin LI 370c9083b85SXin LI /* ========================================================================= */ 3714717628eSXin LI int ZEXPORT deflateInit_(z_streamp strm, int level, const char *version, 3724717628eSXin LI int stream_size) { 373c9083b85SXin LI return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL, 374c9083b85SXin LI Z_DEFAULT_STRATEGY, version, stream_size); 375c9083b85SXin LI /* To do: ignore strm->next_in if we use it as window */ 376c9083b85SXin LI } 377c9083b85SXin LI 378c9083b85SXin LI /* ========================================================================= */ 3794717628eSXin LI int ZEXPORT deflateInit2_(z_streamp strm, int level, int method, 3804717628eSXin LI int windowBits, int memLevel, int strategy, 3814717628eSXin LI const char *version, int stream_size) { 382c9083b85SXin LI deflate_state *s; 383c9083b85SXin LI int wrap = 1; 384c9083b85SXin LI static const char my_version[] = ZLIB_VERSION; 385c9083b85SXin LI 386c9083b85SXin LI if (version == Z_NULL || version[0] != my_version[0] || 387c9083b85SXin LI stream_size != sizeof(z_stream)) { 388c9083b85SXin LI return Z_VERSION_ERROR; 389c9083b85SXin LI } 390c9083b85SXin LI if (strm == Z_NULL) return Z_STREAM_ERROR; 391c9083b85SXin LI 392c9083b85SXin LI strm->msg = Z_NULL; 393c9083b85SXin LI if (strm->zalloc == (alloc_func)0) { 394a15cb219SXin LI #if defined(Z_SOLO) && !defined(_KERNEL) 395c9083b85SXin LI return Z_STREAM_ERROR; 396c9083b85SXin LI #else 397c9083b85SXin LI strm->zalloc = zcalloc; 398c9083b85SXin LI strm->opaque = (voidpf)0; 399c9083b85SXin LI #endif 400c9083b85SXin LI } 401c9083b85SXin LI if (strm->zfree == (free_func)0) 402a15cb219SXin LI #if defined(Z_SOLO) && !defined(_KERNEL) 403c9083b85SXin LI return Z_STREAM_ERROR; 404c9083b85SXin LI #else 405c9083b85SXin LI strm->zfree = zcfree; 406c9083b85SXin LI #endif 407c9083b85SXin LI 408c9083b85SXin LI #ifdef FASTEST 409c9083b85SXin LI if (level != 0) level = 1; 410c9083b85SXin LI #else 411c9083b85SXin LI if (level == Z_DEFAULT_COMPRESSION) level = 6; 412c9083b85SXin LI #endif 413c9083b85SXin LI 414c9083b85SXin LI if (windowBits < 0) { /* suppress zlib wrapper */ 415c9083b85SXin LI wrap = 0; 416e37bb444SXin LI if (windowBits < -15) 417e37bb444SXin LI return Z_STREAM_ERROR; 418c9083b85SXin LI windowBits = -windowBits; 419c9083b85SXin LI } 420c9083b85SXin LI #ifdef GZIP 421c9083b85SXin LI else if (windowBits > 15) { 422c9083b85SXin LI wrap = 2; /* write gzip wrapper instead */ 423c9083b85SXin LI windowBits -= 16; 424c9083b85SXin LI } 425c9083b85SXin LI #endif 426c9083b85SXin LI if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED || 427c9083b85SXin LI windowBits < 8 || windowBits > 15 || level < 0 || level > 9 || 428c9083b85SXin LI strategy < 0 || strategy > Z_FIXED || (windowBits == 8 && wrap != 1)) { 429c9083b85SXin LI return Z_STREAM_ERROR; 430c9083b85SXin LI } 431c9083b85SXin LI if (windowBits == 8) windowBits = 9; /* until 256-byte window bug fixed */ 432c9083b85SXin LI s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state)); 433c9083b85SXin LI if (s == Z_NULL) return Z_MEM_ERROR; 434c9083b85SXin LI strm->state = (struct internal_state FAR *)s; 435c9083b85SXin LI s->strm = strm; 436c9083b85SXin LI s->status = INIT_STATE; /* to pass state test in deflateReset() */ 437c9083b85SXin LI 438c9083b85SXin LI s->wrap = wrap; 439c9083b85SXin LI s->gzhead = Z_NULL; 440c9083b85SXin LI s->w_bits = (uInt)windowBits; 441c9083b85SXin LI s->w_size = 1 << s->w_bits; 442c9083b85SXin LI s->w_mask = s->w_size - 1; 443c9083b85SXin LI 444c9083b85SXin LI s->hash_bits = (uInt)memLevel + 7; 445c9083b85SXin LI s->hash_size = 1 << s->hash_bits; 446c9083b85SXin LI s->hash_mask = s->hash_size - 1; 447c9083b85SXin LI s->hash_shift = ((s->hash_bits + MIN_MATCH-1) / MIN_MATCH); 448c9083b85SXin LI 449c9083b85SXin LI s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte)); 450c9083b85SXin LI s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos)); 451c9083b85SXin LI s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos)); 452c9083b85SXin LI 453c9083b85SXin LI s->high_water = 0; /* nothing written to s->window yet */ 454c9083b85SXin LI 455c9083b85SXin LI s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */ 456c9083b85SXin LI 457cd882207SXin LI /* We overlay pending_buf and sym_buf. This works since the average size 458cd882207SXin LI * for length/distance pairs over any compressed block is assured to be 31 459cd882207SXin LI * bits or less. 460cd882207SXin LI * 461cd882207SXin LI * Analysis: The longest fixed codes are a length code of 8 bits plus 5 462cd882207SXin LI * extra bits, for lengths 131 to 257. The longest fixed distance codes are 463cd882207SXin LI * 5 bits plus 13 extra bits, for distances 16385 to 32768. The longest 464cd882207SXin LI * possible fixed-codes length/distance pair is then 31 bits total. 465cd882207SXin LI * 466cd882207SXin LI * sym_buf starts one-fourth of the way into pending_buf. So there are 467cd882207SXin LI * three bytes in sym_buf for every four bytes in pending_buf. Each symbol 468cd882207SXin LI * in sym_buf is three bytes -- two for the distance and one for the 469cd882207SXin LI * literal/length. As each symbol is consumed, the pointer to the next 470cd882207SXin LI * sym_buf value to read moves forward three bytes. From that symbol, up to 471cd882207SXin LI * 31 bits are written to pending_buf. The closest the written pending_buf 472cd882207SXin LI * bits gets to the next sym_buf symbol to read is just before the last 473cd882207SXin LI * code is written. At that time, 31*(n - 2) bits have been written, just 474cd882207SXin LI * after 24*(n - 2) bits have been consumed from sym_buf. sym_buf starts at 475cd882207SXin LI * 8*n bits into pending_buf. (Note that the symbol buffer fills when n - 1 476cd882207SXin LI * symbols are written.) The closest the writing gets to what is unread is 477cd882207SXin LI * then n + 14 bits. Here n is lit_bufsize, which is 16384 by default, and 478cd882207SXin LI * can range from 128 to 32768. 479cd882207SXin LI * 480cd882207SXin LI * Therefore, at a minimum, there are 142 bits of space between what is 481cd882207SXin LI * written and what is read in the overlain buffers, so the symbols cannot 482cd882207SXin LI * be overwritten by the compressed data. That space is actually 139 bits, 483cd882207SXin LI * due to the three-bit fixed-code block header. 484cd882207SXin LI * 485cd882207SXin LI * That covers the case where either Z_FIXED is specified, forcing fixed 486cd882207SXin LI * codes, or when the use of fixed codes is chosen, because that choice 487cd882207SXin LI * results in a smaller compressed block than dynamic codes. That latter 488cd882207SXin LI * condition then assures that the above analysis also covers all dynamic 489cd882207SXin LI * blocks. A dynamic-code block will only be chosen to be emitted if it has 490cd882207SXin LI * fewer bits than a fixed-code block would for the same set of symbols. 491cd882207SXin LI * Therefore its average symbol length is assured to be less than 31. So 492cd882207SXin LI * the compressed data for a dynamic block also cannot overwrite the 493cd882207SXin LI * symbols from which it is being constructed. 494cd882207SXin LI */ 495cd882207SXin LI 496cd882207SXin LI s->pending_buf = (uchf *) ZALLOC(strm, s->lit_bufsize, 4); 497cd882207SXin LI s->pending_buf_size = (ulg)s->lit_bufsize * 4; 498c9083b85SXin LI 499c9083b85SXin LI if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL || 500c9083b85SXin LI s->pending_buf == Z_NULL) { 501c9083b85SXin LI s->status = FINISH_STATE; 502c9083b85SXin LI strm->msg = ERR_MSG(Z_MEM_ERROR); 503c9083b85SXin LI deflateEnd (strm); 504c9083b85SXin LI return Z_MEM_ERROR; 505c9083b85SXin LI } 506cd882207SXin LI s->sym_buf = s->pending_buf + s->lit_bufsize; 507cd882207SXin LI s->sym_end = (s->lit_bufsize - 1) * 3; 508cd882207SXin LI /* We avoid equality with lit_bufsize*3 because of wraparound at 64K 509cd882207SXin LI * on 16 bit machines and because stored blocks are restricted to 510cd882207SXin LI * 64K-1 bytes. 511cd882207SXin LI */ 512c9083b85SXin LI 513c9083b85SXin LI s->level = level; 514c9083b85SXin LI s->strategy = strategy; 515c9083b85SXin LI s->method = (Byte)method; 516c9083b85SXin LI 517c9083b85SXin LI return deflateReset(strm); 518c9083b85SXin LI } 519c9083b85SXin LI 520c9083b85SXin LI /* ========================================================================= 521c9083b85SXin LI * Check for a valid deflate stream state. Return 0 if ok, 1 if not. 522c9083b85SXin LI */ 5234717628eSXin LI local int deflateStateCheck(z_streamp strm) { 524c9083b85SXin LI deflate_state *s; 525c9083b85SXin LI if (strm == Z_NULL || 526c9083b85SXin LI strm->zalloc == (alloc_func)0 || strm->zfree == (free_func)0) 527c9083b85SXin LI return 1; 528c9083b85SXin LI s = strm->state; 529c9083b85SXin LI if (s == Z_NULL || s->strm != strm || (s->status != INIT_STATE && 530c9083b85SXin LI #ifdef GZIP 531c9083b85SXin LI s->status != GZIP_STATE && 532c9083b85SXin LI #endif 533c9083b85SXin LI s->status != EXTRA_STATE && 534c9083b85SXin LI s->status != NAME_STATE && 535c9083b85SXin LI s->status != COMMENT_STATE && 536c9083b85SXin LI s->status != HCRC_STATE && 537c9083b85SXin LI s->status != BUSY_STATE && 538c9083b85SXin LI s->status != FINISH_STATE)) 539c9083b85SXin LI return 1; 540c9083b85SXin LI return 0; 541c9083b85SXin LI } 542c9083b85SXin LI 543c9083b85SXin LI /* ========================================================================= */ 5444717628eSXin LI int ZEXPORT deflateSetDictionary(z_streamp strm, const Bytef *dictionary, 5454717628eSXin LI uInt dictLength) { 546c9083b85SXin LI deflate_state *s; 547c9083b85SXin LI uInt str, n; 548c9083b85SXin LI int wrap; 549c9083b85SXin LI unsigned avail; 550c9083b85SXin LI z_const unsigned char *next; 551c9083b85SXin LI 552c9083b85SXin LI if (deflateStateCheck(strm) || dictionary == Z_NULL) 553c9083b85SXin LI return Z_STREAM_ERROR; 554c9083b85SXin LI s = strm->state; 555c9083b85SXin LI wrap = s->wrap; 556c9083b85SXin LI if (wrap == 2 || (wrap == 1 && s->status != INIT_STATE) || s->lookahead) 557c9083b85SXin LI return Z_STREAM_ERROR; 558c9083b85SXin LI 559c9083b85SXin LI /* when using zlib wrappers, compute Adler-32 for provided dictionary */ 560c9083b85SXin LI if (wrap == 1) 561c9083b85SXin LI strm->adler = adler32(strm->adler, dictionary, dictLength); 562c9083b85SXin LI s->wrap = 0; /* avoid computing Adler-32 in read_buf */ 563c9083b85SXin LI 564c9083b85SXin LI /* if dictionary would fill window, just replace the history */ 565c9083b85SXin LI if (dictLength >= s->w_size) { 566c9083b85SXin LI if (wrap == 0) { /* already empty otherwise */ 567c9083b85SXin LI CLEAR_HASH(s); 568c9083b85SXin LI s->strstart = 0; 569c9083b85SXin LI s->block_start = 0L; 570c9083b85SXin LI s->insert = 0; 571c9083b85SXin LI } 572c9083b85SXin LI dictionary += dictLength - s->w_size; /* use the tail */ 573c9083b85SXin LI dictLength = s->w_size; 574c9083b85SXin LI } 575c9083b85SXin LI 576c9083b85SXin LI /* insert dictionary into window and hash */ 577c9083b85SXin LI avail = strm->avail_in; 578c9083b85SXin LI next = strm->next_in; 579c9083b85SXin LI strm->avail_in = dictLength; 580c9083b85SXin LI strm->next_in = (z_const Bytef *)dictionary; 581c9083b85SXin LI fill_window(s); 582c9083b85SXin LI while (s->lookahead >= MIN_MATCH) { 583c9083b85SXin LI str = s->strstart; 584c9083b85SXin LI n = s->lookahead - (MIN_MATCH-1); 585c9083b85SXin LI do { 586c9083b85SXin LI UPDATE_HASH(s, s->ins_h, s->window[str + MIN_MATCH-1]); 587c9083b85SXin LI #ifndef FASTEST 588c9083b85SXin LI s->prev[str & s->w_mask] = s->head[s->ins_h]; 589c9083b85SXin LI #endif 590c9083b85SXin LI s->head[s->ins_h] = (Pos)str; 591c9083b85SXin LI str++; 592c9083b85SXin LI } while (--n); 593c9083b85SXin LI s->strstart = str; 594c9083b85SXin LI s->lookahead = MIN_MATCH-1; 595c9083b85SXin LI fill_window(s); 596c9083b85SXin LI } 597c9083b85SXin LI s->strstart += s->lookahead; 598c9083b85SXin LI s->block_start = (long)s->strstart; 599c9083b85SXin LI s->insert = s->lookahead; 600c9083b85SXin LI s->lookahead = 0; 601c9083b85SXin LI s->match_length = s->prev_length = MIN_MATCH-1; 602c9083b85SXin LI s->match_available = 0; 603c9083b85SXin LI strm->next_in = next; 604c9083b85SXin LI strm->avail_in = avail; 605c9083b85SXin LI s->wrap = wrap; 606c9083b85SXin LI return Z_OK; 607c9083b85SXin LI } 608c9083b85SXin LI 609c9083b85SXin LI /* ========================================================================= */ 6104717628eSXin LI int ZEXPORT deflateGetDictionary(z_streamp strm, Bytef *dictionary, 6114717628eSXin LI uInt *dictLength) { 612c9083b85SXin LI deflate_state *s; 613c9083b85SXin LI uInt len; 614c9083b85SXin LI 615c9083b85SXin LI if (deflateStateCheck(strm)) 616c9083b85SXin LI return Z_STREAM_ERROR; 617c9083b85SXin LI s = strm->state; 618c9083b85SXin LI len = s->strstart + s->lookahead; 619c9083b85SXin LI if (len > s->w_size) 620c9083b85SXin LI len = s->w_size; 621c9083b85SXin LI if (dictionary != Z_NULL && len) 622c9083b85SXin LI zmemcpy(dictionary, s->window + s->strstart + s->lookahead - len, len); 623c9083b85SXin LI if (dictLength != Z_NULL) 624c9083b85SXin LI *dictLength = len; 625c9083b85SXin LI return Z_OK; 626c9083b85SXin LI } 627c9083b85SXin LI 628c9083b85SXin LI /* ========================================================================= */ 6294717628eSXin LI int ZEXPORT deflateResetKeep(z_streamp strm) { 630c9083b85SXin LI deflate_state *s; 631c9083b85SXin LI 632c9083b85SXin LI if (deflateStateCheck(strm)) { 633c9083b85SXin LI return Z_STREAM_ERROR; 634c9083b85SXin LI } 635c9083b85SXin LI 636c9083b85SXin LI strm->total_in = strm->total_out = 0; 637c9083b85SXin LI strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */ 638c9083b85SXin LI strm->data_type = Z_UNKNOWN; 639c9083b85SXin LI 640c9083b85SXin LI s = (deflate_state *)strm->state; 641c9083b85SXin LI s->pending = 0; 642c9083b85SXin LI s->pending_out = s->pending_buf; 643c9083b85SXin LI 644c9083b85SXin LI if (s->wrap < 0) { 645c9083b85SXin LI s->wrap = -s->wrap; /* was made negative by deflate(..., Z_FINISH); */ 646c9083b85SXin LI } 647c9083b85SXin LI s->status = 648c9083b85SXin LI #ifdef GZIP 649c9083b85SXin LI s->wrap == 2 ? GZIP_STATE : 650c9083b85SXin LI #endif 651cd882207SXin LI INIT_STATE; 652c9083b85SXin LI strm->adler = 653c9083b85SXin LI #ifdef GZIP 654c9083b85SXin LI s->wrap == 2 ? crc32(0L, Z_NULL, 0) : 655c9083b85SXin LI #endif 656c9083b85SXin LI adler32(0L, Z_NULL, 0); 657c9083b85SXin LI s->last_flush = -2; 658c9083b85SXin LI 659c9083b85SXin LI _tr_init(s); 660c9083b85SXin LI 661c9083b85SXin LI return Z_OK; 662c9083b85SXin LI } 663c9083b85SXin LI 6644717628eSXin LI /* =========================================================================== 6654717628eSXin LI * Initialize the "longest match" routines for a new zlib stream 6664717628eSXin LI */ 6674717628eSXin LI local void lm_init(deflate_state *s) { 6684717628eSXin LI s->window_size = (ulg)2L*s->w_size; 6694717628eSXin LI 6704717628eSXin LI CLEAR_HASH(s); 6714717628eSXin LI 6724717628eSXin LI /* Set the default configuration parameters: 6734717628eSXin LI */ 6744717628eSXin LI s->max_lazy_match = configuration_table[s->level].max_lazy; 6754717628eSXin LI s->good_match = configuration_table[s->level].good_length; 6764717628eSXin LI s->nice_match = configuration_table[s->level].nice_length; 6774717628eSXin LI s->max_chain_length = configuration_table[s->level].max_chain; 6784717628eSXin LI 6794717628eSXin LI s->strstart = 0; 6804717628eSXin LI s->block_start = 0L; 6814717628eSXin LI s->lookahead = 0; 6824717628eSXin LI s->insert = 0; 6834717628eSXin LI s->match_length = s->prev_length = MIN_MATCH-1; 6844717628eSXin LI s->match_available = 0; 6854717628eSXin LI s->ins_h = 0; 6864717628eSXin LI } 6874717628eSXin LI 688c9083b85SXin LI /* ========================================================================= */ 6894717628eSXin LI int ZEXPORT deflateReset(z_streamp strm) { 690c9083b85SXin LI int ret; 691c9083b85SXin LI 692c9083b85SXin LI ret = deflateResetKeep(strm); 693c9083b85SXin LI if (ret == Z_OK) 694c9083b85SXin LI lm_init(strm->state); 695c9083b85SXin LI return ret; 696c9083b85SXin LI } 697c9083b85SXin LI 698c9083b85SXin LI /* ========================================================================= */ 6994717628eSXin LI int ZEXPORT deflateSetHeader(z_streamp strm, gz_headerp head) { 700c9083b85SXin LI if (deflateStateCheck(strm) || strm->state->wrap != 2) 701c9083b85SXin LI return Z_STREAM_ERROR; 702c9083b85SXin LI strm->state->gzhead = head; 703c9083b85SXin LI return Z_OK; 704c9083b85SXin LI } 705c9083b85SXin LI 706c9083b85SXin LI /* ========================================================================= */ 7074717628eSXin LI int ZEXPORT deflatePending(z_streamp strm, unsigned *pending, int *bits) { 708c9083b85SXin LI if (deflateStateCheck(strm)) return Z_STREAM_ERROR; 709c9083b85SXin LI if (pending != Z_NULL) 710c9083b85SXin LI *pending = strm->state->pending; 711c9083b85SXin LI if (bits != Z_NULL) 712c9083b85SXin LI *bits = strm->state->bi_valid; 713c9083b85SXin LI return Z_OK; 714c9083b85SXin LI } 715c9083b85SXin LI 716c9083b85SXin LI /* ========================================================================= */ 7174717628eSXin LI int ZEXPORT deflatePrime(z_streamp strm, int bits, int value) { 718c9083b85SXin LI deflate_state *s; 719c9083b85SXin LI int put; 720c9083b85SXin LI 721c9083b85SXin LI if (deflateStateCheck(strm)) return Z_STREAM_ERROR; 722c9083b85SXin LI s = strm->state; 723cd882207SXin LI if (bits < 0 || bits > 16 || 724cd882207SXin LI s->sym_buf < s->pending_out + ((Buf_size + 7) >> 3)) 725c9083b85SXin LI return Z_BUF_ERROR; 726c9083b85SXin LI do { 727c9083b85SXin LI put = Buf_size - s->bi_valid; 728c9083b85SXin LI if (put > bits) 729c9083b85SXin LI put = bits; 730c9083b85SXin LI s->bi_buf |= (ush)((value & ((1 << put) - 1)) << s->bi_valid); 731c9083b85SXin LI s->bi_valid += put; 732c9083b85SXin LI _tr_flush_bits(s); 733c9083b85SXin LI value >>= put; 734c9083b85SXin LI bits -= put; 735c9083b85SXin LI } while (bits); 736c9083b85SXin LI return Z_OK; 737c9083b85SXin LI } 738c9083b85SXin LI 739c9083b85SXin LI /* ========================================================================= */ 7404717628eSXin LI int ZEXPORT deflateParams(z_streamp strm, int level, int strategy) { 741c9083b85SXin LI deflate_state *s; 742c9083b85SXin LI compress_func func; 743c9083b85SXin LI 744c9083b85SXin LI if (deflateStateCheck(strm)) return Z_STREAM_ERROR; 745c9083b85SXin LI s = strm->state; 746c9083b85SXin LI 747c9083b85SXin LI #ifdef FASTEST 748c9083b85SXin LI if (level != 0) level = 1; 749c9083b85SXin LI #else 750c9083b85SXin LI if (level == Z_DEFAULT_COMPRESSION) level = 6; 751c9083b85SXin LI #endif 752c9083b85SXin LI if (level < 0 || level > 9 || strategy < 0 || strategy > Z_FIXED) { 753c9083b85SXin LI return Z_STREAM_ERROR; 754c9083b85SXin LI } 755c9083b85SXin LI func = configuration_table[s->level].func; 756c9083b85SXin LI 757c9083b85SXin LI if ((strategy != s->strategy || func != configuration_table[level].func) && 758c9083b85SXin LI s->last_flush != -2) { 759c9083b85SXin LI /* Flush the last buffer: */ 760c9083b85SXin LI int err = deflate(strm, Z_BLOCK); 761c9083b85SXin LI if (err == Z_STREAM_ERROR) 762c9083b85SXin LI return err; 763c9083b85SXin LI if (strm->avail_in || (s->strstart - s->block_start) + s->lookahead) 764c9083b85SXin LI return Z_BUF_ERROR; 765c9083b85SXin LI } 766c9083b85SXin LI if (s->level != level) { 767c9083b85SXin LI if (s->level == 0 && s->matches != 0) { 768c9083b85SXin LI if (s->matches == 1) 769c9083b85SXin LI slide_hash(s); 770c9083b85SXin LI else 771c9083b85SXin LI CLEAR_HASH(s); 772c9083b85SXin LI s->matches = 0; 773c9083b85SXin LI } 774c9083b85SXin LI s->level = level; 775c9083b85SXin LI s->max_lazy_match = configuration_table[level].max_lazy; 776c9083b85SXin LI s->good_match = configuration_table[level].good_length; 777c9083b85SXin LI s->nice_match = configuration_table[level].nice_length; 778c9083b85SXin LI s->max_chain_length = configuration_table[level].max_chain; 779c9083b85SXin LI } 780c9083b85SXin LI s->strategy = strategy; 781c9083b85SXin LI return Z_OK; 782c9083b85SXin LI } 783c9083b85SXin LI 784c9083b85SXin LI /* ========================================================================= */ 7854717628eSXin LI int ZEXPORT deflateTune(z_streamp strm, int good_length, int max_lazy, 7864717628eSXin LI int nice_length, int max_chain) { 787c9083b85SXin LI deflate_state *s; 788c9083b85SXin LI 789c9083b85SXin LI if (deflateStateCheck(strm)) return Z_STREAM_ERROR; 790c9083b85SXin LI s = strm->state; 791c9083b85SXin LI s->good_match = (uInt)good_length; 792c9083b85SXin LI s->max_lazy_match = (uInt)max_lazy; 793c9083b85SXin LI s->nice_match = nice_length; 794c9083b85SXin LI s->max_chain_length = (uInt)max_chain; 795c9083b85SXin LI return Z_OK; 796c9083b85SXin LI } 797c9083b85SXin LI 798c9083b85SXin LI /* ========================================================================= 799e37bb444SXin LI * For the default windowBits of 15 and memLevel of 8, this function returns a 800e37bb444SXin LI * close to exact, as well as small, upper bound on the compressed size. This 801e37bb444SXin LI * is an expansion of ~0.03%, plus a small constant. 802c9083b85SXin LI * 803e37bb444SXin LI * For any setting other than those defaults for windowBits and memLevel, one 804e37bb444SXin LI * of two worst case bounds is returned. This is at most an expansion of ~4% or 805e37bb444SXin LI * ~13%, plus a small constant. 806c9083b85SXin LI * 807e37bb444SXin LI * Both the 0.03% and 4% derive from the overhead of stored blocks. The first 808e37bb444SXin LI * one is for stored blocks of 16383 bytes (memLevel == 8), whereas the second 809e37bb444SXin LI * is for stored blocks of 127 bytes (the worst case memLevel == 1). The 810e37bb444SXin LI * expansion results from five bytes of header for each stored block. 811e37bb444SXin LI * 812e37bb444SXin LI * The larger expansion of 13% results from a window size less than or equal to 813e37bb444SXin LI * the symbols buffer size (windowBits <= memLevel + 7). In that case some of 814e37bb444SXin LI * the data being compressed may have slid out of the sliding window, impeding 815e37bb444SXin LI * a stored block from being emitted. Then the only choice is a fixed or 816e37bb444SXin LI * dynamic block, where a fixed block limits the maximum expansion to 9 bits 817e37bb444SXin LI * per 8-bit byte, plus 10 bits for every block. The smallest block size for 818e37bb444SXin LI * which this can occur is 255 (memLevel == 2). 819e37bb444SXin LI * 820e37bb444SXin LI * Shifts are used to approximate divisions, for speed. 821c9083b85SXin LI */ 8224717628eSXin LI uLong ZEXPORT deflateBound(z_streamp strm, uLong sourceLen) { 823c9083b85SXin LI deflate_state *s; 824e37bb444SXin LI uLong fixedlen, storelen, wraplen; 825c9083b85SXin LI 826e37bb444SXin LI /* upper bound for fixed blocks with 9-bit literals and length 255 827e37bb444SXin LI (memLevel == 2, which is the lowest that may not use stored blocks) -- 828e37bb444SXin LI ~13% overhead plus a small constant */ 829e37bb444SXin LI fixedlen = sourceLen + (sourceLen >> 3) + (sourceLen >> 8) + 830e37bb444SXin LI (sourceLen >> 9) + 4; 831c9083b85SXin LI 832e37bb444SXin LI /* upper bound for stored blocks with length 127 (memLevel == 1) -- 833e37bb444SXin LI ~4% overhead plus a small constant */ 834e37bb444SXin LI storelen = sourceLen + (sourceLen >> 5) + (sourceLen >> 7) + 835e37bb444SXin LI (sourceLen >> 11) + 7; 836e37bb444SXin LI 837e37bb444SXin LI /* if can't get parameters, return larger bound plus a zlib wrapper */ 838c9083b85SXin LI if (deflateStateCheck(strm)) 839e37bb444SXin LI return (fixedlen > storelen ? fixedlen : storelen) + 6; 840c9083b85SXin LI 841c9083b85SXin LI /* compute wrapper length */ 842c9083b85SXin LI s = strm->state; 843c9083b85SXin LI switch (s->wrap) { 844c9083b85SXin LI case 0: /* raw deflate */ 845c9083b85SXin LI wraplen = 0; 846c9083b85SXin LI break; 847c9083b85SXin LI case 1: /* zlib wrapper */ 848c9083b85SXin LI wraplen = 6 + (s->strstart ? 4 : 0); 849c9083b85SXin LI break; 850c9083b85SXin LI #ifdef GZIP 851c9083b85SXin LI case 2: /* gzip wrapper */ 852c9083b85SXin LI wraplen = 18; 853c9083b85SXin LI if (s->gzhead != Z_NULL) { /* user-supplied gzip header */ 854c9083b85SXin LI Bytef *str; 855c9083b85SXin LI if (s->gzhead->extra != Z_NULL) 856c9083b85SXin LI wraplen += 2 + s->gzhead->extra_len; 857c9083b85SXin LI str = s->gzhead->name; 858c9083b85SXin LI if (str != Z_NULL) 859c9083b85SXin LI do { 860c9083b85SXin LI wraplen++; 861c9083b85SXin LI } while (*str++); 862c9083b85SXin LI str = s->gzhead->comment; 863c9083b85SXin LI if (str != Z_NULL) 864c9083b85SXin LI do { 865c9083b85SXin LI wraplen++; 866c9083b85SXin LI } while (*str++); 867c9083b85SXin LI if (s->gzhead->hcrc) 868c9083b85SXin LI wraplen += 2; 869c9083b85SXin LI } 870c9083b85SXin LI break; 871c9083b85SXin LI #endif 872c9083b85SXin LI default: /* for compiler happiness */ 873c9083b85SXin LI wraplen = 6; 874c9083b85SXin LI } 875c9083b85SXin LI 876e37bb444SXin LI /* if not default parameters, return one of the conservative bounds */ 877c9083b85SXin LI if (s->w_bits != 15 || s->hash_bits != 8 + 7) 8784717628eSXin LI return (s->w_bits <= s->hash_bits && s->level ? fixedlen : storelen) + 8794717628eSXin LI wraplen; 880c9083b85SXin LI 881e37bb444SXin LI /* default settings: return tight bound for that case -- ~0.03% overhead 882e37bb444SXin LI plus a small constant */ 883c9083b85SXin LI return sourceLen + (sourceLen >> 12) + (sourceLen >> 14) + 884c9083b85SXin LI (sourceLen >> 25) + 13 - 6 + wraplen; 885c9083b85SXin LI } 886c9083b85SXin LI 887c9083b85SXin LI /* ========================================================================= 888c9083b85SXin LI * Put a short in the pending buffer. The 16-bit value is put in MSB order. 889c9083b85SXin LI * IN assertion: the stream state is correct and there is enough room in 890c9083b85SXin LI * pending_buf. 891c9083b85SXin LI */ 8924717628eSXin LI local void putShortMSB(deflate_state *s, uInt b) { 893c9083b85SXin LI put_byte(s, (Byte)(b >> 8)); 894c9083b85SXin LI put_byte(s, (Byte)(b & 0xff)); 895c9083b85SXin LI } 896c9083b85SXin LI 897c9083b85SXin LI /* ========================================================================= 898c9083b85SXin LI * Flush as much pending output as possible. All deflate() output, except for 899c9083b85SXin LI * some deflate_stored() output, goes through this function so some 900c9083b85SXin LI * applications may wish to modify it to avoid allocating a large 901c9083b85SXin LI * strm->next_out buffer and copying into it. (See also read_buf()). 902c9083b85SXin LI */ 9034717628eSXin LI local void flush_pending(z_streamp strm) { 904c9083b85SXin LI unsigned len; 905c9083b85SXin LI deflate_state *s = strm->state; 906c9083b85SXin LI 907c9083b85SXin LI _tr_flush_bits(s); 908c9083b85SXin LI len = s->pending; 909c9083b85SXin LI if (len > strm->avail_out) len = strm->avail_out; 910c9083b85SXin LI if (len == 0) return; 911c9083b85SXin LI 912c9083b85SXin LI zmemcpy(strm->next_out, s->pending_out, len); 913c9083b85SXin LI strm->next_out += len; 914c9083b85SXin LI s->pending_out += len; 915c9083b85SXin LI strm->total_out += len; 916c9083b85SXin LI strm->avail_out -= len; 917c9083b85SXin LI s->pending -= len; 918c9083b85SXin LI if (s->pending == 0) { 919c9083b85SXin LI s->pending_out = s->pending_buf; 920c9083b85SXin LI } 921c9083b85SXin LI } 922c9083b85SXin LI 923c9083b85SXin LI /* =========================================================================== 924c9083b85SXin LI * Update the header CRC with the bytes s->pending_buf[beg..s->pending - 1]. 925c9083b85SXin LI */ 926c9083b85SXin LI #define HCRC_UPDATE(beg) \ 927c9083b85SXin LI do { \ 928c9083b85SXin LI if (s->gzhead->hcrc && s->pending > (beg)) \ 929c9083b85SXin LI strm->adler = crc32(strm->adler, s->pending_buf + (beg), \ 930c9083b85SXin LI s->pending - (beg)); \ 931c9083b85SXin LI } while (0) 932c9083b85SXin LI 933c9083b85SXin LI /* ========================================================================= */ 9344717628eSXin LI int ZEXPORT deflate(z_streamp strm, int flush) { 935c9083b85SXin LI int old_flush; /* value of flush param for previous deflate call */ 936c9083b85SXin LI deflate_state *s; 937c9083b85SXin LI 938c9083b85SXin LI if (deflateStateCheck(strm) || flush > Z_BLOCK || flush < 0) { 939c9083b85SXin LI return Z_STREAM_ERROR; 940c9083b85SXin LI } 941c9083b85SXin LI s = strm->state; 942c9083b85SXin LI 943c9083b85SXin LI if (strm->next_out == Z_NULL || 944c9083b85SXin LI (strm->avail_in != 0 && strm->next_in == Z_NULL) || 945c9083b85SXin LI (s->status == FINISH_STATE && flush != Z_FINISH)) { 946c9083b85SXin LI ERR_RETURN(strm, Z_STREAM_ERROR); 947c9083b85SXin LI } 948c9083b85SXin LI if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR); 949c9083b85SXin LI 950c9083b85SXin LI old_flush = s->last_flush; 951c9083b85SXin LI s->last_flush = flush; 952c9083b85SXin LI 953c9083b85SXin LI /* Flush as much pending output as possible */ 954c9083b85SXin LI if (s->pending != 0) { 955c9083b85SXin LI flush_pending(strm); 956c9083b85SXin LI if (strm->avail_out == 0) { 957c9083b85SXin LI /* Since avail_out is 0, deflate will be called again with 958c9083b85SXin LI * more output space, but possibly with both pending and 959c9083b85SXin LI * avail_in equal to zero. There won't be anything to do, 960c9083b85SXin LI * but this is not an error situation so make sure we 961c9083b85SXin LI * return OK instead of BUF_ERROR at next call of deflate: 962c9083b85SXin LI */ 963c9083b85SXin LI s->last_flush = -1; 964c9083b85SXin LI return Z_OK; 965c9083b85SXin LI } 966c9083b85SXin LI 967c9083b85SXin LI /* Make sure there is something to do and avoid duplicate consecutive 968c9083b85SXin LI * flushes. For repeated and useless calls with Z_FINISH, we keep 969c9083b85SXin LI * returning Z_STREAM_END instead of Z_BUF_ERROR. 970c9083b85SXin LI */ 971c9083b85SXin LI } else if (strm->avail_in == 0 && RANK(flush) <= RANK(old_flush) && 972c9083b85SXin LI flush != Z_FINISH) { 973c9083b85SXin LI ERR_RETURN(strm, Z_BUF_ERROR); 974c9083b85SXin LI } 975c9083b85SXin LI 976c9083b85SXin LI /* User must not provide more input after the first FINISH: */ 977c9083b85SXin LI if (s->status == FINISH_STATE && strm->avail_in != 0) { 978c9083b85SXin LI ERR_RETURN(strm, Z_BUF_ERROR); 979c9083b85SXin LI } 980c9083b85SXin LI 981c9083b85SXin LI /* Write the header */ 982cd882207SXin LI if (s->status == INIT_STATE && s->wrap == 0) 983cd882207SXin LI s->status = BUSY_STATE; 984c9083b85SXin LI if (s->status == INIT_STATE) { 985c9083b85SXin LI /* zlib header */ 986c9083b85SXin LI uInt header = (Z_DEFLATED + ((s->w_bits - 8) << 4)) << 8; 987c9083b85SXin LI uInt level_flags; 988c9083b85SXin LI 989c9083b85SXin LI if (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2) 990c9083b85SXin LI level_flags = 0; 991c9083b85SXin LI else if (s->level < 6) 992c9083b85SXin LI level_flags = 1; 993c9083b85SXin LI else if (s->level == 6) 994c9083b85SXin LI level_flags = 2; 995c9083b85SXin LI else 996c9083b85SXin LI level_flags = 3; 997c9083b85SXin LI header |= (level_flags << 6); 998c9083b85SXin LI if (s->strstart != 0) header |= PRESET_DICT; 999c9083b85SXin LI header += 31 - (header % 31); 1000c9083b85SXin LI 1001c9083b85SXin LI putShortMSB(s, header); 1002c9083b85SXin LI 1003c9083b85SXin LI /* Save the adler32 of the preset dictionary: */ 1004c9083b85SXin LI if (s->strstart != 0) { 1005c9083b85SXin LI putShortMSB(s, (uInt)(strm->adler >> 16)); 1006c9083b85SXin LI putShortMSB(s, (uInt)(strm->adler & 0xffff)); 1007c9083b85SXin LI } 1008c9083b85SXin LI strm->adler = adler32(0L, Z_NULL, 0); 1009c9083b85SXin LI s->status = BUSY_STATE; 1010c9083b85SXin LI 1011c9083b85SXin LI /* Compression must start with an empty pending buffer */ 1012c9083b85SXin LI flush_pending(strm); 1013c9083b85SXin LI if (s->pending != 0) { 1014c9083b85SXin LI s->last_flush = -1; 1015c9083b85SXin LI return Z_OK; 1016c9083b85SXin LI } 1017c9083b85SXin LI } 1018c9083b85SXin LI #ifdef GZIP 1019c9083b85SXin LI if (s->status == GZIP_STATE) { 1020c9083b85SXin LI /* gzip header */ 1021c9083b85SXin LI strm->adler = crc32(0L, Z_NULL, 0); 1022c9083b85SXin LI put_byte(s, 31); 1023c9083b85SXin LI put_byte(s, 139); 1024c9083b85SXin LI put_byte(s, 8); 1025c9083b85SXin LI if (s->gzhead == Z_NULL) { 1026c9083b85SXin LI put_byte(s, 0); 1027c9083b85SXin LI put_byte(s, 0); 1028c9083b85SXin LI put_byte(s, 0); 1029c9083b85SXin LI put_byte(s, 0); 1030c9083b85SXin LI put_byte(s, 0); 1031c9083b85SXin LI put_byte(s, s->level == 9 ? 2 : 1032c9083b85SXin LI (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ? 1033c9083b85SXin LI 4 : 0)); 1034c9083b85SXin LI put_byte(s, OS_CODE); 1035c9083b85SXin LI s->status = BUSY_STATE; 1036c9083b85SXin LI 1037c9083b85SXin LI /* Compression must start with an empty pending buffer */ 1038c9083b85SXin LI flush_pending(strm); 1039c9083b85SXin LI if (s->pending != 0) { 1040c9083b85SXin LI s->last_flush = -1; 1041c9083b85SXin LI return Z_OK; 1042c9083b85SXin LI } 1043c9083b85SXin LI } 1044c9083b85SXin LI else { 1045c9083b85SXin LI put_byte(s, (s->gzhead->text ? 1 : 0) + 1046c9083b85SXin LI (s->gzhead->hcrc ? 2 : 0) + 1047c9083b85SXin LI (s->gzhead->extra == Z_NULL ? 0 : 4) + 1048c9083b85SXin LI (s->gzhead->name == Z_NULL ? 0 : 8) + 1049c9083b85SXin LI (s->gzhead->comment == Z_NULL ? 0 : 16) 1050c9083b85SXin LI ); 1051c9083b85SXin LI put_byte(s, (Byte)(s->gzhead->time & 0xff)); 1052c9083b85SXin LI put_byte(s, (Byte)((s->gzhead->time >> 8) & 0xff)); 1053c9083b85SXin LI put_byte(s, (Byte)((s->gzhead->time >> 16) & 0xff)); 1054c9083b85SXin LI put_byte(s, (Byte)((s->gzhead->time >> 24) & 0xff)); 1055c9083b85SXin LI put_byte(s, s->level == 9 ? 2 : 1056c9083b85SXin LI (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ? 1057c9083b85SXin LI 4 : 0)); 1058c9083b85SXin LI put_byte(s, s->gzhead->os & 0xff); 1059c9083b85SXin LI if (s->gzhead->extra != Z_NULL) { 1060c9083b85SXin LI put_byte(s, s->gzhead->extra_len & 0xff); 1061c9083b85SXin LI put_byte(s, (s->gzhead->extra_len >> 8) & 0xff); 1062c9083b85SXin LI } 1063c9083b85SXin LI if (s->gzhead->hcrc) 1064c9083b85SXin LI strm->adler = crc32(strm->adler, s->pending_buf, 1065c9083b85SXin LI s->pending); 1066c9083b85SXin LI s->gzindex = 0; 1067c9083b85SXin LI s->status = EXTRA_STATE; 1068c9083b85SXin LI } 1069c9083b85SXin LI } 1070c9083b85SXin LI if (s->status == EXTRA_STATE) { 1071c9083b85SXin LI if (s->gzhead->extra != Z_NULL) { 1072c9083b85SXin LI ulg beg = s->pending; /* start of bytes to update crc */ 1073c9083b85SXin LI uInt left = (s->gzhead->extra_len & 0xffff) - s->gzindex; 1074c9083b85SXin LI while (s->pending + left > s->pending_buf_size) { 1075c9083b85SXin LI uInt copy = s->pending_buf_size - s->pending; 1076c9083b85SXin LI zmemcpy(s->pending_buf + s->pending, 1077c9083b85SXin LI s->gzhead->extra + s->gzindex, copy); 1078c9083b85SXin LI s->pending = s->pending_buf_size; 1079c9083b85SXin LI HCRC_UPDATE(beg); 1080c9083b85SXin LI s->gzindex += copy; 1081c9083b85SXin LI flush_pending(strm); 1082c9083b85SXin LI if (s->pending != 0) { 1083c9083b85SXin LI s->last_flush = -1; 1084c9083b85SXin LI return Z_OK; 1085c9083b85SXin LI } 1086c9083b85SXin LI beg = 0; 1087c9083b85SXin LI left -= copy; 1088c9083b85SXin LI } 1089c9083b85SXin LI zmemcpy(s->pending_buf + s->pending, 1090c9083b85SXin LI s->gzhead->extra + s->gzindex, left); 1091c9083b85SXin LI s->pending += left; 1092c9083b85SXin LI HCRC_UPDATE(beg); 1093c9083b85SXin LI s->gzindex = 0; 1094c9083b85SXin LI } 1095c9083b85SXin LI s->status = NAME_STATE; 1096c9083b85SXin LI } 1097c9083b85SXin LI if (s->status == NAME_STATE) { 1098c9083b85SXin LI if (s->gzhead->name != Z_NULL) { 1099c9083b85SXin LI ulg beg = s->pending; /* start of bytes to update crc */ 1100c9083b85SXin LI int val; 1101c9083b85SXin LI do { 1102c9083b85SXin LI if (s->pending == s->pending_buf_size) { 1103c9083b85SXin LI HCRC_UPDATE(beg); 1104c9083b85SXin LI flush_pending(strm); 1105c9083b85SXin LI if (s->pending != 0) { 1106c9083b85SXin LI s->last_flush = -1; 1107c9083b85SXin LI return Z_OK; 1108c9083b85SXin LI } 1109c9083b85SXin LI beg = 0; 1110c9083b85SXin LI } 1111c9083b85SXin LI val = s->gzhead->name[s->gzindex++]; 1112c9083b85SXin LI put_byte(s, val); 1113c9083b85SXin LI } while (val != 0); 1114c9083b85SXin LI HCRC_UPDATE(beg); 1115c9083b85SXin LI s->gzindex = 0; 1116c9083b85SXin LI } 1117c9083b85SXin LI s->status = COMMENT_STATE; 1118c9083b85SXin LI } 1119c9083b85SXin LI if (s->status == COMMENT_STATE) { 1120c9083b85SXin LI if (s->gzhead->comment != Z_NULL) { 1121c9083b85SXin LI ulg beg = s->pending; /* start of bytes to update crc */ 1122c9083b85SXin LI int val; 1123c9083b85SXin LI do { 1124c9083b85SXin LI if (s->pending == s->pending_buf_size) { 1125c9083b85SXin LI HCRC_UPDATE(beg); 1126c9083b85SXin LI flush_pending(strm); 1127c9083b85SXin LI if (s->pending != 0) { 1128c9083b85SXin LI s->last_flush = -1; 1129c9083b85SXin LI return Z_OK; 1130c9083b85SXin LI } 1131c9083b85SXin LI beg = 0; 1132c9083b85SXin LI } 1133c9083b85SXin LI val = s->gzhead->comment[s->gzindex++]; 1134c9083b85SXin LI put_byte(s, val); 1135c9083b85SXin LI } while (val != 0); 1136c9083b85SXin LI HCRC_UPDATE(beg); 1137c9083b85SXin LI } 1138c9083b85SXin LI s->status = HCRC_STATE; 1139c9083b85SXin LI } 1140c9083b85SXin LI if (s->status == HCRC_STATE) { 1141c9083b85SXin LI if (s->gzhead->hcrc) { 1142c9083b85SXin LI if (s->pending + 2 > s->pending_buf_size) { 1143c9083b85SXin LI flush_pending(strm); 1144c9083b85SXin LI if (s->pending != 0) { 1145c9083b85SXin LI s->last_flush = -1; 1146c9083b85SXin LI return Z_OK; 1147c9083b85SXin LI } 1148c9083b85SXin LI } 1149c9083b85SXin LI put_byte(s, (Byte)(strm->adler & 0xff)); 1150c9083b85SXin LI put_byte(s, (Byte)((strm->adler >> 8) & 0xff)); 1151c9083b85SXin LI strm->adler = crc32(0L, Z_NULL, 0); 1152c9083b85SXin LI } 1153c9083b85SXin LI s->status = BUSY_STATE; 1154c9083b85SXin LI 1155c9083b85SXin LI /* Compression must start with an empty pending buffer */ 1156c9083b85SXin LI flush_pending(strm); 1157c9083b85SXin LI if (s->pending != 0) { 1158c9083b85SXin LI s->last_flush = -1; 1159c9083b85SXin LI return Z_OK; 1160c9083b85SXin LI } 1161c9083b85SXin LI } 1162c9083b85SXin LI #endif 1163c9083b85SXin LI 1164c9083b85SXin LI /* Start a new block or continue the current one. 1165c9083b85SXin LI */ 1166c9083b85SXin LI if (strm->avail_in != 0 || s->lookahead != 0 || 1167c9083b85SXin LI (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) { 1168c9083b85SXin LI block_state bstate; 1169c9083b85SXin LI 1170c9083b85SXin LI bstate = s->level == 0 ? deflate_stored(s, flush) : 1171c9083b85SXin LI s->strategy == Z_HUFFMAN_ONLY ? deflate_huff(s, flush) : 1172c9083b85SXin LI s->strategy == Z_RLE ? deflate_rle(s, flush) : 1173c9083b85SXin LI (*(configuration_table[s->level].func))(s, flush); 1174c9083b85SXin LI 1175c9083b85SXin LI if (bstate == finish_started || bstate == finish_done) { 1176c9083b85SXin LI s->status = FINISH_STATE; 1177c9083b85SXin LI } 1178c9083b85SXin LI if (bstate == need_more || bstate == finish_started) { 1179c9083b85SXin LI if (strm->avail_out == 0) { 1180c9083b85SXin LI s->last_flush = -1; /* avoid BUF_ERROR next call, see above */ 1181c9083b85SXin LI } 1182c9083b85SXin LI return Z_OK; 1183c9083b85SXin LI /* If flush != Z_NO_FLUSH && avail_out == 0, the next call 1184c9083b85SXin LI * of deflate should use the same flush parameter to make sure 1185c9083b85SXin LI * that the flush is complete. So we don't have to output an 1186c9083b85SXin LI * empty block here, this will be done at next call. This also 1187c9083b85SXin LI * ensures that for a very small output buffer, we emit at most 1188c9083b85SXin LI * one empty block. 1189c9083b85SXin LI */ 1190c9083b85SXin LI } 1191c9083b85SXin LI if (bstate == block_done) { 1192c9083b85SXin LI if (flush == Z_PARTIAL_FLUSH) { 1193c9083b85SXin LI _tr_align(s); 1194c9083b85SXin LI } else if (flush != Z_BLOCK) { /* FULL_FLUSH or SYNC_FLUSH */ 1195c9083b85SXin LI _tr_stored_block(s, (char*)0, 0L, 0); 1196c9083b85SXin LI /* For a full flush, this empty block will be recognized 1197c9083b85SXin LI * as a special marker by inflate_sync(). 1198c9083b85SXin LI */ 1199c9083b85SXin LI if (flush == Z_FULL_FLUSH) { 1200c9083b85SXin LI CLEAR_HASH(s); /* forget history */ 1201c9083b85SXin LI if (s->lookahead == 0) { 1202c9083b85SXin LI s->strstart = 0; 1203c9083b85SXin LI s->block_start = 0L; 1204c9083b85SXin LI s->insert = 0; 1205c9083b85SXin LI } 1206c9083b85SXin LI } 1207c9083b85SXin LI } 1208c9083b85SXin LI flush_pending(strm); 1209c9083b85SXin LI if (strm->avail_out == 0) { 1210c9083b85SXin LI s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */ 1211c9083b85SXin LI return Z_OK; 1212c9083b85SXin LI } 1213c9083b85SXin LI } 1214c9083b85SXin LI } 1215c9083b85SXin LI 1216c9083b85SXin LI if (flush != Z_FINISH) return Z_OK; 1217c9083b85SXin LI if (s->wrap <= 0) return Z_STREAM_END; 1218c9083b85SXin LI 1219c9083b85SXin LI /* Write the trailer */ 1220c9083b85SXin LI #ifdef GZIP 1221c9083b85SXin LI if (s->wrap == 2) { 1222c9083b85SXin LI put_byte(s, (Byte)(strm->adler & 0xff)); 1223c9083b85SXin LI put_byte(s, (Byte)((strm->adler >> 8) & 0xff)); 1224c9083b85SXin LI put_byte(s, (Byte)((strm->adler >> 16) & 0xff)); 1225c9083b85SXin LI put_byte(s, (Byte)((strm->adler >> 24) & 0xff)); 1226c9083b85SXin LI put_byte(s, (Byte)(strm->total_in & 0xff)); 1227c9083b85SXin LI put_byte(s, (Byte)((strm->total_in >> 8) & 0xff)); 1228c9083b85SXin LI put_byte(s, (Byte)((strm->total_in >> 16) & 0xff)); 1229c9083b85SXin LI put_byte(s, (Byte)((strm->total_in >> 24) & 0xff)); 1230c9083b85SXin LI } 1231c9083b85SXin LI else 1232c9083b85SXin LI #endif 1233c9083b85SXin LI { 1234c9083b85SXin LI putShortMSB(s, (uInt)(strm->adler >> 16)); 1235c9083b85SXin LI putShortMSB(s, (uInt)(strm->adler & 0xffff)); 1236c9083b85SXin LI } 1237c9083b85SXin LI flush_pending(strm); 1238c9083b85SXin LI /* If avail_out is zero, the application will call deflate again 1239c9083b85SXin LI * to flush the rest. 1240c9083b85SXin LI */ 1241c9083b85SXin LI if (s->wrap > 0) s->wrap = -s->wrap; /* write the trailer only once! */ 1242c9083b85SXin LI return s->pending != 0 ? Z_OK : Z_STREAM_END; 1243c9083b85SXin LI } 1244c9083b85SXin LI 1245c9083b85SXin LI /* ========================================================================= */ 12464717628eSXin LI int ZEXPORT deflateEnd(z_streamp strm) { 1247c9083b85SXin LI int status; 1248c9083b85SXin LI 1249c9083b85SXin LI if (deflateStateCheck(strm)) return Z_STREAM_ERROR; 1250c9083b85SXin LI 1251c9083b85SXin LI status = strm->state->status; 1252c9083b85SXin LI 1253c9083b85SXin LI /* Deallocate in reverse order of allocations: */ 1254c9083b85SXin LI TRY_FREE(strm, strm->state->pending_buf); 1255c9083b85SXin LI TRY_FREE(strm, strm->state->head); 1256c9083b85SXin LI TRY_FREE(strm, strm->state->prev); 1257c9083b85SXin LI TRY_FREE(strm, strm->state->window); 1258c9083b85SXin LI 1259c9083b85SXin LI ZFREE(strm, strm->state); 1260c9083b85SXin LI strm->state = Z_NULL; 1261c9083b85SXin LI 1262c9083b85SXin LI return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK; 1263c9083b85SXin LI } 1264c9083b85SXin LI 1265c9083b85SXin LI /* ========================================================================= 1266c9083b85SXin LI * Copy the source state to the destination state. 1267c9083b85SXin LI * To simplify the source, this is not supported for 16-bit MSDOS (which 1268c9083b85SXin LI * doesn't have enough memory anyway to duplicate compression states). 1269c9083b85SXin LI */ 12704717628eSXin LI int ZEXPORT deflateCopy(z_streamp dest, z_streamp source) { 1271c9083b85SXin LI #ifdef MAXSEG_64K 12724717628eSXin LI (void)dest; 12734717628eSXin LI (void)source; 1274c9083b85SXin LI return Z_STREAM_ERROR; 1275c9083b85SXin LI #else 1276c9083b85SXin LI deflate_state *ds; 1277c9083b85SXin LI deflate_state *ss; 1278c9083b85SXin LI 1279c9083b85SXin LI 1280c9083b85SXin LI if (deflateStateCheck(source) || dest == Z_NULL) { 1281c9083b85SXin LI return Z_STREAM_ERROR; 1282c9083b85SXin LI } 1283c9083b85SXin LI 1284c9083b85SXin LI ss = source->state; 1285c9083b85SXin LI 1286c9083b85SXin LI zmemcpy((voidpf)dest, (voidpf)source, sizeof(z_stream)); 1287c9083b85SXin LI 1288c9083b85SXin LI ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state)); 1289c9083b85SXin LI if (ds == Z_NULL) return Z_MEM_ERROR; 1290c9083b85SXin LI dest->state = (struct internal_state FAR *) ds; 1291c9083b85SXin LI zmemcpy((voidpf)ds, (voidpf)ss, sizeof(deflate_state)); 1292c9083b85SXin LI ds->strm = dest; 1293c9083b85SXin LI 1294c9083b85SXin LI ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte)); 1295c9083b85SXin LI ds->prev = (Posf *) ZALLOC(dest, ds->w_size, sizeof(Pos)); 1296c9083b85SXin LI ds->head = (Posf *) ZALLOC(dest, ds->hash_size, sizeof(Pos)); 1297cd882207SXin LI ds->pending_buf = (uchf *) ZALLOC(dest, ds->lit_bufsize, 4); 1298c9083b85SXin LI 1299c9083b85SXin LI if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL || 1300c9083b85SXin LI ds->pending_buf == Z_NULL) { 1301c9083b85SXin LI deflateEnd (dest); 1302c9083b85SXin LI return Z_MEM_ERROR; 1303c9083b85SXin LI } 1304c9083b85SXin LI /* following zmemcpy do not work for 16-bit MSDOS */ 1305c9083b85SXin LI zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte)); 1306c9083b85SXin LI zmemcpy((voidpf)ds->prev, (voidpf)ss->prev, ds->w_size * sizeof(Pos)); 1307c9083b85SXin LI zmemcpy((voidpf)ds->head, (voidpf)ss->head, ds->hash_size * sizeof(Pos)); 1308c9083b85SXin LI zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size); 1309c9083b85SXin LI 1310c9083b85SXin LI ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf); 1311cd882207SXin LI ds->sym_buf = ds->pending_buf + ds->lit_bufsize; 1312c9083b85SXin LI 1313c9083b85SXin LI ds->l_desc.dyn_tree = ds->dyn_ltree; 1314c9083b85SXin LI ds->d_desc.dyn_tree = ds->dyn_dtree; 1315c9083b85SXin LI ds->bl_desc.dyn_tree = ds->bl_tree; 1316c9083b85SXin LI 1317c9083b85SXin LI return Z_OK; 1318c9083b85SXin LI #endif /* MAXSEG_64K */ 1319c9083b85SXin LI } 1320c9083b85SXin LI 1321c9083b85SXin LI #ifndef FASTEST 1322c9083b85SXin LI /* =========================================================================== 1323c9083b85SXin LI * Set match_start to the longest match starting at the given string and 1324c9083b85SXin LI * return its length. Matches shorter or equal to prev_length are discarded, 1325c9083b85SXin LI * in which case the result is equal to prev_length and match_start is 1326c9083b85SXin LI * garbage. 1327c9083b85SXin LI * IN assertions: cur_match is the head of the hash chain for the current 1328c9083b85SXin LI * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1 1329c9083b85SXin LI * OUT assertion: the match length is not greater than s->lookahead. 1330c9083b85SXin LI */ 13314717628eSXin LI local uInt longest_match(deflate_state *s, IPos cur_match) { 1332c9083b85SXin LI unsigned chain_length = s->max_chain_length;/* max hash chain length */ 1333c9083b85SXin LI register Bytef *scan = s->window + s->strstart; /* current string */ 1334c9083b85SXin LI register Bytef *match; /* matched string */ 1335c9083b85SXin LI register int len; /* length of current match */ 1336c9083b85SXin LI int best_len = (int)s->prev_length; /* best match length so far */ 1337c9083b85SXin LI int nice_match = s->nice_match; /* stop if match long enough */ 1338c9083b85SXin LI IPos limit = s->strstart > (IPos)MAX_DIST(s) ? 1339c9083b85SXin LI s->strstart - (IPos)MAX_DIST(s) : NIL; 1340c9083b85SXin LI /* Stop when cur_match becomes <= limit. To simplify the code, 1341c9083b85SXin LI * we prevent matches with the string of window index 0. 1342c9083b85SXin LI */ 1343c9083b85SXin LI Posf *prev = s->prev; 1344c9083b85SXin LI uInt wmask = s->w_mask; 1345c9083b85SXin LI 1346c9083b85SXin LI #ifdef UNALIGNED_OK 1347c9083b85SXin LI /* Compare two bytes at a time. Note: this is not always beneficial. 1348c9083b85SXin LI * Try with and without -DUNALIGNED_OK to check. 1349c9083b85SXin LI */ 1350c9083b85SXin LI register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1; 1351c9083b85SXin LI register ush scan_start = *(ushf*)scan; 1352c9083b85SXin LI register ush scan_end = *(ushf*)(scan + best_len - 1); 1353c9083b85SXin LI #else 1354c9083b85SXin LI register Bytef *strend = s->window + s->strstart + MAX_MATCH; 1355c9083b85SXin LI register Byte scan_end1 = scan[best_len - 1]; 1356c9083b85SXin LI register Byte scan_end = scan[best_len]; 1357c9083b85SXin LI #endif 1358c9083b85SXin LI 1359c9083b85SXin LI /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. 1360c9083b85SXin LI * It is easy to get rid of this optimization if necessary. 1361c9083b85SXin LI */ 1362c9083b85SXin LI Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever"); 1363c9083b85SXin LI 1364c9083b85SXin LI /* Do not waste too much time if we already have a good match: */ 1365c9083b85SXin LI if (s->prev_length >= s->good_match) { 1366c9083b85SXin LI chain_length >>= 2; 1367c9083b85SXin LI } 1368c9083b85SXin LI /* Do not look for matches beyond the end of the input. This is necessary 1369c9083b85SXin LI * to make deflate deterministic. 1370c9083b85SXin LI */ 1371c9083b85SXin LI if ((uInt)nice_match > s->lookahead) nice_match = (int)s->lookahead; 1372c9083b85SXin LI 1373e37bb444SXin LI Assert((ulg)s->strstart <= s->window_size - MIN_LOOKAHEAD, 1374e37bb444SXin LI "need lookahead"); 1375c9083b85SXin LI 1376c9083b85SXin LI do { 1377c9083b85SXin LI Assert(cur_match < s->strstart, "no future"); 1378c9083b85SXin LI match = s->window + cur_match; 1379c9083b85SXin LI 1380c9083b85SXin LI /* Skip to next match if the match length cannot increase 1381c9083b85SXin LI * or if the match length is less than 2. Note that the checks below 1382c9083b85SXin LI * for insufficient lookahead only occur occasionally for performance 1383c9083b85SXin LI * reasons. Therefore uninitialized memory will be accessed, and 1384c9083b85SXin LI * conditional jumps will be made that depend on those values. 1385c9083b85SXin LI * However the length of the match is limited to the lookahead, so 1386c9083b85SXin LI * the output of deflate is not affected by the uninitialized values. 1387c9083b85SXin LI */ 1388c9083b85SXin LI #if (defined(UNALIGNED_OK) && MAX_MATCH == 258) 1389c9083b85SXin LI /* This code assumes sizeof(unsigned short) == 2. Do not use 1390c9083b85SXin LI * UNALIGNED_OK if your compiler uses a different size. 1391c9083b85SXin LI */ 1392c9083b85SXin LI if (*(ushf*)(match + best_len - 1) != scan_end || 1393c9083b85SXin LI *(ushf*)match != scan_start) continue; 1394c9083b85SXin LI 1395c9083b85SXin LI /* It is not necessary to compare scan[2] and match[2] since they are 1396c9083b85SXin LI * always equal when the other bytes match, given that the hash keys 1397c9083b85SXin LI * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at 1398e37bb444SXin LI * strstart + 3, + 5, up to strstart + 257. We check for insufficient 1399c9083b85SXin LI * lookahead only every 4th comparison; the 128th check will be made 1400c9083b85SXin LI * at strstart + 257. If MAX_MATCH-2 is not a multiple of 8, it is 1401c9083b85SXin LI * necessary to put more guard bytes at the end of the window, or 1402c9083b85SXin LI * to check more often for insufficient lookahead. 1403c9083b85SXin LI */ 1404c9083b85SXin LI Assert(scan[2] == match[2], "scan[2]?"); 1405c9083b85SXin LI scan++, match++; 1406c9083b85SXin LI do { 1407c9083b85SXin LI } while (*(ushf*)(scan += 2) == *(ushf*)(match += 2) && 1408c9083b85SXin LI *(ushf*)(scan += 2) == *(ushf*)(match += 2) && 1409c9083b85SXin LI *(ushf*)(scan += 2) == *(ushf*)(match += 2) && 1410c9083b85SXin LI *(ushf*)(scan += 2) == *(ushf*)(match += 2) && 1411c9083b85SXin LI scan < strend); 1412c9083b85SXin LI /* The funny "do {}" generates better code on most compilers */ 1413c9083b85SXin LI 1414c9083b85SXin LI /* Here, scan <= window + strstart + 257 */ 1415e37bb444SXin LI Assert(scan <= s->window + (unsigned)(s->window_size - 1), 1416e37bb444SXin LI "wild scan"); 1417c9083b85SXin LI if (*scan == *match) scan++; 1418c9083b85SXin LI 1419c9083b85SXin LI len = (MAX_MATCH - 1) - (int)(strend - scan); 1420c9083b85SXin LI scan = strend - (MAX_MATCH-1); 1421c9083b85SXin LI 1422c9083b85SXin LI #else /* UNALIGNED_OK */ 1423c9083b85SXin LI 1424c9083b85SXin LI if (match[best_len] != scan_end || 1425c9083b85SXin LI match[best_len - 1] != scan_end1 || 1426c9083b85SXin LI *match != *scan || 1427c9083b85SXin LI *++match != scan[1]) continue; 1428c9083b85SXin LI 1429c9083b85SXin LI /* The check at best_len - 1 can be removed because it will be made 1430c9083b85SXin LI * again later. (This heuristic is not always a win.) 1431c9083b85SXin LI * It is not necessary to compare scan[2] and match[2] since they 1432c9083b85SXin LI * are always equal when the other bytes match, given that 1433c9083b85SXin LI * the hash keys are equal and that HASH_BITS >= 8. 1434c9083b85SXin LI */ 1435c9083b85SXin LI scan += 2, match++; 1436c9083b85SXin LI Assert(*scan == *match, "match[2]?"); 1437c9083b85SXin LI 1438c9083b85SXin LI /* We check for insufficient lookahead only every 8th comparison; 1439c9083b85SXin LI * the 256th check will be made at strstart + 258. 1440c9083b85SXin LI */ 1441c9083b85SXin LI do { 1442c9083b85SXin LI } while (*++scan == *++match && *++scan == *++match && 1443c9083b85SXin LI *++scan == *++match && *++scan == *++match && 1444c9083b85SXin LI *++scan == *++match && *++scan == *++match && 1445c9083b85SXin LI *++scan == *++match && *++scan == *++match && 1446c9083b85SXin LI scan < strend); 1447c9083b85SXin LI 1448e37bb444SXin LI Assert(scan <= s->window + (unsigned)(s->window_size - 1), 1449e37bb444SXin LI "wild scan"); 1450c9083b85SXin LI 1451c9083b85SXin LI len = MAX_MATCH - (int)(strend - scan); 1452c9083b85SXin LI scan = strend - MAX_MATCH; 1453c9083b85SXin LI 1454c9083b85SXin LI #endif /* UNALIGNED_OK */ 1455c9083b85SXin LI 1456c9083b85SXin LI if (len > best_len) { 1457c9083b85SXin LI s->match_start = cur_match; 1458c9083b85SXin LI best_len = len; 1459c9083b85SXin LI if (len >= nice_match) break; 1460c9083b85SXin LI #ifdef UNALIGNED_OK 1461c9083b85SXin LI scan_end = *(ushf*)(scan + best_len - 1); 1462c9083b85SXin LI #else 1463c9083b85SXin LI scan_end1 = scan[best_len - 1]; 1464c9083b85SXin LI scan_end = scan[best_len]; 1465c9083b85SXin LI #endif 1466c9083b85SXin LI } 1467c9083b85SXin LI } while ((cur_match = prev[cur_match & wmask]) > limit 1468c9083b85SXin LI && --chain_length != 0); 1469c9083b85SXin LI 1470c9083b85SXin LI if ((uInt)best_len <= s->lookahead) return (uInt)best_len; 1471c9083b85SXin LI return s->lookahead; 1472c9083b85SXin LI } 1473c9083b85SXin LI 1474c9083b85SXin LI #else /* FASTEST */ 1475c9083b85SXin LI 1476c9083b85SXin LI /* --------------------------------------------------------------------------- 1477c9083b85SXin LI * Optimized version for FASTEST only 1478c9083b85SXin LI */ 14794717628eSXin LI local uInt longest_match(deflate_state *s, IPos cur_match) { 1480c9083b85SXin LI register Bytef *scan = s->window + s->strstart; /* current string */ 1481c9083b85SXin LI register Bytef *match; /* matched string */ 1482c9083b85SXin LI register int len; /* length of current match */ 1483c9083b85SXin LI register Bytef *strend = s->window + s->strstart + MAX_MATCH; 1484c9083b85SXin LI 1485c9083b85SXin LI /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. 1486c9083b85SXin LI * It is easy to get rid of this optimization if necessary. 1487c9083b85SXin LI */ 1488c9083b85SXin LI Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever"); 1489c9083b85SXin LI 1490e37bb444SXin LI Assert((ulg)s->strstart <= s->window_size - MIN_LOOKAHEAD, 1491e37bb444SXin LI "need lookahead"); 1492c9083b85SXin LI 1493c9083b85SXin LI Assert(cur_match < s->strstart, "no future"); 1494c9083b85SXin LI 1495c9083b85SXin LI match = s->window + cur_match; 1496c9083b85SXin LI 1497c9083b85SXin LI /* Return failure if the match length is less than 2: 1498c9083b85SXin LI */ 1499c9083b85SXin LI if (match[0] != scan[0] || match[1] != scan[1]) return MIN_MATCH-1; 1500c9083b85SXin LI 1501c9083b85SXin LI /* The check at best_len - 1 can be removed because it will be made 1502c9083b85SXin LI * again later. (This heuristic is not always a win.) 1503c9083b85SXin LI * It is not necessary to compare scan[2] and match[2] since they 1504c9083b85SXin LI * are always equal when the other bytes match, given that 1505c9083b85SXin LI * the hash keys are equal and that HASH_BITS >= 8. 1506c9083b85SXin LI */ 1507c9083b85SXin LI scan += 2, match += 2; 1508c9083b85SXin LI Assert(*scan == *match, "match[2]?"); 1509c9083b85SXin LI 1510c9083b85SXin LI /* We check for insufficient lookahead only every 8th comparison; 1511c9083b85SXin LI * the 256th check will be made at strstart + 258. 1512c9083b85SXin LI */ 1513c9083b85SXin LI do { 1514c9083b85SXin LI } while (*++scan == *++match && *++scan == *++match && 1515c9083b85SXin LI *++scan == *++match && *++scan == *++match && 1516c9083b85SXin LI *++scan == *++match && *++scan == *++match && 1517c9083b85SXin LI *++scan == *++match && *++scan == *++match && 1518c9083b85SXin LI scan < strend); 1519c9083b85SXin LI 1520c9083b85SXin LI Assert(scan <= s->window + (unsigned)(s->window_size - 1), "wild scan"); 1521c9083b85SXin LI 1522c9083b85SXin LI len = MAX_MATCH - (int)(strend - scan); 1523c9083b85SXin LI 1524c9083b85SXin LI if (len < MIN_MATCH) return MIN_MATCH - 1; 1525c9083b85SXin LI 1526c9083b85SXin LI s->match_start = cur_match; 1527c9083b85SXin LI return (uInt)len <= s->lookahead ? (uInt)len : s->lookahead; 1528c9083b85SXin LI } 1529c9083b85SXin LI 1530c9083b85SXin LI #endif /* FASTEST */ 1531c9083b85SXin LI 1532c9083b85SXin LI #ifdef ZLIB_DEBUG 1533c9083b85SXin LI 1534c9083b85SXin LI #define EQUAL 0 1535c9083b85SXin LI /* result of memcmp for equal strings */ 1536c9083b85SXin LI 1537c9083b85SXin LI /* =========================================================================== 1538c9083b85SXin LI * Check that the match at match_start is indeed a match. 1539c9083b85SXin LI */ 15404717628eSXin LI local void check_match(deflate_state *s, IPos start, IPos match, int length) { 1541c9083b85SXin LI /* check that the match is indeed a match */ 1542c9083b85SXin LI if (zmemcmp(s->window + match, 1543c9083b85SXin LI s->window + start, length) != EQUAL) { 1544c9083b85SXin LI fprintf(stderr, " start %u, match %u, length %d\n", 1545c9083b85SXin LI start, match, length); 1546c9083b85SXin LI do { 1547c9083b85SXin LI fprintf(stderr, "%c%c", s->window[match++], s->window[start++]); 1548c9083b85SXin LI } while (--length != 0); 1549c9083b85SXin LI z_error("invalid match"); 1550c9083b85SXin LI } 1551c9083b85SXin LI if (z_verbose > 1) { 1552c9083b85SXin LI fprintf(stderr,"\\[%d,%d]", start - match, length); 1553c9083b85SXin LI do { putc(s->window[start++], stderr); } while (--length != 0); 1554c9083b85SXin LI } 1555c9083b85SXin LI } 1556c9083b85SXin LI #else 1557c9083b85SXin LI # define check_match(s, start, match, length) 1558c9083b85SXin LI #endif /* ZLIB_DEBUG */ 1559c9083b85SXin LI 1560c9083b85SXin LI /* =========================================================================== 1561c9083b85SXin LI * Flush the current block, with given end-of-file flag. 1562c9083b85SXin LI * IN assertion: strstart is set to the end of the current match. 1563c9083b85SXin LI */ 1564c9083b85SXin LI #define FLUSH_BLOCK_ONLY(s, last) { \ 1565c9083b85SXin LI _tr_flush_block(s, (s->block_start >= 0L ? \ 1566c9083b85SXin LI (charf *)&s->window[(unsigned)s->block_start] : \ 1567c9083b85SXin LI (charf *)Z_NULL), \ 1568c9083b85SXin LI (ulg)((long)s->strstart - s->block_start), \ 1569c9083b85SXin LI (last)); \ 1570c9083b85SXin LI s->block_start = s->strstart; \ 1571c9083b85SXin LI flush_pending(s->strm); \ 1572c9083b85SXin LI Tracev((stderr,"[FLUSH]")); \ 1573c9083b85SXin LI } 1574c9083b85SXin LI 1575c9083b85SXin LI /* Same but force premature exit if necessary. */ 1576c9083b85SXin LI #define FLUSH_BLOCK(s, last) { \ 1577c9083b85SXin LI FLUSH_BLOCK_ONLY(s, last); \ 1578c9083b85SXin LI if (s->strm->avail_out == 0) return (last) ? finish_started : need_more; \ 1579c9083b85SXin LI } 1580c9083b85SXin LI 1581c9083b85SXin LI /* Maximum stored block length in deflate format (not including header). */ 1582c9083b85SXin LI #define MAX_STORED 65535 1583c9083b85SXin LI 15840ed1d6fbSXin LI #if !defined(MIN) 1585c9083b85SXin LI /* Minimum of a and b. */ 1586c9083b85SXin LI #define MIN(a, b) ((a) > (b) ? (b) : (a)) 15870ed1d6fbSXin LI #endif 1588c9083b85SXin LI 1589c9083b85SXin LI /* =========================================================================== 1590c9083b85SXin LI * Copy without compression as much as possible from the input stream, return 1591c9083b85SXin LI * the current block state. 1592c9083b85SXin LI * 1593c9083b85SXin LI * In case deflateParams() is used to later switch to a non-zero compression 1594c9083b85SXin LI * level, s->matches (otherwise unused when storing) keeps track of the number 1595c9083b85SXin LI * of hash table slides to perform. If s->matches is 1, then one hash table 1596c9083b85SXin LI * slide will be done when switching. If s->matches is 2, the maximum value 1597c9083b85SXin LI * allowed here, then the hash table will be cleared, since two or more slides 1598c9083b85SXin LI * is the same as a clear. 1599c9083b85SXin LI * 1600c9083b85SXin LI * deflate_stored() is written to minimize the number of times an input byte is 1601c9083b85SXin LI * copied. It is most efficient with large input and output buffers, which 1602e37bb444SXin LI * maximizes the opportunities to have a single copy from next_in to next_out. 1603c9083b85SXin LI */ 16044717628eSXin LI local block_state deflate_stored(deflate_state *s, int flush) { 1605c9083b85SXin LI /* Smallest worthy block size when not flushing or finishing. By default 1606c9083b85SXin LI * this is 32K. This can be as small as 507 bytes for memLevel == 1. For 1607c9083b85SXin LI * large input and output buffers, the stored block size will be larger. 1608c9083b85SXin LI */ 1609c9083b85SXin LI unsigned min_block = MIN(s->pending_buf_size - 5, s->w_size); 1610c9083b85SXin LI 1611c9083b85SXin LI /* Copy as many min_block or larger stored blocks directly to next_out as 1612c9083b85SXin LI * possible. If flushing, copy the remaining available input to next_out as 1613c9083b85SXin LI * stored blocks, if there is enough space. 1614c9083b85SXin LI */ 1615c9083b85SXin LI unsigned len, left, have, last = 0; 1616c9083b85SXin LI unsigned used = s->strm->avail_in; 1617c9083b85SXin LI do { 1618c9083b85SXin LI /* Set len to the maximum size block that we can copy directly with the 1619c9083b85SXin LI * available input data and output space. Set left to how much of that 1620c9083b85SXin LI * would be copied from what's left in the window. 1621c9083b85SXin LI */ 1622c9083b85SXin LI len = MAX_STORED; /* maximum deflate stored block length */ 1623c9083b85SXin LI have = (s->bi_valid + 42) >> 3; /* number of header bytes */ 1624c9083b85SXin LI if (s->strm->avail_out < have) /* need room for header */ 1625c9083b85SXin LI break; 1626c9083b85SXin LI /* maximum stored block length that will fit in avail_out: */ 1627c9083b85SXin LI have = s->strm->avail_out - have; 1628c9083b85SXin LI left = s->strstart - s->block_start; /* bytes left in window */ 1629c9083b85SXin LI if (len > (ulg)left + s->strm->avail_in) 1630c9083b85SXin LI len = left + s->strm->avail_in; /* limit len to the input */ 1631c9083b85SXin LI if (len > have) 1632c9083b85SXin LI len = have; /* limit len to the output */ 1633c9083b85SXin LI 1634c9083b85SXin LI /* If the stored block would be less than min_block in length, or if 1635c9083b85SXin LI * unable to copy all of the available input when flushing, then try 1636c9083b85SXin LI * copying to the window and the pending buffer instead. Also don't 1637c9083b85SXin LI * write an empty block when flushing -- deflate() does that. 1638c9083b85SXin LI */ 1639c9083b85SXin LI if (len < min_block && ((len == 0 && flush != Z_FINISH) || 1640c9083b85SXin LI flush == Z_NO_FLUSH || 1641c9083b85SXin LI len != left + s->strm->avail_in)) 1642c9083b85SXin LI break; 1643c9083b85SXin LI 1644c9083b85SXin LI /* Make a dummy stored block in pending to get the header bytes, 1645c9083b85SXin LI * including any pending bits. This also updates the debugging counts. 1646c9083b85SXin LI */ 1647c9083b85SXin LI last = flush == Z_FINISH && len == left + s->strm->avail_in ? 1 : 0; 1648c9083b85SXin LI _tr_stored_block(s, (char *)0, 0L, last); 1649c9083b85SXin LI 1650c9083b85SXin LI /* Replace the lengths in the dummy stored block with len. */ 1651c9083b85SXin LI s->pending_buf[s->pending - 4] = len; 1652c9083b85SXin LI s->pending_buf[s->pending - 3] = len >> 8; 1653c9083b85SXin LI s->pending_buf[s->pending - 2] = ~len; 1654c9083b85SXin LI s->pending_buf[s->pending - 1] = ~len >> 8; 1655c9083b85SXin LI 1656c9083b85SXin LI /* Write the stored block header bytes. */ 1657c9083b85SXin LI flush_pending(s->strm); 1658c9083b85SXin LI 1659c9083b85SXin LI #ifdef ZLIB_DEBUG 1660c9083b85SXin LI /* Update debugging counts for the data about to be copied. */ 1661c9083b85SXin LI s->compressed_len += len << 3; 1662c9083b85SXin LI s->bits_sent += len << 3; 1663c9083b85SXin LI #endif 1664c9083b85SXin LI 1665c9083b85SXin LI /* Copy uncompressed bytes from the window to next_out. */ 1666c9083b85SXin LI if (left) { 1667c9083b85SXin LI if (left > len) 1668c9083b85SXin LI left = len; 1669c9083b85SXin LI zmemcpy(s->strm->next_out, s->window + s->block_start, left); 1670c9083b85SXin LI s->strm->next_out += left; 1671c9083b85SXin LI s->strm->avail_out -= left; 1672c9083b85SXin LI s->strm->total_out += left; 1673c9083b85SXin LI s->block_start += left; 1674c9083b85SXin LI len -= left; 1675c9083b85SXin LI } 1676c9083b85SXin LI 1677c9083b85SXin LI /* Copy uncompressed bytes directly from next_in to next_out, updating 1678c9083b85SXin LI * the check value. 1679c9083b85SXin LI */ 1680c9083b85SXin LI if (len) { 1681c9083b85SXin LI read_buf(s->strm, s->strm->next_out, len); 1682c9083b85SXin LI s->strm->next_out += len; 1683c9083b85SXin LI s->strm->avail_out -= len; 1684c9083b85SXin LI s->strm->total_out += len; 1685c9083b85SXin LI } 1686c9083b85SXin LI } while (last == 0); 1687c9083b85SXin LI 1688c9083b85SXin LI /* Update the sliding window with the last s->w_size bytes of the copied 1689c9083b85SXin LI * data, or append all of the copied data to the existing window if less 1690c9083b85SXin LI * than s->w_size bytes were copied. Also update the number of bytes to 1691c9083b85SXin LI * insert in the hash tables, in the event that deflateParams() switches to 1692c9083b85SXin LI * a non-zero compression level. 1693c9083b85SXin LI */ 1694c9083b85SXin LI used -= s->strm->avail_in; /* number of input bytes directly copied */ 1695c9083b85SXin LI if (used) { 1696c9083b85SXin LI /* If any input was used, then no unused input remains in the window, 1697c9083b85SXin LI * therefore s->block_start == s->strstart. 1698c9083b85SXin LI */ 1699c9083b85SXin LI if (used >= s->w_size) { /* supplant the previous history */ 1700c9083b85SXin LI s->matches = 2; /* clear hash */ 1701c9083b85SXin LI zmemcpy(s->window, s->strm->next_in - s->w_size, s->w_size); 1702c9083b85SXin LI s->strstart = s->w_size; 1703cd882207SXin LI s->insert = s->strstart; 1704c9083b85SXin LI } 1705c9083b85SXin LI else { 1706c9083b85SXin LI if (s->window_size - s->strstart <= used) { 1707c9083b85SXin LI /* Slide the window down. */ 1708c9083b85SXin LI s->strstart -= s->w_size; 1709c9083b85SXin LI zmemcpy(s->window, s->window + s->w_size, s->strstart); 1710c9083b85SXin LI if (s->matches < 2) 1711c9083b85SXin LI s->matches++; /* add a pending slide_hash() */ 1712cd882207SXin LI if (s->insert > s->strstart) 1713cd882207SXin LI s->insert = s->strstart; 1714c9083b85SXin LI } 1715c9083b85SXin LI zmemcpy(s->window + s->strstart, s->strm->next_in - used, used); 1716c9083b85SXin LI s->strstart += used; 1717cd882207SXin LI s->insert += MIN(used, s->w_size - s->insert); 1718c9083b85SXin LI } 1719c9083b85SXin LI s->block_start = s->strstart; 1720c9083b85SXin LI } 1721c9083b85SXin LI if (s->high_water < s->strstart) 1722c9083b85SXin LI s->high_water = s->strstart; 1723c9083b85SXin LI 1724c9083b85SXin LI /* If the last block was written to next_out, then done. */ 1725c9083b85SXin LI if (last) 1726c9083b85SXin LI return finish_done; 1727c9083b85SXin LI 1728c9083b85SXin LI /* If flushing and all input has been consumed, then done. */ 1729c9083b85SXin LI if (flush != Z_NO_FLUSH && flush != Z_FINISH && 1730c9083b85SXin LI s->strm->avail_in == 0 && (long)s->strstart == s->block_start) 1731c9083b85SXin LI return block_done; 1732c9083b85SXin LI 1733c9083b85SXin LI /* Fill the window with any remaining input. */ 1734cd882207SXin LI have = s->window_size - s->strstart; 1735c9083b85SXin LI if (s->strm->avail_in > have && s->block_start >= (long)s->w_size) { 1736c9083b85SXin LI /* Slide the window down. */ 1737c9083b85SXin LI s->block_start -= s->w_size; 1738c9083b85SXin LI s->strstart -= s->w_size; 1739c9083b85SXin LI zmemcpy(s->window, s->window + s->w_size, s->strstart); 1740c9083b85SXin LI if (s->matches < 2) 1741c9083b85SXin LI s->matches++; /* add a pending slide_hash() */ 1742c9083b85SXin LI have += s->w_size; /* more space now */ 1743cd882207SXin LI if (s->insert > s->strstart) 1744cd882207SXin LI s->insert = s->strstart; 1745c9083b85SXin LI } 1746c9083b85SXin LI if (have > s->strm->avail_in) 1747c9083b85SXin LI have = s->strm->avail_in; 1748c9083b85SXin LI if (have) { 1749c9083b85SXin LI read_buf(s->strm, s->window + s->strstart, have); 1750c9083b85SXin LI s->strstart += have; 1751cd882207SXin LI s->insert += MIN(have, s->w_size - s->insert); 1752c9083b85SXin LI } 1753c9083b85SXin LI if (s->high_water < s->strstart) 1754c9083b85SXin LI s->high_water = s->strstart; 1755c9083b85SXin LI 1756c9083b85SXin LI /* There was not enough avail_out to write a complete worthy or flushed 1757c9083b85SXin LI * stored block to next_out. Write a stored block to pending instead, if we 1758c9083b85SXin LI * have enough input for a worthy block, or if flushing and there is enough 1759c9083b85SXin LI * room for the remaining input as a stored block in the pending buffer. 1760c9083b85SXin LI */ 1761c9083b85SXin LI have = (s->bi_valid + 42) >> 3; /* number of header bytes */ 1762c9083b85SXin LI /* maximum stored block length that will fit in pending: */ 1763c9083b85SXin LI have = MIN(s->pending_buf_size - have, MAX_STORED); 1764c9083b85SXin LI min_block = MIN(have, s->w_size); 1765c9083b85SXin LI left = s->strstart - s->block_start; 1766c9083b85SXin LI if (left >= min_block || 1767c9083b85SXin LI ((left || flush == Z_FINISH) && flush != Z_NO_FLUSH && 1768c9083b85SXin LI s->strm->avail_in == 0 && left <= have)) { 1769c9083b85SXin LI len = MIN(left, have); 1770c9083b85SXin LI last = flush == Z_FINISH && s->strm->avail_in == 0 && 1771c9083b85SXin LI len == left ? 1 : 0; 1772c9083b85SXin LI _tr_stored_block(s, (charf *)s->window + s->block_start, len, last); 1773c9083b85SXin LI s->block_start += len; 1774c9083b85SXin LI flush_pending(s->strm); 1775c9083b85SXin LI } 1776c9083b85SXin LI 1777c9083b85SXin LI /* We've done all we can with the available input and output. */ 1778c9083b85SXin LI return last ? finish_started : need_more; 1779c9083b85SXin LI } 1780c9083b85SXin LI 1781c9083b85SXin LI /* =========================================================================== 1782c9083b85SXin LI * Compress as much as possible from the input stream, return the current 1783c9083b85SXin LI * block state. 1784c9083b85SXin LI * This function does not perform lazy evaluation of matches and inserts 1785c9083b85SXin LI * new strings in the dictionary only for unmatched strings or for short 1786c9083b85SXin LI * matches. It is used only for the fast compression options. 1787c9083b85SXin LI */ 17884717628eSXin LI local block_state deflate_fast(deflate_state *s, int flush) { 1789c9083b85SXin LI IPos hash_head; /* head of the hash chain */ 1790c9083b85SXin LI int bflush; /* set if current block must be flushed */ 1791c9083b85SXin LI 1792c9083b85SXin LI for (;;) { 1793c9083b85SXin LI /* Make sure that we always have enough lookahead, except 1794c9083b85SXin LI * at the end of the input file. We need MAX_MATCH bytes 1795c9083b85SXin LI * for the next match, plus MIN_MATCH bytes to insert the 1796c9083b85SXin LI * string following the next match. 1797c9083b85SXin LI */ 1798c9083b85SXin LI if (s->lookahead < MIN_LOOKAHEAD) { 1799c9083b85SXin LI fill_window(s); 1800c9083b85SXin LI if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { 1801c9083b85SXin LI return need_more; 1802c9083b85SXin LI } 1803c9083b85SXin LI if (s->lookahead == 0) break; /* flush the current block */ 1804c9083b85SXin LI } 1805c9083b85SXin LI 1806c9083b85SXin LI /* Insert the string window[strstart .. strstart + 2] in the 1807c9083b85SXin LI * dictionary, and set hash_head to the head of the hash chain: 1808c9083b85SXin LI */ 1809c9083b85SXin LI hash_head = NIL; 1810c9083b85SXin LI if (s->lookahead >= MIN_MATCH) { 1811c9083b85SXin LI INSERT_STRING(s, s->strstart, hash_head); 1812c9083b85SXin LI } 1813c9083b85SXin LI 1814c9083b85SXin LI /* Find the longest match, discarding those <= prev_length. 1815c9083b85SXin LI * At this point we have always match_length < MIN_MATCH 1816c9083b85SXin LI */ 1817c9083b85SXin LI if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) { 1818c9083b85SXin LI /* To simplify the code, we prevent matches with the string 1819c9083b85SXin LI * of window index 0 (in particular we have to avoid a match 1820c9083b85SXin LI * of the string with itself at the start of the input file). 1821c9083b85SXin LI */ 1822c9083b85SXin LI s->match_length = longest_match (s, hash_head); 1823c9083b85SXin LI /* longest_match() sets match_start */ 1824c9083b85SXin LI } 1825c9083b85SXin LI if (s->match_length >= MIN_MATCH) { 1826c9083b85SXin LI check_match(s, s->strstart, s->match_start, s->match_length); 1827c9083b85SXin LI 1828c9083b85SXin LI _tr_tally_dist(s, s->strstart - s->match_start, 1829c9083b85SXin LI s->match_length - MIN_MATCH, bflush); 1830c9083b85SXin LI 1831c9083b85SXin LI s->lookahead -= s->match_length; 1832c9083b85SXin LI 1833c9083b85SXin LI /* Insert new strings in the hash table only if the match length 1834c9083b85SXin LI * is not too large. This saves time but degrades compression. 1835c9083b85SXin LI */ 1836c9083b85SXin LI #ifndef FASTEST 1837c9083b85SXin LI if (s->match_length <= s->max_insert_length && 1838c9083b85SXin LI s->lookahead >= MIN_MATCH) { 1839c9083b85SXin LI s->match_length--; /* string at strstart already in table */ 1840c9083b85SXin LI do { 1841c9083b85SXin LI s->strstart++; 1842c9083b85SXin LI INSERT_STRING(s, s->strstart, hash_head); 1843c9083b85SXin LI /* strstart never exceeds WSIZE-MAX_MATCH, so there are 1844c9083b85SXin LI * always MIN_MATCH bytes ahead. 1845c9083b85SXin LI */ 1846c9083b85SXin LI } while (--s->match_length != 0); 1847c9083b85SXin LI s->strstart++; 1848c9083b85SXin LI } else 1849c9083b85SXin LI #endif 1850c9083b85SXin LI { 1851c9083b85SXin LI s->strstart += s->match_length; 1852c9083b85SXin LI s->match_length = 0; 1853c9083b85SXin LI s->ins_h = s->window[s->strstart]; 1854c9083b85SXin LI UPDATE_HASH(s, s->ins_h, s->window[s->strstart + 1]); 1855c9083b85SXin LI #if MIN_MATCH != 3 1856c9083b85SXin LI Call UPDATE_HASH() MIN_MATCH-3 more times 1857c9083b85SXin LI #endif 1858c9083b85SXin LI /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not 1859c9083b85SXin LI * matter since it will be recomputed at next deflate call. 1860c9083b85SXin LI */ 1861c9083b85SXin LI } 1862c9083b85SXin LI } else { 1863c9083b85SXin LI /* No match, output a literal byte */ 1864c9083b85SXin LI Tracevv((stderr,"%c", s->window[s->strstart])); 1865c9083b85SXin LI _tr_tally_lit(s, s->window[s->strstart], bflush); 1866c9083b85SXin LI s->lookahead--; 1867c9083b85SXin LI s->strstart++; 1868c9083b85SXin LI } 1869c9083b85SXin LI if (bflush) FLUSH_BLOCK(s, 0); 1870c9083b85SXin LI } 1871c9083b85SXin LI s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1; 1872c9083b85SXin LI if (flush == Z_FINISH) { 1873c9083b85SXin LI FLUSH_BLOCK(s, 1); 1874c9083b85SXin LI return finish_done; 1875c9083b85SXin LI } 1876cd882207SXin LI if (s->sym_next) 1877c9083b85SXin LI FLUSH_BLOCK(s, 0); 1878c9083b85SXin LI return block_done; 1879c9083b85SXin LI } 1880c9083b85SXin LI 1881c9083b85SXin LI #ifndef FASTEST 1882c9083b85SXin LI /* =========================================================================== 1883c9083b85SXin LI * Same as above, but achieves better compression. We use a lazy 1884c9083b85SXin LI * evaluation for matches: a match is finally adopted only if there is 1885c9083b85SXin LI * no better match at the next window position. 1886c9083b85SXin LI */ 18874717628eSXin LI local block_state deflate_slow(deflate_state *s, int flush) { 1888c9083b85SXin LI IPos hash_head; /* head of hash chain */ 1889c9083b85SXin LI int bflush; /* set if current block must be flushed */ 1890c9083b85SXin LI 1891c9083b85SXin LI /* Process the input block. */ 1892c9083b85SXin LI for (;;) { 1893c9083b85SXin LI /* Make sure that we always have enough lookahead, except 1894c9083b85SXin LI * at the end of the input file. We need MAX_MATCH bytes 1895c9083b85SXin LI * for the next match, plus MIN_MATCH bytes to insert the 1896c9083b85SXin LI * string following the next match. 1897c9083b85SXin LI */ 1898c9083b85SXin LI if (s->lookahead < MIN_LOOKAHEAD) { 1899c9083b85SXin LI fill_window(s); 1900c9083b85SXin LI if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { 1901c9083b85SXin LI return need_more; 1902c9083b85SXin LI } 1903c9083b85SXin LI if (s->lookahead == 0) break; /* flush the current block */ 1904c9083b85SXin LI } 1905c9083b85SXin LI 1906c9083b85SXin LI /* Insert the string window[strstart .. strstart + 2] in the 1907c9083b85SXin LI * dictionary, and set hash_head to the head of the hash chain: 1908c9083b85SXin LI */ 1909c9083b85SXin LI hash_head = NIL; 1910c9083b85SXin LI if (s->lookahead >= MIN_MATCH) { 1911c9083b85SXin LI INSERT_STRING(s, s->strstart, hash_head); 1912c9083b85SXin LI } 1913c9083b85SXin LI 1914c9083b85SXin LI /* Find the longest match, discarding those <= prev_length. 1915c9083b85SXin LI */ 1916c9083b85SXin LI s->prev_length = s->match_length, s->prev_match = s->match_start; 1917c9083b85SXin LI s->match_length = MIN_MATCH-1; 1918c9083b85SXin LI 1919c9083b85SXin LI if (hash_head != NIL && s->prev_length < s->max_lazy_match && 1920c9083b85SXin LI s->strstart - hash_head <= MAX_DIST(s)) { 1921c9083b85SXin LI /* To simplify the code, we prevent matches with the string 1922c9083b85SXin LI * of window index 0 (in particular we have to avoid a match 1923c9083b85SXin LI * of the string with itself at the start of the input file). 1924c9083b85SXin LI */ 1925c9083b85SXin LI s->match_length = longest_match (s, hash_head); 1926c9083b85SXin LI /* longest_match() sets match_start */ 1927c9083b85SXin LI 1928c9083b85SXin LI if (s->match_length <= 5 && (s->strategy == Z_FILTERED 1929c9083b85SXin LI #if TOO_FAR <= 32767 1930c9083b85SXin LI || (s->match_length == MIN_MATCH && 1931c9083b85SXin LI s->strstart - s->match_start > TOO_FAR) 1932c9083b85SXin LI #endif 1933c9083b85SXin LI )) { 1934c9083b85SXin LI 1935c9083b85SXin LI /* If prev_match is also MIN_MATCH, match_start is garbage 1936c9083b85SXin LI * but we will ignore the current match anyway. 1937c9083b85SXin LI */ 1938c9083b85SXin LI s->match_length = MIN_MATCH-1; 1939c9083b85SXin LI } 1940c9083b85SXin LI } 1941c9083b85SXin LI /* If there was a match at the previous step and the current 1942c9083b85SXin LI * match is not better, output the previous match: 1943c9083b85SXin LI */ 1944c9083b85SXin LI if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) { 1945c9083b85SXin LI uInt max_insert = s->strstart + s->lookahead - MIN_MATCH; 1946c9083b85SXin LI /* Do not insert strings in hash table beyond this. */ 1947c9083b85SXin LI 1948c9083b85SXin LI check_match(s, s->strstart - 1, s->prev_match, s->prev_length); 1949c9083b85SXin LI 1950c9083b85SXin LI _tr_tally_dist(s, s->strstart - 1 - s->prev_match, 1951c9083b85SXin LI s->prev_length - MIN_MATCH, bflush); 1952c9083b85SXin LI 1953c9083b85SXin LI /* Insert in hash table all strings up to the end of the match. 1954c9083b85SXin LI * strstart - 1 and strstart are already inserted. If there is not 1955c9083b85SXin LI * enough lookahead, the last two strings are not inserted in 1956c9083b85SXin LI * the hash table. 1957c9083b85SXin LI */ 1958c9083b85SXin LI s->lookahead -= s->prev_length - 1; 1959c9083b85SXin LI s->prev_length -= 2; 1960c9083b85SXin LI do { 1961c9083b85SXin LI if (++s->strstart <= max_insert) { 1962c9083b85SXin LI INSERT_STRING(s, s->strstart, hash_head); 1963c9083b85SXin LI } 1964c9083b85SXin LI } while (--s->prev_length != 0); 1965c9083b85SXin LI s->match_available = 0; 1966c9083b85SXin LI s->match_length = MIN_MATCH-1; 1967c9083b85SXin LI s->strstart++; 1968c9083b85SXin LI 1969c9083b85SXin LI if (bflush) FLUSH_BLOCK(s, 0); 1970c9083b85SXin LI 1971c9083b85SXin LI } else if (s->match_available) { 1972c9083b85SXin LI /* If there was no match at the previous position, output a 1973c9083b85SXin LI * single literal. If there was a match but the current match 1974c9083b85SXin LI * is longer, truncate the previous match to a single literal. 1975c9083b85SXin LI */ 1976c9083b85SXin LI Tracevv((stderr,"%c", s->window[s->strstart - 1])); 1977c9083b85SXin LI _tr_tally_lit(s, s->window[s->strstart - 1], bflush); 1978c9083b85SXin LI if (bflush) { 1979c9083b85SXin LI FLUSH_BLOCK_ONLY(s, 0); 1980c9083b85SXin LI } 1981c9083b85SXin LI s->strstart++; 1982c9083b85SXin LI s->lookahead--; 1983c9083b85SXin LI if (s->strm->avail_out == 0) return need_more; 1984c9083b85SXin LI } else { 1985c9083b85SXin LI /* There is no previous match to compare with, wait for 1986c9083b85SXin LI * the next step to decide. 1987c9083b85SXin LI */ 1988c9083b85SXin LI s->match_available = 1; 1989c9083b85SXin LI s->strstart++; 1990c9083b85SXin LI s->lookahead--; 1991c9083b85SXin LI } 1992c9083b85SXin LI } 1993c9083b85SXin LI Assert (flush != Z_NO_FLUSH, "no flush?"); 1994c9083b85SXin LI if (s->match_available) { 1995c9083b85SXin LI Tracevv((stderr,"%c", s->window[s->strstart - 1])); 1996c9083b85SXin LI _tr_tally_lit(s, s->window[s->strstart - 1], bflush); 1997c9083b85SXin LI s->match_available = 0; 1998c9083b85SXin LI } 1999c9083b85SXin LI s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1; 2000c9083b85SXin LI if (flush == Z_FINISH) { 2001c9083b85SXin LI FLUSH_BLOCK(s, 1); 2002c9083b85SXin LI return finish_done; 2003c9083b85SXin LI } 2004cd882207SXin LI if (s->sym_next) 2005c9083b85SXin LI FLUSH_BLOCK(s, 0); 2006c9083b85SXin LI return block_done; 2007c9083b85SXin LI } 2008c9083b85SXin LI #endif /* FASTEST */ 2009c9083b85SXin LI 2010c9083b85SXin LI /* =========================================================================== 2011c9083b85SXin LI * For Z_RLE, simply look for runs of bytes, generate matches only of distance 2012c9083b85SXin LI * one. Do not maintain a hash table. (It will be regenerated if this run of 2013c9083b85SXin LI * deflate switches away from Z_RLE.) 2014c9083b85SXin LI */ 20154717628eSXin LI local block_state deflate_rle(deflate_state *s, int flush) { 2016c9083b85SXin LI int bflush; /* set if current block must be flushed */ 2017c9083b85SXin LI uInt prev; /* byte at distance one to match */ 2018c9083b85SXin LI Bytef *scan, *strend; /* scan goes up to strend for length of run */ 2019c9083b85SXin LI 2020c9083b85SXin LI for (;;) { 2021c9083b85SXin LI /* Make sure that we always have enough lookahead, except 2022c9083b85SXin LI * at the end of the input file. We need MAX_MATCH bytes 2023c9083b85SXin LI * for the longest run, plus one for the unrolled loop. 2024c9083b85SXin LI */ 2025c9083b85SXin LI if (s->lookahead <= MAX_MATCH) { 2026c9083b85SXin LI fill_window(s); 2027c9083b85SXin LI if (s->lookahead <= MAX_MATCH && flush == Z_NO_FLUSH) { 2028c9083b85SXin LI return need_more; 2029c9083b85SXin LI } 2030c9083b85SXin LI if (s->lookahead == 0) break; /* flush the current block */ 2031c9083b85SXin LI } 2032c9083b85SXin LI 2033c9083b85SXin LI /* See how many times the previous byte repeats */ 2034c9083b85SXin LI s->match_length = 0; 2035c9083b85SXin LI if (s->lookahead >= MIN_MATCH && s->strstart > 0) { 2036c9083b85SXin LI scan = s->window + s->strstart - 1; 2037c9083b85SXin LI prev = *scan; 2038c9083b85SXin LI if (prev == *++scan && prev == *++scan && prev == *++scan) { 2039c9083b85SXin LI strend = s->window + s->strstart + MAX_MATCH; 2040c9083b85SXin LI do { 2041c9083b85SXin LI } while (prev == *++scan && prev == *++scan && 2042c9083b85SXin LI prev == *++scan && prev == *++scan && 2043c9083b85SXin LI prev == *++scan && prev == *++scan && 2044c9083b85SXin LI prev == *++scan && prev == *++scan && 2045c9083b85SXin LI scan < strend); 2046c9083b85SXin LI s->match_length = MAX_MATCH - (uInt)(strend - scan); 2047c9083b85SXin LI if (s->match_length > s->lookahead) 2048c9083b85SXin LI s->match_length = s->lookahead; 2049c9083b85SXin LI } 2050e37bb444SXin LI Assert(scan <= s->window + (uInt)(s->window_size - 1), 2051e37bb444SXin LI "wild scan"); 2052c9083b85SXin LI } 2053c9083b85SXin LI 2054c9083b85SXin LI /* Emit match if have run of MIN_MATCH or longer, else emit literal */ 2055c9083b85SXin LI if (s->match_length >= MIN_MATCH) { 2056c9083b85SXin LI check_match(s, s->strstart, s->strstart - 1, s->match_length); 2057c9083b85SXin LI 2058c9083b85SXin LI _tr_tally_dist(s, 1, s->match_length - MIN_MATCH, bflush); 2059c9083b85SXin LI 2060c9083b85SXin LI s->lookahead -= s->match_length; 2061c9083b85SXin LI s->strstart += s->match_length; 2062c9083b85SXin LI s->match_length = 0; 2063c9083b85SXin LI } else { 2064c9083b85SXin LI /* No match, output a literal byte */ 2065c9083b85SXin LI Tracevv((stderr,"%c", s->window[s->strstart])); 2066c9083b85SXin LI _tr_tally_lit(s, s->window[s->strstart], bflush); 2067c9083b85SXin LI s->lookahead--; 2068c9083b85SXin LI s->strstart++; 2069c9083b85SXin LI } 2070c9083b85SXin LI if (bflush) FLUSH_BLOCK(s, 0); 2071c9083b85SXin LI } 2072c9083b85SXin LI s->insert = 0; 2073c9083b85SXin LI if (flush == Z_FINISH) { 2074c9083b85SXin LI FLUSH_BLOCK(s, 1); 2075c9083b85SXin LI return finish_done; 2076c9083b85SXin LI } 2077cd882207SXin LI if (s->sym_next) 2078c9083b85SXin LI FLUSH_BLOCK(s, 0); 2079c9083b85SXin LI return block_done; 2080c9083b85SXin LI } 2081c9083b85SXin LI 2082c9083b85SXin LI /* =========================================================================== 2083c9083b85SXin LI * For Z_HUFFMAN_ONLY, do not look for matches. Do not maintain a hash table. 2084c9083b85SXin LI * (It will be regenerated if this run of deflate switches away from Huffman.) 2085c9083b85SXin LI */ 20864717628eSXin LI local block_state deflate_huff(deflate_state *s, int flush) { 2087c9083b85SXin LI int bflush; /* set if current block must be flushed */ 2088c9083b85SXin LI 2089c9083b85SXin LI for (;;) { 2090c9083b85SXin LI /* Make sure that we have a literal to write. */ 2091c9083b85SXin LI if (s->lookahead == 0) { 2092c9083b85SXin LI fill_window(s); 2093c9083b85SXin LI if (s->lookahead == 0) { 2094c9083b85SXin LI if (flush == Z_NO_FLUSH) 2095c9083b85SXin LI return need_more; 2096c9083b85SXin LI break; /* flush the current block */ 2097c9083b85SXin LI } 2098c9083b85SXin LI } 2099c9083b85SXin LI 2100c9083b85SXin LI /* Output a literal byte */ 2101c9083b85SXin LI s->match_length = 0; 2102c9083b85SXin LI Tracevv((stderr,"%c", s->window[s->strstart])); 2103c9083b85SXin LI _tr_tally_lit(s, s->window[s->strstart], bflush); 2104c9083b85SXin LI s->lookahead--; 2105c9083b85SXin LI s->strstart++; 2106c9083b85SXin LI if (bflush) FLUSH_BLOCK(s, 0); 2107c9083b85SXin LI } 2108c9083b85SXin LI s->insert = 0; 2109c9083b85SXin LI if (flush == Z_FINISH) { 2110c9083b85SXin LI FLUSH_BLOCK(s, 1); 2111c9083b85SXin LI return finish_done; 2112c9083b85SXin LI } 2113cd882207SXin LI if (s->sym_next) 2114c9083b85SXin LI FLUSH_BLOCK(s, 0); 2115c9083b85SXin LI return block_done; 2116c9083b85SXin LI } 2117