/* deflate.c -- compress data using the deflation algorithm

* Copyright (C) 1995-2024 Jean-loup Gailly and Mark Adler

* For conditions of distribution and use, see copyright notice in zlib.h

*/

/*

* ALGORITHM

*

* The "deflation" process depends on being able to identify portions

* of the input text which are identical to earlier input (within a

* sliding window trailing behind the input currently being processed).

*

* The most straightforward technique turns out to be the fastest for

* most input files: try all possible matches and select the longest.

* The key feature of this algorithm is that insertions into the string

* dictionary are very simple and thus fast, and deletions are avoided

* completely. Insertions are performed at each input character, whereas

* string matches are performed only when the previous match ends. So it

* is preferable to spend more time in matches to allow very fast string

* insertions and avoid deletions. The matching algorithm for small

* strings is inspired from that of Rabin & Karp. A brute force approach

* is used to find longer strings when a small match has been found.

* A similar algorithm is used in comic (by Jan-Mark Wams) and freeze

* (by Leonid Broukhis).

* A previous version of this file used a more sophisticated algorithm

* (by Fiala and Greene) which is guaranteed to run in linear amortized

* time, but has a larger average cost, uses more memory and is patented.

* However the F&G algorithm may be faster for some highly redundant

* files if the parameter max_chain_length (described below) is too large.

*

* ACKNOWLEDGEMENTS

*

* The idea of lazy evaluation of matches is due to Jan-Mark Wams, and

* I found it in 'freeze' written by Leonid Broukhis.

* Thanks to many people for bug reports and testing.

*

* REFERENCES

*

* Deutsch, L.P.,"DEFLATE Compressed Data Format Specification".

* Available in http://tools.ietf.org/html/rfc1951

*

* A description of the Rabin and Karp algorithm is given in the book

* "Algorithms" by R. Sedgewick, Addison-Wesley, p252.

*

* Fiala,E.R., and Greene,D.H.

* Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595

*

*/

/* @(#) $Id$ */

#include <assert.h>

#include "deflate.h"

#include "cpu_features.h"

#if defined(DEFLATE_SLIDE_HASH_SSE2) || defined(DEFLATE_SLIDE_HASH_NEON)

#include "slide_hash_simd.h"

#endif

#if defined(QAT_COMPRESSION_ENABLED)

#include "contrib/qat/deflate_qat.h"

#endif

#include "contrib/optimizations/insert_string.h"

#ifdef FASTEST

/* See http://crbug.com/1113596 */

#error "FASTEST is not supported in Chromium's zlib."

#endif

const char deflate_copyright[] =

" deflate 1.3.1 Copyright 1995-2024 Jean-loup Gailly and Mark Adler ";

/*

If you use the zlib library in a product, an acknowledgment is welcome

in the documentation of your product. If for some reason you cannot

include such an acknowledgment, I would appreciate that you keep this

copyright string in the executable of your product.

*/

typedef enum {

need_more, /* block not completed, need more input or more output */

block_done, /* block flush performed */

finish_started, /* finish started, need only more output at next deflate */

finish_done /* finish done, accept no more input or output */

} block_state;

typedef block_state (*compress_func)(deflate_state *s, int flush);

/* Compression function. Returns the block state after the call. */

local block_state deflate_stored(deflate_state *s, int flush);

local block_state deflate_fast(deflate_state *s, int flush);

#ifndef FASTEST

local block_state deflate_slow(deflate_state *s, int flush);

#endif

local block_state deflate_rle(deflate_state *s, int flush);

local block_state deflate_huff(deflate_state *s, int flush);

/* From crc32.c */

extern void ZLIB_INTERNAL crc_reset(deflate_state *const s);

extern void ZLIB_INTERNAL crc_finalize(deflate_state *const s);

extern void ZLIB_INTERNAL copy_with_crc(z_streamp strm, Bytef *dst, long size);

/* ===========================================================================

* Local data

*/

#define NIL 0

/* Tail of hash chains */

#ifndef TOO_FAR

# define TOO_FAR 4096

#endif

/* Matches of length 3 are discarded if their distance exceeds TOO_FAR */

/* Values for max_lazy_match, good_match and max_chain_length, depending on

* the desired pack level (0..9). The values given below have been tuned to

* exclude worst case performance for pathological files. Better values may be

* found for specific files.

*/

