AliHLTHuffmanNode& AliHLTHuffmanNode::operator =(const AliHLTHuffmanNode& other) {
/// assignment operator
+ if (this==&other) return *this;
this->fValue = other.fValue;
this->fWeight = other.fWeight;
return *this;
}
AliHLTHuffmanTreeNode::AliHLTHuffmanTreeNode(const AliHLTHuffmanTreeNode& other)
- : AliHLTHuffmanNode()
+ : AliHLTHuffmanNode(other)
, fBinaryCodeLength(other.fBinaryCodeLength)
, fBinaryCode(other.fBinaryCode)
, fLeft(other.GetLeftChild())
}
AliHLTHuffmanLeaveNode::AliHLTHuffmanLeaveNode(const AliHLTHuffmanLeaveNode& other)
- : AliHLTHuffmanNode()
+ : AliHLTHuffmanNode(other)
, fBinaryCodeLength(other.fBinaryCodeLength)
, fBinaryCode(other.fBinaryCode)
, fLeft(other.GetLeftChild())
, fNodes(0)
, fHuffTopNode(NULL)
, fReverseCode(true)
+ , fMaxCodeLength(0)
+ , fDecodingNodes()
+ , fDecodingTopNode(NULL)
{
/// nop
}
, fNodes(other.fNodes)
, fHuffTopNode(NULL)
, fReverseCode(other.fReverseCode)
+ , fMaxCodeLength(other.fMaxCodeLength)
+ , fDecodingNodes()
+ , fDecodingTopNode(NULL)
{
/// nop
}
, fNodes((((AliHLTUInt64_t) 1) << maxBits))
, fHuffTopNode(NULL)
, fReverseCode(true)
+ , fMaxCodeLength(0)
+ , fDecodingNodes()
+ , fDecodingTopNode(NULL)
{
/// standard constructor
for (AliHLTUInt64_t i = 0; i <= fMaxValue; i++) {
return dummy;
}
-Bool_t AliHLTHuffman::Decode(std::bitset<64> bits, AliHLTUInt64_t& value,
- AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const {
- // TODO: check decoding logic, righ now it is just as written
+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;
if (currNode->GetValue() >= 0) {
// follow left branch
currNode = currNode->GetLeftChild();
bits >>= 1;
- if (currNode->GetValue() >= 0) {
+ if (currNode && currNode->GetValue() >= 0) {
value = currNode->GetValue();
length = fMaxBits;
codeLength = currNode->GetBinaryCodeLength();
if (!bits[0] && currNode->GetRightChild()) {
currNode = currNode->GetRightChild();
bits >>= 1;
- if (currNode->GetValue() >= 0) {
+ if (currNode && currNode->GetValue() >= 0) {
value = currNode->GetValue();
length = fMaxBits;
codeLength = currNode->GetBinaryCodeLength();
return kFALSE;
}
+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;
+ if (currNode->GetValue() >= 0) {
+ // handle case with just one node - also quite unlikely
+ value = currNode->GetValue();
+ return kTRUE;
+ }
+ while (currNode) {
+ if (bits[63] && currNode->GetLeftChild()) {
+ // follow left branch
+ currNode = currNode->GetLeftChild();
+ bits <<= 1;
+ if (currNode && currNode->GetValue() >= 0) {
+ value = currNode->GetValue();
+ length = fMaxBits;
+ codeLength = currNode->GetBinaryCodeLength();
+ return kTRUE;
+ }
+ continue;
+ }
+ if (!bits[63] && currNode->GetRightChild()) {
+ currNode = currNode->GetRightChild();
+ bits <<= 1;
+ if (currNode && currNode->GetValue() >= 0) {
+ value = currNode->GetValue();
+ length = fMaxBits;
+ codeLength = currNode->GetBinaryCodeLength();
+ return kTRUE;
+ }
+ continue;
+ }
+ break;
+ }
+ value = ((AliHLTUInt64_t)1) << 63;
+ 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 && 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 && 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) {
//assign value
fHuffTopNode = *nodeCollection.begin();
fHuffTopNode->AssignCode(fReverseCode);
+ InitMaxCodeLength();
return kTRUE;
}
void AliHLTHuffman::Print(Option_t* option) const {
std::cout << GetName() << endl;
- bool bPrintShort=strcmp(option, "short")==0;
+ bool bPrintShort=strcmp(option, "full")!=0;
if (fHuffTopNode && !bPrintShort) {
std::cout << "Huffman tree:" << endl;
fHuffTopNode->Print();
}
AliHLTHuffman& AliHLTHuffman::operator =(const AliHLTHuffman& other) {
+ if (this==&other) return *this;
fMaxValue = other.fMaxValue;
fNodes = other.fNodes;
fHuffTopNode = NULL;
+ fMaxCodeLength = 0;
return *this;
}
AliHLTUInt32_t readbacklen=0;
AliHLTUInt32_t readbackcodelen=0;
if (fReverseCode) {
- // reverse if needed
- // Note: for optimized bit stream the huffman code is reversed, and
- // that needs to be taken into account
- std::bitset<64> rcode;
- for (AliHLTUInt64_t i=0; i<codeLength; i++) {rcode<<=1; rcode[0]=code[i];}
- code=rcode;
- }
- if (!Decode(code, readback, readbacklen, readbackcodelen)) {
+ code<<=64-codeLength;
+ if (!DecodeMSB(code, readback, readbacklen, readbackcodelen)) {
+ cout << "Decode failed" << endl;
+ return false;
+ }
+ } else {
+ if (!DecodeLSB(code, readback, readbacklen, readbackcodelen)) {
cout << "Decode failed" << endl;
return false;
}
+ }
if (v!=readback) {
cout << "readback of value " << v << " code length " << codeLength << " failed: got " << readback << " code length " << readbackcodelen << endl;
return false;
return true;
}
+UInt_t AliHLTHuffman::InitMaxCodeLength()
+{
+ // loop over leave nodes and set maximum code length
+ fMaxCodeLength=0;
+ for (std::vector<AliHLTHuffmanLeaveNode>::const_iterator node=fNodes.begin();
+ node!=fNodes.end(); node++) {
+ if (fMaxCodeLength<node->GetBinaryCodeLength())
+ fMaxCodeLength=node->GetBinaryCodeLength();
+ }
+ 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)
git://git.uio.no / u / mrichter / AliRoot.git / blobdiff