2 //**************************************************************************
3 //* This file is property of and copyright by the ALICE HLT Project *
4 //* ALICE Experiment at CERN, All rights reserved. *
6 //* Primary Authors: Thorsten Kollegger <kollegge@ikf.uni-frankfurt.de> *
7 //* for The ALICE HLT Project. *
9 //* Permission to use, copy, modify and distribute this software and its *
10 //* documentation strictly for non-commercial purposes is hereby granted *
11 //* without fee, provided that the above copyright notice appears in all *
12 //* copies and that both the copyright notice and this permission notice *
13 //* appear in the supporting documentation. The authors make no claims *
14 //* about the suitability of this software for any purpose. It is *
15 //* provided "as is" without express or implied warranty. *
16 //**************************************************************************
18 /// @file AliHLTHuffman.cxx
19 /// @author Thorsten Kollegger, Matthias Richter
21 /// @brief Huffman code generator/encoder/decoder
23 #include "AliHLTHuffman.h"
30 AliHLTHuffmanNode::AliHLTHuffmanNode()
38 AliHLTHuffmanNode::AliHLTHuffmanNode(const AliHLTHuffmanNode& other)
40 , fValue(other.GetValue())
41 , fWeight(other.GetWeight())
45 AliHLTHuffmanNode& AliHLTHuffmanNode::operator =(const AliHLTHuffmanNode& other) {
46 /// assignment operator
47 if (this==&other) return *this;
48 this->fValue = other.fValue;
49 this->fWeight = other.fWeight;
53 AliHLTHuffmanNode::~AliHLTHuffmanNode() {
56 void AliHLTHuffmanNode::AssignCode(bool bReverse) {
57 /// assign code to this node loop to right and left nodes
58 /// the decoding always has to start from the least significant bit since the
59 /// code length is variable. Thats why the bit corresponding to the parent node
60 /// has to be right of the bit of child nodes, i.e. bits correspond to the
61 /// current code length. For storage in a bit stream however, bits are stored
62 /// in a stream from MSB to LSB and overwrapping to the MSBs of the next byte.
63 /// Here the reverse code is needed and the word of fixed length read from the
64 /// stream needs to be reversed before decoding.
65 /// Note: by changing the AliHLTDataDeflater interface to write from LSB to MSB
66 /// this can be avoided.
69 std::bitset < 64 > v = (this->GetBinaryCode() << 1);
71 GetLeftChild()->SetBinaryCode(this->GetBinaryCodeLength() + 1, v);
73 std::bitset < 64 > v = (this->GetBinaryCode());
74 int codelen=this->GetBinaryCodeLength();
76 GetLeftChild()->SetBinaryCode(codelen + 1, v);
78 GetLeftChild()->AssignCode(bReverse);
80 if (GetRightChild()) {
82 std::bitset < 64 > v = (this->GetBinaryCode() << 1);
84 GetRightChild()->SetBinaryCode(this->GetBinaryCodeLength() + 1, v);
86 std::bitset < 64 > v = (this->GetBinaryCode());
87 int codelen=this->GetBinaryCodeLength();
89 GetRightChild()->SetBinaryCode(codelen + 1, v);
91 GetRightChild()->AssignCode(bReverse);
95 void AliHLTHuffmanNode::Print(Option_t* /*option*/) const {
97 std::cout << "value=" << GetValue() << ", weight=" << GetWeight() << ", length="
98 << GetBinaryCodeLength() << ", code=" << GetBinaryCode().to_string()
100 if (GetLeftChild()) {
101 GetLeftChild()->Print();
103 if (GetRightChild()) {
104 GetRightChild()->Print();
108 ClassImp(AliHLTHuffmanNode)
110 ///////////////////////////////////////////////////////////////////////////////////////////////
112 AliHLTHuffmanTreeNode::AliHLTHuffmanTreeNode()
113 : AliHLTHuffmanNode()
114 , fBinaryCodeLength(0)
122 AliHLTHuffmanTreeNode::AliHLTHuffmanTreeNode(const AliHLTHuffmanTreeNode& other)
123 : AliHLTHuffmanNode(other)
124 , fBinaryCodeLength(other.fBinaryCodeLength)
125 , fBinaryCode(other.fBinaryCode)
126 , fLeft(other.GetLeftChild())
127 , fRight(other.GetRightChild())
132 AliHLTHuffmanTreeNode& AliHLTHuffmanTreeNode::operator =(const AliHLTHuffmanTreeNode& other)
134 /// assignment operator
135 if (&other==this) return *this;
136 this->fBinaryCodeLength = other.GetBinaryCodeLength();
137 this->fBinaryCode = other.GetBinaryCode();
138 this->fLeft = other.GetLeftChild();
139 this->fRight = other.GetRightChild();
140 AliHLTHuffmanNode::operator=(other);
144 AliHLTHuffmanTreeNode::AliHLTHuffmanTreeNode(AliHLTHuffmanNode* l, AliHLTHuffmanNode* r)
145 : AliHLTHuffmanNode()
146 , fBinaryCodeLength(0)
151 SetWeight(l->GetWeight() + r->GetWeight());
152 } else if (l && !r) {
153 SetWeight(l->GetWeight());
154 } else if (!l && r) {
155 SetWeight(r->GetWeight());
159 AliHLTHuffmanTreeNode::~AliHLTHuffmanTreeNode()
164 ClassImp(AliHLTHuffmanTreeNode)
166 ///////////////////////////////////////////////////////////////////////////////////////////////
168 AliHLTHuffmanLeaveNode::AliHLTHuffmanLeaveNode()
169 : AliHLTHuffmanNode()
170 , fBinaryCodeLength(0)
178 AliHLTHuffmanLeaveNode::AliHLTHuffmanLeaveNode(const AliHLTHuffmanLeaveNode& other)
179 : AliHLTHuffmanNode(other)
180 , fBinaryCodeLength(other.fBinaryCodeLength)
181 , fBinaryCode(other.fBinaryCode)
182 , fLeft(other.GetLeftChild())
183 , fRight(other.GetRightChild())
188 AliHLTHuffmanLeaveNode& AliHLTHuffmanLeaveNode::operator =(const AliHLTHuffmanLeaveNode& other)
190 /// assignment operator
191 if (&other==this) return *this;
192 this->fBinaryCodeLength = other.GetBinaryCodeLength();
193 this->fBinaryCode = other.GetBinaryCode();
194 this->fLeft = other.GetLeftChild();
195 this->fRight = other.GetRightChild();
196 AliHLTHuffmanNode::operator=(other);
200 AliHLTHuffmanLeaveNode::~AliHLTHuffmanLeaveNode()
205 ClassImp(AliHLTHuffmanLeaveNode)
207 ///////////////////////////////////////////////////////////////////////////////////////////////
209 AliHLTHuffman::AliHLTHuffman()
218 , fDecodingTopNode(NULL)
223 AliHLTHuffman::AliHLTHuffman(const AliHLTHuffman& other)
226 , fMaxBits(other.fMaxBits)
227 , fMaxValue(other.fMaxValue)
228 , fNodes(other.fNodes)
230 , fReverseCode(other.fReverseCode)
231 , fMaxCodeLength(other.fMaxCodeLength)
233 , fDecodingTopNode(NULL)
238 AliHLTHuffman::AliHLTHuffman(const char* name, UInt_t maxBits)
241 , fMaxValue((((AliHLTUInt64_t) 1) << maxBits) - 1)
242 , fNodes((((AliHLTUInt64_t) 1) << maxBits))
247 , fDecodingTopNode(NULL)
249 /// standard constructor
250 for (AliHLTUInt64_t i = 0; i <= fMaxValue; i++) {
251 fNodes[i].SetValue(i);
255 AliHLTHuffman::~AliHLTHuffman() {
259 const std::bitset<64>& AliHLTHuffman::Encode(const AliHLTUInt64_t v, AliHLTUInt64_t& codeLength) const {
262 if (v <= fMaxValue) {
263 // valid symbol/value
265 // huffman code has been generated
266 codeLength = fNodes[v].GetBinaryCodeLength();
267 return fNodes[v].GetBinaryCode();
269 HLTError("encoder '%s' does not seem to be initialized", GetName());
272 HLTError("encoder %s: value %llu exceeds range of %d bits", GetName(), v, GetMaxBits());
275 static const std::bitset<64> dummy;
279 Bool_t AliHLTHuffman::DecodeLSB(std::bitset<64> bits, AliHLTUInt64_t& value,
280 AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const
283 AliHLTHuffmanNode* currNode = fHuffTopNode;
284 if (!currNode) return kFALSE;
285 if (currNode->GetValue() >= 0) {
286 // handle case with just one node - also quite unlikely
287 value = currNode->GetValue();
291 if (bits[0] && currNode->GetLeftChild()) {
292 // follow left branch
293 currNode = currNode->GetLeftChild();
295 if (currNode && currNode->GetValue() >= 0) {
296 value = currNode->GetValue();
298 codeLength = currNode->GetBinaryCodeLength();
303 if (!bits[0] && currNode->GetRightChild()) {
304 currNode = currNode->GetRightChild();
306 if (currNode && currNode->GetValue() >= 0) {
307 value = currNode->GetValue();
309 codeLength = currNode->GetBinaryCodeLength();
316 value = ((AliHLTUInt64_t)1) << 63;
320 Bool_t AliHLTHuffman::DecodeMSB(std::bitset<64> bits, AliHLTUInt64_t& value,
321 AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const
324 AliHLTHuffmanNode* currNode = fHuffTopNode;
325 if (!currNode) return kFALSE;
326 if (currNode->GetValue() >= 0) {
327 // handle case with just one node - also quite unlikely
328 value = currNode->GetValue();
332 if (bits[63] && currNode->GetLeftChild()) {
333 // follow left branch
334 currNode = currNode->GetLeftChild();
336 if (currNode && currNode->GetValue() >= 0) {
337 value = currNode->GetValue();
339 codeLength = currNode->GetBinaryCodeLength();
344 if (!bits[63] && currNode->GetRightChild()) {
345 currNode = currNode->GetRightChild();
347 if (currNode && currNode->GetValue() >= 0) {
348 value = currNode->GetValue();
350 codeLength = currNode->GetBinaryCodeLength();
357 value = ((AliHLTUInt64_t)1) << 63;
361 Bool_t AliHLTHuffman::FastDecodeMSB(std::bitset<64> bits, AliHLTUInt64_t& value,
362 AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const
364 // huffman decoding using the binary node map
365 HLTFatal("this function needs to be tested and commisioned");
366 AliHuffmanDecodingNode* currNode = fDecodingTopNode;
367 if (!currNode) return kFALSE;
368 if (currNode->fValue >= 0) {
369 // handle case with just one node - also quite unlikely
370 value = currNode->fValue;
374 if (bits[63] && currNode->fLeft) {
375 // follow left branch
376 currNode = currNode->fLeft;
378 if (currNode && currNode->fValue >= 0) {
379 value = currNode->fValue;
381 codeLength = currNode->fBinaryCodeLength;
386 if (!bits[63] && currNode->fRight) {
387 currNode = currNode->fRight;
389 if (currNode && currNode->fValue >= 0) {
390 value = currNode->fValue;
392 codeLength = currNode->fBinaryCodeLength;
399 value = ((AliHLTUInt64_t)1) << 63;
403 Bool_t AliHLTHuffman::AddTrainingValue(const AliHLTUInt64_t value,
404 const Float_t weight) {
405 if (value > fMaxValue) {
406 /* TODO: ERROR message */
409 fNodes[value].AddWeight(weight);
413 Bool_t AliHLTHuffman::GenerateHuffmanTree() {
414 // insert pointer to nodes into ordered structure to build tree
415 std::multiset<AliHLTHuffmanNode*, AliHLTHuffmanNode::less> nodeCollection;
416 // std::copy(fNodes.begin(), fNodes.end(),
417 // std::inserter(freq_coll, freq_coll.begin()));
418 for (std::vector<AliHLTHuffmanLeaveNode>::iterator i = fNodes.begin(); i
419 != fNodes.end(); ++i) {
420 nodeCollection.insert(&(*i));
422 while (nodeCollection.size() > 1) {
423 // insert new node into structure, combining the two with lowest probability
424 AliHLTHuffmanNode* node=new AliHLTHuffmanTreeNode(*nodeCollection.begin(), *++nodeCollection.begin());
425 if (!node) return kFALSE;
426 nodeCollection.insert(node);
427 nodeCollection.erase(nodeCollection.begin());
428 nodeCollection.erase(nodeCollection.begin());
431 fHuffTopNode = *nodeCollection.begin();
432 fHuffTopNode->AssignCode(fReverseCode);
437 void AliHLTHuffman::Print(Option_t* option) const {
438 std::cout << GetName() << endl;
439 bool bPrintShort=strcmp(option, "full")!=0;
440 if (fHuffTopNode && !bPrintShort) {
441 std::cout << "Huffman tree:" << endl;
442 fHuffTopNode->Print();
444 Double_t uncompressedSize = 0;
445 Double_t compressedSize = 0;
446 Double_t totalWeight = 0;
448 std::cout << std::endl << "Huffman codes:" << std::endl;
449 for (AliHLTUInt64_t i = 0; i <= fMaxValue; i++) {
450 if (!bPrintShort) fNodes[i].Print();
451 totalWeight += fNodes[i].GetWeight();
452 uncompressedSize += fNodes[i].GetWeight() * fMaxBits;
453 compressedSize += fNodes[i].GetWeight()
454 * fNodes[i].GetBinaryCodeLength();
456 if (uncompressedSize > 0) {
457 std::cout << "compression ratio: " << compressedSize
458 / uncompressedSize << std::endl;
459 std::cout << "<bits> uncompressed: " << uncompressedSize / totalWeight
461 std::cout << "<bits> compressed: " << compressedSize / totalWeight
466 AliHLTHuffman& AliHLTHuffman::operator =(const AliHLTHuffman& other) {
467 if (this==&other) return *this;
468 fMaxValue = other.fMaxValue;
469 fNodes = other.fNodes;
475 bool AliHLTHuffman::CheckConsistency() const
478 cout << "huffman table not yet generated" << endl;
481 for (AliHLTUInt64_t v=0; v<GetMaxValue(); v++) {
482 AliHLTUInt64_t codeLength=0;
483 std::bitset<64> code=AliHLTHuffman::Encode(v, codeLength);
484 AliHLTUInt64_t readback=0;
485 AliHLTUInt32_t readbacklen=0;
486 AliHLTUInt32_t readbackcodelen=0;
488 code<<=64-codeLength;
489 if (!DecodeMSB(code, readback, readbacklen, readbackcodelen)) {
490 cout << "Decode failed" << endl;
494 if (!DecodeLSB(code, readback, readbacklen, readbackcodelen)) {
495 cout << "Decode failed" << endl;
500 cout << "readback of value " << v << " code length " << codeLength << " failed: got " << readback << " code length " << readbackcodelen << endl;
507 UInt_t AliHLTHuffman::InitMaxCodeLength()
509 // loop over leave nodes and set maximum code length
511 for (std::vector<AliHLTHuffmanLeaveNode>::const_iterator node=fNodes.begin();
512 node!=fNodes.end(); node++) {
513 if (fMaxCodeLength<node->GetBinaryCodeLength())
514 fMaxCodeLength=node->GetBinaryCodeLength();
516 return fMaxCodeLength;
519 int AliHLTHuffman::EnableDecodingMap()
521 // build decoder nodes from node tree
522 fDecodingTopNode=NULL;
523 fDecodingNodes.clear();
524 if (fNodes.size()==0) {
527 fDecodingNodes.reserve(2*fNodes.size());
528 fDecodingTopNode=BuildDecodingNode(fHuffTopNode, fDecodingNodes);
529 if (!fDecodingTopNode) {
530 fDecodingNodes.clear();
532 HLTError("decoder nodes created sucessfully");
537 AliHLTHuffman::AliHuffmanDecodingNode* AliHLTHuffman::BuildDecodingNode(AliHLTHuffmanNode* node, vector<AliHuffmanDecodingNode>& decodernodes) const
539 // build and add decoder node structure corresponding to huffman node
541 HLTError("invalid node pointer");
544 for (vector<AliHuffmanDecodingNode>::iterator i=decodernodes.begin();
545 i!=decodernodes.end(); i++) {
546 if (i->fParent==node) {
547 HLTError("node %p already existing in decoder nodes", node);
552 AliHuffmanDecodingNode* decodernode=NULL;
553 if (decodernodes.size()+1>decodernodes.capacity()) {
554 HLTError("initial size of array too small, can not add more nodes because pointers will become invalid when growing vector");
556 AliHuffmanDecodingNode dn;
558 dn.fValue=node->GetValue();
561 dn.fBinaryCodeLength=0;
562 decodernodes.push_back(dn);
563 decodernode=&(decodernodes.back());
566 if (decodernode && decodernode->fValue<0) {
567 decodernode->fRight=BuildDecodingNode(node->GetRightChild(), decodernodes);
568 decodernode->fLeft=BuildDecodingNode(node->GetLeftChild(), decodernodes);
569 if (decodernode->fLeft==NULL || decodernode->fRight==0) {
570 HLTError("failed to build corresponding decoder node for node %p", node);
578 ClassImp(AliHLTHuffman)