typedef struct config_s {

ush good_length; /* reduce lazy search above this match length */

ush max_lazy; /* do not perform lazy search above this match length */

ush nice_length; /* quit search above this match length */

ush max_chain;

compress_func func;

} config;

#ifdef FASTEST

local const config configuration_table[2] = {

/* good lazy nice chain */

/* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */

/* 1 */ {4, 4, 8, 4, deflate_fast}}; /* max speed, no lazy matches */

#else

local const config configuration_table[10] = {

/* good lazy nice chain */

/* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */

/* 1 */ {4, 4, 8, 4, deflate_fast}, /* max speed, no lazy matches */

/* 2 */ {4, 5, 16, 8, deflate_fast},

/* 3 */ {4, 6, 32, 32, deflate_fast},

/* 4 */ {4, 4, 16, 16, deflate_slow}, /* lazy matches */

/* 5 */ {8, 16, 32, 32, deflate_slow},

/* 6 */ {8, 16, 128, 128, deflate_slow},

/* 7 */ {8, 32, 128, 256, deflate_slow},

/* 8 */ {32, 128, 258, 1024, deflate_slow},

/* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* max compression */

#endif

/* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4

* For deflate_fast() (levels <= 3) good is ignored and lazy has a different

* meaning.

*/

/* rank Z_BLOCK between Z_NO_FLUSH and Z_PARTIAL_FLUSH */

#define RANK(f) (((f) * 2) - ((f) > 4 ? 9 : 0))

/* ===========================================================================

* Initialize the hash table (avoiding 64K overflow for 16 bit systems).

* prev[] will be initialized on the fly.

* TODO(cavalcantii): optimization opportunity, check comments on:

* https://chromium-review.googlesource.com/c/chromium/src/+/3561506/

*/

#define CLEAR_HASH(s) \

do { \

s->head[s->hash_size - 1] = NIL; \

zmemzero((Bytef *)s->head, \

(unsigned)(s->hash_size - 1)*sizeof(*s->head)); \

} while (0)

/* ===========================================================================

* Slide the hash table when sliding the window down (could be avoided with 32

* bit values at the expense of memory usage). We slide even when level == 0 to

* keep the hash table consistent if we switch back to level > 0 later.

*/

#if defined(__has_feature)

# if __has_feature(memory_sanitizer)

__attribute__((no_sanitize("memory")))

# endif

#endif

local void slide_hash(deflate_state *s) {

#if defined(DEFLATE_SLIDE_HASH_SSE2) || defined(DEFLATE_SLIDE_HASH_NEON)

slide_hash_simd(s->head, s->prev, s->w_size, s->hash_size);

return;

#endif

unsigned n, m;

Posf *p;

uInt wsize = s->w_size;

n = s->hash_size;

p = &s->head[n];

do {

m = *--p;

*p = (Pos)(m >= wsize ? m - wsize : NIL);

} while (--n);

n = wsize;

#ifndef FASTEST

p = &s->prev[n];

do {

m = *--p;

*p = (Pos)(m >= wsize ? m - wsize : NIL);

/* If n is not on any hash chain, prev[n] is garbage but

* its value will never be used.

*/

} while (--n);

#endif

}

/* ===========================================================================

* Read a new buffer from the current input stream, update the adler32

* and total number of bytes read. All deflate() input goes through

* this function so some applications may wish to modify it to avoid

* allocating a large strm->next_in buffer and copying from it.

* (See also flush_pending()).

*/

local unsigned read_buf(z_streamp strm, Bytef *buf, unsigned size) {

unsigned len = strm->avail_in;

if (len > size) len = size;

if (len == 0) return 0;

strm->avail_in -= len;

/* TODO(cavalcantii): verify if we can remove 'copy_with_crc', it is legacy

* of the Intel optimizations dating back to 2015.

*/

#ifdef GZIP

if (strm->state->wrap == 2)

copy_with_crc(strm, buf, len);

else

#endif

{

zmemcpy(buf, strm->next_in, len);

if (strm->state->wrap == 1)

strm->adler = adler32(strm->adler, buf, len);

}

strm->next_in += len;

strm->total_in += len;

return len;

}

/* ===========================================================================

* Fill the window when the lookahead becomes insufficient.

* Updates strstart and lookahead.

*

* IN assertion: lookahead < MIN_LOOKAHEAD

* OUT assertions: strstart <= window_size-MIN_LOOKAHEAD

* At least one byte has been read, or avail_in == 0; reads are

* performed for at least two bytes (required for the zip translate_eol

* option -- not supported here).

*/

local void fill_window(deflate_state *s) {

unsigned n;

unsigned more; /* Amount of free space at the end of the window. */

uInt wsize = s->w_size;

Assert(s->lookahead < MIN_LOOKAHEAD, "already enough lookahead");

do {

more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart);

/* Deal with !@#$% 64K limit: */

if (sizeof(int) <= 2) {

if (more == 0 && s->strstart == 0 && s->lookahead == 0) {

more = wsize;

} else if (more == (unsigned)(-1)) {

/* Very unlikely, but possible on 16 bit machine if

* strstart == 0 && lookahead == 1 (input done a byte at time)

*/

more--;

}

}

/* If the window is almost full and there is insufficient lookahead,

* move the upper half to the lower one to make room in the upper half.

*/

if (s->strstart >= wsize + MAX_DIST(s)) {

zmemcpy(s->window, s->window + wsize, (unsigned)wsize - more);

s->match_start -= wsize;

s->strstart -= wsize; /* we now have strstart >= MAX_DIST */

s->block_start -= (long) wsize;

if (s->insert > s->strstart)

s->insert = s->strstart;

slide_hash(s);

more += wsize;

}

if (s->strm->avail_in == 0) break;

/* If there was no sliding:

* strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 &&

* more == window_size - lookahead - strstart

* => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1)

* => more >= window_size - 2*WSIZE + 2

* In the BIG_MEM or MMAP case (not yet supported),

* window_size == input_size + MIN_LOOKAHEAD &&

* strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD.

* Otherwise, window_size == 2*WSIZE so more >= 2.

* If there was sliding, more >= WSIZE. So in all cases, more >= 2.

*/

Assert(more >= 2, "more < 2");

n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more);

s->lookahead += n;

/* Initialize the hash value now that we have some input: */

if (s->chromium_zlib_hash) {

/* chromium hash reads 4 bytes */

if (s->lookahead + s->insert > MIN_MATCH) {

uInt str = s->strstart - s->insert;

while (s->insert) {

insert_string(s, str);

str++;

s->insert--;

if (s->lookahead + s->insert <= MIN_MATCH)

break;

}

}

} else

/* Initialize the hash value now that we have some input: */

if (s->lookahead + s->insert >= MIN_MATCH) {

uInt str = s->strstart - s->insert;

s->ins_h = s->window[str];

UPDATE_HASH(s, s->ins_h, s->window[str + 1]);

#if MIN_MATCH != 3

Call UPDATE_HASH() MIN_MATCH-3 more times

#endif

while (s->insert) {

UPDATE_HASH(s, s->ins_h, s->window[str + MIN_MATCH-1]);

#ifndef FASTEST

s->prev[str & s->w_mask] = s->head[s->ins_h];

#endif

s->head[s->ins_h] = (Pos)str;

str++;

s->insert--;

if (s->lookahead + s->insert < MIN_MATCH)

break;

}

}

/* If the whole input has less than MIN_MATCH bytes, ins_h is garbage,

* but this is not important since only literal bytes will be emitted.

*/

} while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0);

