Burger::CompressDeflate Class Reference

Compress data using Deflate Encoding. More...

Inheritance diagram for Burger::CompressDeflate:

Collaboration diagram for Burger::CompressDeflate:

Classes
struct	CodeData_t
	Structure for each huffman tree entry. More...
struct	StaticTreeDesc_t
	Structure for each static huffman tree entry. More...
struct	TreeDesc_t

Public Member Functions
const Burger::StaticRTTI *	get_StaticRTTI (void) const noexcept override
	Get the description to the class.
	CompressDeflate (void)
	Default constructor.
eError	Init (void) override
	Reset the RLE compressor.
eError	Process (const void *pInput, uintptr_t uInputLength) override
	Compress the input data using RLE.
eError	Finalize (void) override
	Finalize RLE compression.
Public Member Functions inherited from Burger::Compress
	Compress (void)
	Default constructor.
virtual	~Compress ()
	Default destructor.
OutputMemoryStream *	GetOutput (void) noexcept
	Get the output data.
uintptr_t	GetOutputSize (void) const noexcept
	Get the output data size in bytes.
uint32_t	GetSignature (void) const noexcept
	Return the signature for this compressor.
Public Member Functions inherited from Burger::Base
const char *	get_class_name (void) const noexcept
	Get the name of the class.
virtual	~Base () noexcept=default
	Destructor.

Static Public Attributes
static const Burger::StaticRTTI	g_StaticRTTI
	The global description of the class.
static const uint32_t	Signature = 0x5A4C4942
	'ZLIB'
Static Public Attributes inherited from Burger::Compress
static const Burger::StaticRTTI	g_StaticRTTI
	The global description of the class.
Static Public Attributes inherited from Burger::Base
static const Burger::StaticRTTI	g_StaticRTTI
	The global description of the class.

Protected Types
enum	eState { DEFAULT_STATE =0 , INIT_STATE =42 , BUSY_STATE =113 , FINISH_STATE =666 }
enum	eBlockState { STATE_NEEDMORE , STATE_BLOCKDONE , STATE_FINISHSTARTED , STATE_FINISHDONE }
enum	eDataType { Z_BINARY =0 , Z_ASCII =1 , Z_UNKNOWN =2 }
enum	eStreamTreeType { STORED_BLOCK =0 , STATIC_TREES =1 , DYN_TREES =2 }
enum	{   MAX_WBITS =15 , MAX_MEM_LEVEL =9 , Z_BEST_COMPRESSION =9 , Z_DEFLATED =8 ,   SMALLEST =1 , MIN_MATCH =3 , MAX_MATCH =258 , DIST_CODE_LEN =512 ,   TOO_FAR =4096 , MIN_LOOKAHEAD =(MAX_MATCH+MIN_MATCH+1) , PRESET_DICT =0x20 , LENGTH_CODES =29 ,   LITERALS =256 , L_CODES =(LITERALS+1+LENGTH_CODES) , D_CODES =30 , BL_CODES =19 ,   HEAP_SIZE =(2*L_CODES+1) , MAX_BITS =15 , MAX_BL_BITS =7 , END_BLOCK =256 ,   REP_3_6 =16 , REPZ_3_10 =17 , REPZ_11_138 =18 }

Protected Member Functions
uint_t	TallyLiteral (uint_t uInput)
uint_t	TallyDistance (uint_t uDistance, uint_t uLength)
void	SendBits (uint_t uInput, uint_t uLength)
void	send_code (uint_t uCode, const CodeData_t *pTree)
void	ClearHash (void)
uint_t	InsertString (uint_t uStringIndex)
void	FlushBlock (uint_t bEOF)
void	OutputBigEndian16 (uint_t b)
	Insert a 16 bit value in the output stream in Big Endian order.
void	BitIndexFlush (void)
	Flush the bit buffer, keeping at most 7 bits in it.
void	BitIndexFlushToByte (void)
	Flush the bit buffer and align the output on a byte boundary.
void	CopyBlock (const uint8_t *pInput, uintptr_t uInputLength)
	Copy a stored block, storing first the length and its one's complement.
void	SetDataType (void)
	Determine if the data to compress is ASCII or BINARY.
void	InitBlock (void)
	Init a new deflate block.
void	StaticTreeInit (void)
	Initialize the tree data structures for a new zlib stream.
void	PQDownHeap (const CodeData_t *pTree, int k)
	Restore the heap.
