// Copyright (c) 2004-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:
// e32test/buffer/t_huff.cpp
// Overview:
// Test methods of the Huffman, TBitInput and TBitOutput classes.
// API Information:
// Huffman, TBitInput, TBitOutput
// Details:
// - Test and verify the results of TBitInput bit reading:
// - test and verify single bit reads, multiple bit reads and 32-bit reads
// - test and verify single bit reads and multiple bit reads from a 
// fractured input.
// - test and verify overrun reads
// - Test and verify the results of TBitOutput bit writing:
// - test and verify bitstream padding
// - test and verify single bit and multiple bit writes
// - test and verify overflow writes
// - Test and verify the results of a Huffman decoder using Huffman class 
// static methods, TBitOutput and TBitInput objects.
// - Test and verify the results of a Huffman generator for known distributions:
// flat, power-of-2 and Fibonacci.
// - Test and verify the results of a Huffman generator for random distributions:
// - generate random frequency distributions and verify:
// (a) the Huffman generator creates a mathematically 'optimal code'
// (b) the canonical encoding is canonical
// (c) the decoding tree correctly decodes each code
// (d) the encoding can be correctly externalised and internalised
// Platforms/Drives/Compatibility:
// All 
// Assumptions/Requirement/Pre-requisites:
// Failures and causes:
// Base Port information:
// 
//

#include <e32test.h>
#include <e32math.h>
#include <e32huffman.h>

RTest test(_L("T_HUFF"));

const Uint64 KTestData=UI64LIT(0x6f1b09a7e8c523d4);
const TUint8 KTestBuffer[] = {0x6f,0x1b,0x09,0xa7,0xe8,0xc5,0x23,0xd4};
const TInt KTestBytes=sizeof(KTestBuffer);
const TInt KTestBits=KTestBytes*8;

// Input stream: bit and multi-bit read tests with exhsautive buffer reload testing

typedef TBool (*TestFn)(TBitInput& aIn, Uint64 aBits, TInt aCount);

class TAlignedBitInput : public TBitInput
	{
public:
	TAlignedBitInput(const TUint8*,TInt,TInt);
private:
	void UnderflowL();
private:
	const TUint8* iRemainder;
	TInt iCount;
	};

TAlignedBitInput::TAlignedBitInput(const TUint8* aPtr,TInt aCount,TInt aOffset)
	:TBitInput(aPtr,32-aOffset,aOffset), iRemainder(aPtr+4), iCount(aOffset+aCount-32)
	{}

void TAlignedBitInput::UnderflowL()
	{
	if (!iRemainder)
		User::Leave(KErrUnderflow);
	else
		{
		Set(iRemainder,iCount);
		iRemainder=0;
		}
	}

class TSplitBitInput : public TBitInput
	{
public:
	TSplitBitInput(const TUint8*,TInt,TInt,TInt);
private:
	void UnderflowL();
private:
	const TUint8* iBase;
	TInt iBlockSize;
	TInt iOffset;
	TInt iAvail;
	};

TSplitBitInput::TSplitBitInput(const TUint8* aPtr,TInt aLength,TInt aOffset,TInt aSize)
	:TBitInput(aPtr,aSize,aOffset), iBase(aPtr), iBlockSize(aSize), iOffset(aOffset+aSize), iAvail(aLength-aSize)
	{}

void TSplitBitInput::UnderflowL()
	{
	TInt len=Min(iBlockSize,iAvail);
	if (len==0)
		User::Leave(KErrUnderflow);
	Set(iBase,len,iOffset);
	iOffset+=len;
	iAvail-=len;
	}

class TAlternateBitInput : public TBitInput
	{
public:
	TAlternateBitInput(const TUint8*,TInt,TInt);
private:
	void UnderflowL();
private:
	const TUint8* iBase;
	TInt iOffset;
	TInt iAvail;
	};