/* If the WIN_INIT bytes after the end of the current data have never been

* written, then zero those bytes in order to avoid memory check reports of

* the use of uninitialized (or uninitialised as Julian writes) bytes by

* the longest match routines. Update the high water mark for the next

* time through here. WIN_INIT is set to MAX_MATCH since the longest match

* routines allow scanning to strstart + MAX_MATCH, ignoring lookahead.

*/

if (s->high_water < s->window_size) {

ulg curr = s->strstart + (ulg)(s->lookahead);

ulg init;

if (s->high_water < curr) {

/* Previous high water mark below current data -- zero WIN_INIT

* bytes or up to end of window, whichever is less.

*/

init = s->window_size - curr;

if (init > WIN_INIT)

init = WIN_INIT;

zmemzero(s->window + curr, (unsigned)init);

s->high_water = curr + init;

}

else if (s->high_water < (ulg)curr + WIN_INIT) {

/* High water mark at or above current data, but below current data

* plus WIN_INIT -- zero out to current data plus WIN_INIT, or up

* to end of window, whichever is less.

*/

init = (ulg)curr + WIN_INIT - s->high_water;

if (init > s->window_size - s->high_water)

init = s->window_size - s->high_water;

zmemzero(s->window + s->high_water, (unsigned)init);

s->high_water += init;

}

}