void	CompressBlock (const CodeData_t *pLengthTree, const CodeData_t *pDistanceTree)
	Send the block data compressed using the given Huffman trees.
uintptr_t	ReadBuffer (uint8_t *pOutput, uintptr_t uOutputSize)
	Read a new buffer from the current input stream.
void	FillWindow (void)
	Fill the window when the lookahead becomes insufficient.
void	GenerateBitLengths (const TreeDesc_t *pTreeDescription)
	Compute the optimal bit lengths for a tree and update the total bit length for the current block.
void	GenerateCodes (CodeData_t *tree, int max_code, uint16_t *bl_count)
void	BuildTree (TreeDesc_t *desc)
void	ScanTree (CodeData_t *tree, int max_code)
int	BuildBitLengthTree (void)
void	StoredBlock (const uint8_t *buf, uint32_t stored_len, int eof)
void	SendTree (CodeData_t *tree, int max_code)
void	SendAllTrees (int lcodes, int dcodes, int blcodes)
void	FlushBlock (const uint8_t *buf, uint32_t stored_len, uint_t bEOF)
void	FlushPending (void)
uint_t	LongestMatch (uint_t cur_match)
eBlockState	DeflateSlow (int flush)
void	Align (void)
int	DeflateEnd (void)
void	LongestMatchInit (void)
int	DeflateReset (void)
int	DeflateInit (void)
int	PerformDeflate (int flush)

Static Protected Member Functions
static uint_t	UpdateHash (uint_t uHash, uint8_t uInput)

Protected Attributes
const uint8_t *	m_pInput
	Next input byte.
uint8_t *	m_pPendingOutput
	Next pending byte to output to the stream.
uintptr_t	m_uInputLength
	Number of bytes available at next_in.
intptr_t	m_iBlockStart
	Window position at the beginning of the current output block. Gets negative when the window is moved backwards.
uint32_t	m_uAdler
	Adler32 value of the uncompressed data.
uint32_t	m_uOptimalLength
	bit length of current block with optimal trees
uint32_t	m_uStaticLength
	bit length of current block with static trees
uint_t	m_uInsertHash
	hash index of string to be inserted
uint_t	m_uMatchLength
	Length of best match.
uint_t	m_uPreviousMatch
	previous match
uint_t	m_bMatchAvailable
	set if previous match exists
uint_t	m_uStringStart
	start of string to insert
uint_t	m_uMatchStart
	start of matching string
uint_t	m_uLookAhead
	number of valid bytes ahead in window
uint_t	m_uPreviousLength
	Length of the best match at previous step. Matches not greater than this are discarded. This is used in the lazy match evaluation.
uint_t	m_uLastLiteral
	running index in l_buf
uint_t	m_uMatches
	number of string matches in current block
uint_t	m_uBitIndexBuffer
	Number of valid bits in bi_buf. All bits above the last valid bit are always zero.
uint_t	m_uBitIndexValid
	Number of bits in the output buffer.
uint_t	m_bInitialized
	TRUE if initialized
uint_t	m_uLastEOBLength
	bit length of EOB code for last block
int	m_iPending
	Number of bytes in the pending buffer.
int	m_bNoHeader
	Suppress zlib header and adler32.
int	m_iLastFlush
	Value of flush param for previous deflate call.
int	m_iHeapLength
	number of elements in the heap
int	m_iHeapMaximum
	element of largest frequency
eState	m_eState
	As the name implies.
eDataType	m_eDataType
	UNKNOWN, BINARY or ASCII.
uint8_t	m_bMethod
	STORED (for zip only) or DEFLATED.
CodeData_t	m_DynamicLengthTrees [HEAP_SIZE]
	literal and length tree
CodeData_t	m_DynamicDistanceTrees [2 *D_CODES+1]
	distance tree
CodeData_t	m_BitLengthTrees [2 *BL_CODES+1]
	Huffman tree for bit lengths.
TreeDesc_t	m_LiteralDescription
	desc. for literal tree
TreeDesc_t	m_DistanceDescription
	desc. for distance tree
TreeDesc_t	m_BitLengthDescription
	desc. for bit length tree
int	m_Heap [2 *L_CODES+1]
	heap used to build the Huffman trees
uint16_t	m_Head [c_uHashSize]
	Heads of the hash chains or 0.
uint16_t	m_Previous [c_uWSize]
	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.
uint16_t	m_BitLengthCount [MAX_BITS+1]
	MAX_BITS = 15, so this is long aligned.