TAlternateBitInput::TAlternateBitInput(const TUint8* aPtr,TInt aLength,TInt aOffset)
	:TBitInput(aPtr,1,aOffset), iBase(aPtr), iOffset(aOffset+2), iAvail(aLength-2)
	{}

void TAlternateBitInput::UnderflowL()
	{
	if (iAvail<=0)
		User::Leave(KErrUnderflow);
	Set(iBase,1,iOffset);
	iOffset+=2;
	iAvail-=2;
	}

void TestReader(TBitInput& aIn, TestFn aFunc, Uint64 aBits, TInt aCount)
	{
	TBool eof=EFalse;
	TRAPD(r,eof=aFunc(aIn,aBits,aCount));
	test (r==KErrNone);
	if (eof)
		{
		TRAP(r,aIn.ReadL());
		test (r==KErrUnderflow);
		}
	}

void TestBits(TInt aOffset, TInt aCount, TestFn aFunc)
	{
	Uint64 bits=KTestData;
	if (aOffset)
		bits<<=aOffset;
	if (aCount<64)
		bits&=~((Uint64(1)<<(64-aCount))-1);
	// test with direct input
	TBitInput in1(KTestBuffer,aCount,aOffset);
	TestReader(in1,aFunc,bits,aCount);
	// test with aligned input
	if (aOffset<32 && aOffset+aCount>32)
		{
		TAlignedBitInput in2(KTestBuffer,aCount,aOffset);
		TestReader(in2,aFunc,bits,aCount);
		}
	// test with blocked input
	for (TInt block=aCount;--block>0;)
		{
		TSplitBitInput in3(KTestBuffer,aCount,aOffset,block);
		TestReader(in3,aFunc,bits,aCount);
		}
	}

void TestAlternateBits(TInt aOffset, TInt aCount, TestFn aFunc)
	{
	Uint64 bits=0;
	TInt c=0;
	for (TInt ix=aOffset;ix<aOffset+aCount;ix+=2)
		{
		if (KTestData<<ix>>63)
			bits|=Uint64(1)<<(63-c);
		++c;
		}
	// test with alternate input
	TAlternateBitInput in1(KTestBuffer,aCount,aOffset);
	TestReader(in1,aFunc,bits,c);
	}

void PermBits(TestFn aFunc, TInt aMinCount=1, TInt aMaxCount=64)
	{
	for (TInt offset=0;offset<KTestBits;++offset)
		for (TInt count=Min(KTestBits-offset,aMaxCount);count>=aMinCount;--count)
			TestBits(offset,count,aFunc);
	}

void AlternateBits(TestFn aFunc, TInt aMinCount=1)
	{
	for (TInt offset=0;offset<KTestBits;++offset)
		for (TInt count=KTestBits-offset;count>=aMinCount;--count)
			TestAlternateBits(offset,count,aFunc);
	}

TBool SingleBitRead(TBitInput& aIn, Uint64 aBits, TInt aCount)
	{
	while (--aCount>=0)
		{
		test (aIn.ReadL() == (aBits>>63));
		aBits<<=1;
		}
	return ETrue;
	}

TBool MultiBitRead(TBitInput& aIn, Uint64 aBits, TInt aCount)
	{
	TInt c=aCount/2;
	TUint v=aIn.ReadL(c);
	if (c==0)
		test (v==0);
	else
		{
		test (v==TUint(aBits>>(64-c)));
		aBits<<=c;
		}
	c=aCount-c;
	v=aIn.ReadL(c);
	if (c==0)
		test (v==0);
	else
		test (v==TUint(aBits>>(64-c)));
	return ETrue;
	}

TBool LongShortRead(TBitInput& aIn, Uint64 aBits, TInt aCount)
	{
	TUint v=aIn.ReadL(32);
	test (v==TUint(aBits>>32));
	aBits<<=32;
	TInt c=aCount-32;
	v=aIn.ReadL(c);
	if (c==0)
		test (v==0);
	else
		test (v==TUint(aBits>>(64-c)));
	return ETrue;
	}

