1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/kernelhwsrv/kerneltest/e32test/buffer/t_huff.cpp Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,995 @@
1.4 +// Copyright (c) 2004-2009 Nokia Corporation and/or its subsidiary(-ies).
1.5 +// All rights reserved.
1.6 +// This component and the accompanying materials are made available
1.7 +// under the terms of the License "Eclipse Public License v1.0"
1.8 +// which accompanies this distribution, and is available
1.9 +// at the URL "http://www.eclipse.org/legal/epl-v10.html".
1.10 +//
1.11 +// Initial Contributors:
1.12 +// Nokia Corporation - initial contribution.
1.13 +//
1.14 +// Contributors:
1.15 +//
1.16 +// Description:
1.17 +// e32test/buffer/t_huff.cpp
1.18 +// Overview:
1.19 +// Test methods of the Huffman, TBitInput and TBitOutput classes.
1.20 +// API Information:
1.21 +// Huffman, TBitInput, TBitOutput
1.22 +// Details:
1.23 +// - Test and verify the results of TBitInput bit reading:
1.24 +// - test and verify single bit reads, multiple bit reads and 32-bit reads
1.25 +// - test and verify single bit reads and multiple bit reads from a
1.26 +// fractured input.
1.27 +// - test and verify overrun reads
1.28 +// - Test and verify the results of TBitOutput bit writing:
1.29 +// - test and verify bitstream padding
1.30 +// - test and verify single bit and multiple bit writes
1.31 +// - test and verify overflow writes
1.32 +// - Test and verify the results of a Huffman decoder using Huffman class
1.33 +// static methods, TBitOutput and TBitInput objects.
1.34 +// - Test and verify the results of a Huffman generator for known distributions:
1.35 +// flat, power-of-2 and Fibonacci.
1.36 +// - Test and verify the results of a Huffman generator for random distributions:
1.37 +// - generate random frequency distributions and verify:
1.38 +// (a) the Huffman generator creates a mathematically 'optimal code'
1.39 +// (b) the canonical encoding is canonical
1.40 +// (c) the decoding tree correctly decodes each code
1.41 +// (d) the encoding can be correctly externalised and internalised
1.42 +// Platforms/Drives/Compatibility:
1.43 +// All
1.44 +// Assumptions/Requirement/Pre-requisites:
1.45 +// Failures and causes:
1.46 +// Base Port information:
1.47 +//
1.48 +//
1.49 +
1.50 +#include <e32test.h>
1.51 +#include <e32math.h>
1.52 +#include <e32huffman.h>
1.53 +
1.54 +RTest test(RProcess().FileName());
1.55 +
1.56 +const Uint64 KTestData=UI64LIT(0x6f1b09a7e8c523d4);
1.57 +const TUint8 KTestBuffer[] = {0x6f,0x1b,0x09,0xa7,0xe8,0xc5,0x23,0xd4};
1.58 +const TInt KTestBytes=sizeof(KTestBuffer);
1.59 +const TInt KTestBits=KTestBytes*8;
1.60 +
1.61 +// Input stream: bit and multi-bit read tests with exhsautive buffer reload testing
1.62 +
1.63 +typedef TBool (*TestFn)(TBitInput& aIn, Uint64 aBits, TInt aCount);
1.64 +
1.65 +class TAlignedBitInput : public TBitInput
1.66 + {
1.67 +public:
1.68 + TAlignedBitInput(const TUint8*,TInt,TInt);
1.69 +private:
1.70 + void UnderflowL();
1.71 +private:
1.72 + const TUint8* iRemainder;
1.73 + TInt iCount;
1.74 + };
1.75 +
1.76 +TAlignedBitInput::TAlignedBitInput(const TUint8* aPtr,TInt aCount,TInt aOffset)
1.77 + :TBitInput(aPtr,32-aOffset,aOffset), iRemainder(aPtr+4), iCount(aOffset+aCount-32)
1.78 + {}
1.79 +
1.80 +void TAlignedBitInput::UnderflowL()
1.81 + {
1.82 + if (!iRemainder)
1.83 + User::Leave(KErrUnderflow);
1.84 + else
1.85 + {
1.86 + Set(iRemainder,iCount);
1.87 + iRemainder=0;
1.88 + }
1.89 + }
1.90 +
1.91 +class TSplitBitInput : public TBitInput
1.92 + {
1.93 +public:
1.94 + TSplitBitInput(const TUint8*,TInt,TInt,TInt);
1.95 +private:
1.96 + void UnderflowL();
1.97 +private:
1.98 + const TUint8* iBase;
1.99 + TInt iBlockSize;
1.100 + TInt iOffset;
1.101 + TInt iAvail;
1.102 + };
1.103 +
1.104 +TSplitBitInput::TSplitBitInput(const TUint8* aPtr,TInt aLength,TInt aOffset,TInt aSize)
1.105 + :TBitInput(aPtr,aSize,aOffset), iBase(aPtr), iBlockSize(aSize), iOffset(aOffset+aSize), iAvail(aLength-aSize)
1.106 + {}
1.107 +
1.108 +void TSplitBitInput::UnderflowL()
1.109 + {
1.110 + TInt len=Min(iBlockSize,iAvail);
1.111 + if (len==0)
1.112 + User::Leave(KErrUnderflow);
1.113 + Set(iBase,len,iOffset);
1.114 + iOffset+=len;
1.115 + iAvail-=len;
1.116 + }
1.117 +
1.118 +class TAlternateBitInput : public TBitInput
1.119 + {
1.120 +public:
1.121 + TAlternateBitInput(const TUint8*,TInt,TInt);
1.122 +private:
1.123 + void UnderflowL();
1.124 +private:
1.125 + const TUint8* iBase;
1.126 + TInt iOffset;
1.127 + TInt iAvail;
1.128 + };
1.129 +
1.130 +TAlternateBitInput::TAlternateBitInput(const TUint8* aPtr,TInt aLength,TInt aOffset)
1.131 + :TBitInput(aPtr,1,aOffset), iBase(aPtr), iOffset(aOffset+2), iAvail(aLength-2)
1.132 + {}
1.133 +
1.134 +void TAlternateBitInput::UnderflowL()
1.135 + {
1.136 + if (iAvail<=0)
1.137 + User::Leave(KErrUnderflow);
1.138 + Set(iBase,1,iOffset);
1.139 + iOffset+=2;
1.140 + iAvail-=2;
1.141 + }
1.142 +
1.143 +void TestReader(TBitInput& aIn, TestFn aFunc, Uint64 aBits, TInt aCount)
1.144 + {
1.145 + TBool eof=EFalse;
1.146 + TRAPD(r,eof=aFunc(aIn,aBits,aCount));
1.147 + test (r==KErrNone);
1.148 + if (eof)
1.149 + {
1.150 + TRAP(r,aIn.ReadL());
1.151 + test (r==KErrUnderflow);
1.152 + }
1.153 + }
1.154 +
1.155 +void TestBits(TInt aOffset, TInt aCount, TestFn aFunc)
1.156 + {
1.157 + Uint64 bits=KTestData;
1.158 + if (aOffset)
1.159 + bits<<=aOffset;
1.160 + if (aCount<64)
1.161 + bits&=~((Uint64(1)<<(64-aCount))-1);
1.162 + // test with direct input
1.163 + TBitInput in1(KTestBuffer,aCount,aOffset);
1.164 + TestReader(in1,aFunc,bits,aCount);
1.165 + // test with aligned input
1.166 + if (aOffset<32 && aOffset+aCount>32)
1.167 + {
1.168 + TAlignedBitInput in2(KTestBuffer,aCount,aOffset);
1.169 + TestReader(in2,aFunc,bits,aCount);
1.170 + }
1.171 + // test with blocked input
1.172 + for (TInt block=aCount;--block>0;)
1.173 + {
1.174 + TSplitBitInput in3(KTestBuffer,aCount,aOffset,block);
1.175 + TestReader(in3,aFunc,bits,aCount);
1.176 + }
1.177 + }
1.178 +
1.179 +void TestAlternateBits(TInt aOffset, TInt aCount, TestFn aFunc)
1.180 + {
1.181 + Uint64 bits=0;
1.182 + TInt c=0;
1.183 + for (TInt ix=aOffset;ix<aOffset+aCount;ix+=2)
1.184 + {
1.185 + if (KTestData<<ix>>63)
1.186 + bits|=Uint64(1)<<(63-c);
1.187 + ++c;
1.188 + }
1.189 + // test with alternate input
1.190 + TAlternateBitInput in1(KTestBuffer,aCount,aOffset);
1.191 + TestReader(in1,aFunc,bits,c);
1.192 + }
1.193 +
1.194 +void PermBits(TestFn aFunc, TInt aMinCount=1, TInt aMaxCount=64)
1.195 + {
1.196 + for (TInt offset=0;offset<KTestBits;++offset)
1.197 + for (TInt count=Min(KTestBits-offset,aMaxCount);count>=aMinCount;--count)
1.198 + TestBits(offset,count,aFunc);
1.199 + }
1.200 +
1.201 +void AlternateBits(TestFn aFunc, TInt aMinCount=1)
1.202 + {
1.203 + for (TInt offset=0;offset<KTestBits;++offset)
1.204 + for (TInt count=KTestBits-offset;count>=aMinCount;--count)
1.205 + TestAlternateBits(offset,count,aFunc);
1.206 + }
1.207 +
1.208 +TBool SingleBitRead(TBitInput& aIn, Uint64 aBits, TInt aCount)
1.209 + {
1.210 + while (--aCount>=0)
1.211 + {
1.212 + test (aIn.ReadL() == (aBits>>63));
1.213 + aBits<<=1;
1.214 + }
1.215 + return ETrue;
1.216 + }
1.217 +
1.218 +TBool MultiBitRead(TBitInput& aIn, Uint64 aBits, TInt aCount)
1.219 + {
1.220 + TInt c=aCount/2;
1.221 + TUint v=aIn.ReadL(c);
1.222 + if (c==0)
1.223 + test (v==0);
1.224 + else
1.225 + {
1.226 + test (v==TUint(aBits>>(64-c)));
1.227 + aBits<<=c;
1.228 + }
1.229 + c=aCount-c;
1.230 + v=aIn.ReadL(c);
1.231 + if (c==0)
1.232 + test (v==0);
1.233 + else
1.234 + test (v==TUint(aBits>>(64-c)));
1.235 + return ETrue;
1.236 + }
1.237 +
1.238 +TBool LongShortRead(TBitInput& aIn, Uint64 aBits, TInt aCount)
1.239 + {
1.240 + TUint v=aIn.ReadL(32);
1.241 + test (v==TUint(aBits>>32));
1.242 + aBits<<=32;
1.243 + TInt c=aCount-32;
1.244 + v=aIn.ReadL(c);
1.245 + if (c==0)
1.246 + test (v==0);
1.247 + else
1.248 + test (v==TUint(aBits>>(64-c)));
1.249 + return ETrue;
1.250 + }
1.251 +
1.252 +TBool ShortLongRead(TBitInput& aIn, Uint64 aBits, TInt aCount)
1.253 + {
1.254 + TInt c=aCount-32;
1.255 + TUint v=aIn.ReadL(c);
1.256 + if (c==0)
1.257 + test (v==0);
1.258 + else
1.259 + {
1.260 + test (v==TUint(aBits>>(64-c)));
1.261 + aBits<<=c;
1.262 + }
1.263 + v=aIn.ReadL(32);
1.264 + test (v==TUint(aBits>>32));
1.265 + return ETrue;
1.266 + }
1.267 +
1.268 +TBool EofRead(TBitInput& aIn, Uint64, TInt aCount)
1.269 + {
1.270 + TRAPD(r,aIn.ReadL(aCount+1));
1.271 + test(r==KErrUnderflow);
1.272 + return EFalse;
1.273 + }
1.274 +
1.275 +void TestBitReading()
1.276 + {
1.277 + test.Start(_L("Test single bit reads"));
1.278 + PermBits(&SingleBitRead);
1.279 + test.Next(_L("Test multi bit reads"));
1.280 + PermBits(&MultiBitRead);
1.281 + test.Next(_L("Test 32-bit reads"));
1.282 + PermBits(&LongShortRead,32);
1.283 + PermBits(&ShortLongRead,32);
1.284 + test.Next(_L("Test single bit reads (fractured input)"));
1.285 + AlternateBits(&SingleBitRead);
1.286 + test.Next(_L("Test multi bit reads (fractured input)"));
1.287 + AlternateBits(&MultiBitRead);
1.288 + test.Next(_L("Test overrun reads"));
1.289 + PermBits(&EofRead,1,31);
1.290 + test.End();
1.291 + }
1.292 +
1.293 +// Bit output testing (assumes bit input is correct)
1.294 +
1.295 +void TestPadding()
1.296 + {
1.297 + TUint8 buffer[4];
1.298 + TBitOutput out(buffer,4);
1.299 + test(out.Ptr()==buffer);
1.300 + test(out.BufferedBits()==0);
1.301 + out.PadL(0);
1.302 + test(out.Ptr()==buffer);
1.303 + test(out.BufferedBits()==0);
1.304 + out.WriteL(0,0);
1.305 + out.PadL(0);
1.306 + test(out.Ptr()==buffer);
1.307 + test(out.BufferedBits()==0);
1.308 +
1.309 + TInt i;
1.310 + for (i=1;i<=8;++i)
1.311 + {
1.312 + out.Set(buffer,4);
1.313 + out.WriteL(0,i);
1.314 + test(out.BufferedBits()==(i%8));
1.315 + out.PadL(1);
1.316 + test(out.BufferedBits()==0);
1.317 + out.WriteL(0,i);
1.318 + test(out.BufferedBits()==(i%8));
1.319 + out.PadL(1);
1.320 + test(out.BufferedBits()==0);
1.321 + test (out.Ptr()==buffer+2);
1.322 + test (buffer[0]==(0xff>>i));
1.323 + test (buffer[1]==(0xff>>i));
1.324 + }
1.325 +
1.326 + for (i=1;i<=8;++i)
1.327 + {
1.328 + out.Set(buffer,4);
1.329 + out.WriteL(0xff,i);
1.330 + out.PadL(0);
1.331 + test (out.Ptr()==buffer+1);
1.332 + test (buffer[0]==(0xff^(0xff>>i)));
1.333 + }
1.334 + }
1.335 +
1.336 +void TestBitWrites()
1.337 + {
1.338 + TUint8 buffer[KTestBytes];
1.339 + TBitOutput out(buffer,KTestBytes);
1.340 + TBitInput in(KTestBuffer,KTestBits);
1.341 + TInt i;
1.342 + for (i=KTestBits;--i>=0;)
1.343 + out.WriteL(in.ReadL(),1);
1.344 + test (Mem::Compare(buffer,KTestBytes,KTestBuffer,KTestBytes)==0);
1.345 +
1.346 + Mem::FillZ(buffer,KTestBytes);
1.347 + out.Set(buffer,KTestBytes);
1.348 + Uint64 bits=KTestData;
1.349 + for (i=KTestBits;--i>=0;)
1.350 + out.WriteL(TUint(bits>>i),1);
1.351 + test (Mem::Compare(buffer,KTestBytes,KTestBuffer,KTestBytes)==0);
1.352 + }
1.353 +
1.354 +void TestMultiBitWrites()
1.355 + {
1.356 + TInt i=0;
1.357 + for (TInt j=0;j<32;++j)
1.358 + for (TInt k=0;k<32;++k)
1.359 + {
1.360 + ++i;
1.361 + if (i+j+k>KTestBits)
1.362 + i=0;
1.363 + TUint8 buffer[KTestBytes];
1.364 + TBitInput in(KTestBuffer,KTestBits);
1.365 + TBitOutput out(buffer,KTestBytes);
1.366 + in.ReadL(i);
1.367 + out.WriteL(in.ReadL(j),j);
1.368 + out.WriteL(in.ReadL(k),k);
1.369 + out.PadL(0);
1.370 + const TUint8* p=out.Ptr();
1.371 + test (p-buffer == (j+k+7)/8);
1.372 + Uint64 v=0;
1.373 + while (p>buffer)
1.374 + v=(v>>8) | Uint64(*--p)<<56;
1.375 + Uint64 res=KTestData;
1.376 + if (i+j+k<KTestBits)
1.377 + res>>=KTestBits-i-j-k;
1.378 + if (j+k<KTestBits)
1.379 + res<<=KTestBits-j-k;
1.380 + test (v==res);
1.381 + }
1.382 + }
1.383 +
1.384 +void TestAlternatingWrites()
1.385 + {
1.386 + const TInt KBufferSize=(1+32)*32;
1.387 + TUint8 buffer[(7+KBufferSize)/8];
1.388 + TBitOutput out(buffer,sizeof(buffer));
1.389 + TInt i;
1.390 + for (i=0;i<=32;++i)
1.391 + out.WriteL(i&1?0xffffffff:0,i);
1.392 + while (--i>=0)
1.393 + out.WriteL(i&1?0:0xffffffff,i);
1.394 + out.PadL(0);
1.395 + TBitInput in(buffer,KBufferSize);
1.396 + for (i=0;i<=32;++i)
1.397 + {
1.398 + TUint v=in.ReadL(i);
1.399 + if (i&1)
1.400 + test (v == (1u<<i)-1u);
1.401 + else
1.402 + test (v == 0);
1.403 + }
1.404 + while (--i>=0)
1.405 + {
1.406 + TUint v=in.ReadL(i);
1.407 + if (i&1)
1.408 + test (v == 0);
1.409 + else if (i==32)
1.410 + test (v == 0xffffffffu);
1.411 + else
1.412 + test (v == (1u<<i)-1u);
1.413 + }
1.414 + }
1.415 +
1.416 +class TOverflowOutput : public TBitOutput
1.417 + {
1.418 +public:
1.419 + TOverflowOutput();
1.420 +private:
1.421 + void OverflowL();
1.422 +private:
1.423 + TUint8 iBuf[1];
1.424 + TInt iIx;
1.425 + };
1.426 +
1.427 +TOverflowOutput::TOverflowOutput()
1.428 + :iIx(0)
1.429 + {}
1.430 +
1.431 +void TOverflowOutput::OverflowL()
1.432 + {
1.433 + if (Ptr()!=0)
1.434 + {
1.435 + test (Ptr()-iBuf == 1);
1.436 + test (iBuf[0] == KTestBuffer[iIx]);
1.437 + if (++iIx==KTestBytes)
1.438 + User::Leave(KErrOverflow);
1.439 + }
1.440 + Set(iBuf,1);
1.441 + }
1.442 +
1.443 +void OverflowTestL(TBitOutput& out, TInt j)
1.444 + {
1.445 + for (;;) out.WriteL(0xffffffffu,j);
1.446 + }
1.447 +
1.448 +void TestOverflow()
1.449 + {
1.450 + test.Start(_L("Test default constructed output"));
1.451 + TBitOutput out;
1.452 + TInt i;
1.453 + for (i=1;i<=8;++i)
1.454 + {
1.455 + TRAPD(r,out.WriteL(1,1));
1.456 + if (i<8)
1.457 + {
1.458 + test (out.BufferedBits() == i);
1.459 + test (r == KErrNone);
1.460 + }
1.461 + else
1.462 + test (r == KErrOverflow);
1.463 + }
1.464 +
1.465 + test.Next(_L("Test overflow does not overrun the buffer"));
1.466 + i=0;
1.467 + for (TInt j=1;j<=32;++j)
1.468 + {
1.469 + if (++i>KTestBytes)
1.470 + i=1;
1.471 + TUint8 buffer[KTestBytes+1];
1.472 + Mem::FillZ(buffer,sizeof(buffer));
1.473 + out.Set(buffer,i);
1.474 + TRAPD(r,OverflowTestL(out,j));
1.475 + test (r == KErrOverflow);
1.476 + TInt k=0;
1.477 + while (buffer[k]==0xff)
1.478 + {
1.479 + ++k;
1.480 + test (k<TInt(sizeof(buffer)));
1.481 + }
1.482 + test (k <= i);
1.483 + test ((i-k)*8 < j);
1.484 + while (k<TInt(sizeof(buffer)))
1.485 + {
1.486 + test (buffer[k]==0);
1.487 + ++k;
1.488 + }
1.489 + }
1.490 +
1.491 + test.Next(_L("Test overflow handler"));
1.492 + TOverflowOutput vout;
1.493 + TBitInput in(KTestBuffer,KTestBits);
1.494 + for (i=KTestBits;--i>=0;)
1.495 + vout.WriteL(in.ReadL(),1);
1.496 + test(vout.BufferedBits() == 0);
1.497 + TRAPD(r,vout.WriteL(0,1));
1.498 + test (r == KErrNone);
1.499 + TRAP(r,vout.PadL(0));
1.500 + test (r == KErrOverflow);
1.501 + test.End();
1.502 + }
1.503 +
1.504 +void TestBitWriting()
1.505 + {
1.506 + test.Start(_L("Test padding"));
1.507 + TestPadding();
1.508 + test.Next(_L("Test bit writes"));
1.509 + TestBitWrites();
1.510 + test.Next(_L("Test multi-bit writes"));
1.511 + TestMultiBitWrites();
1.512 + TestAlternatingWrites();
1.513 + test.Next(_L("Test overflow writes"));
1.514 + TestOverflow();
1.515 + test.End();
1.516 + }
1.517 +
1.518 +// Huffman decode testing
1.519 +#ifdef __ARMCC__
1.520 +#pragma Onoinline
1.521 +#endif
1.522 +void Dummy(volatile TInt & /*x*/)
1.523 + {
1.524 + }
1.525 +
1.526 +void TestHuffmanL()
1.527 + {
1.528 + const TInt KTestBits=32*32;
1.529 +
1.530 + // build the huffman decoding tree for
1.531 + // 0: '0'
1.532 + // 1: '10'
1.533 + // 2: '110' etc
1.534 + TUint32 huffman[Huffman::KMaxCodeLength+1];
1.535 + TInt i;
1.536 + for (i=0;i<Huffman::KMaxCodeLength;++i)
1.537 + huffman[i]=i+1;
1.538 + huffman[Huffman::KMaxCodeLength]=Huffman::KMaxCodeLength;
1.539 + Huffman::Decoding(huffman,Huffman::KMaxCodeLength+1,huffman);
1.540 +
1.541 + TUint8 buffer[KTestBits/8];
1.542 + for (TInt sz=0;sz<Huffman::KMaxCodeLength;++sz)
1.543 + {
1.544 + const TInt rep=KTestBits/(sz+1);
1.545 + TBitOutput out(buffer,sizeof(buffer));
1.546 + for (i=0;i<rep;++i)
1.547 + {
1.548 + out.WriteL(0xffffffff,sz);
1.549 + out.WriteL(0,1);
1.550 + }
1.551 + out.PadL(1);
1.552 + for (TInt blk=1;blk<=64;++blk)
1.553 + {
1.554 + TSplitBitInput in(buffer,rep*(sz+1)-1,0,blk);
1.555 + for (i=0;i<rep-1;++i)
1.556 + {
1.557 + TInt v=-1;
1.558 + TRAPD(r,v=in.HuffmanL(huffman));
1.559 + test (r==KErrNone);
1.560 + test (sz==v);
1.561 + }
1.562 + volatile TInt v=-1;
1.563 + Dummy(v);
1.564 + TRAPD(r, v=in.HuffmanL(huffman));
1.565 + test (v==-1);
1.566 + test (r==KErrUnderflow);
1.567 + }
1.568 + }
1.569 + }
1.570 +
1.571 +// Huffman generator testing with known but atypical distributions
1.572 +
1.573 +void FlatHuffman(TInt aMaxCount)
1.574 + {
1.575 + TUint32* tab=new TUint32[aMaxCount];
1.576 + test (tab!=NULL);
1.577 +
1.578 + // test empty distribution
1.579 + Mem::FillZ(tab,sizeof(TUint32)*aMaxCount);
1.580 + TRAPD(r, Huffman::HuffmanL(tab,aMaxCount,tab));
1.581 + test (r==KErrNone);
1.582 + TInt i;
1.583 + for (i=0;i<aMaxCount;++i)
1.584 + test (tab[i]==0);
1.585 + Huffman::Decoding(tab,aMaxCount,tab);
1.586 +
1.587 + // test single-symbol distribution
1.588 + Mem::FillZ(tab,sizeof(TUint32)*aMaxCount);
1.589 + tab[0]=100;
1.590 + TRAP(r, Huffman::HuffmanL(tab,aMaxCount,tab));
1.591 + test (r==KErrNone);
1.592 + test (tab[0]==1);
1.593 + for (i=1;i<aMaxCount;++i)
1.594 + test (tab[i]==0);
1.595 + Huffman::Decoding(tab,aMaxCount,tab,200);
1.596 + TUint8 bits=0;
1.597 + TBitInput in(&bits,1);
1.598 + test (in.HuffmanL(tab)==200);
1.599 +
1.600 + // test flat distributions with 2..aMaxCount symbols
1.601 + TInt len=0;
1.602 + for (TInt c=2;c<aMaxCount;++c)
1.603 + {
1.604 + if ((2<<len)==c)
1.605 + ++len;
1.606 + Mem::FillZ(tab,sizeof(TUint32)*aMaxCount);
1.607 + for (i=0;i<c;++i)
1.608 + tab[i]=100;
1.609 + TRAP(r, Huffman::HuffmanL(tab,aMaxCount,tab));
1.610 + test (r==KErrNone);
1.611 + TInt small=0;
1.612 + for (i=0;i<c;++i)
1.613 + {
1.614 + if (TInt(tab[i])==len)
1.615 + ++small;
1.616 + else
1.617 + test (TInt(tab[i])==len+1);
1.618 + }
1.619 + for (;i<aMaxCount;++i)
1.620 + test (tab[i]==0);
1.621 + test (small == (2<<len)-c);
1.622 + }
1.623 +
1.624 + delete [] tab;
1.625 + }
1.626 +
1.627 +void Power2Huffman()
1.628 +//
1.629 +// Test Huffman generator for the distribution 2^0,2^0,2^1,2^2,2^3,...
1.630 +//
1.631 + {
1.632 + TUint32 tab[Huffman::KMaxCodeLength+2];
1.633 +
1.634 + for (TInt c=1;c<=Huffman::KMaxCodeLength+1;c++)
1.635 + {
1.636 + tab[c]=tab[c-1]=1;
1.637 + TInt i;
1.638 + for (i=c-1;--i>=0;)
1.639 + tab[i]=2*tab[i+1];
1.640 +
1.641 + TRAPD(r,Huffman::HuffmanL(tab,c+1,tab));
1.642 + if (c>Huffman::KMaxCodeLength)
1.643 + {
1.644 + test (r==KErrOverflow);
1.645 + continue;
1.646 + }
1.647 +
1.648 + test (TInt(tab[c]) == c);
1.649 + for (i=0;i<c;++i)
1.650 + test (TInt(tab[i]) == i+1);
1.651 +
1.652 + Huffman::Decoding(tab,c+1,tab);
1.653 + for (i=0;i<=c;++i)
1.654 + {
1.655 + TUint8 buf[4];
1.656 + TBitOutput out(buf,4);
1.657 + out.WriteL(0xffffffff,i);
1.658 + out.WriteL(0,1);
1.659 + out.PadL(1);
1.660 + TBitInput in(buf,Min(i+1,c));
1.661 + TInt ix=-1;
1.662 + TRAP(r, ix=in.HuffmanL(tab));
1.663 + test (r==KErrNone);
1.664 + test (ix==i);
1.665 + TRAP(r, in.HuffmanL(tab));
1.666 + test (r==KErrUnderflow);
1.667 + }
1.668 + }
1.669 + }
1.670 +
1.671 +void FibonacciHuffman()
1.672 +//
1.673 +// Test Huffman generator for the distribution 1,1,2,3,5,8,13,21,...
1.674 +//
1.675 + {
1.676 + TUint32 tab[Huffman::KMaxCodeLength+2];
1.677 +
1.678 + for (TInt c=1;c<=Huffman::KMaxCodeLength+1;c++)
1.679 + {
1.680 + tab[c]=tab[c-1]=1;
1.681 + TInt i;
1.682 + for (i=c-1;--i>=0;)
1.683 + tab[i]=tab[i+1]+tab[i+2];
1.684 +
1.685 + TRAPD(r,Huffman::HuffmanL(tab,c+1,tab));
1.686 + if (c>Huffman::KMaxCodeLength)
1.687 + {
1.688 + test (r==KErrOverflow);
1.689 + continue;
1.690 + }
1.691 +
1.692 + test (TInt(tab[c]) == c);
1.693 + for (i=0;i<c;++i)
1.694 + test (TInt(tab[i]) == i+1);
1.695 +
1.696 + Huffman::Decoding(tab,c+1,tab);
1.697 + for (i=0;i<=c;++i)
1.698 + {
1.699 + TUint8 buf[4];
1.700 + TBitOutput out(buf,4);
1.701 + out.WriteL(0xffffffff,i);
1.702 + out.WriteL(0,1);
1.703 + out.PadL(1);
1.704 + TBitInput in(buf,Min(i+1,c));
1.705 + TInt ix=-1;
1.706 + TRAP(r, ix=in.HuffmanL(tab));
1.707 + test (r==KErrNone);
1.708 + test (ix==i);
1.709 + TRAP(r, in.HuffmanL(tab));
1.710 + test (r==KErrUnderflow);
1.711 + }
1.712 + }
1.713 + }
1.714 +
1.715 +void SpecificHuffman(TInt aMaxCount)
1.716 + {
1.717 + test.Start(_L("Flat distributions"));
1.718 + FlatHuffman(aMaxCount);
1.719 + test.Next(_L("Power-of-2 distributions"));
1.720 + Power2Huffman();
1.721 + test.Next(_L("Fibonacci distributions"));
1.722 + FibonacciHuffman();
1.723 + test.End();
1.724 + }
1.725 +
1.726 +// Huffman generator validity testing. Checking code properties for a sequence of random
1.727 +// frequency distributions.
1.728 +
1.729 +TInt64 RSeed(KTestData);
1.730 +
1.731 +inline TInt Random(TInt aLimit)
1.732 + {return aLimit>0 ? (Math::Rand(RSeed)%aLimit) : 0;}
1.733 +
1.734 +void GenerateFreq(TUint32* aTable, TInt aCount, TInt aTotalFreq, TInt aVariance, TInt aZeros)
1.735 +//
1.736 +// Generate a random frequency table
1.737 +//
1.738 + {
1.739 + for (TInt i=0;i<aCount;++i)
1.740 + {
1.741 + if (aZeros && Random(aCount-i)<aZeros)
1.742 + {
1.743 + aTable[i]=0;
1.744 + --aZeros;
1.745 + }
1.746 + else if (aCount-aZeros-i == 1)
1.747 + {
1.748 + aTable[i]=aTotalFreq;
1.749 + aTotalFreq=0;
1.750 + }
1.751 + else
1.752 + {
1.753 + TInt ave=aTotalFreq/(aCount-aZeros-i);
1.754 + if (aVariance==0)
1.755 + {
1.756 + aTable[i]=ave;
1.757 + aTotalFreq-=ave;
1.758 + }
1.759 + else
1.760 + {
1.761 + TInt var=I64INT(TInt64(ave)<<aVariance>>8);
1.762 + TInt min=Max(1,ave-var);
1.763 + TInt max=Min(1+aTotalFreq-(aCount-aZeros-i),ave+var);
1.764 + TInt f = max<=min ? ave : min+Random(max-min);
1.765 + aTable[i] = f;
1.766 + aTotalFreq-=f;
1.767 + }
1.768 + }
1.769 + }
1.770 + }
1.771 +
1.772 +TInt NumericalSort(const TUint32& aLeft, const TUint32& aRight)
1.773 + {
1.774 + return aLeft-aRight;
1.775 + }
1.776 +
1.777 +TInt64 VerifyOptimalCode(const TUint32* aFreq, const TUint32* aCode, TInt aCount, TInt aTotalFreqLog2)
1.778 +//
1.779 +// We can show tht the expected code length is at least as short as a Shannon-Fano encoding
1.780 +//
1.781 + {
1.782 + TInt64 totalHuff=0;
1.783 + TInt64 totalSF=0;
1.784 + TInt i;
1.785 + for (i=0;i<aCount;++i)
1.786 + {
1.787 + TInt f=aFreq[i];
1.788 + TInt l=aCode[i];
1.789 + if (f == 0)
1.790 + {
1.791 + test (l == 0);
1.792 + continue;
1.793 + }
1.794 + totalHuff+=f*l;
1.795 + TInt s=1;
1.796 + while ((f<<s>>aTotalFreqLog2)!=1)
1.797 + ++s;
1.798 + totalSF+=f*s;
1.799 + }
1.800 + test (totalHuff<=totalSF);
1.801 +
1.802 + RPointerArray<TUint32> index(aCount);
1.803 + CleanupClosePushL(index);
1.804 + for (i=0;i<aCount;++i)
1.805 + {
1.806 + if (aFreq[i] != 0)
1.807 + User::LeaveIfError(index.InsertInOrderAllowRepeats(aFreq+i,&NumericalSort));
1.808 + }
1.809 +
1.810 + TInt smin,smax;
1.811 + smin=smax=aCode[index[0]-aFreq];
1.812 + for (i=1;i<index.Count();++i)
1.813 + {
1.814 + TInt pix=index[i-1]-aFreq;
1.815 + TInt nix=index[i]-aFreq;
1.816 + TInt pf=aFreq[pix];
1.817 + TInt nf=aFreq[nix];
1.818 + TInt ps=aCode[pix];
1.819 + TInt ns=aCode[nix];
1.820 +
1.821 + if (nf==pf)
1.822 + {
1.823 + smin=Min(smin,ns);
1.824 + smax=Max(smax,ns);
1.825 + test (smin==smax || smin+1==smax);
1.826 + }
1.827 + else
1.828 + {
1.829 + test (nf>pf);
1.830 + test (ns<=ps);
1.831 + smin=smax=ns;
1.832 + }
1.833 + }
1.834 + CleanupStack::PopAndDestroy();
1.835 +
1.836 + return totalHuff;
1.837 + }
1.838 +
1.839 +TInt LexicalSort(const TUint32& aLeft, const TUint32& aRight)
1.840 + {
1.841 + const TUint32 KCodeMask=(1<<Huffman::KMaxCodeLength)-1;
1.842 + return (aLeft&KCodeMask)-(aRight&KCodeMask);
1.843 + }
1.844 +
1.845 +void VerifyCanonicalEncodingL(const TUint32* aCode, const TUint32* aEncode, TInt aCount)
1.846 +//
1.847 +// A canonical encoding assigns codes from '0' in increasing code length order, and
1.848 +// in increasing index in the table for equal code length.
1.849 +//
1.850 +// Huffman is also a 'prefix-free' code, so we check this property of the encoding
1.851 +//
1.852 + {
1.853 + TInt i;
1.854 + for (i=0;i<aCount;++i)
1.855 + test (aCode[i] == aEncode[i]>>Huffman::KMaxCodeLength);
1.856 +
1.857 + RPointerArray<TUint32> index(aCount);
1.858 + CleanupClosePushL(index);
1.859 + for (i=0;i<aCount;++i)
1.860 + {
1.861 + if (aCode[i] != 0)
1.862 + User::LeaveIfError(index.InsertInOrder(aEncode+i,&LexicalSort));
1.863 + }
1.864 +
1.865 + for (i=1;i<index.Count();++i)
1.866 + {
1.867 + TInt pix=index[i-1]-aEncode;
1.868 + TInt nix=index[i]-aEncode;
1.869 + test (aCode[pix]<=aCode[nix]); // code lengths are always increasing
1.870 + test (aCode[pix]<aCode[nix] || pix<nix); // same code length => index order preserved
1.871 +
1.872 + // check that a code is not a prefix of the next one. This is sufficent for checking the
1.873 + // prefix condition as we have already sorted the codes in lexicographical order
1.874 + TUint32 pc=aEncode[pix]<<(32-Huffman::KMaxCodeLength);
1.875 + TUint32 nc=aEncode[nix]<<(32-Huffman::KMaxCodeLength);
1.876 + TInt plen=aCode[pix];
1.877 + test ((pc>>(32-plen)) != (nc>>(32-plen))); // pc is not a prefix for nc
1.878 + }
1.879 + CleanupStack::PopAndDestroy(&index);
1.880 + }
1.881 +
1.882 +void VerifyCanonicalDecoding(const TUint32* aEncode, const TUint32* aDecode, TInt aCount, TInt aBase)
1.883 +//
1.884 +// We've checked the encoding is valid, so now we check that the decoding can correctly
1.885 +// decode every code
1.886 +//
1.887 + {
1.888 + TUint8 buffer[(Huffman::KMaxCodeLength+7)/8];
1.889 + TBitInput in;
1.890 + TBitOutput out;
1.891 +
1.892 + while (--aCount>=0)
1.893 + {
1.894 + if (aEncode[aCount])
1.895 + {
1.896 + out.Set(buffer,sizeof(buffer));
1.897 + out.HuffmanL(aEncode[aCount]);
1.898 + out.PadL(0);
1.899 + in.Set(buffer,aEncode[aCount]>>Huffman::KMaxCodeLength);
1.900 + TInt v=-1;
1.901 + TRAPD(r,v=in.HuffmanL(aDecode));
1.902 + test (r==KErrNone);
1.903 + test (v==aCount+aBase);
1.904 + TRAP(r,in.ReadL());
1.905 + test (r==KErrUnderflow);
1.906 + }
1.907 + }
1.908 + }
1.909 +
1.910 +TInt TestExternalizeL(const TUint32* aCode, TUint8* aExtern, TUint32* aIntern, TInt aCount)
1.911 + {
1.912 + TBitOutput out(aExtern,aCount*4);
1.913 + Huffman::ExternalizeL(out,aCode,aCount);
1.914 + TInt bits=out.BufferedBits()+8*(out.Ptr()-aExtern);
1.915 + out.PadL(0);
1.916 + TBitInput in(aExtern,bits);
1.917 + TRAPD(r,Huffman::InternalizeL(in,aIntern,aCount));
1.918 + test (r == KErrNone);
1.919 + test (Mem::Compare((TUint8*)aCode,aCount*sizeof(TUint32),(TUint8*)aIntern,aCount*sizeof(TUint32)) == 0);
1.920 + TRAP(r,in.ReadL());
1.921 + test (r == KErrUnderflow);
1.922 + return bits;
1.923 + }
1.924 +
1.925 +void RandomHuffmanL(TInt aIter, TInt aMaxSymbols)
1.926 +//
1.927 +// generate random frequency distributions and verify
1.928 +// (a) the Huffman generator creates a mathematically 'optimal code'
1.929 +// (b) the canonical encoding is the canonical encoding
1.930 +// (c) the decoding tree correctly decodes each code.
1.931 +// (d) the encoding can be correctly externalised and internalised
1.932 +//
1.933 + {
1.934 + TReal KLog2;
1.935 + Math::Ln(KLog2,2);
1.936 + const TInt KTotalFreqLog2=24;
1.937 + const TInt KTotalFreq=1<<KTotalFreqLog2;
1.938 +
1.939 + while (--aIter >= 0)
1.940 + {
1.941 + TInt num=2+Random(aMaxSymbols-1);
1.942 +
1.943 + TUint32* const freq = new(ELeave) TUint32[num*3];
1.944 + CleanupArrayDeletePushL(freq);
1.945 + TUint32* const code = freq+num;
1.946 + TUint32* const encoding = code+num;
1.947 + TUint32* const decoding = freq;
1.948 + TUint8* const exter = (TUint8*)encoding;
1.949 + TUint32* const intern = freq;
1.950 +
1.951 + TInt var=Random(24);
1.952 + TInt zero=Random(num-2);
1.953 + GenerateFreq(freq,num,KTotalFreq,var,zero);
1.954 +
1.955 + Huffman::HuffmanL(freq,num,code);
1.956 + VerifyOptimalCode(freq,code,num,KTotalFreqLog2);
1.957 +
1.958 + Huffman::Encoding(code,num,encoding);
1.959 + VerifyCanonicalEncodingL(code,encoding,num);
1.960 +
1.961 + TInt base=Random(Huffman::KMaxCodes-num);
1.962 + Huffman::Decoding(code,num,decoding,base);
1.963 + VerifyCanonicalDecoding(encoding,decoding,num,base);
1.964 +
1.965 + TestExternalizeL(code,exter,intern,num);
1.966 + CleanupStack::PopAndDestroy();
1.967 + }
1.968 + }
1.969 +
1.970 +///
1.971 +
1.972 +void MainL()
1.973 + {
1.974 + test.Start(_L("Test Bit reader"));
1.975 + TestBitReading();
1.976 + test.Next(_L("Test Bit writer"));
1.977 + TestBitWriting();
1.978 + test.Next(_L("Test Huffman decoder"));
1.979 + TestHuffmanL();
1.980 + test.Next(_L("Test Huffman generator for known distributions"));
1.981 + SpecificHuffman(800);
1.982 + test.Next(_L("Test Huffman generator for random distributions"));
1.983 + TRAPD(r,RandomHuffmanL(1000,800));
1.984 + test (r==KErrNone);
1.985 + test.End();
1.986 + }
1.987 +
1.988 +TInt E32Main()
1.989 + {
1.990 + test.Title();
1.991 + CTrapCleanup* c=CTrapCleanup::New();
1.992 + test (c!=0);
1.993 + TRAPD(r,MainL());
1.994 + test (r==KErrNone);
1.995 + delete c;
1.996 + test.Close();
1.997 + return r;
1.998 + }