ALib C++ Library
Library Version: 2510 R0
Documentation generated by doxygen
Loading...
Searching...
No Matches
huffman.cpp
1// #################################################################################################
2// ALib C++ Library
3//
4// Copyright 2013-2025 A-Worx GmbH, Germany
5// Published under 'Boost Software License' (a free software license, see LICENSE.txt)
6// #################################################################################################
7#include "alib_precompile.hpp"
8#if !defined(ALIB_C20_MODULES) || ((ALIB_C20_MODULES != 0) && (ALIB_C20_MODULES != 1))
9# error "Symbol ALIB_C20_MODULES has to be given to the compiler as either 0 or 1"
10#endif
11#if ALIB_C20_MODULES
12 module;
13#endif
14// ====================================== Global Fragment ======================================
16
17// =========================================== Module ==========================================
18#if ALIB_C20_MODULES
19 module ALib.BitBuffer;
21#else
23# include "ALib.BitBuffer.H"
24#endif
25
26namespace alib { namespace bitbuffer { namespace ac_v1 {
27
28#if !DOXYGEN
29//#define TEMP_PT(...) __VA_ARGS__
30# define TEMP_PT(...)
31#endif
32
33#if !DOXYGEN
34namespace
35{
36 /// Internal struct representing nodes of the huffman code tree.
37 class Node
38 {
39 using Symbol= HuffmanEncoder::Symbol;
40
41 protected:
42 /// Either a pointer to a left subtree or to a symbol.
43 /// The latter makes the node a leaf.
44 union LeftPointer
45 {
46 Symbol* symbol; ///< The symbol represented by this node (if not \c nullptr).
47 Node* left; ///< The left subtree.
48
49 LeftPointer() = default; ///< Non-initializing default constructor.
50
51 /// Constructs this union with a symbol pointer.
52 /// @param s The symbol to set.
53 LeftPointer( Symbol* s )
54 : symbol( s )
55 {}
56
57 /// Constructs this union with a cursor.
58 /// @param l The node to set.
59 LeftPointer( Node* l )
60 : left ( l )
61 {}
62 };
63
64 LeftPointer left; ///< If #right set, then this is a pointer to the left subtree,
65 ///< otherwise a pointer to a symbol.
66 Node* right; ///< The right subtree.
67
68
69 public:
70 size_t frequency; ///< The frequency of the symbol or the sum of the two subtrees.
71
72 /// Default constructor used when defining arrays of nodes on stack memory.
73 Node() = default;
74
75 /// Constructs a node representing a symbol (leaf).
76 /// Left and right pointers are set to nullptr
77 /// @param s Pointer to the symbol in #symbols, that this node represents.
78 Node(Symbol* s)
79 : left (s)
80 , right (nullptr)
81 , frequency (s->frequency)
82 {}
83
84 /// Constructs a node as an internal non-leaf node.
85 /// Left and right pointers are set to as given.
86 /// @param l Pointer to the left node.
87 /// @param r Pointer to the right node.
88 Node(Node* l, Node* r)
89 : left (l)
90 , right (r)
91 , frequency (l->frequency + r->frequency)
92 {}
93
94 bool isLeaf() const { return right == nullptr; } ///< Determines if this a leaf node.
95 ///< @returns \c true if this is a leaf node.
96 Symbol* getSymbol() const { return left.symbol; } ///< Must be called only for leaf nodes.
97 ///< @returns The pointer to the symbol.
98 Node* getLeft() const { return left.left; } ///< Must be called only for non-leaf nodes.
99 ///< @returns The left node.
100 Node* getRight() const { return right; } ///< @returns The right node.
101 }; //struct Node
102} // anonymous namespace
103
104#endif
105
106
108{
109 constexpr int maxNodesNeeded= 256 + 255;
110 Node nodePool[maxNodesNeeded];
111
112 // buildTree
113 Node* tree;
114 {
115 struct cmpHN { bool operator()(Node* l, Node* r) { return (l->frequency > r->frequency); } };
116
117 // create a list of nodes, sorted by frequency (least in front)
118 // Note: for this, we first create fixed array on the stack, where we fill the
119 // nodes unsorted. Then we move this into the priority queue, what sorts them
120 // once. (unfortunately the move copies the array, but still it is faster than
121 // if the heap was sorted with each insert)
122 int npNext= 0;
123 FixedCapacityVector<Node*, 256> underlyingNodeVector;
124 for (std::size_t i = 0; i < 256 ; ++i)
125 if( (symbols + i)->frequency > 0 )
126 underlyingNodeVector.push_back( new (nodePool + npNext++) Node(symbols + i) );
127 FixedSizePriorityQueue<Node*, 256, cmpHN> sortedNodes(cmpHN(), std::move(underlyingNodeVector));
128
129ALIB_DBG( dbgAllValuesAreSame= (sortedNodes.size() == 1); )
130 // Merge two front nodes into one, until one node remains
131 while (sortedNodes.size() > 1)
132 {
133 // Extract two least freq nodes
134 Node* left = sortedNodes.top(); sortedNodes.pop();
135 Node* right= sortedNodes.top(); sortedNodes.pop();
136
137 // New internal node with frequency equal to the sum of the two nodes frequencies.
138 // The two extracted nodes become left and right children
139 sortedNodes.push(new ( nodePool + npNext++ ) Node(left, right) );
140 }
141
142 tree= sortedNodes.top();
143 ALIB_ASSERT_ERROR( npNext <= maxNodesNeeded , "BITBUFFER/AC/HFMN", "This can never happen" )
144 }
145
146 // generate codes and write tree information to bit buffer
147 {
148 struct Stack
149 {
150 Node* node;
151 int walked;
152 };
153
154 int depth = 0;
155 Stack stack[MAX_CODE_LENGTH];
156 stack[0] = Stack{ tree, 0 };
157 uint32_t words[MAX_WORDS] = {};
158
159TEMP_PT(Log_Warning("------ Huffman Encoding Table ----------") )
160
161 // 'recursion loop'
162 while(depth>=0)
163 {
164 auto* node= stack[depth].node;
165
166 auto wordNo= depth / WORD_SIZE;
167 auto bitNo = depth % WORD_SIZE;
168
169 // leaf?
170 if( node->isLeaf() )
171 {
172 // write '1' for leaf and symbol value
173 bw.Write<9>( 1 | static_cast<unsigned int>(node->getSymbol() - symbols) << 1 );
174
175 // store word length and words to symbol's data
176 node->getSymbol()->wordLength= depth;
177 for( int i= 0 ; i <= wordNo ; ++i )
178 node->getSymbol()->words[i]= words[i];
179
180TEMP_PT( NString512 bits; bits << Bin(node->symbol->words[0], node->symbol->wordLength);
181 bits.Reverse();
182 Lox_Warning("HM I: {:3}: {:<15} (len={!ATAB:2}, freq={:>5})",
183 (node->symbol - symbols),
184 bits,
185 node->symbol->wordLength,
186 node->symbol->frequency ) )
187
188 // clear last bit and step up
189 words[wordNo]&= ~(1 << ( bitNo ) );
190 --depth;
191 continue;
192 }
193
194 // write '0' for not being a leave
195 bw.Write<1>( 0u );
196
197 // process left child
198 if( stack[depth].walked == 0)
199 {
200 stack[depth].walked++;
201 stack[depth+1]= Stack{ node->getLeft() , 0};
202 depth++;
203 continue;
204 }
205
206 // process right child
207 if( stack[depth].walked == 1)
208 {
209 stack[depth].walked++;
210 words[wordNo] |= (1 << ( bitNo ) );
211 stack[depth+1]= Stack{ node->getRight() , 0};
212 depth++;
213 continue;
214 }
215
216 // clear last bit and step up
217 words[wordNo]&= ~(1 << ( bitNo ) );
218 --depth;
219 }
220TEMP_PT( Log_Warning("------End of Huffman Encoding Table ----------") )
221 }
222}
223
225{
226TEMP_PT( Log_Warning("------ Huffman Decoding Table ----------") )
227TEMP_PT( String512 dbgWord; )
228 struct Stack
229 {
230 Node* node;
231 int read; // 0: none, 1: left, 2: both
232 };
233
234 int depth;
236 stack[depth= 0]= Stack{ &tree, 0 };
237 while(depth>=0)
238 {
239 auto* node= stack[depth].node;
240 // leaf?
241 if( br.Read<1>() )
242 {
243 node->symbol= uint8_t(br.Read<8>());
244TEMP_PT( Log_Warning("HM D: {:3}: {:5} (len={})",
245 (node->symbol),
246 dbgWord,
247 dbgWord.Length() ) )
248
249 --depth;
250TEMP_PT( dbgWord.DeleteEnd(1); )
251 continue;
252 }
253
254 // left 'recursion'
255 if( stack[depth].read == 0)
256 {
257 ++stack[depth].read;
258 node->left= new ( nodePool + npNext++ ) Node();
259TEMP_PT( dbgWord << '0'; )
260 stack[depth+1]= Stack{ node->left , 0 };
261 ++depth;
262 continue;
263 }
264
265 // right 'recursion'
266 if( stack[depth].read == 1)
267 {
268 ++stack[depth].read;
269TEMP_PT( dbgWord << '1'; )
270 node->right= new ( nodePool + npNext++ ) Node();
271 stack[depth+1]= Stack{ node->right , 0 };
272 ++depth;
273 continue;
274 }
275
276TEMP_PT( dbgWord.DeleteEnd(1); )
277 --depth;
278 }
279
280ALIB_ASSERT_ERROR( npNext <= MAX_NODES, "BITBUFFER/AC/HFMN", "This can never happen" )
281
282TEMP_PT( Log_Warning("------End of Huffman Decoding Table ----------") )
283}
284
285
286
287
288#undef TEMP_PT
289
290}}} // namespace [alib::bitbuffer::ac_v1]
291
int npNext
The next node in nodePool to use.
Definition huffman.inl:138
static constexpr int MAX_NODES
The maximum number of nodes in the tree.
Definition huffman.inl:133
Node tree
The root node of the symbol tree.
Definition huffman.inl:136
Node nodePool[MAX_NODES]
Pre-allocated node objects.
Definition huffman.inl:137
BitReader & br
The bit reader given in the constructor.
Definition huffman.inl:135
BitWriter & bw
The bit writer to use for encoding the data.
Definition huffman.inl:49
static constexpr int MAX_CODE_LENGTH
Definition huffman.inl:35
Symbol symbols[256]
The symbol table.
Definition huffman.inl:50
ALIB_DLL void Generate()
Generates the huffman encoding table and writes this information to the bit writer.
Definition huffman.cpp:107
#define Log_Warning(...)
#define ALIB_DBG(...)
Definition alib.inl:836
#define ALIB_ASSERT_ERROR(cond, domain,...)
Definition alib.inl:1049
#define Lox_Warning(...)
std::priority_queue< T, FixedCapacityVector< T, TSize >, TCompare > FixedSizePriorityQueue
LocalString< 512 > String512
Type alias name for TLocalString<character,512>.
containers::FixedCapacityVector< T, TSize > FixedCapacityVector
Type alias in namespace alib.
NLocalString< 512 > NString512
Type alias name for TLocalString<nchar,512>.
strings::TBin< character > Bin
Type alias in namespace alib.
Definition format.inl:572
Internal struct representing nodes of the huffman code tree.
Definition huffman.inl:120