1 // Copyright (c) 1998-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 "Symbian Foundation License v1.0"

     5 // which accompanies this distribution, and is available

     6 // at the URL "http://www.symbianfoundation.org/legal/sfl-v10.html".

     7 //

     8 // Initial Contributors:

     9 // Nokia Corporation - initial contribution.

    10 //

    11 // Contributors:

    12 //

    13 // Description:

    14 // e32\euser\us_decode.cpp

    15 // 

    16 //

    17 

    18 #include <e32huffman.h>

    19 #include <e32base.h>

    20 #include <e32panic.h>

    21 #include <cpudefs.h>

    22 

    23 const TInt KHuffTerminate=0x0001;

    24 const TUint32 KBranch1=sizeof(TUint32)<<16;

    25 _LIT(KCat,"Huffman");

    26 

    27 TUint32* HuffmanSubTree(TUint32* aPtr,const TUint32* aValue,TUint32** aLevel)

    28 //

    29 // write the subtree below aPtr and return the head

    30 //

    31 	{

    32 	TUint32* l=*aLevel++;

    33 	if (l>aValue)

    34 		{

    35 		TUint32* sub0=HuffmanSubTree(aPtr,aValue,aLevel);	// 0-tree first

    36 		aPtr=HuffmanSubTree(sub0,aValue-(aPtr-sub0)-1,aLevel);			// 1-tree

    37 		TInt branch0=(TUint8*)sub0-(TUint8*)(aPtr-1);

    38 		*--aPtr=KBranch1|branch0;

    39 		}

    40 	else if (l==aValue)

    41 		{

    42 		TUint term0=*aValue--;						// 0-term

    43 		aPtr=HuffmanSubTree(aPtr,aValue,aLevel);			// 1-tree

    44 		*--aPtr=KBranch1|(term0>>16);

    45 		}

    46 	else	// l<iNext

    47 		{

    48 		TUint term0=*aValue--;						// 0-term

    49 		TUint term1=*aValue--;

    50 		*--aPtr=(term1>>16<<16)|(term0>>16);

    51 		}

    52 	return aPtr;

    53 	}

    54 

    55 /** Create a canonical Huffman decoding tree

    56 

    57 	This generates the huffman decoding tree used by TBitInput::HuffmanL() to read huffman

    58 	encoded data. The input is table of code lengths, as generated by Huffman::HuffmanL()

    59 	and must represent a valid huffman code.

    60 	

    61 	@param aHuffman The table of code lengths as generated by Huffman::HuffmanL()

    62 	@param aNumCodes The number of codes in the table

    63 	@param aDecodeTree The space for the decoding tree. This must be the same

    64 		size as the code-length table, and can safely be the same memory

    65 	@param  aSymbolBase the base value for the output 'symbols' from the decoding tree, by default

    66 		this is zero.

    67 

    68 	@panic "USER ???" If the provided code is not a valid Huffman coding

    69 

    70 	@see IsValid()

    71 	@see HuffmanL()

    72 */

    73 EXPORT_C void Huffman::Decoding(const TUint32 aHuffman[],TInt aNumCodes,TUint32 aDecodeTree[],TInt aSymbolBase)

    74 	{

    75 	__ASSERT_ALWAYS(IsValid(aHuffman,aNumCodes),User::Panic(KCat,EHuffmanInvalidCoding));

    76 //

    77 	TFixedArray<TInt,KMaxCodeLength> counts;

    78 	counts.Reset();

    79 	TInt codes=0;

    80 	TInt ii;

    81 	for (ii=0;ii<aNumCodes;++ii)

    82 		{

    83 		TInt len=aHuffman[ii];

    84 		aDecodeTree[ii]=len;

    85 		if (--len>=0)

    86 			{

    87 			++counts[len];

    88 			++codes;

    89 			}

    90 		}

    91 //

    92 	TFixedArray<TUint32*,KMaxCodeLength> level;

    93 	TUint32* lit=aDecodeTree+codes;

    94 	for (ii=0;ii<KMaxCodeLength;++ii)

    95 		{

    96 		level[ii]=lit;

    97 		lit-=counts[ii];

    98 		}

    99 	aSymbolBase=(aSymbolBase<<17)+(KHuffTerminate<<16);

   100 	for (ii=0;ii<aNumCodes;++ii)

   101 		{

   102 		TUint len=TUint8(aDecodeTree[ii]);

   103 		if (len)

   104 			*--level[len-1]|=(ii<<17)+aSymbolBase;

   105 		}

   106 	if (codes==1)	// codes==1 special case: incomplete tree

   107 		{

   108 		TUint term=aDecodeTree[0]>>16;

   109 		aDecodeTree[0]=term|(term<<16); // 0- and 1-terminate at root

   110 		}

   111 	else if (codes>1)

   112 		HuffmanSubTree(aDecodeTree+codes-1,aDecodeTree+codes-1,&level[0]);

   113 	}

   114 

   115 // The decoding tree for the externalised code

   116 const TUint32 HuffmanDecoding[]=

   117 	{

   118 	0x0004006c,

   119 	0x00040064,

   120 	0x0004005c,

   121 	0x00040050,

   122 	0x00040044,

   123 	0x0004003c,

   124 	0x00040034,

   125 	0x00040021,

   126 	0x00040023,

   127 	0x00040025,

   128 	0x00040027,

   129 	0x00040029,

   130 	0x00040014,

   131 	0x0004000c,

   132 	0x00040035,

   133 	0x00390037,

   134 	0x00330031,

   135 	0x0004002b,

   136 	0x002f002d,

   137 	0x001f001d,

   138 	0x001b0019,

   139 	0x00040013,

   140 	0x00170015,

   141 	0x0004000d,

   142 	0x0011000f,

   143 	0x000b0009,

   144 	0x00070003,

   145 	0x00050001

   146 	};

   147 

   148 /** Restore a canonical huffman encoding from a bit stream

   149 

   150 	The encoding must have been stored using Huffman::ExternalizeL(). The resulting

   151 	code-length table can be used to create an encoding table using Huffman::Encoding()

   152 	or a decoding tree using Huffman::Decoding().

   153 	

   154 	@param aInput The input stream with the encoding

   155 	@param aHuffman The internalized code-length table is placed here

   156 	@param aNumCodes The number of huffman codes in the table

   157 

   158 	@leave TBitInput::HuffmanL()

   159 

   160 	@see ExternalizeL()

   161 */

   162 EXPORT_C void Huffman::InternalizeL(TBitInput& aInput,TUint32 aHuffman[],TInt aNumCodes)

   163 // See ExternalizeL for a description of the format

   164 	{

   165 	// initialise move-to-front list

   166 	TFixedArray<TUint8,Huffman::KMetaCodes> list;

   167 	for (TInt i=0;i<list.Count();++i)

   168 		list[i]=TUint8(i);

   169 	TInt last=0;

   170 	// extract codes, reverse rle-0 and mtf encoding in one pass

   171 	TUint32* p=aHuffman;

   172 	const TUint32* end=aHuffman+aNumCodes;

   173 	TUint rl=0;

   174 	while (p+rl<end)

   175 		{

   176 		TInt c=aInput.HuffmanL(HuffmanDecoding);

   177 		// c is now 0..28

   178 		if (c<2)

   179 			{

   180 			// one of the zero codes used by RLE-0

   181 			// update he run-length

   182 			rl+=rl+c+1;

   183 			}

   184 		else

   185 			{

   186 			if(rl >= TUint(end-p))

   187 				User::Leave(KErrCorrupt);

   188 			while (rl>0)

   189 				{

   190 				*p++=last;

   191 				--rl;

   192 				}

   193 			--c; // c is now 1..27

   194 			list[0]=TUint8(last);

   195 			last=list[c];

   196 			Mem::Copy(&list[1],&list[0],c);

   197 			*p++=last;

   198 			}

   199 		}

   200 

   201 	while (p<end)

   202 		*p++=last;

   203 

   204 	}

   205 

   206 // bit-stream input class

   207 

   208 inline TUint reverse(TUint aVal)

   209 //

   210 // Reverse the byte-order of a 32 bit value

   211 // This generates optimal ARM code (4 instructions)

   212 //

   213 	{

   214 	TUint v=(aVal<<16)|(aVal>>16);

   215 	v^=aVal;

   216 	v&=0xff00ffff;

   217 	aVal=(aVal>>8)|(aVal<<24);

   218 	return aVal^(v>>8);

   219 	}

   220 

   221 /** Construct a bit stream input object

   222 

   223 	Following construction the bit stream is ready for reading bits, but will

   224 	immediately call UnderflowL() as the input buffer is empty.

   225 */

   226 EXPORT_C TBitInput::TBitInput()

   227 	:iCount(0),iRemain(0)

   228 	{}

   229 

   230 /** Construct a bit stream input object over a buffer

   231 

   232 	Following construction the bit stream is ready for reading bits from

   233 	the specified buffer.

   234 

   235 	@param aPtr The address of the buffer containing the bit stream

   236 	@param aLength The length of the bitstream in bits

   237 	@param aOffset The bit offset from the start of the buffer to the bit stream (defaults to zero)

   238 */

   239 EXPORT_C TBitInput::TBitInput(const TUint8* aPtr, TInt aLength, TInt aOffset)

   240 	{

   241 	Set(aPtr,aLength,aOffset);

   242 	}

   243 

   244 /** Set the memory buffer to use for input

   245 

   246 	Bits will be read from this buffer until it is empty, at which point

   247 	UnderflowL() will be called.

   248 	

   249 	@param aPtr The address of the buffer containing the bit stream

   250 	@param aLength The length of the bitstream in bits

   251 	@param aOffset The bit offset from the start of the buffer to the bit stream (defaults to zero)

   252 */

   253 EXPORT_C void TBitInput::Set(const TUint8* aPtr, TInt aLength, TInt aOffset)

   254 	{

   255 	TUint p=(TUint)aPtr;

   256 	p+=aOffset>>3;			// nearest byte to the specified bit offset

   257 	aOffset&=7;				// bit offset within the byte

   258 	const TUint32* ptr=(const TUint32*)(p&~3);	// word containing this byte

   259 	aOffset+=(p&3)<<3;		// bit offset within the word

   260 	if (aLength==0)

   261 		iCount=0;

   262 	else

   263 		{

   264 		// read the first few bits of the stream

   265 		iBits=reverse(*ptr++)<<aOffset;

   266 		aOffset=32-aOffset;

   267 		aLength-=aOffset;

   268 		if (aLength<0)

   269 			aOffset+=aLength;

   270 		iCount=aOffset;

   271 		}

   272 	iRemain=aLength;

   273 	iPtr=ptr;

   274 	}

   275 

   276 #ifndef __HUFFMAN_MACHINE_CODED__

   277 

   278 /** Read a single bit from the input

   279 

   280 	Return the next bit in the input stream. This will call UnderflowL() if

   281 	there are no more bits available.

   282 

   283 	@return The next bit in the stream

   284 

   285 	@leave "UnderflowL()" It the bit stream is exhausted more UnderflowL is called

   286 		to get more data

   287 */

   288 EXPORT_C TUint TBitInput::ReadL()

   289 	{

   290 	TInt c=iCount;

   291 	TUint bits=iBits;

   292 	if (--c<0)

   293 		return ReadL(1);

   294 	iCount=c;

   295 	iBits=bits<<1;

   296 	return bits>>31;

   297 	}

   298 

   299 /** Read a multi-bit value from the input

   300 

   301 	Return the next few bits as an unsigned integer. The last bit read is

   302 	the least significant bit of the returned value, and the value is

   303 	zero extended to return a 32-bit result.

   304 

   305 	A read of zero bits will always reaturn zero.

   306 	

   307 	This will call UnderflowL() if there are not enough bits available.

   308 

   309 	@param aSize The number of bits to read

   310 

   311 	@return The bits read from the stream

   312 

   313 	@leave "UnderflowL()" It the bit stream is exhausted more UnderflowL is called

   314 		to get more data

   315 */

   316 EXPORT_C TUint TBitInput::ReadL(TInt aSize)

   317 	{

   318 	if (!aSize)

   319 		return 0;

   320 	TUint val=0;

   321 	TUint bits=iBits;

   322 	iCount-=aSize;

   323 	while (iCount<0)

   324 		{

   325 		// need more bits

   326 #ifdef __CPU_X86

   327 		// X86 does not allow shift-by-32

   328 		if (iCount+aSize!=0)

   329 			val|=bits>>(32-(iCount+aSize))<<(-iCount);	// scrub low order bits

   330 #else

   331 		val|=bits>>(32-(iCount+aSize))<<(-iCount);	// scrub low order bits

   332 #endif

   333 		aSize=-iCount;	// bits still required

   334 		if (iRemain>0)

   335 			{

   336 			bits=reverse(*iPtr++);

   337 			iCount+=32;

   338 			iRemain-=32;

   339 			if (iRemain<0)

   340 				iCount+=iRemain;

   341 			}

   342 		else

   343 			{

   344 			UnderflowL();

   345 			bits=iBits;

   346 			iCount-=aSize;

   347 			}

   348 		}

   349 #ifdef __CPU_X86

   350 	// X86 does not allow shift-by-32

   351 	iBits=aSize==32?0:bits<<aSize;

   352 #else

   353 	iBits=bits<<aSize;

   354 #endif

   355 	return val|(bits>>(32-aSize));

   356 	}

   357 

   358 /** Read and decode a Huffman Code

   359 

   360 	Interpret the next bits in the input as a Huffman code in the specified

   361 	decoding. The decoding tree should be the output from Huffman::Decoding().

   362 

   363 	@param aTree The huffman decoding tree

   364 

   365 	@return The symbol that was decoded

   366 	

   367 	@leave "UnderflowL()" It the bit stream is exhausted more UnderflowL is called

   368 		to get more data

   369 */

   370 EXPORT_C TUint TBitInput::HuffmanL(const TUint32* aTree)

   371 	{

   372 	TUint huff=0;

   373 	do

   374 		{

   375 		aTree=PtrAdd(aTree,huff>>16);

   376 		huff=*aTree;

   377 		if (ReadL()==0)

   378 			huff<<=16;

   379 		} while ((huff&0x10000u)==0);

   380 	return huff>>17;

   381 	}

   382 

   383 #endif

   384 

   385 /** Handle an empty input buffer

   386 

   387 	This virtual function is called when the input buffer is empty and

   388 	more bits are required. It should reset the input buffer with more

   389 	data using Set().

   390 

   391 	A derived class can replace this to read the data from a file

   392 	(for example) before reseting the input buffer.

   393 

   394 	@leave KErrUnderflow The default implementation leaves

   395 */

   396 void TBitInput::UnderflowL()

   397 	{

   398 	User::Leave(KErrUnderflow);

   399 	}