[u/mrichter/AliRoot.git] / HLT / BASE / AliHLTHuffman.cxx

// $Id$
//**************************************************************************
//* This file is property of and copyright by the ALICE HLT Project        *
//* ALICE Experiment at CERN, All rights reserved.                         *
//*                                                                        *
//* Primary Authors: Thorsten Kollegger <kollegge@ikf.uni-frankfurt.de>    *
//*                  for The ALICE HLT Project.                            *
//*                                                                        *
//* Permission to use, copy, modify and distribute this software and its   *
//* documentation strictly for non-commercial purposes is hereby granted   *
//* without fee, provided that the above copyright notice appears in all   *
//* copies and that both the copyright notice and this permission notice   *
//* appear in the supporting documentation. The authors make no claims     *
//* about the suitability of this software for any purpose. It is          *
//* provided "as is" without express or implied warranty.                  *
//**************************************************************************

/// @file   AliHLTHuffman.cxx
/// @author Thorsten Kollegger, Matthias Richter
/// @date   2011-08-14
/// @brief  Huffman code generator/encoder/decoder

#include "AliHLTHuffman.h"

#include <iostream>
#include <set>
#include <bitset>
#include <algorithm>

AliHLTHuffmanNode::AliHLTHuffmanNode() 
	: TObject()
	, fValue(-1)
	, fWeight(0.)
{
        // nop
}

AliHLTHuffmanNode::AliHLTHuffmanNode(const AliHLTHuffmanNode& other)
	: TObject()
	, fValue(other.GetValue())
	, fWeight(other.GetWeight())
{
}

AliHLTHuffmanNode& AliHLTHuffmanNode::operator =(const AliHLTHuffmanNode& other) {
        /// assignment operator
        if (this==&other) return *this;
	this->fValue = other.fValue;
	this->fWeight = other.fWeight;
	return *this;
}

AliHLTHuffmanNode::~AliHLTHuffmanNode() {
}

void AliHLTHuffmanNode::AssignCode(bool bReverse) {
        /// assign code to this node loop to right and left nodes
        /// the decoding always has to start from the least significant bit since the
        /// code length is variable. Thats why the bit corresponding to the parent node
        /// has to be right of the bit of child nodes, i.e. bits correspond to the
        /// current code length. For storage in a bit stream however, bits are stored
        /// in a stream from MSB to LSB and overwrapping to the MSBs of the next byte.
        /// Here the reverse code is needed and the word of fixed length read from the
        /// stream needs to be reversed before decoding.
        /// Note: by changing the AliHLTDataDeflater interface to write from LSB to MSB
        /// this can be avoided.
	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* /*option*/) const {
        /// print info
	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)
{
        // nop
}

AliHLTHuffmanTreeNode::AliHLTHuffmanTreeNode(const AliHLTHuffmanTreeNode& other)
	: AliHLTHuffmanNode()
	, fBinaryCodeLength(other.fBinaryCodeLength)
	, fBinaryCode(other.fBinaryCode)
	, fLeft(other.GetLeftChild())
	, fRight(other.GetRightChild())
{

}