Assert((ulg)s->strstart <= s->window_size - MIN_LOOKAHEAD,

"not enough room for search");

}

/* ========================================================================= */

int ZEXPORT deflateInit_(z_streamp strm, int level, const char *version,

int stream_size) {

return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL,

Z_DEFAULT_STRATEGY, version, stream_size);

/* To do: ignore strm->next_in if we use it as window */

}

#define WINDOW_PADDING 8

/* ========================================================================= */

int ZEXPORT deflateInit2_(z_streamp strm, int level, int method,

int windowBits, int memLevel, int strategy,

const char *version, int stream_size) {

deflate_state *s;

int wrap = 1;

static const char my_version[] = ZLIB_VERSION;

// Needed to activate optimized insert_string() that helps compression

// for all wrapper formats (e.g. RAW, ZLIB, GZIP).

// Feature detection is not triggered while using RAW mode (i.e. we never

// call crc32() with a NULL buffer).

#if defined(CRC32_ARMV8_CRC32) || defined(CRC32_SIMD_SSE42_PCLMUL) \

|| defined(RISCV_RVV)

cpu_check_features();

#endif

if (version == Z_NULL || version[0] != my_version[0] ||

stream_size != sizeof(z_stream)) {

return Z_VERSION_ERROR;

}

if (strm == Z_NULL) return Z_STREAM_ERROR;

strm->msg = Z_NULL;

if (strm->zalloc == (alloc_func)0) {

#ifdef Z_SOLO

return Z_STREAM_ERROR;

#else

strm->zalloc = zcalloc;

strm->opaque = (voidpf)0;

#endif

}

if (strm->zfree == (free_func)0)

#ifdef Z_SOLO

return Z_STREAM_ERROR;

#else

strm->zfree = zcfree;

#endif

#ifdef FASTEST

if (level != 0) level = 1;

#else

if (level == Z_DEFAULT_COMPRESSION) level = 6;

#endif

if (windowBits < 0) { /* suppress zlib wrapper */

wrap = 0;

if (windowBits < -15)

return Z_STREAM_ERROR;

windowBits = -windowBits;

}

#ifdef GZIP

else if (windowBits > 15) {

wrap = 2; /* write gzip wrapper instead */

windowBits -= 16;

}

#endif

if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED ||

windowBits < 8 || windowBits > 15 || level < 0 || level > 9 ||

strategy < 0 || strategy > Z_FIXED || (windowBits == 8 && wrap != 1)) {

return Z_STREAM_ERROR;

}

if (windowBits == 8) windowBits = 9; /* until 256-byte window bug fixed */

s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state));

if (s == Z_NULL) return Z_MEM_ERROR;

strm->state = (struct internal_state FAR *)s;

s->strm = strm;

s->status = INIT_STATE; /* to pass state test in deflateReset() */

s->wrap = wrap;

s->gzhead = Z_NULL;

s->w_bits = (uInt)windowBits;

s->w_size = 1 << s->w_bits;

s->w_mask = s->w_size - 1;

s->chromium_zlib_hash = 1;

#if defined(USE_ZLIB_RABIN_KARP_ROLLING_HASH)

s->chromium_zlib_hash = 0;

#endif

s->hash_bits = memLevel + 7;

if (s->chromium_zlib_hash && s->hash_bits < 15) {

s->hash_bits = 15;

}

s->hash_size = 1 << s->hash_bits;

s->hash_mask = s->hash_size - 1;

s->hash_shift = ((s->hash_bits + MIN_MATCH-1) / MIN_MATCH);

s->window = (Bytef *) ZALLOC(strm,

s->w_size + WINDOW_PADDING,

2*sizeof(Byte));

s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos));

s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos));

s->high_water = 0; /* nothing written to s->window yet */

s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */

