98 constexpr int maxNodesNeeded= 256 + 255;
99 Node nodePool[maxNodesNeeded];
104 struct cmpHN {
bool operator()(Node* l, Node* r) {
return (l->frequency > r->frequency); } };
113 for (std::size_t i = 0; i < 256 ; ++i)
114 if( (
symbols + i)->frequency > 0 )
115 underlyingNodeVector.
push_back(
new (nodePool + npNext++) Node(
symbols + i) );
118ALIB_DBG( dbgAllValuesAreSame= (sortedNodes.size() == 1); )
120 while (sortedNodes.size() > 1)
123 Node* left = sortedNodes.top(); sortedNodes.pop();
124 Node* right= sortedNodes.top(); sortedNodes.pop();
128 sortedNodes.push(
new ( nodePool + npNext++ ) Node(left, right) );
131 tree= sortedNodes.top();
132 ALIB_ASSERT_ERROR( npNext <= maxNodesNeeded ,
"BITBUFFER/AC/HFMN",
"This can never happen" )
145 stack[0] = Stack{ tree, 0 };
148TEMP_PT(
Log_Warning(
"------ Huffman Encoding Table ----------") )
153 auto* node= stack[depth].node;
162 bw.
Write<9>( 1 |
static_cast<unsigned int>(node->getSymbol() -
symbols) << 1 );
165 node->getSymbol()->wordLength= depth;
166 for(
int i= 0 ; i <= wordNo ; ++i )
167 node->getSymbol()->words[i]= words[i];
171 Lox_Warning(
"HM I: {:3}: {:<15} (len={!ATAB:2}, freq={:>5})",
174 node->symbol->wordLength,
175 node->symbol->frequency ) )
178 words[wordNo]&= ~(1 << ( bitNo ) );
187 if( stack[depth].walked == 0)
189 stack[depth].walked++;
190 stack[depth+1]= Stack{ node->getLeft() , 0};
196 if( stack[depth].walked == 1)
198 stack[depth].walked++;
199 words[wordNo] |= (1 << ( bitNo ) );
200 stack[depth+1]= Stack{ node->getRight() , 0};
206 words[wordNo]&= ~(1 << ( bitNo ) );
209TEMP_PT(
Log_Warning(
"------End of Huffman Encoding Table ----------") )
215TEMP_PT(
Log_Warning(
"------ Huffman Decoding Table ----------") )
225 stack[depth= 0]= Stack{ &
tree, 0 };
228 auto* node= stack[depth].node;
232 node->symbol= uint8_t(
br.
Read<8>());
239TEMP_PT( dbgWord.DeleteEnd(1); )
244 if( stack[depth].read == 0)
248TEMP_PT( dbgWord <<
'0'; )
249 stack[depth+1]= Stack{ node->left , 0 };
255 if( stack[depth].read == 1)
258TEMP_PT( dbgWord <<
'1'; )
260 stack[depth+1]= Stack{ node->right , 0 };
265TEMP_PT( dbgWord.DeleteEnd(1); )
271TEMP_PT(
Log_Warning(
"------End of Huffman Decoding Table ----------") )