[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(other)
	, 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(other)
	, 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)
	, fMaxCodeLength(0)
	, fDecodingNodes()
	, fDecodingTopNode(NULL)
{
        /// nop
}

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)
{
        /// 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)
	, fMaxCodeLength(0)
	, fDecodingNodes()
	, fDecodingTopNode(NULL)
 {
        /// 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::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) {
		// 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 && 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
{
	// 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) {
		/* 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);
	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()
{
  // 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)
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)
6e848d29	123	: AliHLTHuffmanNode(other)
6a1b3945	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)
6e848d29	179	: AliHLTHuffmanNode(other)
6a1b3945	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)
6e848d29	216	, fMaxCodeLength(0)
7227b364	217	, fDecodingNodes()
7227b364	218	, fDecodingTopNode(NULL)
6a1b3945	219	{
	220	/// nop
	221	}
	222
	223	AliHLTHuffman::AliHLTHuffman(const AliHLTHuffman& other)
	224	: TNamed()
	225	, AliHLTLogging()
	226	, fMaxBits(other.fMaxBits)
	227	, fMaxValue(other.fMaxValue)
	228	, fNodes(other.fNodes)
9409b4b1	229	, fHuffTopNode(NULL)
9409b4b1	230	, fReverseCode(other.fReverseCode)
6e848d29	231	, fMaxCodeLength(other.fMaxCodeLength)
7227b364	232	, fDecodingNodes()
7227b364	233	, fDecodingTopNode(NULL)
9409b4b1	234	{
6a1b3945	235	/// nop
	236	}
	237
	238	AliHLTHuffman::AliHLTHuffman(const char* name, UInt_t maxBits)
	239	: TNamed(name, name)
	240	, fMaxBits(maxBits)
	241	, fMaxValue((((AliHLTUInt64_t) 1) << maxBits) - 1)
	242	, fNodes((((AliHLTUInt64_t) 1) << maxBits))
	243	, fHuffTopNode(NULL)
9409b4b1	244	, fReverseCode(true)
6e848d29	245	, fMaxCodeLength(0)
7227b364	246	, fDecodingNodes()
7227b364	247	, fDecodingTopNode(NULL)
6a1b3945	248	{
	249	/// standard constructor
	250	for (AliHLTUInt64_t i = 0; i <= fMaxValue; i++) {
	251	fNodes[i].SetValue(i);
	252	}
	253	}
	254
	255	AliHLTHuffman::~AliHLTHuffman() {
	256	/// destructor, nop
	257	}
	258
	259	const std::bitset<64>& AliHLTHuffman::Encode(const AliHLTUInt64_t v, AliHLTUInt64_t& codeLength) const {
	260	/// encode a value
	261	codeLength = 0;
	262	if (v <= fMaxValue) {
	263	// valid symbol/value
	264	if (fHuffTopNode) {
	265	// huffman code has been generated
	266	codeLength = fNodes[v].GetBinaryCodeLength();
	267	return fNodes[v].GetBinaryCode();
	268	} else {
	269	HLTError("encoder '%s' does not seem to be initialized", GetName());
	270	}
	271	} else {
	272	HLTError("encoder %s: value %llu exceeds range of %d bits", GetName(), v, GetMaxBits());
	273	}
	274
	275	static const std::bitset<64> dummy;
	276	return dummy;
	277	}
	278
7227b364	279	Bool_t AliHLTHuffman::DecodeLSB(std::bitset<64> bits, AliHLTUInt64_t& value,
	280	AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const
	281	{
6e848d29	282	// huffman decoding
6a1b3945	283	AliHLTHuffmanNode* currNode = fHuffTopNode;
cac77957	284	if (!currNode) return kFALSE;
6a1b3945	285	if (currNode->GetValue() >= 0) {
	286	// handle case with just one node - also quite unlikely
	287	value = currNode->GetValue();
	288	return kTRUE;
	289	}
	290	while (currNode) {
	291	if (bits[0] && currNode->GetLeftChild()) {
	292	// follow left branch
	293	currNode = currNode->GetLeftChild();
	294	bits >>= 1;
b971c96b	295	if (currNode && currNode->GetValue() >= 0) {
6a1b3945	296	value = currNode->GetValue();
9409b4b1	297	length = fMaxBits;
9409b4b1	298	codeLength = currNode->GetBinaryCodeLength();
6a1b3945	299	return kTRUE;
6a1b3945	300	}
9409b4b1	301	continue;
6a1b3945	302	}
	303	if (!bits[0] && currNode->GetRightChild()) {
	304	currNode = currNode->GetRightChild();
	305	bits >>= 1;
b971c96b	306	if (currNode && currNode->GetValue() >= 0) {
6a1b3945	307	value = currNode->GetValue();
9409b4b1	308	length = fMaxBits;
9409b4b1	309	codeLength = currNode->GetBinaryCodeLength();
6a1b3945	310	return kTRUE;
6a1b3945	311	}
9409b4b1	312	continue;
6a1b3945	313	}
9409b4b1	314	break;
6a1b3945	315	}
	316	value = ((AliHLTUInt64_t)1) << 63;
	317	return kFALSE;
	318	}
	319
7227b364	320	Bool_t AliHLTHuffman::DecodeMSB(std::bitset<64> bits, AliHLTUInt64_t& value,
	321	AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const
	322	{
6e848d29	323	// huffman decoding
	324	AliHLTHuffmanNode* currNode = fHuffTopNode;
	325	if (!currNode) return kFALSE;
	326	if (currNode->GetValue() >= 0) {
	327	// handle case with just one node - also quite unlikely
	328	value = currNode->GetValue();
	329	return kTRUE;
	330	}
	331	while (currNode) {
	332	if (bits[63] && currNode->GetLeftChild()) {
	333	// follow left branch
	334	currNode = currNode->GetLeftChild();
	335	bits <<= 1;
b971c96b	336	if (currNode && currNode->GetValue() >= 0) {
6e848d29	337	value = currNode->GetValue();
	338	length = fMaxBits;
	339	codeLength = currNode->GetBinaryCodeLength();
	340	return kTRUE;
	341	}
	342	continue;
	343	}
	344	if (!bits[63] && currNode->GetRightChild()) {
	345	currNode = currNode->GetRightChild();
	346	bits <<= 1;
b971c96b	347	if (currNode && currNode->GetValue() >= 0) {
6e848d29	348	value = currNode->GetValue();
	349	length = fMaxBits;
	350	codeLength = currNode->GetBinaryCodeLength();
	351	return kTRUE;
	352	}
	353	continue;
	354	}
	355	break;
	356	}
	357	value = ((AliHLTUInt64_t)1) << 63;
	358	return kFALSE;
	359	}
	360
7227b364	361	Bool_t AliHLTHuffman::FastDecodeMSB(std::bitset<64> bits, AliHLTUInt64_t& value,
	362	AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const
	363	{
	364	// huffman decoding using the binary node map
	365	HLTFatal("this function needs to be tested and commisioned");
	366	AliHuffmanDecodingNode* currNode = fDecodingTopNode;
	367	if (!currNode) return kFALSE;
	368	if (currNode->fValue >= 0) {
	369	// handle case with just one node - also quite unlikely
	370	value = currNode->fValue;
	371	return kTRUE;
	372	}
	373	while (currNode) {
	374	if (bits[63] && currNode->fLeft) {
	375	// follow left branch
	376	currNode = currNode->fLeft;
	377	bits <<= 1;
b971c96b	378	if (currNode && currNode->fValue >= 0) {
7227b364	379	value = currNode->fValue;
	380	length = fMaxBits;
	381	codeLength = currNode->fBinaryCodeLength;
	382	return kTRUE;
	383	}
	384	continue;
	385	}
	386	if (!bits[63] && currNode->fRight) {
	387	currNode = currNode->fRight;
	388	bits <<= 1;
b971c96b	389	if (currNode && currNode->fValue >= 0) {
7227b364	390	value = currNode->fValue;
	391	length = fMaxBits;
	392	codeLength = currNode->fBinaryCodeLength;
	393	return kTRUE;
	394	}
	395	continue;
	396	}
	397	break;
	398	}
	399	value = ((AliHLTUInt64_t)1) << 63;
	400	return kFALSE;
	401	}
	402
6a1b3945	403	Bool_t AliHLTHuffman::AddTrainingValue(const AliHLTUInt64_t value,
84a44d88	404	const Float_t weight) {
6a1b3945	405	if (value > fMaxValue) {
	406	/* TODO: ERROR message */
	407	return kFALSE;
	408	}
	409	fNodes[value].AddWeight(weight);
	410	return kTRUE;
	411	}
	412
	413	Bool_t AliHLTHuffman::GenerateHuffmanTree() {
	414	// insert pointer to nodes into ordered structure to build tree
	415	std::multiset<AliHLTHuffmanNode*, AliHLTHuffmanNode::less> nodeCollection;
	416	// std::copy(fNodes.begin(), fNodes.end(),
	417	// std::inserter(freq_coll, freq_coll.begin()));
	418	for (std::vector<AliHLTHuffmanLeaveNode>::iterator i = fNodes.begin(); i
	419	!= fNodes.end(); ++i) {
	420	nodeCollection.insert(&(*i));
	421	}
	422	while (nodeCollection.size() > 1) {
	423	// insert new node into structure, combining the two with lowest probability
5890ed9f	424	AliHLTHuffmanNode* node=new AliHLTHuffmanTreeNode(nodeCollection.begin(), ++nodeCollection.begin());
	425	if (!node) return kFALSE;
	426	nodeCollection.insert(node);
6a1b3945	427	nodeCollection.erase(nodeCollection.begin());
	428	nodeCollection.erase(nodeCollection.begin());
	429	}
	430	//assign value
	431	fHuffTopNode = *nodeCollection.begin();
9409b4b1	432	fHuffTopNode->AssignCode(fReverseCode);
6e848d29	433	InitMaxCodeLength();
6a1b3945	434	return kTRUE;
	435	}
	436
	437	void AliHLTHuffman::Print(Option_t* option) const {
	438	std::cout << GetName() << endl;
6e848d29	439	bool bPrintShort=strcmp(option, "full")!=0;
6a1b3945	440	if (fHuffTopNode && !bPrintShort) {
	441	std::cout << "Huffman tree:" << endl;
	442	fHuffTopNode->Print();
	443	}
	444	Double_t uncompressedSize = 0;
	445	Double_t compressedSize = 0;
	446	Double_t totalWeight = 0;
	447	if (!bPrintShort)
	448	std::cout << std::endl << "Huffman codes:" << std::endl;
	449	for (AliHLTUInt64_t i = 0; i <= fMaxValue; i++) {
	450	if (!bPrintShort) fNodes[i].Print();
	451	totalWeight += fNodes[i].GetWeight();
	452	uncompressedSize += fNodes[i].GetWeight() * fMaxBits;
	453	compressedSize += fNodes[i].GetWeight()
	454	* fNodes[i].GetBinaryCodeLength();
	455	}
	456	if (uncompressedSize > 0) {
	457	std::cout << "compression ratio: " << compressedSize
	458	/ uncompressedSize << std::endl;
	459	std::cout << "<bits> uncompressed: " << uncompressedSize / totalWeight
	460	<< std::endl;
	461	std::cout << "<bits> compressed: " << compressedSize / totalWeight
	462	<< std::endl;
	463	}
	464	}
	465
	466	AliHLTHuffman& AliHLTHuffman::operator =(const AliHLTHuffman& other) {
5c8ae5fb	467	if (this==&other) return *this;
6a1b3945	468	fMaxValue = other.fMaxValue;
	469	fNodes = other.fNodes;
	470	fHuffTopNode = NULL;
6e848d29	471	fMaxCodeLength = 0;
6a1b3945	472	return *this;
	473	}
	474
9409b4b1	475	bool AliHLTHuffman::CheckConsistency() const
	476	{
	477	if (!fHuffTopNode) {
	478	cout << "huffman table not yet generated" << endl;
	479	}
	480
	481	for (AliHLTUInt64_t v=0; v<GetMaxValue(); v++) {
	482	AliHLTUInt64_t codeLength=0;
	483	std::bitset<64> code=AliHLTHuffman::Encode(v, codeLength);
	484	AliHLTUInt64_t readback=0;
	485	AliHLTUInt32_t readbacklen=0;
	486	AliHLTUInt32_t readbackcodelen=0;
	487	if (fReverseCode) {
6e848d29	488	code<<=64-codeLength;
7227b364	489	if (!DecodeMSB(code, readback, readbacklen, readbackcodelen)) {
6e848d29	490	cout << "Decode failed" << endl;
	491	return false;
	492	}
	493	} else {
7227b364	494	if (!DecodeLSB(code, readback, readbacklen, readbackcodelen)) {
9409b4b1	495	cout << "Decode failed" << endl;
	496	return false;
	497	}
6e848d29	498	}
9409b4b1	499	if (v!=readback) {
	500	cout << "readback of value " << v << " code length " << codeLength << " failed: got " << readback << " code length " << readbackcodelen << endl;
	501	return false;
	502	}
	503	}
	504	return true;
	505	}
	506
6e848d29	507	UInt_t AliHLTHuffman::InitMaxCodeLength()
	508	{
	509	// loop over leave nodes and set maximum code length
	510	fMaxCodeLength=0;
	511	for (std::vector<AliHLTHuffmanLeaveNode>::const_iterator node=fNodes.begin();
	512	node!=fNodes.end(); node++) {
	513	if (fMaxCodeLength<node->GetBinaryCodeLength())
	514	fMaxCodeLength=node->GetBinaryCodeLength();
	515	}
	516	return fMaxCodeLength;
	517	}
	518
7227b364	519	int AliHLTHuffman::EnableDecodingMap()
	520	{
	521	// build decoder nodes from node tree
	522	fDecodingTopNode=NULL;
	523	fDecodingNodes.clear();
	524	if (fNodes.size()==0) {
	525	return 0;
	526	}
	527	fDecodingNodes.reserve(2*fNodes.size());
	528	fDecodingTopNode=BuildDecodingNode(fHuffTopNode, fDecodingNodes);
	529	if (!fDecodingTopNode) {
	530	fDecodingNodes.clear();
	531	} else {
	532	HLTError("decoder nodes created sucessfully");
	533	}
	534	return 0;
	535	}
	536
	537	AliHLTHuffman::AliHuffmanDecodingNode* AliHLTHuffman::BuildDecodingNode(AliHLTHuffmanNode* node, vector<AliHuffmanDecodingNode>& decodernodes) const
	538	{
	539	// build and add decoder node structure corresponding to huffman node
	540	if (!node) {
	541	HLTError("invalid node pointer");
	542	return NULL;
	543	}
	544	for (vector<AliHuffmanDecodingNode>::iterator i=decodernodes.begin();
	545	i!=decodernodes.end(); i++) {
	546	if (i->fParent==node) {
	547	HLTError("node %p already existing in decoder nodes", node);
	548	return NULL;
	549	}
	550	}
	551
	552	AliHuffmanDecodingNode* decodernode=NULL;
	553	if (decodernodes.size()+1>decodernodes.capacity()) {
	554	HLTError("initial size of array too small, can not add more nodes because pointers will become invalid when growing vector");
	555	} else {
	556	AliHuffmanDecodingNode dn;
	557	dn.fParent=node;
	558	dn.fValue=node->GetValue();
	559	dn.fLeft=NULL;
	560	dn.fRight=NULL;
	561	dn.fBinaryCodeLength=0;
	562	decodernodes.push_back(dn);
	563	decodernode=&(decodernodes.back());
	564	}
	565
	566	if (decodernode && decodernode->fValue<0) {
	567	decodernode->fRight=BuildDecodingNode(node->GetRightChild(), decodernodes);
	568	decodernode->fLeft=BuildDecodingNode(node->GetLeftChild(), decodernodes);
	569	if (decodernode->fLeft==NULL \|\| decodernode->fRight==0) {
	570	HLTError("failed to build corresponding decoder node for node %p", node);
	571	decodernode=NULL;
	572	}
	573	}
	574
	575	return decodernode;
	576	}
	577
6a1b3945	578	ClassImp(AliHLTHuffman)
6a1b3945	579