11da177e4SLinus Torvalds /* +++ deflate.c */
21da177e4SLinus Torvalds /* deflate.c -- compress data using the deflation algorithm
31da177e4SLinus Torvalds * Copyright (C) 1995-1996 Jean-loup Gailly.
41da177e4SLinus Torvalds * For conditions of distribution and use, see copyright notice in zlib.h
51da177e4SLinus Torvalds */
61da177e4SLinus Torvalds
71da177e4SLinus Torvalds /*
81da177e4SLinus Torvalds * ALGORITHM
91da177e4SLinus Torvalds *
101da177e4SLinus Torvalds * The "deflation" process depends on being able to identify portions
111da177e4SLinus Torvalds * of the input text which are identical to earlier input (within a
121da177e4SLinus Torvalds * sliding window trailing behind the input currently being processed).
131da177e4SLinus Torvalds *
141da177e4SLinus Torvalds * The most straightforward technique turns out to be the fastest for
151da177e4SLinus Torvalds * most input files: try all possible matches and select the longest.
161da177e4SLinus Torvalds * The key feature of this algorithm is that insertions into the string
171da177e4SLinus Torvalds * dictionary are very simple and thus fast, and deletions are avoided
181da177e4SLinus Torvalds * completely. Insertions are performed at each input character, whereas
191da177e4SLinus Torvalds * string matches are performed only when the previous match ends. So it
201da177e4SLinus Torvalds * is preferable to spend more time in matches to allow very fast string
211da177e4SLinus Torvalds * insertions and avoid deletions. The matching algorithm for small
221da177e4SLinus Torvalds * strings is inspired from that of Rabin & Karp. A brute force approach
231da177e4SLinus Torvalds * is used to find longer strings when a small match has been found.
241da177e4SLinus Torvalds * A similar algorithm is used in comic (by Jan-Mark Wams) and freeze
251da177e4SLinus Torvalds * (by Leonid Broukhis).
261da177e4SLinus Torvalds * A previous version of this file used a more sophisticated algorithm
271da177e4SLinus Torvalds * (by Fiala and Greene) which is guaranteed to run in linear amortized
281da177e4SLinus Torvalds * time, but has a larger average cost, uses more memory and is patented.
291da177e4SLinus Torvalds * However the F&G algorithm may be faster for some highly redundant
301da177e4SLinus Torvalds * files if the parameter max_chain_length (described below) is too large.
311da177e4SLinus Torvalds *
321da177e4SLinus Torvalds * ACKNOWLEDGEMENTS
331da177e4SLinus Torvalds *
341da177e4SLinus Torvalds * The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
351da177e4SLinus Torvalds * I found it in 'freeze' written by Leonid Broukhis.
361da177e4SLinus Torvalds * Thanks to many people for bug reports and testing.
371da177e4SLinus Torvalds *
381da177e4SLinus Torvalds * REFERENCES
391da177e4SLinus Torvalds *
401da177e4SLinus Torvalds * Deutsch, L.P.,"DEFLATE Compressed Data Format Specification".
411da177e4SLinus Torvalds * Available in ftp://ds.internic.net/rfc/rfc1951.txt
421da177e4SLinus Torvalds *
431da177e4SLinus Torvalds * A description of the Rabin and Karp algorithm is given in the book
441da177e4SLinus Torvalds * "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
451da177e4SLinus Torvalds *
461da177e4SLinus Torvalds * Fiala,E.R., and Greene,D.H.
471da177e4SLinus Torvalds * Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
481da177e4SLinus Torvalds *
491da177e4SLinus Torvalds */
501da177e4SLinus Torvalds
511da177e4SLinus Torvalds #include <linux/module.h>
521da177e4SLinus Torvalds #include <linux/zutil.h>
531da177e4SLinus Torvalds #include "defutil.h"
541da177e4SLinus Torvalds
55aa5b395bSMikhail Zaslonko /* architecture-specific bits */
56aa5b395bSMikhail Zaslonko #ifdef CONFIG_ZLIB_DFLTCC
57*9fec9f8eSMikhail Zaslonko # include "../zlib_dfltcc/dfltcc_deflate.h"
58aa5b395bSMikhail Zaslonko #else
59aa5b395bSMikhail Zaslonko #define DEFLATE_RESET_HOOK(strm) do {} while (0)
60aa5b395bSMikhail Zaslonko #define DEFLATE_HOOK(strm, flush, bstate) 0
61aa5b395bSMikhail Zaslonko #define DEFLATE_NEED_CHECKSUM(strm) 1
62803521b1SMikhail Zaslonko #define DEFLATE_DFLTCC_ENABLED() 0
63aa5b395bSMikhail Zaslonko #endif
641da177e4SLinus Torvalds
651da177e4SLinus Torvalds /* ===========================================================================
661da177e4SLinus Torvalds * Function prototypes.
671da177e4SLinus Torvalds */
681da177e4SLinus Torvalds
691da177e4SLinus Torvalds typedef block_state (*compress_func) (deflate_state *s, int flush);
701da177e4SLinus Torvalds /* Compression function. Returns the block state after the call. */
711da177e4SLinus Torvalds
721da177e4SLinus Torvalds static void fill_window (deflate_state *s);
731da177e4SLinus Torvalds static block_state deflate_stored (deflate_state *s, int flush);
741da177e4SLinus Torvalds static block_state deflate_fast (deflate_state *s, int flush);
751da177e4SLinus Torvalds static block_state deflate_slow (deflate_state *s, int flush);
761da177e4SLinus Torvalds static void lm_init (deflate_state *s);
771da177e4SLinus Torvalds static void putShortMSB (deflate_state *s, uInt b);
781da177e4SLinus Torvalds static int read_buf (z_streamp strm, Byte *buf, unsigned size);
791da177e4SLinus Torvalds static uInt longest_match (deflate_state *s, IPos cur_match);
801da177e4SLinus Torvalds
811da177e4SLinus Torvalds #ifdef DEBUG_ZLIB
821da177e4SLinus Torvalds static void check_match (deflate_state *s, IPos start, IPos match,
831da177e4SLinus Torvalds int length);
841da177e4SLinus Torvalds #endif
851da177e4SLinus Torvalds
861da177e4SLinus Torvalds /* ===========================================================================
871da177e4SLinus Torvalds * Local data
881da177e4SLinus Torvalds */
891da177e4SLinus Torvalds
901da177e4SLinus Torvalds #define NIL 0
911da177e4SLinus Torvalds /* Tail of hash chains */
921da177e4SLinus Torvalds
931da177e4SLinus Torvalds #ifndef TOO_FAR
941da177e4SLinus Torvalds # define TOO_FAR 4096
951da177e4SLinus Torvalds #endif
961da177e4SLinus Torvalds /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
971da177e4SLinus Torvalds
981da177e4SLinus Torvalds #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
991da177e4SLinus Torvalds /* Minimum amount of lookahead, except at the end of the input file.
1001da177e4SLinus Torvalds * See deflate.c for comments about the MIN_MATCH+1.
1011da177e4SLinus Torvalds */
1021da177e4SLinus Torvalds
103aa5b395bSMikhail Zaslonko /* Workspace to be allocated for deflate processing */
104aa5b395bSMikhail Zaslonko typedef struct deflate_workspace {
105aa5b395bSMikhail Zaslonko /* State memory for the deflator */
106aa5b395bSMikhail Zaslonko deflate_state deflate_memory;
107aa5b395bSMikhail Zaslonko #ifdef CONFIG_ZLIB_DFLTCC
108aa5b395bSMikhail Zaslonko /* State memory for s390 hardware deflate */
109*9fec9f8eSMikhail Zaslonko struct dfltcc_deflate_state dfltcc_memory;
110aa5b395bSMikhail Zaslonko #endif
111aa5b395bSMikhail Zaslonko Byte *window_memory;
112aa5b395bSMikhail Zaslonko Pos *prev_memory;
113aa5b395bSMikhail Zaslonko Pos *head_memory;
114aa5b395bSMikhail Zaslonko char *overlay_memory;
115aa5b395bSMikhail Zaslonko } deflate_workspace;
116aa5b395bSMikhail Zaslonko
117aa5b395bSMikhail Zaslonko #ifdef CONFIG_ZLIB_DFLTCC
118aa5b395bSMikhail Zaslonko /* dfltcc_state must be doubleword aligned for DFLTCC call */
119aa5b395bSMikhail Zaslonko static_assert(offsetof(struct deflate_workspace, dfltcc_memory) % 8 == 0);
120aa5b395bSMikhail Zaslonko #endif
121aa5b395bSMikhail Zaslonko
1221da177e4SLinus Torvalds /* Values for max_lazy_match, good_match and max_chain_length, depending on
1231da177e4SLinus Torvalds * the desired pack level (0..9). The values given below have been tuned to
1241da177e4SLinus Torvalds * exclude worst case performance for pathological files. Better values may be
1251da177e4SLinus Torvalds * found for specific files.
1261da177e4SLinus Torvalds */
1271da177e4SLinus Torvalds typedef struct config_s {
1281da177e4SLinus Torvalds ush good_length; /* reduce lazy search above this match length */
1291da177e4SLinus Torvalds ush max_lazy; /* do not perform lazy search above this match length */
1301da177e4SLinus Torvalds ush nice_length; /* quit search above this match length */
1311da177e4SLinus Torvalds ush max_chain;
1321da177e4SLinus Torvalds compress_func func;
1331da177e4SLinus Torvalds } config;
1341da177e4SLinus Torvalds
1351da177e4SLinus Torvalds static const config configuration_table[10] = {
1361da177e4SLinus Torvalds /* good lazy nice chain */
1371da177e4SLinus Torvalds /* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */
1381da177e4SLinus Torvalds /* 1 */ {4, 4, 8, 4, deflate_fast}, /* maximum speed, no lazy matches */
1391da177e4SLinus Torvalds /* 2 */ {4, 5, 16, 8, deflate_fast},
1401da177e4SLinus Torvalds /* 3 */ {4, 6, 32, 32, deflate_fast},
1411da177e4SLinus Torvalds
1421da177e4SLinus Torvalds /* 4 */ {4, 4, 16, 16, deflate_slow}, /* lazy matches */
1431da177e4SLinus Torvalds /* 5 */ {8, 16, 32, 32, deflate_slow},
1441da177e4SLinus Torvalds /* 6 */ {8, 16, 128, 128, deflate_slow},
1451da177e4SLinus Torvalds /* 7 */ {8, 32, 128, 256, deflate_slow},
1461da177e4SLinus Torvalds /* 8 */ {32, 128, 258, 1024, deflate_slow},
1471da177e4SLinus Torvalds /* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* maximum compression */
1481da177e4SLinus Torvalds
1491da177e4SLinus Torvalds /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
1501da177e4SLinus Torvalds * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
1511da177e4SLinus Torvalds * meaning.
1521da177e4SLinus Torvalds */
1531da177e4SLinus Torvalds
1541da177e4SLinus Torvalds #define EQUAL 0
1551da177e4SLinus Torvalds /* result of memcmp for equal strings */
1561da177e4SLinus Torvalds
1571da177e4SLinus Torvalds /* ===========================================================================
1581da177e4SLinus Torvalds * Update a hash value with the given input byte
159fd589a8fSAnand Gadiyar * IN assertion: all calls to UPDATE_HASH are made with consecutive
1601da177e4SLinus Torvalds * input characters, so that a running hash key can be computed from the
1611da177e4SLinus Torvalds * previous key instead of complete recalculation each time.
1621da177e4SLinus Torvalds */
1631da177e4SLinus Torvalds #define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)
1641da177e4SLinus Torvalds
1651da177e4SLinus Torvalds
1661da177e4SLinus Torvalds /* ===========================================================================
1671da177e4SLinus Torvalds * Insert string str in the dictionary and set match_head to the previous head
1681da177e4SLinus Torvalds * of the hash chain (the most recent string with same hash key). Return
1691da177e4SLinus Torvalds * the previous length of the hash chain.
170fd589a8fSAnand Gadiyar * IN assertion: all calls to INSERT_STRING are made with consecutive
1711da177e4SLinus Torvalds * input characters and the first MIN_MATCH bytes of str are valid
1721da177e4SLinus Torvalds * (except for the last MIN_MATCH-1 bytes of the input file).
1731da177e4SLinus Torvalds */
1741da177e4SLinus Torvalds #define INSERT_STRING(s, str, match_head) \
1751da177e4SLinus Torvalds (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
1761da177e4SLinus Torvalds s->prev[(str) & s->w_mask] = match_head = s->head[s->ins_h], \
1771da177e4SLinus Torvalds s->head[s->ins_h] = (Pos)(str))
1781da177e4SLinus Torvalds
1791da177e4SLinus Torvalds /* ===========================================================================
1801da177e4SLinus Torvalds * Initialize the hash table (avoiding 64K overflow for 16 bit systems).
1811da177e4SLinus Torvalds * prev[] will be initialized on the fly.
1821da177e4SLinus Torvalds */
1831da177e4SLinus Torvalds #define CLEAR_HASH(s) \
1841da177e4SLinus Torvalds s->head[s->hash_size-1] = NIL; \
1851da177e4SLinus Torvalds memset((char *)s->head, 0, (unsigned)(s->hash_size-1)*sizeof(*s->head));
1861da177e4SLinus Torvalds
1871da177e4SLinus Torvalds /* ========================================================================= */
zlib_deflateInit2(z_streamp strm,int level,int method,int windowBits,int memLevel,int strategy)1884f3865fbSRichard Purdie int zlib_deflateInit2(
1891da177e4SLinus Torvalds z_streamp strm,
1901da177e4SLinus Torvalds int level,
1911da177e4SLinus Torvalds int method,
1921da177e4SLinus Torvalds int windowBits,
1931da177e4SLinus Torvalds int memLevel,
1944f3865fbSRichard Purdie int strategy
1951da177e4SLinus Torvalds )
1961da177e4SLinus Torvalds {
1971da177e4SLinus Torvalds deflate_state *s;
1981da177e4SLinus Torvalds int noheader = 0;
1991da177e4SLinus Torvalds deflate_workspace *mem;
200565d76cbSJim Keniston char *next;
2011da177e4SLinus Torvalds
2021da177e4SLinus Torvalds ush *overlay;
2031da177e4SLinus Torvalds /* We overlay pending_buf and d_buf+l_buf. This works since the average
2041da177e4SLinus Torvalds * output size for (length,distance) codes is <= 24 bits.
2051da177e4SLinus Torvalds */
2061da177e4SLinus Torvalds
2071da177e4SLinus Torvalds if (strm == NULL) return Z_STREAM_ERROR;
2081da177e4SLinus Torvalds
2091da177e4SLinus Torvalds strm->msg = NULL;
2101da177e4SLinus Torvalds
2111da177e4SLinus Torvalds if (level == Z_DEFAULT_COMPRESSION) level = 6;
2121da177e4SLinus Torvalds
2131da177e4SLinus Torvalds mem = (deflate_workspace *) strm->workspace;
2141da177e4SLinus Torvalds
2151da177e4SLinus Torvalds if (windowBits < 0) { /* undocumented feature: suppress zlib header */
2161da177e4SLinus Torvalds noheader = 1;
2171da177e4SLinus Torvalds windowBits = -windowBits;
2181da177e4SLinus Torvalds }
2191da177e4SLinus Torvalds if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED ||
2201da177e4SLinus Torvalds windowBits < 9 || windowBits > 15 || level < 0 || level > 9 ||
2211da177e4SLinus Torvalds strategy < 0 || strategy > Z_HUFFMAN_ONLY) {
2221da177e4SLinus Torvalds return Z_STREAM_ERROR;
2231da177e4SLinus Torvalds }
224565d76cbSJim Keniston
225565d76cbSJim Keniston /*
226565d76cbSJim Keniston * Direct the workspace's pointers to the chunks that were allocated
227565d76cbSJim Keniston * along with the deflate_workspace struct.
228565d76cbSJim Keniston */
229565d76cbSJim Keniston next = (char *) mem;
230565d76cbSJim Keniston next += sizeof(*mem);
231aa5b395bSMikhail Zaslonko #ifdef CONFIG_ZLIB_DFLTCC
232aa5b395bSMikhail Zaslonko /*
233aa5b395bSMikhail Zaslonko * DFLTCC requires the window to be page aligned.
234aa5b395bSMikhail Zaslonko * Thus, we overallocate and take the aligned portion of the buffer.
235aa5b395bSMikhail Zaslonko */
236aa5b395bSMikhail Zaslonko mem->window_memory = (Byte *) PTR_ALIGN(next, PAGE_SIZE);
237aa5b395bSMikhail Zaslonko #else
238565d76cbSJim Keniston mem->window_memory = (Byte *) next;
239aa5b395bSMikhail Zaslonko #endif
240565d76cbSJim Keniston next += zlib_deflate_window_memsize(windowBits);
241565d76cbSJim Keniston mem->prev_memory = (Pos *) next;
242565d76cbSJim Keniston next += zlib_deflate_prev_memsize(windowBits);
243565d76cbSJim Keniston mem->head_memory = (Pos *) next;
244565d76cbSJim Keniston next += zlib_deflate_head_memsize(memLevel);
245565d76cbSJim Keniston mem->overlay_memory = next;
246565d76cbSJim Keniston
2471da177e4SLinus Torvalds s = (deflate_state *) &(mem->deflate_memory);
2481da177e4SLinus Torvalds strm->state = (struct internal_state *)s;
2491da177e4SLinus Torvalds s->strm = strm;
2501da177e4SLinus Torvalds
2511da177e4SLinus Torvalds s->noheader = noheader;
2521da177e4SLinus Torvalds s->w_bits = windowBits;
2531da177e4SLinus Torvalds s->w_size = 1 << s->w_bits;
2541da177e4SLinus Torvalds s->w_mask = s->w_size - 1;
2551da177e4SLinus Torvalds
2561da177e4SLinus Torvalds s->hash_bits = memLevel + 7;
2571da177e4SLinus Torvalds s->hash_size = 1 << s->hash_bits;
2581da177e4SLinus Torvalds s->hash_mask = s->hash_size - 1;
2591da177e4SLinus Torvalds s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);
2601da177e4SLinus Torvalds
2611da177e4SLinus Torvalds s->window = (Byte *) mem->window_memory;
2621da177e4SLinus Torvalds s->prev = (Pos *) mem->prev_memory;
2631da177e4SLinus Torvalds s->head = (Pos *) mem->head_memory;
2641da177e4SLinus Torvalds
2651da177e4SLinus Torvalds s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */
2661da177e4SLinus Torvalds
2671da177e4SLinus Torvalds overlay = (ush *) mem->overlay_memory;
2681da177e4SLinus Torvalds s->pending_buf = (uch *) overlay;
2691da177e4SLinus Torvalds s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L);
2701da177e4SLinus Torvalds
2711da177e4SLinus Torvalds s->d_buf = overlay + s->lit_bufsize/sizeof(ush);
2721da177e4SLinus Torvalds s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize;
2731da177e4SLinus Torvalds
2741da177e4SLinus Torvalds s->level = level;
2751da177e4SLinus Torvalds s->strategy = strategy;
2761da177e4SLinus Torvalds s->method = (Byte)method;
2771da177e4SLinus Torvalds
2781da177e4SLinus Torvalds return zlib_deflateReset(strm);
2791da177e4SLinus Torvalds }
2801da177e4SLinus Torvalds
2811da177e4SLinus Torvalds /* ========================================================================= */
zlib_deflateReset(z_streamp strm)2821da177e4SLinus Torvalds int zlib_deflateReset(
2831da177e4SLinus Torvalds z_streamp strm
2841da177e4SLinus Torvalds )
2851da177e4SLinus Torvalds {
2861da177e4SLinus Torvalds deflate_state *s;
2871da177e4SLinus Torvalds
2881da177e4SLinus Torvalds if (strm == NULL || strm->state == NULL)
2891da177e4SLinus Torvalds return Z_STREAM_ERROR;
2901da177e4SLinus Torvalds
2911da177e4SLinus Torvalds strm->total_in = strm->total_out = 0;
2921da177e4SLinus Torvalds strm->msg = NULL;
2931da177e4SLinus Torvalds strm->data_type = Z_UNKNOWN;
2941da177e4SLinus Torvalds
2951da177e4SLinus Torvalds s = (deflate_state *)strm->state;
2961da177e4SLinus Torvalds s->pending = 0;
2971da177e4SLinus Torvalds s->pending_out = s->pending_buf;
2981da177e4SLinus Torvalds
2991da177e4SLinus Torvalds if (s->noheader < 0) {
3001da177e4SLinus Torvalds s->noheader = 0; /* was set to -1 by deflate(..., Z_FINISH); */
3011da177e4SLinus Torvalds }
3021da177e4SLinus Torvalds s->status = s->noheader ? BUSY_STATE : INIT_STATE;
3031da177e4SLinus Torvalds strm->adler = 1;
3041da177e4SLinus Torvalds s->last_flush = Z_NO_FLUSH;
3051da177e4SLinus Torvalds
3061da177e4SLinus Torvalds zlib_tr_init(s);
3071da177e4SLinus Torvalds lm_init(s);
3081da177e4SLinus Torvalds
309aa5b395bSMikhail Zaslonko DEFLATE_RESET_HOOK(strm);
310aa5b395bSMikhail Zaslonko
3111da177e4SLinus Torvalds return Z_OK;
3121da177e4SLinus Torvalds }
3131da177e4SLinus Torvalds
3141da177e4SLinus Torvalds /* =========================================================================
3151da177e4SLinus Torvalds * Put a short in the pending buffer. The 16-bit value is put in MSB order.
3161da177e4SLinus Torvalds * IN assertion: the stream state is correct and there is enough room in
3171da177e4SLinus Torvalds * pending_buf.
3181da177e4SLinus Torvalds */
putShortMSB(deflate_state * s,uInt b)3191da177e4SLinus Torvalds static void putShortMSB(
3201da177e4SLinus Torvalds deflate_state *s,
3211da177e4SLinus Torvalds uInt b
3221da177e4SLinus Torvalds )
3231da177e4SLinus Torvalds {
3241da177e4SLinus Torvalds put_byte(s, (Byte)(b >> 8));
3251da177e4SLinus Torvalds put_byte(s, (Byte)(b & 0xff));
3261da177e4SLinus Torvalds }
3271da177e4SLinus Torvalds
3281da177e4SLinus Torvalds /* ========================================================================= */
zlib_deflate(z_streamp strm,int flush)3291da177e4SLinus Torvalds int zlib_deflate(
3301da177e4SLinus Torvalds z_streamp strm,
3311da177e4SLinus Torvalds int flush
3321da177e4SLinus Torvalds )
3331da177e4SLinus Torvalds {
3341da177e4SLinus Torvalds int old_flush; /* value of flush param for previous deflate call */
3351da177e4SLinus Torvalds deflate_state *s;
3361da177e4SLinus Torvalds
3371da177e4SLinus Torvalds if (strm == NULL || strm->state == NULL ||
3381da177e4SLinus Torvalds flush > Z_FINISH || flush < 0) {
3391da177e4SLinus Torvalds return Z_STREAM_ERROR;
3401da177e4SLinus Torvalds }
3411da177e4SLinus Torvalds s = (deflate_state *) strm->state;
3421da177e4SLinus Torvalds
3431da177e4SLinus Torvalds if ((strm->next_in == NULL && strm->avail_in != 0) ||
3441da177e4SLinus Torvalds (s->status == FINISH_STATE && flush != Z_FINISH)) {
3451da177e4SLinus Torvalds return Z_STREAM_ERROR;
3461da177e4SLinus Torvalds }
3471da177e4SLinus Torvalds if (strm->avail_out == 0) return Z_BUF_ERROR;
3481da177e4SLinus Torvalds
3491da177e4SLinus Torvalds s->strm = strm; /* just in case */
3501da177e4SLinus Torvalds old_flush = s->last_flush;
3511da177e4SLinus Torvalds s->last_flush = flush;
3521da177e4SLinus Torvalds
3531da177e4SLinus Torvalds /* Write the zlib header */
3541da177e4SLinus Torvalds if (s->status == INIT_STATE) {
3551da177e4SLinus Torvalds
3561da177e4SLinus Torvalds uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8;
3571da177e4SLinus Torvalds uInt level_flags = (s->level-1) >> 1;
3581da177e4SLinus Torvalds
3591da177e4SLinus Torvalds if (level_flags > 3) level_flags = 3;
3601da177e4SLinus Torvalds header |= (level_flags << 6);
3611da177e4SLinus Torvalds if (s->strstart != 0) header |= PRESET_DICT;
3621da177e4SLinus Torvalds header += 31 - (header % 31);
3631da177e4SLinus Torvalds
3641da177e4SLinus Torvalds s->status = BUSY_STATE;
3651da177e4SLinus Torvalds putShortMSB(s, header);
3661da177e4SLinus Torvalds
3671da177e4SLinus Torvalds /* Save the adler32 of the preset dictionary: */
3681da177e4SLinus Torvalds if (s->strstart != 0) {
3691da177e4SLinus Torvalds putShortMSB(s, (uInt)(strm->adler >> 16));
3701da177e4SLinus Torvalds putShortMSB(s, (uInt)(strm->adler & 0xffff));
3711da177e4SLinus Torvalds }
3721da177e4SLinus Torvalds strm->adler = 1L;
3731da177e4SLinus Torvalds }
3741da177e4SLinus Torvalds
3751da177e4SLinus Torvalds /* Flush as much pending output as possible */
3761da177e4SLinus Torvalds if (s->pending != 0) {
3771da177e4SLinus Torvalds flush_pending(strm);
3781da177e4SLinus Torvalds if (strm->avail_out == 0) {
3791da177e4SLinus Torvalds /* Since avail_out is 0, deflate will be called again with
3801da177e4SLinus Torvalds * more output space, but possibly with both pending and
3811da177e4SLinus Torvalds * avail_in equal to zero. There won't be anything to do,
3821da177e4SLinus Torvalds * but this is not an error situation so make sure we
3831da177e4SLinus Torvalds * return OK instead of BUF_ERROR at next call of deflate:
3841da177e4SLinus Torvalds */
3851da177e4SLinus Torvalds s->last_flush = -1;
3861da177e4SLinus Torvalds return Z_OK;
3871da177e4SLinus Torvalds }
3881da177e4SLinus Torvalds
3891da177e4SLinus Torvalds /* Make sure there is something to do and avoid duplicate consecutive
3901da177e4SLinus Torvalds * flushes. For repeated and useless calls with Z_FINISH, we keep
3911da177e4SLinus Torvalds * returning Z_STREAM_END instead of Z_BUFF_ERROR.
3921da177e4SLinus Torvalds */
3931da177e4SLinus Torvalds } else if (strm->avail_in == 0 && flush <= old_flush &&
3941da177e4SLinus Torvalds flush != Z_FINISH) {
3951da177e4SLinus Torvalds return Z_BUF_ERROR;
3961da177e4SLinus Torvalds }
3971da177e4SLinus Torvalds
3981da177e4SLinus Torvalds /* User must not provide more input after the first FINISH: */
3991da177e4SLinus Torvalds if (s->status == FINISH_STATE && strm->avail_in != 0) {
4001da177e4SLinus Torvalds return Z_BUF_ERROR;
4011da177e4SLinus Torvalds }
4021da177e4SLinus Torvalds
4031da177e4SLinus Torvalds /* Start a new block or continue the current one.
4041da177e4SLinus Torvalds */
4051da177e4SLinus Torvalds if (strm->avail_in != 0 || s->lookahead != 0 ||
4061da177e4SLinus Torvalds (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) {
4071da177e4SLinus Torvalds block_state bstate;
4081da177e4SLinus Torvalds
409aa5b395bSMikhail Zaslonko bstate = DEFLATE_HOOK(strm, flush, &bstate) ? bstate :
410aa5b395bSMikhail Zaslonko (*(configuration_table[s->level].func))(s, flush);
4111da177e4SLinus Torvalds
4121da177e4SLinus Torvalds if (bstate == finish_started || bstate == finish_done) {
4131da177e4SLinus Torvalds s->status = FINISH_STATE;
4141da177e4SLinus Torvalds }
4151da177e4SLinus Torvalds if (bstate == need_more || bstate == finish_started) {
4161da177e4SLinus Torvalds if (strm->avail_out == 0) {
4171da177e4SLinus Torvalds s->last_flush = -1; /* avoid BUF_ERROR next call, see above */
4181da177e4SLinus Torvalds }
4191da177e4SLinus Torvalds return Z_OK;
4201da177e4SLinus Torvalds /* If flush != Z_NO_FLUSH && avail_out == 0, the next call
4211da177e4SLinus Torvalds * of deflate should use the same flush parameter to make sure
4221da177e4SLinus Torvalds * that the flush is complete. So we don't have to output an
4231da177e4SLinus Torvalds * empty block here, this will be done at next call. This also
4241da177e4SLinus Torvalds * ensures that for a very small output buffer, we emit at most
4251da177e4SLinus Torvalds * one empty block.
4261da177e4SLinus Torvalds */
4271da177e4SLinus Torvalds }
4281da177e4SLinus Torvalds if (bstate == block_done) {
4291da177e4SLinus Torvalds if (flush == Z_PARTIAL_FLUSH) {
4301da177e4SLinus Torvalds zlib_tr_align(s);
4311da177e4SLinus Torvalds } else if (flush == Z_PACKET_FLUSH) {
4321da177e4SLinus Torvalds /* Output just the 3-bit `stored' block type value,
4331da177e4SLinus Torvalds but not a zero length. */
4341da177e4SLinus Torvalds zlib_tr_stored_type_only(s);
4351da177e4SLinus Torvalds } else { /* FULL_FLUSH or SYNC_FLUSH */
4361da177e4SLinus Torvalds zlib_tr_stored_block(s, (char*)0, 0L, 0);
4371da177e4SLinus Torvalds /* For a full flush, this empty block will be recognized
4381da177e4SLinus Torvalds * as a special marker by inflate_sync().
4391da177e4SLinus Torvalds */
4401da177e4SLinus Torvalds if (flush == Z_FULL_FLUSH) {
4411da177e4SLinus Torvalds CLEAR_HASH(s); /* forget history */
4421da177e4SLinus Torvalds }
4431da177e4SLinus Torvalds }
4441da177e4SLinus Torvalds flush_pending(strm);
4451da177e4SLinus Torvalds if (strm->avail_out == 0) {
4461da177e4SLinus Torvalds s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */
4471da177e4SLinus Torvalds return Z_OK;
4481da177e4SLinus Torvalds }
4491da177e4SLinus Torvalds }
4501da177e4SLinus Torvalds }
4511da177e4SLinus Torvalds Assert(strm->avail_out > 0, "bug2");
4521da177e4SLinus Torvalds
4531da177e4SLinus Torvalds if (flush != Z_FINISH) return Z_OK;
4541da177e4SLinus Torvalds
455195c5ad9SMikhail Zaslonko if (!s->noheader) {
456195c5ad9SMikhail Zaslonko /* Write zlib trailer (adler32) */
4571da177e4SLinus Torvalds putShortMSB(s, (uInt)(strm->adler >> 16));
4581da177e4SLinus Torvalds putShortMSB(s, (uInt)(strm->adler & 0xffff));
459195c5ad9SMikhail Zaslonko }
4601da177e4SLinus Torvalds flush_pending(strm);
4611da177e4SLinus Torvalds /* If avail_out is zero, the application will call deflate again
4621da177e4SLinus Torvalds * to flush the rest.
4631da177e4SLinus Torvalds */
464195c5ad9SMikhail Zaslonko if (!s->noheader) {
4651da177e4SLinus Torvalds s->noheader = -1; /* write the trailer only once! */
466195c5ad9SMikhail Zaslonko }
467195c5ad9SMikhail Zaslonko if (s->pending == 0) {
468195c5ad9SMikhail Zaslonko Assert(s->bi_valid == 0, "bi_buf not flushed");
469195c5ad9SMikhail Zaslonko return Z_STREAM_END;
470195c5ad9SMikhail Zaslonko }
471195c5ad9SMikhail Zaslonko return Z_OK;
4721da177e4SLinus Torvalds }
4731da177e4SLinus Torvalds
4741da177e4SLinus Torvalds /* ========================================================================= */
zlib_deflateEnd(z_streamp strm)4751da177e4SLinus Torvalds int zlib_deflateEnd(
4761da177e4SLinus Torvalds z_streamp strm
4771da177e4SLinus Torvalds )
4781da177e4SLinus Torvalds {
4791da177e4SLinus Torvalds int status;
4801da177e4SLinus Torvalds deflate_state *s;
4811da177e4SLinus Torvalds
4821da177e4SLinus Torvalds if (strm == NULL || strm->state == NULL) return Z_STREAM_ERROR;
4831da177e4SLinus Torvalds s = (deflate_state *) strm->state;
4841da177e4SLinus Torvalds
4851da177e4SLinus Torvalds status = s->status;
4861da177e4SLinus Torvalds if (status != INIT_STATE && status != BUSY_STATE &&
4871da177e4SLinus Torvalds status != FINISH_STATE) {
4881da177e4SLinus Torvalds return Z_STREAM_ERROR;
4891da177e4SLinus Torvalds }
4901da177e4SLinus Torvalds
4911da177e4SLinus Torvalds strm->state = NULL;
4921da177e4SLinus Torvalds
4931da177e4SLinus Torvalds return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK;
4941da177e4SLinus Torvalds }
4951da177e4SLinus Torvalds
4961da177e4SLinus Torvalds /* ===========================================================================
4971da177e4SLinus Torvalds * Read a new buffer from the current input stream, update the adler32
4981da177e4SLinus Torvalds * and total number of bytes read. All deflate() input goes through
4991da177e4SLinus Torvalds * this function so some applications may wish to modify it to avoid
5001da177e4SLinus Torvalds * allocating a large strm->next_in buffer and copying from it.
5011da177e4SLinus Torvalds * (See also flush_pending()).
5021da177e4SLinus Torvalds */
read_buf(z_streamp strm,Byte * buf,unsigned size)5031da177e4SLinus Torvalds static int read_buf(
5041da177e4SLinus Torvalds z_streamp strm,
5051da177e4SLinus Torvalds Byte *buf,
5061da177e4SLinus Torvalds unsigned size
5071da177e4SLinus Torvalds )
5081da177e4SLinus Torvalds {
5091da177e4SLinus Torvalds unsigned len = strm->avail_in;
5101da177e4SLinus Torvalds
5111da177e4SLinus Torvalds if (len > size) len = size;
5121da177e4SLinus Torvalds if (len == 0) return 0;
5131da177e4SLinus Torvalds
5141da177e4SLinus Torvalds strm->avail_in -= len;
5151da177e4SLinus Torvalds
516aa5b395bSMikhail Zaslonko if (!DEFLATE_NEED_CHECKSUM(strm)) {}
517aa5b395bSMikhail Zaslonko else if (!((deflate_state *)(strm->state))->noheader) {
5181da177e4SLinus Torvalds strm->adler = zlib_adler32(strm->adler, strm->next_in, len);
5191da177e4SLinus Torvalds }
5201da177e4SLinus Torvalds memcpy(buf, strm->next_in, len);
5211da177e4SLinus Torvalds strm->next_in += len;
5221da177e4SLinus Torvalds strm->total_in += len;
5231da177e4SLinus Torvalds
5241da177e4SLinus Torvalds return (int)len;
5251da177e4SLinus Torvalds }
5261da177e4SLinus Torvalds
5271da177e4SLinus Torvalds /* ===========================================================================
5281da177e4SLinus Torvalds * Initialize the "longest match" routines for a new zlib stream
5291da177e4SLinus Torvalds */
lm_init(deflate_state * s)5301da177e4SLinus Torvalds static void lm_init(
5311da177e4SLinus Torvalds deflate_state *s
5321da177e4SLinus Torvalds )
5331da177e4SLinus Torvalds {
5341da177e4SLinus Torvalds s->window_size = (ulg)2L*s->w_size;
5351da177e4SLinus Torvalds
5361da177e4SLinus Torvalds CLEAR_HASH(s);
5371da177e4SLinus Torvalds
5381da177e4SLinus Torvalds /* Set the default configuration parameters:
5391da177e4SLinus Torvalds */
5401da177e4SLinus Torvalds s->max_lazy_match = configuration_table[s->level].max_lazy;
5411da177e4SLinus Torvalds s->good_match = configuration_table[s->level].good_length;
5421da177e4SLinus Torvalds s->nice_match = configuration_table[s->level].nice_length;
5431da177e4SLinus Torvalds s->max_chain_length = configuration_table[s->level].max_chain;
5441da177e4SLinus Torvalds
5451da177e4SLinus Torvalds s->strstart = 0;
5461da177e4SLinus Torvalds s->block_start = 0L;
5471da177e4SLinus Torvalds s->lookahead = 0;
5481da177e4SLinus Torvalds s->match_length = s->prev_length = MIN_MATCH-1;
5491da177e4SLinus Torvalds s->match_available = 0;
5501da177e4SLinus Torvalds s->ins_h = 0;
5511da177e4SLinus Torvalds }
5521da177e4SLinus Torvalds
5531da177e4SLinus Torvalds /* ===========================================================================
5541da177e4SLinus Torvalds * Set match_start to the longest match starting at the given string and
5551da177e4SLinus Torvalds * return its length. Matches shorter or equal to prev_length are discarded,
5561da177e4SLinus Torvalds * in which case the result is equal to prev_length and match_start is
5571da177e4SLinus Torvalds * garbage.
5581da177e4SLinus Torvalds * IN assertions: cur_match is the head of the hash chain for the current
5591da177e4SLinus Torvalds * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
5601da177e4SLinus Torvalds * OUT assertion: the match length is not greater than s->lookahead.
5611da177e4SLinus Torvalds */
5621da177e4SLinus Torvalds /* For 80x86 and 680x0, an optimized version will be provided in match.asm or
5631da177e4SLinus Torvalds * match.S. The code will be functionally equivalent.
5641da177e4SLinus Torvalds */
longest_match(deflate_state * s,IPos cur_match)5651da177e4SLinus Torvalds static uInt longest_match(
5661da177e4SLinus Torvalds deflate_state *s,
5671da177e4SLinus Torvalds IPos cur_match /* current match */
5681da177e4SLinus Torvalds )
5691da177e4SLinus Torvalds {
5701da177e4SLinus Torvalds unsigned chain_length = s->max_chain_length;/* max hash chain length */
5711da177e4SLinus Torvalds register Byte *scan = s->window + s->strstart; /* current string */
5721da177e4SLinus Torvalds register Byte *match; /* matched string */
5731da177e4SLinus Torvalds register int len; /* length of current match */
5741da177e4SLinus Torvalds int best_len = s->prev_length; /* best match length so far */
5751da177e4SLinus Torvalds int nice_match = s->nice_match; /* stop if match long enough */
5761da177e4SLinus Torvalds IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
5771da177e4SLinus Torvalds s->strstart - (IPos)MAX_DIST(s) : NIL;
5781da177e4SLinus Torvalds /* Stop when cur_match becomes <= limit. To simplify the code,
5791da177e4SLinus Torvalds * we prevent matches with the string of window index 0.
5801da177e4SLinus Torvalds */
5811da177e4SLinus Torvalds Pos *prev = s->prev;
5821da177e4SLinus Torvalds uInt wmask = s->w_mask;
5831da177e4SLinus Torvalds
5841da177e4SLinus Torvalds #ifdef UNALIGNED_OK
5851da177e4SLinus Torvalds /* Compare two bytes at a time. Note: this is not always beneficial.
5861da177e4SLinus Torvalds * Try with and without -DUNALIGNED_OK to check.
5871da177e4SLinus Torvalds */
5881da177e4SLinus Torvalds register Byte *strend = s->window + s->strstart + MAX_MATCH - 1;
5891da177e4SLinus Torvalds register ush scan_start = *(ush*)scan;
5901da177e4SLinus Torvalds register ush scan_end = *(ush*)(scan+best_len-1);
5911da177e4SLinus Torvalds #else
5921da177e4SLinus Torvalds register Byte *strend = s->window + s->strstart + MAX_MATCH;
5931da177e4SLinus Torvalds register Byte scan_end1 = scan[best_len-1];
5941da177e4SLinus Torvalds register Byte scan_end = scan[best_len];
5951da177e4SLinus Torvalds #endif
5961da177e4SLinus Torvalds
5971da177e4SLinus Torvalds /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
5981da177e4SLinus Torvalds * It is easy to get rid of this optimization if necessary.
5991da177e4SLinus Torvalds */
6001da177e4SLinus Torvalds Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
6011da177e4SLinus Torvalds
6021da177e4SLinus Torvalds /* Do not waste too much time if we already have a good match: */
6031da177e4SLinus Torvalds if (s->prev_length >= s->good_match) {
6041da177e4SLinus Torvalds chain_length >>= 2;
6051da177e4SLinus Torvalds }
6061da177e4SLinus Torvalds /* Do not look for matches beyond the end of the input. This is necessary
6071da177e4SLinus Torvalds * to make deflate deterministic.
6081da177e4SLinus Torvalds */
6091da177e4SLinus Torvalds if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead;
6101da177e4SLinus Torvalds
6111da177e4SLinus Torvalds Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
6121da177e4SLinus Torvalds
6131da177e4SLinus Torvalds do {
6141da177e4SLinus Torvalds Assert(cur_match < s->strstart, "no future");
6151da177e4SLinus Torvalds match = s->window + cur_match;
6161da177e4SLinus Torvalds
6171da177e4SLinus Torvalds /* Skip to next match if the match length cannot increase
6181da177e4SLinus Torvalds * or if the match length is less than 2:
6191da177e4SLinus Torvalds */
6201da177e4SLinus Torvalds #if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
6211da177e4SLinus Torvalds /* This code assumes sizeof(unsigned short) == 2. Do not use
6221da177e4SLinus Torvalds * UNALIGNED_OK if your compiler uses a different size.
6231da177e4SLinus Torvalds */
6241da177e4SLinus Torvalds if (*(ush*)(match+best_len-1) != scan_end ||
6251da177e4SLinus Torvalds *(ush*)match != scan_start) continue;
6261da177e4SLinus Torvalds
6271da177e4SLinus Torvalds /* It is not necessary to compare scan[2] and match[2] since they are
6281da177e4SLinus Torvalds * always equal when the other bytes match, given that the hash keys
6291da177e4SLinus Torvalds * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at
6301da177e4SLinus Torvalds * strstart+3, +5, ... up to strstart+257. We check for insufficient
6311da177e4SLinus Torvalds * lookahead only every 4th comparison; the 128th check will be made
6321da177e4SLinus Torvalds * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is
6331da177e4SLinus Torvalds * necessary to put more guard bytes at the end of the window, or
6341da177e4SLinus Torvalds * to check more often for insufficient lookahead.
6351da177e4SLinus Torvalds */
6361da177e4SLinus Torvalds Assert(scan[2] == match[2], "scan[2]?");
6371da177e4SLinus Torvalds scan++, match++;
6381da177e4SLinus Torvalds do {
6391da177e4SLinus Torvalds } while (*(ush*)(scan+=2) == *(ush*)(match+=2) &&
6401da177e4SLinus Torvalds *(ush*)(scan+=2) == *(ush*)(match+=2) &&
6411da177e4SLinus Torvalds *(ush*)(scan+=2) == *(ush*)(match+=2) &&
6421da177e4SLinus Torvalds *(ush*)(scan+=2) == *(ush*)(match+=2) &&
6431da177e4SLinus Torvalds scan < strend);
6441da177e4SLinus Torvalds /* The funny "do {}" generates better code on most compilers */
6451da177e4SLinus Torvalds
6461da177e4SLinus Torvalds /* Here, scan <= window+strstart+257 */
6471da177e4SLinus Torvalds Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
6481da177e4SLinus Torvalds if (*scan == *match) scan++;
6491da177e4SLinus Torvalds
6501da177e4SLinus Torvalds len = (MAX_MATCH - 1) - (int)(strend-scan);
6511da177e4SLinus Torvalds scan = strend - (MAX_MATCH-1);
6521da177e4SLinus Torvalds
6531da177e4SLinus Torvalds #else /* UNALIGNED_OK */
6541da177e4SLinus Torvalds
6551da177e4SLinus Torvalds if (match[best_len] != scan_end ||
6561da177e4SLinus Torvalds match[best_len-1] != scan_end1 ||
6571da177e4SLinus Torvalds *match != *scan ||
6581da177e4SLinus Torvalds *++match != scan[1]) continue;
6591da177e4SLinus Torvalds
6601da177e4SLinus Torvalds /* The check at best_len-1 can be removed because it will be made
6611da177e4SLinus Torvalds * again later. (This heuristic is not always a win.)
6621da177e4SLinus Torvalds * It is not necessary to compare scan[2] and match[2] since they
6631da177e4SLinus Torvalds * are always equal when the other bytes match, given that
6641da177e4SLinus Torvalds * the hash keys are equal and that HASH_BITS >= 8.
6651da177e4SLinus Torvalds */
6661da177e4SLinus Torvalds scan += 2, match++;
6671da177e4SLinus Torvalds Assert(*scan == *match, "match[2]?");
6681da177e4SLinus Torvalds
6691da177e4SLinus Torvalds /* We check for insufficient lookahead only every 8th comparison;
6701da177e4SLinus Torvalds * the 256th check will be made at strstart+258.
6711da177e4SLinus Torvalds */
6721da177e4SLinus Torvalds do {
6731da177e4SLinus Torvalds } while (*++scan == *++match && *++scan == *++match &&
6741da177e4SLinus Torvalds *++scan == *++match && *++scan == *++match &&
6751da177e4SLinus Torvalds *++scan == *++match && *++scan == *++match &&
6761da177e4SLinus Torvalds *++scan == *++match && *++scan == *++match &&
6771da177e4SLinus Torvalds scan < strend);
6781da177e4SLinus Torvalds
6791da177e4SLinus Torvalds Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
6801da177e4SLinus Torvalds
6811da177e4SLinus Torvalds len = MAX_MATCH - (int)(strend - scan);
6821da177e4SLinus Torvalds scan = strend - MAX_MATCH;
6831da177e4SLinus Torvalds
6841da177e4SLinus Torvalds #endif /* UNALIGNED_OK */
6851da177e4SLinus Torvalds
6861da177e4SLinus Torvalds if (len > best_len) {
6871da177e4SLinus Torvalds s->match_start = cur_match;
6881da177e4SLinus Torvalds best_len = len;
6891da177e4SLinus Torvalds if (len >= nice_match) break;
6901da177e4SLinus Torvalds #ifdef UNALIGNED_OK
6911da177e4SLinus Torvalds scan_end = *(ush*)(scan+best_len-1);
6921da177e4SLinus Torvalds #else
6931da177e4SLinus Torvalds scan_end1 = scan[best_len-1];
6941da177e4SLinus Torvalds scan_end = scan[best_len];
6951da177e4SLinus Torvalds #endif
6961da177e4SLinus Torvalds }
6971da177e4SLinus Torvalds } while ((cur_match = prev[cur_match & wmask]) > limit
6981da177e4SLinus Torvalds && --chain_length != 0);
6991da177e4SLinus Torvalds
7001da177e4SLinus Torvalds if ((uInt)best_len <= s->lookahead) return best_len;
7011da177e4SLinus Torvalds return s->lookahead;
7021da177e4SLinus Torvalds }
7031da177e4SLinus Torvalds
7041da177e4SLinus Torvalds #ifdef DEBUG_ZLIB
7051da177e4SLinus Torvalds /* ===========================================================================
7061da177e4SLinus Torvalds * Check that the match at match_start is indeed a match.
7071da177e4SLinus Torvalds */
check_match(deflate_state * s,IPos start,IPos match,int length)7081da177e4SLinus Torvalds static void check_match(
7091da177e4SLinus Torvalds deflate_state *s,
7101da177e4SLinus Torvalds IPos start,
7111da177e4SLinus Torvalds IPos match,
7121da177e4SLinus Torvalds int length
7131da177e4SLinus Torvalds )
7141da177e4SLinus Torvalds {
7151da177e4SLinus Torvalds /* check that the match is indeed a match */
7161da177e4SLinus Torvalds if (memcmp((char *)s->window + match,
7171da177e4SLinus Torvalds (char *)s->window + start, length) != EQUAL) {
7181da177e4SLinus Torvalds fprintf(stderr, " start %u, match %u, length %d\n",
7191da177e4SLinus Torvalds start, match, length);
7201da177e4SLinus Torvalds do {
7211da177e4SLinus Torvalds fprintf(stderr, "%c%c", s->window[match++], s->window[start++]);
7221da177e4SLinus Torvalds } while (--length != 0);
7231da177e4SLinus Torvalds z_error("invalid match");
7241da177e4SLinus Torvalds }
7251da177e4SLinus Torvalds if (z_verbose > 1) {
7261da177e4SLinus Torvalds fprintf(stderr,"\\[%d,%d]", start-match, length);
7271da177e4SLinus Torvalds do { putc(s->window[start++], stderr); } while (--length != 0);
7281da177e4SLinus Torvalds }
7291da177e4SLinus Torvalds }
7301da177e4SLinus Torvalds #else
7311da177e4SLinus Torvalds # define check_match(s, start, match, length)
7321da177e4SLinus Torvalds #endif
7331da177e4SLinus Torvalds
7341da177e4SLinus Torvalds /* ===========================================================================
7351da177e4SLinus Torvalds * Fill the window when the lookahead becomes insufficient.
7361da177e4SLinus Torvalds * Updates strstart and lookahead.
7371da177e4SLinus Torvalds *
7381da177e4SLinus Torvalds * IN assertion: lookahead < MIN_LOOKAHEAD
7391da177e4SLinus Torvalds * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD
7401da177e4SLinus Torvalds * At least one byte has been read, or avail_in == 0; reads are
7411da177e4SLinus Torvalds * performed for at least two bytes (required for the zip translate_eol
7421da177e4SLinus Torvalds * option -- not supported here).
7431da177e4SLinus Torvalds */
fill_window(deflate_state * s)7441da177e4SLinus Torvalds static void fill_window(
7451da177e4SLinus Torvalds deflate_state *s
7461da177e4SLinus Torvalds )
7471da177e4SLinus Torvalds {
7481da177e4SLinus Torvalds register unsigned n, m;
7491da177e4SLinus Torvalds register Pos *p;
7501da177e4SLinus Torvalds unsigned more; /* Amount of free space at the end of the window. */
7511da177e4SLinus Torvalds uInt wsize = s->w_size;
7521da177e4SLinus Torvalds
7531da177e4SLinus Torvalds do {
7541da177e4SLinus Torvalds more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart);
7551da177e4SLinus Torvalds
7561da177e4SLinus Torvalds /* Deal with !@#$% 64K limit: */
7571da177e4SLinus Torvalds if (more == 0 && s->strstart == 0 && s->lookahead == 0) {
7581da177e4SLinus Torvalds more = wsize;
7591da177e4SLinus Torvalds
7601da177e4SLinus Torvalds } else if (more == (unsigned)(-1)) {
7611da177e4SLinus Torvalds /* Very unlikely, but possible on 16 bit machine if strstart == 0
7621da177e4SLinus Torvalds * and lookahead == 1 (input done one byte at time)
7631da177e4SLinus Torvalds */
7641da177e4SLinus Torvalds more--;
7651da177e4SLinus Torvalds
7661da177e4SLinus Torvalds /* If the window is almost full and there is insufficient lookahead,
7671da177e4SLinus Torvalds * move the upper half to the lower one to make room in the upper half.
7681da177e4SLinus Torvalds */
7691da177e4SLinus Torvalds } else if (s->strstart >= wsize+MAX_DIST(s)) {
7701da177e4SLinus Torvalds
7711da177e4SLinus Torvalds memcpy((char *)s->window, (char *)s->window+wsize,
7721da177e4SLinus Torvalds (unsigned)wsize);
7731da177e4SLinus Torvalds s->match_start -= wsize;
7741da177e4SLinus Torvalds s->strstart -= wsize; /* we now have strstart >= MAX_DIST */
7751da177e4SLinus Torvalds s->block_start -= (long) wsize;
7761da177e4SLinus Torvalds
7771da177e4SLinus Torvalds /* Slide the hash table (could be avoided with 32 bit values
7781da177e4SLinus Torvalds at the expense of memory usage). We slide even when level == 0
7791da177e4SLinus Torvalds to keep the hash table consistent if we switch back to level > 0
7801da177e4SLinus Torvalds later. (Using level 0 permanently is not an optimal usage of
7811da177e4SLinus Torvalds zlib, so we don't care about this pathological case.)
7821da177e4SLinus Torvalds */
7831da177e4SLinus Torvalds n = s->hash_size;
7841da177e4SLinus Torvalds p = &s->head[n];
7851da177e4SLinus Torvalds do {
7861da177e4SLinus Torvalds m = *--p;
7871da177e4SLinus Torvalds *p = (Pos)(m >= wsize ? m-wsize : NIL);
7881da177e4SLinus Torvalds } while (--n);
7891da177e4SLinus Torvalds
7901da177e4SLinus Torvalds n = wsize;
7911da177e4SLinus Torvalds p = &s->prev[n];
7921da177e4SLinus Torvalds do {
7931da177e4SLinus Torvalds m = *--p;
7941da177e4SLinus Torvalds *p = (Pos)(m >= wsize ? m-wsize : NIL);
7951da177e4SLinus Torvalds /* If n is not on any hash chain, prev[n] is garbage but
7961da177e4SLinus Torvalds * its value will never be used.
7971da177e4SLinus Torvalds */
7981da177e4SLinus Torvalds } while (--n);
7991da177e4SLinus Torvalds more += wsize;
8001da177e4SLinus Torvalds }
8011da177e4SLinus Torvalds if (s->strm->avail_in == 0) return;
8021da177e4SLinus Torvalds
8031da177e4SLinus Torvalds /* If there was no sliding:
8041da177e4SLinus Torvalds * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 &&
8051da177e4SLinus Torvalds * more == window_size - lookahead - strstart
8061da177e4SLinus Torvalds * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1)
8071da177e4SLinus Torvalds * => more >= window_size - 2*WSIZE + 2
8081da177e4SLinus Torvalds * In the BIG_MEM or MMAP case (not yet supported),
8091da177e4SLinus Torvalds * window_size == input_size + MIN_LOOKAHEAD &&
8101da177e4SLinus Torvalds * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD.
8111da177e4SLinus Torvalds * Otherwise, window_size == 2*WSIZE so more >= 2.
8121da177e4SLinus Torvalds * If there was sliding, more >= WSIZE. So in all cases, more >= 2.
8131da177e4SLinus Torvalds */
8141da177e4SLinus Torvalds Assert(more >= 2, "more < 2");
8151da177e4SLinus Torvalds
8161da177e4SLinus Torvalds n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more);
8171da177e4SLinus Torvalds s->lookahead += n;
8181da177e4SLinus Torvalds
8191da177e4SLinus Torvalds /* Initialize the hash value now that we have some input: */
8201da177e4SLinus Torvalds if (s->lookahead >= MIN_MATCH) {
8211da177e4SLinus Torvalds s->ins_h = s->window[s->strstart];
8221da177e4SLinus Torvalds UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
8231da177e4SLinus Torvalds #if MIN_MATCH != 3
8241da177e4SLinus Torvalds Call UPDATE_HASH() MIN_MATCH-3 more times
8251da177e4SLinus Torvalds #endif
8261da177e4SLinus Torvalds }
8271da177e4SLinus Torvalds /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage,
8281da177e4SLinus Torvalds * but this is not important since only literal bytes will be emitted.
8291da177e4SLinus Torvalds */
8301da177e4SLinus Torvalds
8311da177e4SLinus Torvalds } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0);
8321da177e4SLinus Torvalds }
8331da177e4SLinus Torvalds
8341da177e4SLinus Torvalds /* ===========================================================================
8351da177e4SLinus Torvalds * Flush the current block, with given end-of-file flag.
8361da177e4SLinus Torvalds * IN assertion: strstart is set to the end of the current match.
8371da177e4SLinus Torvalds */
8381da177e4SLinus Torvalds #define FLUSH_BLOCK_ONLY(s, eof) { \
8391da177e4SLinus Torvalds zlib_tr_flush_block(s, (s->block_start >= 0L ? \
8401da177e4SLinus Torvalds (char *)&s->window[(unsigned)s->block_start] : \
8411da177e4SLinus Torvalds NULL), \
8421da177e4SLinus Torvalds (ulg)((long)s->strstart - s->block_start), \
8431da177e4SLinus Torvalds (eof)); \
8441da177e4SLinus Torvalds s->block_start = s->strstart; \
8451da177e4SLinus Torvalds flush_pending(s->strm); \
8461da177e4SLinus Torvalds Tracev((stderr,"[FLUSH]")); \
8471da177e4SLinus Torvalds }
8481da177e4SLinus Torvalds
8491da177e4SLinus Torvalds /* Same but force premature exit if necessary. */
8501da177e4SLinus Torvalds #define FLUSH_BLOCK(s, eof) { \
8511da177e4SLinus Torvalds FLUSH_BLOCK_ONLY(s, eof); \
8521da177e4SLinus Torvalds if (s->strm->avail_out == 0) return (eof) ? finish_started : need_more; \
8531da177e4SLinus Torvalds }
8541da177e4SLinus Torvalds
8551da177e4SLinus Torvalds /* ===========================================================================
8561da177e4SLinus Torvalds * Copy without compression as much as possible from the input stream, return
8571da177e4SLinus Torvalds * the current block state.
8581da177e4SLinus Torvalds * This function does not insert new strings in the dictionary since
8591da177e4SLinus Torvalds * uncompressible data is probably not useful. This function is used
8601da177e4SLinus Torvalds * only for the level=0 compression option.
8611da177e4SLinus Torvalds * NOTE: this function should be optimized to avoid extra copying from
8621da177e4SLinus Torvalds * window to pending_buf.
8631da177e4SLinus Torvalds */
deflate_stored(deflate_state * s,int flush)8641da177e4SLinus Torvalds static block_state deflate_stored(
8651da177e4SLinus Torvalds deflate_state *s,
8661da177e4SLinus Torvalds int flush
8671da177e4SLinus Torvalds )
8681da177e4SLinus Torvalds {
8691da177e4SLinus Torvalds /* Stored blocks are limited to 0xffff bytes, pending_buf is limited
8701da177e4SLinus Torvalds * to pending_buf_size, and each stored block has a 5 byte header:
8711da177e4SLinus Torvalds */
8721da177e4SLinus Torvalds ulg max_block_size = 0xffff;
8731da177e4SLinus Torvalds ulg max_start;
8741da177e4SLinus Torvalds
8751da177e4SLinus Torvalds if (max_block_size > s->pending_buf_size - 5) {
8761da177e4SLinus Torvalds max_block_size = s->pending_buf_size - 5;
8771da177e4SLinus Torvalds }
8781da177e4SLinus Torvalds
8791da177e4SLinus Torvalds /* Copy as much as possible from input to output: */
8801da177e4SLinus Torvalds for (;;) {
8811da177e4SLinus Torvalds /* Fill the window as much as possible: */
8821da177e4SLinus Torvalds if (s->lookahead <= 1) {
8831da177e4SLinus Torvalds
8841da177e4SLinus Torvalds Assert(s->strstart < s->w_size+MAX_DIST(s) ||
8851da177e4SLinus Torvalds s->block_start >= (long)s->w_size, "slide too late");
8861da177e4SLinus Torvalds
8871da177e4SLinus Torvalds fill_window(s);
8881da177e4SLinus Torvalds if (s->lookahead == 0 && flush == Z_NO_FLUSH) return need_more;
8891da177e4SLinus Torvalds
8901da177e4SLinus Torvalds if (s->lookahead == 0) break; /* flush the current block */
8911da177e4SLinus Torvalds }
8921da177e4SLinus Torvalds Assert(s->block_start >= 0L, "block gone");
8931da177e4SLinus Torvalds
8941da177e4SLinus Torvalds s->strstart += s->lookahead;
8951da177e4SLinus Torvalds s->lookahead = 0;
8961da177e4SLinus Torvalds
8971da177e4SLinus Torvalds /* Emit a stored block if pending_buf will be full: */
8981da177e4SLinus Torvalds max_start = s->block_start + max_block_size;
8991da177e4SLinus Torvalds if (s->strstart == 0 || (ulg)s->strstart >= max_start) {
9001da177e4SLinus Torvalds /* strstart == 0 is possible when wraparound on 16-bit machine */
9011da177e4SLinus Torvalds s->lookahead = (uInt)(s->strstart - max_start);
9021da177e4SLinus Torvalds s->strstart = (uInt)max_start;
9031da177e4SLinus Torvalds FLUSH_BLOCK(s, 0);
9041da177e4SLinus Torvalds }
9051da177e4SLinus Torvalds /* Flush if we may have to slide, otherwise block_start may become
9061da177e4SLinus Torvalds * negative and the data will be gone:
9071da177e4SLinus Torvalds */
9081da177e4SLinus Torvalds if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) {
9091da177e4SLinus Torvalds FLUSH_BLOCK(s, 0);
9101da177e4SLinus Torvalds }
9111da177e4SLinus Torvalds }
9121da177e4SLinus Torvalds FLUSH_BLOCK(s, flush == Z_FINISH);
9131da177e4SLinus Torvalds return flush == Z_FINISH ? finish_done : block_done;
9141da177e4SLinus Torvalds }
9151da177e4SLinus Torvalds
9161da177e4SLinus Torvalds /* ===========================================================================
9171da177e4SLinus Torvalds * Compress as much as possible from the input stream, return the current
9181da177e4SLinus Torvalds * block state.
9191da177e4SLinus Torvalds * This function does not perform lazy evaluation of matches and inserts
9201da177e4SLinus Torvalds * new strings in the dictionary only for unmatched strings or for short
9211da177e4SLinus Torvalds * matches. It is used only for the fast compression options.
9221da177e4SLinus Torvalds */
deflate_fast(deflate_state * s,int flush)9231da177e4SLinus Torvalds static block_state deflate_fast(
9241da177e4SLinus Torvalds deflate_state *s,
9251da177e4SLinus Torvalds int flush
9261da177e4SLinus Torvalds )
9271da177e4SLinus Torvalds {
9281da177e4SLinus Torvalds IPos hash_head = NIL; /* head of the hash chain */
9291da177e4SLinus Torvalds int bflush; /* set if current block must be flushed */
9301da177e4SLinus Torvalds
9311da177e4SLinus Torvalds for (;;) {
9321da177e4SLinus Torvalds /* Make sure that we always have enough lookahead, except
9331da177e4SLinus Torvalds * at the end of the input file. We need MAX_MATCH bytes
9341da177e4SLinus Torvalds * for the next match, plus MIN_MATCH bytes to insert the
9351da177e4SLinus Torvalds * string following the next match.
9361da177e4SLinus Torvalds */
9371da177e4SLinus Torvalds if (s->lookahead < MIN_LOOKAHEAD) {
9381da177e4SLinus Torvalds fill_window(s);
9391da177e4SLinus Torvalds if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
9401da177e4SLinus Torvalds return need_more;
9411da177e4SLinus Torvalds }
9421da177e4SLinus Torvalds if (s->lookahead == 0) break; /* flush the current block */
9431da177e4SLinus Torvalds }
9441da177e4SLinus Torvalds
9451da177e4SLinus Torvalds /* Insert the string window[strstart .. strstart+2] in the
9461da177e4SLinus Torvalds * dictionary, and set hash_head to the head of the hash chain:
9471da177e4SLinus Torvalds */
9481da177e4SLinus Torvalds if (s->lookahead >= MIN_MATCH) {
9491da177e4SLinus Torvalds INSERT_STRING(s, s->strstart, hash_head);
9501da177e4SLinus Torvalds }
9511da177e4SLinus Torvalds
9521da177e4SLinus Torvalds /* Find the longest match, discarding those <= prev_length.
9531da177e4SLinus Torvalds * At this point we have always match_length < MIN_MATCH
9541da177e4SLinus Torvalds */
9551da177e4SLinus Torvalds if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) {
9561da177e4SLinus Torvalds /* To simplify the code, we prevent matches with the string
9571da177e4SLinus Torvalds * of window index 0 (in particular we have to avoid a match
9581da177e4SLinus Torvalds * of the string with itself at the start of the input file).
9591da177e4SLinus Torvalds */
9601da177e4SLinus Torvalds if (s->strategy != Z_HUFFMAN_ONLY) {
9611da177e4SLinus Torvalds s->match_length = longest_match (s, hash_head);
9621da177e4SLinus Torvalds }
9631da177e4SLinus Torvalds /* longest_match() sets match_start */
9641da177e4SLinus Torvalds }
9651da177e4SLinus Torvalds if (s->match_length >= MIN_MATCH) {
9661da177e4SLinus Torvalds check_match(s, s->strstart, s->match_start, s->match_length);
9671da177e4SLinus Torvalds
9681da177e4SLinus Torvalds bflush = zlib_tr_tally(s, s->strstart - s->match_start,
9691da177e4SLinus Torvalds s->match_length - MIN_MATCH);
9701da177e4SLinus Torvalds
9711da177e4SLinus Torvalds s->lookahead -= s->match_length;
9721da177e4SLinus Torvalds
9731da177e4SLinus Torvalds /* Insert new strings in the hash table only if the match length
9741da177e4SLinus Torvalds * is not too large. This saves time but degrades compression.
9751da177e4SLinus Torvalds */
9761da177e4SLinus Torvalds if (s->match_length <= s->max_insert_length &&
9771da177e4SLinus Torvalds s->lookahead >= MIN_MATCH) {
9781da177e4SLinus Torvalds s->match_length--; /* string at strstart already in hash table */
9791da177e4SLinus Torvalds do {
9801da177e4SLinus Torvalds s->strstart++;
9811da177e4SLinus Torvalds INSERT_STRING(s, s->strstart, hash_head);
9821da177e4SLinus Torvalds /* strstart never exceeds WSIZE-MAX_MATCH, so there are
9831da177e4SLinus Torvalds * always MIN_MATCH bytes ahead.
9841da177e4SLinus Torvalds */
9851da177e4SLinus Torvalds } while (--s->match_length != 0);
9861da177e4SLinus Torvalds s->strstart++;
9871da177e4SLinus Torvalds } else {
9881da177e4SLinus Torvalds s->strstart += s->match_length;
9891da177e4SLinus Torvalds s->match_length = 0;
9901da177e4SLinus Torvalds s->ins_h = s->window[s->strstart];
9911da177e4SLinus Torvalds UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
9921da177e4SLinus Torvalds #if MIN_MATCH != 3
9931da177e4SLinus Torvalds Call UPDATE_HASH() MIN_MATCH-3 more times
9941da177e4SLinus Torvalds #endif
9951da177e4SLinus Torvalds /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not
9961da177e4SLinus Torvalds * matter since it will be recomputed at next deflate call.
9971da177e4SLinus Torvalds */
9981da177e4SLinus Torvalds }
9991da177e4SLinus Torvalds } else {
10001da177e4SLinus Torvalds /* No match, output a literal byte */
10011da177e4SLinus Torvalds Tracevv((stderr,"%c", s->window[s->strstart]));
10021da177e4SLinus Torvalds bflush = zlib_tr_tally (s, 0, s->window[s->strstart]);
10031da177e4SLinus Torvalds s->lookahead--;
10041da177e4SLinus Torvalds s->strstart++;
10051da177e4SLinus Torvalds }
10061da177e4SLinus Torvalds if (bflush) FLUSH_BLOCK(s, 0);
10071da177e4SLinus Torvalds }
10081da177e4SLinus Torvalds FLUSH_BLOCK(s, flush == Z_FINISH);
10091da177e4SLinus Torvalds return flush == Z_FINISH ? finish_done : block_done;
10101da177e4SLinus Torvalds }
10111da177e4SLinus Torvalds
10121da177e4SLinus Torvalds /* ===========================================================================
10131da177e4SLinus Torvalds * Same as above, but achieves better compression. We use a lazy
10141da177e4SLinus Torvalds * evaluation for matches: a match is finally adopted only if there is
10151da177e4SLinus Torvalds * no better match at the next window position.
10161da177e4SLinus Torvalds */
deflate_slow(deflate_state * s,int flush)10171da177e4SLinus Torvalds static block_state deflate_slow(
10181da177e4SLinus Torvalds deflate_state *s,
10191da177e4SLinus Torvalds int flush
10201da177e4SLinus Torvalds )
10211da177e4SLinus Torvalds {
10221da177e4SLinus Torvalds IPos hash_head = NIL; /* head of hash chain */
10231da177e4SLinus Torvalds int bflush; /* set if current block must be flushed */
10241da177e4SLinus Torvalds
10251da177e4SLinus Torvalds /* Process the input block. */
10261da177e4SLinus Torvalds for (;;) {
10271da177e4SLinus Torvalds /* Make sure that we always have enough lookahead, except
10281da177e4SLinus Torvalds * at the end of the input file. We need MAX_MATCH bytes
10291da177e4SLinus Torvalds * for the next match, plus MIN_MATCH bytes to insert the
10301da177e4SLinus Torvalds * string following the next match.
10311da177e4SLinus Torvalds */
10321da177e4SLinus Torvalds if (s->lookahead < MIN_LOOKAHEAD) {
10331da177e4SLinus Torvalds fill_window(s);
10341da177e4SLinus Torvalds if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
10351da177e4SLinus Torvalds return need_more;
10361da177e4SLinus Torvalds }
10371da177e4SLinus Torvalds if (s->lookahead == 0) break; /* flush the current block */
10381da177e4SLinus Torvalds }
10391da177e4SLinus Torvalds
10401da177e4SLinus Torvalds /* Insert the string window[strstart .. strstart+2] in the
10411da177e4SLinus Torvalds * dictionary, and set hash_head to the head of the hash chain:
10421da177e4SLinus Torvalds */
10431da177e4SLinus Torvalds if (s->lookahead >= MIN_MATCH) {
10441da177e4SLinus Torvalds INSERT_STRING(s, s->strstart, hash_head);
10451da177e4SLinus Torvalds }
10461da177e4SLinus Torvalds
10471da177e4SLinus Torvalds /* Find the longest match, discarding those <= prev_length.
10481da177e4SLinus Torvalds */
10491da177e4SLinus Torvalds s->prev_length = s->match_length, s->prev_match = s->match_start;
10501da177e4SLinus Torvalds s->match_length = MIN_MATCH-1;
10511da177e4SLinus Torvalds
10521da177e4SLinus Torvalds if (hash_head != NIL && s->prev_length < s->max_lazy_match &&
10531da177e4SLinus Torvalds s->strstart - hash_head <= MAX_DIST(s)) {
10541da177e4SLinus Torvalds /* To simplify the code, we prevent matches with the string
10551da177e4SLinus Torvalds * of window index 0 (in particular we have to avoid a match
10561da177e4SLinus Torvalds * of the string with itself at the start of the input file).
10571da177e4SLinus Torvalds */
10581da177e4SLinus Torvalds if (s->strategy != Z_HUFFMAN_ONLY) {
10591da177e4SLinus Torvalds s->match_length = longest_match (s, hash_head);
10601da177e4SLinus Torvalds }
10611da177e4SLinus Torvalds /* longest_match() sets match_start */
10621da177e4SLinus Torvalds
10631da177e4SLinus Torvalds if (s->match_length <= 5 && (s->strategy == Z_FILTERED ||
10641da177e4SLinus Torvalds (s->match_length == MIN_MATCH &&
10651da177e4SLinus Torvalds s->strstart - s->match_start > TOO_FAR))) {
10661da177e4SLinus Torvalds
10671da177e4SLinus Torvalds /* If prev_match is also MIN_MATCH, match_start is garbage
10681da177e4SLinus Torvalds * but we will ignore the current match anyway.
10691da177e4SLinus Torvalds */
10701da177e4SLinus Torvalds s->match_length = MIN_MATCH-1;
10711da177e4SLinus Torvalds }
10721da177e4SLinus Torvalds }
10731da177e4SLinus Torvalds /* If there was a match at the previous step and the current
10741da177e4SLinus Torvalds * match is not better, output the previous match:
10751da177e4SLinus Torvalds */
10761da177e4SLinus Torvalds if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) {
10771da177e4SLinus Torvalds uInt max_insert = s->strstart + s->lookahead - MIN_MATCH;
10781da177e4SLinus Torvalds /* Do not insert strings in hash table beyond this. */
10791da177e4SLinus Torvalds
10801da177e4SLinus Torvalds check_match(s, s->strstart-1, s->prev_match, s->prev_length);
10811da177e4SLinus Torvalds
10821da177e4SLinus Torvalds bflush = zlib_tr_tally(s, s->strstart -1 - s->prev_match,
10831da177e4SLinus Torvalds s->prev_length - MIN_MATCH);
10841da177e4SLinus Torvalds
10851da177e4SLinus Torvalds /* Insert in hash table all strings up to the end of the match.
10861da177e4SLinus Torvalds * strstart-1 and strstart are already inserted. If there is not
10871da177e4SLinus Torvalds * enough lookahead, the last two strings are not inserted in
10881da177e4SLinus Torvalds * the hash table.
10891da177e4SLinus Torvalds */
10901da177e4SLinus Torvalds s->lookahead -= s->prev_length-1;
10911da177e4SLinus Torvalds s->prev_length -= 2;
10921da177e4SLinus Torvalds do {
10931da177e4SLinus Torvalds if (++s->strstart <= max_insert) {
10941da177e4SLinus Torvalds INSERT_STRING(s, s->strstart, hash_head);
10951da177e4SLinus Torvalds }
10961da177e4SLinus Torvalds } while (--s->prev_length != 0);
10971da177e4SLinus Torvalds s->match_available = 0;
10981da177e4SLinus Torvalds s->match_length = MIN_MATCH-1;
10991da177e4SLinus Torvalds s->strstart++;
11001da177e4SLinus Torvalds
11011da177e4SLinus Torvalds if (bflush) FLUSH_BLOCK(s, 0);
11021da177e4SLinus Torvalds
11031da177e4SLinus Torvalds } else if (s->match_available) {
11041da177e4SLinus Torvalds /* If there was no match at the previous position, output a
11051da177e4SLinus Torvalds * single literal. If there was a match but the current match
11061da177e4SLinus Torvalds * is longer, truncate the previous match to a single literal.
11071da177e4SLinus Torvalds */
11081da177e4SLinus Torvalds Tracevv((stderr,"%c", s->window[s->strstart-1]));
11091da177e4SLinus Torvalds if (zlib_tr_tally (s, 0, s->window[s->strstart-1])) {
11101da177e4SLinus Torvalds FLUSH_BLOCK_ONLY(s, 0);
11111da177e4SLinus Torvalds }
11121da177e4SLinus Torvalds s->strstart++;
11131da177e4SLinus Torvalds s->lookahead--;
11141da177e4SLinus Torvalds if (s->strm->avail_out == 0) return need_more;
11151da177e4SLinus Torvalds } else {
11161da177e4SLinus Torvalds /* There is no previous match to compare with, wait for
11171da177e4SLinus Torvalds * the next step to decide.
11181da177e4SLinus Torvalds */
11191da177e4SLinus Torvalds s->match_available = 1;
11201da177e4SLinus Torvalds s->strstart++;
11211da177e4SLinus Torvalds s->lookahead--;
11221da177e4SLinus Torvalds }
11231da177e4SLinus Torvalds }
11241da177e4SLinus Torvalds Assert (flush != Z_NO_FLUSH, "no flush?");
11251da177e4SLinus Torvalds if (s->match_available) {
11261da177e4SLinus Torvalds Tracevv((stderr,"%c", s->window[s->strstart-1]));
11271da177e4SLinus Torvalds zlib_tr_tally (s, 0, s->window[s->strstart-1]);
11281da177e4SLinus Torvalds s->match_available = 0;
11291da177e4SLinus Torvalds }
11301da177e4SLinus Torvalds FLUSH_BLOCK(s, flush == Z_FINISH);
11311da177e4SLinus Torvalds return flush == Z_FINISH ? finish_done : block_done;
11321da177e4SLinus Torvalds }
11331da177e4SLinus Torvalds
zlib_deflate_workspacesize(int windowBits,int memLevel)1134565d76cbSJim Keniston int zlib_deflate_workspacesize(int windowBits, int memLevel)
11351da177e4SLinus Torvalds {
1136565d76cbSJim Keniston if (windowBits < 0) /* undocumented feature: suppress zlib header */
1137565d76cbSJim Keniston windowBits = -windowBits;
1138565d76cbSJim Keniston
1139565d76cbSJim Keniston /* Since the return value is typically passed to vmalloc() unchecked... */
1140565d76cbSJim Keniston BUG_ON(memLevel < 1 || memLevel > MAX_MEM_LEVEL || windowBits < 9 ||
1141565d76cbSJim Keniston windowBits > 15);
1142565d76cbSJim Keniston
1143565d76cbSJim Keniston return sizeof(deflate_workspace)
1144565d76cbSJim Keniston + zlib_deflate_window_memsize(windowBits)
1145565d76cbSJim Keniston + zlib_deflate_prev_memsize(windowBits)
1146565d76cbSJim Keniston + zlib_deflate_head_memsize(memLevel)
1147565d76cbSJim Keniston + zlib_deflate_overlay_memsize(memLevel);
11481da177e4SLinus Torvalds }
1149803521b1SMikhail Zaslonko
zlib_deflate_dfltcc_enabled(void)1150803521b1SMikhail Zaslonko int zlib_deflate_dfltcc_enabled(void)
1151803521b1SMikhail Zaslonko {
1152803521b1SMikhail Zaslonko return DEFLATE_DFLTCC_ENABLED();
1153803521b1SMikhail Zaslonko }
1154