// 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 "Eclipse Public License v1.0"

 // which accompanies this distribution, and is available

 // at the URL "http://www.eclipse.org/legal/epl-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(RProcess().FileName());

 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;

 	}