uint16_t	m_DataBuffer [c_uLiteralBufferSize]
	Buffer for distances. To simplify the code, d_buf and l_buf have the same number of elements. To use different lengths, an extra flag array would be necessary.
uint8_t	m_LiteralBuffer [c_uLiteralBufferSize]
	buffer for literals or lengths
uint8_t	m_PendingBuffer [c_uLiteralBufferSize]
	Output still pending.
uint8_t	m_Depth [2 *L_CODES+1]
	Depth of each subtree used as tie breaker for trees of equal frequency.
uint8_t	m_Window [c_uWSize *2]
	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.
Protected Attributes inherited from Burger::Compress
OutputMemoryStream	m_Output
	Main output buffer for compressed data.
uint32_t	m_uSignature
	4 character code to identify this compressor

Static Protected Attributes
static const uint_t	c_uBufSize = static_cast<uint_t>(8 * 2*sizeof(uint8_t))
	Number of bits used within bi_buf. (bi_buf might be implemented on more than 16 bits on some systems.)
static const uint_t	c_uWBits = MAX_WBITS
	log2(c_uWSize) (8..16)
static const uint_t	c_uWSize = 1 << c_uWBits
	LZ77 window size (32K by default)
static const uint_t	c_uWMask = c_uWSize - 1
	c_uWSize - 1 Use a faster search when the previous match is longer than this
static const uint_t	c_uHashBits = MAX_MEM_LEVEL + 7
	log2(hash_size)
static const uint_t	c_uHashSize = 1 << c_uHashBits
	number of elements in hash table
static const uint_t	c_uHashMask = c_uHashSize - 1
	hash_size-1
static const uint_t	c_uHashShift = ((c_uHashBits+MIN_MATCH-1)/MIN_MATCH)
	Number of bits by which m_uInsertHash 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.
static const uint_t	c_uLiteralBufferSize = 1 << (MAX_MEM_LEVEL + 6)
	16K elements by default
static const uint_t	c_uWindowSize = 2*c_uWSize
	Actual size of window: 2*wSize, except when the user input buffer is directly used as sliding window.
static const uint_t	c_uMaxLazyMatch = 258
	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.
static const uint_t	c_uGoodMatch = 32
static const int	c_iNiceMatch = 258
	Stop searching when current match exceeds this.
static const uint_t	c_uMaxChainLength = 4096
	To speed up deflation, hash chains are never searched beyond this length. A higher limit improves compression ratio but degrades the speed.
static const int	g_ExtraLengthBits [LENGTH_CODES]
static const int	g_ExtraDistanceBits [D_CODES]
static const int	g_ExtraBitLengthBits [BL_CODES]
static const uint8_t	g_BitLengthOrder [BL_CODES]
static const CodeData_t	g_StaticLengthTrees [L_CODES+2]
static const CodeData_t	g_StaticDistanceTrees [D_CODES]
static const int	g_BaseLengths [LENGTH_CODES]
static const int	g_BaseDistances [D_CODES]
static const StaticTreeDesc_t	g_StaticLengthDescription
static const StaticTreeDesc_t	g_StaticDistanceDescription
static const StaticTreeDesc_t	g_StaticBitLengthDescription
static const uint8_t	g_DistanceCodes [DIST_CODE_LEN]
static const uint8_t	g_LengthCodes [MAX_MATCH-MIN_MATCH+1]

Detailed Description

Compress data using Deflate Encoding.

---

This format is the one used by ZLIB.

Deutsch, L.P.,"DEFLATE Compressed Data Format Specification". Available in http://www.ietf.org/rfc/rfc1951.txt

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

See also

Burger::DecompressDeflate

Member Enumeration Documentation

anonymous enum

anonymous enum

protected

Enumerator
MAX_WBITS	Number of bits deep a huffman entry can be.
MAX_MEM_LEVEL	Memory level.
Z_BEST_COMPRESSION	Compression level.
Z_DEFLATED	ZLIB token for Deflate.
SMALLEST	Index within the heap array of least frequent node in the Huffman tree.
MIN_MATCH	Minimum number of bytes of data to compress in a packet.
MAX_MATCH	Maximum number of bytes of data to compress in a packet.
DIST_CODE_LEN	Length of a distance code.
TOO_FAR	Matches of length 3 are discarded if their distance exceeds TOO_FAR.
MIN_LOOKAHEAD	Minimum amount of lookahead, except at the end of the input file.
PRESET_DICT	Preset dictionary flag in zlib header.
LENGTH_CODES	Number of length codes, not counting the special END_BLOCK code.
LITERALS	Number of literal bytes 0..255.
L_CODES	Number of Literal or Length codes, including the END_BLOCK code.
D_CODES	Number of distance codes.
BL_CODES	Number of codes used to transfer the bit lengths.
HEAP_SIZE	Maximum heap size.
MAX_BITS	All codes must not exceed MAX_BITS bits.
MAX_BL_BITS	Bit length codes must not exceed MAX_BL_BITS bits.
END_BLOCK	End of block literal code.
REP_3_6	Repeat previous bit length 3-6 times (2 bits of repeat count)
REPZ_3_10	Repeat a zero length 3-10 times (3 bits of repeat count)
REPZ_11_138	Repeat a zero length 11-138 times (7 bits of repeat count)

