// Copyright (c) 1998-2009 Nokia Corporation and/or its subsidiary(-ies).
// All rights reserved.
// This component and the accompanying materials are made available
// under the terms of the License "Symbian Foundation License v1.0"
// which accompanies this distribution, and is available
// at the URL "http://www.symbianfoundation.org/legal/sfl-v10.html".
//
// Initial Contributors:
// Nokia Corporation - initial contribution.
//
// Contributors:
//
// Description:
// e32\euser\us_encode.cpp
// 
//

#include <e32huffman.h>
#include <e32base.h>
#include <e32panic.h>

_LIT(KCat,"Huffman");
// local definitions used for Huffman code generation
typedef TUint16 THuff;		/** @internal */
const THuff KLeaf=0x8000;	/** @internal */
struct TNode
/** @internal */
	{
	TUint iCount;
	THuff iLeft;
	THuff iRight;
	};

/** recursive function to calculate the code lengths from the node tree

	@internalComponent
*/
void HuffmanLengthsL(TUint32* aLengths,const TNode* aNodes,TInt aNode,TInt aLen)
	{
	if (++aLen>Huffman::KMaxCodeLength)
		User::Leave(KErrOverflow);

	const TNode& node=aNodes[aNode];
	TUint x=node.iLeft;
	if (x&KLeaf)
		aLengths[x&~KLeaf]=aLen;
	else
		HuffmanLengthsL(aLengths,aNodes,x,aLen);
	x=node.iRight;
	if (x&KLeaf)
		aLengths[x&~KLeaf]=aLen;
	else
		HuffmanLengthsL(aLengths,aNodes,x,aLen);
	}

/**	Insert the {aCount,aValue} pair into the already sorted array of nodes

	@internalComponent
*/
void InsertInOrder(TNode* aNodes, TInt aSize, TUint aCount, TInt aVal)
	{
	// Uses Insertion sort following a binary search...
	TInt l=0, r=aSize;
	while (l < r)
		{
		TInt m = (l+r) >> 1;
		if (aNodes[m].iCount<aCount)
			r=m;
		else
			l=m+1;
		}
	Mem::Copy(aNodes+l+1,aNodes+l,sizeof(TNode)*(aSize-l));
	aNodes[l].iCount=aCount;
	aNodes[l].iRight=TUint16(aVal);
	}

/** Generate a Huffman code

	This generates a Huffman code for a given set of code frequencies. The output
	is a table of code lengths which can be used to build canonincal encoding tables
	or decoding trees for use with the TBitInput and TBitOutput classes.

	Entries in the table with a frequency of zero will have a zero code length
	and thus no associated huffman encoding. If each such symbol should have a
	maximum length encoding, they must be given at least a frequency of 1.

	For an alphabet of n symbols, this algorithm has a transient memory overhead
	of 8n, and a time complexity of O(n*log(n)).

	@param aFrequency The table of code frequencies
	@param aNumCodes The number of codes in the table
	@param aHuffman The table for the output code-length table. This must be
		the same size as the frequency table, and can safely be the same table

	@leave KErrNoMemory If memory used for code generation cannot be allocated

  	@panic "USER ???" If the number of codes exceeds Huffman::KMaxCodes
*/
EXPORT_C void Huffman::HuffmanL(const TUint32 aFrequency[],TInt aNumCodes,TUint32 aHuffman[])
	{
	__ASSERT_ALWAYS(TUint(aNumCodes)<=TUint(KMaxCodes),User::Panic(KCat,EHuffmanTooManyCodes));

	// Sort the values into decreasing order of frequency
	//
	TNode* nodes = new(ELeave) TNode[aNumCodes];
	CleanupArrayDeletePushL(nodes);
	TInt lCount=0;

	for (TInt ii=0;ii<aNumCodes;++ii)
		{
		TInt c=aFrequency[ii];
		if (c!=0)
			InsertInOrder(nodes,lCount++,c,ii|KLeaf);
		}

	// default code length is zero
	Mem::FillZ(aHuffman,aNumCodes*sizeof(TUint32));

	if (lCount==0)
		{
		// no codes with frequency>0. No code has a length
		}
	else if (lCount==1)
		{
		// special case for a single value (always encode as "0")
		aHuffman[nodes[0].iRight&~KLeaf]=1;
		}
	else
		{
		// Huffman algorithm: pair off least frequent nodes and reorder
		//
		do
			{
			--lCount;
			TUint c=nodes[lCount].iCount + nodes[lCount-1].iCount;
			nodes[lCount].iLeft=nodes[lCount-1].iRight;
			// re-order the leaves now to reflect new combined frequency 'c'
			InsertInOrder(nodes,lCount-1,c,lCount);
			} while (lCount>1);
		// generate code lengths in aHuffman[]
		HuffmanLengthsL(aHuffman,nodes,1,0);
		}
	CleanupStack::PopAndDestroy(nodes);

	__ASSERT_DEBUG(IsValid(aHuffman,aNumCodes),User::Panic(KCat,EHuffmanInvalidCoding));
	}