/* We overlay pending_buf and sym_buf. This works since the average size

* for length/distance pairs over any compressed block is assured to be 31

* bits or less.

*

* Analysis: The longest fixed codes are a length code of 8 bits plus 5

* extra bits, for lengths 131 to 257. The longest fixed distance codes are

* 5 bits plus 13 extra bits, for distances 16385 to 32768. The longest

* possible fixed-codes length/distance pair is then 31 bits total.

*

* sym_buf starts one-fourth of the way into pending_buf. So there are

* three bytes in sym_buf for every four bytes in pending_buf. Each symbol

* in sym_buf is three bytes -- two for the distance and one for the

* literal/length. As each symbol is consumed, the pointer to the next

* sym_buf value to read moves forward three bytes. From that symbol, up to

* 31 bits are written to pending_buf. The closest the written pending_buf

* bits gets to the next sym_buf symbol to read is just before the last

* code is written. At that time, 31*(n - 2) bits have been written, just

* after 24*(n - 2) bits have been consumed from sym_buf. sym_buf starts at

* 8*n bits into pending_buf. (Note that the symbol buffer fills when n - 1

* symbols are written.) The closest the writing gets to what is unread is

* then n + 14 bits. Here n is lit_bufsize, which is 16384 by default, and

* can range from 128 to 32768.

*

* Therefore, at a minimum, there are 142 bits of space between what is

* written and what is read in the overlain buffers, so the symbols cannot

* be overwritten by the compressed data. That space is actually 139 bits,

* due to the three-bit fixed-code block header.

*

* That covers the case where either Z_FIXED is specified, forcing fixed

* codes, or when the use of fixed codes is chosen, because that choice

* results in a smaller compressed block than dynamic codes. That latter

* condition then assures that the above analysis also covers all dynamic

* blocks. A dynamic-code block will only be chosen to be emitted if it has

* fewer bits than a fixed-code block would for the same set of symbols.

* Therefore its average symbol length is assured to be less than 31. So

* the compressed data for a dynamic block also cannot overwrite the

* symbols from which it is being constructed.

*/

#ifdef LIT_MEM

s->pending_buf = (uchf *) ZALLOC(strm, s->lit_bufsize, 5);

#else

s->pending_buf = (uchf *) ZALLOC(strm, s->lit_bufsize, 4);

#endif

s->pending_buf_size = (ulg)s->lit_bufsize * 4;

if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL ||

s->pending_buf == Z_NULL) {

s->status = FINISH_STATE;

strm->msg = ERR_MSG(Z_MEM_ERROR);

deflateEnd (strm);

return Z_MEM_ERROR;

}

/* Avoid use of unitialized values in the window, see crbug.com/1137613 and

* crbug.com/1144420 */

zmemzero(s->window, (s->w_size + WINDOW_PADDING) * (2 * sizeof(Byte)));

/* Avoid use of uninitialized value, see:

* https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=11360

*/

zmemzero(s->prev, s->w_size * sizeof(Pos));

#ifdef LIT_MEM

s->d_buf = (ushf *)(s->pending_buf + (s->lit_bufsize << 1));

s->l_buf = s->pending_buf + (s->lit_bufsize << 2);

s->sym_end = s->lit_bufsize - 1;

#else

s->sym_buf = s->pending_buf + s->lit_bufsize;

s->sym_end = (s->lit_bufsize - 1) * 3;

#endif

/* We avoid equality with lit_bufsize*3 because of wraparound at 64K

* on 16 bit machines and because stored blocks are restricted to

* 64K-1 bytes.

*/

s->level = level;

s->strategy = strategy;

s->method = (Byte)method;

#if defined(QAT_COMPRESSION_ENABLED)

s->qat_s = NULL;

if (s->level && qat_deflate_init() == Z_OK) {

s->qat_s = qat_deflate_state_init(s->level, s->wrap);

}

#endif

return deflateReset(strm);

}

/* =========================================================================

* Check for a valid deflate stream state. Return 0 if ok, 1 if not.

*/

local int deflateStateCheck(z_streamp strm) {

deflate_state *s;

if (strm == Z_NULL ||

strm->zalloc == (alloc_func)0 || strm->zfree == (free_func)0)

return 1;

s = strm->state;

if (s == Z_NULL || s->strm != strm || (s->status != INIT_STATE &&

#ifdef GZIP

s->status != GZIP_STATE &&

#endif

s->status != EXTRA_STATE &&

s->status != NAME_STATE &&

s->status != COMMENT_STATE &&

s->status != HCRC_STATE &&

s->status != BUSY_STATE &&

s->status != FINISH_STATE))

return 1;

return 0;

}

/* ========================================================================= */