eBlockState

enum Burger::CompressDeflate::eBlockState

protected

Enumerator
STATE_NEEDMORE	Block not completed, need more input or more output.
STATE_BLOCKDONE	Block flush performed.
STATE_FINISHSTARTED	Finish started, need only more output at next deflate.
STATE_FINISHDONE	Finish done, accept no more input or output.

eDataType

enum Burger::CompressDeflate::eDataType

protected

Enumerator
Z_BINARY	Compress as binary data.
Z_ASCII	Compress as ASCII text (Focus on 32-127)
Z_UNKNOWN	Unknown data.

eState

enum Burger::CompressDeflate::eState

protected

Enumerator
DEFAULT_STATE	Dormant state.
INIT_STATE	Initialization state.
BUSY_STATE	Busy state.
FINISH_STATE	Finish state.

eStreamTreeType

enum Burger::CompressDeflate::eStreamTreeType

protected

Enumerator
STORED_BLOCK	Uncompressed data.
STATIC_TREES	Compressed with the static tree.
DYN_TREES	Compressed with a dynamic tree.

Constructor & Destructor Documentation

CompressDeflate()

Burger::CompressDeflate::CompressDeflate

(

void

)

Default constructor.

---

Initializes the cache buffer.

Member Function Documentation

Align()

void Burger::CompressDeflate::Align ( void )

protected

BitIndexFlush()

void Burger::CompressDeflate::BitIndexFlush ( void )

protected

Flush the bit buffer, keeping at most 7 bits in it.

---

Check the output bit bucket and flush up to 16 bits into the byte stream

BitIndexFlushToByte()

void Burger::CompressDeflate::BitIndexFlushToByte ( void )

protected

Flush the bit buffer and align the output on a byte boundary.

---

BuildBitLengthTree()

int Burger::CompressDeflate::BuildBitLengthTree ( void )

protected

BuildTree()

void Burger::CompressDeflate::BuildTree ( TreeDesc_t * desc )

protected

ClearHash()

void Burger::CompressDeflate::ClearHash ( void )

inlineprotected

CompressBlock()

void Burger::CompressDeflate::CompressBlock ( const CodeData_t * pLengthTree, const CodeData_t * pDistanceTree )

protected

Send the block data compressed using the given Huffman trees.

---

CopyBlock()

void Burger::CompressDeflate::CopyBlock ( const uint8_t * pInput, uintptr_t uInputLength )

protected

Copy a stored block, storing first the length and its one's complement.

---

Parameters

pInput	Pointer to the data block
uInputLength	Length of the data block

DeflateEnd()

int Burger::CompressDeflate::DeflateEnd ( void )

protected

DeflateInit()

int Burger::CompressDeflate::DeflateInit ( void )

protected

DeflateReset()

int Burger::CompressDeflate::DeflateReset ( void )

protected

DeflateSlow()

Burger::CompressDeflate::eBlockState Burger::CompressDeflate::DeflateSlow ( int flush )

protected

FillWindow()

void Burger::CompressDeflate::FillWindow ( void )

protected

Fill the window when the lookahead becomes insufficient.

---

Updates m_uStringStart and m_uLookAhead.

IN assertion: lookahead < MIN_LOOKAHEAD OUT assertions: m_uStringStart <= 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).

Finalize()

Burger::eError Burger::CompressDeflate::Finalize ( void )

overridevirtual

Finalize RLE compression.

---

If any data has been cached from the compression stream, flush it into the output

Returns

Zero if no error, non-zero on error

Implements Burger::Compress.

FlushBlock() [1/2]

void Burger::CompressDeflate::FlushBlock ( const uint8_t * buf, uint32_t stored_len, uint_t bEOF )

protected

