109 constexpr int maxNodesNeeded= 256 + 255;
110 Node nodePool[maxNodesNeeded];
115 struct cmpHN {
bool operator()(Node* l, Node* r) {
return (l->frequency > r->frequency); } };
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) );
129ALIB_DBG( dbgAllValuesAreSame= (sortedNodes.size() == 1); )
131 while (sortedNodes.size() > 1)
134 Node* left = sortedNodes.top(); sortedNodes.pop();
135 Node* right= sortedNodes.top(); sortedNodes.pop();
139 sortedNodes.push(
new ( nodePool + npNext++ ) Node(left, right) );
142 tree= sortedNodes.top();
143 ALIB_ASSERT_ERROR( npNext <= maxNodesNeeded ,
"BITBUFFER/AC/HFMN",
"This can never happen" )
156 stack[0] = Stack{ tree, 0 };
159TEMP_PT(
Log_Warning(
"------ Huffman Encoding Table ----------") )
164 auto* node= stack[depth].node;
173 bw.Write<9>( 1 |
static_cast<unsigned int>(node->getSymbol() -
symbols) << 1 );
176 node->getSymbol()->wordLength= depth;
177 for(
int i= 0 ; i <= wordNo ; ++i )
178 node->getSymbol()->words[i]= words[i];
180TEMP_PT(
NString512 bits; bits <<
Bin(node->symbol->words[0], node->symbol->wordLength);
182 Lox_Warning(
"HM I: {:3}: {:<15} (len={!ATAB:2}, freq={:>5})",
185 node->symbol->wordLength,
186 node->symbol->frequency ) )
189 words[wordNo]&= ~(1 << ( bitNo ) );
198 if( stack[depth].walked == 0)
200 stack[depth].walked++;
201 stack[depth+1]= Stack{ node->getLeft() , 0};
207 if( stack[depth].walked == 1)
209 stack[depth].walked++;
210 words[wordNo] |= (1 << ( bitNo ) );
211 stack[depth+1]= Stack{ node->getRight() , 0};
217 words[wordNo]&= ~(1 << ( bitNo ) );
220TEMP_PT(
Log_Warning(
"------End of Huffman Encoding Table ----------") )
226TEMP_PT(
Log_Warning(
"------ Huffman Decoding Table ----------") )
236 stack[depth= 0]= Stack{ &
tree, 0 };
239 auto* node= stack[depth].node;
243 node->symbol= uint8_t(
br.Read<8>());
250TEMP_PT( dbgWord.DeleteEnd(1); )
255 if( stack[depth].read == 0)
259TEMP_PT( dbgWord <<
'0'; )
260 stack[depth+1]= Stack{ node->left , 0 };
266 if( stack[depth].read == 1)
269TEMP_PT( dbgWord <<
'1'; )
271 stack[depth+1]= Stack{ node->right , 0 };
276TEMP_PT( dbgWord.DeleteEnd(1); )
282TEMP_PT(
Log_Warning(
"------End of Huffman Decoding Table ----------") )