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