deflate_state Struct Reference

Deflate internal state. More...

#include <deflate.h>

Data Fields
z_streamp	strm
	pointer back to this zlib stream
int	status
	as the name implies
Bytef *	pending_buf
	output still pending
ulg	pending_buf_size
	size of pending_buf
Bytef *	pending_out
	next pending byte to output to the stream
ulg	pending
	nb of bytes in the pending buffer
int	wrap
	bit 0 true for zlib, bit 1 true for gzip
gz_headerp	gzhead
	gzip header information to write
ulg	gzindex
	where in extra, name, or comment
Byte	method
	can only be DEFLATED
int	last_flush
	value of flush param for previous deflate call
used by deflate.c:
uInt	w_size
	LZ77 window size (32K by default)
uInt	w_bits
	log2(w_size) (8..16)
uInt	w_mask
	w_size - 1
Bytef *	window
	Sliding window.
ulg	window_size
	Actual size of window: 2*wSize, except when the user input buffer is directly used as sliding window.
Posf *	prev
	Link to older string with same hash index.
Posf *	head
	Heads of the hash chains or NIL.
uInt	ins_h
	hash index of string to be inserted
uInt	hash_size
	number of elements in hash table
uInt	hash_bits
	log2(hash_size)
uInt	hash_mask
	hash_size-1
uInt	hash_shift
	Number of bits by which ins_h must be shifted at each input step.
long	block_start
	Window position at the beginning of the current output block.
uInt	match_length
	length of best match
IPos	prev_match
	previous match
int	match_available
	set if previous match exists
uInt	strstart
	start of string to insert
uInt	match_start
	start of matching string
uInt	lookahead
	number of valid bytes ahead in window
uInt	prev_length
	Length of the best match at previous step.
uInt	max_chain_length
	To speed up deflation, hash chains are never searched beyond this length.
uInt	max_lazy_match
	Attempt to find a better match only when the current match is strictly smaller than this value.
int	level
	compression level (1..9)
int	strategy
	favor or force Huffman coding
uInt	good_match
	Use a faster search when the previous match is longer than this.
int	nice_match
	Stop searching when current match exceeds this.
used by trees.c:
struct ct_data_s	dyn_ltree [HEAP_SIZE]
	literal and length tree
struct ct_data_s	dyn_dtree [2 *D_CODES+1]
	distance tree
struct ct_data_s	bl_tree [2 *BL_CODES+1]
	Huffman tree for bit lengths.
struct tree_desc_s	l_desc
	desc.
struct tree_desc_s	d_desc
	desc.
struct tree_desc_s	bl_desc
	desc.
ush	bl_count [MAX_BITS+1]
	number of codes at each bit length for an optimal tree
int	heap [2 *L_CODES+1]
	heap used to build the Huffman trees
int	heap_len
	number of elements in the heap
int	heap_max
	element of largest frequency
uch	depth [2 *L_CODES+1]
	Depth of each subtree used as tie breaker for trees of equal frequency.
uchf *	sym_buf
	buffer for distances and literals/lengths
uInt	lit_bufsize
	Size of match buffer for literals/lengths.
uInt	sym_next
	running index in symbol buffer
uInt	sym_end
	symbol table full when sym_next reaches this
ulg	opt_len
	bit length of current block with optimal trees
ulg	static_len
	bit length of current block with static trees
uInt	matches
	number of string matches in current block
uInt	insert
	bytes at end of window left to insert
ush	bi_buf
	Output buffer.
int	bi_valid
	Number of valid bits in bi_buf.
ulg	high_water
	High water mark offset in window for initialized bytes – bytes above this are set to zero in order to avoid memory check warnings when longest match routines access bytes past the input.

Detailed Description

Deflate internal state.

Field Documentation

bi_buf

ush deflate_state::bi_buf

Output buffer.

bits are inserted starting at the bottom (least significant bits).

bi_valid

int deflate_state::bi_valid

Number of valid bits in bi_buf.

All bits above the last valid bit are always zero.

bl_desc

struct tree_desc_s deflate_state::bl_desc

desc.

for bit length tree

block_start

long deflate_state::block_start

Window position at the beginning of the current output block.

Gets negative when the window is moved backwards.

d_desc

struct tree_desc_s deflate_state::d_desc

desc.

for distance tree

hash_shift

uInt deflate_state::hash_shift

Number of bits by which ins_h must be shifted at each input step.

It must be such that after MIN_MATCH steps, the oldest byte no longer takes part in the hash key, that is: hash_shift * MIN_MATCH >= hash_bits

high_water

ulg deflate_state::high_water

High water mark offset in window for initialized bytes – bytes above this are set to zero in order to avoid memory check warnings when longest match routines access bytes past the input.

This is then updated to the new high water mark.

l_desc

struct tree_desc_s deflate_state::l_desc

desc.

for literal tree

lit_bufsize

uInt deflate_state::lit_bufsize

Size of match buffer for literals/lengths.

There are 4 reasons for limiting lit_bufsize to 64K:

• frequencies can be kept in 16 bit counters
• if compression is not successful for the first block, all input data is still in the window so we can still emit a stored block even when input comes from standard input. (This can also be done for all blocks if lit_bufsize is not greater than 32K.)
• if compression is not successful for a file smaller than 64K, we can even emit a stored file instead of a stored block (saving 5 bytes). This is applicable only for zip (not gzip or zlib).
• creating new Huffman trees less frequently may not provide fast adaptation to changes in the input data statistics. (Take for example a binary file with poorly compressible code followed by a highly compressible string table.) Smaller buffer sizes give fast adaptation but have of course the overhead of transmitting trees more frequently.
• I can't count above 4

max_chain_length

uInt deflate_state::max_chain_length

To speed up deflation, hash chains are never searched beyond this length.

A higher limit improves compression ratio but degrades the speed.

max_lazy_match

uInt deflate_state::max_lazy_match

Attempt to find a better match only when the current match is strictly smaller than this value.

This mechanism is used only for compression levels >= 4.

prev

Posf* deflate_state::prev

Link to older string with same hash index.

To limit the size of this array to 64K, this link is maintained only for the last 32K strings. An index in this array is thus a window index modulo 32K.

prev_length

uInt deflate_state::prev_length

Length of the best match at previous step.

Matches not greater than this are discarded. This is used in the lazy match evaluation.

window

Bytef* deflate_state::window

Sliding window.

Input bytes are read into the second half of the window, and move to the first half later to keep a dictionary of at least wSize bytes.

With this organization, matches are limited to a distance of wSize-MAX_MATCH bytes, but this ensures that IO is always performed with a length multiple of the block size. Also, it limits the window size to 64K, which is quite useful on MSDOS.

Todo:

use the user input buffer as sliding window.

---

The documentation for this struct was generated from the following file:

• include/deflate.h