/** Validate a Huffman encoding

	This verifies that a Huffman coding described by the code lengths is valid.
	In particular, it ensures that no code exceeds the maximum length and
	that it is possible to generate a canonical coding for the specified lengths.
	
	@param aHuffman The table of code lengths as generated by Huffman::HuffmanL()
	@param aNumCodes The number of codes in the table

	@return True if the code is valid, otherwise false
*/
EXPORT_C TBool Huffman::IsValid(const TUint32 aHuffman[],TInt aNumCodes)
	{
	// The code is valid if one of the following holds:
	// (a) the code exactly fills the 'code space'
	// (b) there is only a single symbol with code length 1
	// (c) there are no encoded symbols
	//
	TUint remain=1<<KMaxCodeLength;
	TInt totlen=0;
	for (const TUint32* p=aHuffman+aNumCodes; p>aHuffman;)
		{
		TInt len=*--p;
		if (len>0)
			{
			totlen+=len;
			if (len>KMaxCodeLength)
				return EFalse;
			TUint c=1<<(KMaxCodeLength-len);
			if (c>remain)
				return EFalse;
			remain-=c;
			}
		}

	return remain==0 || totlen<=1;
	}

/** Create a canonical Huffman encoding table

	This generates the huffman codes used by TBitOutput::HuffmanL() to write huffman
	encoded data. The input is table of code lengths, as generated by Huffman::HuffmanL()
	and must represent a valid huffman code.
	
	@param aHuffman The table of code lengths as generated by Huffman::HuffmanL()
	@param aNumCodes The number of codes in the table
	@param aEncodeTable The table for the output huffman codes. This must be
		the same size as the code-length table, and can safely be the same table

	@panic "USER ???" If the provided code is not a valid Huffman coding
	
	@see IsValid()
	@see HuffmanL()
*/
EXPORT_C void Huffman::Encoding(const TUint32 aHuffman[],TInt aNumCodes,TUint32 aEncodeTable[])
	{
	__ASSERT_ALWAYS(IsValid(aHuffman,aNumCodes),User::Panic(KCat,EHuffmanInvalidCoding));

	TFixedArray<TInt,KMaxCodeLength> lenCount;
	lenCount.Reset();

	TInt ii;
	for (ii=0;ii<aNumCodes;++ii)
		{
		TInt len=aHuffman[ii]-1;
		if (len>=0)
			++lenCount[len];
		}

	TFixedArray<TUint,KMaxCodeLength> nextCode;
	TUint code=0;
	for (ii=0;ii<KMaxCodeLength;++ii)
		{
		code<<=1;
		nextCode[ii]=code;
		code+=lenCount[ii];
		}

	for (ii=0;ii<aNumCodes;++ii)
		{
		TInt len=aHuffman[ii];
		if (len==0)
			aEncodeTable[ii]=0;
		else
			{
			aEncodeTable[ii] = (nextCode[len-1]<<(KMaxCodeLength-len))|(len<<KMaxCodeLength);
			++nextCode[len-1];
			}
		}
	}

/** the encoding table for the externalised code
	@internalComponent
*/
const TUint32 HuffmanEncoding[]=
	{
	0x10000000,
	0x1c000000,
	0x12000000,
	0x1d000000,
	0x26000000,
	0x26800000,
	0x2f000000,
	0x37400000,
	0x37600000,
	0x37800000,
	0x3fa00000,
	0x3fb00000,
	0x3fc00000,
	0x3fd00000,
	0x47e00000,
	0x47e80000,
	0x47f00000,
	0x4ff80000,
	0x57fc0000,
	0x5ffe0000,
	0x67ff0000,
	0x77ff8000,
	0x7fffa000,
	0x7fffb000,
	0x7fffc000,
	0x7fffd000,
	0x7fffe000,
	0x87fff000,
	0x87fff800
	};

/** encode 0a as '0' and 0b as '1', return number of symbols created

	@internalComponent
*/
void EncodeRunLengthL(TBitOutput& aOutput, TInt aLength)
	{
	if (aLength>0)
		{
		EncodeRunLengthL(aOutput,(aLength-1)>>1);
		aOutput.HuffmanL(HuffmanEncoding[1-(aLength&1)]);
		}
	}

/** Store a canonical huffman encoding in compact form

	As the encoding is canonical, only the code lengths of each code needs to be saved.

	Due to the nature of code length tables, these can usually be stored very compactly
	by encoding the encoding itself, hence the use of the bit output stream.
	
	@param aOutput The output stream for the encoding
	@param aHuffman The table of code lengths as generated by Huffman::HuffmanL()
	@param aNumCodes The number of huffman codes in the table

	@leave TBitOutput::HuffmanL()
*/
EXPORT_C void Huffman::ExternalizeL(TBitOutput& aOutput,const TUint32 aHuffman[],TInt aNumCodes)
	{
	// We assume that the code length table is generated by the huffman generator,
	// in which case the maxmimum code length is 27 bits.
	//
	// We apply three transformations to the data:
	// 1. the data goes through a move-to-front coder
	// 2. apply a rle-0 coder which replace runs of '0' with streams of '0a' and '0b'
	// 3. encode the result using a predefined (average) huffman coding
	//
	// This can be done in a single pass over the data, avoiding the need for additional
	// memory.
	//
	// initialise the list for the MTF coder
	TFixedArray<TUint8,Huffman::KMetaCodes> list;
	TInt i;
	for (i=0;i<list.Count();++i)
		list[i]=TUint8(i);
	TInt last=0;

	TInt rl=0;
	const TUint32* p32=aHuffman;
	const TUint32* e32=p32+aNumCodes;
	while (p32<e32)
		{
		TInt c=*p32++;
		if (c==last)
			++rl;	// repeat of last symbol
		else
			{
			// encode run-length
			EncodeRunLengthL(aOutput,rl);
			rl=0;
			// find code in MTF list
			TInt j;
			for (j=1;list[j]!=c;++j)
				;
			// store this code
			aOutput.HuffmanL(HuffmanEncoding[j+1]);
			// adjust list for MTF algorithm
			while (--j>0)
				list[j+1]=list[j];
			list[1]=TUint8(last);
			last=c;
			}
		}
	// encod any remaining run-length
	EncodeRunLengthL(aOutput,rl);
	}


/** Construct a bit stream output object

	Following construction the bit stream is ready for writing bits, but will first call
	OverflowL() as the output buffer is 'full'. A derived class can detect this state as
	Ptr() will return null.
*/
EXPORT_C TBitOutput::TBitOutput()
	:iCode(0),iBits(-8),iPtr(0),iEnd(0)
	{}

/** Construct a bit stream output object over a buffer

	Data will be written to the buffer until it is full, at which point OverflowL() will
	be called. This should handle the data and then can Set() again to reset the buffer
	for further output.
	
	@param aBuf The buffer for output
	@param aSize The size of the buffer in bytes
*/
EXPORT_C TBitOutput::TBitOutput(TUint8* aBuf,TInt aSize)
	:iCode(0),iBits(-8),iPtr(aBuf),iEnd(aBuf+aSize)
	{}

/** Write a huffman code

	This expects a huffman code value as generated by Huffman::Encoding()

	@param aHuffCode The huffman code write to the stream

	@leave OverflowL() If the output buffer is full, OverflowL() is called
*/
EXPORT_C void TBitOutput::HuffmanL(TUint aHuffCode)
	{
	DoWriteL(aHuffCode<<(32-Huffman::KMaxCodeLength),aHuffCode>>Huffman::KMaxCodeLength);
	}

/** Write an arbitrary integer value

	Write an unsigned integer using the number of bits specified. Only
	the low order bits of the value are written to the output, most
	significant bit first.

	@param aValue The value to write to the stream
	@param aLength The number of bits to output

	@leave OverflowL() If the output buffer is full, OverflowL() is called
*/
EXPORT_C void TBitOutput::WriteL(TUint aValue,TInt aLength)
	{
	if (aLength)
		DoWriteL(aValue<<=32-aLength,aLength);
	}

/** Pad the bitstream to the next byte boundary

	Terminate the bitstream by padding the last byte with the requested value.
	Following this operation the bitstream can continue to be used, the data will
	start at the next byte.

	@param aPadding The bit value to pad the final byte with

	@leave OverflowL() If the output buffer is full, OverflowL() is called
*/
EXPORT_C void TBitOutput::PadL(TUint aPadding)
	{
	if (iBits>-8)
		WriteL(aPadding?0xffffffffu:0,-iBits);
	}

/** Write the higher order bits to the stream
	
	@internalComponent
*/
void TBitOutput::DoWriteL(TUint aBits,TInt aSize)
	{
	if (aSize>25)
		{
		// cannot process >25 bits in a single pass
		// so do the top 8 bits first
		ASSERT(aSize<=32);
		DoWriteL(aBits&0xff000000u,8);
		aBits<<=8;
		aSize-=8;
		}

	TInt bits=iBits;
	TUint code=iCode|(aBits>>(bits+8));
	bits+=aSize;
	if (bits>=0)
		{
		TUint8* p=iPtr;
		do
			{
			if (p==iEnd)
				{
				// run out of buffer space so invoke the overflow handler
				iPtr=p;
				OverflowL();
				p=iPtr;
				ASSERT(p!=iEnd);
				}
			*p++=TUint8(code>>24);
			code<<=8;
			bits-=8;
			} while (bits>=0);
		iPtr=p;
		}
	iCode=code;
	iBits=bits;
	}

/** Handle a full output buffer

	This virtual function is called when the output buffer is full. It should deal
	with the data in the buffer before reseting the buffer using Set(), allowing
	further data to be written.

	A derived class can replace this to write the data to a file (for example)
	before marking the buffer as empty.

	@leave KErrOverflow The default implementation leaves
*/
void TBitOutput::OverflowL()
	{
	User::Leave(KErrOverflow);
	}