TBool ShortLongRead(TBitInput& aIn, Uint64 aBits, TInt aCount)
	{
	TInt c=aCount-32;
	TUint v=aIn.ReadL(c);
	if (c==0)
		test (v==0);
	else
		{
		test (v==TUint(aBits>>(64-c)));
		aBits<<=c;
		}
	v=aIn.ReadL(32);
	test (v==TUint(aBits>>32));
	return ETrue;
	}

TBool EofRead(TBitInput& aIn, Uint64, TInt aCount)
	{
	TRAPD(r,aIn.ReadL(aCount+1));
	test(r==KErrUnderflow);
	return EFalse;
	}

void TestBitReading()
	{
	test.Start(_L("Test single bit reads"));
	PermBits(&SingleBitRead);
	test.Next(_L("Test multi bit reads"));
	PermBits(&MultiBitRead);
	test.Next(_L("Test 32-bit reads"));
	PermBits(&LongShortRead,32);
	PermBits(&ShortLongRead,32);
	test.Next(_L("Test single bit reads (fractured input)"));
	AlternateBits(&SingleBitRead);
	test.Next(_L("Test multi bit reads (fractured input)"));
	AlternateBits(&MultiBitRead);
	test.Next(_L("Test overrun reads"));
	PermBits(&EofRead,1,31);
	test.End();
	}

// Bit output testing (assumes bit input is correct)

void TestPadding()
	{
	TUint8 buffer[4];
	TBitOutput out(buffer,4);
	test(out.Ptr()==buffer);
	test(out.BufferedBits()==0);
	out.PadL(0);
	test(out.Ptr()==buffer);
	test(out.BufferedBits()==0);
	out.WriteL(0,0);
	out.PadL(0);
	test(out.Ptr()==buffer);
	test(out.BufferedBits()==0);

	TInt i;
	for (i=1;i<=8;++i)
		{
		out.Set(buffer,4);
		out.WriteL(0,i);
		test(out.BufferedBits()==(i%8));
		out.PadL(1);
		test(out.BufferedBits()==0);
		out.WriteL(0,i);
		test(out.BufferedBits()==(i%8));
		out.PadL(1);
		test(out.BufferedBits()==0);
		test (out.Ptr()==buffer+2);
		test (buffer[0]==(0xff>>i));
		test (buffer[1]==(0xff>>i));
		}

	for (i=1;i<=8;++i)
		{
		out.Set(buffer,4);
		out.WriteL(0xff,i);
		out.PadL(0);
		test (out.Ptr()==buffer+1);
		test (buffer[0]==(0xff^(0xff>>i)));
		}
	}

void TestBitWrites()
	{
	TUint8 buffer[KTestBytes];
	TBitOutput out(buffer,KTestBytes);
	TBitInput in(KTestBuffer,KTestBits);
	TInt i;
	for (i=KTestBits;--i>=0;)
		out.WriteL(in.ReadL(),1);
	test (Mem::Compare(buffer,KTestBytes,KTestBuffer,KTestBytes)==0);	

	Mem::FillZ(buffer,KTestBytes);
	out.Set(buffer,KTestBytes);
	Uint64 bits=KTestData;
	for (i=KTestBits;--i>=0;)
		out.WriteL(TUint(bits>>i),1);
	test (Mem::Compare(buffer,KTestBytes,KTestBuffer,KTestBytes)==0);
	}

void TestMultiBitWrites()
	{
	TInt i=0;
	for (TInt j=0;j<32;++j)
		for (TInt k=0;k<32;++k)
			{
			++i;
			if (i+j+k>KTestBits)
				i=0;
			TUint8 buffer[KTestBytes];
			TBitInput in(KTestBuffer,KTestBits);
			TBitOutput out(buffer,KTestBytes);
			in.ReadL(i);
			out.WriteL(in.ReadL(j),j);
			out.WriteL(in.ReadL(k),k);
			out.PadL(0);
			const TUint8* p=out.Ptr();
			test (p-buffer == (j+k+7)/8);
			Uint64 v=0;
			while (p>buffer)
				v=(v>>8) | Uint64(*--p)<<56;
			Uint64 res=KTestData;
			if (i+j+k<KTestBits)
				res>>=KTestBits-i-j-k;
			if (j+k<KTestBits)
				res<<=KTestBits-j-k;
			test (v==res);
			}
	}

