Compress data using the deflation algorithm. More...

#include "deflate.h"

Data Structures
struct	config
	Values for max_lazy_match, good_match and max_chain_length, depending on the desired pack level (0..9). More...

Macros
#define	NIL 0

#define	TOO_FAR 4096

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

#define	UPDATE_HASH(s, h, c) (h = (((h) << s->hash_shift) ^ (c)) & s->hash_mask)

#define	INSERT_STRING(s, str, match_head)

#define	CLEAR_HASH(s)

#define	HCRC_UPDATE(beg)

#define	check_match(s, start, match, length)

#define	FLUSH_BLOCK_ONLY(s, last)

#define	FLUSH_BLOCK(s, last)

#define	MAX_STORED 65535

#define	MIN(a, b) ((a) > (b) ? (b) : (a))

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

Enumerations
enum	block_state { need_more , block_done , finish_started , finish_done }

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

local block_state	deflate_fast (deflate_state *s, int flush)

local block_state	deflate_slow (deflate_state *s, int flush)

local block_state	deflate_rle (deflate_state *s, int flush)

local block_state	deflate_huff (deflate_state *s, int flush)

local void	slide_hash (deflate_state *s)

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

local void	fill_window (deflate_state *s)

int ZEXPORT	deflateInit_ (z_streamp strm, int level, const char *version, int stream_size)
	Initializes the internal stream state for compression.

int ZEXPORT	deflateInit2_ (z_streamp strm, int level, int method, int windowBits, int memLevel, int strategy, const char *version, int stream_size)
	Another version of deflateInit() with more compression options.

local int	deflateStateCheck (z_streamp strm)

int ZEXPORT	deflateSetDictionary (z_streamp strm, const Bytef *dictionary, uInt dictLength)
	Initializes the compression dictionary from the given byte sequence without producing any compressed output.

int ZEXPORT	deflateGetDictionary (z_streamp strm, Bytef dictionary, uInt dictLength)
	Returns the sliding dictionary being maintained by deflate.

int ZEXPORT	deflateResetKeep (z_streamp strm)

local void	lm_init (deflate_state *s)

int ZEXPORT	deflateReset (z_streamp strm)
	This function is equivalent to deflateEnd followed by deflateInit, but does not free and reallocate the internal compression state.

int ZEXPORT	deflateSetHeader (z_streamp strm, gz_headerp head)
	Provides gzip header information for when a gzip stream is requested by deflateInit2().

int ZEXPORT	deflatePending (z_streamp strm, unsigned pending, int bits)
	Returns the number of bytes and bits of output that have been generated, but not yet provided in the available output.

int ZEXPORT	deflatePrime (z_streamp strm, int bits, int value)
	Inserts bits in the deflate output stream.

int ZEXPORT	deflateParams (z_streamp strm, int level, int strategy)
	Dynamically update the compression level and compression strategy.

int ZEXPORT	deflateTune (z_streamp strm, int good_length, int max_lazy, int nice_length, int max_chain)
	Fine tune deflate's internal compression parameters.

uLong ZEXPORT	deflateBound (z_streamp strm, uLong sourceLen)
	Returns an upper bound on the compressed size after deflation of sourceLen bytes.

local void	putShortMSB (deflate_state *s, uInt b)

local void	flush_pending (z_streamp strm)

int ZEXPORT	deflate (z_streamp strm, int flush)
	Compresses as much data as possible, and stops when the input buffer becomes empty or the output buffer becomes full.

int ZEXPORT	deflateEnd (z_streamp strm)
	All dynamically allocated data structures for this stream are freed.

int ZEXPORT	deflateCopy (z_streamp dest, z_streamp source)
	Sets the destination stream as a complete copy of the source stream.

local uInt	longest_match (deflate_state *s, IPos cur_match)

Variables
const char	deflate_copyright []
	If you use the zlib library in a product, an acknowledgment is welcome in the documentation of your product.

local const config	configuration_table [10]

Detailed Description

Compress data using the deflation algorithm.

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

Macro Definition Documentation

