code cleanup: renaming functions; adding prototype code for later development; no...

diff --git a/HLT/BASE/AliHLTDataInflaterHuffman.cxx b/HLT/BASE/AliHLTDataInflaterHuffman.cxx
index 626b62dc6020e5cb0ef3432810e7062d3b1d51e3..806c1cd529b18dba2e2817d24294ff7d81f125ae 100644 (file)
--- a/HLT/BASE/AliHLTDataInflaterHuffman.cxx
+++ b/HLT/BASE/AliHLTDataInflaterHuffman.cxx
@@ -141,7 +141,7 @@ bool AliHLTDataInflaterHuffman::NextValue(AliHLTUInt64_t& value, AliHLTUInt32_t&
     fInputLength+=inputLength;
   }
   AliHLTUInt32_t codeLength=0;
-  if (!fHuffmanCoders[fCurrentParameter]->DecodeUp(fInput, value, length, codeLength)) return false;
+  if (!fHuffmanCoders[fCurrentParameter]->DecodeMSB(fInput, value, length, codeLength)) return false;
   if (fInputLength<codeLength) {
     HLTError("huffman decoder '%s' pretends to have %d bit(s) decoded, but only %d available",
             fHuffmanCoders[fCurrentParameter]->GetName(), codeLength, fInputLength);

diff --git a/HLT/BASE/AliHLTHuffman.cxx b/HLT/BASE/AliHLTHuffman.cxx
index 2ffdc609df5940d5fe5d0ebba2871d668b860883..bf89f1468aa41e940dbe2aab12b4ee3bb966211c 100644 (file)
--- a/HLT/BASE/AliHLTHuffman.cxx
+++ b/HLT/BASE/AliHLTHuffman.cxx
@@ -214,6 +214,8 @@ AliHLTHuffman::AliHLTHuffman()
        , fHuffTopNode(NULL)
        , fReverseCode(true)
        , fMaxCodeLength(0)
+       , fDecodingNodes()
+       , fDecodingTopNode(NULL)
 {
         /// nop
 }
@@ -227,6 +229,8 @@ AliHLTHuffman::AliHLTHuffman(const AliHLTHuffman& other)
        , fHuffTopNode(NULL)
        , fReverseCode(other.fReverseCode)
        , fMaxCodeLength(other.fMaxCodeLength)
+       , fDecodingNodes()
+       , fDecodingTopNode(NULL)
 {
         /// nop
 }
@@ -239,6 +243,8 @@ AliHLTHuffman::AliHLTHuffman(const char* name, UInt_t maxBits)
        , fHuffTopNode(NULL)
        , fReverseCode(true)
        , fMaxCodeLength(0)
+       , fDecodingNodes()
+       , fDecodingTopNode(NULL)
  {
         /// standard constructor
        for (AliHLTUInt64_t i = 0; i <= fMaxValue; i++) {
@@ -270,8 +276,9 @@ const std::bitset<64>& AliHLTHuffman::Encode(const AliHLTUInt64_t v, AliHLTUInt6
        return dummy;
 }
 
-Bool_t AliHLTHuffman::DecodeDown(std::bitset<64> bits, AliHLTUInt64_t& value,
-                            AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const {
+Bool_t AliHLTHuffman::DecodeLSB(std::bitset<64> bits, AliHLTUInt64_t& value,
+                               AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const
+{
        // huffman decoding
        AliHLTHuffmanNode* currNode = fHuffTopNode;
        if (!currNode) return kFALSE;
@@ -310,8 +317,9 @@ Bool_t AliHLTHuffman::DecodeDown(std::bitset<64> bits, AliHLTUInt64_t& value,
        return kFALSE;
 }
 
-Bool_t AliHLTHuffman::DecodeUp(std::bitset<64> bits, AliHLTUInt64_t& value,
-                            AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const {
+Bool_t AliHLTHuffman::DecodeMSB(std::bitset<64> bits, AliHLTUInt64_t& value,
+                               AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const
+{
        // huffman decoding
        AliHLTHuffmanNode* currNode = fHuffTopNode;
        if (!currNode) return kFALSE;
@@ -350,6 +358,48 @@ Bool_t AliHLTHuffman::DecodeUp(std::bitset<64> bits, AliHLTUInt64_t& value,
        return kFALSE;
 }
 
+Bool_t AliHLTHuffman::FastDecodeMSB(std::bitset<64> bits, AliHLTUInt64_t& value,
+                                   AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const
+{
+       // huffman decoding using the binary node map
+        HLTFatal("this function needs to be tested and commisioned");
+       AliHuffmanDecodingNode* currNode = fDecodingTopNode;
+       if (!currNode) return kFALSE;
+       if (currNode->fValue >= 0) {
+               // handle case with just one node - also quite unlikely
+               value = currNode->fValue;
+               return kTRUE;
+       }
+       while (currNode) {
+               if (bits[63] && currNode->fLeft) {
+                       // follow left branch
+                       currNode = currNode->fLeft;
+                       bits <<= 1;
+                       if (currNode->fValue >= 0) {
+                               value = currNode->fValue;
+                               length = fMaxBits;
+                               codeLength = currNode->fBinaryCodeLength;
+                               return kTRUE;
+                       }
+                       continue;
+               }
+               if (!bits[63] && currNode->fRight) {
+                       currNode = currNode->fRight;
+                       bits <<= 1;
+                       if (currNode->fValue >= 0) {
+                               value = currNode->fValue;
+                               length = fMaxBits;
+                               codeLength = currNode->fBinaryCodeLength;
+                               return kTRUE;
+                       }
+                       continue;
+               }
+               break;
+       }
+       value = ((AliHLTUInt64_t)1) << 63;
+       return kFALSE;
+}
+
 Bool_t AliHLTHuffman::AddTrainingValue(const AliHLTUInt64_t value,
                const Float_t weight) {
        if (value > fMaxValue) {
@@ -436,12 +486,12 @@ bool AliHLTHuffman::CheckConsistency() const
     AliHLTUInt32_t readbackcodelen=0;
     if (fReverseCode) {
       code<<=64-codeLength;
-      if (!DecodeUp(code, readback, readbacklen, readbackcodelen)) {
+      if (!DecodeMSB(code, readback, readbacklen, readbackcodelen)) {
        cout << "Decode failed" << endl;
        return false;
       }
     } else {
-    if (!DecodeDown(code, readback, readbacklen, readbackcodelen)) {
+    if (!DecodeLSB(code, readback, readbacklen, readbackcodelen)) {
       cout << "Decode failed" << endl;
       return false;
     }
@@ -466,5 +516,64 @@ UInt_t AliHLTHuffman::InitMaxCodeLength()
   return fMaxCodeLength;
 }
 
+int AliHLTHuffman::EnableDecodingMap()
+{
+  // build decoder nodes from node tree
+  fDecodingTopNode=NULL;
+  fDecodingNodes.clear();
+  if (fNodes.size()==0) {
+    return 0;
+  }
+  fDecodingNodes.reserve(2*fNodes.size());
+  fDecodingTopNode=BuildDecodingNode(fHuffTopNode, fDecodingNodes);
+  if (!fDecodingTopNode) {
+    fDecodingNodes.clear();
+  } else {
+    HLTError("decoder nodes created sucessfully");
+  }
+  return 0;
+}
+
+AliHLTHuffman::AliHuffmanDecodingNode* AliHLTHuffman::BuildDecodingNode(AliHLTHuffmanNode* node, vector<AliHuffmanDecodingNode>& decodernodes) const
+{
+  // build and add decoder node structure corresponding to huffman node
+  if (!node) {
+    HLTError("invalid node pointer");
+    return NULL;
+  }
+  for (vector<AliHuffmanDecodingNode>::iterator i=decodernodes.begin();
+       i!=decodernodes.end(); i++) {
+    if (i->fParent==node) {
+      HLTError("node %p already existing in decoder nodes", node);
+      return NULL;
+    }
+  }
+
+  AliHuffmanDecodingNode* decodernode=NULL;
+  if (decodernodes.size()+1>decodernodes.capacity()) {
+    HLTError("initial size of array too small, can not add more nodes because pointers will become invalid when growing vector");
+  } else {
+    AliHuffmanDecodingNode dn;
+    dn.fParent=node;
+    dn.fValue=node->GetValue();
+    dn.fLeft=NULL;
+    dn.fRight=NULL;
+    dn.fBinaryCodeLength=0;
+    decodernodes.push_back(dn);
+    decodernode=&(decodernodes.back());
+  }
+
+  if (decodernode && decodernode->fValue<0) {
+    decodernode->fRight=BuildDecodingNode(node->GetRightChild(), decodernodes);
+    decodernode->fLeft=BuildDecodingNode(node->GetLeftChild(), decodernodes);
+    if (decodernode->fLeft==NULL || decodernode->fRight==0) {
+      HLTError("failed to build corresponding decoder node for node %p", node);
+      decodernode=NULL;
+    }
+  }
+
+  return decodernode;
+}
+
 ClassImp(AliHLTHuffman)
 

diff --git a/HLT/BASE/AliHLTHuffman.h b/HLT/BASE/AliHLTHuffman.h
index 8cba6b57e4ebe3c3e54764226b9768e4ff2f4943..b11857b4972ef441a6b8027b3031792e2df22477 100644 (file)
--- a/HLT/BASE/AliHLTHuffman.h
+++ b/HLT/BASE/AliHLTHuffman.h
@@ -239,9 +239,12 @@ public:
        const std::bitset<64>& Encode(const AliHLTUInt64_t v, AliHLTUInt64_t& codeLength) const;
 
        /// Return value for bit pattern, LSB first
-        Bool_t DecodeDown(std::bitset<64> /*bits*/, AliHLTUInt64_t& /*value*/, AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const;
+        Bool_t DecodeLSB(std::bitset<64> /*bits*/, AliHLTUInt64_t& /*value*/, AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const;
        /// Return value for bit pattern, MSB first
-        Bool_t DecodeUp(std::bitset<64> /*bits*/, AliHLTUInt64_t& /*value*/, AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const;
+        Bool_t DecodeMSB(std::bitset<64> /*bits*/, AliHLTUInt64_t& /*value*/, AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const;
+       /// Return value for bit pattern using decoder node array, MSB first
+        Bool_t FastDecodeMSB(std::bitset<64> bits, AliHLTUInt64_t& value,
+                            AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const;
 
        /// Add a new training value (with optional weight) to the training sample
        Bool_t AddTrainingValue(const AliHLTUInt64_t value,
@@ -255,15 +258,33 @@ public:
 
         bool CheckConsistency() const;
 
+        /**
+         * Binary structure for fast access of node information
+         * in the decoding
+         */
+        struct AliHuffmanDecodingNode {
+         AliHLTHuffmanNode* fParent;      // parent
+          AliHLTInt64_t fValue;            // value
+          AliHuffmanDecodingNode* fLeft;    // left neighbor
+          AliHuffmanDecodingNode* fRight;   // right neighbor
+          AliHLTUInt8_t fBinaryCodeLength; // code length
+        };
+
+        int EnableDecodingMap();
+
 private:
+        AliHuffmanDecodingNode* BuildDecodingNode(AliHLTHuffmanNode* node, vector<AliHuffmanDecodingNode>& decodingnodes) const;
+
        UInt_t fMaxBits;    // bit lenght
        UInt_t fMaxValue;   // maximum value
        std::vector<AliHLTHuffmanLeaveNode> fNodes; // array of nodes
        AliHLTHuffmanNode* fHuffTopNode;       // top node
        bool fReverseCode; // indicate the type of the binary code
        UInt_t fMaxCodeLength; //! maximum code length
+       std::vector<AliHuffmanDecodingNode> fDecodingNodes; //! array of reduced nodes
+       AliHuffmanDecodingNode* fDecodingTopNode; //! top node of reduced nodes
 
-ClassDef(AliHLTHuffman, 3)
+ClassDef(AliHLTHuffman, 4)
 };
 
 #endif