FlushBlock() [2/2]

void Burger::CompressDeflate::FlushBlock ( uint_t bEOF )

inlineprotected

FlushPending()

void Burger::CompressDeflate::FlushPending ( void )

protected

GenerateBitLengths()

void Burger::CompressDeflate::GenerateBitLengths ( const TreeDesc_t * pTreeDescription )

protected

Compute the optimal bit lengths for a tree and update the total bit length for the current block.

---

IN assertion: the fields freq and dad are set, heap[heap_max] and above are the tree nodes sorted by increasing frequency. OUT assertions: the field len is set to the optimal bit length, the array bl_count contains the frequencies for each bit length. The length opt_len is updated; static_len is also updated if stree is not null.

GenerateCodes()

void Burger::CompressDeflate::GenerateCodes ( CodeData_t * tree, int max_code, uint16_t * bl_count )

protected

get_StaticRTTI()

const Burger::StaticRTTI * Burger::CompressDeflate::get_StaticRTTI ( void ) const

overridevirtualnoexcept

Get the description to the class.

---

This virtual function will pull the pointer to the StaticRTTI instance that has the name of the class. Due to it being virtual, it will be the name of the most derived class.

Returns

Pointer to a global, read only instance of StaticRTTI for the true class

Reimplemented from Burger::Compress.

Init()

Burger::eError Burger::CompressDeflate::Init ( void )

overridevirtual

Reset the RLE compressor.

---

Resets the cache buffer.

Implements Burger::Compress.

InitBlock()

void Burger::CompressDeflate::InitBlock ( void )

protected

Init a new deflate block.

---

InsertString()

uint_t Burger::CompressDeflate::InsertString ( uint_t uStringIndex )

inlineprotected

LongestMatch()

uint_t Burger::CompressDeflate::LongestMatch ( uint_t cur_match )

protected

LongestMatchInit()

void Burger::CompressDeflate::LongestMatchInit ( void )

protected

OutputBigEndian16()

void Burger::CompressDeflate::OutputBigEndian16 ( uint_t uInput )

protected

Insert a 16 bit value in the output stream in Big Endian order.

---

Parameters

uInput

16 bit value to store in the byte stream

PerformDeflate()

int Burger::CompressDeflate::PerformDeflate ( int flush )

protected

PQDownHeap()

void Burger::CompressDeflate::PQDownHeap ( const CodeData_t * pTree, int k )

protected

Restore the heap.

---

Restore the heap property by moving down the tree starting at node k, exchanging a node with the smallest of its two sons if necessary, stopping when the heap property is re-established (each father smaller than its two sons).

Parameters

pTree	Pointer to the tree array to test
k	Heap index (Tested against m_iHeapLength)

Process()

Burger::eError Burger::CompressDeflate::Process ( const void * pInput, uintptr_t uInputLength )

overridevirtual

Compress the input data using RLE.

---

Compresses the data using RLE and stores the compressed data into an OutputMemoryStream

Implements Burger::Compress.

ReadBuffer()

uintptr_t Burger::CompressDeflate::ReadBuffer ( uint8_t * pOutput, uintptr_t uOutputSize )

protected

Read a new buffer from the current input stream.

---

Update the adler32 and total number of bytes read.

ScanTree()

void Burger::CompressDeflate::ScanTree ( CodeData_t * tree, int max_code )

protected

send_code()

void Burger::CompressDeflate::send_code ( uint_t uCode, const CodeData_t * pTree )

inlineprotected

SendAllTrees()

void Burger::CompressDeflate::SendAllTrees ( int lcodes, int dcodes, int blcodes )

protected

SendBits()

void Burger::CompressDeflate::SendBits ( uint_t uInput, uint_t uLength )

inlineprotected

SendTree()

void Burger::CompressDeflate::SendTree ( CodeData_t * tree, int max_code )

protected

SetDataType()

void Burger::CompressDeflate::SetDataType ( void )

protected

Determine if the data to compress is ASCII or BINARY.

---

Set the data type to ASCII or BINARY, using a crude approximation: binary if more than 20% of the bytes are <= 6 or >= 128, ASCII otherwise.

Sets the variable m_eDataType to Z_ASCII or Z_BINARY as output

StaticTreeInit()

void Burger::CompressDeflate::StaticTreeInit ( void )

protected

Initialize the tree data structures for a new zlib stream.

---

StoredBlock()

void Burger::CompressDeflate::StoredBlock ( const uint8_t * buf, uint32_t stored_len, int eof )

