code cleanup: renaming functions; adding prototype code for later development; no...
[u/mrichter/AliRoot.git] / HLT / BASE / AliHLTHuffman.cxx
CommitLineData
6a1b3945 1// $Id$
2//**************************************************************************
3//* This file is property of and copyright by the ALICE HLT Project *
4//* ALICE Experiment at CERN, All rights reserved. *
5//* *
6//* Primary Authors: Thorsten Kollegger <kollegge@ikf.uni-frankfurt.de> *
7//* for The ALICE HLT Project. *
8//* *
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//**************************************************************************
17
18/// @file AliHLTHuffman.cxx
19/// @author Thorsten Kollegger, Matthias Richter
20/// @date 2011-08-14
21/// @brief Huffman code generator/encoder/decoder
22
23#include "AliHLTHuffman.h"
24
25#include <iostream>
26#include <set>
27#include <bitset>
28#include <algorithm>
29
30AliHLTHuffmanNode::AliHLTHuffmanNode()
31 : TObject()
32 , fValue(-1)
33 , fWeight(0.)
34{
35 // nop
36}
37
38AliHLTHuffmanNode::AliHLTHuffmanNode(const AliHLTHuffmanNode& other)
39 : TObject()
40 , fValue(other.GetValue())
41 , fWeight(other.GetWeight())
42{
43}
44
45AliHLTHuffmanNode& AliHLTHuffmanNode::operator =(const AliHLTHuffmanNode& other) {
46 /// assignment operator
5c8ae5fb 47 if (this==&other) return *this;
6a1b3945 48 this->fValue = other.fValue;
49 this->fWeight = other.fWeight;
50 return *this;
51}
52
53AliHLTHuffmanNode::~AliHLTHuffmanNode() {
54}
55
9409b4b1 56void AliHLTHuffmanNode::AssignCode(bool bReverse) {
6a1b3945 57 /// assign code to this node loop to right and left nodes
9409b4b1 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.
6a1b3945 67 if (GetLeftChild()) {
9409b4b1 68 if (bReverse) {
6a1b3945 69 std::bitset < 64 > v = (this->GetBinaryCode() << 1);
70 v.set(0);
71 GetLeftChild()->SetBinaryCode(this->GetBinaryCodeLength() + 1, v);
9409b4b1 72 } else {
73 std::bitset < 64 > v = (this->GetBinaryCode());
74 int codelen=this->GetBinaryCodeLength();
75 v.set(codelen);
76 GetLeftChild()->SetBinaryCode(codelen + 1, v);
77 }
78 GetLeftChild()->AssignCode(bReverse);
6a1b3945 79 }
80 if (GetRightChild()) {
9409b4b1 81 if (bReverse) {
6a1b3945 82 std::bitset < 64 > v = (this->GetBinaryCode() << 1);
83 v.reset(0);
84 GetRightChild()->SetBinaryCode(this->GetBinaryCodeLength() + 1, v);
9409b4b1 85 } else {
86 std::bitset < 64 > v = (this->GetBinaryCode());
87 int codelen=this->GetBinaryCodeLength();
88 v.reset(codelen);
89 GetRightChild()->SetBinaryCode(codelen + 1, v);
90 }
91 GetRightChild()->AssignCode(bReverse);
6a1b3945 92 }
93}
94
95void AliHLTHuffmanNode::Print(Option_t* /*option*/) const {
96 /// print info
97 std::cout << "value=" << GetValue() << ", weight=" << GetWeight() << ", length="
98 << GetBinaryCodeLength() << ", code=" << GetBinaryCode().to_string()
99 << std::endl;
100 if (GetLeftChild()) {
101 GetLeftChild()->Print();
102 }
103 if (GetRightChild()) {
104 GetRightChild()->Print();
105 }
106}
107
108ClassImp(AliHLTHuffmanNode)
109
110///////////////////////////////////////////////////////////////////////////////////////////////
111
112AliHLTHuffmanTreeNode::AliHLTHuffmanTreeNode()
113 : AliHLTHuffmanNode()
114 , fBinaryCodeLength(0)
115 , fBinaryCode(0)
116 , fLeft(NULL)
117 , fRight(NULL)
118{
119 // nop
120}
121
122AliHLTHuffmanTreeNode::AliHLTHuffmanTreeNode(const AliHLTHuffmanTreeNode& other)
6e848d29 123 : AliHLTHuffmanNode(other)
6a1b3945 124 , fBinaryCodeLength(other.fBinaryCodeLength)
125 , fBinaryCode(other.fBinaryCode)
126 , fLeft(other.GetLeftChild())
127 , fRight(other.GetRightChild())
128{
129
130}
131
132AliHLTHuffmanTreeNode& AliHLTHuffmanTreeNode::operator =(const AliHLTHuffmanTreeNode& other)
133{
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);
141 return *this;
142}
143
144AliHLTHuffmanTreeNode::AliHLTHuffmanTreeNode(AliHLTHuffmanNode* l, AliHLTHuffmanNode* r)
145 : AliHLTHuffmanNode()
146 , fBinaryCodeLength(0)
147 , fBinaryCode(0)
148 , fLeft(l)
149 , fRight(r) {
150 if (l && r) {
151 SetWeight(l->GetWeight() + r->GetWeight());
152 } else if (l && !r) {
153 SetWeight(l->GetWeight());
154 } else if (!l && r) {
155 SetWeight(r->GetWeight());
156 }
157}
158
159AliHLTHuffmanTreeNode::~AliHLTHuffmanTreeNode()
160{
161 // nop
162}
163
164ClassImp(AliHLTHuffmanTreeNode)
165
166///////////////////////////////////////////////////////////////////////////////////////////////
167
168AliHLTHuffmanLeaveNode::AliHLTHuffmanLeaveNode()
169 : AliHLTHuffmanNode()
170 , fBinaryCodeLength(0)
171 , fBinaryCode(0)
172 , fLeft(NULL)
173 , fRight(NULL)
174{
175 // nop
176}
177
178AliHLTHuffmanLeaveNode::AliHLTHuffmanLeaveNode(const AliHLTHuffmanLeaveNode& other)
6e848d29 179 : AliHLTHuffmanNode(other)
6a1b3945 180 , fBinaryCodeLength(other.fBinaryCodeLength)
181 , fBinaryCode(other.fBinaryCode)
182 , fLeft(other.GetLeftChild())
183 , fRight(other.GetRightChild())
184{
185
186}
187
188AliHLTHuffmanLeaveNode& AliHLTHuffmanLeaveNode::operator =(const AliHLTHuffmanLeaveNode& other)
189{
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);
197 return *this;
198}
199
200AliHLTHuffmanLeaveNode::~AliHLTHuffmanLeaveNode()
201{
202 // nop
203}
204
205ClassImp(AliHLTHuffmanLeaveNode)
206
207///////////////////////////////////////////////////////////////////////////////////////////////
208
209AliHLTHuffman::AliHLTHuffman()
210 : TNamed()
211 , fMaxBits(0)
212 , fMaxValue(0)
213 , fNodes(0)
214 , fHuffTopNode(NULL)
9409b4b1 215 , fReverseCode(true)
6e848d29 216 , fMaxCodeLength(0)
7227b364 217 , fDecodingNodes()
218 , fDecodingTopNode(NULL)
6a1b3945 219{
220 /// nop
221}
222
223AliHLTHuffman::AliHLTHuffman(const AliHLTHuffman& other)
224 : TNamed()
225 , AliHLTLogging()
226 , fMaxBits(other.fMaxBits)
227 , fMaxValue(other.fMaxValue)
228 , fNodes(other.fNodes)
9409b4b1 229 , fHuffTopNode(NULL)
230 , fReverseCode(other.fReverseCode)
6e848d29 231 , fMaxCodeLength(other.fMaxCodeLength)
7227b364 232 , fDecodingNodes()
233 , fDecodingTopNode(NULL)
9409b4b1 234{
6a1b3945 235 /// nop
236}
237
238AliHLTHuffman::AliHLTHuffman(const char* name, UInt_t maxBits)
239 : TNamed(name, name)
240 , fMaxBits(maxBits)
241 , fMaxValue((((AliHLTUInt64_t) 1) << maxBits) - 1)
242 , fNodes((((AliHLTUInt64_t) 1) << maxBits))
243 , fHuffTopNode(NULL)
9409b4b1 244 , fReverseCode(true)
6e848d29 245 , fMaxCodeLength(0)
7227b364 246 , fDecodingNodes()
247 , fDecodingTopNode(NULL)
6a1b3945 248 {
249 /// standard constructor
250 for (AliHLTUInt64_t i = 0; i <= fMaxValue; i++) {
251 fNodes[i].SetValue(i);
252 }
253}
254
255AliHLTHuffman::~AliHLTHuffman() {
256 /// destructor, nop
257}
258
259const std::bitset<64>& AliHLTHuffman::Encode(const AliHLTUInt64_t v, AliHLTUInt64_t& codeLength) const {
260 /// encode a value
261 codeLength = 0;
262 if (v <= fMaxValue) {
263 // valid symbol/value
264 if (fHuffTopNode) {
265 // huffman code has been generated
266 codeLength = fNodes[v].GetBinaryCodeLength();
267 return fNodes[v].GetBinaryCode();
268 } else {
269 HLTError("encoder '%s' does not seem to be initialized", GetName());
270 }
271 } else {
272 HLTError("encoder %s: value %llu exceeds range of %d bits", GetName(), v, GetMaxBits());
273 }
274
275 static const std::bitset<64> dummy;
276 return dummy;
277}
278
7227b364 279Bool_t AliHLTHuffman::DecodeLSB(std::bitset<64> bits, AliHLTUInt64_t& value,
280 AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const
281{
6e848d29 282 // huffman decoding
6a1b3945 283 AliHLTHuffmanNode* currNode = fHuffTopNode;
cac77957 284 if (!currNode) return kFALSE;
6a1b3945 285 if (currNode->GetValue() >= 0) {
286 // handle case with just one node - also quite unlikely
287 value = currNode->GetValue();
288 return kTRUE;
289 }
290 while (currNode) {
291 if (bits[0] && currNode->GetLeftChild()) {
292 // follow left branch
293 currNode = currNode->GetLeftChild();
294 bits >>= 1;
295 if (currNode->GetValue() >= 0) {
296 value = currNode->GetValue();
9409b4b1 297 length = fMaxBits;
298 codeLength = currNode->GetBinaryCodeLength();
6a1b3945 299 return kTRUE;
300 }
9409b4b1 301 continue;
6a1b3945 302 }
303 if (!bits[0] && currNode->GetRightChild()) {
304 currNode = currNode->GetRightChild();
305 bits >>= 1;
306 if (currNode->GetValue() >= 0) {
307 value = currNode->GetValue();
9409b4b1 308 length = fMaxBits;
309 codeLength = currNode->GetBinaryCodeLength();
6a1b3945 310 return kTRUE;
311 }
9409b4b1 312 continue;
6a1b3945 313 }
9409b4b1 314 break;
6a1b3945 315 }
316 value = ((AliHLTUInt64_t)1) << 63;
317 return kFALSE;
318}
319
7227b364 320Bool_t AliHLTHuffman::DecodeMSB(std::bitset<64> bits, AliHLTUInt64_t& value,
321 AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const
322{
6e848d29 323 // huffman decoding
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();
329 return kTRUE;
330 }
331 while (currNode) {
332 if (bits[63] && currNode->GetLeftChild()) {
333 // follow left branch
334 currNode = currNode->GetLeftChild();
335 bits <<= 1;
336 if (currNode->GetValue() >= 0) {
337 value = currNode->GetValue();
338 length = fMaxBits;
339 codeLength = currNode->GetBinaryCodeLength();
340 return kTRUE;
341 }
342 continue;
343 }
344 if (!bits[63] && currNode->GetRightChild()) {
345 currNode = currNode->GetRightChild();
346 bits <<= 1;
347 if (currNode->GetValue() >= 0) {
348 value = currNode->GetValue();
349 length = fMaxBits;
350 codeLength = currNode->GetBinaryCodeLength();
351 return kTRUE;
352 }
353 continue;
354 }
355 break;
356 }
357 value = ((AliHLTUInt64_t)1) << 63;
358 return kFALSE;
359}
360
7227b364 361Bool_t AliHLTHuffman::FastDecodeMSB(std::bitset<64> bits, AliHLTUInt64_t& value,
362 AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const
363{
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;
371 return kTRUE;
372 }
373 while (currNode) {
374 if (bits[63] && currNode->fLeft) {
375 // follow left branch
376 currNode = currNode->fLeft;
377 bits <<= 1;
378 if (currNode->fValue >= 0) {
379 value = currNode->fValue;
380 length = fMaxBits;
381 codeLength = currNode->fBinaryCodeLength;
382 return kTRUE;
383 }
384 continue;
385 }
386 if (!bits[63] && currNode->fRight) {
387 currNode = currNode->fRight;
388 bits <<= 1;
389 if (currNode->fValue >= 0) {
390 value = currNode->fValue;
391 length = fMaxBits;
392 codeLength = currNode->fBinaryCodeLength;
393 return kTRUE;
394 }
395 continue;
396 }
397 break;
398 }
399 value = ((AliHLTUInt64_t)1) << 63;
400 return kFALSE;
401}
402
6a1b3945 403Bool_t AliHLTHuffman::AddTrainingValue(const AliHLTUInt64_t value,
84a44d88 404 const Float_t weight) {
6a1b3945 405 if (value > fMaxValue) {
406 /* TODO: ERROR message */
407 return kFALSE;
408 }
409 fNodes[value].AddWeight(weight);
410 return kTRUE;
411}
412
413Bool_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));
421 }
422 while (nodeCollection.size() > 1) {
423 // insert new node into structure, combining the two with lowest probability
5890ed9f 424 AliHLTHuffmanNode* node=new AliHLTHuffmanTreeNode(*nodeCollection.begin(), *++nodeCollection.begin());
425 if (!node) return kFALSE;
426 nodeCollection.insert(node);
6a1b3945 427 nodeCollection.erase(nodeCollection.begin());
428 nodeCollection.erase(nodeCollection.begin());
429 }
430 //assign value
431 fHuffTopNode = *nodeCollection.begin();
9409b4b1 432 fHuffTopNode->AssignCode(fReverseCode);
6e848d29 433 InitMaxCodeLength();
6a1b3945 434 return kTRUE;
435}
436
437void AliHLTHuffman::Print(Option_t* option) const {
438 std::cout << GetName() << endl;
6e848d29 439 bool bPrintShort=strcmp(option, "full")!=0;
6a1b3945 440 if (fHuffTopNode && !bPrintShort) {
441 std::cout << "Huffman tree:" << endl;
442 fHuffTopNode->Print();
443 }
444 Double_t uncompressedSize = 0;
445 Double_t compressedSize = 0;
446 Double_t totalWeight = 0;
447 if (!bPrintShort)
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();
455 }
456 if (uncompressedSize > 0) {
457 std::cout << "compression ratio: " << compressedSize
458 / uncompressedSize << std::endl;
459 std::cout << "<bits> uncompressed: " << uncompressedSize / totalWeight
460 << std::endl;
461 std::cout << "<bits> compressed: " << compressedSize / totalWeight
462 << std::endl;
463 }
464}
465
466AliHLTHuffman& AliHLTHuffman::operator =(const AliHLTHuffman& other) {
5c8ae5fb 467 if (this==&other) return *this;
6a1b3945 468 fMaxValue = other.fMaxValue;
469 fNodes = other.fNodes;
470 fHuffTopNode = NULL;
6e848d29 471 fMaxCodeLength = 0;
6a1b3945 472 return *this;
473}
474
9409b4b1 475bool AliHLTHuffman::CheckConsistency() const
476{
477 if (!fHuffTopNode) {
478 cout << "huffman table not yet generated" << endl;
479 }
480
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;
487 if (fReverseCode) {
6e848d29 488 code<<=64-codeLength;
7227b364 489 if (!DecodeMSB(code, readback, readbacklen, readbackcodelen)) {
6e848d29 490 cout << "Decode failed" << endl;
491 return false;
492 }
493 } else {
7227b364 494 if (!DecodeLSB(code, readback, readbacklen, readbackcodelen)) {
9409b4b1 495 cout << "Decode failed" << endl;
496 return false;
497 }
6e848d29 498 }
9409b4b1 499 if (v!=readback) {
500 cout << "readback of value " << v << " code length " << codeLength << " failed: got " << readback << " code length " << readbackcodelen << endl;
501 return false;
502 }
503 }
504 return true;
505}
506
6e848d29 507UInt_t AliHLTHuffman::InitMaxCodeLength()
508{
509 // loop over leave nodes and set maximum code length
510 fMaxCodeLength=0;
511 for (std::vector<AliHLTHuffmanLeaveNode>::const_iterator node=fNodes.begin();
512 node!=fNodes.end(); node++) {
513 if (fMaxCodeLength<node->GetBinaryCodeLength())
514 fMaxCodeLength=node->GetBinaryCodeLength();
515 }
516 return fMaxCodeLength;
517}
518
7227b364 519int AliHLTHuffman::EnableDecodingMap()
520{
521 // build decoder nodes from node tree
522 fDecodingTopNode=NULL;
523 fDecodingNodes.clear();
524 if (fNodes.size()==0) {
525 return 0;
526 }
527 fDecodingNodes.reserve(2*fNodes.size());
528 fDecodingTopNode=BuildDecodingNode(fHuffTopNode, fDecodingNodes);
529 if (!fDecodingTopNode) {
530 fDecodingNodes.clear();
531 } else {
532 HLTError("decoder nodes created sucessfully");
533 }
534 return 0;
535}
536
537AliHLTHuffman::AliHuffmanDecodingNode* AliHLTHuffman::BuildDecodingNode(AliHLTHuffmanNode* node, vector<AliHuffmanDecodingNode>& decodernodes) const
538{
539 // build and add decoder node structure corresponding to huffman node
540 if (!node) {
541 HLTError("invalid node pointer");
542 return NULL;
543 }
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);
548 return NULL;
549 }
550 }
551
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");
555 } else {
556 AliHuffmanDecodingNode dn;
557 dn.fParent=node;
558 dn.fValue=node->GetValue();
559 dn.fLeft=NULL;
560 dn.fRight=NULL;
561 dn.fBinaryCodeLength=0;
562 decodernodes.push_back(dn);
563 decodernode=&(decodernodes.back());
564 }
565
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);
571 decodernode=NULL;
572 }
573 }
574
575 return decodernode;
576}
577
6a1b3945 578ClassImp(AliHLTHuffman)
579