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