Compress data using LZSS encoding. More...
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. | |
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
Burger::CompressLZSS::CompressLZSS | ( | void | ) |
Initialize the compressor to defaults.
|
protected |
Removes a node from the binary tree.
Prunes an entry from the binary string match tree
uNodeNumber | Ring buffer index (0-(CompressLZSS::RINGBUFFERSIZE-1)) |
|
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()
Implements Burger::Compress.
|
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.
Reimplemented from Burger::Compress.
|
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.
Implements Burger::Compress.
|
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
|
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.
uNodeNumber | Ring buffer index (0-(CompressLZSS::RINGBUFFERSIZE-1)) |
|
overridevirtual |
Compress data.
Pass data into the compressor and store the output into the data stream
pInput | Pointer to data to compress |
uInputLength | Number of bytes in the data |
Implements Burger::Compress.
|
static |
The global description of the class.
This record contains the name of this class and a reference to the parent
|
protected |
Bit field to store in the output stream.
|
protected |
Bit mask for which bit is currently being modified.
|
protected |
Left child.
|
protected |
Right child / Hash table.
|
protected |
Ring buffer of size RINGBUFFERSIZE, with extra MAXMATCHLENGTH-1 bytes to facilitate string comparison.
|
protected |
Roots for each binary tree left & right children & parents.
|
protected |
Location in the output stream to store any bit masks.
|
protected |
Ring buffer cache size (Max CompressLZSS::MAXMATCHLENGTH)
|
protected |
Index to remove nodes from (is usually CompressLZSS::m_uSourceIndex-MAXMATCHLENGTH)
|
protected |
Match size iterator.
|
protected |
Offset of string match.
|
protected |
Length of string match 0-18 of longest match. These are set by the InsertNode() procedure.
|
protected |
Length of the last match.
|
protected |
Index to insert nodes into.
|
staticprotected |
Largest size of a string to match.
|
staticprotected |
Encode string into position and length.
|
staticprotected |
Index for root of binary search trees.
|
staticprotected |
Size of the LZSS ring buffer.
|
static |
'LZSS'