huffman/huffcodec.cpp

Wed, 20 Jul 2016 17:56:40 +0300

author
Teemu Piippo <teemu@compsta2.com>
date
Wed, 20 Jul 2016 17:56:40 +0300
branch
protocol5
changeset 150
37db42ad451a
parent 76
6de6d9a64ebd
permissions
-rw-r--r--

Merged with default

8
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
1 /*
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
2 * skulltag::HuffmanCodec class - Huffman encoder and decoder.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
3 *
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
4 * Copyright 2009 Timothy Landers
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
5 * email: code.vortexcortex@gmail.com
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
6 *
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
7 * Permission is hereby granted, free of charge, to any person obtaining a copy
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
8 * of this software and associated documentation files (the "Software"), to deal
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
9 * in the Software without restriction, including without limitation the rights
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
10 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
11 * copies of the Software, and to permit persons to whom the Software is
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
12 * furnished to do so, subject to the following conditions:
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
13 *
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
14 * The above copyright notice and this permission notice shall be included in
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
15 * all copies or substantial portions of the Software.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
16 *
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
20 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
23 * THE SOFTWARE.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
24 */
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
25
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
26 #include "huffcodec.h"
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
27
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
28 /** Prevents naming convention problems via encapsulation. */
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
29 namespace skulltag {
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
30
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
31 // HuffmanCodec Implementation
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
32
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
33 /** Reverses the order of bits in a byte.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
34 * EG: The statement <code>reverseMap[0xAF] == 0xF5</code> is <code>true</code>. <br>
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
35 * The index <code>10101111</code> stores the reverse value: <code>11110101</code>. <br>
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
36 * Note: One array lookup is much faster than Eight bit manipulating loop iterations. */
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
37 unsigned char const HuffmanCodec::reverseMap[] = {
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
38 0,128, 64,192, 32,160, 96,224, 16,144, 80,208, 48,176,112,240,
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
39 8,136, 72,200, 40,168,104,232, 24,152, 88,216, 56,184,120,248,
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
40 4,132, 68,196, 36,164,100,228, 20,148, 84,212, 52,180,116,244,
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
41 12,140, 76,204, 44,172,108,236, 28,156, 92,220, 60,188,124,252,
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
42 2,130, 66,194, 34,162, 98,226, 18,146, 82,210, 50,178,114,242,
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
43 10,138, 74,202, 42,170,106,234, 26,154, 90,218, 58,186,122,250,
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
44 6,134, 70,198, 38,166,102,230, 22,150, 86,214, 54,182,118,246,
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
45 14,142, 78,206, 46,174,110,238, 30,158, 94,222, 62,190,126,254,
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
46 1,129, 65,193, 33,161, 97,225, 17,145, 81,209, 49,177,113,241,
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
47 9,137, 73,201, 41,169,105,233, 25,153, 89,217, 57,185,121,249,
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
48 5,133, 69,197, 37,165,101,229, 21,149, 85,213, 53,181,117,245,
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
49 13,141, 77,205, 45,173,109,237, 29,157, 93,221, 61,189,125,253,
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
50 3,131, 67,195, 35,163, 99,227, 19,147, 83,211, 51,179,115,243,
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
51 11,139, 75,203, 43,171,107,235, 27,155, 91,219, 59,187,123,251,
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
52 7,135, 71,199, 39,167,103,231, 23,151, 87,215, 55,183,119,247,
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
53 15,143, 79,207, 47,175,111,239, 31,159, 95,223, 63,191,127,255
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
54 };
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
55
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
56 /** Creates a new HuffmanCodec
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
57 * @param treeData char array containing the tree data to use.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
58 * @param dataLength number of chars in treeData. */
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
59 HuffmanCodec::HuffmanCodec(
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
60 unsigned char const * const treeData,
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
61 int dataLength
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
62 ) : Codec() {
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
63 init();
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
64 // init code table (256 pointers to Huffman Leaf Nodes.)
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
65 codeTable = new HuffmanNode*[256];
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
66 for (int i = 0; i < 256; i++) codeTable[i] = 0;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
67 // build root node
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
68 root = new HuffmanNode;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
69 root->bitCount = 0;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
70 root->code = 0;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
71 root->value = -1;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
72 // recursive Huffman tree builder.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
73 buildTree( root, treeData, 0, dataLength, codeTable, 256 );
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
74 huffResourceOwner = true;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
75 }
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
76
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
77
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
78 /** Creates a new HuffmanCodec that uses the specified Huffman resources.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
79 * @param treeRootNode The root node of a valid huffman tree.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
80 * @param leafCodeTable A code lookup table where references to HuffmanNodes are stored with their array index equal to their value.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
81 * Note: The tree nodes will not be released upon destruction of this HuffmanCodec. */
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
82 HuffmanCodec::HuffmanCodec(
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
83 HuffmanNode * treeRootNode,
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
84 HuffmanNode ** leafCodeTable
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
85 ){
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
86 init();
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
87 // assign values -- no table building or allocations.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
88 root = treeRootNode;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
89 codeTable = leafCodeTable;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
90 huffResourceOwner = false;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
91 }
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
92
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
93 /** Checks the ownership state of this HuffmanCodec's resources.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
94 * @return true if the tree & code table will be released upon destruction of this HuffmanCodec. <br>
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
95 * A false return value means this HuffmanCodec is not responsible for deleting its resources. */
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
96 bool HuffmanCodec::huffmanResourceOwner(){
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
97 return huffResourceOwner;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
98 }
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
99
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
100 /** Perform initialization procedures common to all constructors. */
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
101 void HuffmanCodec::init(){
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
102 writer = new BitWriter();
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
103 reverseBits = false;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
104 expandable = true;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
105 huffResourceOwner = false;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
106 }
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
107
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
108 /** Increases a codeLength up to the longest Huffman code bit length found in the node or any of its children. <br>
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
109 * Set to Zero before calling to determine maximum code bit length.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
110 * @param node in: The node to begin searching at.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
111 * @param codeLength out: Variable to hold the longest code bit length found. */
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
112 void HuffmanCodec::maxCodeLength( HuffmanNode const * const node, int &codeLength ){
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
113 // [TL] We must walk each tree node since the codeTable may not contain the set of all leaf nodes.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
114 // bail on NULL node (tree is corrupt).
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
115 if ( node == 0) return;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
116 // Recurse across children if they exist.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
117 if ( node->branch != 0 ){
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
118 maxCodeLength( &(node->branch[0]), codeLength );
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
119 maxCodeLength( &(node->branch[1]), codeLength );
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
120 } else if ( codeLength < node->bitCount ){
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
121 // set codeLength if it's smaller than current node's bitCount.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
122 codeLength = node->bitCount;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
123 }
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
124 }
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
125
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
126 /** Decreases a codeLength to the shortest Huffman code bit length found in the node or any of its children. <br>
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
127 * Set to Zero before calling to determine minimum code bit length.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
128 * @param node in: The node to begin searching at.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
129 * @param codeLength out: Variable to hold the longest code bit length found. */
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
130 void HuffmanCodec::minCodeLength( HuffmanNode const * const node, int &codeLength ){
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
131 /* [TL] Do not optimize under the assumption child nodes will have longer code Lengths!
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
132 * Future subclasses may have trees that diverge from Huffman specs. */
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
133 // bail on NULL node (tree is corrupt).
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
134 if ( node == 0 ) return;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
135 // Recurse across children if they exist.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
136 if ( node->branch != 0 ){
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
137 minCodeLength( &(node->branch[0]), codeLength );
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
138 minCodeLength( &(node->branch[1]), codeLength );
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
139 } else if ( (codeLength > node->bitCount) || (codeLength == 0) ) {
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
140 // set codeLength if it's Zero or larger than current node's bitCount.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
141 codeLength = node->bitCount;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
142 }
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
143 }
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
144
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
145 /** Recursively builds a Huffman Tree. <br>
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
146 * The initial root node should have the following field values: <br>
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
147 * <pre>
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
148 * bitCount : 0
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
149 * code : 0
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
150 * value : -1
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
151 * branch : 0 (NULL)
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
152 * </pre>
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
153 * @param node in/out: branch node of the Huffman Tree.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
154 * @param treeData in: char array containing the Huffman Tree's byte representation.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
155 * @param index in: Current array element to read the next tree node from.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
156 * @param dataLength in: Length of treeData
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
157 * @param codeTable in/out: array of pointers to HuffmanNode structs.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
158 * @param tableLength in: maximum index allowed in the codeTable.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
159 * @return the next index to read from or -1 if an error occurs.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
160 * */
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
161 int HuffmanCodec::buildTree(
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
162 HuffmanNode * node,
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
163 unsigned char const * const treeData,
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
164 int index,
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
165 int dataLength,
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
166 HuffmanNode ** const &codeTable,
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
167 int tableLength
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
168 ){
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
169 if ( index >= dataLength ) return -1;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
170 // Read the branch description bit field
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
171 int desc = treeData[index];
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
172 index++;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
173
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
174 // Create the array that will hold L/R child nodes of this branch.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
175 node->branch = new HuffmanNode[2];
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
176
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
177 // Read the child Nodes for this branch.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
178 for ( int i = 0; i < 2; i++ ){
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
179 // Increase bit count, and update huffman code to match the node's tree position.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
180 node->branch[i].bitCount = node->bitCount + 1;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
181 node->branch[i].code = (node->code << 1) | i; // appends a 0 or 1 depending on L/R branch.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
182 node->branch[i].value = -1; // default value.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
183
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
184 // Test a bit from the branch description (least significant bit == left)
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
185 if ( (desc & (1 << i)) == 0 ){
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
186 // Child node is a branch; Recurse.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
187 if ( (index = buildTree( &(node->branch[i]), treeData, index, dataLength, codeTable, tableLength )) < 0 ) return -1;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
188 // This means the entire left sub tree will be read before the right sub tree gets read.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
189 } else {
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
190 // Read leaf value and map its value/index in the nodes array.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
191 if ( index >= dataLength ) return -1;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
192 // set the nodes huffman code values.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
193 node->branch[i].code = (node->code << 1) | i;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
194 node->branch[i].bitCount = node->bitCount+1;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
195 node->branch[i].value = treeData[index] & 0xff;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
196 // NULL the child node's branch to mark it as a leaf.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
197 node->branch[i].branch = 0;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
198 // buffer overflow check.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
199 if ( (node->branch[i].value >= 0) && (node->branch[i].value <= tableLength ) )
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
200 // store a pointer to the leaf node into the code table at the location of its byte value.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
201 codeTable[ node->branch[i].value ] = &node->branch[i];
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
202 index++;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
203 }
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
204 }
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
205
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
206 return index;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
207 }
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
208
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
209 /** Decodes data read from an input buffer and stores the result in the output buffer.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
210 * @return number of bytes stored in the output buffer or -1 if an error occurs while encoding. */
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
211 int HuffmanCodec::encode(
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
212 unsigned char const * const input, /**< in: pointer to the first byte to encode. */
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
213 unsigned char * const output, /**< out: pointer to an output buffer to store data. */
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
214 int const &inLength, /**< in: number of bytes of input buffer to encoded. */
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
215 int const &outLength /**< in: maximum length of data to output. */
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
216 ) const {
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
217 // setup the bit buffer to output. if not expandable Limit output to input length.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
218 if ( expandable ) writer->outputBuffer( output, outLength );
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
219 else writer->outputBuffer( output, ((inLength + 1) < outLength) ? inLength + 1 : outLength );
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
220
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
221 writer->put( (unsigned char)0 ); // reserve place for padding signal.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
222
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
223 HuffmanNode * node; // temp ptr cache;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
224 for ( int i = 0; i < inLength; i++ ){
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
225 node = codeTable[ 0xff & input[i] ]; //lookup node
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
226 // Put the huffman code into the bit buffer and bail if error occurs.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
227 if ( !writer->put( node->code, node->bitCount ) ) return -1;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
228 }
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
229 int bytesWritten, padding;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
230 if ( writer->finish( bytesWritten, padding ) ){
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
231 // write padding signal byte to begining of stream.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
232 output[0] = (unsigned char)padding;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
233 } else return -1;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
234
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
235 // Reverse the bit order of each byte (Old Huffman Compatibility Mode)
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
236 if ( reverseBits ) for ( int i = 1; i < bytesWritten; i++ ){
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
237 output[i] = reverseMap[ 0xff & output[i] ];
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
238 }
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
239
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
240 return bytesWritten;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
241 } // end function encode
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
242
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
243 /** Decodes data read from an input buffer and stores the result in the output buffer.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
244 * @return number of bytes stored in the output buffer or -1 if an error occurs while decoding. */
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
245 int HuffmanCodec::decode(
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
246 unsigned char const * const input, /**< in: pointer to data that needs decoding. */
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
247 unsigned char * const output, /**< out: pointer to output buffer to store decoded data. */
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
248 int const &inLength, /**< in: number of bytes of input buffer to read. */
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
249 int const &outLength /**< in: maximum length of data to output. */
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
250 ){
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
251 if ( inLength < 1 ) return 0;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
252 int bitsAvailable = ((inLength-1) << 3) - (0xff & input[0]);
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
253 int rIndex = 1; // read index of input buffer.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
254 int wIndex = 0; // write index of output buffer.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
255 char byte = 0; // bits of the current byte.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
256 int bitsLeft = 0; // bits left in byte;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
257
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
258 HuffmanNode * node = root;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
259
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
260 // Traverse the tree, output values.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
261 while ( (bitsAvailable > 0) && (node != 0) ){
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
262
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
263 // Get the next byte if we've run out.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
264 if ( bitsLeft <= 0 ){
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
265 byte = input[rIndex++];
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
266 if ( reverseBits ) byte = reverseMap[ 0xff & byte ];
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
267 bitsLeft = 8;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
268 }
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
269
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
270 // Traverse the tree according to the most significant bit.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
271 node = &(node->branch[ ((byte >> 7) & 0x01) ]);
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
272
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
273 // Is the node Non NULL, and a leaf?
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
274 if ( (node != 0) && (node->branch == 0) ){
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
275 // buffer overflow prevention
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
276 if ( wIndex >= outLength ) return wIndex;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
277 // Output leaf node's value and restart traversal at root node.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
278 output[ wIndex++ ] = (unsigned char)(node->value & 0xff);
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
279 node = root;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
280 }
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
281
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
282 byte <<= 1; // cue up the next bit
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
283 bitsLeft--; // use up one bit of byte
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
284 bitsAvailable--; // decrement total bits left
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
285 }
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
286
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
287 return wIndex;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
288 } // end function decode
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
289
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
290 /** Deletes all sub nodes of a HuffmanNode by traversing and deleting its child nodes.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
291 * @param treeNode pointer to a HuffmanNode whos children will be deleted. */
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
292 void HuffmanCodec::deleteTree( HuffmanNode * treeNode ){
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
293 if ( treeNode == 0 ) return;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
294 if ( treeNode->branch != 0 ){
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
295 deleteTree( &(treeNode->branch[0]) );
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
296 deleteTree( &(treeNode->branch[1]) );
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
297 delete treeNode->branch;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
298 }
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
299 }
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
300
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
301 /** Destructor - frees resources. */
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
302 HuffmanCodec::~HuffmanCodec() {
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
303 delete writer;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
304 //check for resource ownership before deletion
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
305 if ( huffmanResourceOwner() ){
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
306 delete codeTable;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
307 deleteTree( root );
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
308 delete root;
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
309 }
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
310 }
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
311
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
312 /** Enables or Disables backwards bit ordering of bytes.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
313 * @param backwards "true" enables reversed bit order bytes, "false" uses standard byte bit ordering. */
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
314 void HuffmanCodec::reversedBytes( bool backwards ){ reverseBits = backwards; }
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
315
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
316 /** Check the state of backwards bit ordering for bytes.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
317 * @return true: bits within bytes are reversed. false: bits within bytes are normal. */
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
318 bool HuffmanCodec::reversedBytes(){ return reverseBits; }
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
319
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
320 /** Enable or Disable data expansion during encoding.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
321 * @param expandingAllowed "true" allows encoding to expand data. "false" causes failure upon expansion. */
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
322 void HuffmanCodec::allowExpansion( bool expandingAllowed ){ expandable = expandingAllowed; }
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
323
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
324 /** Check the state of data expandability.
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
325 * @return true: data expansion is allowed. false: data is not allowed to expand. */
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
326 bool HuffmanCodec::allowExpansion(){ return expandable; }
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
327
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
328
8b697d30c49f - added huffman lib, now capable of initializing an rcon connection!
Teemu Piippo <crimsondusk64@gmail.com>
parents:
diff changeset
329 }; // end namespace skulltag

mercurial