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         this->fValue = other.fValue;
  48         this->fWeight = other.fWeight;
  49         return *this;
  50 }
  51
  52 AliHLTHuffmanNode::~AliHLTHuffmanNode() {
  53 }
  54
  55 void AliHLTHuffmanNode::AssignCode(bool bReverse) {
  56         /// assign code to this node loop to right and left nodes
  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.
  66         if (GetLeftChild()) {
  67           if (bReverse) {
  68                 std::bitset < 64 > v = (this->GetBinaryCode() << 1);
  69                 v.set(0);
  70                 GetLeftChild()->SetBinaryCode(this->GetBinaryCodeLength() + 1, v);
  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);
  78         }
  79         if (GetRightChild()) {
  80           if (bReverse) {
  81                 std::bitset < 64 > v = (this->GetBinaryCode() << 1);
  82                 v.reset(0);
  83                 GetRightChild()->SetBinaryCode(this->GetBinaryCodeLength() + 1, v);
  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);
  91         }
  92 }
  93
  94 void 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
 107 ClassImp(AliHLTHuffmanNode)
 108
 109 ///////////////////////////////////////////////////////////////////////////////////////////////
 110
 111 AliHLTHuffmanTreeNode::AliHLTHuffmanTreeNode()
 112         : AliHLTHuffmanNode()
 113         , fBinaryCodeLength(0)
 114         , fBinaryCode(0)
 115         , fLeft(NULL)
 116         , fRight(NULL)
 117 {
 118         // nop
 119 }
 120
 121 AliHLTHuffmanTreeNode::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
 131 AliHLTHuffmanTreeNode& 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
 143 AliHLTHuffmanTreeNode::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
 158 AliHLTHuffmanTreeNode::~AliHLTHuffmanTreeNode()
 159 {
 160         // nop
 161 }
 162
 163 ClassImp(AliHLTHuffmanTreeNode)
 164
 165 ///////////////////////////////////////////////////////////////////////////////////////////////
 166
 167 AliHLTHuffmanLeaveNode::AliHLTHuffmanLeaveNode()
 168         : AliHLTHuffmanNode()
 169         , fBinaryCodeLength(0)
 170         , fBinaryCode(0)
 171         , fLeft(NULL)
 172         , fRight(NULL)
 173 {
 174         // nop
 175 }
 176
 177 AliHLTHuffmanLeaveNode::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
 187 AliHLTHuffmanLeaveNode& 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
 199 AliHLTHuffmanLeaveNode::~AliHLTHuffmanLeaveNode()
 200 {
 201         // nop
 202 }
 203
 204 ClassImp(AliHLTHuffmanLeaveNode)
 205
 206 ///////////////////////////////////////////////////////////////////////////////////////////////
 207
 208 AliHLTHuffman::AliHLTHuffman()
 209         : TNamed()
 210         , fMaxBits(0)
 211         , fMaxValue(0)
 212         , fNodes(0)
 213         , fHuffTopNode(NULL)
 214         , fReverseCode(true)
 215 {
 216         /// nop
 217 }
 218
 219 AliHLTHuffman::AliHLTHuffman(const AliHLTHuffman& other)
 220         : TNamed()
 221         , AliHLTLogging()
 222         , fMaxBits(other.fMaxBits)
 223         , fMaxValue(other.fMaxValue)
 224         , fNodes(other.fNodes)
 225         , fHuffTopNode(NULL)
 226         , fReverseCode(other.fReverseCode)
 227 {
 228         /// nop
 229 }
 230
 231 AliHLTHuffman::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)
 237         , fReverseCode(true)
 238  {
 239         /// standard constructor
 240         for (AliHLTUInt64_t i = 0; i <= fMaxValue; i++) {
 241                 fNodes[i].SetValue(i);
 242         }
 243 }
 244
 245 AliHLTHuffman::~AliHLTHuffman() {
 246         /// destructor, nop
 247 }
 248
 249 const 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
 269 Bool_t AliHLTHuffman::Decode(std::bitset<64> bits, AliHLTUInt64_t& value,
 270                              AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const {
 271         // TODO: check decoding logic, righ now it is just as written
 272         AliHLTHuffmanNode* currNode = fHuffTopNode;
 273         if (!currNode) return kFALSE;
 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();
 286                                 length = fMaxBits;
 287                                 codeLength = currNode->GetBinaryCodeLength();
 288                                 return kTRUE;
 289                         }
 290                         continue;
 291                 }
 292                 if (!bits[0] && currNode->GetRightChild()) {
 293                         currNode = currNode->GetRightChild();
 294                         bits >>= 1;
 295                         if (currNode->GetValue() >= 0) {
 296                                 value = currNode->GetValue();
 297                                 length = fMaxBits;
 298                                 codeLength = currNode->GetBinaryCodeLength();
 299                                 return kTRUE;
 300                         }
 301                         continue;
 302                 }
 303                 break;
 304         }
 305         value = ((AliHLTUInt64_t)1) << 63;
 306         return kFALSE;
 307 }
 308
 309 Bool_t AliHLTHuffman::AddTrainingValue(const AliHLTUInt64_t value,
 310                 const Float_t weight) {
 311         if (value > fMaxValue) {
 312                 /* TODO: ERROR message */
 313                 return kFALSE;
 314         }
 315         fNodes[value].AddWeight(weight);
 316         return kTRUE;
 317 }
 318
 319 Bool_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
 330                 AliHLTHuffmanNode* node=new AliHLTHuffmanTreeNode(*nodeCollection.begin(), *++nodeCollection.begin());
 331                 if (!node) return kFALSE;
 332                 nodeCollection.insert(node);
 333                 nodeCollection.erase(nodeCollection.begin());
 334                 nodeCollection.erase(nodeCollection.begin());
 335         }
 336         //assign value
 337         fHuffTopNode = *nodeCollection.begin();
 338         fHuffTopNode->AssignCode(fReverseCode);
 339         return kTRUE;
 340 }
 341
 342 void 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
 371 AliHLTHuffman& AliHLTHuffman::operator =(const AliHLTHuffman& other) {
 372         fMaxValue = other.fMaxValue;
 373         fNodes = other.fNodes;
 374         fHuffTopNode = NULL;
 375         return *this;
 376 }
 377
 378 bool 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
 410 ClassImp(AliHLTHuffman)
 411