[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
	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
		nodeCollection.insert(
				new AliHLTHuffmanTreeNode(*nodeCollection.begin(),
						*++nodeCollection.begin()));
		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) {
	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
	47	this->fValue = other.fValue;
	48	this->fWeight = other.fWeight;
	49	return *this;
	50	}
	51
	52	AliHLTHuffmanNode::~AliHLTHuffmanNode() {
	53	}
	54
9409b4b1	55	void AliHLTHuffmanNode::AssignCode(bool bReverse) {
6a1b3945	56	/// assign code to this node loop to right and left nodes
9409b4b1	57	/// the decoding always has to start from the least significant bit since the
	58	/// code length is variable. Thats why the bit corresponding to the parent node
	59	/// has to be right of the bit of child nodes, i.e. bits correspond to the
	60	/// current code length. For storage in a bit stream however, bits are stored
	61	/// in a stream from MSB to LSB and overwrapping to the MSBs of the next byte.
	62	/// Here the reverse code is needed and the word of fixed length read from the
	63	/// stream needs to be reversed before decoding.
	64	/// Note: by changing the AliHLTDataDeflater interface to write from LSB to MSB
	65	/// this can be avoided.
6a1b3945	66	if (GetLeftChild()) {
9409b4b1	67	if (bReverse) {
6a1b3945	68	std::bitset < 64 > v = (this->GetBinaryCode() << 1);
	69	v.set(0);
	70	GetLeftChild()->SetBinaryCode(this->GetBinaryCodeLength() + 1, v);
9409b4b1	71	} else {
	72	std::bitset < 64 > v = (this->GetBinaryCode());
	73	int codelen=this->GetBinaryCodeLength();
	74	v.set(codelen);
	75	GetLeftChild()->SetBinaryCode(codelen + 1, v);
	76	}
	77	GetLeftChild()->AssignCode(bReverse);
6a1b3945	78	}
6a1b3945	79	if (GetRightChild()) {
9409b4b1	80	if (bReverse) {
6a1b3945	81	std::bitset < 64 > v = (this->GetBinaryCode() << 1);
	82	v.reset(0);
	83	GetRightChild()->SetBinaryCode(this->GetBinaryCodeLength() + 1, v);
9409b4b1	84	} else {
	85	std::bitset < 64 > v = (this->GetBinaryCode());
	86	int codelen=this->GetBinaryCodeLength();
	87	v.reset(codelen);
	88	GetRightChild()->SetBinaryCode(codelen + 1, v);
	89	}
	90	GetRightChild()->AssignCode(bReverse);
6a1b3945	91	}
	92	}
	93
	94	void AliHLTHuffmanNode::Print(Option_t* /option/) const {
	95	/// print info
	96	std::cout << "value=" << GetValue() << ", weight=" << GetWeight() << ", length="
	97	<< GetBinaryCodeLength() << ", code=" << GetBinaryCode().to_string()
	98	<< std::endl;
	99	if (GetLeftChild()) {
	100	GetLeftChild()->Print();
	101	}
	102	if (GetRightChild()) {
	103	GetRightChild()->Print();
	104	}
	105	}
	106
	107	ClassImp(AliHLTHuffmanNode)
	108
	109	///////////////////////////////////////////////////////////////////////////////////////////////
	110
	111	AliHLTHuffmanTreeNode::AliHLTHuffmanTreeNode()
	112	: AliHLTHuffmanNode()
	113	, fBinaryCodeLength(0)
	114	, fBinaryCode(0)
	115	, fLeft(NULL)
	116	, fRight(NULL)
	117	{
	118	// nop
	119	}
	120
	121	AliHLTHuffmanTreeNode::AliHLTHuffmanTreeNode(const AliHLTHuffmanTreeNode& other)
	122	: AliHLTHuffmanNode()
	123	, fBinaryCodeLength(other.fBinaryCodeLength)
	124	, fBinaryCode(other.fBinaryCode)
	125	, fLeft(other.GetLeftChild())
	126	, fRight(other.GetRightChild())
	127	{
	128
	129	}
	130
	131	AliHLTHuffmanTreeNode& AliHLTHuffmanTreeNode::operator =(const AliHLTHuffmanTreeNode& other)
	132	{
	133	/// assignment operator
	134	if (&other==this) return *this;
	135	this->fBinaryCodeLength = other.GetBinaryCodeLength();
	136	this->fBinaryCode = other.GetBinaryCode();
	137	this->fLeft = other.GetLeftChild();
	138	this->fRight = other.GetRightChild();
	139	AliHLTHuffmanNode::operator=(other);
	140	return *this;
	141	}
	142
	143	AliHLTHuffmanTreeNode::AliHLTHuffmanTreeNode(AliHLTHuffmanNode* l, AliHLTHuffmanNode* r)
	144	: AliHLTHuffmanNode()
	145	, fBinaryCodeLength(0)
	146	, fBinaryCode(0)
	147	, fLeft(l)
	148	, fRight(r) {
	149	if (l && r) {
	150	SetWeight(l->GetWeight() + r->GetWeight());
	151	} else if (l && !r) {
	152	SetWeight(l->GetWeight());
	153	} else if (!l && r) {
	154	SetWeight(r->GetWeight());
155	}
156	}
157
158	AliHLTHuffmanTreeNode::~AliHLTHuffmanTreeNode()
159	{
160	// nop
161	}
162
163	ClassImp(AliHLTHuffmanTreeNode)
164
165	///////////////////////////////////////////////////////////////////////////////////////////////
166
167	AliHLTHuffmanLeaveNode::AliHLTHuffmanLeaveNode()
168	: AliHLTHuffmanNode()
169	, fBinaryCodeLength(0)
170	, fBinaryCode(0)
171	, fLeft(NULL)
172	, fRight(NULL)
173	{
174	// nop
175	}
176
177	AliHLTHuffmanLeaveNode::AliHLTHuffmanLeaveNode(const AliHLTHuffmanLeaveNode& other)
178	: AliHLTHuffmanNode()
179	, fBinaryCodeLength(other.fBinaryCodeLength)
180	, fBinaryCode(other.fBinaryCode)
181	, fLeft(other.GetLeftChild())
182	, fRight(other.GetRightChild())
183	{
184
185	}
186
187	AliHLTHuffmanLeaveNode& AliHLTHuffmanLeaveNode::operator =(const AliHLTHuffmanLeaveNode& other)
188	{
189	/// assignment operator
190	if (&other==this) return *this;
191	this->fBinaryCodeLength = other.GetBinaryCodeLength();
192	this->fBinaryCode = other.GetBinaryCode();
193	this->fLeft = other.GetLeftChild();
194	this->fRight = other.GetRightChild();
195	AliHLTHuffmanNode::operator=(other);
196	return *this;
197	}
198
199	AliHLTHuffmanLeaveNode::~AliHLTHuffmanLeaveNode()
200	{
201	// nop
202	}
203
204	ClassImp(AliHLTHuffmanLeaveNode)
205
206	///////////////////////////////////////////////////////////////////////////////////////////////
207
208	AliHLTHuffman::AliHLTHuffman()
209	: TNamed()
210	, fMaxBits(0)
211	, fMaxValue(0)
212	, fNodes(0)
213	, fHuffTopNode(NULL)
9409b4b1	214	, fReverseCode(true)
6a1b3945	215	{
	216	/// nop
	217	}
	218
	219	AliHLTHuffman::AliHLTHuffman(const AliHLTHuffman& other)
	220	: TNamed()
	221	, AliHLTLogging()
	222	, fMaxBits(other.fMaxBits)
	223	, fMaxValue(other.fMaxValue)
	224	, fNodes(other.fNodes)
9409b4b1	225	, fHuffTopNode(NULL)
	226	, fReverseCode(other.fReverseCode)
	227	{
6a1b3945	228	/// nop
	229	}
	230
	231	AliHLTHuffman::AliHLTHuffman(const char* name, UInt_t maxBits)
	232	: TNamed(name, name)
	233	, fMaxBits(maxBits)
	234	, fMaxValue((((AliHLTUInt64_t) 1) << maxBits) - 1)
	235	, fNodes((((AliHLTUInt64_t) 1) << maxBits))
	236	, fHuffTopNode(NULL)
9409b4b1	237	, fReverseCode(true)
6a1b3945	238	{
	239	/// standard constructor
	240	for (AliHLTUInt64_t i = 0; i <= fMaxValue; i++) {
	241	fNodes[i].SetValue(i);
	242	}
	243	}
	244
	245	AliHLTHuffman::~AliHLTHuffman() {
	246	/// destructor, nop
	247	}
	248
	249	const std::bitset<64>& AliHLTHuffman::Encode(const AliHLTUInt64_t v, AliHLTUInt64_t& codeLength) const {
	250	/// encode a value
	251	codeLength = 0;
	252	if (v <= fMaxValue) {
	253	// valid symbol/value
	254	if (fHuffTopNode) {
	255	// huffman code has been generated
	256	codeLength = fNodes[v].GetBinaryCodeLength();
	257	return fNodes[v].GetBinaryCode();
	258	} else {
	259	HLTError("encoder '%s' does not seem to be initialized", GetName());
	260	}
	261	} else {
	262	HLTError("encoder %s: value %llu exceeds range of %d bits", GetName(), v, GetMaxBits());
	263	}
	264
	265	static const std::bitset<64> dummy;
	266	return dummy;
	267	}
	268
