Compress data using LZSS encoding. More...

Inheritance diagram for Burger::CompressLZSS:

[legend]

Collaboration diagram for Burger::CompressLZSS:

[legend]

Public Member Functions
const Burger::StaticRTTI *	get_StaticRTTI (void) const noexcept override
	Get the description to the class.

	CompressLZSS (void)
	Initialize the compressor to defaults.

eError	Init (void) override
	Initialize the compression algorithm.

eError	Process (const void *pInput, uintptr_t uInputLength) override
	Compress data.

eError	Finalize (void) override
	Finish the 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 = 0x4C5A5353
	'LZSS'

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 Member Functions
void	DeleteNode (uintptr_t uNodeNumber)
	Removes a node from the binary tree.

void	InsertNode (uintptr_t uNodeNumber)
	Scans the node in the ring buffer for a previous match.

void	InitTrees (void)
	Init the binary tree needed for the compression system.

Protected Attributes
uintptr_t	m_uBitMaskOffset
	Location in the output stream to store any bit masks.

uint_t	m_uSourceIndex
	Index to insert nodes into.

uint_t	m_uDestIndex
	Index to remove nodes from (is usually CompressLZSS::m_uSourceIndex-MAXMATCHLENGTH)

uint_t	m_uCachedLength
	Ring buffer cache size (Max CompressLZSS::MAXMATCHLENGTH)

uint_t	m_uMatchOffset
	Offset of string match.

uint_t	m_uMatchSize
	Length of string match 0-18 of longest match. These are set by the InsertNode() procedure.

uint_t	m_uPreviousMatchSize
	Length of the last match.

uint_t	m_uMatchIterator
	Match size iterator.

uint_t	m_LeftBranch [RINGBUFFERSIZE+1]
	Left child.

uint_t	m_RightBranch [RINGBUFFERSIZE+1+256]
	Right child / Hash table.

uint_t	m_RootBranch [RINGBUFFERSIZE+1]
	Roots for each binary tree left & right children & parents.

uint8_t	m_bBitMask
	Bit field to store in the output stream.

uint8_t	m_bOrMask
	Bit mask for which bit is currently being modified.

uint8_t	m_RingBuffer [RINGBUFFERSIZE+MAXMATCHLENGTH-1]
	Ring buffer of size RINGBUFFERSIZE, with extra MAXMATCHLENGTH-1 bytes to facilitate string comparison.

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	RINGBUFFERSIZE =4096
	Size of the LZSS ring buffer.

static const uint_t	MAXMATCHLENGTH =18
	Largest size of a string to match.

static const uint_t	MINMATCHLENGTH =2
	Encode string into position and length.

static const uint_t	NOTUSED =RINGBUFFERSIZE
	Index for root of binary search trees.

Detailed Description

Compress data using LZSS encoding.

Lempel Ziv Storer Szymanski (LZSS) encoding is explained here.

http://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Storer%E2%80%93Szymanski

This compression performs string compares from the previous 4096 bytes of the data stream and if a match of 3 to 18 bytes are found, a sixteen bit index token is encoded to perform a copy from the previous data to the current data.

The format is as follows, a byte is encoded with 8 bits with a one meaning an 8 bit value follows or a zero meaning a 16 bit index follows. After 8 samples have been parsed, another 8 bit byte will be fetched and the process is repeated.

The 16 bit token has the upper 4 bits encoded with 0-15 converted to 3-18 as a byte count and the lower 12 bits is negative sign extended and added to the current output pointer and the bytes are copied from the previously decompressed data to the current buffer

See also: Burger::DecompressLZSS

Constructor & Destructor Documentation

◆ CompressLZSS()

Burger::CompressLZSS::CompressLZSS ( void )

Initialize the compressor to defaults.

Member Function Documentation

◆ DeleteNode()

void Burger::CompressLZSS::DeleteNode ( uintptr_t uNodeNumber )

protected

Removes a node from the binary tree.

Prunes an entry from the binary string match tree

Parameters

uNodeNumber Ring buffer index (0-(CompressLZSS::RINGBUFFERSIZE-1))

See also: InsertNode(uint_t)

◆ Finalize()

Burger::eError Burger::CompressLZSS::Finalize ( void )

overridevirtual

Finish the compression.

Perform the final data compaction and clean up. After this call is performed, the output is valid and can be accessed with calls to GetOutput() and GetOutputSize()

Note: This is must be implemented by derived class.

Returns: Zero if no failure, non-zero is an error code

See also: GetOutput() and GetOutputSize()

Implements Burger::Compress.

◆ get_StaticRTTI()

const Burger::StaticRTTI * Burger::CompressLZSS::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::CompressLZSS::Init ( void )

overridevirtual

Initialize the compression algorithm.

This function will reset the compression algorithm (Which may or may not require memory allocations) and returns an error code if there was a failure.

Note: This is must be implemented by derived class and it also acts as a "reset" function to recycle this class to perform compression on new data.

Returns: Zero if no failure, non-zero is an error code

Implements Burger::Compress.

◆ InitTrees()

void Burger::CompressLZSS::InitTrees ( void )

protected

Init the binary tree needed for the compression system.

For i = 0 to CompressLZSS::RINGBUFFERSIZE - 1, CompressLZSS::m_RightBranch[i] and CompressLZSS::m_LeftBranch[i] will be the right and left children of node i. These nodes need not be initialized. Also, CompressLZSS::m_RootBranch[i] is the parent of node i. These are initialized to CompressLZSS::NOTUSED For i = 0 to 255, CompressLZSSm_RightBranch[CompressLZSS::RINGBUFFERSIZE + i + 1] is the root of the tree for strings that begin with character i. These are initialized to CompressLZSS::NOTUSED.

