comparison: huffman/huffcodec.h
huffman/huffcodec.h
- changeset 76
- 6de6d9a64ebd
- parent 8
- 8b697d30c49f
equal
deleted
inserted
replaced
| 75:5f8a03274d75 | 76:6de6d9a64ebd |
|---|---|
| 1 /* | |
| 2 * skulltag::HuffmanCodec class - Huffman encoder and decoder. | |
| 3 * | |
| 4 * Copyright 2009 Timothy Landers | |
| 5 * email: code.vortexcortex@gmail.com | |
| 6 * | |
| 7 * Permission is hereby granted, free of charge, to any person obtaining a copy | |
| 8 * of this software and associated documentation files (the "Software"), to deal | |
| 9 * in the Software without restriction, including without limitation the rights | |
| 10 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell | |
| 11 * copies of the Software, and to permit persons to whom the Software is | |
| 12 * furnished to do so, subject to the following conditions: | |
| 13 * | |
| 14 * The above copyright notice and this permission notice shall be included in | |
| 15 * all copies or substantial portions of the Software. | |
| 16 * | |
| 17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | |
| 18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | |
| 19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE | |
| 20 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER | |
| 21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, | |
| 22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN | |
| 23 * THE SOFTWARE. | |
| 24 */ | |
| 25 | |
| 26 #ifndef _HUFFMAN_CODEC_VERSION | |
| 27 #define _HUFFMAN_CODEC_VERSION 1 | |
| 28 #define _HUFFMAN_CODEC_REV 0 | |
| 29 | |
| 30 #include "codec.h" | |
| 31 #include "bitwriter.h" | |
| 32 #include "bitreader.h" | |
| 33 | |
| 34 /** Prevents naming convention problems via encapsulation. */ | |
| 35 namespace skulltag { | |
| 36 | |
| 37 /** HuffmanCodec class - Encodes and Decodes data using a Huffman tree. */ | |
| 38 class HuffmanCodec : public Codec { | |
| 39 | |
| 40 /** top level node of the Huffman tree used for decoding. */ | |
| 41 HuffmanNode * root; | |
| 42 | |
| 43 /** table of Huffman codes and bit lengths used for encoding. */ | |
| 44 HuffmanNode ** codeTable; | |
| 45 | |
| 46 /** intermediary destination of huffman codes. */ | |
| 47 BitWriter * writer; | |
| 48 | |
| 49 /** When true this HuffmanCodec reverses its bytes after encoding and before decoding to | |
| 50 * provide compatibility with the backwards bit ordering of the original ST Huffman Encoding. | |
| 51 * Default value is "false" (do not reverse bits). */ | |
| 52 bool reverseBits; | |
| 53 | |
| 54 /** When false this HuffmanCodec return -1 instead of expanding data during encoding. | |
| 55 * Default value is "true" (allow data expansion). */ | |
| 56 bool expandable; | |
| 57 | |
| 58 /** Determines if this HuffmanCodec owns its Huffman tree nodes. */ | |
| 59 bool huffResourceOwner; | |
| 60 | |
| 61 /** Reverses the order of bits in a byte. | |
| 62 * EG: The statement <code>reverseMap[0xAF] == 0xF5</code> is <code>true</code>. <br> | |
| 63 * The index <code>10101111</code> stores the reverse value: <code>11110101</code>. <br> | |
| 64 * Note: One array lookup is much faster than Eight bit manipulating loop iterations. */ | |
| 65 static unsigned char const reverseMap[]; | |
| 66 | |
| 67 /** Number of bits the shortest huffman code in the tree has. */ | |
| 68 int shortestCode; | |
| 69 | |
| 70 public: | |
| 71 | |
| 72 /** Creates a new HuffmanCodec from the Huffman tree data. | |
| 73 * @param treeData pointer to a buffer containing the Huffman tree structure definition. | |
| 74 * @param dataLength length in bytes of the Huffman tree structure data. */ | |
| 75 HuffmanCodec( unsigned char const * const treeData, int dataLength ); | |
| 76 | |
| 77 /** Creates a new HuffmanCodec that uses the specified Huffman resources. | |
| 78 * @param treeRootNode The root node of a valid huffman tree. | |
| 79 * @param leafCodeTable A code lookup table where references to HuffmanNodes are stored with their array index equal to their value. | |
| 80 * Note: The tree nodes will not be released upon destruction of this HuffmanCodec. */ | |
| 81 HuffmanCodec( | |
| 82 HuffmanNode * treeRootNode, | |
| 83 HuffmanNode ** leafCodeTable | |
| 84 ); | |
| 85 | |
| 86 /** Frees resources used internally by this HuffmanCodec. */ | |
| 87 virtual ~HuffmanCodec(); | |
| 88 | |
| 89 /** Decodes data read from an input buffer and stores the result in the output buffer. | |
| 90 * @return number of bytes stored in the output buffer or -1 if an error occurs while encoding. */ | |
| 91 virtual int encode( | |
| 92 unsigned char const * const input, /**< in: pointer to the first byte to encode. */ | |
| 93 unsigned char * const output, /**< out: pointer to an output buffer to store data. */ | |
| 94 int const &inLength, /**< in: number of bytes of input buffer to encoded. */ | |
| 95 int const &outLength /**< in: maximum length of data to output. */ | |
| 96 ) const; | |
| 97 | |
| 98 /** Decodes data read from an input buffer and stores the result in the output buffer. | |
| 99 * @return number of bytes stored in the output buffer or -1 if an error occurs while decoding. */ | |
| 100 virtual int decode( | |
| 101 unsigned char const * const input, /**< in: pointer to data that needs decoding. */ | |
| 102 unsigned char * const output, /**< out: pointer to output buffer to store decoded data. */ | |
| 103 int const &inLength, /**< in: number of bytes of input buffer to read. */ | |
| 104 int const &outLength /**< in: maximum length of data to output. */ | |
| 105 ); | |
| 106 | |
| 107 /** Enables or Disables backwards bit ordering of bytes. | |
| 108 * @param backwards "true" enables reversed bit order bytes, "false" uses standard byte bit ordering. */ | |
| 109 void reversedBytes( bool backwards ); | |
| 110 | |
| 111 /** Check the state of backwards bit ordering for bytes. | |
| 112 * @return true: bits within bytes are reversed. false: bits within bytes are normal. */ | |
| 113 bool reversedBytes(); | |
| 114 | |
| 115 /** Enable or Disable data expansion during encoding. | |
| 116 * @param expandingAllowed "true" allows encoding to expand data. "false" causes failure upon expansion. */ | |
| 117 void allowExpansion( bool expandable ); | |
| 118 | |
| 119 /** Check the state of data expandability. | |
| 120 * @return true: data expansion is allowed. false: data is not allowed to expand. */ | |
| 121 bool allowExpansion(); | |
| 122 | |
| 123 /** Sets the ownership of this HuffmanCodec's resources. | |
| 124 * @param ownsResources When false the tree will not be released upon destruction of this HuffmanCodec. | |
| 125 * When true deleting this HuffmanCodec will cause the Huffman tree to be released. */ | |
| 126 void huffmanResourceOwner( bool ownsResources ); | |
| 127 | |
| 128 /** Checks the ownership state of this HuffmanCodec's resources. | |
| 129 * @return ownsResources When false the tree will not be released upon destruction of this HuffmanCodec. | |
| 130 * When true deleting this HuffmanCodec will cause the Huffman tree to be released. */ | |
| 131 bool huffmanResourceOwner(); | |
| 132 | |
| 133 /** Deletes all sub nodes of a HuffmanNode by traversing and deleting its child nodes. | |
| 134 * @param treeNode pointer to a HuffmanNode whos children will be deleted. */ | |
| 135 static void deleteTree( HuffmanNode * treeNode ); | |
| 136 | |
| 137 /** Recursively builds a Huffman Tree. <br> | |
| 138 * The initial root node should have the following field values: <br> | |
| 139 * <pre> | |
| 140 * bitCount : 0 | |
| 141 * code : 0 | |
| 142 * value : -1 | |
| 143 * branch : 0 (NULL) | |
| 144 * </pre> | |
| 145 * @param node in/out: branch node of the Huffman Tree. | |
| 146 * @param treeData in: char array containing the Huffman Tree's byte representation. | |
| 147 * @param index in: Current array element to read the next tree node from. | |
| 148 * @param dataLength in: Length of treeData | |
| 149 * @param codeTable in/out: array of pointers to HuffmanNode structs. | |
| 150 * @param tableLength in: maximum index allowed in the codeTable. | |
| 151 * @return the next index to read from or -1 if an error occurs. | |
| 152 * */ | |
| 153 int buildTree( | |
| 154 HuffmanNode * node, | |
| 155 unsigned char const * const treeData, | |
| 156 int index, | |
| 157 int dataLength, | |
| 158 HuffmanNode ** const &codeTable, | |
| 159 int tableLength | |
| 160 ); | |
| 161 | |
| 162 /** Decreases a codeLength to the shortest Huffman code bit length found in the node or any of its children. <br> | |
| 163 * Set to Zero before calling to determine minimum code bit length. | |
| 164 * @param node in: The node to begin searching at. | |
| 165 * @param codeLength out: Variable to hold the longest code bit length found. */ | |
| 166 static void minCodeLength( HuffmanNode const * const node, int &codeLength ); | |
| 167 | |
| 168 /** Increases a codeLength up to the longest Huffman code bit length found in the node or any of its children. <br> | |
| 169 * Set to Zero before calling to determine maximum code bit length. | |
| 170 * @param node in: The node to begin searching at. | |
| 171 * @param codeLength out: Variable to hold the longest code bit length found. */ | |
| 172 static void maxCodeLength( HuffmanNode const * const node, int &codeLength ); | |
| 173 | |
| 174 private: | |
| 175 | |
| 176 /** Perform initialization procedures common to all constructors. */ | |
| 177 void init(); | |
| 178 | |
| 179 }; // end class Huffman Codec. | |
| 180 } // end namespace skulltag | |
| 181 | |
| 182 #endif |