int ZEXPORT deflateSetDictionary(z_streamp strm, const Bytef *dictionary,

uInt dictLength) {

deflate_state *s;

uInt str, n;

int wrap;

unsigned avail;

z_const unsigned char *next;

if (deflateStateCheck(strm) || dictionary == Z_NULL)

return Z_STREAM_ERROR;

s = strm->state;

wrap = s->wrap;

if (wrap == 2 || (wrap == 1 && s->status != INIT_STATE) || s->lookahead)

return Z_STREAM_ERROR;

/* when using zlib wrappers, compute Adler-32 for provided dictionary */

if (wrap == 1)

strm->adler = adler32(strm->adler, dictionary, dictLength);

s->wrap = 0; /* avoid computing Adler-32 in read_buf */

/* if dictionary would fill window, just replace the history */

if (dictLength >= s->w_size) {

if (wrap == 0) { /* already empty otherwise */

CLEAR_HASH(s);

s->strstart = 0;

s->block_start = 0L;

s->insert = 0;

}

dictionary += dictLength - s->w_size; /* use the tail */

dictLength = s->w_size;

}

/* insert dictionary into window and hash */

avail = strm->avail_in;

next = strm->next_in;

strm->avail_in = dictLength;

strm->next_in = (z_const Bytef *)dictionary;

fill_window(s);

while (s->lookahead >= MIN_MATCH) {

str = s->strstart;

n = s->lookahead - (MIN_MATCH-1);

do {

insert_string(s, str);

str++;

} while (--n);

s->strstart = str;

s->lookahead = MIN_MATCH-1;

fill_window(s);

}

s->strstart += s->lookahead;

s->block_start = (long)s->strstart;

s->insert = s->lookahead;

s->lookahead = 0;

s->match_length = s->prev_length = MIN_MATCH-1;

s->match_available = 0;

strm->next_in = next;

strm->avail_in = avail;

s->wrap = wrap;

return Z_OK;

}

/* ========================================================================= */

int ZEXPORT deflateGetDictionary(z_streamp strm, Bytef *dictionary,

uInt *dictLength) {

deflate_state *s;

uInt len;

if (deflateStateCheck(strm))

return Z_STREAM_ERROR;

s = strm->state;

len = s->strstart + s->lookahead;

if (len > s->w_size)

len = s->w_size;

if (dictionary != Z_NULL && len)

zmemcpy(dictionary, s->window + s->strstart + s->lookahead - len, len);

if (dictLength != Z_NULL)

*dictLength = len;

return Z_OK;

}

/* ========================================================================= */

int ZEXPORT deflateResetKeep(z_streamp strm) {

deflate_state *s;

if (deflateStateCheck(strm)) {

return Z_STREAM_ERROR;

}

strm->total_in = strm->total_out = 0;

strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */

strm->data_type = Z_UNKNOWN;

s = (deflate_state *)strm->state;

s->pending = 0;

s->pending_out = s->pending_buf;

if (s->wrap < 0) {

s->wrap = -s->wrap; /* was made negative by deflate(..., Z_FINISH); */

}

s->status =

#ifdef GZIP

s->wrap == 2 ? GZIP_STATE :

#endif

INIT_STATE;

strm->adler =

#ifdef GZIP

s->wrap == 2 ? crc32(0L, Z_NULL, 0) :

#endif

adler32(0L, Z_NULL, 0);

s->last_flush = -2;

_tr_init(s);

return Z_OK;

}

/* ===========================================================================

* Initialize the "longest match" routines for a new zlib stream

*/

local void lm_init(deflate_state *s) {

s->window_size = (ulg)2L*s->w_size;

CLEAR_HASH(s);

/* Set the default configuration parameters:

*/

s->max_lazy_match = configuration_table[s->level].max_lazy;

s->good_match = configuration_table[s->level].good_length;

s->nice_match = configuration_table[s->level].nice_length;

s->max_chain_length = configuration_table[s->level].max_chain;

s->strstart = 0;

s->block_start = 0L;

s->lookahead = 0;

s->insert = 0;

s->match_length = s->prev_length = MIN_MATCH-1;

s->match_available = 0;

s->ins_h = 0;

}

/* ========================================================================= */

int ZEXPORT deflateReset(z_streamp strm) {

int ret;

ret = deflateResetKeep(strm);

if (ret == Z_OK)

lm_init(strm->state);

return ret;

}