void TestAlternatingWrites()
	{
	const TInt KBufferSize=(1+32)*32;
	TUint8 buffer[(7+KBufferSize)/8];
	TBitOutput out(buffer,sizeof(buffer));
	TInt i;
	for (i=0;i<=32;++i)
		out.WriteL(i&1?0xffffffff:0,i);
	while (--i>=0)
		out.WriteL(i&1?0:0xffffffff,i);
	out.PadL(0);
	TBitInput in(buffer,KBufferSize);
	for (i=0;i<=32;++i)
		{
		TUint v=in.ReadL(i);
		if (i&1)
			test (v == (1u<<i)-1u);
		else
			test (v == 0);
		}
	while (--i>=0)
		{
		TUint v=in.ReadL(i);
		if (i&1)
			test (v == 0);
		else if (i==32)
			test (v == 0xffffffffu);
		else
			test (v == (1u<<i)-1u);
		}
	}

class TOverflowOutput : public TBitOutput
	{
public:
	TOverflowOutput();
private:
	void OverflowL();
private:
	TUint8 iBuf[1];
	TInt iIx;
	};

TOverflowOutput::TOverflowOutput()
	:iIx(0)
	{}

void TOverflowOutput::OverflowL()
	{
	if (Ptr()!=0)
		{
		test (Ptr()-iBuf == 1);
		test (iBuf[0] == KTestBuffer[iIx]);
		if (++iIx==KTestBytes)
			User::Leave(KErrOverflow);
		}
	Set(iBuf,1);
	}

void OverflowTestL(TBitOutput& out, TInt j)
	{
	for (;;) out.WriteL(0xffffffffu,j);
	}

void TestOverflow()
	{
	test.Start(_L("Test default constructed output"));
	TBitOutput out;
	TInt i;
	for (i=1;i<=8;++i)
		{
		TRAPD(r,out.WriteL(1,1));
		if (i<8)
			{
			test (out.BufferedBits() == i);
			test (r == KErrNone);
			}
		else
			test (r == KErrOverflow);
		}

	test.Next(_L("Test overflow does not overrun the buffer"));
	i=0;
	for (TInt j=1;j<=32;++j)
		{
		if (++i>KTestBytes)
			i=1;
		TUint8 buffer[KTestBytes+1];
		Mem::FillZ(buffer,sizeof(buffer));
		out.Set(buffer,i);
		TRAPD(r,OverflowTestL(out,j));
		test (r == KErrOverflow);
		TInt k=0;
		while (buffer[k]==0xff)
			{
			++k;
			test (k<TInt(sizeof(buffer)));
			}
		test (k <= i);
		test ((i-k)*8 < j);
		while (k<TInt(sizeof(buffer)))
			{
			test (buffer[k]==0);
			++k;
			}
		}

	test.Next(_L("Test overflow handler"));
	TOverflowOutput vout;
	TBitInput in(KTestBuffer,KTestBits);
	for (i=KTestBits;--i>=0;)
		vout.WriteL(in.ReadL(),1);
	test(vout.BufferedBits() == 0);
	TRAPD(r,vout.WriteL(0,1));
	test (r == KErrNone);
	TRAP(r,vout.PadL(0));
	test (r == KErrOverflow);
	test.End();
	}

void TestBitWriting()
	{
	test.Start(_L("Test padding"));
	TestPadding();
	test.Next(_L("Test bit writes"));
	TestBitWrites();
	test.Next(_L("Test multi-bit writes"));
	TestMultiBitWrites();
	TestAlternatingWrites();
	test.Next(_L("Test overflow writes"));
	TestOverflow();
	test.End();
	}

