ALIROOT-5600 - skip non-participating detector modules
[u/mrichter/AliRoot.git] / HLT / BASE / AliHLTHuffman.cxx
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
30 AliHLTHuffmanNode::AliHLTHuffmanNode() 
31         : TObject()
32         , fValue(-1)
33         , fWeight(0.)
34 {
35         // nop
36 }
37
38 AliHLTHuffmanNode::AliHLTHuffmanNode(const AliHLTHuffmanNode& other)
39         : TObject()
40         , fValue(other.GetValue())
41         , fWeight(other.GetWeight())
42 {
43 }
44
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;
50         return *this;
51 }
52
53 AliHLTHuffmanNode::~AliHLTHuffmanNode() {
54 }
55
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.
67         if (GetLeftChild()) {
68           if (bReverse) {
69                 std::bitset < 64 > v = (this->GetBinaryCode() << 1);
70                 v.set(0);
71                 GetLeftChild()->SetBinaryCode(this->GetBinaryCodeLength() + 1, v);
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);
79         }
80         if (GetRightChild()) {
81           if (bReverse) {
82                 std::bitset < 64 > v = (this->GetBinaryCode() << 1);
83                 v.reset(0);
84                 GetRightChild()->SetBinaryCode(this->GetBinaryCodeLength() + 1, v);
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);
92         }
93 }
94
95 void 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
108 ClassImp(AliHLTHuffmanNode)
109
110 ///////////////////////////////////////////////////////////////////////////////////////////////
111
112 AliHLTHuffmanTreeNode::AliHLTHuffmanTreeNode() 
113         : AliHLTHuffmanNode()
114         , fBinaryCodeLength(0)
115         , fBinaryCode(0)
116         , fLeft(NULL)
117         , fRight(NULL)
118 {
119         // nop
120 }
121
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())
128 {
129
130 }
131
132 AliHLTHuffmanTreeNode& 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
144 AliHLTHuffmanTreeNode::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
159 AliHLTHuffmanTreeNode::~AliHLTHuffmanTreeNode() 
160 {
161         // nop
162 }
163
164 ClassImp(AliHLTHuffmanTreeNode)
165
166 ///////////////////////////////////////////////////////////////////////////////////////////////
167
168 AliHLTHuffmanLeaveNode::AliHLTHuffmanLeaveNode() 
169         : AliHLTHuffmanNode()
170         , fBinaryCodeLength(0)
171         , fBinaryCode(0)
172         , fLeft(NULL)
173         , fRight(NULL)
174 {
175         // nop
176 }
177
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())
184 {
185
186 }
187
188 AliHLTHuffmanLeaveNode& 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
200 AliHLTHuffmanLeaveNode::~AliHLTHuffmanLeaveNode() 
201 {
202         // nop
203 }
204
205 ClassImp(AliHLTHuffmanLeaveNode)
206
207 ///////////////////////////////////////////////////////////////////////////////////////////////
208
209 AliHLTHuffman::AliHLTHuffman()
210         : TNamed()
211         , fMaxBits(0)
212         , fMaxValue(0)
213         , fNodes(0)
214         , fHuffTopNode(NULL)
215         , fReverseCode(true)
216         , fMaxCodeLength(0)
217         , fDecodingNodes()
218         , fDecodingTopNode(NULL)
219 {
220         /// nop
221 }
222
223 AliHLTHuffman::AliHLTHuffman(const AliHLTHuffman& other)
224         : TNamed()
225         , AliHLTLogging()
226         , fMaxBits(other.fMaxBits)
227         , fMaxValue(other.fMaxValue)
228         , fNodes(other.fNodes)
229         , fHuffTopNode(NULL)
230         , fReverseCode(other.fReverseCode)
231         , fMaxCodeLength(other.fMaxCodeLength)
232         , fDecodingNodes()
233         , fDecodingTopNode(NULL)
234 {
235         /// nop
236 }
237
238 AliHLTHuffman::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)
244         , fReverseCode(true)
245         , fMaxCodeLength(0)
246         , fDecodingNodes()
247         , fDecodingTopNode(NULL)
248  {
249         /// standard constructor
250         for (AliHLTUInt64_t i = 0; i <= fMaxValue; i++) {
251                 fNodes[i].SetValue(i);
252         }
253 }
254
255 AliHLTHuffman::~AliHLTHuffman() {
256         /// destructor, nop
257 }
258
259 const 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
279 Bool_t AliHLTHuffman::DecodeLSB(std::bitset<64> bits, AliHLTUInt64_t& value,
280                                 AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const
281 {
282         // huffman decoding
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();
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 && currNode->GetValue() >= 0) {
296                                 value = currNode->GetValue();
297                                 length = fMaxBits;
298                                 codeLength = currNode->GetBinaryCodeLength();
299                                 return kTRUE;
300                         }
301                         continue;
302                 }
303                 if (!bits[0] && currNode->GetRightChild()) {
304                         currNode = currNode->GetRightChild();
305                         bits >>= 1;
306                         if (currNode && currNode->GetValue() >= 0) {
307                                 value = currNode->GetValue();
308                                 length = fMaxBits;
309                                 codeLength = currNode->GetBinaryCodeLength();
310                                 return kTRUE;
311                         }
312                         continue;
313                 }
314                 break;
315         }
316         value = ((AliHLTUInt64_t)1) << 63;
317         return kFALSE;
318 }
319
320 Bool_t AliHLTHuffman::DecodeMSB(std::bitset<64> bits, AliHLTUInt64_t& value,
321                                 AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const
322 {
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 && 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 && 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
361 Bool_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 && 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 && 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
403 Bool_t AliHLTHuffman::AddTrainingValue(const AliHLTUInt64_t value,
404                 const Float_t weight) {
405         if (value > fMaxValue) {
406                 /* TODO: ERROR message */
407                 return kFALSE;
408         }
409         fNodes[value].AddWeight(weight);
410         return kTRUE;
411 }
412
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));
421         }
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());
429         }
430         //assign value
431         fHuffTopNode = *nodeCollection.begin();
432         fHuffTopNode->AssignCode(fReverseCode);
433         InitMaxCodeLength();
434         return kTRUE;
435 }
436
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();
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
466 AliHLTHuffman& AliHLTHuffman::operator =(const AliHLTHuffman& other) {
467         if (this==&other) return *this;
468         fMaxValue = other.fMaxValue;
469         fNodes = other.fNodes;
470         fHuffTopNode = NULL;
471         fMaxCodeLength = 0;
472         return *this;
473 }
474
475 bool 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) {
488       code<<=64-codeLength;
489       if (!DecodeMSB(code, readback, readbacklen, readbackcodelen)) {
490         cout << "Decode failed" << endl;
491         return false;
492       }
493     } else {
494     if (!DecodeLSB(code, readback, readbacklen, readbackcodelen)) {
495       cout << "Decode failed" << endl;
496       return false;
497     }
498     }
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
507 UInt_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
519 int 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
537 AliHLTHuffman::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
578 ClassImp(AliHLTHuffman)
579