diff -r c55016431358 -r 0a7b44b10206 symport/e32test/buffer/t_huff.cpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/symport/e32test/buffer/t_huff.cpp	Thu Jun 25 15:59:54 2009 +0100
@@ -0,0 +1,995 @@
+// 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;
+	}