AliHLTHuffmanTreeNode& AliHLTHuffmanTreeNode::operator =(const AliHLTHuffmanTreeNode& other)
{
        /// assignment operator
        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() 
{
        // nop
}

ClassImp(AliHLTHuffmanTreeNode)

///////////////////////////////////////////////////////////////////////////////////////////////

AliHLTHuffmanLeaveNode::AliHLTHuffmanLeaveNode() 
	: AliHLTHuffmanNode()
	, fBinaryCodeLength(0)
	, fBinaryCode(0)
	, fLeft(NULL)
	, fRight(NULL)
{
        // nop
}

AliHLTHuffmanLeaveNode::AliHLTHuffmanLeaveNode(const AliHLTHuffmanLeaveNode& other)
	: AliHLTHuffmanNode()
	, fBinaryCodeLength(other.fBinaryCodeLength)
	, fBinaryCode(other.fBinaryCode)
	, fLeft(other.GetLeftChild())
	, fRight(other.GetRightChild())
{

}

AliHLTHuffmanLeaveNode& AliHLTHuffmanLeaveNode::operator =(const AliHLTHuffmanLeaveNode& other)
{
        /// assignment operator
        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() 
{
        // nop
}

ClassImp(AliHLTHuffmanLeaveNode)

///////////////////////////////////////////////////////////////////////////////////////////////

AliHLTHuffman::AliHLTHuffman()
	: TNamed()
	, fMaxBits(0)
	, fMaxValue(0)
	, fNodes(0)
	, fHuffTopNode(NULL)
	, fReverseCode(true)
{
        /// nop
}

AliHLTHuffman::AliHLTHuffman(const AliHLTHuffman& other)
	: TNamed()
	, AliHLTLogging()
	, fMaxBits(other.fMaxBits)
	, fMaxValue(other.fMaxValue)
	, fNodes(other.fNodes)
	, fHuffTopNode(NULL)
	, fReverseCode(other.fReverseCode)
{
        /// nop
}

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)
 {
        /// standard constructor
	for (AliHLTUInt64_t i = 0; i <= fMaxValue; i++) {
		fNodes[i].SetValue(i);
	}
}

AliHLTHuffman::~AliHLTHuffman() {
        /// destructor, nop
}

const std::bitset<64>& AliHLTHuffman::Encode(const AliHLTUInt64_t v, AliHLTUInt64_t& codeLength) const {
        /// encode a value
	codeLength = 0;
	if (v <= fMaxValue) {
		// valid symbol/value
		if (fHuffTopNode) {
			// huffman code has been generated
			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::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
	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[0] && currNode->GetLeftChild()) {
			// follow left branch
			currNode = currNode->GetLeftChild();
			bits >>= 1;
			if (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->GetValue() >= 0) {
				value = currNode->GetValue();
				length = fMaxBits;
				codeLength = currNode->GetBinaryCodeLength();
				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) {
		/* TODO: ERROR message */
		return kFALSE;
	}
	fNodes[value].AddWeight(weight);
	return kTRUE;
}

Bool_t AliHLTHuffman::GenerateHuffmanTree() {
	// insert pointer to nodes into ordered structure to build tree
	std::multiset<AliHLTHuffmanNode*, AliHLTHuffmanNode::less> nodeCollection;
	//	std::copy(fNodes.begin(), fNodes.end(),
	//			std::inserter(freq_coll, freq_coll.begin()));
	for (std::vector<AliHLTHuffmanLeaveNode>::iterator i = fNodes.begin(); i
			!= fNodes.end(); ++i) {
		nodeCollection.insert(&(*i));
	}
	while (nodeCollection.size() > 1) {
		// insert new node into structure, combining the two with lowest probability
		AliHLTHuffmanNode* node=new AliHLTHuffmanTreeNode(*nodeCollection.begin(), *++nodeCollection.begin());
		if (!node) return kFALSE;
		nodeCollection.insert(node);
		nodeCollection.erase(nodeCollection.begin());
		nodeCollection.erase(nodeCollection.begin());
	}
	//assign value
	fHuffTopNode = *nodeCollection.begin();
	fHuffTopNode->AssignCode(fReverseCode);
	return kTRUE;
}

void AliHLTHuffman::Print(Option_t* option) const {
        std::cout << GetName() << endl;
        bool bPrintShort=strcmp(option, "short")==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;
	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) {
      // 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)) {
      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;
}

ClassImp(AliHLTHuffman)
Commit	Line	Data
6a1b3945	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
5c8ae5fb	47	if (this==&other) return *this;
6a1b3945	48	this->fValue = other.fValue;
	49	this->fWeight = other.fWeight;
	50	return *this;
	51	}
	52
	53	AliHLTHuffmanNode::~AliHLTHuffmanNode() {
	54	}
	55
9409b4b1	56	void AliHLTHuffmanNode::AssignCode(bool bReverse) {
6a1b3945	57	/// assign code to this node loop to right and left nodes
9409b4b1	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.
6a1b3945	67	if (GetLeftChild()) {
9409b4b1	68	if (bReverse) {
6a1b3945	69	std::bitset < 64 > v = (this->GetBinaryCode() << 1);
	70	v.set(0);
	71	GetLeftChild()->SetBinaryCode(this->GetBinaryCodeLength() + 1, v);
9409b4b1	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);
6a1b3945	79	}
6a1b3945	80	if (GetRightChild()) {
9409b4b1	81	if (bReverse) {
6a1b3945	82	std::bitset < 64 > v = (this->GetBinaryCode() << 1);
	83	v.reset(0);
	84	GetRightChild()->SetBinaryCode(this->GetBinaryCodeLength() + 1, v);
9409b4b1	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);
6a1b3945	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)
9409b4b1	215	, fReverseCode(true)
6a1b3945	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)
9409b4b1	226	, fHuffTopNode(NULL)
	227	, fReverseCode(other.fReverseCode)
	228	{
6a1b3945	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)
9409b4b1	238	, fReverseCode(true)
6a1b3945	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
9409b4b1	270	Bool_t AliHLTHuffman::Decode(std::bitset<64> bits, AliHLTUInt64_t& value,
9409b4b1	271	AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const {
6a1b3945	272	// TODO: check decoding logic, righ now it is just as written
6a1b3945	273	AliHLTHuffmanNode* currNode = fHuffTopNode;
cac77957	274	if (!currNode) return kFALSE;
6a1b3945	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();
9409b4b1	287	length = fMaxBits;
9409b4b1	288	codeLength = currNode->GetBinaryCodeLength();
6a1b3945	289	return kTRUE;
6a1b3945	290	}
9409b4b1	291	continue;
6a1b3945	292	}
	293	if (!bits[0] && currNode->GetRightChild()) {
	294	currNode = currNode->GetRightChild();
	295	bits >>= 1;
	296	if (currNode->GetValue() >= 0) {
	297	value = currNode->GetValue();
9409b4b1	298	length = fMaxBits;
9409b4b1	299	codeLength = currNode->GetBinaryCodeLength();
6a1b3945	300	return kTRUE;
6a1b3945	301	}
9409b4b1	302	continue;
6a1b3945	303	}
9409b4b1	304	break;
6a1b3945	305	}
	306	value = ((AliHLTUInt64_t)1) << 63;
	307	return kFALSE;
	308	}
	309
	310	Bool_t AliHLTHuffman::AddTrainingValue(const AliHLTUInt64_t value,
84a44d88	311	const Float_t weight) {
6a1b3945	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
5890ed9f	331	AliHLTHuffmanNode* node=new AliHLTHuffmanTreeNode(nodeCollection.begin(), ++nodeCollection.begin());
	332	if (!node) return kFALSE;
	333	nodeCollection.insert(node);
6a1b3945	334	nodeCollection.erase(nodeCollection.begin());
	335	nodeCollection.erase(nodeCollection.begin());
	336	}
	337	//assign value
	338	fHuffTopNode = *nodeCollection.begin();
9409b4b1	339	fHuffTopNode->AssignCode(fReverseCode);
6a1b3945	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) {
5c8ae5fb	373	if (this==&other) return *this;
6a1b3945	374	fMaxValue = other.fMaxValue;
	375	fNodes = other.fNodes;
	376	fHuffTopNode = NULL;
	377	return *this;
	378	}
	379
9409b4b1	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
6a1b3945	412	ClassImp(AliHLTHuffman)
6a1b3945	413