changeset
- moved huffman from sources/ to top level because it's external
Fri, 15 May 2015 20:13:36 +0300
- author
- Teemu Piippo <crimsondusk64@gmail.com>
- date
- Fri, 15 May 2015 20:13:36 +0300
- changeset 76
- 6de6d9a64ebd
- parent 75
- 5f8a03274d75
- child 77
- 32ef969adeed
- moved huffman from sources/ to top level because it's external
--- a/CMakeLists.txt Fri May 15 20:10:44 2015 +0300 +++ b/CMakeLists.txt Fri May 15 20:13:36 2015 +0300 @@ -1,6 +1,13 @@ cmake_minimum_required (VERSION 2.4) project (zfc9000) +add_library (huffman STATIC + huffman/bitreader.cpp + huffman/bitwriter.cpp + huffman/huffcodec.cpp + huffman/huffman.cpp +) + set (SOURCE_FILES sources/coloredline.cpp sources/format.cpp @@ -13,10 +20,6 @@ sources/network/ipaddress.cpp sources/network/rconsession.cpp sources/network/udpsocket.cpp - sources/huffman/bitreader.cpp - sources/huffman/bitwriter.cpp - sources/huffman/huffcodec.cpp - sources/huffman/huffman.cpp ) set (CURSES_NEED_NCURSES, True) @@ -24,8 +27,9 @@ find_package (Curses) include_directories (${CURSES_INCUDE_DIRS}) include_directories (${CMAKE_CURRENT_BINARY_DIR}) +include_directories (huffman) add_executable (${PROJECT_NAME} ${SOURCE_FILES}) -target_link_libraries (${PROJECT_NAME} ${CURSES_LIBRARIES}) +target_link_libraries (${PROJECT_NAME} ${CURSES_LIBRARIES} huffman) add_custom_target (make_hginfo_h COMMAND python
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/huffman/bitreader.cpp Fri May 15 20:13:36 2015 +0300 @@ -0,0 +1,144 @@ +/* + * skulltag::BitReader class - Allows reading arbitrary bit lengths of data. + * Version 1 - Revsion 0 + * + * Copyright 2009 Timothy Landers + * email: code.vortexcortex@gmail.com + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. + */ + +#include "bitreader.h" +/** Prevents naming convention problems via encapsulation. */ +namespace skulltag { + // BitReader class implementation + + int BitReader::intBitSize = 0; + int BitReader::intSize = 0; + int BitReader::mask[32] = {0}; + + /** Creates a new BitReader. */ + BitReader::BitReader(){ + init(); + } + + /** Creates a new BitReader. + * @param input Source of data that bits will be read from. + * @param max Maximum number of chars to read. */ + BitReader::BitReader( unsigned char const * input, int const &max ){ + inputBuffer( input, max ); + } + + /** Sets the input buffer that bytes will be read from. + * @param input Source of data that bits will be read from. + * @param max Maximum number of chars to input. + * @return true if successful, false if an error occurs. */ + bool BitReader::inputBuffer( unsigned char const * input, int const &max ){ + init(); // zero the vars. + currentByte = input; + if ( input == 0 ) return false; + if ( max < 1 ) return false; + bytesAvailable = max; + bitsAvailable = max << 3; + maximumBytes = max; + return true; + } + + /** Initializes this BitReader */ + void BitReader::init(){ + // initialize static variables if not initialized yet. + if ( intSize == 0 ){ + intSize = sizeof maximumBytes; + mask[0] = 0; + + // fill mask such that m = { 0, 1, 3, 7, 15, etc. } + for ( int i = 1; i < 32; i++ ) mask[i] = (mask[i-1] << 1) | 1; + + intBitSize = intSize << 3; + } + + // initialize member variables. + bitsAvailable = 0; + bytesAvailable = 0; + bufferBits = 0; + currentByte = 0; + maximumBytes = 0; + bitsUsed = 0; + } + + /** Fills the internal bit buffer. + * @return true if successful, false if an error occurs. */ + bool BitReader::fill(){ + if ( (currentByte == 0) || (bytesAvailable <= 0) ) return false; + + // while there's at least one octet free in the buffer, and one byte to read. + while ( (bitsUsed < (intBitSize - 8)) && (bytesAvailable > 0) ){ + + // put a byte into the bottom end of the buffer. + bufferBits |= (*currentByte & mask[8]) << (intBitSize - bitsUsed - 8); + + // Set variables to reflect the change. + currentByte++; + bytesAvailable--; + bitsUsed += 8; + } + return true; + } + + /** Fetches a specified number of bits and stores them in an int. + * @param bits destination of the retrieved bits. <br> + * The bits will be stored in the least significant portion of the int. + * @param count the number of bits to fetch. + * @return the number of bits read -- may not be equal to the amount requested. */ + int BitReader::get( int &bits, int const &count ){ + bits = 0; + // Requesting more bits than are available. + if ( count > bitsAvailable ) return 0; + if ( (count > bitsUsed) && (!fill()) ) return 0; + bits = (bufferBits >> (intBitSize - count)) & mask[count]; + // lesser of bits in buffer or requested bits. + int got = (bitsUsed < count) ? bitsUsed : count; + // get as many bits from the buffer as we can. + if ( got > 0 ){ + bufferBits <<= got; + bitsUsed -= got; + bitsAvailable -= got; + } + // if more bits are requested. + if ( count > got ){ + if (!fill()) { + bits = (bits >> (count - got)) & mask[count - got]; + return got; + } + got = count - got; + // avoid reading more bits than available. + if ( got <= bitsAvailable ){ + bits |= (bufferBits >> (intBitSize - got)) & mask[got]; + bufferBits <<= got; + bitsUsed -= got; + bitsAvailable -= got; + } + } + return count; + } + + /** @return Amount of bits that can be read from this BitReader. */ + int BitReader::availableBits(){ return bitsAvailable; } + +} // end namespace skulltag
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/huffman/bitreader.h Fri May 15 20:13:36 2015 +0300 @@ -0,0 +1,85 @@ +/** + * skulltag::BitReader class - Allows reading arbitrary bit lengths of data. + * Version 1 - Revsion 0 + * + * Copyright 2009 Timothy Landers + * email: code.vortexcortex@gmail.com + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. + */ + +#ifndef _BIT_READER_VERSION +#define _BIT_READER_VERSION 1 + +/** Prevents naming convention problems via encapsulation. */ +namespace skulltag { // scope limitation + +/** BitReader - Allows reading of varying amounts of bits from a char buffer. <br> + * Very usefull for inputting variable bit length encodings such as Huffman. */ + + class BitReader { + int bufferBits; /**< intermediary buffer of bits. */ + int bitsUsed; /**< number of bits used in the buffer. */ + unsigned char const * currentByte; /**< position in memory the next char will be read. */ + int bytesAvailable; /**< amount of available space left in the input buffer in bytes. Excludes the contents of bufferBits. */ + int bitsAvailable; /**< amount of available space left in the input buffer in bits. Includes the contents of bufferBits. */ + int maximumBytes; /**< total amount of bytes that can be read from the input buffer. */ + static int mask[]; /**< maps a number of bits to a bit mask containing as many bits. */ + static int intSize; /**< number of chars in an int. */ + static int intBitSize; /**< number of bits in an ing. */ +public: + + /** Creates a new BitReader. */ + BitReader(); + + /** Creates a new BitReader. + * @param input Source of data that bits will be read from. + * @param max Maximum number of chars to read. */ + BitReader( unsigned char const * input, int const &max ); + + /** Sets the input buffer that bytes will be read from. + * @param input Source of data that bits will be read from. + * @param max Maximum number of chars to input. + * @return true if successful, false if an error occurs. */ + bool inputBuffer( unsigned char const * input, int const &max ); + + /** Fetches a specified number of bits and stores them in an int. + * @param bits destination of the retrieved bits. <br> + * The bits will be stored in the least significant portion of the int. + * @param count the number of bits to fetch. + * @return the number of bits read -- may not be equal to the amount requested. */ + int get( int &bits, int const &count ); + + /** @return Amount of bits that can be read from this BitReader. */ + int availableBits(); + + private: + + /** Fills the internal bit buffer. + * @return true if successful, false if an error occurs. */ + bool fill(); + + /** Initializes this BitReader. */ + void init(); + + }; + +} +#endif +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/huffman/bitwriter.cpp Fri May 15 20:13:36 2015 +0300 @@ -0,0 +1,271 @@ +/* + * skulltag::BitWriter class - Enables writing arbitrary bit lengths of data. + * + * Copyright 2009 Timothy Landers + * email: code.vortexcortex@gmail.com + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. + */ + +#include "bitwriter.h" + +/* The internal buffer of bits is an int which is initiallized to zero. + * The Bit Buffer: [00000000000000000000000000000000] - 0 bits stored. + * + * Bits stored in the bit buffer occupy the most significant bits available. + * When bits are stored their order is preserved. + * Storing the 5 bits 01011 into the bit buffer would result in: + * The Bit Buffer: [01011000000000000000000000000000] - 5 bits stored. + * + * Additionally storing 0x12f3 (13 bits) would result in: + * The Bit Buffer: [01011100101111001100000000000000] - 18 bits stored. + * + * Data is stored via any of the put(...) functions. + * + * To retrieve bytes (chars) of data from the bit buffer and empty the bit buffer: flush(); + * Flushing the bit buffer takes groups of 8 bits (octets) and stores them in the + * output buffer at the current byte position. Calling flush() would cause output + * to receive 2 bytes (0x5c, 0xbc) == (01011100, 10111100) and the remaining bits would + * be moved to the most significant bit positions. + * The Bit Buffer: [11000000000000000000000000000000] - 2 bits stored. + * Note: The empty bits of the bit buffer must be zero to avoid additional masking operations. + * flush() is called automatically if the bit buffer is too full during a call to put(...) + * + * When the bit storage operation is complete call finish(...). Finish will flush as many full + * bytes of data into the output buffer as possible, the remaining bits will be padded out + * to a full octet with zeros (on their less significant side), then written to the output + * buffer. finish( bytesStored, padding ) passes by reference the number of bytes stored + * and number of padding bits added (0 to 7) to the last stored byte. + * + * Bits are not added one at a time, they are masked, shifted and bitwise OR'ed into + * the buffer in as large a group as possible. This allows the BitWriter to add multiple bits in a single + * operation instead of calling a function for each 1 bit added. + * + * Normal usage: + * + * char * dataArray = new char[ max_output_size ]; + * BitWriter * buffer = new BitWriter( dataArray, max_output_size ); + * ... + * // various calls to put(...); + * ... + * int numBytesOutput, paddedBits; + * buffer->finish( numBytesOutput, paddedBits ); + * ... + * // do something with dataArray + * ... + * delete buffer; + * delete dataArray; + * + * */ + +/** Prevents naming convention problems via encapsulation. */ +namespace skulltag { + + // Static variable initially set to zero as a signal for init() + int BitWriter::intSize = 0; + int BitWriter::mask[32]; + + /** Initializes this BitWriter. */ + void BitWriter::init(){ + + // initialize static variables if not initialized yet. + if ( intSize == 0 ){ + intSize = sizeof maximumBytes; + mask[0] = 0; + + // fill mask such that m = { 0, 1, 3, 7, 15, etc. } + for ( int i = 1; i < 32; i++ ) mask[i] = (mask[i-1] << 1) | 1; + } + + // initialize member variables. + bitsAvailable = 0; + bytesAvailable = 0; + bufferBits = 0; + currentByte = 0; + maximumBytes = 0; + bitsLeft = intSize << 3; + } + + /** Creates a new BitWriter. */ + BitWriter::BitWriter(){ + init(); + } + + /** Creates a new BitWriter. + * @param output Destination that bits will be written to. + * @param max Maximum number of chars to output. */ + BitWriter::BitWriter( unsigned char * const output, int const &max ){ + outputBuffer( output, max ); + } + + /** Sets the output buffer that bytes will be written to. + * @param output Destination that bits will be written to. + * @param max Maximum number of chars to output. + * @return true if successful, false otherwise. */ + bool BitWriter::outputBuffer( unsigned char * const output, int const &max ){ + init(); // zero the vars. + currentByte = output; + if ( output == 0 ) return false; + if ( max < 1 ) return false; + bytesAvailable = max; + bitsAvailable = max << 3; + maximumBytes = max; + return true; + } + + /** Appends a char worth of bits to the buffer. + * @param bits the bits to append. + * @return true if successful, false otherwise. */ + bool BitWriter::put( unsigned char const &bits ){ + return put( (int)bits, 8 ); + } + + /** Appends a short worth of bits to the buffer. + * @param bits the bits to append. + * @return true if successful, false otherwise. */ + bool BitWriter::put( short const &bits ){ + static int shortBitSize = (sizeof bits) << 3; + return put( (int)bits, shortBitSize ); + } + /** Appends an int worth of bits to the buffer. + * @param bits the bits to append. + * @return true if successful, false otherwise. */ + bool BitWriter::put( int const &bits ){ + static int intBitSize = intSize << 3; + return put( bits, intBitSize); + } + + /** Appends multiple chars from a buffer to this BitWriter. + * @param inputBuffer pointer to char data + * @param count number of chars to read + * @return true if successful, false otherwise. */ + bool BitWriter::put( unsigned char const * const inputBuffer, int count ){ + int i = 0; + + // Read in 4 bytes at a time and send all at once to the bit buffer. + while ( (i + 3) < count ){ + if ( !put( + ((int)inputBuffer[ i ] << 24) | + ((int)inputBuffer[i+1] << 16) | + ((int)inputBuffer[i+2] << 8) | + (int)inputBuffer[i+3], 32 + ) ) return false; + i+=4; + } + + // If any bytes remain, output them one at a time. + while ( i < count ){ + if ( !put( (int)inputBuffer[ i ], 8 ) ) return false; + i++; + } + + return true; + } + + /** Appends a specified number of bits from an int to the buffer. + * @param bits the bits to append. <br> + * The bits should be stored in the least significant portion of the int. + * @param count the number of bits to append. + * @return true if successful, false otherwise. */ + bool BitWriter::put( int const &bits, int count ){ + if ( count > bitsAvailable ) return false; + if ( (bitsLeft < 1) && (!flush()) ) return false; + if ( count > bitsLeft ){ + // not enough space in buffer, fill buffer with top end of input bits then flush. + bufferBits |= mask[bitsLeft] & (bits >> (count - bitsLeft)); + count -= bitsLeft; + bitsAvailable -= bitsLeft; + bitsLeft = 0; + + // Buffer's full, needs flushing. + if (!flush()) return false; + } + + // if there are still bits of input... + if ( count > 0 ){ + + // shift the input bits up to the end of the bit buffer. + bufferBits |= (mask[count] & bits) << (bitsLeft - count); + bitsAvailable -= count; + bitsLeft -= count; + } + return true; + } + + /** Writes any full chars of data stored in this BitWriter to the output char buffer. + * @return true if successful, false if an error occurs. */ + bool BitWriter::flush(){ + // static var to hold how many bits are in an int. + static int intBitSize = intSize << 3; + if ( currentByte == 0 ) return false; + int numBits = intBitSize - bitsLeft; + + // while there's at least one octet of data in the buffer. + while ( numBits > 7 ){ + + // fail if no bytes can be written. + if ( bytesAvailable <= 0 ) return false; + + // get a byte off the top end of the buffer. + *currentByte = (bufferBits >> (intBitSize - 8)) & mask[8]; + + // Set variables to reflect the change. + currentByte++; + bytesAvailable--; + bufferBits = bufferBits << 8; + bitsLeft += 8; + numBits -= 8; + } + return true; + } + + /** Flushes this BitWriter then outputs any partial chars by padding them with zeros. <br> + * After calling finish() all other calls to update the BitWriter will fail until a buffer is set via outputBuffer(). + * @param bytesWritten out: the number of bytes written to the output buffer. + * @param paddingBits out: the number of padding bits used in the final byte of output. + * @return true if successful, false if an error occurs. */ + bool BitWriter::finish( int &bytesWritten, int &paddingBits ){ + static int intBitSize = intSize << 3; + // set meaningful return values even if flush() fails. + bytesWritten = maximumBytes - bytesAvailable; + paddingBits = 0; + if ( flush() ){ + // use a temp var to avoid setting paddingBits to invalid value on failure. + int pad = (8 - (intBitSize - bitsLeft)) & 7; + if ( pad > 0 ){ + // all empty bits should be zero. Artificially extend by the number of bits needed. + bitsLeft -= pad; + if ( !flush() ){ + // Prevent futher use even on failure. + init(); + return false; + } + // return the temp bit padding value. + paddingBits = pad; + } + bytesWritten = maximumBytes - bytesAvailable; + init(); // set initial state -- no further writing can occur. + return true; + } + // Prevents futher use even on failure. + init(); + return false; + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/huffman/bitwriter.h Fri May 15 20:13:36 2015 +0300 @@ -0,0 +1,109 @@ +/* + * skulltag::BitWriter class - Enables writing arbitrary bit lengths of data. + * + * Copyright 2009 Timothy Landers + * email: code.vortexcortex@gmail.com + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. + */ + +#ifndef _BIT_WRITER_VERSION +#define _BIT_WRITER_VERSION 1 + +/** Prevents naming convention problems via encapsulation. */ +namespace skulltag { // scope limitation + +/** BitWriter - Allows writing of varying amounts of bits to a char buffer. <br> + * Very usefull for outputting variable bit length encodings such as Huffman. */ + + class BitWriter { + int bufferBits; /**< intermediary buffer of bits. */ + int bitsLeft; /**< number of bits left in the buffer. */ + unsigned char * currentByte; /**< position in memory the next char will be stored. */ + int bytesAvailable; /**< amount of available space left in the output buffer in bytes. Excludes the contents of bufferBits. */ + int bitsAvailable; /**< amount of available space left in the output buffer in bits. Includes the contents of bufferBits. */ + int maximumBytes; /**< total amount of bytes that can be written to the output buffer. */ + static int mask[]; /**< maps a number of bits to a bit mask containing as many bits. */ + static int intSize; /**< number of chars in an int. */ +public: + + /** Creates a new BitWriter. */ + BitWriter(); + + /** Creates a new BitWriter. + * @param output Destination that bits will be written to. + * @param max Maximum number of chars to output. */ + BitWriter( unsigned char * const output, int const &max ); + + /** Appends a char worth of bits to the buffer. + * @param bits the bits to append. + * @return true if successful, false if an error occurs. */ + bool put( unsigned char const &bits ); + + /** Appends a short worth of bits to the buffer. + * @param bits the bits to append. + * @return true if successful, false otherwise. + * @return true if successful, false if an error occurs. */ + bool put( short const &bits ); + + /** Appends an int worth of bits to the buffer. + * @param bits the bits to append. + * @return true if successful, false if an error occurs. */ + bool put( int const &bits ); + + /** Appends a specified number of bits from an int to the buffer. + * @param bits the bits to append. <br> + * The bits should be stored in the least significant portion of the int. + * @param count the number of bits to append. + * @return true if successful, false if an error occurs. */ + bool put( int const &bits, int count ); + + /** Appends multiple chars from a buffer to this BitWriter. + * @param inputBuffer pointer to char data + * @param count number of chars to read + * @return true if successful, false if an error occurs. */ + bool put( unsigned char const * const inputBuffer, int count ); + + /** Sets the output buffer that bytes will be written to. + * @param output Destination that bits will be written to. + * @param max Maximum number of chars to output. + * @return true if successful, false if an error occurs. */ + bool outputBuffer( unsigned char * const output, int const &max ); + + /** Writes any full chars of data stored in this BitWriter to the output char buffer. + * @return true if successful, false if an error occurs. */ + bool flush(); + + /** Flushes this BitWriter then outputs any partial chars by padding them with zeros. <br> + * After calling finish() all other calls to update the BitWriter will fail until a buffer is set via outputBuffer(). + * @param bytesWritten out: the number of bytes written to the output buffer. + * @param paddingBits out: the number of padding bits used in the final byte of output. + * @return true if successful, false if an error occurs. */ + bool finish( int &bytesWritten, int &paddingBits ); + + private: + + /** Initializes this BitWriter. */ + void init(); + + }; + +} +#endif +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/huffman/codec.h Fri May 15 20:13:36 2015 +0300 @@ -0,0 +1,70 @@ +/* + * skulltag::Codec class interface - Base class for data encoding or decoding operations. + * + * Copyright 2009 Timothy Landers + * email: code.vortexcortex@gmail.com + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. + */ + +#ifndef _CODEC_VERSION +#define _CODEC_VERSION 1 + +/** Prevents naming convention problems via encapsulation. */ +namespace skulltag { + + /** Huffman tree node -- used to represent a Huffman tree. <br> + * Huffman trees are use by compression / decompression codecs. */ + struct HuffmanNode { + int bitCount; /**< number of bits in the Huffman code. */ + int code; /**< bit representation of a Huffman code. */ + int value; /**< the value the Huffman code represents. */ + HuffmanNode * branch; /**< the left and right child branches or NULL (0) if leaf. */ + }; + +// Codec Class Interface + + /** Base class for encoding and decoding data. */ + class Codec { + + public: + + /** Decodes data read from an input buffer and stores the result in the output buffer. + * @return number of bytes stored in the output buffer or -1 if an error occurs while encoding. */ + virtual int encode( + unsigned char const * const input, /**< in: pointer to the first byte to encode. */ + unsigned char * const output, /**< out: pointer to an output buffer to store data. */ + int const &inLength, /**< in: number of bytes of input buffer to encoded. */ + int const &outLength /**< in: maximum length of data to output. */ + ) const = 0; + + /** Decodes data read from an input buffer and stores the result in the output buffer. + * @return number of bytes stored in the output buffer or -1 if an error occurs while decoding. */ + virtual int decode( + unsigned char const * const input, /**< in: pointer to data that needs decoding. */ + unsigned char * const output, /**< out: pointer to output buffer to store decoded data. */ + int const &inLength, /**< in: number of bytes of input buffer to read. */ + int const &outLength /**< in: maximum length of data to output. */ + ) = 0; + + }; // end class Codec + +}; // end namespace Codec + +#endif
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/huffman/huffcodec.cpp Fri May 15 20:13:36 2015 +0300 @@ -0,0 +1,329 @@ +/* + * skulltag::HuffmanCodec class - Huffman encoder and decoder. + * + * Copyright 2009 Timothy Landers + * email: code.vortexcortex@gmail.com + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. + */ + +#include "huffcodec.h" + +/** Prevents naming convention problems via encapsulation. */ +namespace skulltag { + +// HuffmanCodec Implementation + + /** Reverses the order of bits in a byte. + * EG: The statement <code>reverseMap[0xAF] == 0xF5</code> is <code>true</code>. <br> + * The index <code>10101111</code> stores the reverse value: <code>11110101</code>. <br> + * Note: One array lookup is much faster than Eight bit manipulating loop iterations. */ + unsigned char const HuffmanCodec::reverseMap[] = { + 0,128, 64,192, 32,160, 96,224, 16,144, 80,208, 48,176,112,240, + 8,136, 72,200, 40,168,104,232, 24,152, 88,216, 56,184,120,248, + 4,132, 68,196, 36,164,100,228, 20,148, 84,212, 52,180,116,244, + 12,140, 76,204, 44,172,108,236, 28,156, 92,220, 60,188,124,252, + 2,130, 66,194, 34,162, 98,226, 18,146, 82,210, 50,178,114,242, + 10,138, 74,202, 42,170,106,234, 26,154, 90,218, 58,186,122,250, + 6,134, 70,198, 38,166,102,230, 22,150, 86,214, 54,182,118,246, + 14,142, 78,206, 46,174,110,238, 30,158, 94,222, 62,190,126,254, + 1,129, 65,193, 33,161, 97,225, 17,145, 81,209, 49,177,113,241, + 9,137, 73,201, 41,169,105,233, 25,153, 89,217, 57,185,121,249, + 5,133, 69,197, 37,165,101,229, 21,149, 85,213, 53,181,117,245, + 13,141, 77,205, 45,173,109,237, 29,157, 93,221, 61,189,125,253, + 3,131, 67,195, 35,163, 99,227, 19,147, 83,211, 51,179,115,243, + 11,139, 75,203, 43,171,107,235, 27,155, 91,219, 59,187,123,251, + 7,135, 71,199, 39,167,103,231, 23,151, 87,215, 55,183,119,247, + 15,143, 79,207, 47,175,111,239, 31,159, 95,223, 63,191,127,255 + }; + + /** Creates a new HuffmanCodec + * @param treeData char array containing the tree data to use. + * @param dataLength number of chars in treeData. */ + HuffmanCodec::HuffmanCodec( + unsigned char const * const treeData, + int dataLength + ) : Codec() { + init(); + // init code table (256 pointers to Huffman Leaf Nodes.) + codeTable = new HuffmanNode*[256]; + for (int i = 0; i < 256; i++) codeTable[i] = 0; + // build root node + root = new HuffmanNode; + root->bitCount = 0; + root->code = 0; + root->value = -1; + // recursive Huffman tree builder. + buildTree( root, treeData, 0, dataLength, codeTable, 256 ); + huffResourceOwner = true; + } + + + /** Creates a new HuffmanCodec that uses the specified Huffman resources. + * @param treeRootNode The root node of a valid huffman tree. + * @param leafCodeTable A code lookup table where references to HuffmanNodes are stored with their array index equal to their value. + * Note: The tree nodes will not be released upon destruction of this HuffmanCodec. */ + HuffmanCodec::HuffmanCodec( + HuffmanNode * treeRootNode, + HuffmanNode ** leafCodeTable + ){ + init(); + // assign values -- no table building or allocations. + root = treeRootNode; + codeTable = leafCodeTable; + huffResourceOwner = false; + } + + /** Checks the ownership state of this HuffmanCodec's resources. + * @return true if the tree & code table will be released upon destruction of this HuffmanCodec. <br> + * A false return value means this HuffmanCodec is not responsible for deleting its resources. */ + bool HuffmanCodec::huffmanResourceOwner(){ + return huffResourceOwner; + } + + /** Perform initialization procedures common to all constructors. */ + void HuffmanCodec::init(){ + writer = new BitWriter(); + reverseBits = false; + expandable = true; + huffResourceOwner = false; + } + + /** Increases a codeLength up to the longest Huffman code bit length found in the node or any of its children. <br> + * Set to Zero before calling to determine maximum code bit length. + * @param node in: The node to begin searching at. + * @param codeLength out: Variable to hold the longest code bit length found. */ + void HuffmanCodec::maxCodeLength( HuffmanNode const * const node, int &codeLength ){ + // [TL] We must walk each tree node since the codeTable may not contain the set of all leaf nodes. + // bail on NULL node (tree is corrupt). + if ( node == 0) return; + // Recurse across children if they exist. + if ( node->branch != 0 ){ + maxCodeLength( &(node->branch[0]), codeLength ); + maxCodeLength( &(node->branch[1]), codeLength ); + } else if ( codeLength < node->bitCount ){ + // set codeLength if it's smaller than current node's bitCount. + codeLength = node->bitCount; + } + } + + /** Decreases a codeLength to the shortest Huffman code bit length found in the node or any of its children. <br> + * Set to Zero before calling to determine minimum code bit length. + * @param node in: The node to begin searching at. + * @param codeLength out: Variable to hold the longest code bit length found. */ + void HuffmanCodec::minCodeLength( HuffmanNode const * const node, int &codeLength ){ + /* [TL] Do not optimize under the assumption child nodes will have longer code Lengths! + * Future subclasses may have trees that diverge from Huffman specs. */ + // bail on NULL node (tree is corrupt). + if ( node == 0 ) return; + // Recurse across children if they exist. + if ( node->branch != 0 ){ + minCodeLength( &(node->branch[0]), codeLength ); + minCodeLength( &(node->branch[1]), codeLength ); + } else if ( (codeLength > node->bitCount) || (codeLength == 0) ) { + // set codeLength if it's Zero or larger than current node's bitCount. + codeLength = node->bitCount; + } + } + + /** Recursively builds a Huffman Tree. <br> + * The initial root node should have the following field values: <br> + * <pre> + * bitCount : 0 + * code : 0 + * value : -1 + * branch : 0 (NULL) + * </pre> + * @param node in/out: branch node of the Huffman Tree. + * @param treeData in: char array containing the Huffman Tree's byte representation. + * @param index in: Current array element to read the next tree node from. + * @param dataLength in: Length of treeData + * @param codeTable in/out: array of pointers to HuffmanNode structs. + * @param tableLength in: maximum index allowed in the codeTable. + * @return the next index to read from or -1 if an error occurs. + * */ + int HuffmanCodec::buildTree( + HuffmanNode * node, + unsigned char const * const treeData, + int index, + int dataLength, + HuffmanNode ** const &codeTable, + int tableLength + ){ + if ( index >= dataLength ) return -1; + // Read the branch description bit field + int desc = treeData[index]; + index++; + + // Create the array that will hold L/R child nodes of this branch. + node->branch = new HuffmanNode[2]; + + // Read the child Nodes for this branch. + for ( int i = 0; i < 2; i++ ){ + // Increase bit count, and update huffman code to match the node's tree position. + node->branch[i].bitCount = node->bitCount + 1; + node->branch[i].code = (node->code << 1) | i; // appends a 0 or 1 depending on L/R branch. + node->branch[i].value = -1; // default value. + + // Test a bit from the branch description (least significant bit == left) + if ( (desc & (1 << i)) == 0 ){ + // Child node is a branch; Recurse. + if ( (index = buildTree( &(node->branch[i]), treeData, index, dataLength, codeTable, tableLength )) < 0 ) return -1; + // This means the entire left sub tree will be read before the right sub tree gets read. + } else { + // Read leaf value and map its value/index in the nodes array. + if ( index >= dataLength ) return -1; + // set the nodes huffman code values. + node->branch[i].code = (node->code << 1) | i; + node->branch[i].bitCount = node->bitCount+1; + node->branch[i].value = treeData[index] & 0xff; + // NULL the child node's branch to mark it as a leaf. + node->branch[i].branch = 0; + // buffer overflow check. + if ( (node->branch[i].value >= 0) && (node->branch[i].value <= tableLength ) ) + // store a pointer to the leaf node into the code table at the location of its byte value. + codeTable[ node->branch[i].value ] = &node->branch[i]; + index++; + } + } + + return index; + } + + /** Decodes data read from an input buffer and stores the result in the output buffer. + * @return number of bytes stored in the output buffer or -1 if an error occurs while encoding. */ + int HuffmanCodec::encode( + unsigned char const * const input, /**< in: pointer to the first byte to encode. */ + unsigned char * const output, /**< out: pointer to an output buffer to store data. */ + int const &inLength, /**< in: number of bytes of input buffer to encoded. */ + int const &outLength /**< in: maximum length of data to output. */ + ) const { + // setup the bit buffer to output. if not expandable Limit output to input length. + if ( expandable ) writer->outputBuffer( output, outLength ); + else writer->outputBuffer( output, ((inLength + 1) < outLength) ? inLength + 1 : outLength ); + + writer->put( (unsigned char)0 ); // reserve place for padding signal. + + HuffmanNode * node; // temp ptr cache; + for ( int i = 0; i < inLength; i++ ){ + node = codeTable[ 0xff & input[i] ]; //lookup node + // Put the huffman code into the bit buffer and bail if error occurs. + if ( !writer->put( node->code, node->bitCount ) ) return -1; + } + int bytesWritten, padding; + if ( writer->finish( bytesWritten, padding ) ){ + // write padding signal byte to begining of stream. + output[0] = (unsigned char)padding; + } else return -1; + + // Reverse the bit order of each byte (Old Huffman Compatibility Mode) + if ( reverseBits ) for ( int i = 1; i < bytesWritten; i++ ){ + output[i] = reverseMap[ 0xff & output[i] ]; + } + + return bytesWritten; + } // end function encode + + /** Decodes data read from an input buffer and stores the result in the output buffer. + * @return number of bytes stored in the output buffer or -1 if an error occurs while decoding. */ + int HuffmanCodec::decode( + unsigned char const * const input, /**< in: pointer to data that needs decoding. */ + unsigned char * const output, /**< out: pointer to output buffer to store decoded data. */ + int const &inLength, /**< in: number of bytes of input buffer to read. */ + int const &outLength /**< in: maximum length of data to output. */ + ){ + if ( inLength < 1 ) return 0; + int bitsAvailable = ((inLength-1) << 3) - (0xff & input[0]); + int rIndex = 1; // read index of input buffer. + int wIndex = 0; // write index of output buffer. + char byte = 0; // bits of the current byte. + int bitsLeft = 0; // bits left in byte; + + HuffmanNode * node = root; + + // Traverse the tree, output values. + while ( (bitsAvailable > 0) && (node != 0) ){ + + // Get the next byte if we've run out. + if ( bitsLeft <= 0 ){ + byte = input[rIndex++]; + if ( reverseBits ) byte = reverseMap[ 0xff & byte ]; + bitsLeft = 8; + } + + // Traverse the tree according to the most significant bit. + node = &(node->branch[ ((byte >> 7) & 0x01) ]); + + // Is the node Non NULL, and a leaf? + if ( (node != 0) && (node->branch == 0) ){ + // buffer overflow prevention + if ( wIndex >= outLength ) return wIndex; + // Output leaf node's value and restart traversal at root node. + output[ wIndex++ ] = (unsigned char)(node->value & 0xff); + node = root; + } + + byte <<= 1; // cue up the next bit + bitsLeft--; // use up one bit of byte + bitsAvailable--; // decrement total bits left + } + + return wIndex; + } // end function decode + + /** Deletes all sub nodes of a HuffmanNode by traversing and deleting its child nodes. + * @param treeNode pointer to a HuffmanNode whos children will be deleted. */ + void HuffmanCodec::deleteTree( HuffmanNode * treeNode ){ + if ( treeNode == 0 ) return; + if ( treeNode->branch != 0 ){ + deleteTree( &(treeNode->branch[0]) ); + deleteTree( &(treeNode->branch[1]) ); + delete treeNode->branch; + } + } + + /** Destructor - frees resources. */ + HuffmanCodec::~HuffmanCodec() { + delete writer; + //check for resource ownership before deletion + if ( huffmanResourceOwner() ){ + delete codeTable; + deleteTree( root ); + delete root; + } + } + + /** Enables or Disables backwards bit ordering of bytes. + * @param backwards "true" enables reversed bit order bytes, "false" uses standard byte bit ordering. */ + void HuffmanCodec::reversedBytes( bool backwards ){ reverseBits = backwards; } + + /** Check the state of backwards bit ordering for bytes. + * @return true: bits within bytes are reversed. false: bits within bytes are normal. */ + bool HuffmanCodec::reversedBytes(){ return reverseBits; } + + /** Enable or Disable data expansion during encoding. + * @param expandingAllowed "true" allows encoding to expand data. "false" causes failure upon expansion. */ + void HuffmanCodec::allowExpansion( bool expandingAllowed ){ expandable = expandingAllowed; } + + /** Check the state of data expandability. + * @return true: data expansion is allowed. false: data is not allowed to expand. */ + bool HuffmanCodec::allowExpansion(){ return expandable; } + + +}; // end namespace skulltag
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/huffman/huffcodec.h Fri May 15 20:13:36 2015 +0300 @@ -0,0 +1,182 @@ +/* + * skulltag::HuffmanCodec class - Huffman encoder and decoder. + * + * Copyright 2009 Timothy Landers + * email: code.vortexcortex@gmail.com + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. + */ + +#ifndef _HUFFMAN_CODEC_VERSION +#define _HUFFMAN_CODEC_VERSION 1 +#define _HUFFMAN_CODEC_REV 0 + +#include "codec.h" +#include "bitwriter.h" +#include "bitreader.h" + +/** Prevents naming convention problems via encapsulation. */ +namespace skulltag { + + /** HuffmanCodec class - Encodes and Decodes data using a Huffman tree. */ + class HuffmanCodec : public Codec { + + /** top level node of the Huffman tree used for decoding. */ + HuffmanNode * root; + + /** table of Huffman codes and bit lengths used for encoding. */ + HuffmanNode ** codeTable; + + /** intermediary destination of huffman codes. */ + BitWriter * writer; + + /** When true this HuffmanCodec reverses its bytes after encoding and before decoding to + * provide compatibility with the backwards bit ordering of the original ST Huffman Encoding. + * Default value is "false" (do not reverse bits). */ + bool reverseBits; + + /** When false this HuffmanCodec return -1 instead of expanding data during encoding. + * Default value is "true" (allow data expansion). */ + bool expandable; + + /** Determines if this HuffmanCodec owns its Huffman tree nodes. */ + bool huffResourceOwner; + + /** Reverses the order of bits in a byte. + * EG: The statement <code>reverseMap[0xAF] == 0xF5</code> is <code>true</code>. <br> + * The index <code>10101111</code> stores the reverse value: <code>11110101</code>. <br> + * Note: One array lookup is much faster than Eight bit manipulating loop iterations. */ + static unsigned char const reverseMap[]; + + /** Number of bits the shortest huffman code in the tree has. */ + int shortestCode; + + public: + + /** Creates a new HuffmanCodec from the Huffman tree data. + * @param treeData pointer to a buffer containing the Huffman tree structure definition. + * @param dataLength length in bytes of the Huffman tree structure data. */ + HuffmanCodec( unsigned char const * const treeData, int dataLength ); + + /** Creates a new HuffmanCodec that uses the specified Huffman resources. + * @param treeRootNode The root node of a valid huffman tree. + * @param leafCodeTable A code lookup table where references to HuffmanNodes are stored with their array index equal to their value. + * Note: The tree nodes will not be released upon destruction of this HuffmanCodec. */ + HuffmanCodec( + HuffmanNode * treeRootNode, + HuffmanNode ** leafCodeTable + ); + + /** Frees resources used internally by this HuffmanCodec. */ + virtual ~HuffmanCodec(); + + /** Decodes data read from an input buffer and stores the result in the output buffer. + * @return number of bytes stored in the output buffer or -1 if an error occurs while encoding. */ + virtual int encode( + unsigned char const * const input, /**< in: pointer to the first byte to encode. */ + unsigned char * const output, /**< out: pointer to an output buffer to store data. */ + int const &inLength, /**< in: number of bytes of input buffer to encoded. */ + int const &outLength /**< in: maximum length of data to output. */ + ) const; + + /** Decodes data read from an input buffer and stores the result in the output buffer. + * @return number of bytes stored in the output buffer or -1 if an error occurs while decoding. */ + virtual int decode( + unsigned char const * const input, /**< in: pointer to data that needs decoding. */ + unsigned char * const output, /**< out: pointer to output buffer to store decoded data. */ + int const &inLength, /**< in: number of bytes of input buffer to read. */ + int const &outLength /**< in: maximum length of data to output. */ + ); + + /** Enables or Disables backwards bit ordering of bytes. + * @param backwards "true" enables reversed bit order bytes, "false" uses standard byte bit ordering. */ + void reversedBytes( bool backwards ); + + /** Check the state of backwards bit ordering for bytes. + * @return true: bits within bytes are reversed. false: bits within bytes are normal. */ + bool reversedBytes(); + + /** Enable or Disable data expansion during encoding. + * @param expandingAllowed "true" allows encoding to expand data. "false" causes failure upon expansion. */ + void allowExpansion( bool expandable ); + + /** Check the state of data expandability. + * @return true: data expansion is allowed. false: data is not allowed to expand. */ + bool allowExpansion(); + + /** Sets the ownership of this HuffmanCodec's resources. + * @param ownsResources When false the tree will not be released upon destruction of this HuffmanCodec. + * When true deleting this HuffmanCodec will cause the Huffman tree to be released. */ + void huffmanResourceOwner( bool ownsResources ); + + /** Checks the ownership state of this HuffmanCodec's resources. + * @return ownsResources When false the tree will not be released upon destruction of this HuffmanCodec. + * When true deleting this HuffmanCodec will cause the Huffman tree to be released. */ + bool huffmanResourceOwner(); + + /** Deletes all sub nodes of a HuffmanNode by traversing and deleting its child nodes. + * @param treeNode pointer to a HuffmanNode whos children will be deleted. */ + static void deleteTree( HuffmanNode * treeNode ); + + /** Recursively builds a Huffman Tree. <br> + * The initial root node should have the following field values: <br> + * <pre> + * bitCount : 0 + * code : 0 + * value : -1 + * branch : 0 (NULL) + * </pre> + * @param node in/out: branch node of the Huffman Tree. + * @param treeData in: char array containing the Huffman Tree's byte representation. + * @param index in: Current array element to read the next tree node from. + * @param dataLength in: Length of treeData + * @param codeTable in/out: array of pointers to HuffmanNode structs. + * @param tableLength in: maximum index allowed in the codeTable. + * @return the next index to read from or -1 if an error occurs. + * */ + int buildTree( + HuffmanNode * node, + unsigned char const * const treeData, + int index, + int dataLength, + HuffmanNode ** const &codeTable, + int tableLength + ); + + /** Decreases a codeLength to the shortest Huffman code bit length found in the node or any of its children. <br> + * Set to Zero before calling to determine minimum code bit length. + * @param node in: The node to begin searching at. + * @param codeLength out: Variable to hold the longest code bit length found. */ + static void minCodeLength( HuffmanNode const * const node, int &codeLength ); + + /** Increases a codeLength up to the longest Huffman code bit length found in the node or any of its children. <br> + * Set to Zero before calling to determine maximum code bit length. + * @param node in: The node to begin searching at. + * @param codeLength out: Variable to hold the longest code bit length found. */ + static void maxCodeLength( HuffmanNode const * const node, int &codeLength ); + + private: + + /** Perform initialization procedures common to all constructors. */ + void init(); + + }; // end class Huffman Codec. +} // end namespace skulltag + +#endif
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/huffman/huffman.cpp Fri May 15 20:13:36 2015 +0300 @@ -0,0 +1,159 @@ +/* + * Replacement for older Skulltag Launcher Protocol's huffman.cpp + * + * Copyright 2009 Timothy Landers + * email: code.vortexcortex@gmail.com + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. + */ + +// required for atexit() +#include <stdlib.h> +#include <stdio.h> + +#include "huffman.h" +#include "huffcodec.h" +// #include "i_system.h" + +using namespace skulltag; +// Global Variables + +/** Reference to the HuffmanCodec Object that will perform the encoding and decoding. */ +static HuffmanCodec * __codec = NULL; + +// Function Implementation + +/** Creates and intitializes a HuffmanCodec Object. <br> + * Also arranges for HUFFMAN_Destruct() to be called upon termination. */ +void HUFFMAN_Construct(){ + + // The exact structure description of a Huffman tree + static unsigned char const compatible_huffman_tree[] = { + 0, 0, 0, 1,128, 0, 0, 0, 3, 38, 34, 2, 1, 80, 3,110, + 144, 67, 0, 2, 1, 74, 3,243,142, 37, 2, 3,124, 58,182, 0, + 0, 1, 36, 0, 3,221,131, 3,245,163, 1, 35, 3,113, 85, 0, + 1, 41, 1, 77, 3,199,130, 0, 1,206, 3,185,153, 3, 70,118, + 0, 3, 3, 5, 0, 0, 1, 24, 0, 2, 3,198,190, 63, 2, 3, + 139,186, 75, 0, 1, 44, 2, 3,240,218, 56, 3, 40, 39, 0, 0, + 2, 2, 3,244,247, 81, 65, 0, 3, 9,125, 3, 68, 60, 0, 0, + 1, 25, 3,191,138, 3, 86, 17, 0, 1, 23, 3,220,178, 2, 3, + 165,194, 14, 1, 0, 2, 2, 0, 0, 2, 1,208, 3,150,157,181, + 1,222, 2, 3,216,230,211, 0, 2, 2, 3,252,141, 10, 42, 0, + 2, 3,134,135,104, 1,103, 3,187,225, 95, 32, 0, 0, 0, 0, + 0, 0, 1, 57, 1, 61, 3,183,237, 0, 0, 3,233,234, 3,246, + 203, 2, 3,250,147, 79, 1,129, 0, 1, 7, 3,143,136, 1, 20, + 3,179,148, 0, 0, 0, 3, 28,106, 3,101, 87, 1, 66, 0, 3, + 180,219, 3,227,241, 0, 1, 26, 1,251, 3,229,214, 3, 54, 69, + 0, 0, 0, 0, 0, 3,231,212, 3,156,176, 3, 93, 83, 0, 3, + 96,253, 3, 30, 13, 0, 0, 2, 3,175,254, 94, 3,159, 27, 2, + 1, 8, 3,204,226, 78, 0, 0, 0, 3,107, 88, 1, 31, 3,137, + 169, 2, 2, 3,215,145, 6, 4, 1,127, 0, 1, 99, 3,209,217, + 0, 3,213,238, 3,177,170, 1,132, 0, 0, 0, 2, 3, 22, 12, + 114, 2, 2, 3,158,197, 97, 45, 0, 1, 46, 1,112, 3,174,249, + 0, 3,224,102, 2, 3,171,151,193, 0, 0, 0, 3, 15, 16, 3, + 2,168, 1, 49, 3, 91,146, 0, 1, 48, 3,173, 29, 0, 3, 19, + 126, 3, 92,242, 0, 0, 0, 0, 0, 0, 3,205,192, 2, 3,235, + 149,255, 2, 3,223,184,248, 0, 0, 3,108,236, 3,111, 90, 2, + 3,117,115, 71, 0, 0, 3, 11, 50, 0, 3,188,119, 1,122, 3, + 167,162, 1,160, 1,133, 3,123, 21, 0, 0, 2, 1, 59, 2, 3, + 155,154, 98, 43, 0, 3, 76, 51, 2, 3,201,116, 72, 2, 0, 2, + 3,109,100,121, 2, 3,195,232, 18, 1, 0, 2, 0, 1,164, 2, + 3,120,189, 73, 0, 1,196, 3,239,210, 3, 64, 62, 89, 0, 0, + 1, 33, 2, 3,228,161, 55, 2, 3, 84,152, 47, 0, 0, 2, 3, + 207,172,140, 3, 82,166, 0, 3, 53,105, 1, 52, 3,202,200 + }; + + // create a HuffmanCodec that is compatible with the previous implementation. + __codec = new HuffmanCodec( compatible_huffman_tree, sizeof compatible_huffman_tree ); + + // set up the HuffmanCodec to perform in a backwards compatible fashion. + __codec->reversedBytes( true ); + __codec->allowExpansion( false ); + + // request that the destruct function be called upon exit. + // atterm( HUFFMAN_Destruct ); + atexit( HUFFMAN_Destruct ); +} + +/** Releases resources allocated by the HuffmanCodec. */ +void HUFFMAN_Destruct(){ + delete __codec; + __codec = NULL; +} + +/** Applies Huffman encoding to a block of data. */ +void HUFFMAN_Encode( + /** in: Pointer to start of data that is to be encoded. */ + unsigned char const * const inputBuffer, + /** out: Pointer to destination buffer where encoded data will be stored. */ + unsigned char * const outputBuffer, + /** in: Number of chars to read from inputBuffer. */ + int const &inputBufferSize, + /**< in+out: Max chars to write into outputBuffer. <br> + * Upon return holds the number of chars stored or 0 if an error occurs. */ + int * outputBufferSize +){ + int bytesWritten = __codec->encode( inputBuffer, outputBuffer, inputBufferSize, *outputBufferSize ); + + // expansion occured -- provide backwards compatibility + if ( bytesWritten < 0 ){ + // check buffer sizes + if ( *outputBufferSize < (inputBufferSize + 1) ){ + // outputBuffer too small, return "no bytes written" + *outputBufferSize = 0; + return; + } + + // perform the unencoded copy + for ( int i = 0; i < inputBufferSize; i++ ) outputBuffer[i+1] = inputBuffer[i]; + // supply the "unencoded" signal and bytesWritten + outputBuffer[0] = 0xff; + *outputBufferSize = inputBufferSize + 1; + } else { + // assign the bytesWritten return value + *outputBufferSize = bytesWritten; + } +} // end function HUFFMAN_Encode + +/** Decodes a block of data that is Huffman encoded. */ +void HUFFMAN_Decode( + unsigned char const * const inputBuffer, /**< in: Pointer to start of data that is to be decoded. */ + unsigned char * const outputBuffer, /**< out: Pointer to destination buffer where decoded data will be stored. */ + int const &inputBufferSize, /**< in: Number of chars to read from inputBuffer. */ + int *outputBufferSize /**< in+out: Max chars to write into outputBuffer. Upon return holds the number of chars stored or 0 if an error occurs. */ +){ + // check for "unencoded" signal & provide backwards compatibility + if ((inputBufferSize > 0) && ((inputBuffer[0]&0xff) == 0xff)){ + // check buffer sizes + if ( *outputBufferSize < (inputBufferSize - 1) ){ + // outputBuffer too small, return "no bytes written" + *outputBufferSize = 0; + return; + } + + // perform the unencoded copy + for ( int i = 1; i < inputBufferSize; i++ ) outputBuffer[i-1] = inputBuffer[i]; + + // supply the bytesWritten + *outputBufferSize = inputBufferSize - 1; + } else { + // decode the data + *outputBufferSize = __codec->decode( inputBuffer, outputBuffer, inputBufferSize, *outputBufferSize ); + } +} // end function HUFFMAN_Decode
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/huffman/huffman.h Fri May 15 20:13:36 2015 +0300 @@ -0,0 +1,55 @@ +/* + * Replacement for older Skulltag Launcher Protocol's huffman.cpp + * + * Copyright 2009 Timothy Landers + * email: code.vortexcortex@gmail.com + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. + */ + +//Macro name kept for backwards compatibility. +#ifndef __HUFFMAN_H__ +#define __HUFFMAN_H__ + +#include "huffcodec.h" + +/** Creates and intitializes a HuffmanCodec Object. <br> + * Also arranges for HUFFMAN_Destruct() to be called upon termination. */ +void HUFFMAN_Construct(); + +/** Releases resources allocated by the HuffmanCodec. */ +void HUFFMAN_Destruct(); + +/** Applies Huffman encoding to a block of data. */ +void HUFFMAN_Encode( + unsigned char const * const inputBuffer, /**< in: Pointer to start of data that is to be encoded. */ + unsigned char * const outputBuffer, /**< out: Pointer to destination buffer where encoded data will be stored. */ + int const &inputBufferSize, /**< in: Number of chars to read from inputBuffer. */ + int *outputBufferSize /**< in+out: Max chars to write into outputBuffer. Upon return holds the number of chars stored or 0 if an error occurs. */ +); + +/** Decodes a block of data that is Huffman encoded. */ +void HUFFMAN_Decode( + unsigned char const * const inputBuffer, /**< in: Pointer to start of data that is to be decoded. */ + unsigned char * const outputBuffer, /**< out: Pointer to destination buffer where decoded data will be stored. */ + int const &inputBufferSize, /**< in: Number of chars to read from inputBuffer. */ + int *outputBufferSize /**< in+out: Max chars to write into outputBuffer. Upon return holds the number of chars stored or 0 if an error occurs. */ +); + +#endif // __HUFFMAN_H__
--- a/sources/huffman/bitreader.cpp Fri May 15 20:10:44 2015 +0300 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,144 +0,0 @@ -/* - * skulltag::BitReader class - Allows reading arbitrary bit lengths of data. - * Version 1 - Revsion 0 - * - * Copyright 2009 Timothy Landers - * email: code.vortexcortex@gmail.com - * - * Permission is hereby granted, free of charge, to any person obtaining a copy - * of this software and associated documentation files (the "Software"), to deal - * in the Software without restriction, including without limitation the rights - * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell - * copies of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice shall be included in - * all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE - * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, - * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN - * THE SOFTWARE. - */ - -#include "bitreader.h" -/** Prevents naming convention problems via encapsulation. */ -namespace skulltag { - // BitReader class implementation - - int BitReader::intBitSize = 0; - int BitReader::intSize = 0; - int BitReader::mask[32] = {0}; - - /** Creates a new BitReader. */ - BitReader::BitReader(){ - init(); - } - - /** Creates a new BitReader. - * @param input Source of data that bits will be read from. - * @param max Maximum number of chars to read. */ - BitReader::BitReader( unsigned char const * input, int const &max ){ - inputBuffer( input, max ); - } - - /** Sets the input buffer that bytes will be read from. - * @param input Source of data that bits will be read from. - * @param max Maximum number of chars to input. - * @return true if successful, false if an error occurs. */ - bool BitReader::inputBuffer( unsigned char const * input, int const &max ){ - init(); // zero the vars. - currentByte = input; - if ( input == 0 ) return false; - if ( max < 1 ) return false; - bytesAvailable = max; - bitsAvailable = max << 3; - maximumBytes = max; - return true; - } - - /** Initializes this BitReader */ - void BitReader::init(){ - // initialize static variables if not initialized yet. - if ( intSize == 0 ){ - intSize = sizeof maximumBytes; - mask[0] = 0; - - // fill mask such that m = { 0, 1, 3, 7, 15, etc. } - for ( int i = 1; i < 32; i++ ) mask[i] = (mask[i-1] << 1) | 1; - - intBitSize = intSize << 3; - } - - // initialize member variables. - bitsAvailable = 0; - bytesAvailable = 0; - bufferBits = 0; - currentByte = 0; - maximumBytes = 0; - bitsUsed = 0; - } - - /** Fills the internal bit buffer. - * @return true if successful, false if an error occurs. */ - bool BitReader::fill(){ - if ( (currentByte == 0) || (bytesAvailable <= 0) ) return false; - - // while there's at least one octet free in the buffer, and one byte to read. - while ( (bitsUsed < (intBitSize - 8)) && (bytesAvailable > 0) ){ - - // put a byte into the bottom end of the buffer. - bufferBits |= (*currentByte & mask[8]) << (intBitSize - bitsUsed - 8); - - // Set variables to reflect the change. - currentByte++; - bytesAvailable--; - bitsUsed += 8; - } - return true; - } - - /** Fetches a specified number of bits and stores them in an int. - * @param bits destination of the retrieved bits. <br> - * The bits will be stored in the least significant portion of the int. - * @param count the number of bits to fetch. - * @return the number of bits read -- may not be equal to the amount requested. */ - int BitReader::get( int &bits, int const &count ){ - bits = 0; - // Requesting more bits than are available. - if ( count > bitsAvailable ) return 0; - if ( (count > bitsUsed) && (!fill()) ) return 0; - bits = (bufferBits >> (intBitSize - count)) & mask[count]; - // lesser of bits in buffer or requested bits. - int got = (bitsUsed < count) ? bitsUsed : count; - // get as many bits from the buffer as we can. - if ( got > 0 ){ - bufferBits <<= got; - bitsUsed -= got; - bitsAvailable -= got; - } - // if more bits are requested. - if ( count > got ){ - if (!fill()) { - bits = (bits >> (count - got)) & mask[count - got]; - return got; - } - got = count - got; - // avoid reading more bits than available. - if ( got <= bitsAvailable ){ - bits |= (bufferBits >> (intBitSize - got)) & mask[got]; - bufferBits <<= got; - bitsUsed -= got; - bitsAvailable -= got; - } - } - return count; - } - - /** @return Amount of bits that can be read from this BitReader. */ - int BitReader::availableBits(){ return bitsAvailable; } - -} // end namespace skulltag
--- a/sources/huffman/bitreader.h Fri May 15 20:10:44 2015 +0300 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,85 +0,0 @@ -/** - * skulltag::BitReader class - Allows reading arbitrary bit lengths of data. - * Version 1 - Revsion 0 - * - * Copyright 2009 Timothy Landers - * email: code.vortexcortex@gmail.com - * - * Permission is hereby granted, free of charge, to any person obtaining a copy - * of this software and associated documentation files (the "Software"), to deal - * in the Software without restriction, including without limitation the rights - * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell - * copies of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice shall be included in - * all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE - * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, - * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN - * THE SOFTWARE. - */ - -#ifndef _BIT_READER_VERSION -#define _BIT_READER_VERSION 1 - -/** Prevents naming convention problems via encapsulation. */ -namespace skulltag { // scope limitation - -/** BitReader - Allows reading of varying amounts of bits from a char buffer. <br> - * Very usefull for inputting variable bit length encodings such as Huffman. */ - - class BitReader { - int bufferBits; /**< intermediary buffer of bits. */ - int bitsUsed; /**< number of bits used in the buffer. */ - unsigned char const * currentByte; /**< position in memory the next char will be read. */ - int bytesAvailable; /**< amount of available space left in the input buffer in bytes. Excludes the contents of bufferBits. */ - int bitsAvailable; /**< amount of available space left in the input buffer in bits. Includes the contents of bufferBits. */ - int maximumBytes; /**< total amount of bytes that can be read from the input buffer. */ - static int mask[]; /**< maps a number of bits to a bit mask containing as many bits. */ - static int intSize; /**< number of chars in an int. */ - static int intBitSize; /**< number of bits in an ing. */ -public: - - /** Creates a new BitReader. */ - BitReader(); - - /** Creates a new BitReader. - * @param input Source of data that bits will be read from. - * @param max Maximum number of chars to read. */ - BitReader( unsigned char const * input, int const &max ); - - /** Sets the input buffer that bytes will be read from. - * @param input Source of data that bits will be read from. - * @param max Maximum number of chars to input. - * @return true if successful, false if an error occurs. */ - bool inputBuffer( unsigned char const * input, int const &max ); - - /** Fetches a specified number of bits and stores them in an int. - * @param bits destination of the retrieved bits. <br> - * The bits will be stored in the least significant portion of the int. - * @param count the number of bits to fetch. - * @return the number of bits read -- may not be equal to the amount requested. */ - int get( int &bits, int const &count ); - - /** @return Amount of bits that can be read from this BitReader. */ - int availableBits(); - - private: - - /** Fills the internal bit buffer. - * @return true if successful, false if an error occurs. */ - bool fill(); - - /** Initializes this BitReader. */ - void init(); - - }; - -} -#endif -
--- a/sources/huffman/bitwriter.cpp Fri May 15 20:10:44 2015 +0300 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,271 +0,0 @@ -/* - * skulltag::BitWriter class - Enables writing arbitrary bit lengths of data. - * - * Copyright 2009 Timothy Landers - * email: code.vortexcortex@gmail.com - * - * Permission is hereby granted, free of charge, to any person obtaining a copy - * of this software and associated documentation files (the "Software"), to deal - * in the Software without restriction, including without limitation the rights - * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell - * copies of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice shall be included in - * all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE - * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, - * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN - * THE SOFTWARE. - */ - -#include "bitwriter.h" - -/* The internal buffer of bits is an int which is initiallized to zero. - * The Bit Buffer: [00000000000000000000000000000000] - 0 bits stored. - * - * Bits stored in the bit buffer occupy the most significant bits available. - * When bits are stored their order is preserved. - * Storing the 5 bits 01011 into the bit buffer would result in: - * The Bit Buffer: [01011000000000000000000000000000] - 5 bits stored. - * - * Additionally storing 0x12f3 (13 bits) would result in: - * The Bit Buffer: [01011100101111001100000000000000] - 18 bits stored. - * - * Data is stored via any of the put(...) functions. - * - * To retrieve bytes (chars) of data from the bit buffer and empty the bit buffer: flush(); - * Flushing the bit buffer takes groups of 8 bits (octets) and stores them in the - * output buffer at the current byte position. Calling flush() would cause output - * to receive 2 bytes (0x5c, 0xbc) == (01011100, 10111100) and the remaining bits would - * be moved to the most significant bit positions. - * The Bit Buffer: [11000000000000000000000000000000] - 2 bits stored. - * Note: The empty bits of the bit buffer must be zero to avoid additional masking operations. - * flush() is called automatically if the bit buffer is too full during a call to put(...) - * - * When the bit storage operation is complete call finish(...). Finish will flush as many full - * bytes of data into the output buffer as possible, the remaining bits will be padded out - * to a full octet with zeros (on their less significant side), then written to the output - * buffer. finish( bytesStored, padding ) passes by reference the number of bytes stored - * and number of padding bits added (0 to 7) to the last stored byte. - * - * Bits are not added one at a time, they are masked, shifted and bitwise OR'ed into - * the buffer in as large a group as possible. This allows the BitWriter to add multiple bits in a single - * operation instead of calling a function for each 1 bit added. - * - * Normal usage: - * - * char * dataArray = new char[ max_output_size ]; - * BitWriter * buffer = new BitWriter( dataArray, max_output_size ); - * ... - * // various calls to put(...); - * ... - * int numBytesOutput, paddedBits; - * buffer->finish( numBytesOutput, paddedBits ); - * ... - * // do something with dataArray - * ... - * delete buffer; - * delete dataArray; - * - * */ - -/** Prevents naming convention problems via encapsulation. */ -namespace skulltag { - - // Static variable initially set to zero as a signal for init() - int BitWriter::intSize = 0; - int BitWriter::mask[32]; - - /** Initializes this BitWriter. */ - void BitWriter::init(){ - - // initialize static variables if not initialized yet. - if ( intSize == 0 ){ - intSize = sizeof maximumBytes; - mask[0] = 0; - - // fill mask such that m = { 0, 1, 3, 7, 15, etc. } - for ( int i = 1; i < 32; i++ ) mask[i] = (mask[i-1] << 1) | 1; - } - - // initialize member variables. - bitsAvailable = 0; - bytesAvailable = 0; - bufferBits = 0; - currentByte = 0; - maximumBytes = 0; - bitsLeft = intSize << 3; - } - - /** Creates a new BitWriter. */ - BitWriter::BitWriter(){ - init(); - } - - /** Creates a new BitWriter. - * @param output Destination that bits will be written to. - * @param max Maximum number of chars to output. */ - BitWriter::BitWriter( unsigned char * const output, int const &max ){ - outputBuffer( output, max ); - } - - /** Sets the output buffer that bytes will be written to. - * @param output Destination that bits will be written to. - * @param max Maximum number of chars to output. - * @return true if successful, false otherwise. */ - bool BitWriter::outputBuffer( unsigned char * const output, int const &max ){ - init(); // zero the vars. - currentByte = output; - if ( output == 0 ) return false; - if ( max < 1 ) return false; - bytesAvailable = max; - bitsAvailable = max << 3; - maximumBytes = max; - return true; - } - - /** Appends a char worth of bits to the buffer. - * @param bits the bits to append. - * @return true if successful, false otherwise. */ - bool BitWriter::put( unsigned char const &bits ){ - return put( (int)bits, 8 ); - } - - /** Appends a short worth of bits to the buffer. - * @param bits the bits to append. - * @return true if successful, false otherwise. */ - bool BitWriter::put( short const &bits ){ - static int shortBitSize = (sizeof bits) << 3; - return put( (int)bits, shortBitSize ); - } - /** Appends an int worth of bits to the buffer. - * @param bits the bits to append. - * @return true if successful, false otherwise. */ - bool BitWriter::put( int const &bits ){ - static int intBitSize = intSize << 3; - return put( bits, intBitSize); - } - - /** Appends multiple chars from a buffer to this BitWriter. - * @param inputBuffer pointer to char data - * @param count number of chars to read - * @return true if successful, false otherwise. */ - bool BitWriter::put( unsigned char const * const inputBuffer, int count ){ - int i = 0; - - // Read in 4 bytes at a time and send all at once to the bit buffer. - while ( (i + 3) < count ){ - if ( !put( - ((int)inputBuffer[ i ] << 24) | - ((int)inputBuffer[i+1] << 16) | - ((int)inputBuffer[i+2] << 8) | - (int)inputBuffer[i+3], 32 - ) ) return false; - i+=4; - } - - // If any bytes remain, output them one at a time. - while ( i < count ){ - if ( !put( (int)inputBuffer[ i ], 8 ) ) return false; - i++; - } - - return true; - } - - /** Appends a specified number of bits from an int to the buffer. - * @param bits the bits to append. <br> - * The bits should be stored in the least significant portion of the int. - * @param count the number of bits to append. - * @return true if successful, false otherwise. */ - bool BitWriter::put( int const &bits, int count ){ - if ( count > bitsAvailable ) return false; - if ( (bitsLeft < 1) && (!flush()) ) return false; - if ( count > bitsLeft ){ - // not enough space in buffer, fill buffer with top end of input bits then flush. - bufferBits |= mask[bitsLeft] & (bits >> (count - bitsLeft)); - count -= bitsLeft; - bitsAvailable -= bitsLeft; - bitsLeft = 0; - - // Buffer's full, needs flushing. - if (!flush()) return false; - } - - // if there are still bits of input... - if ( count > 0 ){ - - // shift the input bits up to the end of the bit buffer. - bufferBits |= (mask[count] & bits) << (bitsLeft - count); - bitsAvailable -= count; - bitsLeft -= count; - } - return true; - } - - /** Writes any full chars of data stored in this BitWriter to the output char buffer. - * @return true if successful, false if an error occurs. */ - bool BitWriter::flush(){ - // static var to hold how many bits are in an int. - static int intBitSize = intSize << 3; - if ( currentByte == 0 ) return false; - int numBits = intBitSize - bitsLeft; - - // while there's at least one octet of data in the buffer. - while ( numBits > 7 ){ - - // fail if no bytes can be written. - if ( bytesAvailable <= 0 ) return false; - - // get a byte off the top end of the buffer. - *currentByte = (bufferBits >> (intBitSize - 8)) & mask[8]; - - // Set variables to reflect the change. - currentByte++; - bytesAvailable--; - bufferBits = bufferBits << 8; - bitsLeft += 8; - numBits -= 8; - } - return true; - } - - /** Flushes this BitWriter then outputs any partial chars by padding them with zeros. <br> - * After calling finish() all other calls to update the BitWriter will fail until a buffer is set via outputBuffer(). - * @param bytesWritten out: the number of bytes written to the output buffer. - * @param paddingBits out: the number of padding bits used in the final byte of output. - * @return true if successful, false if an error occurs. */ - bool BitWriter::finish( int &bytesWritten, int &paddingBits ){ - static int intBitSize = intSize << 3; - // set meaningful return values even if flush() fails. - bytesWritten = maximumBytes - bytesAvailable; - paddingBits = 0; - if ( flush() ){ - // use a temp var to avoid setting paddingBits to invalid value on failure. - int pad = (8 - (intBitSize - bitsLeft)) & 7; - if ( pad > 0 ){ - // all empty bits should be zero. Artificially extend by the number of bits needed. - bitsLeft -= pad; - if ( !flush() ){ - // Prevent futher use even on failure. - init(); - return false; - } - // return the temp bit padding value. - paddingBits = pad; - } - bytesWritten = maximumBytes - bytesAvailable; - init(); // set initial state -- no further writing can occur. - return true; - } - // Prevents futher use even on failure. - init(); - return false; - } - -}
--- a/sources/huffman/bitwriter.h Fri May 15 20:10:44 2015 +0300 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,109 +0,0 @@ -/* - * skulltag::BitWriter class - Enables writing arbitrary bit lengths of data. - * - * Copyright 2009 Timothy Landers - * email: code.vortexcortex@gmail.com - * - * Permission is hereby granted, free of charge, to any person obtaining a copy - * of this software and associated documentation files (the "Software"), to deal - * in the Software without restriction, including without limitation the rights - * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell - * copies of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice shall be included in - * all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE - * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, - * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN - * THE SOFTWARE. - */ - -#ifndef _BIT_WRITER_VERSION -#define _BIT_WRITER_VERSION 1 - -/** Prevents naming convention problems via encapsulation. */ -namespace skulltag { // scope limitation - -/** BitWriter - Allows writing of varying amounts of bits to a char buffer. <br> - * Very usefull for outputting variable bit length encodings such as Huffman. */ - - class BitWriter { - int bufferBits; /**< intermediary buffer of bits. */ - int bitsLeft; /**< number of bits left in the buffer. */ - unsigned char * currentByte; /**< position in memory the next char will be stored. */ - int bytesAvailable; /**< amount of available space left in the output buffer in bytes. Excludes the contents of bufferBits. */ - int bitsAvailable; /**< amount of available space left in the output buffer in bits. Includes the contents of bufferBits. */ - int maximumBytes; /**< total amount of bytes that can be written to the output buffer. */ - static int mask[]; /**< maps a number of bits to a bit mask containing as many bits. */ - static int intSize; /**< number of chars in an int. */ -public: - - /** Creates a new BitWriter. */ - BitWriter(); - - /** Creates a new BitWriter. - * @param output Destination that bits will be written to. - * @param max Maximum number of chars to output. */ - BitWriter( unsigned char * const output, int const &max ); - - /** Appends a char worth of bits to the buffer. - * @param bits the bits to append. - * @return true if successful, false if an error occurs. */ - bool put( unsigned char const &bits ); - - /** Appends a short worth of bits to the buffer. - * @param bits the bits to append. - * @return true if successful, false otherwise. - * @return true if successful, false if an error occurs. */ - bool put( short const &bits ); - - /** Appends an int worth of bits to the buffer. - * @param bits the bits to append. - * @return true if successful, false if an error occurs. */ - bool put( int const &bits ); - - /** Appends a specified number of bits from an int to the buffer. - * @param bits the bits to append. <br> - * The bits should be stored in the least significant portion of the int. - * @param count the number of bits to append. - * @return true if successful, false if an error occurs. */ - bool put( int const &bits, int count ); - - /** Appends multiple chars from a buffer to this BitWriter. - * @param inputBuffer pointer to char data - * @param count number of chars to read - * @return true if successful, false if an error occurs. */ - bool put( unsigned char const * const inputBuffer, int count ); - - /** Sets the output buffer that bytes will be written to. - * @param output Destination that bits will be written to. - * @param max Maximum number of chars to output. - * @return true if successful, false if an error occurs. */ - bool outputBuffer( unsigned char * const output, int const &max ); - - /** Writes any full chars of data stored in this BitWriter to the output char buffer. - * @return true if successful, false if an error occurs. */ - bool flush(); - - /** Flushes this BitWriter then outputs any partial chars by padding them with zeros. <br> - * After calling finish() all other calls to update the BitWriter will fail until a buffer is set via outputBuffer(). - * @param bytesWritten out: the number of bytes written to the output buffer. - * @param paddingBits out: the number of padding bits used in the final byte of output. - * @return true if successful, false if an error occurs. */ - bool finish( int &bytesWritten, int &paddingBits ); - - private: - - /** Initializes this BitWriter. */ - void init(); - - }; - -} -#endif -
--- a/sources/huffman/codec.h Fri May 15 20:10:44 2015 +0300 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,70 +0,0 @@ -/* - * skulltag::Codec class interface - Base class for data encoding or decoding operations. - * - * Copyright 2009 Timothy Landers - * email: code.vortexcortex@gmail.com - * - * Permission is hereby granted, free of charge, to any person obtaining a copy - * of this software and associated documentation files (the "Software"), to deal - * in the Software without restriction, including without limitation the rights - * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell - * copies of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice shall be included in - * all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE - * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, - * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN - * THE SOFTWARE. - */ - -#ifndef _CODEC_VERSION -#define _CODEC_VERSION 1 - -/** Prevents naming convention problems via encapsulation. */ -namespace skulltag { - - /** Huffman tree node -- used to represent a Huffman tree. <br> - * Huffman trees are use by compression / decompression codecs. */ - struct HuffmanNode { - int bitCount; /**< number of bits in the Huffman code. */ - int code; /**< bit representation of a Huffman code. */ - int value; /**< the value the Huffman code represents. */ - HuffmanNode * branch; /**< the left and right child branches or NULL (0) if leaf. */ - }; - -// Codec Class Interface - - /** Base class for encoding and decoding data. */ - class Codec { - - public: - - /** Decodes data read from an input buffer and stores the result in the output buffer. - * @return number of bytes stored in the output buffer or -1 if an error occurs while encoding. */ - virtual int encode( - unsigned char const * const input, /**< in: pointer to the first byte to encode. */ - unsigned char * const output, /**< out: pointer to an output buffer to store data. */ - int const &inLength, /**< in: number of bytes of input buffer to encoded. */ - int const &outLength /**< in: maximum length of data to output. */ - ) const = 0; - - /** Decodes data read from an input buffer and stores the result in the output buffer. - * @return number of bytes stored in the output buffer or -1 if an error occurs while decoding. */ - virtual int decode( - unsigned char const * const input, /**< in: pointer to data that needs decoding. */ - unsigned char * const output, /**< out: pointer to output buffer to store decoded data. */ - int const &inLength, /**< in: number of bytes of input buffer to read. */ - int const &outLength /**< in: maximum length of data to output. */ - ) = 0; - - }; // end class Codec - -}; // end namespace Codec - -#endif
--- a/sources/huffman/huffcodec.cpp Fri May 15 20:10:44 2015 +0300 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,329 +0,0 @@ -/* - * skulltag::HuffmanCodec class - Huffman encoder and decoder. - * - * Copyright 2009 Timothy Landers - * email: code.vortexcortex@gmail.com - * - * Permission is hereby granted, free of charge, to any person obtaining a copy - * of this software and associated documentation files (the "Software"), to deal - * in the Software without restriction, including without limitation the rights - * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell - * copies of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice shall be included in - * all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE - * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, - * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN - * THE SOFTWARE. - */ - -#include "huffcodec.h" - -/** Prevents naming convention problems via encapsulation. */ -namespace skulltag { - -// HuffmanCodec Implementation - - /** Reverses the order of bits in a byte. - * EG: The statement <code>reverseMap[0xAF] == 0xF5</code> is <code>true</code>. <br> - * The index <code>10101111</code> stores the reverse value: <code>11110101</code>. <br> - * Note: One array lookup is much faster than Eight bit manipulating loop iterations. */ - unsigned char const HuffmanCodec::reverseMap[] = { - 0,128, 64,192, 32,160, 96,224, 16,144, 80,208, 48,176,112,240, - 8,136, 72,200, 40,168,104,232, 24,152, 88,216, 56,184,120,248, - 4,132, 68,196, 36,164,100,228, 20,148, 84,212, 52,180,116,244, - 12,140, 76,204, 44,172,108,236, 28,156, 92,220, 60,188,124,252, - 2,130, 66,194, 34,162, 98,226, 18,146, 82,210, 50,178,114,242, - 10,138, 74,202, 42,170,106,234, 26,154, 90,218, 58,186,122,250, - 6,134, 70,198, 38,166,102,230, 22,150, 86,214, 54,182,118,246, - 14,142, 78,206, 46,174,110,238, 30,158, 94,222, 62,190,126,254, - 1,129, 65,193, 33,161, 97,225, 17,145, 81,209, 49,177,113,241, - 9,137, 73,201, 41,169,105,233, 25,153, 89,217, 57,185,121,249, - 5,133, 69,197, 37,165,101,229, 21,149, 85,213, 53,181,117,245, - 13,141, 77,205, 45,173,109,237, 29,157, 93,221, 61,189,125,253, - 3,131, 67,195, 35,163, 99,227, 19,147, 83,211, 51,179,115,243, - 11,139, 75,203, 43,171,107,235, 27,155, 91,219, 59,187,123,251, - 7,135, 71,199, 39,167,103,231, 23,151, 87,215, 55,183,119,247, - 15,143, 79,207, 47,175,111,239, 31,159, 95,223, 63,191,127,255 - }; - - /** Creates a new HuffmanCodec - * @param treeData char array containing the tree data to use. - * @param dataLength number of chars in treeData. */ - HuffmanCodec::HuffmanCodec( - unsigned char const * const treeData, - int dataLength - ) : Codec() { - init(); - // init code table (256 pointers to Huffman Leaf Nodes.) - codeTable = new HuffmanNode*[256]; - for (int i = 0; i < 256; i++) codeTable[i] = 0; - // build root node - root = new HuffmanNode; - root->bitCount = 0; - root->code = 0; - root->value = -1; - // recursive Huffman tree builder. - buildTree( root, treeData, 0, dataLength, codeTable, 256 ); - huffResourceOwner = true; - } - - - /** Creates a new HuffmanCodec that uses the specified Huffman resources. - * @param treeRootNode The root node of a valid huffman tree. - * @param leafCodeTable A code lookup table where references to HuffmanNodes are stored with their array index equal to their value. - * Note: The tree nodes will not be released upon destruction of this HuffmanCodec. */ - HuffmanCodec::HuffmanCodec( - HuffmanNode * treeRootNode, - HuffmanNode ** leafCodeTable - ){ - init(); - // assign values -- no table building or allocations. - root = treeRootNode; - codeTable = leafCodeTable; - huffResourceOwner = false; - } - - /** Checks the ownership state of this HuffmanCodec's resources. - * @return true if the tree & code table will be released upon destruction of this HuffmanCodec. <br> - * A false return value means this HuffmanCodec is not responsible for deleting its resources. */ - bool HuffmanCodec::huffmanResourceOwner(){ - return huffResourceOwner; - } - - /** Perform initialization procedures common to all constructors. */ - void HuffmanCodec::init(){ - writer = new BitWriter(); - reverseBits = false; - expandable = true; - huffResourceOwner = false; - } - - /** Increases a codeLength up to the longest Huffman code bit length found in the node or any of its children. <br> - * Set to Zero before calling to determine maximum code bit length. - * @param node in: The node to begin searching at. - * @param codeLength out: Variable to hold the longest code bit length found. */ - void HuffmanCodec::maxCodeLength( HuffmanNode const * const node, int &codeLength ){ - // [TL] We must walk each tree node since the codeTable may not contain the set of all leaf nodes. - // bail on NULL node (tree is corrupt). - if ( node == 0) return; - // Recurse across children if they exist. - if ( node->branch != 0 ){ - maxCodeLength( &(node->branch[0]), codeLength ); - maxCodeLength( &(node->branch[1]), codeLength ); - } else if ( codeLength < node->bitCount ){ - // set codeLength if it's smaller than current node's bitCount. - codeLength = node->bitCount; - } - } - - /** Decreases a codeLength to the shortest Huffman code bit length found in the node or any of its children. <br> - * Set to Zero before calling to determine minimum code bit length. - * @param node in: The node to begin searching at. - * @param codeLength out: Variable to hold the longest code bit length found. */ - void HuffmanCodec::minCodeLength( HuffmanNode const * const node, int &codeLength ){ - /* [TL] Do not optimize under the assumption child nodes will have longer code Lengths! - * Future subclasses may have trees that diverge from Huffman specs. */ - // bail on NULL node (tree is corrupt). - if ( node == 0 ) return; - // Recurse across children if they exist. - if ( node->branch != 0 ){ - minCodeLength( &(node->branch[0]), codeLength ); - minCodeLength( &(node->branch[1]), codeLength ); - } else if ( (codeLength > node->bitCount) || (codeLength == 0) ) { - // set codeLength if it's Zero or larger than current node's bitCount. - codeLength = node->bitCount; - } - } - - /** Recursively builds a Huffman Tree. <br> - * The initial root node should have the following field values: <br> - * <pre> - * bitCount : 0 - * code : 0 - * value : -1 - * branch : 0 (NULL) - * </pre> - * @param node in/out: branch node of the Huffman Tree. - * @param treeData in: char array containing the Huffman Tree's byte representation. - * @param index in: Current array element to read the next tree node from. - * @param dataLength in: Length of treeData - * @param codeTable in/out: array of pointers to HuffmanNode structs. - * @param tableLength in: maximum index allowed in the codeTable. - * @return the next index to read from or -1 if an error occurs. - * */ - int HuffmanCodec::buildTree( - HuffmanNode * node, - unsigned char const * const treeData, - int index, - int dataLength, - HuffmanNode ** const &codeTable, - int tableLength - ){ - if ( index >= dataLength ) return -1; - // Read the branch description bit field - int desc = treeData[index]; - index++; - - // Create the array that will hold L/R child nodes of this branch. - node->branch = new HuffmanNode[2]; - - // Read the child Nodes for this branch. - for ( int i = 0; i < 2; i++ ){ - // Increase bit count, and update huffman code to match the node's tree position. - node->branch[i].bitCount = node->bitCount + 1; - node->branch[i].code = (node->code << 1) | i; // appends a 0 or 1 depending on L/R branch. - node->branch[i].value = -1; // default value. - - // Test a bit from the branch description (least significant bit == left) - if ( (desc & (1 << i)) == 0 ){ - // Child node is a branch; Recurse. - if ( (index = buildTree( &(node->branch[i]), treeData, index, dataLength, codeTable, tableLength )) < 0 ) return -1; - // This means the entire left sub tree will be read before the right sub tree gets read. - } else { - // Read leaf value and map its value/index in the nodes array. - if ( index >= dataLength ) return -1; - // set the nodes huffman code values. - node->branch[i].code = (node->code << 1) | i; - node->branch[i].bitCount = node->bitCount+1; - node->branch[i].value = treeData[index] & 0xff; - // NULL the child node's branch to mark it as a leaf. - node->branch[i].branch = 0; - // buffer overflow check. - if ( (node->branch[i].value >= 0) && (node->branch[i].value <= tableLength ) ) - // store a pointer to the leaf node into the code table at the location of its byte value. - codeTable[ node->branch[i].value ] = &node->branch[i]; - index++; - } - } - - return index; - } - - /** Decodes data read from an input buffer and stores the result in the output buffer. - * @return number of bytes stored in the output buffer or -1 if an error occurs while encoding. */ - int HuffmanCodec::encode( - unsigned char const * const input, /**< in: pointer to the first byte to encode. */ - unsigned char * const output, /**< out: pointer to an output buffer to store data. */ - int const &inLength, /**< in: number of bytes of input buffer to encoded. */ - int const &outLength /**< in: maximum length of data to output. */ - ) const { - // setup the bit buffer to output. if not expandable Limit output to input length. - if ( expandable ) writer->outputBuffer( output, outLength ); - else writer->outputBuffer( output, ((inLength + 1) < outLength) ? inLength + 1 : outLength ); - - writer->put( (unsigned char)0 ); // reserve place for padding signal. - - HuffmanNode * node; // temp ptr cache; - for ( int i = 0; i < inLength; i++ ){ - node = codeTable[ 0xff & input[i] ]; //lookup node - // Put the huffman code into the bit buffer and bail if error occurs. - if ( !writer->put( node->code, node->bitCount ) ) return -1; - } - int bytesWritten, padding; - if ( writer->finish( bytesWritten, padding ) ){ - // write padding signal byte to begining of stream. - output[0] = (unsigned char)padding; - } else return -1; - - // Reverse the bit order of each byte (Old Huffman Compatibility Mode) - if ( reverseBits ) for ( int i = 1; i < bytesWritten; i++ ){ - output[i] = reverseMap[ 0xff & output[i] ]; - } - - return bytesWritten; - } // end function encode - - /** Decodes data read from an input buffer and stores the result in the output buffer. - * @return number of bytes stored in the output buffer or -1 if an error occurs while decoding. */ - int HuffmanCodec::decode( - unsigned char const * const input, /**< in: pointer to data that needs decoding. */ - unsigned char * const output, /**< out: pointer to output buffer to store decoded data. */ - int const &inLength, /**< in: number of bytes of input buffer to read. */ - int const &outLength /**< in: maximum length of data to output. */ - ){ - if ( inLength < 1 ) return 0; - int bitsAvailable = ((inLength-1) << 3) - (0xff & input[0]); - int rIndex = 1; // read index of input buffer. - int wIndex = 0; // write index of output buffer. - char byte = 0; // bits of the current byte. - int bitsLeft = 0; // bits left in byte; - - HuffmanNode * node = root; - - // Traverse the tree, output values. - while ( (bitsAvailable > 0) && (node != 0) ){ - - // Get the next byte if we've run out. - if ( bitsLeft <= 0 ){ - byte = input[rIndex++]; - if ( reverseBits ) byte = reverseMap[ 0xff & byte ]; - bitsLeft = 8; - } - - // Traverse the tree according to the most significant bit. - node = &(node->branch[ ((byte >> 7) & 0x01) ]); - - // Is the node Non NULL, and a leaf? - if ( (node != 0) && (node->branch == 0) ){ - // buffer overflow prevention - if ( wIndex >= outLength ) return wIndex; - // Output leaf node's value and restart traversal at root node. - output[ wIndex++ ] = (unsigned char)(node->value & 0xff); - node = root; - } - - byte <<= 1; // cue up the next bit - bitsLeft--; // use up one bit of byte - bitsAvailable--; // decrement total bits left - } - - return wIndex; - } // end function decode - - /** Deletes all sub nodes of a HuffmanNode by traversing and deleting its child nodes. - * @param treeNode pointer to a HuffmanNode whos children will be deleted. */ - void HuffmanCodec::deleteTree( HuffmanNode * treeNode ){ - if ( treeNode == 0 ) return; - if ( treeNode->branch != 0 ){ - deleteTree( &(treeNode->branch[0]) ); - deleteTree( &(treeNode->branch[1]) ); - delete treeNode->branch; - } - } - - /** Destructor - frees resources. */ - HuffmanCodec::~HuffmanCodec() { - delete writer; - //check for resource ownership before deletion - if ( huffmanResourceOwner() ){ - delete codeTable; - deleteTree( root ); - delete root; - } - } - - /** Enables or Disables backwards bit ordering of bytes. - * @param backwards "true" enables reversed bit order bytes, "false" uses standard byte bit ordering. */ - void HuffmanCodec::reversedBytes( bool backwards ){ reverseBits = backwards; } - - /** Check the state of backwards bit ordering for bytes. - * @return true: bits within bytes are reversed. false: bits within bytes are normal. */ - bool HuffmanCodec::reversedBytes(){ return reverseBits; } - - /** Enable or Disable data expansion during encoding. - * @param expandingAllowed "true" allows encoding to expand data. "false" causes failure upon expansion. */ - void HuffmanCodec::allowExpansion( bool expandingAllowed ){ expandable = expandingAllowed; } - - /** Check the state of data expandability. - * @return true: data expansion is allowed. false: data is not allowed to expand. */ - bool HuffmanCodec::allowExpansion(){ return expandable; } - - -}; // end namespace skulltag
--- a/sources/huffman/huffcodec.h Fri May 15 20:10:44 2015 +0300 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,182 +0,0 @@ -/* - * skulltag::HuffmanCodec class - Huffman encoder and decoder. - * - * Copyright 2009 Timothy Landers - * email: code.vortexcortex@gmail.com - * - * Permission is hereby granted, free of charge, to any person obtaining a copy - * of this software and associated documentation files (the "Software"), to deal - * in the Software without restriction, including without limitation the rights - * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell - * copies of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice shall be included in - * all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE - * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, - * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN - * THE SOFTWARE. - */ - -#ifndef _HUFFMAN_CODEC_VERSION -#define _HUFFMAN_CODEC_VERSION 1 -#define _HUFFMAN_CODEC_REV 0 - -#include "codec.h" -#include "bitwriter.h" -#include "bitreader.h" - -/** Prevents naming convention problems via encapsulation. */ -namespace skulltag { - - /** HuffmanCodec class - Encodes and Decodes data using a Huffman tree. */ - class HuffmanCodec : public Codec { - - /** top level node of the Huffman tree used for decoding. */ - HuffmanNode * root; - - /** table of Huffman codes and bit lengths used for encoding. */ - HuffmanNode ** codeTable; - - /** intermediary destination of huffman codes. */ - BitWriter * writer; - - /** When true this HuffmanCodec reverses its bytes after encoding and before decoding to - * provide compatibility with the backwards bit ordering of the original ST Huffman Encoding. - * Default value is "false" (do not reverse bits). */ - bool reverseBits; - - /** When false this HuffmanCodec return -1 instead of expanding data during encoding. - * Default value is "true" (allow data expansion). */ - bool expandable; - - /** Determines if this HuffmanCodec owns its Huffman tree nodes. */ - bool huffResourceOwner; - - /** Reverses the order of bits in a byte. - * EG: The statement <code>reverseMap[0xAF] == 0xF5</code> is <code>true</code>. <br> - * The index <code>10101111</code> stores the reverse value: <code>11110101</code>. <br> - * Note: One array lookup is much faster than Eight bit manipulating loop iterations. */ - static unsigned char const reverseMap[]; - - /** Number of bits the shortest huffman code in the tree has. */ - int shortestCode; - - public: - - /** Creates a new HuffmanCodec from the Huffman tree data. - * @param treeData pointer to a buffer containing the Huffman tree structure definition. - * @param dataLength length in bytes of the Huffman tree structure data. */ - HuffmanCodec( unsigned char const * const treeData, int dataLength ); - - /** Creates a new HuffmanCodec that uses the specified Huffman resources. - * @param treeRootNode The root node of a valid huffman tree. - * @param leafCodeTable A code lookup table where references to HuffmanNodes are stored with their array index equal to their value. - * Note: The tree nodes will not be released upon destruction of this HuffmanCodec. */ - HuffmanCodec( - HuffmanNode * treeRootNode, - HuffmanNode ** leafCodeTable - ); - - /** Frees resources used internally by this HuffmanCodec. */ - virtual ~HuffmanCodec(); - - /** Decodes data read from an input buffer and stores the result in the output buffer. - * @return number of bytes stored in the output buffer or -1 if an error occurs while encoding. */ - virtual int encode( - unsigned char const * const input, /**< in: pointer to the first byte to encode. */ - unsigned char * const output, /**< out: pointer to an output buffer to store data. */ - int const &inLength, /**< in: number of bytes of input buffer to encoded. */ - int const &outLength /**< in: maximum length of data to output. */ - ) const; - - /** Decodes data read from an input buffer and stores the result in the output buffer. - * @return number of bytes stored in the output buffer or -1 if an error occurs while decoding. */ - virtual int decode( - unsigned char const * const input, /**< in: pointer to data that needs decoding. */ - unsigned char * const output, /**< out: pointer to output buffer to store decoded data. */ - int const &inLength, /**< in: number of bytes of input buffer to read. */ - int const &outLength /**< in: maximum length of data to output. */ - ); - - /** Enables or Disables backwards bit ordering of bytes. - * @param backwards "true" enables reversed bit order bytes, "false" uses standard byte bit ordering. */ - void reversedBytes( bool backwards ); - - /** Check the state of backwards bit ordering for bytes. - * @return true: bits within bytes are reversed. false: bits within bytes are normal. */ - bool reversedBytes(); - - /** Enable or Disable data expansion during encoding. - * @param expandingAllowed "true" allows encoding to expand data. "false" causes failure upon expansion. */ - void allowExpansion( bool expandable ); - - /** Check the state of data expandability. - * @return true: data expansion is allowed. false: data is not allowed to expand. */ - bool allowExpansion(); - - /** Sets the ownership of this HuffmanCodec's resources. - * @param ownsResources When false the tree will not be released upon destruction of this HuffmanCodec. - * When true deleting this HuffmanCodec will cause the Huffman tree to be released. */ - void huffmanResourceOwner( bool ownsResources ); - - /** Checks the ownership state of this HuffmanCodec's resources. - * @return ownsResources When false the tree will not be released upon destruction of this HuffmanCodec. - * When true deleting this HuffmanCodec will cause the Huffman tree to be released. */ - bool huffmanResourceOwner(); - - /** Deletes all sub nodes of a HuffmanNode by traversing and deleting its child nodes. - * @param treeNode pointer to a HuffmanNode whos children will be deleted. */ - static void deleteTree( HuffmanNode * treeNode ); - - /** Recursively builds a Huffman Tree. <br> - * The initial root node should have the following field values: <br> - * <pre> - * bitCount : 0 - * code : 0 - * value : -1 - * branch : 0 (NULL) - * </pre> - * @param node in/out: branch node of the Huffman Tree. - * @param treeData in: char array containing the Huffman Tree's byte representation. - * @param index in: Current array element to read the next tree node from. - * @param dataLength in: Length of treeData - * @param codeTable in/out: array of pointers to HuffmanNode structs. - * @param tableLength in: maximum index allowed in the codeTable. - * @return the next index to read from or -1 if an error occurs. - * */ - int buildTree( - HuffmanNode * node, - unsigned char const * const treeData, - int index, - int dataLength, - HuffmanNode ** const &codeTable, - int tableLength - ); - - /** Decreases a codeLength to the shortest Huffman code bit length found in the node or any of its children. <br> - * Set to Zero before calling to determine minimum code bit length. - * @param node in: The node to begin searching at. - * @param codeLength out: Variable to hold the longest code bit length found. */ - static void minCodeLength( HuffmanNode const * const node, int &codeLength ); - - /** Increases a codeLength up to the longest Huffman code bit length found in the node or any of its children. <br> - * Set to Zero before calling to determine maximum code bit length. - * @param node in: The node to begin searching at. - * @param codeLength out: Variable to hold the longest code bit length found. */ - static void maxCodeLength( HuffmanNode const * const node, int &codeLength ); - - private: - - /** Perform initialization procedures common to all constructors. */ - void init(); - - }; // end class Huffman Codec. -} // end namespace skulltag - -#endif
--- a/sources/huffman/huffman.cpp Fri May 15 20:10:44 2015 +0300 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,159 +0,0 @@ -/* - * Replacement for older Skulltag Launcher Protocol's huffman.cpp - * - * Copyright 2009 Timothy Landers - * email: code.vortexcortex@gmail.com - * - * Permission is hereby granted, free of charge, to any person obtaining a copy - * of this software and associated documentation files (the "Software"), to deal - * in the Software without restriction, including without limitation the rights - * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell - * copies of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice shall be included in - * all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE - * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, - * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN - * THE SOFTWARE. - */ - -// required for atexit() -#include <stdlib.h> -#include <stdio.h> - -#include "huffman.h" -#include "huffcodec.h" -// #include "i_system.h" - -using namespace skulltag; -// Global Variables - -/** Reference to the HuffmanCodec Object that will perform the encoding and decoding. */ -static HuffmanCodec * __codec = NULL; - -// Function Implementation - -/** Creates and intitializes a HuffmanCodec Object. <br> - * Also arranges for HUFFMAN_Destruct() to be called upon termination. */ -void HUFFMAN_Construct(){ - - // The exact structure description of a Huffman tree - static unsigned char const compatible_huffman_tree[] = { - 0, 0, 0, 1,128, 0, 0, 0, 3, 38, 34, 2, 1, 80, 3,110, - 144, 67, 0, 2, 1, 74, 3,243,142, 37, 2, 3,124, 58,182, 0, - 0, 1, 36, 0, 3,221,131, 3,245,163, 1, 35, 3,113, 85, 0, - 1, 41, 1, 77, 3,199,130, 0, 1,206, 3,185,153, 3, 70,118, - 0, 3, 3, 5, 0, 0, 1, 24, 0, 2, 3,198,190, 63, 2, 3, - 139,186, 75, 0, 1, 44, 2, 3,240,218, 56, 3, 40, 39, 0, 0, - 2, 2, 3,244,247, 81, 65, 0, 3, 9,125, 3, 68, 60, 0, 0, - 1, 25, 3,191,138, 3, 86, 17, 0, 1, 23, 3,220,178, 2, 3, - 165,194, 14, 1, 0, 2, 2, 0, 0, 2, 1,208, 3,150,157,181, - 1,222, 2, 3,216,230,211, 0, 2, 2, 3,252,141, 10, 42, 0, - 2, 3,134,135,104, 1,103, 3,187,225, 95, 32, 0, 0, 0, 0, - 0, 0, 1, 57, 1, 61, 3,183,237, 0, 0, 3,233,234, 3,246, - 203, 2, 3,250,147, 79, 1,129, 0, 1, 7, 3,143,136, 1, 20, - 3,179,148, 0, 0, 0, 3, 28,106, 3,101, 87, 1, 66, 0, 3, - 180,219, 3,227,241, 0, 1, 26, 1,251, 3,229,214, 3, 54, 69, - 0, 0, 0, 0, 0, 3,231,212, 3,156,176, 3, 93, 83, 0, 3, - 96,253, 3, 30, 13, 0, 0, 2, 3,175,254, 94, 3,159, 27, 2, - 1, 8, 3,204,226, 78, 0, 0, 0, 3,107, 88, 1, 31, 3,137, - 169, 2, 2, 3,215,145, 6, 4, 1,127, 0, 1, 99, 3,209,217, - 0, 3,213,238, 3,177,170, 1,132, 0, 0, 0, 2, 3, 22, 12, - 114, 2, 2, 3,158,197, 97, 45, 0, 1, 46, 1,112, 3,174,249, - 0, 3,224,102, 2, 3,171,151,193, 0, 0, 0, 3, 15, 16, 3, - 2,168, 1, 49, 3, 91,146, 0, 1, 48, 3,173, 29, 0, 3, 19, - 126, 3, 92,242, 0, 0, 0, 0, 0, 0, 3,205,192, 2, 3,235, - 149,255, 2, 3,223,184,248, 0, 0, 3,108,236, 3,111, 90, 2, - 3,117,115, 71, 0, 0, 3, 11, 50, 0, 3,188,119, 1,122, 3, - 167,162, 1,160, 1,133, 3,123, 21, 0, 0, 2, 1, 59, 2, 3, - 155,154, 98, 43, 0, 3, 76, 51, 2, 3,201,116, 72, 2, 0, 2, - 3,109,100,121, 2, 3,195,232, 18, 1, 0, 2, 0, 1,164, 2, - 3,120,189, 73, 0, 1,196, 3,239,210, 3, 64, 62, 89, 0, 0, - 1, 33, 2, 3,228,161, 55, 2, 3, 84,152, 47, 0, 0, 2, 3, - 207,172,140, 3, 82,166, 0, 3, 53,105, 1, 52, 3,202,200 - }; - - // create a HuffmanCodec that is compatible with the previous implementation. - __codec = new HuffmanCodec( compatible_huffman_tree, sizeof compatible_huffman_tree ); - - // set up the HuffmanCodec to perform in a backwards compatible fashion. - __codec->reversedBytes( true ); - __codec->allowExpansion( false ); - - // request that the destruct function be called upon exit. - // atterm( HUFFMAN_Destruct ); - atexit( HUFFMAN_Destruct ); -} - -/** Releases resources allocated by the HuffmanCodec. */ -void HUFFMAN_Destruct(){ - delete __codec; - __codec = NULL; -} - -/** Applies Huffman encoding to a block of data. */ -void HUFFMAN_Encode( - /** in: Pointer to start of data that is to be encoded. */ - unsigned char const * const inputBuffer, - /** out: Pointer to destination buffer where encoded data will be stored. */ - unsigned char * const outputBuffer, - /** in: Number of chars to read from inputBuffer. */ - int const &inputBufferSize, - /**< in+out: Max chars to write into outputBuffer. <br> - * Upon return holds the number of chars stored or 0 if an error occurs. */ - int * outputBufferSize -){ - int bytesWritten = __codec->encode( inputBuffer, outputBuffer, inputBufferSize, *outputBufferSize ); - - // expansion occured -- provide backwards compatibility - if ( bytesWritten < 0 ){ - // check buffer sizes - if ( *outputBufferSize < (inputBufferSize + 1) ){ - // outputBuffer too small, return "no bytes written" - *outputBufferSize = 0; - return; - } - - // perform the unencoded copy - for ( int i = 0; i < inputBufferSize; i++ ) outputBuffer[i+1] = inputBuffer[i]; - // supply the "unencoded" signal and bytesWritten - outputBuffer[0] = 0xff; - *outputBufferSize = inputBufferSize + 1; - } else { - // assign the bytesWritten return value - *outputBufferSize = bytesWritten; - } -} // end function HUFFMAN_Encode - -/** Decodes a block of data that is Huffman encoded. */ -void HUFFMAN_Decode( - unsigned char const * const inputBuffer, /**< in: Pointer to start of data that is to be decoded. */ - unsigned char * const outputBuffer, /**< out: Pointer to destination buffer where decoded data will be stored. */ - int const &inputBufferSize, /**< in: Number of chars to read from inputBuffer. */ - int *outputBufferSize /**< in+out: Max chars to write into outputBuffer. Upon return holds the number of chars stored or 0 if an error occurs. */ -){ - // check for "unencoded" signal & provide backwards compatibility - if ((inputBufferSize > 0) && ((inputBuffer[0]&0xff) == 0xff)){ - // check buffer sizes - if ( *outputBufferSize < (inputBufferSize - 1) ){ - // outputBuffer too small, return "no bytes written" - *outputBufferSize = 0; - return; - } - - // perform the unencoded copy - for ( int i = 1; i < inputBufferSize; i++ ) outputBuffer[i-1] = inputBuffer[i]; - - // supply the bytesWritten - *outputBufferSize = inputBufferSize - 1; - } else { - // decode the data - *outputBufferSize = __codec->decode( inputBuffer, outputBuffer, inputBufferSize, *outputBufferSize ); - } -} // end function HUFFMAN_Decode
--- a/sources/huffman/huffman.h Fri May 15 20:10:44 2015 +0300 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,55 +0,0 @@ -/* - * Replacement for older Skulltag Launcher Protocol's huffman.cpp - * - * Copyright 2009 Timothy Landers - * email: code.vortexcortex@gmail.com - * - * Permission is hereby granted, free of charge, to any person obtaining a copy - * of this software and associated documentation files (the "Software"), to deal - * in the Software without restriction, including without limitation the rights - * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell - * copies of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice shall be included in - * all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE - * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, - * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN - * THE SOFTWARE. - */ - -//Macro name kept for backwards compatibility. -#ifndef __HUFFMAN_H__ -#define __HUFFMAN_H__ - -#include "huffcodec.h" - -/** Creates and intitializes a HuffmanCodec Object. <br> - * Also arranges for HUFFMAN_Destruct() to be called upon termination. */ -void HUFFMAN_Construct(); - -/** Releases resources allocated by the HuffmanCodec. */ -void HUFFMAN_Destruct(); - -/** Applies Huffman encoding to a block of data. */ -void HUFFMAN_Encode( - unsigned char const * const inputBuffer, /**< in: Pointer to start of data that is to be encoded. */ - unsigned char * const outputBuffer, /**< out: Pointer to destination buffer where encoded data will be stored. */ - int const &inputBufferSize, /**< in: Number of chars to read from inputBuffer. */ - int *outputBufferSize /**< in+out: Max chars to write into outputBuffer. Upon return holds the number of chars stored or 0 if an error occurs. */ -); - -/** Decodes a block of data that is Huffman encoded. */ -void HUFFMAN_Decode( - unsigned char const * const inputBuffer, /**< in: Pointer to start of data that is to be decoded. */ - unsigned char * const outputBuffer, /**< out: Pointer to destination buffer where decoded data will be stored. */ - int const &inputBufferSize, /**< in: Number of chars to read from inputBuffer. */ - int *outputBufferSize /**< in+out: Max chars to write into outputBuffer. Upon return holds the number of chars stored or 0 if an error occurs. */ -); - -#endif // __HUFFMAN_H__
--- a/sources/main.cpp Fri May 15 20:10:44 2015 +0300 +++ b/sources/main.cpp Fri May 15 20:13:36 2015 +0300 @@ -32,7 +32,7 @@ #include <sys/select.h> #include "main.h" #include "network/rconsession.h" -#include "huffman/huffman.h" +#include "huffman.h" #include "interface.h" // -------------------------------------------------------------------------------------------------
