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 "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 // e32\euser\us_decode.cpp

    15 // 

    16 //

    17 

    18 #include "e32huffman.h"

    19 #include <e32base.h>

    20 #include <e32base_private.h>

    21 #include <e32panic.h>

    22 #include <cpudefs.h>

    23 

    24 const TInt KHuffTerminate=0x0001;

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

    26 _LIT(KCat,"Huffman");

    27 

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

    29 //

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

    31 //

    32 	{

    33 	TUint32* l=*aLevel++;

    34 	if (l>aValue)

    35 		{

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

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

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

    39 		*--aPtr=KBranch1|branch0;

    40 		}

    41 	else if (l==aValue)

    42 		{

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

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

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

    46 		}

    47 	else	// l<iNext

    48 		{

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

    50 		TUint term1=*aValue--;

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

    52 		}

    53 	return aPtr;

    54 	}

    55 

    56 /** Create a canonical Huffman decoding tree

    57 

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

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

    60 	and must represent a valid huffman code.

    61 	

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

    63 	@param aNumCodes The number of codes in the table

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

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

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

    67 		this is zero.

    68 

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

    70 

    71 	@see IsValid()

    72 	@see HuffmanL()

    73 */

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

    75 	{

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

    77 //

    78 	TFixedArray<TInt,KMaxCodeLength> counts;

    79 	counts.Reset();

    80 	TInt codes=0;

    81 	TInt ii;

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

    83 		{

    84 		TInt len=aHuffman[ii];

    85 		aDecodeTree[ii]=len;

    86 		if (--len>=0)

    87 			{

    88 			++counts[len];

    89 			++codes;

    90 			}

    91 		}

    92 //

    93 	TFixedArray<TUint32*,KMaxCodeLength> level;

    94 	TUint32* lit=aDecodeTree+codes;

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

    96 		{

    97 		level[ii]=lit;

    98 		lit-=counts[ii];

    99 		}

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

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

   102 		{

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

   104 		if (len)

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

   106 		}

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

   108 		{

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

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

   111 		}

   112 	else if (codes>1)

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

   114 	}

   115 

   116 // The decoding tree for the externalised code

   117 const TUint32 HuffmanDecoding[]=

   118 	{

   119 	0x0004006c,

   120 	0x00040064,

   121 	0x0004005c,

   122 	0x00040050,

   123 	0x00040044,

   124 	0x0004003c,

   125 	0x00040034,

   126 	0x00040021,

   127 	0x00040023,

   128 	0x00040025,

   129 	0x00040027,

   130 	0x00040029,

   131 	0x00040014,

   132 	0x0004000c,

   133 	0x00040035,

   134 	0x00390037,

   135 	0x00330031,

   136 	0x0004002b,

   137 	0x002f002d,

   138 	0x001f001d,

   139 	0x001b0019,

   140 	0x00040013,

   141 	0x00170015,

   142 	0x0004000d,

   143 	0x0011000f,

   144 	0x000b0009,

   145 	0x00070003,

   146 	0x00050001

   147 	};

   148 

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

   150 

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

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

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

   154 	

   155 	@param aInput The input stream with the encoding

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

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

   158 

   159 	@leave TBitInput::HuffmanL()

   160 

   161 	@see ExternalizeL()

   162 */

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

   164 // See ExternalizeL for a description of the format

   165 	{

   166 	// initialise move-to-front list

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

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

   169 		list[i]=TUint8(i);

   170 	TInt last=0;

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

   172 	TUint32* p=aHuffman;

   173 	const TUint32* end=aHuffman+aNumCodes;

   174 	TUint rl=0;

   175 	while (p+rl<end)

   176 		{

   177 		TInt c=aInput.HuffmanL(HuffmanDecoding);

   178 		// c is now 0..28

   179 		if (c<2)

   180 			{

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

   182 			// update he run-length

   183 			rl+=rl+c+1;

   184 			}

   185 		else

   186 			{

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

   188 				User::Leave(KErrCorrupt);

   189 			while (rl>0)

   190 				{

   191 				*p++=last;

   192 				--rl;

   193 				}

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

   195 			list[0]=TUint8(last);

   196 			last=list[c];

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

   198 			*p++=last;

   199 			}

   200 		}

   201 

   202 	while (p<end)

   203 		*p++=last;

   204 

   205 	}

   206 

   207 // bit-stream input class

   208 

   209 inline TUint reverse(TUint aVal)

   210 //

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

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

   213 //

   214 	{

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

   216 	v^=aVal;

   217 	v&=0xff00ffff;

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

   219 	return aVal^(v>>8);

   220 	}

   221 

   222 /** Construct a bit stream input object

   223 

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

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

   226 */

   227 EXPORT_C TBitInput::TBitInput()

   228 	:iCount(0),iRemain(0)

   229 	{}

   230 

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

   232 

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

   234 	the specified buffer.

   235 

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

   237 	@param aLength The length of the bitstream in bits

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

   239 */

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

   241 	{

   242 	Set(aPtr,aLength,aOffset);

   243 	}

   244 

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

   246 

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

   248 	UnderflowL() will be called.

   249 	

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

   251 	@param aLength The length of the bitstream in bits

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

   253 */

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

   255 	{

   256 	TUint p=(TUint)aPtr;

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

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

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

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

   261 	if (aLength==0)

   262 		iCount=0;

   263 	else

   264 		{

   265 		// read the first few bits of the stream

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

   267 		aOffset=32-aOffset;

   268 		aLength-=aOffset;

   269 		if (aLength<0)

   270 			aOffset+=aLength;

   271 		iCount=aOffset;

   272 		}

   273 	iRemain=aLength;

   274 	iPtr=ptr;

   275 	}

   276 

   277 #ifndef __HUFFMAN_MACHINE_CODED__

   278 

   279 /** Read a single bit from the input

   280 

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

   282 	there are no more bits available.

   283 

   284 	@return The next bit in the stream

   285 

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

   287 		to get more data

   288 */

   289 EXPORT_C TUint TBitInput::ReadL()

   290 	{

   291 	TInt c=iCount;

   292 	TUint bits=iBits;

   293 	if (--c<0)

   294 		return ReadL(1);

   295 	iCount=c;

   296 	iBits=bits<<1;

   297 	return bits>>31;

   298 	}

   299 

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

   301 

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

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

   304 	zero extended to return a 32-bit result.

   305 

   306 	A read of zero bits will always reaturn zero.

   307 	

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

   309 

   310 	@param aSize The number of bits to read

   311 

   312 	@return The bits read from the stream

   313 

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

   315 		to get more data

   316 */

   317 EXPORT_C TUint TBitInput::ReadL(TInt aSize)

   318 	{

   319 	if (!aSize)

   320 		return 0;

   321 	TUint val=0;

   322 	TUint bits=iBits;

   323 	iCount-=aSize;

   324 	while (iCount<0)

   325 		{

   326 		// need more bits

   327 #ifdef __CPU_X86

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

   329 		if (iCount+aSize!=0)

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

   331 #else

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

   333 #endif

   334 		aSize=-iCount;	// bits still required

   335 		if (iRemain>0)

   336 			{

   337 			bits=reverse(*iPtr++);

   338 			iCount+=32;

   339 			iRemain-=32;

   340 			if (iRemain<0)

   341 				iCount+=iRemain;

   342 			}

   343 		else

   344 			{

   345 			UnderflowL();

   346 			bits=iBits;

   347 			iCount-=aSize;

   348 			}

   349 		}

   350 #ifdef __CPU_X86

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

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

   353 #else

   354 	iBits=bits<<aSize;

   355 #endif

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

   357 	}

   358 

   359 /** Read and decode a Huffman Code

   360 

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

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

   363 

   364 	@param aTree The huffman decoding tree

   365 

   366 	@return The symbol that was decoded

   367 	

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

   369 		to get more data

   370 */

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

   372 	{

   373 	TUint huff=0;

   374 	do

   375 		{

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

   377 		huff=*aTree;

   378 		if (ReadL()==0)

   379 			huff<<=16;

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

   381 	return huff>>17;

   382 	}

   383 

   384 #endif

   385 

   386 /** Handle an empty input buffer

   387 

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

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

   390 	data using Set().

   391 

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

   393 	(for example) before reseting the input buffer.

   394 

   395 	@leave KErrUnderflow The default implementation leaves

   396 */

   397 void TBitInput::UnderflowL()

   398 	{

   399 	User::Leave(KErrUnderflow);

   400 	}