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 "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 // e32tools\petran\Szip\decode.cpp

    15 // 

    16 //

    17 

    18 #include "huffman.h"

    19 #include "panic.h"

    20 #include <cpudefs.h>

    21 #include "h_utl.h"

    22 #include "farray.h"

    23 

    24 

    25 const TInt KHuffTerminate=0x0001;

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

    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 void Huffman::Decoding(const TUint32 aHuffman[],TInt aNumCodes,TUint32 aDecodeTree[],TInt aSymbolBase)

    57 /** Create a canonical Huffman decoding tree

    58 

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

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

    61 	and must represent a valid huffman code.

    62 	

    63 	@param "const TUint32 aHuffman[]" The table of code lengths as generated by Huffman::HuffmanL()

    64 	@param "TInt aNumCodes" The number of codes in the table

    65 	@param "TUint32 aDecodeTree[]" The space for the decoding tree. This must be the same

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

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

    68 		this is zero.

    69 

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

    71 

    72 	@see IsValid()

    73 	@see HuffmanL()

    74 */

    75 	{

    76 	if(!IsValid(aHuffman,aNumCodes))

    77 		Panic(EHuffmanInvalidCoding);

    78 //

    79 	TFixedArray<TInt,KMaxCodeLength> counts;

    80 	counts.Reset();

    81 	TInt codes=0;

    82 	TInt ii;

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

    84 		{

    85 		TInt len=aHuffman[ii];

    86 		aDecodeTree[ii]=len;

    87 		if (--len>=0)

    88 			{

    89 			++counts[len];

    90 			++codes;

    91 			}

    92 		}

    93 //

    94 	TFixedArray<TUint32*,KMaxCodeLength> level;

    95 	TUint32* lit=aDecodeTree+codes;

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

    97 		{

    98 		level[ii]=lit;

    99 		lit-=counts[ii];

   100 		}

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

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

   103 		{

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

   105 		if (len)

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

   107 		}

   108 	if (codes==1)	// codes==1 special case: the tree is not complete

   109 		{

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

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

   112 		}

   113 	else if (codes>1)

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

   115 	}

   116 

   117 // The decoding tree for the externalised code

   118 const TUint32 HuffmanDecoding[]=

   119 	{

   120 	0x0004006c,

   121 	0x00040064,

   122 	0x0004005c,

   123 	0x00040050,

   124 	0x00040044,

   125 	0x0004003c,

   126 	0x00040034,

   127 	0x00040021,

   128 	0x00040023,

   129 	0x00040025,

   130 	0x00040027,

   131 	0x00040029,

   132 	0x00040014,

   133 	0x0004000c,

   134 	0x00040035,

   135 	0x00390037,

   136 	0x00330031,

   137 	0x0004002b,

   138 	0x002f002d,

   139 	0x001f001d,

   140 	0x001b0019,

   141 	0x00040013,

   142 	0x00170015,

   143 	0x0004000d,

   144 	0x0011000f,

   145 	0x000b0009,

   146 	0x00070003,

   147 	0x00050001

   148 	};

   149 

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

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

   152 

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

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

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

   156 	

   157 	@param "TBitInput& aInput" The input stream with the encoding

   158 	@param "TUint32 aHuffman[]" The internalized code-length table is placed here

   159 	@param "TInt aNumCodes" The number of huffman codes in the table

   160 

   161 	@leave "TBitInput::HuffmanL()"

   162 

   163 	@see ExternalizeL()

   164 */

   165 // See ExternalizeL for a description of the format

   166 	{

   167 	// initialise move-to-front list

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

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

   170 		list[i]=TUint8(i);

   171 	TInt last=0;

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

   173 	TUint32* p=aHuffman;

   174 	const TUint32* end=aHuffman+aNumCodes;

   175 	TInt rl=0;

   176 	while (p+rl<end)

   177 		{

   178 		TInt c=aInput.HuffmanL(HuffmanDecoding);

   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 			while (rl>0)

   188 				{

   189 				if (p>end)

   190 					{

   191 					Panic(EHuffmanCorruptFile);

   192 					}

   193 				*p++=last;

   194 				--rl;

   195 				}

   196 			--c;

   197 			list[0]=TUint8(last);

   198 			last=list[c];

   199 			HMem::Copy(&list[1],&list[0],c);

   200 			if (p>end)

   201 				{

   202 				Panic(EHuffmanCorruptFile);

   203 				}

   204 			*p++=last;

   205 			}

   206 		}

   207 	while (rl>0)

   208 		{

   209 		if (p>end)

   210 			{

   211 			Panic(EHuffmanCorruptFile);

   212 			}

   213 		*p++=last;

   214 		--rl;

   215 		}

   216 	}

   217 

   218 // bit-stream input class

   219 

   220 inline TUint reverse(TUint aVal)

   221 //

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

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

   224 //

   225 	{

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

   227 	v^=aVal;

   228 	v&=0xff00ffff;

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

   230 	return aVal^(v>>8);

   231 	}

   232 

   233 TBitInput::TBitInput()

   234 /** Construct a bit stream input object

   235 

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

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

   238 */

   239 	:iCount(0),iRemain(0)

   240 	{}

   241 

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

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

   244 

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

   246 	the specified buffer.

   247 

   248 	@param "const TUint8* aPtr" The address of the buffer containing the bit stream

   249 	@param "TInt aLength" The length of the bitstream in bits

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

   251 */

   252 	{

   253 	Set(aPtr,aLength,aOffset);

   254 	}

   255 

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

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

   258 

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

   260 	UnderflowL() will be called.

   261 	

   262 	@param "const TUint8* aPtr" The address of the buffer containing the bit stream

   263 	@param "TInt aLength" The length of the bitstream in bits

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

   265 */

   266 	{

   267 	TUint p=(TUint)aPtr;

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

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

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

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

   272 	if (aLength==0)

   273 		iCount=0;

   274 	else

   275 		{

   276 		// read the first few bits of the stream

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

   278 		aOffset=32-aOffset;

   279 		aLength-=aOffset;

   280 		if (aLength<0)

   281 			aOffset+=aLength;

   282 		iCount=aOffset;

   283 		}

   284 	iRemain=aLength;

   285 	iPtr=ptr;

   286 	}

   287 

   288 #ifndef __HUFFMAN_MACHINE_CODED__

   289 

   290 TUint TBitInput::ReadL()

   291 /** Read a single bit from the input

   292 

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

   294 	there are no more bits available.

   295 

   296 	@return The next bit in the stream

   297 

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

   299 		to get more data

   300 */

   301 	{

   302 	TInt c=iCount;

   303 	TUint bits=iBits;

   304 	if (--c<0)

   305 		return ReadL(1);

   306 	iCount=c;

   307 	iBits=bits<<1;

   308 	return bits>>31;

   309 	}

   310 

   311 TUint TBitInput::ReadL(TInt aSize)

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

   313 

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

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

   316 	zero extended to return a 32-bit result.

   317 

   318 	A read of zero bits will always reaturn zero.

   319 	

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

   321 

   322 	@param "TInt aSize" The number of bits to read

   323 

   324 	@return The bits read from the stream

   325 

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

   327 		to get more data

   328 */

   329 	{

   330 	if (!aSize)

   331 		return 0;

   332 	TUint val=0;

   333 	TUint bits=iBits;

   334 	iCount-=aSize;

   335 	while (iCount<0)

   336 		{

   337 		// need more bits

   338 #ifdef __CPU_X86

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

   340 		if (iCount+aSize!=0)

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

   342 #else

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

   344 #endif

   345 		aSize=-iCount;	// bits still required

   346 		if (iRemain>0)

   347 			{

   348 			bits=reverse(*iPtr++);

   349 			iCount+=32;

   350 			iRemain-=32;

   351 			if (iRemain<0)

   352 				iCount+=iRemain;

   353 			}

   354 		else

   355 			{

   356 			UnderflowL();

   357 			bits=iBits;

   358 			iCount-=aSize;

   359 			}

   360 		}

   361 #ifdef __CPU_X86

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

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

   364 #else

   365 	iBits=bits<<aSize;

   366 #endif

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

   368 	}

   369 

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

   371 /** Read and decode a Huffman Code

   372 

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

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

   375 

   376 	@param "const TUint32* aTree" The huffman decoding tree

   377 

   378 	@return The symbol that was decoded

   379 	

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

   381 		to get more data

   382 */

   383 	{

   384 	TUint huff=0;

   385 	do

   386 		{

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

   388 		huff=*aTree;

   389 		if (ReadL()==0)

   390 			huff<<=16;

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

   392 	return huff>>17;

   393 	}

   394 

   395 #endif

   396 

   397 void TBitInput::UnderflowL()

   398 /** Handle an empty input buffer

   399 

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

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

   402 	data using Set().

   403 

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

   405 	(for example) before reseting the input buffer.

   406 

   407 	@leave "KErrUnderflow" The default implementation leaves

   408 */

   409 	{

   410 	Panic(EHuffmanBufferOverflow);

   411 	}

   412