#include "AliHLTHuffman.h"
#include <iostream>
#include <set>
#include <bitset>
#include <algorithm>
AliHLTHuffmanNode::AliHLTHuffmanNode()
: TObject()
, fValue(-1)
, fWeight(0.)
{
}
AliHLTHuffmanNode::AliHLTHuffmanNode(const AliHLTHuffmanNode& other)
: TObject()
, fValue(other.GetValue())
, fWeight(other.GetWeight())
{
}
AliHLTHuffmanNode& AliHLTHuffmanNode::operator =(const AliHLTHuffmanNode& other) {
if (this==&other) return *this;
this->fValue = other.fValue;
this->fWeight = other.fWeight;
return *this;
}
AliHLTHuffmanNode::~AliHLTHuffmanNode() {
}
void AliHLTHuffmanNode::AssignCode(bool bReverse) {
if (GetLeftChild()) {
if (bReverse) {
std::bitset < 64 > v = (this->GetBinaryCode() << 1);
v.set(0);
GetLeftChild()->SetBinaryCode(this->GetBinaryCodeLength() + 1, v);
} else {
std::bitset < 64 > v = (this->GetBinaryCode());
int codelen=this->GetBinaryCodeLength();
v.set(codelen);
GetLeftChild()->SetBinaryCode(codelen + 1, v);
}
GetLeftChild()->AssignCode(bReverse);
}
if (GetRightChild()) {
if (bReverse) {
std::bitset < 64 > v = (this->GetBinaryCode() << 1);
v.reset(0);
GetRightChild()->SetBinaryCode(this->GetBinaryCodeLength() + 1, v);
} else {
std::bitset < 64 > v = (this->GetBinaryCode());
int codelen=this->GetBinaryCodeLength();
v.reset(codelen);
GetRightChild()->SetBinaryCode(codelen + 1, v);
}
GetRightChild()->AssignCode(bReverse);
}
}
void AliHLTHuffmanNode::Print(Option_t* ) const {
std::cout << "value=" << GetValue() << ", weight=" << GetWeight() << ", length="
<< GetBinaryCodeLength() << ", code=" << GetBinaryCode().to_string()
<< std::endl;
if (GetLeftChild()) {
GetLeftChild()->Print();
}
if (GetRightChild()) {
GetRightChild()->Print();
}
}
ClassImp(AliHLTHuffmanNode)
AliHLTHuffmanTreeNode::AliHLTHuffmanTreeNode()
: AliHLTHuffmanNode()
, fBinaryCodeLength(0)
, fBinaryCode(0)
, fLeft(NULL)
, fRight(NULL)
{
}
AliHLTHuffmanTreeNode::AliHLTHuffmanTreeNode(const AliHLTHuffmanTreeNode& other)
: AliHLTHuffmanNode(other)
, fBinaryCodeLength(other.fBinaryCodeLength)
, fBinaryCode(other.fBinaryCode)
, fLeft(other.GetLeftChild())
, fRight(other.GetRightChild())
{
}
AliHLTHuffmanTreeNode& AliHLTHuffmanTreeNode::operator =(const AliHLTHuffmanTreeNode& other)
{
if (&other==this) return *this;
this->fBinaryCodeLength = other.GetBinaryCodeLength();
this->fBinaryCode = other.GetBinaryCode();
this->fLeft = other.GetLeftChild();
this->fRight = other.GetRightChild();
AliHLTHuffmanNode::operator=(other);
return *this;
}
AliHLTHuffmanTreeNode::AliHLTHuffmanTreeNode(AliHLTHuffmanNode* l, AliHLTHuffmanNode* r)
: AliHLTHuffmanNode()
, fBinaryCodeLength(0)
, fBinaryCode(0)
, fLeft(l)
, fRight(r) {
if (l && r) {
SetWeight(l->GetWeight() + r->GetWeight());
} else if (l && !r) {
SetWeight(l->GetWeight());
} else if (!l && r) {
SetWeight(r->GetWeight());
}
}
AliHLTHuffmanTreeNode::~AliHLTHuffmanTreeNode()
{
}
ClassImp(AliHLTHuffmanTreeNode)
AliHLTHuffmanLeaveNode::AliHLTHuffmanLeaveNode()
: AliHLTHuffmanNode()
, fBinaryCodeLength(0)
, fBinaryCode(0)
, fLeft(NULL)
, fRight(NULL)
{
}
AliHLTHuffmanLeaveNode::AliHLTHuffmanLeaveNode(const AliHLTHuffmanLeaveNode& other)
: AliHLTHuffmanNode(other)
, fBinaryCodeLength(other.fBinaryCodeLength)
, fBinaryCode(other.fBinaryCode)
, fLeft(other.GetLeftChild())
, fRight(other.GetRightChild())
{
}
AliHLTHuffmanLeaveNode& AliHLTHuffmanLeaveNode::operator =(const AliHLTHuffmanLeaveNode& other)
{
if (&other==this) return *this;
this->fBinaryCodeLength = other.GetBinaryCodeLength();
this->fBinaryCode = other.GetBinaryCode();
this->fLeft = other.GetLeftChild();
this->fRight = other.GetRightChild();
AliHLTHuffmanNode::operator=(other);
return *this;
}
AliHLTHuffmanLeaveNode::~AliHLTHuffmanLeaveNode()
{
}
ClassImp(AliHLTHuffmanLeaveNode)
AliHLTHuffman::AliHLTHuffman()
: TNamed()
, fMaxBits(0)
, fMaxValue(0)
, fNodes(0)
, fHuffTopNode(NULL)
, fReverseCode(true)
, fMaxCodeLength(0)
, fDecodingNodes()
, fDecodingTopNode(NULL)
{
}
AliHLTHuffman::AliHLTHuffman(const AliHLTHuffman& other)
: TNamed()
, AliHLTLogging()
, fMaxBits(other.fMaxBits)
, fMaxValue(other.fMaxValue)
, fNodes(other.fNodes)
, fHuffTopNode(NULL)
, fReverseCode(other.fReverseCode)
, fMaxCodeLength(other.fMaxCodeLength)
, fDecodingNodes()
, fDecodingTopNode(NULL)
{
}
AliHLTHuffman::AliHLTHuffman(const char* name, UInt_t maxBits)
: TNamed(name, name)
, fMaxBits(maxBits)
, fMaxValue((((AliHLTUInt64_t) 1) << maxBits) - 1)
, fNodes((((AliHLTUInt64_t) 1) << maxBits))
, fHuffTopNode(NULL)
, fReverseCode(true)
, fMaxCodeLength(0)
, fDecodingNodes()
, fDecodingTopNode(NULL)
{
for (AliHLTUInt64_t i = 0; i <= fMaxValue; i++) {
fNodes[i].SetValue(i);
}
}
AliHLTHuffman::~AliHLTHuffman() {
}
const std::bitset<64>& AliHLTHuffman::Encode(const AliHLTUInt64_t v, AliHLTUInt64_t& codeLength) const {
codeLength = 0;
if (v <= fMaxValue) {
if (fHuffTopNode) {
codeLength = fNodes[v].GetBinaryCodeLength();
return fNodes[v].GetBinaryCode();
} else {
HLTError("encoder '%s' does not seem to be initialized", GetName());
}
} else {
HLTError("encoder %s: value %llu exceeds range of %d bits", GetName(), v, GetMaxBits());
}
static const std::bitset<64> dummy;
return dummy;
}
Bool_t AliHLTHuffman::DecodeLSB(std::bitset<64> bits, AliHLTUInt64_t& value,
AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const
{
AliHLTHuffmanNode* currNode = fHuffTopNode;
if (!currNode) return kFALSE;
if (currNode->GetValue() >= 0) {
value = currNode->GetValue();
return kTRUE;
}
while (currNode) {
if (bits[0] && currNode->GetLeftChild()) {
currNode = currNode->GetLeftChild();
bits >>= 1;
if (currNode && currNode->GetValue() >= 0) {
value = currNode->GetValue();
length = fMaxBits;
codeLength = currNode->GetBinaryCodeLength();
return kTRUE;
}
continue;
}
if (!bits[0] && 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::DecodeMSB(std::bitset<64> bits, AliHLTUInt64_t& value,
AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const
{
AliHLTHuffmanNode* currNode = fHuffTopNode;
if (!currNode) return kFALSE;
if (currNode->GetValue() >= 0) {
value = currNode->GetValue();
return kTRUE;
}
while (currNode) {
if (bits[63] && currNode->GetLeftChild()) {
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
{
HLTFatal("this function needs to be tested and commisioned");
AliHuffmanDecodingNode* currNode = fDecodingTopNode;
if (!currNode) return kFALSE;
if (currNode->fValue >= 0) {
value = currNode->fValue;
return kTRUE;
}
while (currNode) {
if (bits[63] && currNode->fLeft) {
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) {
return kFALSE;
}
fNodes[value].AddWeight(weight);
return kTRUE;
}
Bool_t AliHLTHuffman::GenerateHuffmanTree() {
std::multiset<AliHLTHuffmanNode*, AliHLTHuffmanNode::less> nodeCollection;
for (std::vector<AliHLTHuffmanLeaveNode>::iterator i = fNodes.begin(); i
!= fNodes.end(); ++i) {
nodeCollection.insert(&(*i));
}
while (nodeCollection.size() > 1) {
AliHLTHuffmanNode* node=new AliHLTHuffmanTreeNode(*nodeCollection.begin(), *++nodeCollection.begin());
if (!node) return kFALSE;
nodeCollection.insert(node);
nodeCollection.erase(nodeCollection.begin());
nodeCollection.erase(nodeCollection.begin());
}
fHuffTopNode = *nodeCollection.begin();
fHuffTopNode->AssignCode(fReverseCode);
InitMaxCodeLength();
return kTRUE;
}
void AliHLTHuffman::Print(Option_t* option) const {
std::cout << GetName() << endl;
bool bPrintShort=strcmp(option, "full")!=0;
if (fHuffTopNode && !bPrintShort) {
std::cout << "Huffman tree:" << endl;
fHuffTopNode->Print();
}
Double_t uncompressedSize = 0;
Double_t compressedSize = 0;
Double_t totalWeight = 0;
if (!bPrintShort)
std::cout << std::endl << "Huffman codes:" << std::endl;
for (AliHLTUInt64_t i = 0; i <= fMaxValue; i++) {
if (!bPrintShort) fNodes[i].Print();
totalWeight += fNodes[i].GetWeight();
uncompressedSize += fNodes[i].GetWeight() * fMaxBits;
compressedSize += fNodes[i].GetWeight()
* fNodes[i].GetBinaryCodeLength();
}
if (uncompressedSize > 0) {
std::cout << "compression ratio: " << compressedSize
/ uncompressedSize << std::endl;
std::cout << "<bits> uncompressed: " << uncompressedSize / totalWeight
<< std::endl;
std::cout << "<bits> compressed: " << compressedSize / totalWeight
<< std::endl;
}
}
AliHLTHuffman& AliHLTHuffman::operator =(const AliHLTHuffman& other) {
if (this==&other) return *this;
fMaxValue = other.fMaxValue;
fNodes = other.fNodes;
fHuffTopNode = NULL;
fMaxCodeLength = 0;
return *this;
}
bool AliHLTHuffman::CheckConsistency() const
{
if (!fHuffTopNode) {
cout << "huffman table not yet generated" << endl;
}
for (AliHLTUInt64_t v=0; v<GetMaxValue(); v++) {
AliHLTUInt64_t codeLength=0;
std::bitset<64> code=AliHLTHuffman::Encode(v, codeLength);
AliHLTUInt64_t readback=0;
AliHLTUInt32_t readbacklen=0;
AliHLTUInt32_t readbackcodelen=0;
if (fReverseCode) {
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()
{
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()
{
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
{
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)