/* ========================================================================= */

int ZEXPORT deflateSetHeader(z_streamp strm, gz_headerp head) {

if (deflateStateCheck(strm) || strm->state->wrap != 2)

return Z_STREAM_ERROR;

strm->state->gzhead = head;

return Z_OK;

}

/* ========================================================================= */

int ZEXPORT deflatePending(z_streamp strm, unsigned *pending, int *bits) {

if (deflateStateCheck(strm)) return Z_STREAM_ERROR;

if (pending != Z_NULL)

*pending = strm->state->pending;

if (bits != Z_NULL)

*bits = strm->state->bi_valid;

return Z_OK;

}

/* ========================================================================= */

int ZEXPORT deflatePrime(z_streamp strm, int bits, int value) {

deflate_state *s;

int put;

if (deflateStateCheck(strm)) return Z_STREAM_ERROR;

s = strm->state;

#ifdef LIT_MEM

if (bits < 0 || bits > 16 ||

(uchf *)s->d_buf < s->pending_out + ((Buf_size + 7) >> 3))

return Z_BUF_ERROR;

#else

if (bits < 0 || bits > 16 ||

s->sym_buf < s->pending_out + ((Buf_size + 7) >> 3))

return Z_BUF_ERROR;

#endif

do {

put = Buf_size - s->bi_valid;

if (put > bits)

put = bits;

#if defined(DEFLATE_CHUNK_WRITE_64LE)

s->bi_buf |= (uint64_t)((value & ((1ULL << put) - 1)) << s->bi_valid);

#else

s->bi_buf |= (ush)((value & ((1 << put) - 1)) << s->bi_valid);

#endif /* DEFLATE_CHUNK_WRITE_64LE */

s->bi_valid += put;

_tr_flush_bits(s);

value >>= put;

bits -= put;

} while (bits);

return Z_OK;

}

/* ========================================================================= */

int ZEXPORT deflateParams(z_streamp strm, int level, int strategy) {

deflate_state *s;

compress_func func;

if (deflateStateCheck(strm)) return Z_STREAM_ERROR;

s = strm->state;

#ifdef FASTEST

if (level != 0) level = 1;

#else

if (level == Z_DEFAULT_COMPRESSION) level = 6;

#endif

if (level < 0 || level > 9 || strategy < 0 || strategy > Z_FIXED) {

return Z_STREAM_ERROR;

}

func = configuration_table[s->level].func;

if ((strategy != s->strategy || func != configuration_table[level].func) &&

s->last_flush != -2) {

/* Flush the last buffer: */

int err = deflate(strm, Z_BLOCK);

if (err == Z_STREAM_ERROR)

return err;

if (strm->avail_in || (s->strstart - s->block_start) + s->lookahead)

return Z_BUF_ERROR;

}

if (s->level != level) {

if (s->level == 0 && s->matches != 0) {

if (s->matches == 1)

slide_hash(s);

else

CLEAR_HASH(s);

s->matches = 0;

}

s->level = level;

s->max_lazy_match = configuration_table[level].max_lazy;

s->good_match = configuration_table[level].good_length;

s->nice_match = configuration_table[level].nice_length;

s->max_chain_length = configuration_table[level].max_chain;

}

s->strategy = strategy;

return Z_OK;

}

/* ========================================================================= */

int ZEXPORT deflateTune(z_streamp strm, int good_length, int max_lazy,

int nice_length, int max_chain) {

deflate_state *s;

if (deflateStateCheck(strm)) return Z_STREAM_ERROR;

s = strm->state;

s->good_match = (uInt)good_length;

s->max_lazy_match = (uInt)max_lazy;

s->nice_match = nice_length;

s->max_chain_length = (uInt)max_chain;

return Z_OK;

}