// Huffman decode testing
#ifdef __ARMCC__
#pragma Onoinline
#endif
void Dummy(volatile TInt & /*x*/)
        {
	}

void TestHuffmanL()
	{
	const TInt KTestBits=32*32;

	// build the huffman decoding tree for
	// 0: '0'
	// 1: '10'
	// 2: '110' etc
	TUint32 huffman[Huffman::KMaxCodeLength+1];
	TInt i;
	for (i=0;i<Huffman::KMaxCodeLength;++i)
		huffman[i]=i+1;
	huffman[Huffman::KMaxCodeLength]=Huffman::KMaxCodeLength;
	Huffman::Decoding(huffman,Huffman::KMaxCodeLength+1,huffman);

	TUint8 buffer[KTestBits/8];
	for (TInt sz=0;sz<Huffman::KMaxCodeLength;++sz)
		{
		const TInt rep=KTestBits/(sz+1);
		TBitOutput out(buffer,sizeof(buffer));
		for (i=0;i<rep;++i)
			{
			out.WriteL(0xffffffff,sz);
			out.WriteL(0,1);
			}
		out.PadL(1);
		for (TInt blk=1;blk<=64;++blk)
			{
			TSplitBitInput in(buffer,rep*(sz+1)-1,0,blk);
			for (i=0;i<rep-1;++i)
				{
				TInt v=-1;
				TRAPD(r,v=in.HuffmanL(huffman));
				test (r==KErrNone);
				test (sz==v);
				}
			volatile TInt v=-1;
		        Dummy(v);
			TRAPD(r, v=in.HuffmanL(huffman));
			test (v==-1);
			test (r==KErrUnderflow);
			}
		}
	}

// Huffman generator testing with known but atypical distributions

void FlatHuffman(TInt aMaxCount)
	{
	TUint32* tab=new TUint32[aMaxCount];
	test (tab!=NULL);

	// test empty distribution
	Mem::FillZ(tab,sizeof(TUint32)*aMaxCount);
	TRAPD(r, Huffman::HuffmanL(tab,aMaxCount,tab));
	test (r==KErrNone);
	TInt i;
	for (i=0;i<aMaxCount;++i)
		test (tab[i]==0);
	Huffman::Decoding(tab,aMaxCount,tab);

	// test single-symbol distribution
	Mem::FillZ(tab,sizeof(TUint32)*aMaxCount);
	tab[0]=100;
	TRAP(r, Huffman::HuffmanL(tab,aMaxCount,tab));
	test (r==KErrNone);
	test (tab[0]==1);
	for (i=1;i<aMaxCount;++i)
		test (tab[i]==0);
	Huffman::Decoding(tab,aMaxCount,tab,200);
	TUint8 bits=0;
	TBitInput in(&bits,1);
	test (in.HuffmanL(tab)==200);

	// test flat distributions with 2..aMaxCount symbols
	TInt len=0;
	for (TInt c=2;c<aMaxCount;++c)
		{
		if ((2<<len)==c)
			++len;
		Mem::FillZ(tab,sizeof(TUint32)*aMaxCount);
		for (i=0;i<c;++i)
			tab[i]=100;
		TRAP(r, Huffman::HuffmanL(tab,aMaxCount,tab));
		test (r==KErrNone);
		TInt small=0;
		for (i=0;i<c;++i)
			{
			if (TInt(tab[i])==len)
				++small;
			else
				test (TInt(tab[i])==len+1);
			}
		for (;i<aMaxCount;++i)
			test (tab[i]==0);
		test (small == (2<<len)-c);
		}

	delete [] tab;
	}

void Power2Huffman()
//
// Test Huffman generator for the distribution 2^0,2^0,2^1,2^2,2^3,...
//
	{
	TUint32 tab[Huffman::KMaxCodeLength+2];

	for (TInt c=1;c<=Huffman::KMaxCodeLength+1;c++)
		{
		tab[c]=tab[c-1]=1;
		TInt i;
		for (i=c-1;--i>=0;)
			tab[i]=2*tab[i+1];

		TRAPD(r,Huffman::HuffmanL(tab,c+1,tab));
		if (c>Huffman::KMaxCodeLength)
			{
			test (r==KErrOverflow);
			continue;
			}

		test (TInt(tab[c]) == c);
		for (i=0;i<c;++i)
			test (TInt(tab[i]) == i+1);

		Huffman::Decoding(tab,c+1,tab);
		for (i=0;i<=c;++i)
			{
			TUint8 buf[4];
			TBitOutput out(buf,4);
			out.WriteL(0xffffffff,i);
			out.WriteL(0,1);
			out.PadL(1);
			TBitInput in(buf,Min(i+1,c));
			TInt ix=-1;
			TRAP(r, ix=in.HuffmanL(tab));
			test (r==KErrNone);
			test (ix==i);
			TRAP(r, in.HuffmanL(tab));
			test (r==KErrUnderflow);
			}
		}
	}

void FibonacciHuffman()
//
// Test Huffman generator for the distribution 1,1,2,3,5,8,13,21,...
//
	{
	TUint32 tab[Huffman::KMaxCodeLength+2];

	for (TInt c=1;c<=Huffman::KMaxCodeLength+1;c++)
		{
		tab[c]=tab[c-1]=1;
		TInt i;
		for (i=c-1;--i>=0;)
			tab[i]=tab[i+1]+tab[i+2];

		TRAPD(r,Huffman::HuffmanL(tab,c+1,tab));
		if (c>Huffman::KMaxCodeLength)
			{
			test (r==KErrOverflow);
			continue;
			}

		test (TInt(tab[c]) == c);
		for (i=0;i<c;++i)
			test (TInt(tab[i]) == i+1);

		Huffman::Decoding(tab,c+1,tab);
		for (i=0;i<=c;++i)
			{
			TUint8 buf[4];
			TBitOutput out(buf,4);
			out.WriteL(0xffffffff,i);
			out.WriteL(0,1);
			out.PadL(1);
			TBitInput in(buf,Min(i+1,c));
			TInt ix=-1;
			TRAP(r, ix=in.HuffmanL(tab));
			test (r==KErrNone);
			test (ix==i);
			TRAP(r, in.HuffmanL(tab));
			test (r==KErrUnderflow);
			}
		}
	}

void SpecificHuffman(TInt aMaxCount)
	{
	test.Start(_L("Flat distributions"));
	FlatHuffman(aMaxCount);
	test.Next(_L("Power-of-2 distributions"));
	Power2Huffman();
	test.Next(_L("Fibonacci distributions"));
	FibonacciHuffman();
	test.End();
	}

// Huffman generator validity testing. Checking code properties for a sequence of random
// frequency distributions.

TInt64 RSeed(KTestData);

inline TInt Random(TInt aLimit)
	{return aLimit>0 ? (Math::Rand(RSeed)%aLimit) : 0;}

void GenerateFreq(TUint32* aTable, TInt aCount, TInt aTotalFreq, TInt aVariance, TInt aZeros)
//
// Generate a random frequency table
//
	{
	for (TInt i=0;i<aCount;++i)
		{
		if (aZeros && Random(aCount-i)<aZeros)
			{
			aTable[i]=0;
			--aZeros;
			}
		else if (aCount-aZeros-i == 1)
			{
			aTable[i]=aTotalFreq;
			aTotalFreq=0;
			}
		else
			{
			TInt ave=aTotalFreq/(aCount-aZeros-i);
			if (aVariance==0)
				{
				aTable[i]=ave;
				aTotalFreq-=ave;
				}
			else
				{
				TInt var=I64INT(TInt64(ave)<<aVariance>>8);
				TInt min=Max(1,ave-var);
				TInt max=Min(1+aTotalFreq-(aCount-aZeros-i),ave+var);
				TInt f = max<=min ? ave : min+Random(max-min);
				aTable[i] = f;
				aTotalFreq-=f;
				}
			}
		}
	}

