diff options
Diffstat (limited to 'src/include/usr/ecmddatabuffer/prdfCompressBuffer.H')
| -rw-r--r-- | src/include/usr/ecmddatabuffer/prdfCompressBuffer.H | 389 |
1 files changed, 389 insertions, 0 deletions
diff --git a/src/include/usr/ecmddatabuffer/prdfCompressBuffer.H b/src/include/usr/ecmddatabuffer/prdfCompressBuffer.H new file mode 100644 index 000000000..a77e526ba --- /dev/null +++ b/src/include/usr/ecmddatabuffer/prdfCompressBuffer.H @@ -0,0 +1,389 @@ +// IBM_PROLOG_BEGIN_TAG +// This is an automatically generated prolog. +// +// $Source: src/include/usr/ecmddatabuffer/prdfCompressBuffer.H $ +// +// IBM CONFIDENTIAL +// +// COPYRIGHT International Business Machines Corp. 2011 +// +// p1 +// +// Object Code Only (OCO) source materials +// Licensed Internal Code Source Materials +// IBM HostBoot Licensed Internal Code +// +// The source code for this program is not published or other- +// wise divested of its trade secrets, irrespective of what has +// been deposited with the U.S. Copyright Office. +// +// Origin: 30 +// +// IBM_PROLOG_END +// IMPORTED FROM FIPS340 V1.2 on 11/10/2011 + +// Change Log ***************************************************************** +// +// Flag Reason Vers Date Coder Description +// ---- ------- ---- -------- -------- -------------------------------------- +// F478331 f225 10/07/04 iawillia Initial file creation. +// +// End Change Log ************************************************************* + +#ifndef __PRDFCOMPRESSBUFFER_H +#define __PRDFCOMPRESSBUFFER_H + +#include <stdint.h> +#include <string.h> + +#ifndef MIN +#define MIN(a, b) ( ((a) < (b)) ? (a) : (b) ) +#endif + +/* + * Prdf Compression Algorithm: + * The purpose of these compression routines are to compress the register + * dumps contained in our error logs. In large systems, we could possibly have + * more register data than we could possibly fit in an error log. These + * routines will allow us to fit more data into the error logs. In addition, + * the algorithms have been designed such that even if the end of the stream + * is lost (cut short), we can uncompress all of the data up to that point. We + * had proposed using the Zlib compression algorithms, but they required the + * CRC to match and we did not want that requirement. + * + * This compression algorithm is based off the LZ77 compression algorithm. + * The algorithm consists of a look-behind buffer of 1024 bytes, and a + * look-ahead buffer of 63 bytes. The algorithm attempts to find a match from + * the start of the look-ahead buffer located inside the look-behind buffer. + * If the longest match is bigger than 2 bytes (2 bytes is the break-even + * point), it converts the match into a token (pos in look-behind, length) of + * two bytes (12 bits to pos, 6 to length). If no match is found, the first + * character is popped from the look-ahead buffer. As matches are found (or + * not found) and popped from the look-ahead buffer, they are added to the + * end of the look-behind buffer (if the buffer increases over 1024, the start + * is shifted forward). + * + * As the stream (look-ahead buffer) is converted into tokens, they are + * bundled into groups of 8. A special token is added to the beginning of the + * bundle, recording the size of the following 8 tokens (2 or 1 bytes). Once + * the token bundle is complete (or end-of-stream), it is added to the output + * buffer. + * + * To use these routines, #define PRDF_COMPRESSBUFFER_UNCOMPRESS_FUNCTIONS + * or PRDF_COMPRESSBUFFER_COMPRESS_FUNCTIONS, depending on usage. These reduce + * the code footprint, since only the needed functions are compiled in. + * + */ + +namespace PrdfCompressBuffer +{ + /* size_t compressedBufferMax(size_t) + * Determines the maximum size of the compressed buffer (worst + * case) based on an input buffer size. + */ + #ifdef PRDF_COMPRESSBUFFER_COMPRESS_FUNCTIONS + size_t compressedBufferMax(size_t i_bufSize) + { + return 1 + ((i_bufSize * 9) / 8); + }; + #endif + + static size_t COMPRESSION_BREAKEVEN = 3; + /* class CompressedToken + * Internal class for converting (pos,size) tokens to two char. + */ + class CompressedToken + { + private: + uint8_t token[2]; + + public: + #ifdef PRDF_COMPRESSBUFFER_UNCOMPRESS_FUNCTIONS + // Default constructor. + CompressedToken() {}; + #endif + + #ifdef PRDF_COMPRESSBUFFER_COMPRESS_FUNCTIONS + /* CompressedToken(size_t, size_t) + * Convert position and size to uint8 tokens. + */ + CompressedToken(size_t i_pos, size_t i_size) + { + uint16_t l_token = (i_pos << 6) + | (i_size - COMPRESSION_BREAKEVEN); + token[1] = l_token & 0xFF; + token[0] = (l_token >> 8) & 0xFF; + }; + #endif + + #ifdef PRDF_COMPRESSBUFFER_UNCOMPRESS_FUNCTIONS + /* void uncompress(uint8_t *, uint8_t *&, size_t&) + * Convert uint8 tokens to pos,size values. Changes + * o_pos to be a pointer to the string inside the buffer and sets + * o_size to be the size of the string. + */ + void uncompress(uint8_t * i_buf, uint8_t * &o_pos, size_t &o_size) + { + uint16_t l_token = (token[0] << 8) | token[1]; + + o_pos = &i_buf[(l_token & 0xFFC0) >> 6]; + o_size = (l_token & 0x3F) + COMPRESSION_BREAKEVEN; + + return; + }; + /* void read(uint8_t *) + * Read two bytes from the buffer to keep as tokens. + * NOTE: Does not modify i_buf. + */ + void read(uint8_t * i_buf) + { + token[0] = i_buf[0]; + token[1] = i_buf[1]; + }; + #endif + + #ifdef PRDF_COMPRESSBUFFER_COMPRESS_FUNCTIONS + /* void write(uint8_t *) + * Copy tokens into the beginning of the buffer. + */ + void write(uint8_t * o_buf) { memcpy(o_buf, token, 2); }; + #endif + + size_t size() { return 2; }; + }; + + #ifdef PRDF_COMPRESSBUFFER_COMPRESS_FUNCTIONS + /* void compressBuffer(uint8_t *, size_t, uint8_t *, size_t &) + * Compresses i_buf and stores result into o_buf. + * + * i_buf : pointer to input buffer. + * i_size : size of input buffer. + * o_buf : pointer to output buffer (supplied by caller). + * o_size : max size of output buffer. After function, size of + * compressed buffer. + * + * NOTE: The size of the output buffer should be 1 + ((i_size * 9) / 8) + * to guarentee no data is lost (worst case for compression). + */ + void compressBuffer(uint8_t * i_buf, size_t i_size, + uint8_t * o_buf, size_t &o_size) + { + // Asserts. + if ((i_buf == NULL) || (o_buf == NULL)) + { + o_size = 0; + return; + } + + uint8_t * l_lookahead = i_buf; // Pointer to the look-behind buf. + size_t l_laSize = 0; // Size of look-behind. + + size_t l_tokPos = 0; // Number of tokens in the bundle. + uint8_t * l_tokC = o_buf++; // Store compress bits and advance ptr. + size_t l_outputSize = 1; // start with l_tokC. + + while((i_size > 0) && (l_outputSize < o_size)) + { + size_t l_curLen = 1; + uint8_t * l_match = NULL; + + // Find the longest match. (2 is our break-even pt, + // but 3 will provide better compression). + for (size_t i = 3; + i < MIN(i_size, l_laSize) && (i < (64 + COMPRESSION_BREAKEVEN)) + ; i++) + { + uint8_t * l_tmpMatch = NULL; + + // MIKE TODO + l_tmpMatch = NULL; + //l_tmpMatch = (uint8_t *) memmem(l_lookahead, l_laSize, + //i_buf, i); + + if (l_tmpMatch != NULL) // found match. + { + l_match = l_tmpMatch; + l_curLen = i; + } + else + i = i_size + l_laSize; // abort for loop. + } + + // Create token. + if (l_match != NULL) + { + // found match, make sure there is room for the token. + if (o_size - l_outputSize >= 2) + { + CompressedToken l_token(l_match - l_lookahead, l_curLen); + + l_token.write(o_buf); + o_buf += 2; + l_outputSize += 2; + + (*l_tokC) = (*l_tokC << 1) | 0x1; + l_tokPos++; + + i_buf += l_curLen; + l_laSize += l_curLen; + i_size -= l_curLen; + } + else + { + l_outputSize = o_size; + } + } + else + { + // no match, copy if room in the buffer. + if (o_size - l_outputSize >= 1) + { + o_buf[0] = i_buf[0]; + o_buf++; + l_outputSize++; + + (*l_tokC) = (*l_tokC << 1) | 0x0; + l_tokPos++; + + i_buf++; + l_laSize++; + i_size--; + } + // else <= 0, so don't mess with l_outputSize. + } + + // flush out lookahead. (keep at 1024 bytes) + while(l_laSize >= 1024) + { + l_laSize--; + l_lookahead++; + } + + // check if bundle complete, create new bundle. + if (l_tokPos == 8) + { + l_tokPos = 0; + l_tokC = o_buf++; + l_outputSize++; + } + + } // end while. + + // Shift our bundle bits correctly. (the uncompressor doesn't know if + // the bundle was complete, so always assumes so. + if (l_tokPos != 0) + (*l_tokC) = (*l_tokC) << (8 - l_tokPos); + + // We never _really_ go past our buffer, but sometimes our size says + // we did, so fix that up... + if (l_outputSize <= o_size) + o_size = l_outputSize; + + return; + }; + #endif + + #ifdef PRDF_COMPRESSBUFFER_UNCOMPRESS_FUNCTIONS + /* void uncompressBuffer(uint8_t *, size_t, uint8_t *, size_t &) + * Uncompresses i_buf and stores result into o_buf. + * + * i_buf : pointer to input buffer. + * i_size : size of input buffer. + * o_buf : pointer to output buffer (supplied by caller). + * o_size : max size of output buffer. After function, size of + * uncompressed buffer. + * + * NOTE: The size is never stored in an compressed or uncompressed buffer. + * The caller needs to keep track of those kind of things and add + * whatever kind of header they need. If o_size isn't big enough + * you're not going to get the whole stream. These functions will + * not overrun the buffer. + */ + void uncompressBuffer(uint8_t * i_buf, size_t i_size, + uint8_t * o_buf, size_t & o_size) + { + // Asserts. + if ((i_buf == NULL) || (o_buf == NULL)) + { + o_size = 0; + return; + } + + uint8_t * l_lookahead = o_buf; // Look-behind buffer. + size_t l_laSize = 0; // look-behind size. + + uint8_t l_tokC = 0; // Bundle bits. + uint8_t l_tokPos = 8; // Number of tokens from the bundle + // thus far. (start at 8 to get a new + // bundle right away). + + size_t l_outputSize = 0; // Size of output buffer. + + while ((i_size > 0) & (o_size > 0)) // while we're at the end of a buf. + { + // Check if we need to get a new bundle. + if (l_tokPos == 8) + { + l_tokPos = 0; + l_tokC = i_buf[0]; + i_buf++; + i_size--; + continue; + } + + + // Check if token was compressed or not. + if ((l_tokC >> (7 - l_tokPos)) & 0x1) + { + // compressed token... + + size_t l_matchSize; + uint8_t * l_match; + CompressedToken l_tok; + + // read token from stream. + l_tok.read(i_buf); + i_buf += l_tok.size(); + i_size -= l_tok.size(); + + // get pointer to lookahead buffer, copy into output buffer. + l_tok.uncompress(l_lookahead, l_match, l_matchSize); + memcpy(o_buf, l_match, MIN(l_matchSize, o_size)); + + // fix up all our sizes and pointers. + l_laSize += l_matchSize; + l_outputSize += MIN (l_matchSize, o_size); + o_size -= MIN (l_matchSize, o_size); + o_buf += l_matchSize; + } + else + { + // uncompressed token... just copy the byte. + + o_buf[0] = i_buf[0]; + o_size--; + o_buf++; + i_buf++; + i_size--; + + l_laSize++; + l_outputSize++; + } + l_tokPos++; // just did a token, so inc the bundle count. + + // Advance the look-behind buffer as needed. + while (l_laSize >= 1024) + { + l_lookahead++; + l_laSize--; + } + } + + // fix up o_size (since we've been decrementing it...) + o_size = l_outputSize; + }; + #endif + +}; // end namespace. + +#endif |
