avoid compilation warning on some architectures
[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
47 this->fValue = other.fValue;
48 this->fWeight = other.fWeight;
49 return *this;
50}
51
52AliHLTHuffmanNode::~AliHLTHuffmanNode() {
53}
54
9409b4b1 55void AliHLTHuffmanNode::AssignCode(bool bReverse) {
6a1b3945 56 /// assign code to this node loop to right and left nodes
9409b4b1 57 /// the decoding always has to start from the least significant bit since the
58 /// code length is variable. Thats why the bit corresponding to the parent node
59 /// has to be right of the bit of child nodes, i.e. bits correspond to the
60 /// current code length. For storage in a bit stream however, bits are stored
61 /// in a stream from MSB to LSB and overwrapping to the MSBs of the next byte.
62 /// Here the reverse code is needed and the word of fixed length read from the
63 /// stream needs to be reversed before decoding.
64 /// Note: by changing the AliHLTDataDeflater interface to write from LSB to MSB
65 /// this can be avoided.
6a1b3945 66 if (GetLeftChild()) {
9409b4b1 67 if (bReverse) {
6a1b3945 68 std::bitset < 64 > v = (this->GetBinaryCode() << 1);
69 v.set(0);
70 GetLeftChild()->SetBinaryCode(this->GetBinaryCodeLength() + 1, v);
9409b4b1 71 } else {
72 std::bitset < 64 > v = (this->GetBinaryCode());
73 int codelen=this->GetBinaryCodeLength();
74 v.set(codelen);
75 GetLeftChild()->SetBinaryCode(codelen + 1, v);
76 }
77 GetLeftChild()->AssignCode(bReverse);
6a1b3945 78 }
79 if (GetRightChild()) {
9409b4b1 80 if (bReverse) {
6a1b3945 81 std::bitset < 64 > v = (this->GetBinaryCode() << 1);
82 v.reset(0);
83 GetRightChild()->SetBinaryCode(this->GetBinaryCodeLength() + 1, v);
9409b4b1 84 } else {
85 std::bitset < 64 > v = (this->GetBinaryCode());
86 int codelen=this->GetBinaryCodeLength();
87 v.reset(codelen);
88 GetRightChild()->SetBinaryCode(codelen + 1, v);
89 }
90 GetRightChild()->AssignCode(bReverse);
6a1b3945 91 }
92}
93
94void AliHLTHuffmanNode::Print(Option_t* /*option*/) const {
95 /// print info
96 std::cout << "value=" << GetValue() << ", weight=" << GetWeight() << ", length="
97 << GetBinaryCodeLength() << ", code=" << GetBinaryCode().to_string()
98 << std::endl;
99 if (GetLeftChild()) {
100 GetLeftChild()->Print();
101 }
102 if (GetRightChild()) {
103 GetRightChild()->Print();
104 }
105}
106
107ClassImp(AliHLTHuffmanNode)
108
109///////////////////////////////////////////////////////////////////////////////////////////////
110
111AliHLTHuffmanTreeNode::AliHLTHuffmanTreeNode()
112 : AliHLTHuffmanNode()
113 , fBinaryCodeLength(0)
114 , fBinaryCode(0)
115 , fLeft(NULL)
116 , fRight(NULL)
117{
118 // nop
119}
120
121AliHLTHuffmanTreeNode::AliHLTHuffmanTreeNode(const AliHLTHuffmanTreeNode& other)
122 : AliHLTHuffmanNode()
123 , fBinaryCodeLength(other.fBinaryCodeLength)
124 , fBinaryCode(other.fBinaryCode)
125 , fLeft(other.GetLeftChild())
126 , fRight(other.GetRightChild())
127{
128
129}
130
131AliHLTHuffmanTreeNode& AliHLTHuffmanTreeNode::operator =(const AliHLTHuffmanTreeNode& other)
132{
133 /// assignment operator
134 if (&other==this) return *this;
135 this->fBinaryCodeLength = other.GetBinaryCodeLength();
136 this->fBinaryCode = other.GetBinaryCode();
137 this->fLeft = other.GetLeftChild();
138 this->fRight = other.GetRightChild();
139 AliHLTHuffmanNode::operator=(other);
140 return *this;
141}
142
143AliHLTHuffmanTreeNode::AliHLTHuffmanTreeNode(AliHLTHuffmanNode* l, AliHLTHuffmanNode* r)
144 : AliHLTHuffmanNode()
145 , fBinaryCodeLength(0)
146 , fBinaryCode(0)
147 , fLeft(l)
148 , fRight(r) {
149 if (l && r) {
150 SetWeight(l->GetWeight() + r->GetWeight());
151 } else if (l && !r) {
152 SetWeight(l->GetWeight());
153 } else if (!l && r) {
154 SetWeight(r->GetWeight());
155 }
156}
157
158AliHLTHuffmanTreeNode::~AliHLTHuffmanTreeNode()
159{
160 // nop
161}
162
163ClassImp(AliHLTHuffmanTreeNode)
164
165///////////////////////////////////////////////////////////////////////////////////////////////
166
167AliHLTHuffmanLeaveNode::AliHLTHuffmanLeaveNode()
168 : AliHLTHuffmanNode()
169 , fBinaryCodeLength(0)
170 , fBinaryCode(0)
171 , fLeft(NULL)
172 , fRight(NULL)
173{
174 // nop
175}
176
177AliHLTHuffmanLeaveNode::AliHLTHuffmanLeaveNode(const AliHLTHuffmanLeaveNode& other)
178 : AliHLTHuffmanNode()
179 , fBinaryCodeLength(other.fBinaryCodeLength)
180 , fBinaryCode(other.fBinaryCode)
181 , fLeft(other.GetLeftChild())
182 , fRight(other.GetRightChild())
183{
184
185}
186
187AliHLTHuffmanLeaveNode& AliHLTHuffmanLeaveNode::operator =(const AliHLTHuffmanLeaveNode& other)
188{
189 /// assignment operator
190 if (&other==this) return *this;
191 this->fBinaryCodeLength = other.GetBinaryCodeLength();
192 this->fBinaryCode = other.GetBinaryCode();
193 this->fLeft = other.GetLeftChild();
194 this->fRight = other.GetRightChild();
195 AliHLTHuffmanNode::operator=(other);
196 return *this;
197}
198
199AliHLTHuffmanLeaveNode::~AliHLTHuffmanLeaveNode()
200{
201 // nop
202}
203
204ClassImp(AliHLTHuffmanLeaveNode)
205
206///////////////////////////////////////////////////////////////////////////////////////////////
207
208AliHLTHuffman::AliHLTHuffman()
209 : TNamed()
210 , fMaxBits(0)
211 , fMaxValue(0)
212 , fNodes(0)
213 , fHuffTopNode(NULL)
9409b4b1 214 , fReverseCode(true)
6a1b3945 215{
216 /// nop
217}
218
219AliHLTHuffman::AliHLTHuffman(const AliHLTHuffman& other)
220 : TNamed()
221 , AliHLTLogging()
222 , fMaxBits(other.fMaxBits)
223 , fMaxValue(other.fMaxValue)
224 , fNodes(other.fNodes)
9409b4b1 225 , fHuffTopNode(NULL)
226 , fReverseCode(other.fReverseCode)
227{
6a1b3945 228 /// nop
229}
230
231AliHLTHuffman::AliHLTHuffman(const char* name, UInt_t maxBits)
232 : TNamed(name, name)
233 , fMaxBits(maxBits)
234 , fMaxValue((((AliHLTUInt64_t) 1) << maxBits) - 1)
235 , fNodes((((AliHLTUInt64_t) 1) << maxBits))
236 , fHuffTopNode(NULL)
9409b4b1 237 , fReverseCode(true)
6a1b3945 238 {
239 /// standard constructor
240 for (AliHLTUInt64_t i = 0; i <= fMaxValue; i++) {
241 fNodes[i].SetValue(i);
242 }
243}
244
245AliHLTHuffman::~AliHLTHuffman() {
246 /// destructor, nop
247}
248
249const std::bitset<64>& AliHLTHuffman::Encode(const AliHLTUInt64_t v, AliHLTUInt64_t& codeLength) const {
250 /// encode a value
251 codeLength = 0;
252 if (v <= fMaxValue) {
253 // valid symbol/value
254 if (fHuffTopNode) {
255 // huffman code has been generated
256 codeLength = fNodes[v].GetBinaryCodeLength();
257 return fNodes[v].GetBinaryCode();
258 } else {
259 HLTError("encoder '%s' does not seem to be initialized", GetName());
260 }
261 } else {
262 HLTError("encoder %s: value %llu exceeds range of %d bits", GetName(), v, GetMaxBits());
263 }
264
265 static const std::bitset<64> dummy;
266 return dummy;
267}
268
9409b4b1 269Bool_t AliHLTHuffman::Decode(std::bitset<64> bits, AliHLTUInt64_t& value,
270 AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const {
6a1b3945 271 // TODO: check decoding logic, righ now it is just as written
272 AliHLTHuffmanNode* currNode = fHuffTopNode;
cac77957 273 if (!currNode) return kFALSE;
6a1b3945 274 if (currNode->GetValue() >= 0) {
275 // handle case with just one node - also quite unlikely
276 value = currNode->GetValue();
277 return kTRUE;
278 }
279 while (currNode) {
280 if (bits[0] && currNode->GetLeftChild()) {
281 // follow left branch
282 currNode = currNode->GetLeftChild();
283 bits >>= 1;
284 if (currNode->GetValue() >= 0) {
285 value = currNode->GetValue();
9409b4b1 286 length = fMaxBits;
287 codeLength = currNode->GetBinaryCodeLength();
6a1b3945 288 return kTRUE;
289 }
9409b4b1 290 continue;
6a1b3945 291 }
292 if (!bits[0] && currNode->GetRightChild()) {
293 currNode = currNode->GetRightChild();
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 }
9409b4b1 303 break;
6a1b3945 304 }
305 value = ((AliHLTUInt64_t)1) << 63;
306 return kFALSE;
307}
308
309Bool_t AliHLTHuffman::AddTrainingValue(const AliHLTUInt64_t value,
84a44d88 310 const Float_t weight) {
6a1b3945 311 if (value > fMaxValue) {
312 /* TODO: ERROR message */
313 return kFALSE;
314 }
315 fNodes[value].AddWeight(weight);
316 return kTRUE;
317}
318
319Bool_t AliHLTHuffman::GenerateHuffmanTree() {
320 // insert pointer to nodes into ordered structure to build tree
321 std::multiset<AliHLTHuffmanNode*, AliHLTHuffmanNode::less> nodeCollection;
322 // std::copy(fNodes.begin(), fNodes.end(),
323 // std::inserter(freq_coll, freq_coll.begin()));
324 for (std::vector<AliHLTHuffmanLeaveNode>::iterator i = fNodes.begin(); i
325 != fNodes.end(); ++i) {
326 nodeCollection.insert(&(*i));
327 }
328 while (nodeCollection.size() > 1) {
329 // insert new node into structure, combining the two with lowest probability
5890ed9f 330 AliHLTHuffmanNode* node=new AliHLTHuffmanTreeNode(*nodeCollection.begin(), *++nodeCollection.begin());
331 if (!node) return kFALSE;
332 nodeCollection.insert(node);
6a1b3945 333 nodeCollection.erase(nodeCollection.begin());
334 nodeCollection.erase(nodeCollection.begin());
335 }
336 //assign value
337 fHuffTopNode = *nodeCollection.begin();
9409b4b1 338 fHuffTopNode->AssignCode(fReverseCode);
6a1b3945 339 return kTRUE;
340}
341
342void AliHLTHuffman::Print(Option_t* option) const {
343 std::cout << GetName() << endl;
344 bool bPrintShort=strcmp(option, "short")==0;
345 if (fHuffTopNode && !bPrintShort) {
346 std::cout << "Huffman tree:" << endl;
347 fHuffTopNode->Print();
348 }
349 Double_t uncompressedSize = 0;
350 Double_t compressedSize = 0;
351 Double_t totalWeight = 0;
352 if (!bPrintShort)
353 std::cout << std::endl << "Huffman codes:" << std::endl;
354 for (AliHLTUInt64_t i = 0; i <= fMaxValue; i++) {
355 if (!bPrintShort) fNodes[i].Print();
356 totalWeight += fNodes[i].GetWeight();
357 uncompressedSize += fNodes[i].GetWeight() * fMaxBits;
358 compressedSize += fNodes[i].GetWeight()
359 * fNodes[i].GetBinaryCodeLength();
360 }
361 if (uncompressedSize > 0) {
362 std::cout << "compression ratio: " << compressedSize
363 / uncompressedSize << std::endl;
364 std::cout << "<bits> uncompressed: " << uncompressedSize / totalWeight
365 << std::endl;
366 std::cout << "<bits> compressed: " << compressedSize / totalWeight
367 << std::endl;
368 }
369}
370
371AliHLTHuffman& AliHLTHuffman::operator =(const AliHLTHuffman& other) {
372 fMaxValue = other.fMaxValue;
373 fNodes = other.fNodes;
374 fHuffTopNode = NULL;
375 return *this;
376}
377
9409b4b1 378bool AliHLTHuffman::CheckConsistency() const
379{
380 if (!fHuffTopNode) {
381 cout << "huffman table not yet generated" << endl;
382 }
383
384 for (AliHLTUInt64_t v=0; v<GetMaxValue(); v++) {
385 AliHLTUInt64_t codeLength=0;
386 std::bitset<64> code=AliHLTHuffman::Encode(v, codeLength);
387 AliHLTUInt64_t readback=0;
388 AliHLTUInt32_t readbacklen=0;
389 AliHLTUInt32_t readbackcodelen=0;
390 if (fReverseCode) {
391 // reverse if needed
392 // Note: for optimized bit stream the huffman code is reversed, and
393 // that needs to be taken into account
394 std::bitset<64> rcode;
395 for (AliHLTUInt64_t i=0; i<codeLength; i++) {rcode<<=1; rcode[0]=code[i];}
396 code=rcode;
397 }
398 if (!Decode(code, readback, readbacklen, readbackcodelen)) {
399 cout << "Decode failed" << endl;
400 return false;
401 }
402 if (v!=readback) {
403 cout << "readback of value " << v << " code length " << codeLength << " failed: got " << readback << " code length " << readbackcodelen << endl;
404 return false;
405 }
406 }
407 return true;
408}
409
6a1b3945 410ClassImp(AliHLTHuffman)
411