TInt NumericalSort(const TUint32& aLeft, const TUint32& aRight)
	{
	return aLeft-aRight;
	}

TInt64 VerifyOptimalCode(const TUint32* aFreq, const TUint32* aCode, TInt aCount, TInt aTotalFreqLog2)
//
// We can show tht the expected code length is at least as short as a Shannon-Fano encoding
//
	{
	TInt64 totalHuff=0;
	TInt64 totalSF=0;
	TInt i;
	for (i=0;i<aCount;++i)
		{
		TInt f=aFreq[i];
		TInt l=aCode[i];
		if (f == 0)
			{
			test (l == 0);
			continue;
			}
		totalHuff+=f*l;
		TInt s=1;
		while ((f<<s>>aTotalFreqLog2)!=1)
			++s;
		totalSF+=f*s;
		}
	test (totalHuff<=totalSF);

	RPointerArray<TUint32> index(aCount);
	CleanupClosePushL(index);
	for (i=0;i<aCount;++i)
		{
		if (aFreq[i] != 0)
			User::LeaveIfError(index.InsertInOrderAllowRepeats(aFreq+i,&NumericalSort));
		}

	TInt smin,smax;
	smin=smax=aCode[index[0]-aFreq];
	for (i=1;i<index.Count();++i)
		{
		TInt pix=index[i-1]-aFreq;
		TInt nix=index[i]-aFreq;
		TInt pf=aFreq[pix];
		TInt nf=aFreq[nix];
		TInt ps=aCode[pix];
		TInt ns=aCode[nix];

		if (nf==pf)
			{
			smin=Min(smin,ns);
			smax=Max(smax,ns);
			test (smin==smax || smin+1==smax);
			}
		else
			{
			test (nf>pf);
			test (ns<=ps);
			smin=smax=ns;
			}
		}
	CleanupStack::PopAndDestroy();

	return totalHuff;
	}

TInt LexicalSort(const TUint32& aLeft, const TUint32& aRight)
	{
	const TUint32 KCodeMask=(1<<Huffman::KMaxCodeLength)-1;
	return (aLeft&KCodeMask)-(aRight&KCodeMask);
	}

void VerifyCanonicalEncodingL(const TUint32* aCode, const TUint32* aEncode, TInt aCount)
//
// A canonical encoding assigns codes from '0' in increasing code length order, and
// in increasing index in the table for equal code length.
//
// Huffman is also a 'prefix-free' code, so we check this property of the encoding
//
	{
	TInt i;
	for (i=0;i<aCount;++i)
		test (aCode[i] == aEncode[i]>>Huffman::KMaxCodeLength);

	RPointerArray<TUint32> index(aCount);
	CleanupClosePushL(index);
	for (i=0;i<aCount;++i)
		{
		if (aCode[i] != 0)
			User::LeaveIfError(index.InsertInOrder(aEncode+i,&LexicalSort));
		}

	for (i=1;i<index.Count();++i)
		{
		TInt pix=index[i-1]-aEncode;
		TInt nix=index[i]-aEncode;
		test (aCode[pix]<=aCode[nix]);				// code lengths are always increasing
		test (aCode[pix]<aCode[nix] || pix<nix);	// same code length => index order preserved

		// check that a code is not a prefix of the next one. This is sufficent for checking the
		// prefix condition as we have already sorted the codes in lexicographical order
		TUint32 pc=aEncode[pix]<<(32-Huffman::KMaxCodeLength);
		TUint32 nc=aEncode[nix]<<(32-Huffman::KMaxCodeLength);
		TInt plen=aCode[pix];
		test ((pc>>(32-plen)) != (nc>>(32-plen)));	// pc is not a prefix for nc
		}
	CleanupStack::PopAndDestroy(&index);
	}