◆ CLEAR_HASH

#define CLEAR_HASH ( s )

Value:

    do { \
        s->head[s->hash_size - 1] = NIL; \
        zmemzero((Bytef *)s->head, \
                 (unsigned)(s->hash_size - 1)*sizeof(*s->head)); \
    } while (0)

◆ FLUSH_BLOCK

#define FLUSH_BLOCK	(	s,
		last
	)

Value:

   { \
   FLUSH_BLOCK_ONLY(s, last); \
   if (s->strm->avail_out == 0) return (last) ? finish_started : need_more; \
}

◆ FLUSH_BLOCK_ONLY

#define FLUSH_BLOCK_ONLY	(	s,
		last
	)

Value:

   { \
   _tr_flush_block(s, (s->block_start >= 0L ? \
                   (charf *)&s->window[(unsigned)s->block_start] : \
                   (charf *)Z_NULL), \
                (ulg)((long)s->strstart - s->block_start), \
                (last)); \
   s->block_start = s->strstart; \
   flush_pending(s->strm); \
   Tracev((stderr,"[FLUSH]")); \
}

◆ HCRC_UPDATE

#define HCRC_UPDATE ( beg )

Value:

    do { \
        if (s->gzhead->hcrc && s->pending > (beg)) \
            strm->adler = crc32(strm->adler, s->pending_buf + (beg), \
                                s->pending - (beg)); \
    } while (0)

◆ INSERT_STRING

#define INSERT_STRING	(	s,
		str,
		match_head
	)

Value:

   (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
    match_head = s->prev[(str) & s->w_mask] = s->head[s->ins_h], \
    s->head[s->ins_h] = (Pos)(str))

Function Documentation

◆ deflateInit_()

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

Initializes the internal stream state for compression.

Parameters

strm	pointrer to compressed stream state information The fields z_stream::zalloc, z_stream::zfree and z_stream::opaque must be initialized before by the caller.
level	compression level.

If zalloc and zfree are set to Z_NULL, deflateInit updates them to use default allocation functions. total_in, total_out, adler, and msg are initialized.

The compression level must be Z_DEFAULT_COMPRESSION, or between 0 and 9: 1 gives best speed, 9 gives best compression, 0 gives no compression at all (the input data is simply copied a block at a time). Z_DEFAULT_COMPRESSION requests a default compromise between speed and compression (currently equivalent to level 6).

deflateInit returns Z_OK if success, Z_MEM_ERROR if there was not enough memory, Z_STREAM_ERROR if level is not a valid compression level, or Z_VERSION_ERROR if the zlib library version (zlib_version) is incompatible with the version assumed by the caller (ZLIB_VERSION).

Note: msg is set to null if there is no error message. deflateInit() does not perform any compression; this will be done by deflate().

Variable Documentation

◆ configuration_table

local const config configuration_table[10]

Initial value:

= {
 
 {0,    0,  0,    0, deflate_stored},  
 {4,    4,  8,    4, deflate_fast}, 
 {4,    5, 16,    8, deflate_fast},
 {4,    6, 32,   32, deflate_fast},
 
 {4,    4, 16,   16, deflate_slow},  
 {8,   16, 32,   32, deflate_slow},
 {8,   16, 128, 128, deflate_slow},
 {8,   32, 128, 256, deflate_slow},
 {32, 128, 258, 1024, deflate_slow},
 {32, 258, 258, 4096, deflate_slow}}

◆ deflate_copyright

const char deflate_copyright[]

Initial value:

=

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.

Data Structures

Macros

Typedefs

Enumerations

Functions

Variables

Detailed Description

ALGORITHM

ACKNOWLEDGEMENTS

REFERENCES

Macro Definition Documentation

◆ CLEAR_HASH

◆ FLUSH_BLOCK

◆ FLUSH_BLOCK_ONLY

◆ HCRC_UPDATE

◆ INSERT_STRING

Function Documentation

◆ deflateInit_()

Variable Documentation

◆ configuration_table

◆ deflate_copyright