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

     2 // All rights reserved.

     3 // This component and the accompanying materials are made available

     4 // under the terms of the License "Eclipse Public License v1.0"

     5 // which accompanies this distribution, and is available

     6 // at the URL "http://www.eclipse.org/legal/epl-v10.html".

     7 //

     8 // Initial Contributors:

     9 // Nokia Corporation - initial contribution.

    10 //

    11 // Contributors:

    12 //

    13 // Description:

    14 // e32test/buffer/t_huff.cpp

    15 // Overview:

    16 // Test methods of the Huffman, TBitInput and TBitOutput classes.

    17 // API Information:

    18 // Huffman, TBitInput, TBitOutput

    19 // Details:

    20 // - Test and verify the results of TBitInput bit reading:

    21 // - test and verify single bit reads, multiple bit reads and 32-bit reads

    22 // - test and verify single bit reads and multiple bit reads from a 

    23 // fractured input.

    24 // - test and verify overrun reads

    25 // - Test and verify the results of TBitOutput bit writing:

    26 // - test and verify bitstream padding

    27 // - test and verify single bit and multiple bit writes

    28 // - test and verify overflow writes

    29 // - Test and verify the results of a Huffman decoder using Huffman class 

    30 // static methods, TBitOutput and TBitInput objects.

    31 // - Test and verify the results of a Huffman generator for known distributions:

    32 // flat, power-of-2 and Fibonacci.

    33 // - Test and verify the results of a Huffman generator for random distributions:

    34 // - generate random frequency distributions and verify:

    35 // (a) the Huffman generator creates a mathematically 'optimal code'

    36 // (b) the canonical encoding is canonical

    37 // (c) the decoding tree correctly decodes each code

    38 // (d) the encoding can be correctly externalised and internalised

    39 // Platforms/Drives/Compatibility:

    40 // All 

    41 // Assumptions/Requirement/Pre-requisites:

    42 // Failures and causes:

    43 // Base Port information:

    44 // 

    45 //

    46 

    47 #include <e32test.h>

    48 #include <e32math.h>

    49 #include <e32huffman.h>

    50 

    51 RTest test(RProcess().FileName());

    52 

    53 const Uint64 KTestData=UI64LIT(0x6f1b09a7e8c523d4);

    54 const TUint8 KTestBuffer[] = {0x6f,0x1b,0x09,0xa7,0xe8,0xc5,0x23,0xd4};

    55 const TInt KTestBytes=sizeof(KTestBuffer);

    56 const TInt KTestBits=KTestBytes*8;

    57 

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

    59 

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

    61 

    62 class TAlignedBitInput : public TBitInput

    63 	{

    64 public:

    65 	TAlignedBitInput(const TUint8*,TInt,TInt);

    66 private:

    67 	void UnderflowL();

    68 private:

    69 	const TUint8* iRemainder;

    70 	TInt iCount;

    71 	};

    72 

    73 TAlignedBitInput::TAlignedBitInput(const TUint8* aPtr,TInt aCount,TInt aOffset)

    74 	:TBitInput(aPtr,32-aOffset,aOffset), iRemainder(aPtr+4), iCount(aOffset+aCount-32)

    75 	{}

    76 

    77 void TAlignedBitInput::UnderflowL()

    78 	{

    79 	if (!iRemainder)

    80 		User::Leave(KErrUnderflow);

    81 	else

    82 		{

    83 		Set(iRemainder,iCount);

    84 		iRemainder=0;

    85 		}

    86 	}

    87 

    88 class TSplitBitInput : public TBitInput

    89 	{

    90 public:

    91 	TSplitBitInput(const TUint8*,TInt,TInt,TInt);

    92 private:

    93 	void UnderflowL();

    94 private:

    95 	const TUint8* iBase;

    96 	TInt iBlockSize;

    97 	TInt iOffset;

    98 	TInt iAvail;

    99 	};

   100 

   101 TSplitBitInput::TSplitBitInput(const TUint8* aPtr,TInt aLength,TInt aOffset,TInt aSize)

   102 	:TBitInput(aPtr,aSize,aOffset), iBase(aPtr), iBlockSize(aSize), iOffset(aOffset+aSize), iAvail(aLength-aSize)

   103 	{}

   104 

   105 void TSplitBitInput::UnderflowL()

   106 	{

   107 	TInt len=Min(iBlockSize,iAvail);

   108 	if (len==0)

   109 		User::Leave(KErrUnderflow);

   110 	Set(iBase,len,iOffset);

   111 	iOffset+=len;

   112 	iAvail-=len;

   113 	}

   114 

   115 class TAlternateBitInput : public TBitInput

   116 	{

   117 public:

   118 	TAlternateBitInput(const TUint8*,TInt,TInt);

   119 private:

   120 	void UnderflowL();

   121 private:

   122 	const TUint8* iBase;

   123 	TInt iOffset;

   124 	TInt iAvail;

   125 	};

   126 

   127 TAlternateBitInput::TAlternateBitInput(const TUint8* aPtr,TInt aLength,TInt aOffset)

   128 	:TBitInput(aPtr,1,aOffset), iBase(aPtr), iOffset(aOffset+2), iAvail(aLength-2)

   129 	{}

   130 

   131 void TAlternateBitInput::UnderflowL()

   132 	{

   133 	if (iAvail<=0)

   134 		User::Leave(KErrUnderflow);

   135 	Set(iBase,1,iOffset);

   136 	iOffset+=2;

   137 	iAvail-=2;

   138 	}

   139 

   140 void TestReader(TBitInput& aIn, TestFn aFunc, Uint64 aBits, TInt aCount)

   141 	{

   142 	TBool eof=EFalse;

   143 	TRAPD(r,eof=aFunc(aIn,aBits,aCount));

   144 	test (r==KErrNone);

   145 	if (eof)

   146 		{

   147 		TRAP(r,aIn.ReadL());

   148 		test (r==KErrUnderflow);

   149 		}

   150 	}

   151 

   152 void TestBits(TInt aOffset, TInt aCount, TestFn aFunc)

   153 	{

   154 	Uint64 bits=KTestData;

   155 	if (aOffset)

   156 		bits<<=aOffset;

   157 	if (aCount<64)

   158 		bits&=~((Uint64(1)<<(64-aCount))-1);

   159 	// test with direct input

   160 	TBitInput in1(KTestBuffer,aCount,aOffset);

   161 	TestReader(in1,aFunc,bits,aCount);

   162 	// test with aligned input

   163 	if (aOffset<32 && aOffset+aCount>32)

   164 		{

   165 		TAlignedBitInput in2(KTestBuffer,aCount,aOffset);

   166 		TestReader(in2,aFunc,bits,aCount);

   167 		}

   168 	// test with blocked input

   169 	for (TInt block=aCount;--block>0;)

   170 		{

   171 		TSplitBitInput in3(KTestBuffer,aCount,aOffset,block);

   172 		TestReader(in3,aFunc,bits,aCount);

   173 		}

   174 	}

   175 

   176 void TestAlternateBits(TInt aOffset, TInt aCount, TestFn aFunc)

   177 	{

   178 	Uint64 bits=0;

   179 	TInt c=0;

   180 	for (TInt ix=aOffset;ix<aOffset+aCount;ix+=2)

   181 		{

   182 		if (KTestData<<ix>>63)

   183 			bits|=Uint64(1)<<(63-c);

   184 		++c;

   185 		}

   186 	// test with alternate input

   187 	TAlternateBitInput in1(KTestBuffer,aCount,aOffset);

   188 	TestReader(in1,aFunc,bits,c);

   189 	}

   190 

   191 void PermBits(TestFn aFunc, TInt aMinCount=1, TInt aMaxCount=64)

   192 	{

   193 	for (TInt offset=0;offset<KTestBits;++offset)

   194 		for (TInt count=Min(KTestBits-offset,aMaxCount);count>=aMinCount;--count)

   195 			TestBits(offset,count,aFunc);

   196 	}

   197 

   198 void AlternateBits(TestFn aFunc, TInt aMinCount=1)

   199 	{

   200 	for (TInt offset=0;offset<KTestBits;++offset)

   201 		for (TInt count=KTestBits-offset;count>=aMinCount;--count)

   202 			TestAlternateBits(offset,count,aFunc);

   203 	}

   204 

   205 TBool SingleBitRead(TBitInput& aIn, Uint64 aBits, TInt aCount)

   206 	{

   207 	while (--aCount>=0)

   208 		{

   209 		test (aIn.ReadL() == (aBits>>63));

   210 		aBits<<=1;

   211 		}

   212 	return ETrue;

   213 	}

   214 

   215 TBool MultiBitRead(TBitInput& aIn, Uint64 aBits, TInt aCount)

   216 	{

   217 	TInt c=aCount/2;

   218 	TUint v=aIn.ReadL(c);

   219 	if (c==0)

   220 		test (v==0);

   221 	else

   222 		{

   223 		test (v==TUint(aBits>>(64-c)));

   224 		aBits<<=c;

   225 		}

   226 	c=aCount-c;

   227 	v=aIn.ReadL(c);

   228 	if (c==0)

   229 		test (v==0);

   230 	else

   231 		test (v==TUint(aBits>>(64-c)));

   232 	return ETrue;

   233 	}

   234 

   235 TBool LongShortRead(TBitInput& aIn, Uint64 aBits, TInt aCount)

   236 	{

   237 	TUint v=aIn.ReadL(32);

   238 	test (v==TUint(aBits>>32));

   239 	aBits<<=32;

   240 	TInt c=aCount-32;

   241 	v=aIn.ReadL(c);

   242 	if (c==0)

   243 		test (v==0);

   244 	else

   245 		test (v==TUint(aBits>>(64-c)));

   246 	return ETrue;

   247 	}

   248 

   249 TBool ShortLongRead(TBitInput& aIn, Uint64 aBits, TInt aCount)

   250 	{

   251 	TInt c=aCount-32;

   252 	TUint v=aIn.ReadL(c);

   253 	if (c==0)

   254 		test (v==0);

   255 	else

   256 		{

   257 		test (v==TUint(aBits>>(64-c)));

   258 		aBits<<=c;

   259 		}

   260 	v=aIn.ReadL(32);

   261 	test (v==TUint(aBits>>32));

   262 	return ETrue;

   263 	}

   264 

   265 TBool EofRead(TBitInput& aIn, Uint64, TInt aCount)

   266 	{

   267 	TRAPD(r,aIn.ReadL(aCount+1));

   268 	test(r==KErrUnderflow);

   269 	return EFalse;

   270 	}

   271 

   272 void TestBitReading()

   273 	{

   274 	test.Start(_L("Test single bit reads"));

   275 	PermBits(&SingleBitRead);

   276 	test.Next(_L("Test multi bit reads"));

   277 	PermBits(&MultiBitRead);

   278 	test.Next(_L("Test 32-bit reads"));

   279 	PermBits(&LongShortRead,32);

   280 	PermBits(&ShortLongRead,32);

   281 	test.Next(_L("Test single bit reads (fractured input)"));

   282 	AlternateBits(&SingleBitRead);

   283 	test.Next(_L("Test multi bit reads (fractured input)"));

   284 	AlternateBits(&MultiBitRead);

   285 	test.Next(_L("Test overrun reads"));

   286 	PermBits(&EofRead,1,31);

   287 	test.End();

   288 	}

   289 

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

   291 

   292 void TestPadding()

   293 	{

   294 	TUint8 buffer[4];

   295 	TBitOutput out(buffer,4);

   296 	test(out.Ptr()==buffer);

   297 	test(out.BufferedBits()==0);

   298 	out.PadL(0);

   299 	test(out.Ptr()==buffer);

   300 	test(out.BufferedBits()==0);

   301 	out.WriteL(0,0);

   302 	out.PadL(0);

   303 	test(out.Ptr()==buffer);

   304 	test(out.BufferedBits()==0);

   305 

   306 	TInt i;

   307 	for (i=1;i<=8;++i)

   308 		{

   309 		out.Set(buffer,4);

   310 		out.WriteL(0,i);

   311 		test(out.BufferedBits()==(i%8));

   312 		out.PadL(1);

   313 		test(out.BufferedBits()==0);

   314 		out.WriteL(0,i);

   315 		test(out.BufferedBits()==(i%8));

   316 		out.PadL(1);

   317 		test(out.BufferedBits()==0);

   318 		test (out.Ptr()==buffer+2);

   319 		test (buffer[0]==(0xff>>i));

   320 		test (buffer[1]==(0xff>>i));

   321 		}

   322 

   323 	for (i=1;i<=8;++i)

   324 		{

   325 		out.Set(buffer,4);

   326 		out.WriteL(0xff,i);

   327 		out.PadL(0);

   328 		test (out.Ptr()==buffer+1);

   329 		test (buffer[0]==(0xff^(0xff>>i)));

   330 		}

   331 	}

   332 

   333 void TestBitWrites()

   334 	{

   335 	TUint8 buffer[KTestBytes];

   336 	TBitOutput out(buffer,KTestBytes);

   337 	TBitInput in(KTestBuffer,KTestBits);

   338 	TInt i;

   339 	for (i=KTestBits;--i>=0;)

   340 		out.WriteL(in.ReadL(),1);

   341 	test (Mem::Compare(buffer,KTestBytes,KTestBuffer,KTestBytes)==0);	

   342 

   343 	Mem::FillZ(buffer,KTestBytes);

   344 	out.Set(buffer,KTestBytes);

   345 	Uint64 bits=KTestData;

   346 	for (i=KTestBits;--i>=0;)

   347 		out.WriteL(TUint(bits>>i),1);

   348 	test (Mem::Compare(buffer,KTestBytes,KTestBuffer,KTestBytes)==0);

   349 	}

   350 

   351 void TestMultiBitWrites()

   352 	{

   353 	TInt i=0;

   354 	for (TInt j=0;j<32;++j)

   355 		for (TInt k=0;k<32;++k)

   356 			{

   357 			++i;

   358 			if (i+j+k>KTestBits)

   359 				i=0;

   360 			TUint8 buffer[KTestBytes];

   361 			TBitInput in(KTestBuffer,KTestBits);

   362 			TBitOutput out(buffer,KTestBytes);

   363 			in.ReadL(i);

   364 			out.WriteL(in.ReadL(j),j);

   365 			out.WriteL(in.ReadL(k),k);

   366 			out.PadL(0);

   367 			const TUint8* p=out.Ptr();

   368 			test (p-buffer == (j+k+7)/8);

   369 			Uint64 v=0;

   370 			while (p>buffer)

   371 				v=(v>>8) | Uint64(*--p)<<56;

   372 			Uint64 res=KTestData;

   373 			if (i+j+k<KTestBits)

   374 				res>>=KTestBits-i-j-k;

   375 			if (j+k<KTestBits)

   376 				res<<=KTestBits-j-k;

   377 			test (v==res);

   378 			}

   379 	}

   380 

   381 void TestAlternatingWrites()

   382 	{

   383 	const TInt KBufferSize=(1+32)*32;

   384 	TUint8 buffer[(7+KBufferSize)/8];

   385 	TBitOutput out(buffer,sizeof(buffer));

   386 	TInt i;

   387 	for (i=0;i<=32;++i)

   388 		out.WriteL(i&1?0xffffffff:0,i);

   389 	while (--i>=0)

   390 		out.WriteL(i&1?0:0xffffffff,i);

   391 	out.PadL(0);

   392 	TBitInput in(buffer,KBufferSize);

   393 	for (i=0;i<=32;++i)

   394 		{

   395 		TUint v=in.ReadL(i);

   396 		if (i&1)

   397 			test (v == (1u<<i)-1u);

   398 		else

   399 			test (v == 0);

   400 		}

   401 	while (--i>=0)

   402 		{

   403 		TUint v=in.ReadL(i);

   404 		if (i&1)

   405 			test (v == 0);

   406 		else if (i==32)

   407 			test (v == 0xffffffffu);

   408 		else

   409 			test (v == (1u<<i)-1u);

   410 		}

   411 	}

   412 

   413 class TOverflowOutput : public TBitOutput

   414 	{

   415 public:

   416 	TOverflowOutput();

   417 private:

   418 	void OverflowL();

   419 private:

   420 	TUint8 iBuf[1];

   421 	TInt iIx;

   422 	};

   423 

   424 TOverflowOutput::TOverflowOutput()

   425 	:iIx(0)

   426 	{}

   427 

   428 void TOverflowOutput::OverflowL()

   429 	{

   430 	if (Ptr()!=0)

   431 		{

   432 		test (Ptr()-iBuf == 1);

   433 		test (iBuf[0] == KTestBuffer[iIx]);

   434 		if (++iIx==KTestBytes)

   435 			User::Leave(KErrOverflow);

   436 		}

   437 	Set(iBuf,1);

   438 	}

   439 

   440 void OverflowTestL(TBitOutput& out, TInt j)

   441 	{

   442 	for (;;) out.WriteL(0xffffffffu,j);

   443 	}

   444 

   445 void TestOverflow()

   446 	{

   447 	test.Start(_L("Test default constructed output"));

   448 	TBitOutput out;

   449 	TInt i;

   450 	for (i=1;i<=8;++i)

   451 		{

   452 		TRAPD(r,out.WriteL(1,1));

   453 		if (i<8)

   454 			{

   455 			test (out.BufferedBits() == i);

   456 			test (r == KErrNone);

   457 			}

   458 		else

   459 			test (r == KErrOverflow);

   460 		}

   461 

   462 	test.Next(_L("Test overflow does not overrun the buffer"));

   463 	i=0;

   464 	for (TInt j=1;j<=32;++j)

   465 		{

   466 		if (++i>KTestBytes)

   467 			i=1;

   468 		TUint8 buffer[KTestBytes+1];

   469 		Mem::FillZ(buffer,sizeof(buffer));

   470 		out.Set(buffer,i);

   471 		TRAPD(r,OverflowTestL(out,j));

   472 		test (r == KErrOverflow);

   473 		TInt k=0;

   474 		while (buffer[k]==0xff)

   475 			{

   476 			++k;

   477 			test (k<TInt(sizeof(buffer)));

   478 			}

   479 		test (k <= i);

   480 		test ((i-k)*8 < j);

   481 		while (k<TInt(sizeof(buffer)))

   482 			{

   483 			test (buffer[k]==0);

   484 			++k;

   485 			}

   486 		}

   487 

   488 	test.Next(_L("Test overflow handler"));

   489 	TOverflowOutput vout;

   490 	TBitInput in(KTestBuffer,KTestBits);

   491 	for (i=KTestBits;--i>=0;)

   492 		vout.WriteL(in.ReadL(),1);

   493 	test(vout.BufferedBits() == 0);

   494 	TRAPD(r,vout.WriteL(0,1));

   495 	test (r == KErrNone);

   496 	TRAP(r,vout.PadL(0));

   497 	test (r == KErrOverflow);

   498 	test.End();

   499 	}

   500 

   501 void TestBitWriting()

   502 	{

   503 	test.Start(_L("Test padding"));

   504 	TestPadding();

   505 	test.Next(_L("Test bit writes"));

   506 	TestBitWrites();

   507 	test.Next(_L("Test multi-bit writes"));

   508 	TestMultiBitWrites();

   509 	TestAlternatingWrites();

   510 	test.Next(_L("Test overflow writes"));

   511 	TestOverflow();

   512 	test.End();

   513 	}

   514 

   515 // Huffman decode testing

   516 #ifdef __ARMCC__

   517 #pragma Onoinline

   518 #endif

   519 void Dummy(volatile TInt & /*x*/)

   520         {

   521 	}

   522 

   523 void TestHuffmanL()

   524 	{

   525 	const TInt KTestBits=32*32;

   526 

   527 	// build the huffman decoding tree for

   528 	// 0: '0'

   529 	// 1: '10'

   530 	// 2: '110' etc

   531 	TUint32 huffman[Huffman::KMaxCodeLength+1];

   532 	TInt i;

   533 	for (i=0;i<Huffman::KMaxCodeLength;++i)

   534 		huffman[i]=i+1;

   535 	huffman[Huffman::KMaxCodeLength]=Huffman::KMaxCodeLength;

   536 	Huffman::Decoding(huffman,Huffman::KMaxCodeLength+1,huffman);

   537 

   538 	TUint8 buffer[KTestBits/8];

   539 	for (TInt sz=0;sz<Huffman::KMaxCodeLength;++sz)

   540 		{

   541 		const TInt rep=KTestBits/(sz+1);

   542 		TBitOutput out(buffer,sizeof(buffer));

   543 		for (i=0;i<rep;++i)

   544 			{

   545 			out.WriteL(0xffffffff,sz);

   546 			out.WriteL(0,1);

   547 			}

   548 		out.PadL(1);

   549 		for (TInt blk=1;blk<=64;++blk)

   550 			{

   551 			TSplitBitInput in(buffer,rep*(sz+1)-1,0,blk);

   552 			for (i=0;i<rep-1;++i)

   553 				{

   554 				TInt v=-1;

   555 				TRAPD(r,v=in.HuffmanL(huffman));

   556 				test (r==KErrNone);

   557 				test (sz==v);

   558 				}

   559 			volatile TInt v=-1;

   560 		        Dummy(v);

   561 			TRAPD(r, v=in.HuffmanL(huffman));

   562 			test (v==-1);

   563 			test (r==KErrUnderflow);

   564 			}

   565 		}

   566 	}

   567 

   568 // Huffman generator testing with known but atypical distributions

   569 

   570 void FlatHuffman(TInt aMaxCount)

   571 	{

   572 	TUint32* tab=new TUint32[aMaxCount];

   573 	test (tab!=NULL);

   574 

   575 	// test empty distribution

   576 	Mem::FillZ(tab,sizeof(TUint32)*aMaxCount);

   577 	TRAPD(r, Huffman::HuffmanL(tab,aMaxCount,tab));

   578 	test (r==KErrNone);

   579 	TInt i;

   580 	for (i=0;i<aMaxCount;++i)

   581 		test (tab[i]==0);

   582 	Huffman::Decoding(tab,aMaxCount,tab);

   583 

   584 	// test single-symbol distribution

   585 	Mem::FillZ(tab,sizeof(TUint32)*aMaxCount);

   586 	tab[0]=100;

   587 	TRAP(r, Huffman::HuffmanL(tab,aMaxCount,tab));

   588 	test (r==KErrNone);

   589 	test (tab[0]==1);

   590 	for (i=1;i<aMaxCount;++i)

   591 		test (tab[i]==0);

   592 	Huffman::Decoding(tab,aMaxCount,tab,200);

   593 	TUint8 bits=0;

   594 	TBitInput in(&bits,1);

   595 	test (in.HuffmanL(tab)==200);

   596 

   597 	// test flat distributions with 2..aMaxCount symbols

   598 	TInt len=0;

   599 	for (TInt c=2;c<aMaxCount;++c)

   600 		{

   601 		if ((2<<len)==c)

   602 			++len;

   603 		Mem::FillZ(tab,sizeof(TUint32)*aMaxCount);

   604 		for (i=0;i<c;++i)

   605 			tab[i]=100;

   606 		TRAP(r, Huffman::HuffmanL(tab,aMaxCount,tab));

   607 		test (r==KErrNone);

   608 		TInt small=0;

   609 		for (i=0;i<c;++i)

   610 			{

   611 			if (TInt(tab[i])==len)

   612 				++small;

   613 			else

   614 				test (TInt(tab[i])==len+1);

   615 			}

   616 		for (;i<aMaxCount;++i)

   617 			test (tab[i]==0);

   618 		test (small == (2<<len)-c);

   619 		}

   620 

   621 	delete [] tab;

   622 	}

   623 

   624 void Power2Huffman()

   625 //

   626 // Test Huffman generator for the distribution 2^0,2^0,2^1,2^2,2^3,...

   627 //

   628 	{

   629 	TUint32 tab[Huffman::KMaxCodeLength+2];

   630 

   631 	for (TInt c=1;c<=Huffman::KMaxCodeLength+1;c++)

   632 		{

   633 		tab[c]=tab[c-1]=1;

   634 		TInt i;

   635 		for (i=c-1;--i>=0;)

   636 			tab[i]=2*tab[i+1];

   637 

   638 		TRAPD(r,Huffman::HuffmanL(tab,c+1,tab));

   639 		if (c>Huffman::KMaxCodeLength)

   640 			{

   641 			test (r==KErrOverflow);

   642 			continue;

   643 			}

   644 

   645 		test (TInt(tab[c]) == c);

   646 		for (i=0;i<c;++i)

   647 			test (TInt(tab[i]) == i+1);

   648 

   649 		Huffman::Decoding(tab,c+1,tab);

   650 		for (i=0;i<=c;++i)

   651 			{

   652 			TUint8 buf[4];

   653 			TBitOutput out(buf,4);

   654 			out.WriteL(0xffffffff,i);

   655 			out.WriteL(0,1);

   656 			out.PadL(1);

   657 			TBitInput in(buf,Min(i+1,c));

   658 			TInt ix=-1;

   659 			TRAP(r, ix=in.HuffmanL(tab));

   660 			test (r==KErrNone);

   661 			test (ix==i);

   662 			TRAP(r, in.HuffmanL(tab));

   663 			test (r==KErrUnderflow);

   664 			}

   665 		}

   666 	}

   667 

   668 void FibonacciHuffman()

   669 //

   670 // Test Huffman generator for the distribution 1,1,2,3,5,8,13,21,...

   671 //

   672 	{

   673 	TUint32 tab[Huffman::KMaxCodeLength+2];

   674 

   675 	for (TInt c=1;c<=Huffman::KMaxCodeLength+1;c++)

   676 		{

   677 		tab[c]=tab[c-1]=1;

   678 		TInt i;

   679 		for (i=c-1;--i>=0;)

   680 			tab[i]=tab[i+1]+tab[i+2];

   681 

   682 		TRAPD(r,Huffman::HuffmanL(tab,c+1,tab));

   683 		if (c>Huffman::KMaxCodeLength)

   684 			{

   685 			test (r==KErrOverflow);

   686 			continue;

   687 			}

   688 

   689 		test (TInt(tab[c]) == c);

   690 		for (i=0;i<c;++i)

   691 			test (TInt(tab[i]) == i+1);

   692 

   693 		Huffman::Decoding(tab,c+1,tab);

   694 		for (i=0;i<=c;++i)

   695 			{

   696 			TUint8 buf[4];

   697 			TBitOutput out(buf,4);

   698 			out.WriteL(0xffffffff,i);

   699 			out.WriteL(0,1);

   700 			out.PadL(1);

   701 			TBitInput in(buf,Min(i+1,c));

   702 			TInt ix=-1;

   703 			TRAP(r, ix=in.HuffmanL(tab));

   704 			test (r==KErrNone);

   705 			test (ix==i);

   706 			TRAP(r, in.HuffmanL(tab));

   707 			test (r==KErrUnderflow);

   708 			}

   709 		}

   710 	}

   711 

   712 void SpecificHuffman(TInt aMaxCount)

   713 	{

   714 	test.Start(_L("Flat distributions"));

   715 	FlatHuffman(aMaxCount);

   716 	test.Next(_L("Power-of-2 distributions"));

   717 	Power2Huffman();

   718 	test.Next(_L("Fibonacci distributions"));

   719 	FibonacciHuffman();

   720 	test.End();

   721 	}

   722 

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

   724 // frequency distributions.

   725 

   726 TInt64 RSeed(KTestData);

   727 

   728 inline TInt Random(TInt aLimit)

   729 	{return aLimit>0 ? (Math::Rand(RSeed)%aLimit) : 0;}

   730 

   731 void GenerateFreq(TUint32* aTable, TInt aCount, TInt aTotalFreq, TInt aVariance, TInt aZeros)

   732 //

   733 // Generate a random frequency table

   734 //

   735 	{

   736 	for (TInt i=0;i<aCount;++i)

   737 		{

   738 		if (aZeros && Random(aCount-i)<aZeros)

   739 			{

   740 			aTable[i]=0;

   741 			--aZeros;

   742 			}

   743 		else if (aCount-aZeros-i == 1)

   744 			{

   745 			aTable[i]=aTotalFreq;

   746 			aTotalFreq=0;

   747 			}

   748 		else

   749 			{

   750 			TInt ave=aTotalFreq/(aCount-aZeros-i);

   751 			if (aVariance==0)

   752 				{

   753 				aTable[i]=ave;

   754 				aTotalFreq-=ave;

   755 				}

   756 			else

   757 				{

   758 				TInt var=I64INT(TInt64(ave)<<aVariance>>8);

   759 				TInt min=Max(1,ave-var);

   760 				TInt max=Min(1+aTotalFreq-(aCount-aZeros-i),ave+var);

   761 				TInt f = max<=min ? ave : min+Random(max-min);

   762 				aTable[i] = f;

   763 				aTotalFreq-=f;

   764 				}

   765 			}

   766 		}

   767 	}

   768 

   769 TInt NumericalSort(const TUint32& aLeft, const TUint32& aRight)

   770 	{

   771 	return aLeft-aRight;

   772 	}

   773 

   774 TInt64 VerifyOptimalCode(const TUint32* aFreq, const TUint32* aCode, TInt aCount, TInt aTotalFreqLog2)

   775 //

   776 // We can show tht the expected code length is at least as short as a Shannon-Fano encoding

   777 //

   778 	{

   779 	TInt64 totalHuff=0;

   780 	TInt64 totalSF=0;

   781 	TInt i;

   782 	for (i=0;i<aCount;++i)

   783 		{

   784 		TInt f=aFreq[i];

   785 		TInt l=aCode[i];

   786 		if (f == 0)

   787 			{

   788 			test (l == 0);

   789 			continue;

   790 			}

   791 		totalHuff+=f*l;

   792 		TInt s=1;

   793 		while ((f<<s>>aTotalFreqLog2)!=1)

   794 			++s;

   795 		totalSF+=f*s;

   796 		}

   797 	test (totalHuff<=totalSF);

   798 

   799 	RPointerArray<TUint32> index(aCount);

   800 	CleanupClosePushL(index);

   801 	for (i=0;i<aCount;++i)

   802 		{

   803 		if (aFreq[i] != 0)

   804 			User::LeaveIfError(index.InsertInOrderAllowRepeats(aFreq+i,&NumericalSort));

   805 		}

   806 

   807 	TInt smin,smax;

   808 	smin=smax=aCode[index[0]-aFreq];

   809 	for (i=1;i<index.Count();++i)

   810 		{

   811 		TInt pix=index[i-1]-aFreq;

   812 		TInt nix=index[i]-aFreq;

   813 		TInt pf=aFreq[pix];

   814 		TInt nf=aFreq[nix];

   815 		TInt ps=aCode[pix];

   816 		TInt ns=aCode[nix];

   817 

   818 		if (nf==pf)

   819 			{

   820 			smin=Min(smin,ns);

   821 			smax=Max(smax,ns);

   822 			test (smin==smax || smin+1==smax);

   823 			}

   824 		else

   825 			{

   826 			test (nf>pf);

   827 			test (ns<=ps);

   828 			smin=smax=ns;

   829 			}

   830 		}

   831 	CleanupStack::PopAndDestroy();

   832 

   833 	return totalHuff;

   834 	}

   835 

   836 TInt LexicalSort(const TUint32& aLeft, const TUint32& aRight)

   837 	{

   838 	const TUint32 KCodeMask=(1<<Huffman::KMaxCodeLength)-1;

   839 	return (aLeft&KCodeMask)-(aRight&KCodeMask);

   840 	}

   841 

   842 void VerifyCanonicalEncodingL(const TUint32* aCode, const TUint32* aEncode, TInt aCount)

   843 //

   844 // A canonical encoding assigns codes from '0' in increasing code length order, and

   845 // in increasing index in the table for equal code length.

   846 //

   847 // Huffman is also a 'prefix-free' code, so we check this property of the encoding

   848 //

   849 	{

   850 	TInt i;

   851 	for (i=0;i<aCount;++i)

   852 		test (aCode[i] == aEncode[i]>>Huffman::KMaxCodeLength);

   853 

   854 	RPointerArray<TUint32> index(aCount);

   855 	CleanupClosePushL(index);

   856 	for (i=0;i<aCount;++i)

   857 		{

   858 		if (aCode[i] != 0)

   859 			User::LeaveIfError(index.InsertInOrder(aEncode+i,&LexicalSort));

   860 		}

   861 

   862 	for (i=1;i<index.Count();++i)

   863 		{

   864 		TInt pix=index[i-1]-aEncode;

   865 		TInt nix=index[i]-aEncode;

   866 		test (aCode[pix]<=aCode[nix]);				// code lengths are always increasing

   867 		test (aCode[pix]<aCode[nix] || pix<nix);	// same code length => index order preserved

   868 

   869 		// check that a code is not a prefix of the next one. This is sufficent for checking the

   870 		// prefix condition as we have already sorted the codes in lexicographical order

   871 		TUint32 pc=aEncode[pix]<<(32-Huffman::KMaxCodeLength);

   872 		TUint32 nc=aEncode[nix]<<(32-Huffman::KMaxCodeLength);

   873 		TInt plen=aCode[pix];

   874 		test ((pc>>(32-plen)) != (nc>>(32-plen)));	// pc is not a prefix for nc

   875 		}

   876 	CleanupStack::PopAndDestroy(&index);

   877 	}

   878 

   879 void VerifyCanonicalDecoding(const TUint32* aEncode, const TUint32* aDecode, TInt aCount, TInt aBase)

   880 //

   881 // We've checked the encoding is valid, so now we check that the decoding can correctly

   882 // decode every code

   883 //

   884 	{

   885 	TUint8 buffer[(Huffman::KMaxCodeLength+7)/8];

   886 	TBitInput in;

   887 	TBitOutput out;

   888 

   889 	while (--aCount>=0)

   890 		{

   891 		if (aEncode[aCount])

   892 			{

   893 			out.Set(buffer,sizeof(buffer));

   894 			out.HuffmanL(aEncode[aCount]);

   895 			out.PadL(0);

   896 			in.Set(buffer,aEncode[aCount]>>Huffman::KMaxCodeLength);

   897 			TInt v=-1;

   898 			TRAPD(r,v=in.HuffmanL(aDecode));

   899 			test (r==KErrNone);

   900 			test (v==aCount+aBase);

   901 			TRAP(r,in.ReadL());

   902 			test (r==KErrUnderflow);

   903 			}

   904 		}

   905 	}

   906 

   907 TInt TestExternalizeL(const TUint32* aCode, TUint8* aExtern, TUint32* aIntern, TInt aCount)

   908 	{

   909 	TBitOutput out(aExtern,aCount*4);

   910 	Huffman::ExternalizeL(out,aCode,aCount);

   911 	TInt bits=out.BufferedBits()+8*(out.Ptr()-aExtern);

   912 	out.PadL(0);

   913 	TBitInput in(aExtern,bits);

   914 	TRAPD(r,Huffman::InternalizeL(in,aIntern,aCount));

   915 	test (r == KErrNone);

   916 	test (Mem::Compare((TUint8*)aCode,aCount*sizeof(TUint32),(TUint8*)aIntern,aCount*sizeof(TUint32)) == 0);

   917 	TRAP(r,in.ReadL());

   918 	test (r == KErrUnderflow);

   919 	return bits;

   920 	}

   921 

   922 void RandomHuffmanL(TInt aIter, TInt aMaxSymbols)

   923 //

   924 // generate random frequency distributions and verify

   925 // (a) the Huffman generator creates a mathematically 'optimal code'

   926 // (b) the canonical encoding is the canonical encoding

   927 // (c) the decoding tree correctly decodes each code.

   928 // (d) the encoding can be correctly externalised and internalised

   929 //

   930 	{

   931 	TReal KLog2;

   932 	Math::Ln(KLog2,2);

   933 	const TInt KTotalFreqLog2=24;

   934 	const TInt KTotalFreq=1<<KTotalFreqLog2;

   935 

   936 	while (--aIter >= 0)

   937 		{

   938 		TInt num=2+Random(aMaxSymbols-1);

   939 

   940 		TUint32* const freq = new(ELeave) TUint32[num*3];

   941 		CleanupArrayDeletePushL(freq);

   942 		TUint32* const code = freq+num;

   943 		TUint32* const encoding = code+num;

   944 		TUint32* const decoding = freq;

   945 		TUint8* const exter = (TUint8*)encoding;

   946 		TUint32* const intern = freq;

   947 

   948 		TInt var=Random(24);

   949 		TInt zero=Random(num-2);

   950 		GenerateFreq(freq,num,KTotalFreq,var,zero);

   951 

   952 		Huffman::HuffmanL(freq,num,code);

   953 		VerifyOptimalCode(freq,code,num,KTotalFreqLog2);

   954 

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

   956 		VerifyCanonicalEncodingL(code,encoding,num);

   957 

   958 		TInt base=Random(Huffman::KMaxCodes-num);

   959 		Huffman::Decoding(code,num,decoding,base);

   960 		VerifyCanonicalDecoding(encoding,decoding,num,base);

   961 

   962 		TestExternalizeL(code,exter,intern,num);

   963 		CleanupStack::PopAndDestroy();

   964 		}

   965 	}

   966 

   967 ///

   968 

   969 void MainL()

   970 	{

   971 	test.Start(_L("Test Bit reader"));

   972 	TestBitReading();

   973 	test.Next(_L("Test Bit writer"));

   974 	TestBitWriting();

   975 	test.Next(_L("Test Huffman decoder"));

   976 	TestHuffmanL();

   977 	test.Next(_L("Test Huffman generator for known distributions"));

   978 	SpecificHuffman(800);

   979 	test.Next(_L("Test Huffman generator for random distributions"));

   980 	TRAPD(r,RandomHuffmanL(1000,800));

   981 	test (r==KErrNone);

   982 	test.End();

   983 	}

   984 

   985 TInt E32Main()

   986 	{

   987 	test.Title();

   988 	CTrapCleanup* c=CTrapCleanup::New();

   989 	test (c!=0);

   990 	TRAPD(r,MainL());

   991 	test (r==KErrNone);

   992 	delete c;

   993 	test.Close();

   994 	return r;

   995 	}