9409b4b1	269	Bool_t AliHLTHuffman::Decode(std::bitset<64> bits, AliHLTUInt64_t& value,
9409b4b1	270	AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const {
6a1b3945	271	// TODO: check decoding logic, righ now it is just as written
6a1b3945	272	AliHLTHuffmanNode* currNode = fHuffTopNode;
cac77957	273	if (!currNode) return kFALSE;
6a1b3945	274	if (currNode->GetValue() >= 0) {
	275	// handle case with just one node - also quite unlikely
	276	value = currNode->GetValue();
	277	return kTRUE;
	278	}
	279	while (currNode) {
	280	if (bits[0] && currNode->GetLeftChild()) {
	281	// follow left branch
	282	currNode = currNode->GetLeftChild();
	283	bits >>= 1;
	284	if (currNode->GetValue() >= 0) {
	285	value = currNode->GetValue();
9409b4b1	286	length = fMaxBits;
9409b4b1	287	codeLength = currNode->GetBinaryCodeLength();
6a1b3945	288	return kTRUE;
6a1b3945	289	}
9409b4b1	290	continue;
6a1b3945	291	}
	292	if (!bits[0] && currNode->GetRightChild()) {
	293	currNode = currNode->GetRightChild();
	294	bits >>= 1;
	295	if (currNode->GetValue() >= 0) {
	296	value = currNode->GetValue();
9409b4b1	297	length = fMaxBits;
9409b4b1	298	codeLength = currNode->GetBinaryCodeLength();
6a1b3945	299	return kTRUE;
6a1b3945	300	}
9409b4b1	301	continue;
6a1b3945	302	}
9409b4b1	303	break;
6a1b3945	304	}
	305	value = ((AliHLTUInt64_t)1) << 63;
	306	return kFALSE;
	307	}
	308
	309	Bool_t AliHLTHuffman::AddTrainingValue(const AliHLTUInt64_t value,
84a44d88	310	const Float_t weight) {
6a1b3945	311	if (value > fMaxValue) {
	312	/* TODO: ERROR message */
	313	return kFALSE;
	314	}
	315	fNodes[value].AddWeight(weight);
	316	return kTRUE;
	317	}
	318
	319	Bool_t AliHLTHuffman::GenerateHuffmanTree() {
	320	// insert pointer to nodes into ordered structure to build tree
	321	std::multiset<AliHLTHuffmanNode*, AliHLTHuffmanNode::less> nodeCollection;
	322	// std::copy(fNodes.begin(), fNodes.end(),
	323	// std::inserter(freq_coll, freq_coll.begin()));
	324	for (std::vector<AliHLTHuffmanLeaveNode>::iterator i = fNodes.begin(); i
	325	!= fNodes.end(); ++i) {
	326	nodeCollection.insert(&(*i));
	327	}
	328	while (nodeCollection.size() > 1) {
	329	// insert new node into structure, combining the two with lowest probability
	330	nodeCollection.insert(
	331	new AliHLTHuffmanTreeNode(*nodeCollection.begin(),
	332	*++nodeCollection.begin()));
	333	nodeCollection.erase(nodeCollection.begin());
	334	nodeCollection.erase(nodeCollection.begin());
	335	}
	336	//assign value
	337	fHuffTopNode = *nodeCollection.begin();
9409b4b1	338	fHuffTopNode->AssignCode(fReverseCode);
6a1b3945	339	return kTRUE;
	340	}
	341
	342	void AliHLTHuffman::Print(Option_t* option) const {
	343	std::cout << GetName() << endl;
	344	bool bPrintShort=strcmp(option, "short")==0;
	345	if (fHuffTopNode && !bPrintShort) {
	346	std::cout << "Huffman tree:" << endl;
	347	fHuffTopNode->Print();
	348	}
	349	Double_t uncompressedSize = 0;
	350	Double_t compressedSize = 0;
	351	Double_t totalWeight = 0;
	352	if (!bPrintShort)
	353	std::cout << std::endl << "Huffman codes:" << std::endl;
	354	for (AliHLTUInt64_t i = 0; i <= fMaxValue; i++) {
	355	if (!bPrintShort) fNodes[i].Print();
	356	totalWeight += fNodes[i].GetWeight();
	357	uncompressedSize += fNodes[i].GetWeight() * fMaxBits;
	358	compressedSize += fNodes[i].GetWeight()
	359	* fNodes[i].GetBinaryCodeLength();
	360	}
	361	if (uncompressedSize > 0) {
	362	std::cout << "compression ratio: " << compressedSize
	363	/ uncompressedSize << std::endl;
	364	std::cout << "<bits> uncompressed: " << uncompressedSize / totalWeight
	365	<< std::endl;
	366	std::cout << "<bits> compressed: " << compressedSize / totalWeight
	367	<< std::endl;
	368	}
	369	}
	370
	371	AliHLTHuffman& AliHLTHuffman::operator =(const AliHLTHuffman& other) {
	372	fMaxValue = other.fMaxValue;
	373	fNodes = other.fNodes;
	374	fHuffTopNode = NULL;
	375	return *this;
	376	}
	377
9409b4b1	378	bool AliHLTHuffman::CheckConsistency() const
	379	{
	380	if (!fHuffTopNode) {
	381	cout << "huffman table not yet generated" << endl;
	382	}
	383
	384	for (AliHLTUInt64_t v=0; v<GetMaxValue(); v++) {
	385	AliHLTUInt64_t codeLength=0;
	386	std::bitset<64> code=AliHLTHuffman::Encode(v, codeLength);
	387	AliHLTUInt64_t readback=0;
	388	AliHLTUInt32_t readbacklen=0;
	389	AliHLTUInt32_t readbackcodelen=0;
	390	if (fReverseCode) {
	391	// reverse if needed
	392	// Note: for optimized bit stream the huffman code is reversed, and
	393	// that needs to be taken into account
	394	std::bitset<64> rcode;
	395	for (AliHLTUInt64_t i=0; i<codeLength; i++) {rcode<<=1; rcode[0]=code[i];}
	396	code=rcode;
	397	}
	398	if (!Decode(code, readback, readbacklen, readbackcodelen)) {
	399	cout << "Decode failed" << endl;
	400	return false;
	401	}
	402	if (v!=readback) {
	403	cout << "readback of value " << v << " code length " << codeLength << " failed: got " << readback << " code length " << readbackcodelen << endl;
	404	return false;
	405	}
	406	}
	407	return true;
	408	}
	409
6a1b3945	410	ClassImp(AliHLTHuffman)
6a1b3945	411