/* =========================================================================

* For the default windowBits of 15 and memLevel of 8, this function returns a

* close to exact, as well as small, upper bound on the compressed size. This

* is an expansion of ~0.03%, plus a small constant.

*

* For any setting other than those defaults for windowBits and memLevel, one

* of two worst case bounds is returned. This is at most an expansion of ~4% or

* ~13%, plus a small constant.

*

* Both the 0.03% and 4% derive from the overhead of stored blocks. The first

* one is for stored blocks of 16383 bytes (memLevel == 8), whereas the second

* is for stored blocks of 127 bytes (the worst case memLevel == 1). The

* expansion results from five bytes of header for each stored block.

*

* The larger expansion of 13% results from a window size less than or equal to

* the symbols buffer size (windowBits <= memLevel + 7). In that case some of

* the data being compressed may have slid out of the sliding window, impeding

* a stored block from being emitted. Then the only choice is a fixed or

* dynamic block, where a fixed block limits the maximum expansion to 9 bits

* per 8-bit byte, plus 10 bits for every block. The smallest block size for

* which this can occur is 255 (memLevel == 2).

*

* Shifts are used to approximate divisions, for speed.

*/

uLong ZEXPORT deflateBound(z_streamp strm, uLong sourceLen) {

deflate_state *s;

uLong fixedlen, storelen, wraplen;

/* upper bound for fixed blocks with 9-bit literals and length 255

(memLevel == 2, which is the lowest that may not use stored blocks) --

~13% overhead plus a small constant */

fixedlen = sourceLen + (sourceLen >> 3) + (sourceLen >> 8) +

(sourceLen >> 9) + 4;

/* upper bound for stored blocks with length 127 (memLevel == 1) --

~4% overhead plus a small constant */

storelen = sourceLen + (sourceLen >> 5) + (sourceLen >> 7) +

(sourceLen >> 11) + 7;

/* if can't get parameters, return larger bound plus a zlib wrapper */

if (deflateStateCheck(strm))

return (fixedlen > storelen ? fixedlen : storelen) + 6;

/* compute wrapper length */

s = strm->state;

switch (s->wrap) {

case 0: /* raw deflate */

wraplen = 0;

break;

case 1: /* zlib wrapper */

wraplen = 6 + (s->strstart ? 4 : 0);

break;

#ifdef GZIP

case 2: /* gzip wrapper */

wraplen = 18;

if (s->gzhead != Z_NULL) { /* user-supplied gzip header */

Bytef *str;

if (s->gzhead->extra != Z_NULL)

wraplen += 2 + s->gzhead->extra_len;

str = s->gzhead->name;

if (str != Z_NULL)

do {

wraplen++;

} while (*str++);

str = s->gzhead->comment;

if (str != Z_NULL)

do {

wraplen++;

} while (*str++);

if (s->gzhead->hcrc)

wraplen += 2;

}

break;

#endif

default: /* for compiler happiness */

wraplen = 6;

}

/* With Chromium's hashing, s->hash_bits may not correspond to the

memLevel, making the computations below incorrect. Return the

conservative bound. */

if (s->chromium_zlib_hash)

return (fixedlen > storelen ? fixedlen : storelen) + wraplen;

/* if not default parameters, return one of the conservative bounds */

if (s->w_bits != 15 || s->hash_bits != 8 + 7)

return (s->w_bits <= s->hash_bits && s->level ? fixedlen : storelen) +

wraplen;

/* default settings: return tight bound for that case -- ~0.03% overhead

plus a small constant */

return sourceLen + (sourceLen >> 12) + (sourceLen >> 14) +

(sourceLen >> 25) + 13 - 6 + wraplen;

}

/* =========================================================================

* Put a short in the pending buffer. The 16-bit value is put in MSB order.

* IN assertion: the stream state is correct and there is enough room in

* pending_buf.

*/

local void putShortMSB(deflate_state *s, uInt b) {

put_byte(s, (Byte)(b >> 8));

put_byte(s, (Byte)(b & 0xff));

}

/* =========================================================================

* Flush as much pending output as possible. All deflate() output, except for

* some deflate_stored() output, goes through this function so some

* applications may wish to modify it to avoid allocating a large

* strm->next_out buffer and copying into it. (See also read_buf()).

*/

local void flush_pending(z_streamp strm) {

unsigned len;

deflate_state *s = strm->state;

#if defined(QAT_COMPRESSION_ENABLED)

if (s->qat_s) {

qat_flush_pending(s);

}

#endif

_tr_flush_bits(s);

len = s->pending;

if (len > strm->avail_out) len = strm->avail_out;

if (len == 0) return;

zmemcpy(strm->next_out, s->pending_out, len);

strm->next_out += len;

s->pending_out += len;

strm->total_out += len;

strm->avail_out -= len;

s->pending -= len;

if (s->pending == 0) {

s->pending_out = s->pending_buf;

}

}