void VerifyCanonicalDecoding(const TUint32* aEncode, const TUint32* aDecode, TInt aCount, TInt aBase)
//
// We've checked the encoding is valid, so now we check that the decoding can correctly
// decode every code
//
	{
	TUint8 buffer[(Huffman::KMaxCodeLength+7)/8];
	TBitInput in;
	TBitOutput out;

	while (--aCount>=0)
		{
		if (aEncode[aCount])
			{
			out.Set(buffer,sizeof(buffer));
			out.HuffmanL(aEncode[aCount]);
			out.PadL(0);
			in.Set(buffer,aEncode[aCount]>>Huffman::KMaxCodeLength);
			TInt v=-1;
			TRAPD(r,v=in.HuffmanL(aDecode));
			test (r==KErrNone);
			test (v==aCount+aBase);
			TRAP(r,in.ReadL());
			test (r==KErrUnderflow);
			}
		}
	}

TInt TestExternalizeL(const TUint32* aCode, TUint8* aExtern, TUint32* aIntern, TInt aCount)
	{
	TBitOutput out(aExtern,aCount*4);
	Huffman::ExternalizeL(out,aCode,aCount);
	TInt bits=out.BufferedBits()+8*(out.Ptr()-aExtern);
	out.PadL(0);
	TBitInput in(aExtern,bits);
	TRAPD(r,Huffman::InternalizeL(in,aIntern,aCount));
	test (r == KErrNone);
	test (Mem::Compare((TUint8*)aCode,aCount*sizeof(TUint32),(TUint8*)aIntern,aCount*sizeof(TUint32)) == 0);
	TRAP(r,in.ReadL());
	test (r == KErrUnderflow);
	return bits;
	}

void RandomHuffmanL(TInt aIter, TInt aMaxSymbols)
//
// generate random frequency distributions and verify
// (a) the Huffman generator creates a mathematically 'optimal code'
// (b) the canonical encoding is the canonical encoding
// (c) the decoding tree correctly decodes each code.
// (d) the encoding can be correctly externalised and internalised
//
	{
	TReal KLog2;
	Math::Ln(KLog2,2);
	const TInt KTotalFreqLog2=24;
	const TInt KTotalFreq=1<<KTotalFreqLog2;

	while (--aIter >= 0)
		{
		TInt num=2+Random(aMaxSymbols-1);

		TUint32* const freq = new(ELeave) TUint32[num*3];
		CleanupArrayDeletePushL(freq);
		TUint32* const code = freq+num;
		TUint32* const encoding = code+num;
		TUint32* const decoding = freq;
		TUint8* const exter = (TUint8*)encoding;
		TUint32* const intern = freq;

		TInt var=Random(24);
		TInt zero=Random(num-2);
		GenerateFreq(freq,num,KTotalFreq,var,zero);

		Huffman::HuffmanL(freq,num,code);
		VerifyOptimalCode(freq,code,num,KTotalFreqLog2);

		Huffman::Encoding(code,num,encoding);
		VerifyCanonicalEncodingL(code,encoding,num);

		TInt base=Random(Huffman::KMaxCodes-num);
		Huffman::Decoding(code,num,decoding,base);
		VerifyCanonicalDecoding(encoding,decoding,num,base);

		TestExternalizeL(code,exter,intern,num);
		CleanupStack::PopAndDestroy();
		}
	}

///

void MainL()
	{
	test.Start(_L("Test Bit reader"));
	TestBitReading();
	test.Next(_L("Test Bit writer"));
	TestBitWriting();
	test.Next(_L("Test Huffman decoder"));
	TestHuffmanL();
	test.Next(_L("Test Huffman generator for known distributions"));
	SpecificHuffman(800);
	test.Next(_L("Test Huffman generator for random distributions"));
	TRAPD(r,RandomHuffmanL(1000,800));
	test (r==KErrNone);
	test.End();
	}

TInt E32Main()
	{
	test.Title();
	CTrapCleanup* c=CTrapCleanup::New();
	test (c!=0);
	TRAPD(r,MainL());
	test (r==KErrNone);
	delete c;
	test.Close();
	return r;
	}