// Copyright (c) 2004-2009 Nokia Corporation and/or its subsidiary(-ies).

// All rights reserved.

// This component and the accompanying materials are made available

// which accompanies this distribution, and is available

//

// 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'