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 {
 218         /// nop
 219 }
 220
 221 AliHLTHuffman::AliHLTHuffman(const AliHLTHuffman& other)
 222         : TNamed()
 223         , AliHLTLogging()
 224         , fMaxBits(other.fMaxBits)
 225         , fMaxValue(other.fMaxValue)
 226         , fNodes(other.fNodes)
 227         , fHuffTopNode(NULL)
 228         , fReverseCode(other.fReverseCode)
 229         , fMaxCodeLength(other.fMaxCodeLength)
 230 {
 231         /// nop
 232 }
 233
 234 AliHLTHuffman::AliHLTHuffman(const char* name, UInt_t maxBits)
 235         : TNamed(name, name)
 236         , fMaxBits(maxBits)
 237         , fMaxValue((((AliHLTUInt64_t) 1) << maxBits) - 1)
 238         , fNodes((((AliHLTUInt64_t) 1) << maxBits))
 239         , fHuffTopNode(NULL)
 240         , fReverseCode(true)
 241         , fMaxCodeLength(0)
 242  {
 243         /// standard constructor
 244         for (AliHLTUInt64_t i = 0; i <= fMaxValue; i++) {
 245                 fNodes[i].SetValue(i);
 246         }
 247 }
 248
 249 AliHLTHuffman::~AliHLTHuffman() {
 250         /// destructor, nop
 251 }
 252
 253 const std::bitset<64>& AliHLTHuffman::Encode(const AliHLTUInt64_t v, AliHLTUInt64_t& codeLength) const {
 254         /// encode a value
 255         codeLength = 0;
 256         if (v <= fMaxValue) {
 257                 // valid symbol/value
 258                 if (fHuffTopNode) {
 259                         // huffman code has been generated
 260                         codeLength = fNodes[v].GetBinaryCodeLength();
 261                         return fNodes[v].GetBinaryCode();
 262                 } else {
 263                   HLTError("encoder '%s' does not seem to be initialized", GetName());
 264                 }
 265         } else {
 266           HLTError("encoder %s: value %llu exceeds range of %d bits", GetName(), v, GetMaxBits());
 267         }
 268
 269         static const std::bitset<64> dummy;
 270         return dummy;
 271 }
 272
 273 Bool_t AliHLTHuffman::DecodeDown(std::bitset<64> bits, AliHLTUInt64_t& value,
 274                              AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const {
 275         // huffman decoding
 276         AliHLTHuffmanNode* currNode = fHuffTopNode;
 277         if (!currNode) return kFALSE;
 278         if (currNode->GetValue() >= 0) {
 279                 // handle case with just one node - also quite unlikely
 280                 value = currNode->GetValue();
 281                 return kTRUE;
 282         }
 283         while (currNode) {
 284                 if (bits[0] && currNode->GetLeftChild()) {
 285                         // follow left branch
 286                         currNode = currNode->GetLeftChild();
 287                         bits >>= 1;
 288                         if (currNode->GetValue() >= 0) {
 289                                 value = currNode->GetValue();
 290                                 length = fMaxBits;
 291                                 codeLength = currNode->GetBinaryCodeLength();
 292                                 return kTRUE;
 293                         }
 294                         continue;
 295                 }
 296                 if (!bits[0] && currNode->GetRightChild()) {
 297                         currNode = currNode->GetRightChild();
 298                         bits >>= 1;
 299                         if (currNode->GetValue() >= 0) {
 300                                 value = currNode->GetValue();
 301                                 length = fMaxBits;
 302                                 codeLength = currNode->GetBinaryCodeLength();
 303                                 return kTRUE;
 304                         }
 305                         continue;
 306                 }
 307                 break;
 308         }
 309         value = ((AliHLTUInt64_t)1) << 63;
 310         return kFALSE;
 311 }
 312
 313 Bool_t AliHLTHuffman::DecodeUp(std::bitset<64> bits, AliHLTUInt64_t& value,
 314                              AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const {
 315         // huffman decoding
 316         AliHLTHuffmanNode* currNode = fHuffTopNode;
 317         if (!currNode) return kFALSE;
 318         if (currNode->GetValue() >= 0) {
 319                 // handle case with just one node - also quite unlikely
 320                 value = currNode->GetValue();
 321                 return kTRUE;
 322         }
 323         while (currNode) {
 324                 if (bits[63] && currNode->GetLeftChild()) {
 325                         // follow left branch
 326                         currNode = currNode->GetLeftChild();
 327                         bits <<= 1;
 328                         if (currNode->GetValue() >= 0) {
 329                                 value = currNode->GetValue();
 330                                 length = fMaxBits;
 331                                 codeLength = currNode->GetBinaryCodeLength();
 332                                 return kTRUE;
 333                         }
 334                         continue;
 335                 }
 336                 if (!bits[63] && currNode->GetRightChild()) {
 337                         currNode = currNode->GetRightChild();
 338                         bits <<= 1;
 339                         if (currNode->GetValue() >= 0) {
 340                                 value = currNode->GetValue();
 341                                 length = fMaxBits;
 342                                 codeLength = currNode->GetBinaryCodeLength();
 343                                 return kTRUE;
 344                         }
 345                         continue;
 346                 }
 347                 break;
 348         }
 349         value = ((AliHLTUInt64_t)1) << 63;
 350         return kFALSE;
 351 }
 352
 353 Bool_t AliHLTHuffman::AddTrainingValue(const AliHLTUInt64_t value,
 354                 const Float_t weight) {
 355         if (value > fMaxValue) {
 356                 /* TODO: ERROR message */
 357                 return kFALSE;
 358         }
 359         fNodes[value].AddWeight(weight);
 360         return kTRUE;
 361 }
 362
 363 Bool_t AliHLTHuffman::GenerateHuffmanTree() {
 364         // insert pointer to nodes into ordered structure to build tree
 365         std::multiset<AliHLTHuffmanNode*, AliHLTHuffmanNode::less> nodeCollection;
 366         //      std::copy(fNodes.begin(), fNodes.end(),
 367         //                      std::inserter(freq_coll, freq_coll.begin()));
 368         for (std::vector<AliHLTHuffmanLeaveNode>::iterator i = fNodes.begin(); i
 369                         != fNodes.end(); ++i) {
 370                 nodeCollection.insert(&(*i));
 371         }
 372         while (nodeCollection.size() > 1) {
 373                 // insert new node into structure, combining the two with lowest probability
 374                 AliHLTHuffmanNode* node=new AliHLTHuffmanTreeNode(*nodeCollection.begin(), *++nodeCollection.begin());
 375                 if (!node) return kFALSE;
 376                 nodeCollection.insert(node);
 377                 nodeCollection.erase(nodeCollection.begin());
 378                 nodeCollection.erase(nodeCollection.begin());
 379         }
 380         //assign value
 381         fHuffTopNode = *nodeCollection.begin();
 382         fHuffTopNode->AssignCode(fReverseCode);
 383         InitMaxCodeLength();
 384         return kTRUE;
 385 }
 386
 387 void AliHLTHuffman::Print(Option_t* option) const {
 388         std::cout << GetName() << endl;
 389         bool bPrintShort=strcmp(option, "full")!=0;
 390         if (fHuffTopNode && !bPrintShort) {
 391                 std::cout << "Huffman tree:" << endl;
 392                 fHuffTopNode->Print();
 393         }
 394         Double_t uncompressedSize = 0;
 395         Double_t compressedSize = 0;
 396         Double_t totalWeight = 0;
 397         if (!bPrintShort)
 398           std::cout << std::endl << "Huffman codes:" << std::endl;
 399         for (AliHLTUInt64_t i = 0; i <= fMaxValue; i++) {
 400           if (!bPrintShort) fNodes[i].Print();
 401                 totalWeight += fNodes[i].GetWeight();
 402                 uncompressedSize += fNodes[i].GetWeight() * fMaxBits;
 403                 compressedSize += fNodes[i].GetWeight()
 404                                 * fNodes[i].GetBinaryCodeLength();
 405         }
 406         if (uncompressedSize > 0) {
 407                 std::cout << "compression ratio: " << compressedSize
 408                                 / uncompressedSize << std::endl;
 409                 std::cout << "<bits> uncompressed: " << uncompressedSize / totalWeight
 410                                 << std::endl;
 411                 std::cout << "<bits> compressed:   " << compressedSize / totalWeight
 412                                 << std::endl;
 413         }
 414 }
 415
 416 AliHLTHuffman& AliHLTHuffman::operator =(const AliHLTHuffman& other) {
 417         if (this==&other) return *this;
 418         fMaxValue = other.fMaxValue;
 419         fNodes = other.fNodes;
 420         fHuffTopNode = NULL;
 421         fMaxCodeLength = 0;
 422         return *this;
 423 }
 424
 425 bool AliHLTHuffman::CheckConsistency() const
 426 {
 427   if (!fHuffTopNode) {
 428     cout << "huffman table not yet generated" << endl;
 429   }
 430
 431   for (AliHLTUInt64_t v=0; v<GetMaxValue(); v++) {
 432     AliHLTUInt64_t codeLength=0;
 433     std::bitset<64> code=AliHLTHuffman::Encode(v, codeLength);
 434     AliHLTUInt64_t readback=0;
 435     AliHLTUInt32_t readbacklen=0;
 436     AliHLTUInt32_t readbackcodelen=0;
 437     if (fReverseCode) {
 438       code<<=64-codeLength;
 439       if (!DecodeUp(code, readback, readbacklen, readbackcodelen)) {
 440         cout << "Decode failed" << endl;
 441         return false;
 442       }
 443     } else {
 444     if (!DecodeDown(code, readback, readbacklen, readbackcodelen)) {
 445       cout << "Decode failed" << endl;
 446       return false;
 447     }
 448     }
 449     if (v!=readback) {
 450       cout << "readback of value " << v << " code length " << codeLength << " failed: got " << readback << " code length " << readbackcodelen << endl;
 451       return false;
 452     }
 453   }
 454   return true;
 455 }
 456
 457 UInt_t AliHLTHuffman::InitMaxCodeLength()
 458 {
 459   // loop over leave nodes and set maximum code length
 460   fMaxCodeLength=0;
 461   for (std::vector<AliHLTHuffmanLeaveNode>::const_iterator node=fNodes.begin();
 462        node!=fNodes.end(); node++) {
 463     if (fMaxCodeLength<node->GetBinaryCodeLength())
 464       fMaxCodeLength=node->GetBinaryCodeLength();
 465   }
 466   return fMaxCodeLength;
 467 }
 468
 469 ClassImp(AliHLTHuffman)
 470