protected

TallyDistance()

uint_t Burger::CompressDeflate::TallyDistance ( uint_t uDistance, uint_t uLength )

inlineprotected

TallyLiteral()

uint_t Burger::CompressDeflate::TallyLiteral ( uint_t uInput )

inlineprotected

UpdateHash()

static uint_t Burger::CompressDeflate::UpdateHash ( uint_t uHash, uint8_t uInput )

inlinestaticprotected

Member Data Documentation

c_iNiceMatch

const int Burger::CompressDeflate::c_iNiceMatch = 258

staticprotected

Stop searching when current match exceeds this.

c_uBufSize

const uint_t Burger::CompressDeflate::c_uBufSize = static_cast<uint_t>(8 * 2*sizeof(uint8_t))

staticprotected

Number of bits used within bi_buf. (bi_buf might be implemented on more than 16 bits on some systems.)

c_uGoodMatch

const uint_t Burger::CompressDeflate::c_uGoodMatch = 32

staticprotected

c_uHashBits

const uint_t Burger::CompressDeflate::c_uHashBits = MAX_MEM_LEVEL + 7

staticprotected

log2(hash_size)

c_uHashMask

const uint_t Burger::CompressDeflate::c_uHashMask = c_uHashSize - 1

staticprotected

hash_size-1

c_uHashShift

const uint_t Burger::CompressDeflate::c_uHashShift = ((c_uHashBits+MIN_MATCH-1)/MIN_MATCH)

staticprotected

Number of bits by which m_uInsertHash 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.

c_uHashSize

const uint_t Burger::CompressDeflate::c_uHashSize = 1 << c_uHashBits

staticprotected

number of elements in hash table

c_uLiteralBufferSize

const uint_t Burger::CompressDeflate::c_uLiteralBufferSize = 1 << (MAX_MEM_LEVEL + 6)

staticprotected

16K elements by default

c_uMaxChainLength

const uint_t Burger::CompressDeflate::c_uMaxChainLength = 4096

staticprotected

To speed up deflation, hash chains are never searched beyond this length. A higher limit improves compression ratio but degrades the speed.

c_uMaxLazyMatch

const uint_t Burger::CompressDeflate::c_uMaxLazyMatch = 258

staticprotected

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.

c_uWBits

const uint_t Burger::CompressDeflate::c_uWBits = MAX_WBITS

staticprotected

log2(c_uWSize) (8..16)

c_uWindowSize

const uint_t Burger::CompressDeflate::c_uWindowSize = 2*c_uWSize

staticprotected

Actual size of window: 2*wSize, except when the user input buffer is directly used as sliding window.

c_uWMask

const uint_t Burger::CompressDeflate::c_uWMask = c_uWSize - 1

staticprotected

c_uWSize - 1 Use a faster search when the previous match is longer than this

c_uWSize

const uint_t Burger::CompressDeflate::c_uWSize = 1 << c_uWBits

staticprotected

LZ77 window size (32K by default)

g_BaseDistances

const int Burger::CompressDeflate::g_BaseDistances

staticprotected

Initial value:

= {
 0, 1, 2, 3, 4, 6, 8, 12, 16, 24,
 32, 48, 64, 96, 128, 192, 256, 384, 512, 768,
 1024, 1536, 2048, 3072, 4096, 6144, 8192, 12288, 16384, 24576
}

g_BaseLengths

const int Burger::CompressDeflate::g_BaseLengths

staticprotected

Initial value:

= {
 0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 16, 20, 24, 28, 32, 40, 48, 56,
 64, 80, 96, 112, 128, 160, 192, 224, 0
}

g_BitLengthOrder

const uint8_t Burger::CompressDeflate::g_BitLengthOrder

staticprotected

Initial value:

= {
 16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15}

g_DistanceCodes

const uint8_t Burger::CompressDeflate::g_DistanceCodes

staticprotected

Initial value:

= {
 0, 1, 2, 3, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8,
 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10,
 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13,
 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15,
 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 0, 0, 16, 17,
 18, 18, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22, 22, 22,
 23, 23, 23, 23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
 24, 24, 24, 24, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27,
 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
 28, 28, 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29
}

g_ExtraBitLengthBits

const int Burger::CompressDeflate::g_ExtraBitLengthBits

staticprotected

Initial value:

= {
 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7}

g_ExtraDistanceBits

const int Burger::CompressDeflate::g_ExtraDistanceBits

staticprotected

Initial value:

