# HG changeset patch # User Teemu Piippo # Date 1418275091 -7200 # Node ID 8b697d30c49f0c1e3bd193c179a4ea8877168e25 # Parent 01e4e9ae323ac49b22eb31d148319723ab2dfd00 - added huffman lib, now capable of initializing an rcon connection! diff -r 01e4e9ae323a -r 8b697d30c49f CMakeLists.txt --- a/CMakeLists.txt Thu Dec 11 06:13:32 2014 +0200 +++ b/CMakeLists.txt Thu Dec 11 07:18:11 2014 +0200 @@ -10,6 +10,10 @@ sources/network/bytestream.cpp sources/network/ipaddress.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) diff -r 01e4e9ae323a -r 8b697d30c49f sources/huffman/bitreader.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/sources/huffman/bitreader.cpp Thu Dec 11 07:18:11 2014 +0200 @@ -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.
+ * 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 diff -r 01e4e9ae323a -r 8b697d30c49f sources/huffman/bitreader.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/sources/huffman/bitreader.h Thu Dec 11 07:18:11 2014 +0200 @@ -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.
+ * 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.
+ * 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 + diff -r 01e4e9ae323a -r 8b697d30c49f sources/huffman/bitwriter.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/sources/huffman/bitwriter.cpp Thu Dec 11 07:18:11 2014 +0200 @@ -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.
+ * 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.
+ * 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; + } + +} diff -r 01e4e9ae323a -r 8b697d30c49f sources/huffman/bitwriter.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/sources/huffman/bitwriter.h Thu Dec 11 07:18:11 2014 +0200 @@ -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.
+ * 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.
+ * 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.
+ * 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 + diff -r 01e4e9ae323a -r 8b697d30c49f sources/huffman/codec.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/sources/huffman/codec.h Thu Dec 11 07:18:11 2014 +0200 @@ -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.
+ * 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 diff -r 01e4e9ae323a -r 8b697d30c49f sources/huffman/huffcodec.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/sources/huffman/huffcodec.cpp Thu Dec 11 07:18:11 2014 +0200 @@ -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 reverseMap[0xAF] == 0xF5 is true.
+ * The index 10101111 stores the reverse value: 11110101.
+ * 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.
+ * 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.
+ * 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.
+ * 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.
+ * The initial root node should have the following field values:
+ * 
+	 * bitCount : 0
+	 * code     : 0
+	 * value    : -1
+	 * branch   : 0 (NULL)
+	 *
+ * @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 diff -r 01e4e9ae323a -r 8b697d30c49f sources/huffman/huffcodec.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/sources/huffman/huffcodec.h Thu Dec 11 07:18:11 2014 +0200 @@ -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 reverseMap[0xAF] == 0xF5 is true.
+ * The index 10101111 stores the reverse value: 11110101.
+ * 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.
+ * The initial root node should have the following field values:
+ * 
+		 * bitCount : 0
+		 * code     : 0
+		 * value    : -1
+		 * branch   : 0 (NULL)
+		 *
+ * @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.
+ * 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.
+ * 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 diff -r 01e4e9ae323a -r 8b697d30c49f sources/huffman/huffman.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/sources/huffman/huffman.cpp Thu Dec 11 07:18:11 2014 +0200 @@ -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 +#include + +#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.
+ * 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.
+ * 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 diff -r 01e4e9ae323a -r 8b697d30c49f sources/huffman/huffman.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/sources/huffman/huffman.h Thu Dec 11 07:18:11 2014 +0200 @@ -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.
+ * 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__ diff -r 01e4e9ae323a -r 8b697d30c49f sources/main.cpp --- a/sources/main.cpp Thu Dec 11 06:13:32 2014 +0200 +++ b/sources/main.cpp Thu Dec 11 07:18:11 2014 +0200 @@ -29,13 +29,30 @@ */ #include "main.h" -#include "network/bytestream.h" +#include "network/udpsocket.h" +#include "huffman/huffman.h" // ------------------------------------------------------------------------------------------------- // FUNCTION main (int argc, char* argv[]) -> int { + HUFFMAN_Construct(); + Bytestream packet; + packet.write_byte (0x34); // header + packet.write_byte (0x03); // version + UDPSocket socket; + assert (socket.set_blocking (false)); + socket.send (IPAddress (localhost, 10666), packet); + Datagram datagram; + + while (socket.read (datagram) == false) + ; + + printf ("Recieved datagram of %lu bytes from %s\n", datagram.data.written_length(), datagram.from.to_string (IP_WITH_PORT).chars()); + HUFFMAN_Destruct(); + return 0; + initscr(); start_color(); raw(); diff -r 01e4e9ae323a -r 8b697d30c49f sources/network/ipaddress.cpp --- a/sources/network/ipaddress.cpp Thu Dec 11 06:13:32 2014 +0200 +++ b/sources/network/ipaddress.cpp Thu Dec 11 07:18:11 2014 +0200 @@ -6,7 +6,6 @@ #include #include "ipaddress.h" -const IPAddress localhost (0x7F000001, 0); bool IPAddress::sink; // ----------------------------------------------------------------------------- diff -r 01e4e9ae323a -r 8b697d30c49f sources/network/ipaddress.h --- a/sources/network/ipaddress.h Thu Dec 11 06:13:32 2014 +0200 +++ b/sources/network/ipaddress.h Thu Dec 11 07:18:11 2014 +0200 @@ -30,7 +30,7 @@ static METHOD resolve (String node, bool* ok = &sink) -> IPAddress; }; -extern const IPAddress localhost; +static const unsigned long localhost = 0x7F000001; inline METHOD IPAddress::operator[] (int n) const -> unsigned char diff -r 01e4e9ae323a -r 8b697d30c49f sources/network/udpsocket.cpp --- a/sources/network/udpsocket.cpp Thu Dec 11 06:13:32 2014 +0200 +++ b/sources/network/udpsocket.cpp Thu Dec 11 07:18:11 2014 +0200 @@ -5,6 +5,9 @@ #include #include #include "udpsocket.h" +#include "../huffman/huffman.h" + +static unsigned char g_huffmanBuffer[131072]; // ----------------------------------------------------------------------------- // @@ -21,7 +24,7 @@ UDPSocket::set_blocking (bool a) -> bool { int flags = fcntl (m_socket, F_GETFL, 0); - int newflags = (a ? (flags | O_NONBLOCK) : (flags & ~O_NONBLOCK)); + int newflags = (a ? (flags & ~O_NONBLOCK) : (flags | O_NONBLOCK)); if (flags < 0 || fcntl (m_socket, F_SETFL, newflags) != 0) { @@ -60,7 +63,7 @@ sockaddr_in claddr; socklen_t socklen = sizeof claddr; static unsigned char packet[MAX_DATAGRAM_LENGTH]; - int length = ::recvfrom (m_socket, packet, sizeof packet, 0, + int length = ::recvfrom (m_socket, g_huffmanBuffer, sizeof packet, 0, reinterpret_cast (&claddr), &socklen); if (length == -1) @@ -72,20 +75,23 @@ return false; } + int decodedlength = sizeof g_huffmanBuffer; + HUFFMAN_Decode (g_huffmanBuffer, packet, length, &decodedlength); datagram.from.host = ntohl (claddr.sin_addr.s_addr); datagram.from.port = ntohs (claddr.sin_port); - datagram.data = Bytestream (packet, length); + datagram.data = Bytestream (packet, decodedlength); return true; } // ------------------------------------------------------------------------------------------------- // METHOD -UDPSocket::send (const Bytestream& data, const IPAddress& addr) -> bool +UDPSocket::send (const IPAddress& address, const Bytestream& data) -> bool { - struct sockaddr_in claddr = addr.to_sockaddr_in(); - - int res = ::sendto (m_socket, data.data(), data.written_length(), 0, + int encodedlength = sizeof g_huffmanBuffer; + HUFFMAN_Encode (data.data(), g_huffmanBuffer, data.written_length(), &encodedlength); + struct sockaddr_in claddr = address.to_sockaddr_in(); + int res = ::sendto (m_socket, g_huffmanBuffer, encodedlength, 0, reinterpret_cast (&claddr), sizeof claddr); if (res == -1) diff -r 01e4e9ae323a -r 8b697d30c49f sources/network/udpsocket.h --- a/sources/network/udpsocket.h Thu Dec 11 06:13:32 2014 +0200 +++ b/sources/network/udpsocket.h Thu Dec 11 07:18:11 2014 +0200 @@ -21,7 +21,7 @@ METHOD bind (unsigned short port) -> bool; METHOD read (Datagram& datagram) -> bool; - METHOD send (const Bytestream& data, const IPAddress& addr) -> bool; + METHOD send (const IPAddress& address, const Bytestream& data) -> bool; METHOD set_blocking (bool a) -> bool; private: