--- /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