From 7227b364280147c60cc3e9eccb6339b394e94011 Mon Sep 17 00:00:00 2001 From: richterm Date: Thu, 3 Jan 2013 12:46:10 +0000 Subject: [PATCH] code cleanup: renaming functions; adding prototype code for later development; no functional change --- HLT/BASE/AliHLTDataInflaterHuffman.cxx | 2 +- HLT/BASE/AliHLTHuffman.cxx | 121 +++++++++++++++++++++++-- HLT/BASE/AliHLTHuffman.h | 27 +++++- 3 files changed, 140 insertions(+), 10 deletions(-) diff --git a/HLT/BASE/AliHLTDataInflaterHuffman.cxx b/HLT/BASE/AliHLTDataInflaterHuffman.cxx index 626b62dc602..806c1cd529b 100644 --- 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 (fInputLengthGetName(), codeLength, fInputLength); diff --git a/HLT/BASE/AliHLTHuffman.cxx b/HLT/BASE/AliHLTHuffman.cxx index 2ffdc609df5..bf89f1468aa 100644 --- 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& decodernodes) const +{ + // build and add decoder node structure corresponding to huffman node + if (!node) { + HLTError("invalid node pointer"); + return NULL; + } + for (vector::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 8cba6b57e4e..b11857b4972 100644 --- 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& decodingnodes) const; + UInt_t fMaxBits; // bit lenght UInt_t fMaxValue; // maximum value std::vector 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 fDecodingNodes; //! array of reduced nodes + AliHuffmanDecodingNode* fDecodingTopNode; //! top node of reduced nodes -ClassDef(AliHLTHuffman, 3) +ClassDef(AliHLTHuffman, 4) }; #endif -- 2.43.5