= {
 0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13
}

g_ExtraLengthBits

const int Burger::CompressDeflate::g_ExtraLengthBits

staticprotected

Initial value:

= {
 0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0
}

g_LengthCodes

const uint8_t Burger::CompressDeflate::g_LengthCodes

staticprotected

Initial value:

= {
 0, 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 12, 12,
 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16,
 17, 17, 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19,
 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 22, 22, 22, 22,
 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23,
 23, 23, 23, 23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26, 26, 26,
 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 28
}

g_StaticBitLengthDescription

const Burger::CompressDeflate::StaticTreeDesc_t Burger::CompressDeflate::g_StaticBitLengthDescription

staticprotected

Initial value:

= {
 NULL,g_ExtraBitLengthBits,0,BL_CODES, MAX_BL_BITS
}

g_StaticDistanceDescription

const Burger::CompressDeflate::StaticTreeDesc_t Burger::CompressDeflate::g_StaticDistanceDescription

staticprotected

Initial value:

= {
 g_StaticDistanceTrees, g_ExtraDistanceBits, 0,D_CODES, MAX_BITS
}

g_StaticDistanceTrees

const Burger::CompressDeflate::CodeData_t Burger::CompressDeflate::g_StaticDistanceTrees

staticprotected

Initial value:

= {
 {{ 0},{ 5}}, {{16},{ 5}}, {{ 8},{ 5}}, {{24},{ 5}}, {{ 4},{ 5}},
 {{20},{ 5}}, {{12},{ 5}}, {{28},{ 5}}, {{ 2},{ 5}}, {{18},{ 5}}, 
 {{10},{ 5}}, {{26},{ 5}}, {{ 6},{ 5}}, {{22},{ 5}}, {{14},{ 5}},
 {{30},{ 5}}, {{ 1},{ 5}}, {{17},{ 5}}, {{ 9},{ 5}}, {{25},{ 5}},
 {{ 5},{ 5}}, {{21},{ 5}}, {{13},{ 5}}, {{29},{ 5}}, {{ 3},{ 5}},
 {{19},{ 5}}, {{11},{ 5}}, {{27},{ 5}}, {{ 7},{ 5}}, {{23},{ 5}}
}

g_StaticLengthDescription

const Burger::CompressDeflate::StaticTreeDesc_t Burger::CompressDeflate::g_StaticLengthDescription

staticprotected

Initial value:

= {
 g_StaticLengthTrees, g_ExtraLengthBits, LITERALS+1, L_CODES, MAX_BITS
}

g_StaticLengthTrees

const Burger::CompressDeflate::CodeData_t Burger::CompressDeflate::g_StaticLengthTrees

staticprotected

g_StaticRTTI

const Burger::StaticRTTI Burger::CompressDeflate::g_StaticRTTI

static

The global description of the class.

---

This record contains the name of this class and a reference to the parent

m_bInitialized

uint_t Burger::CompressDeflate::m_bInitialized

protected

TRUE if initialized

m_BitLengthCount

uint16_t Burger::CompressDeflate::m_BitLengthCount[MAX_BITS+1]

protected

MAX_BITS = 15, so this is long aligned.

m_BitLengthDescription

TreeDesc_t Burger::CompressDeflate::m_BitLengthDescription

protected

desc. for bit length tree

m_BitLengthTrees

CodeData_t Burger::CompressDeflate::m_BitLengthTrees[2 *BL_CODES+1]

protected

Huffman tree for bit lengths.

m_bMatchAvailable

uint_t Burger::CompressDeflate::m_bMatchAvailable

protected

set if previous match exists

m_bMethod

uint8_t Burger::CompressDeflate::m_bMethod

protected

STORED (for zip only) or DEFLATED.

m_bNoHeader

int Burger::CompressDeflate::m_bNoHeader

protected

Suppress zlib header and adler32.

m_DataBuffer

uint16_t Burger::CompressDeflate::m_DataBuffer[c_uLiteralBufferSize]

protected

Buffer for distances. To simplify the code, d_buf and l_buf have the same number of elements. To use different lengths, an extra flag array would be necessary.

m_Depth

uint8_t Burger::CompressDeflate::m_Depth[2 *L_CODES+1]

protected

Depth of each subtree used as tie breaker for trees of equal frequency.

m_DistanceDescription

TreeDesc_t Burger::CompressDeflate::m_DistanceDescription

protected

desc. for distance tree

m_DynamicDistanceTrees

