Line data Source code
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 <iomanip>
27 : #include <set>
28 : #include <bitset>
29 : #include <algorithm>
30 :
31 : AliHLTHuffmanNode::AliHLTHuffmanNode()
32 702702 : : TObject()
33 702702 : , fValue(-1)
34 702702 : , fWeight(0.)
35 702702 : , fWeightDouble(0.)
36 2108106 : {
37 : // nop
38 702702 : }
39 :
40 : AliHLTHuffmanNode::AliHLTHuffmanNode(const AliHLTHuffmanNode& other)
41 0 : : TObject()
42 0 : , fValue(other.GetValue())
43 0 : , fWeight(other.GetWeight())
44 0 : , fWeightDouble(other.GetWeight())
45 0 : {
46 0 : }
47 :
48 : AliHLTHuffmanNode& AliHLTHuffmanNode::operator =(const AliHLTHuffmanNode& other) {
49 : /// assignment operator
50 0 : if (this==&other) return *this;
51 0 : this->fValue = other.fValue;
52 0 : this->fWeight = other.fWeight;
53 0 : this->fWeightDouble = other.fWeightDouble;
54 0 : return *this;
55 0 : }
56 :
57 0 : AliHLTHuffmanNode::~AliHLTHuffmanNode() {
58 468484 : }
59 :
60 : void AliHLTHuffmanNode::AssignCode(bool bReverse) {
61 : /// assign code to this node loop to right and left nodes
62 : /// the decoding always has to start from the least significant bit since the
63 : /// code length is variable. Thats why the bit corresponding to the parent node
64 : /// has to be right of the bit of child nodes, i.e. bits correspond to the
65 : /// current code length. For storage in a bit stream however, bits are stored
66 : /// in a stream from MSB to LSB and overwrapping to the MSBs of the next byte.
67 : /// Here the reverse code is needed and the word of fixed length read from the
68 : /// stream needs to be reversed before decoding.
69 : /// Note: by changing the AliHLTDataDeflater interface to write from LSB to MSB
70 : /// this can be avoided.
71 0 : if (GetLeftChild()) {
72 0 : if (bReverse) {
73 0 : std::bitset < 64 > v = (this->GetBinaryCode() << 1);
74 0 : v.set(0);
75 0 : GetLeftChild()->SetBinaryCode(this->GetBinaryCodeLength() + 1, v);
76 0 : } else {
77 0 : std::bitset < 64 > v = (this->GetBinaryCode());
78 0 : int codelen=this->GetBinaryCodeLength();
79 0 : v.set(codelen);
80 0 : GetLeftChild()->SetBinaryCode(codelen + 1, v);
81 0 : }
82 0 : GetLeftChild()->AssignCode(bReverse);
83 0 : }
84 0 : if (GetRightChild()) {
85 0 : if (bReverse) {
86 0 : std::bitset < 64 > v = (this->GetBinaryCode() << 1);
87 0 : v.reset(0);
88 0 : GetRightChild()->SetBinaryCode(this->GetBinaryCodeLength() + 1, v);
89 0 : } else {
90 0 : std::bitset < 64 > v = (this->GetBinaryCode());
91 0 : int codelen=this->GetBinaryCodeLength();
92 0 : v.reset(codelen);
93 0 : GetRightChild()->SetBinaryCode(codelen + 1, v);
94 0 : }
95 0 : GetRightChild()->AssignCode(bReverse);
96 0 : }
97 0 : }
98 :
99 : void AliHLTHuffmanNode::Print(Option_t* /*option*/) const {
100 : /// print info
101 0 : std::streamsize precbackup = std::cout.precision();
102 0 : std::streamsize widthbackup = std::cout.width();
103 0 : std::ios::fmtflags flagsbackup = std::cout.flags();
104 0 : std::cout.precision(6);
105 0 : std::cout << " value=" << std::setw(6) << std::left << GetValue()
106 0 : << " weight=" << std::setw(12) << std::scientific << GetWeight()
107 0 : << " length=" << std::setw(3) << GetBinaryCodeLength()
108 0 : << " code=" << GetBinaryCode().to_string()
109 0 : << std::endl;
110 0 : if (GetLeftChild()) {
111 0 : GetLeftChild()->Print();
112 0 : }
113 0 : if (GetRightChild()) {
114 0 : GetRightChild()->Print();
115 0 : }
116 0 : std::cout.precision(precbackup);
117 0 : std::cout.width(widthbackup);
118 0 : std::cout.flags(flagsbackup);
119 0 : }
120 :
121 126 : ClassImp(AliHLTHuffmanNode)
122 :
123 : ///////////////////////////////////////////////////////////////////////////////////////////////
124 :
125 : AliHLTHuffmanTreeNode::AliHLTHuffmanTreeNode()
126 234220 : : AliHLTHuffmanNode()
127 234220 : , fBinaryCodeLength(0)
128 234220 : , fBinaryCode(0)
129 234220 : , fLeft(NULL)
130 234220 : , fRight(NULL)
131 1171100 : {
132 : // nop
133 468440 : }
134 :
135 : AliHLTHuffmanTreeNode::AliHLTHuffmanTreeNode(const AliHLTHuffmanTreeNode& other)
136 0 : : AliHLTHuffmanNode(other)
137 0 : , fBinaryCodeLength(other.fBinaryCodeLength)
138 0 : , fBinaryCode(other.fBinaryCode)
139 0 : , fLeft(other.GetLeftChild())
140 0 : , fRight(other.GetRightChild())
141 0 : {
142 :
143 0 : }
144 :
145 : AliHLTHuffmanTreeNode& AliHLTHuffmanTreeNode::operator =(const AliHLTHuffmanTreeNode& other)
146 : {
147 : /// assignment operator
148 0 : if (&other==this) return *this;
149 0 : this->fBinaryCodeLength = other.GetBinaryCodeLength();
150 0 : this->fBinaryCode = other.GetBinaryCode();
151 0 : this->fLeft = other.GetLeftChild();
152 0 : this->fRight = other.GetRightChild();
153 0 : AliHLTHuffmanNode::operator=(other);
154 0 : return *this;
155 0 : }
156 :
157 : AliHLTHuffmanTreeNode::AliHLTHuffmanTreeNode(AliHLTHuffmanNode* l, AliHLTHuffmanNode* r)
158 0 : : AliHLTHuffmanNode()
159 0 : , fBinaryCodeLength(0)
160 0 : , fBinaryCode(0)
161 0 : , fLeft(l)
162 0 : , fRight(r) {
163 0 : if (l && r) {
164 0 : SetWeight(l->GetWeight() + r->GetWeight());
165 0 : } else if (l && !r) {
166 0 : SetWeight(l->GetWeight());
167 0 : } else if (!l && r) {
168 0 : SetWeight(r->GetWeight());
169 0 : }
170 0 : }
171 :
172 : AliHLTHuffmanTreeNode::~AliHLTHuffmanTreeNode()
173 0 : {
174 : // nop
175 0 : }
176 :
177 126 : ClassImp(AliHLTHuffmanTreeNode)
178 :
179 : ///////////////////////////////////////////////////////////////////////////////////////////////
180 :
181 : AliHLTHuffmanLeaveNode::AliHLTHuffmanLeaveNode()
182 468482 : : AliHLTHuffmanNode()
183 468482 : , fBinaryCodeLength(0)
184 468482 : , fBinaryCode(0)
185 468482 : , fLeft(NULL)
186 468482 : , fRight(NULL)
187 2342410 : {
188 : // nop
189 936964 : }
190 :
191 : AliHLTHuffmanLeaveNode::AliHLTHuffmanLeaveNode(const AliHLTHuffmanLeaveNode& other)
192 0 : : AliHLTHuffmanNode(other)
193 0 : , fBinaryCodeLength(other.fBinaryCodeLength)
194 0 : , fBinaryCode(other.fBinaryCode)
195 0 : , fLeft(other.GetLeftChild())
196 0 : , fRight(other.GetRightChild())
197 0 : {
198 :
199 0 : }
200 :
201 : AliHLTHuffmanLeaveNode& AliHLTHuffmanLeaveNode::operator =(const AliHLTHuffmanLeaveNode& other)
202 : {
203 : /// assignment operator
204 0 : if (&other==this) return *this;
205 0 : this->fBinaryCodeLength = other.GetBinaryCodeLength();
206 0 : this->fBinaryCode = other.GetBinaryCode();
207 0 : this->fLeft = other.GetLeftChild();
208 0 : this->fRight = other.GetRightChild();
209 0 : AliHLTHuffmanNode::operator=(other);
210 0 : return *this;
211 0 : }
212 :
213 : AliHLTHuffmanLeaveNode::~AliHLTHuffmanLeaveNode()
214 468488 : {
215 : // nop
216 702728 : }
217 :
218 126 : ClassImp(AliHLTHuffmanLeaveNode)
219 :
220 : ///////////////////////////////////////////////////////////////////////////////////////////////
221 :
222 20 : AliHLTHuffman::AliHLTHuffman()
223 20 : : TNamed()
224 20 : , fMaxBits(0)
225 20 : , fMaxValue(0)
226 20 : , fNodes(0)
227 20 : , fHuffTopNode(NULL)
228 20 : , fReverseCode(true)
229 20 : , fMaxCodeLength(0)
230 20 : , fDecodingNodes()
231 20 : , fDecodingTopNode(NULL)
232 120 : {
233 : /// nop
234 40 : }
235 :
236 : AliHLTHuffman::AliHLTHuffman(const AliHLTHuffman& other)
237 0 : : TNamed()
238 0 : , AliHLTLogging()
239 0 : , fMaxBits(other.fMaxBits)
240 0 : , fMaxValue(other.fMaxValue)
241 0 : , fNodes(other.fNodes)
242 0 : , fHuffTopNode(NULL)
243 0 : , fReverseCode(other.fReverseCode)
244 0 : , fMaxCodeLength(other.fMaxCodeLength)
245 0 : , fDecodingNodes()
246 0 : , fDecodingTopNode(NULL)
247 0 : {
248 : /// nop
249 0 : }
250 :
251 0 : AliHLTHuffman::AliHLTHuffman(const char* name, UInt_t maxBits)
252 0 : : TNamed(name, name)
253 0 : , fMaxBits(maxBits)
254 0 : , fMaxValue((((AliHLTUInt64_t) 1) << maxBits) - 1)
255 0 : , fNodes((((AliHLTUInt64_t) 1) << maxBits))
256 0 : , fHuffTopNode(NULL)
257 0 : , fReverseCode(true)
258 0 : , fMaxCodeLength(0)
259 0 : , fDecodingNodes()
260 0 : , fDecodingTopNode(NULL)
261 0 : {
262 : /// standard constructor
263 0 : for (AliHLTUInt64_t i = 0; i <= fMaxValue; i++) {
264 0 : fNodes[i].SetValue(i);
265 : }
266 0 : }
267 :
268 120 : AliHLTHuffman::~AliHLTHuffman() {
269 : /// destructor, nop
270 60 : }
271 :
272 : const std::bitset<64>& AliHLTHuffman::Encode(const AliHLTUInt64_t v, AliHLTUInt64_t& codeLength) const {
273 : /// encode a value
274 0 : codeLength = 0;
275 0 : if (v <= fMaxValue) {
276 : // valid symbol/value
277 0 : if (fHuffTopNode) {
278 : // huffman code has been generated
279 0 : codeLength = fNodes[v].GetBinaryCodeLength();
280 0 : return fNodes[v].GetBinaryCode();
281 : } else {
282 0 : HLTError("encoder '%s' does not seem to be initialized", GetName());
283 : }
284 : } else {
285 0 : HLTError("encoder %s: value %llu exceeds range of %d bits", GetName(), v, GetMaxBits());
286 : }
287 :
288 : static const std::bitset<64> dummy;
289 0 : return dummy;
290 0 : }
291 :
292 : Bool_t AliHLTHuffman::DecodeLSB(std::bitset<64> bits, AliHLTUInt64_t& value,
293 : AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const
294 : {
295 : // huffman decoding
296 0 : AliHLTHuffmanNode* currNode = fHuffTopNode;
297 0 : if (!currNode) return kFALSE;
298 0 : if (currNode->GetValue() >= 0) {
299 : // handle case with just one node - also quite unlikely
300 0 : value = currNode->GetValue();
301 0 : return kTRUE;
302 : }
303 0 : while (currNode) {
304 0 : if (bits[0] && currNode->GetLeftChild()) {
305 : // follow left branch
306 0 : currNode = currNode->GetLeftChild();
307 0 : bits >>= 1;
308 0 : if (currNode && currNode->GetValue() >= 0) {
309 0 : value = currNode->GetValue();
310 0 : length = fMaxBits;
311 0 : codeLength = currNode->GetBinaryCodeLength();
312 0 : return kTRUE;
313 : }
314 : continue;
315 : }
316 0 : if (!bits[0] && currNode->GetRightChild()) {
317 0 : currNode = currNode->GetRightChild();
318 0 : bits >>= 1;
319 0 : if (currNode && currNode->GetValue() >= 0) {
320 0 : value = currNode->GetValue();
321 0 : length = fMaxBits;
322 0 : codeLength = currNode->GetBinaryCodeLength();
323 0 : return kTRUE;
324 : }
325 : continue;
326 : }
327 : break;
328 : }
329 0 : value = ((AliHLTUInt64_t)1) << 63;
330 0 : return kFALSE;
331 0 : }
332 :
333 : Bool_t AliHLTHuffman::DecodeMSB(std::bitset<64> bits, AliHLTUInt64_t& value,
334 : AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const
335 : {
336 : // huffman decoding
337 0 : AliHLTHuffmanNode* currNode = fHuffTopNode;
338 0 : if (!currNode) return kFALSE;
339 0 : if (currNode->GetValue() >= 0) {
340 : // handle case with just one node - also quite unlikely
341 0 : value = currNode->GetValue();
342 0 : return kTRUE;
343 : }
344 0 : while (currNode) {
345 0 : if (bits[63] && currNode->GetLeftChild()) {
346 : // follow left branch
347 0 : currNode = currNode->GetLeftChild();
348 0 : bits <<= 1;
349 0 : if (currNode && currNode->GetValue() >= 0) {
350 0 : value = currNode->GetValue();
351 0 : length = fMaxBits;
352 0 : codeLength = currNode->GetBinaryCodeLength();
353 0 : return kTRUE;
354 : }
355 : continue;
356 : }
357 0 : if (!bits[63] && currNode->GetRightChild()) {
358 0 : currNode = currNode->GetRightChild();
359 0 : bits <<= 1;
360 0 : if (currNode && currNode->GetValue() >= 0) {
361 0 : value = currNode->GetValue();
362 0 : length = fMaxBits;
363 0 : codeLength = currNode->GetBinaryCodeLength();
364 0 : return kTRUE;
365 : }
366 : continue;
367 : }
368 : break;
369 : }
370 0 : value = ((AliHLTUInt64_t)1) << 63;
371 0 : return kFALSE;
372 0 : }
373 :
374 : Bool_t AliHLTHuffman::FastDecodeMSB(std::bitset<64> bits, AliHLTUInt64_t& value,
375 : AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const
376 : {
377 : // huffman decoding using the binary node map
378 0 : HLTFatal("this function needs to be tested and commisioned");
379 0 : AliHuffmanDecodingNode* currNode = fDecodingTopNode;
380 0 : if (!currNode) return kFALSE;
381 0 : if (currNode->fValue >= 0) {
382 : // handle case with just one node - also quite unlikely
383 0 : value = currNode->fValue;
384 0 : return kTRUE;
385 : }
386 0 : while (currNode) {
387 0 : if (bits[63] && currNode->fLeft) {
388 : // follow left branch
389 : currNode = currNode->fLeft;
390 0 : bits <<= 1;
391 0 : if (currNode && currNode->fValue >= 0) {
392 0 : value = currNode->fValue;
393 0 : length = fMaxBits;
394 0 : codeLength = currNode->fBinaryCodeLength;
395 0 : return kTRUE;
396 : }
397 : continue;
398 : }
399 0 : if (!bits[63] && currNode->fRight) {
400 : currNode = currNode->fRight;
401 0 : bits <<= 1;
402 0 : if (currNode && currNode->fValue >= 0) {
403 0 : value = currNode->fValue;
404 0 : length = fMaxBits;
405 0 : codeLength = currNode->fBinaryCodeLength;
406 0 : return kTRUE;
407 : }
408 : continue;
409 : }
410 : break;
411 : }
412 0 : value = ((AliHLTUInt64_t)1) << 63;
413 0 : return kFALSE;
414 0 : }
415 :
416 : Bool_t AliHLTHuffman::AddTrainingValue(const AliHLTUInt64_t value,
417 : const Float_t weight) {
418 0 : if (value > fMaxValue) {
419 : /* TODO: ERROR message */
420 0 : return kFALSE;
421 : }
422 0 : fNodes[value].AddWeight(weight);
423 0 : return kTRUE;
424 0 : }
425 :
426 : Bool_t AliHLTHuffman::GenerateHuffmanTree() {
427 : // insert pointer to nodes into ordered structure to build tree
428 0 : std::multiset<AliHLTHuffmanNode*, AliHLTHuffmanNode::less> nodeCollection;
429 : // std::copy(fNodes.begin(), fNodes.end(),
430 : // std::inserter(freq_coll, freq_coll.begin()));
431 : Double_t totalWeight = 0.;
432 : Double_t leastWeight = -1.;
433 0 : for (std::vector<AliHLTHuffmanLeaveNode>::iterator i = fNodes.begin(); i
434 0 : != fNodes.end(); ++i) {
435 0 : nodeCollection.insert(&(*i));
436 0 : Double_t nodeWeight = i->GetWeight();
437 0 : totalWeight += nodeWeight;
438 0 : if (nodeWeight > 0. &&
439 0 : (leastWeight < 0. || leastWeight > nodeWeight))
440 0 : leastWeight = nodeWeight;
441 : }
442 : Double_t scaleexp = 0.;
443 0 : if (leastWeight > 0.) {
444 0 : scaleexp = std::floor(std::log10(leastWeight));
445 0 : }
446 : // float has 23 bit fraction, to be accurate for the occurence counting
447 : // number has to fit into that fraction (exponent 0)
448 0 : if (totalWeight > (0x1 << 23)) {
449 0 : if (scaleexp > 0.) {
450 0 : HLTInfo("scaling weights by exponent %f, total weight %f", scaleexp, totalWeight);
451 0 : for (std::vector<AliHLTHuffmanLeaveNode>::iterator i = fNodes.begin();
452 0 : i != fNodes.end(); ++i) {
453 0 : i->ScaleWeight(std::pow(10., scaleexp));
454 : }
455 0 : } else {
456 : // we can not scale, through a warning
457 0 : HLTWarning("single float precision does not sufficiently represent "
458 : "small differences at total weight > 2^23 (~ 8.3e6), "
459 : "total weight %f; huffman table will be generated correctly "
460 : "however the weigth of nodes stored in the object has a "
461 : "small inaccuracy",
462 : totalWeight
463 : );
464 : }
465 : }
466 0 : while (nodeCollection.size() > 1) {
467 : // insert new node into structure, combining the two with lowest probability
468 0 : AliHLTHuffmanNode* node=new AliHLTHuffmanTreeNode(*nodeCollection.begin(), *++nodeCollection.begin());
469 0 : if (!node) return kFALSE;
470 0 : nodeCollection.insert(node);
471 0 : nodeCollection.erase(nodeCollection.begin());
472 0 : nodeCollection.erase(nodeCollection.begin());
473 0 : }
474 : //assign value
475 0 : fHuffTopNode = *nodeCollection.begin();
476 0 : fHuffTopNode->AssignCode(fReverseCode);
477 0 : InitMaxCodeLength();
478 0 : return kTRUE;
479 0 : }
480 :
481 : void AliHLTHuffman::Print(Option_t* option) const {
482 0 : std::cout << GetName() << endl;
483 0 : bool bPrintShort=strcmp(option, "full")!=0;
484 0 : if (fHuffTopNode && !bPrintShort) {
485 0 : std::cout << "Huffman tree:" << endl;
486 0 : fHuffTopNode->Print();
487 0 : }
488 : Double_t uncompressedSize = 0;
489 : Double_t compressedSize = 0;
490 : Double_t totalWeight = 0;
491 0 : if (!bPrintShort)
492 0 : std::cout << std::endl << "Huffman codes:" << std::endl;
493 0 : for (AliHLTUInt64_t i = 0; i <= fMaxValue; i++) {
494 0 : Double_t nodeWeight = fNodes[i].GetWeight();
495 0 : if (!bPrintShort) fNodes[i].Print();
496 0 : totalWeight += nodeWeight;
497 0 : uncompressedSize += nodeWeight * fMaxBits;
498 0 : compressedSize += nodeWeight * fNodes[i].GetBinaryCodeLength();
499 : }
500 0 : if (uncompressedSize > 0) {
501 0 : std::cout << "compression ratio: " << compressedSize
502 0 : / uncompressedSize << std::endl;
503 0 : std::cout << "<bits> uncompressed: " << uncompressedSize / totalWeight
504 0 : << std::endl;
505 0 : std::cout << "<bits> compressed: " << compressedSize / totalWeight
506 0 : << std::endl;
507 0 : } else {
508 0 : std::cout << " no weights available" << std::endl;
509 : }
510 0 : }
511 :
512 : AliHLTHuffman& AliHLTHuffman::operator =(const AliHLTHuffman& other) {
513 0 : if (this==&other) return *this;
514 0 : fMaxValue = other.fMaxValue;
515 0 : fNodes = other.fNodes;
516 0 : fHuffTopNode = NULL;
517 0 : fMaxCodeLength = 0;
518 0 : return *this;
519 0 : }
520 :
521 : bool AliHLTHuffman::CheckConsistency() const
522 : {
523 0 : if (!fHuffTopNode) {
524 0 : cout << "huffman table not yet generated" << endl;
525 0 : }
526 :
527 0 : for (AliHLTUInt64_t v=0; v<GetMaxValue(); v++) {
528 0 : AliHLTUInt64_t codeLength=0;
529 0 : std::bitset<64> code=AliHLTHuffman::Encode(v, codeLength);
530 0 : AliHLTUInt64_t readback=0;
531 0 : AliHLTUInt32_t readbacklen=0;
532 0 : AliHLTUInt32_t readbackcodelen=0;
533 0 : if (fReverseCode) {
534 0 : code<<=64-codeLength;
535 0 : if (!DecodeMSB(code, readback, readbacklen, readbackcodelen)) {
536 0 : cout << "Decode failed" << endl;
537 0 : return false;
538 : }
539 : } else {
540 0 : if (!DecodeLSB(code, readback, readbacklen, readbackcodelen)) {
541 0 : cout << "Decode failed" << endl;
542 0 : return false;
543 : }
544 : }
545 0 : if (v!=readback) {
546 0 : cout << "readback of value " << v << " code length " << codeLength << " failed: got " << readback << " code length " << readbackcodelen << endl;
547 0 : return false;
548 : }
549 0 : }
550 0 : return true;
551 0 : }
552 :
553 : UInt_t AliHLTHuffman::InitMaxCodeLength()
554 : {
555 : // loop over leave nodes and set maximum code length
556 0 : fMaxCodeLength=0;
557 0 : for (std::vector<AliHLTHuffmanLeaveNode>::const_iterator node=fNodes.begin();
558 0 : node!=fNodes.end(); node++) {
559 0 : if (fMaxCodeLength<node->GetBinaryCodeLength())
560 0 : fMaxCodeLength=node->GetBinaryCodeLength();
561 : }
562 0 : return fMaxCodeLength;
563 : }
564 :
565 : int AliHLTHuffman::EnableDecodingMap()
566 : {
567 : // build decoder nodes from node tree
568 0 : fDecodingTopNode=NULL;
569 0 : fDecodingNodes.clear();
570 0 : if (fNodes.size()==0) {
571 0 : return 0;
572 : }
573 0 : fDecodingNodes.reserve(2*fNodes.size());
574 0 : fDecodingTopNode=BuildDecodingNode(fHuffTopNode, fDecodingNodes);
575 0 : if (!fDecodingTopNode) {
576 0 : fDecodingNodes.clear();
577 0 : } else {
578 0 : HLTError("decoder nodes created sucessfully");
579 : }
580 0 : return 0;
581 0 : }
582 :
583 : AliHLTHuffman::AliHuffmanDecodingNode* AliHLTHuffman::BuildDecodingNode(AliHLTHuffmanNode* node, vector<AliHuffmanDecodingNode>& decodernodes) const
584 : {
585 : // build and add decoder node structure corresponding to huffman node
586 0 : if (!node) {
587 0 : HLTError("invalid node pointer");
588 0 : return NULL;
589 : }
590 0 : for (vector<AliHuffmanDecodingNode>::iterator i=decodernodes.begin();
591 0 : i!=decodernodes.end(); i++) {
592 0 : if (i->fParent==node) {
593 0 : HLTError("node %p already existing in decoder nodes", node);
594 0 : return NULL;
595 : }
596 : }
597 :
598 : AliHuffmanDecodingNode* decodernode=NULL;
599 0 : if (decodernodes.size()+1>decodernodes.capacity()) {
600 0 : HLTError("initial size of array too small, can not add more nodes because pointers will become invalid when growing vector");
601 : } else {
602 0 : AliHuffmanDecodingNode dn;
603 0 : dn.fParent=node;
604 0 : dn.fValue=node->GetValue();
605 0 : dn.fLeft=NULL;
606 0 : dn.fRight=NULL;
607 0 : dn.fBinaryCodeLength=0;
608 0 : decodernodes.push_back(dn);
609 0 : decodernode=&(decodernodes.back());
610 0 : }
611 :
612 0 : if (decodernode && decodernode->fValue<0) {
613 0 : decodernode->fRight=BuildDecodingNode(node->GetRightChild(), decodernodes);
614 0 : decodernode->fLeft=BuildDecodingNode(node->GetLeftChild(), decodernodes);
615 0 : if (decodernode->fLeft==NULL || decodernode->fRight==0) {
616 0 : HLTError("failed to build corresponding decoder node for node %p", node);
617 : decodernode=NULL;
618 0 : }
619 : }
620 :
621 : return decodernode;
622 0 : }
623 :
624 126 : ClassImp(AliHLTHuffman)
625 :
|