The hash is 8 bit, hence 256 hash entries

See also: Init(void)

◆ InsertNode()

void Burger::CompressLZSS::InsertNode ( uintptr_t uNodeNumber )

protected

Scans the node in the ring buffer for a previous match.

Inserts string of length CompressLZSS::MAXMATCHLENGTH, CompressLZSS::m_RingBuffer[?..?+ CompressLZSS::MAXMATCHLENGTH -1], into one of the trees (CompressLZSS::m_RingBuffer[uNodeNumber]'th tree) and returns the longest-match position and length via the variables CompressLZSS::m_uMatchOffset and CompressLZSS::m_uMatchSize. If CompressLZSS::m_uMatchSize = CompressLZSS::MAXMATCHLENGTH, then removes the old node in favor of the new one, because the old one will be deleted sooner.

Note: uNodeNumber plays double role, as tree node and position in buffer.

Parameters

uNodeNumber Ring buffer index (0-(CompressLZSS::RINGBUFFERSIZE-1))

See also: DeleteNode(uint_t)

◆ Process()

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

overridevirtual

Compress data.

Pass data into the compressor and store the output into the data stream

Note: This is must be implemented by derived class.

Parameters

pInput	Pointer to data to compress
uInputLength	Number of bytes in the data

Returns: Zero if no failure, non-zero is an error code

Implements Burger::Compress.

Member Data Documentation

◆ g_StaticRTTI

const Burger::StaticRTTI Burger::CompressLZSS::g_StaticRTTI

static

The global description of the class.

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

◆ m_bBitMask

uint8_t Burger::CompressLZSS::m_bBitMask

protected

Bit field to store in the output stream.

◆ m_bOrMask

uint8_t Burger::CompressLZSS::m_bOrMask

protected

Bit mask for which bit is currently being modified.

◆ m_LeftBranch

uint_t Burger::CompressLZSS::m_LeftBranch[RINGBUFFERSIZE+1]

protected

Left child.

◆ m_RightBranch

uint_t Burger::CompressLZSS::m_RightBranch[RINGBUFFERSIZE+1+256]

protected

Right child / Hash table.

◆ m_RingBuffer

uint8_t Burger::CompressLZSS::m_RingBuffer[RINGBUFFERSIZE+MAXMATCHLENGTH-1]

protected

Ring buffer of size RINGBUFFERSIZE, with extra MAXMATCHLENGTH-1 bytes to facilitate string comparison.

◆ m_RootBranch

uint_t Burger::CompressLZSS::m_RootBranch[RINGBUFFERSIZE+1]

protected

Roots for each binary tree left & right children & parents.

◆ m_uBitMaskOffset

uintptr_t Burger::CompressLZSS::m_uBitMaskOffset

protected

Location in the output stream to store any bit masks.

◆ m_uCachedLength

uint_t Burger::CompressLZSS::m_uCachedLength

protected

Ring buffer cache size (Max CompressLZSS::MAXMATCHLENGTH)

◆ m_uDestIndex

uint_t Burger::CompressLZSS::m_uDestIndex

protected

Index to remove nodes from (is usually CompressLZSS::m_uSourceIndex-MAXMATCHLENGTH)

◆ m_uMatchIterator

uint_t Burger::CompressLZSS::m_uMatchIterator

protected

Match size iterator.

◆ m_uMatchOffset

uint_t Burger::CompressLZSS::m_uMatchOffset

protected

Offset of string match.

◆ m_uMatchSize

uint_t Burger::CompressLZSS::m_uMatchSize

protected

Length of string match 0-18 of longest match. These are set by the InsertNode() procedure.

◆ m_uPreviousMatchSize

uint_t Burger::CompressLZSS::m_uPreviousMatchSize

protected

Length of the last match.

◆ m_uSourceIndex

uint_t Burger::CompressLZSS::m_uSourceIndex

protected

Index to insert nodes into.

◆ MAXMATCHLENGTH

const uint_t Burger::CompressLZSS::MAXMATCHLENGTH =18

staticprotected

Largest size of a string to match.

◆ MINMATCHLENGTH

const uint_t Burger::CompressLZSS::MINMATCHLENGTH =2

staticprotected

Encode string into position and length.

◆ NOTUSED

const uint_t Burger::CompressLZSS::NOTUSED =RINGBUFFERSIZE

staticprotected

Index for root of binary search trees.

◆ RINGBUFFERSIZE

const uint_t Burger::CompressLZSS::RINGBUFFERSIZE =4096

staticprotected

Size of the LZSS ring buffer.

◆ Signature

const uint32_t Burger::CompressLZSS::Signature = 0x4C5A5353

static

'LZSS'

Public Member Functions

Static Public Attributes

Protected Member Functions

Protected Attributes

Static Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ CompressLZSS()

Member Function Documentation

◆ DeleteNode()

◆ Finalize()

◆ get_StaticRTTI()

◆ Init()

◆ InitTrees()

◆ InsertNode()

◆ Process()

Member Data Documentation

◆ g_StaticRTTI

◆ m_bBitMask

◆ m_bOrMask

◆ m_LeftBranch

◆ m_RightBranch

◆ m_RingBuffer

◆ m_RootBranch

◆ m_uBitMaskOffset

◆ m_uCachedLength

◆ m_uDestIndex

◆ m_uMatchIterator

◆ m_uMatchOffset

◆ m_uMatchSize

◆ m_uPreviousMatchSize

◆ m_uSourceIndex

◆ MAXMATCHLENGTH

◆ MINMATCHLENGTH

◆ NOTUSED

◆ RINGBUFFERSIZE

◆ Signature