CodeData_t Burger::CompressDeflate::m_DynamicDistanceTrees[2 *D_CODES+1]

protected

distance tree

m_DynamicLengthTrees

CodeData_t Burger::CompressDeflate::m_DynamicLengthTrees[HEAP_SIZE]

protected

literal and length tree

m_eDataType

eDataType Burger::CompressDeflate::m_eDataType

protected

UNKNOWN, BINARY or ASCII.

m_eState

eState Burger::CompressDeflate::m_eState

protected

As the name implies.

m_Head

uint16_t Burger::CompressDeflate::m_Head[c_uHashSize]

protected

Heads of the hash chains or 0.

m_Heap

int Burger::CompressDeflate::m_Heap[2 *L_CODES+1]

protected

heap used to build the Huffman trees

m_iBlockStart

intptr_t Burger::CompressDeflate::m_iBlockStart

protected

Window position at the beginning of the current output block. Gets negative when the window is moved backwards.

m_iHeapLength

int Burger::CompressDeflate::m_iHeapLength

protected

number of elements in the heap

m_iHeapMaximum

int Burger::CompressDeflate::m_iHeapMaximum

protected

element of largest frequency

m_iLastFlush

int Burger::CompressDeflate::m_iLastFlush

protected

Value of flush param for previous deflate call.

m_iPending

int Burger::CompressDeflate::m_iPending

protected

Number of bytes in the pending buffer.

m_LiteralBuffer

uint8_t Burger::CompressDeflate::m_LiteralBuffer[c_uLiteralBufferSize]

protected

buffer for literals or lengths

m_LiteralDescription

TreeDesc_t Burger::CompressDeflate::m_LiteralDescription

protected

desc. for literal tree

m_PendingBuffer

uint8_t Burger::CompressDeflate::m_PendingBuffer[c_uLiteralBufferSize]

protected

Output still pending.

m_pInput

const uint8_t* Burger::CompressDeflate::m_pInput

protected

Next input byte.

m_pPendingOutput

uint8_t* Burger::CompressDeflate::m_pPendingOutput

protected

Next pending byte to output to the stream.

m_Previous

uint16_t Burger::CompressDeflate::m_Previous[c_uWSize]

protected

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.

m_uAdler

uint32_t Burger::CompressDeflate::m_uAdler

protected

Adler32 value of the uncompressed data.

m_uBitIndexBuffer

uint_t Burger::CompressDeflate::m_uBitIndexBuffer

protected

Number of valid bits in bi_buf. All bits above the last valid bit are always zero.

m_uBitIndexValid

uint_t Burger::CompressDeflate::m_uBitIndexValid

protected

Number of bits in the output buffer.

m_uInputLength

uintptr_t Burger::CompressDeflate::m_uInputLength

protected

Number of bytes available at next_in.

m_uInsertHash

uint_t Burger::CompressDeflate::m_uInsertHash

protected

hash index of string to be inserted

m_uLastEOBLength

uint_t Burger::CompressDeflate::m_uLastEOBLength

protected

bit length of EOB code for last block

m_uLastLiteral

uint_t Burger::CompressDeflate::m_uLastLiteral

protected

running index in l_buf

m_uLookAhead

uint_t Burger::CompressDeflate::m_uLookAhead

protected

number of valid bytes ahead in window

m_uMatches

uint_t Burger::CompressDeflate::m_uMatches

protected

number of string matches in current block

m_uMatchLength

uint_t Burger::CompressDeflate::m_uMatchLength

protected

Length of best match.

m_uMatchStart

uint_t Burger::CompressDeflate::m_uMatchStart

protected

start of matching string

m_uOptimalLength

uint32_t Burger::CompressDeflate::m_uOptimalLength

protected

bit length of current block with optimal trees

m_uPreviousLength

uint_t Burger::CompressDeflate::m_uPreviousLength

protected

Length of the best match at previous step. Matches not greater than this are discarded. This is used in the lazy match evaluation.

m_uPreviousMatch

uint_t Burger::CompressDeflate::m_uPreviousMatch

protected

previous match

m_uStaticLength

uint32_t Burger::CompressDeflate::m_uStaticLength

protected

bit length of current block with static trees

m_uStringStart

uint_t Burger::CompressDeflate::m_uStringStart

protected

start of string to insert

m_Window

uint8_t Burger::CompressDeflate::m_Window[c_uWSize *2]

protected

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.

Signature

const uint32_t Burger::CompressDeflate::Signature = 0x5A4C4942

static

'ZLIB'