1 /*

     2 * Copyright (c) 1998-2009 Nokia Corporation and/or its subsidiary(-ies).

     3 * All rights reserved.

     4 * This component and the accompanying materials are made available

     5 * under the terms of the License "Eclipse Public License v1.0"

     6 * which accompanies this distribution, and is available

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

     8 *

     9 * Initial Contributors:

    10 * Nokia Corporation - initial contribution.

    11 *

    12 * Contributors:

    13 *

    14 * Description: 

    15 * e32tools\petran\Szip\decode.cpp

    16 *

    17 */

    18 

    19 

    20 #include "huffman.h"

    21 #include "panic.h"

    22 #include <cpudefs.h>

    23 #include "h_utl.h"

    24 #include "farray.h"

    25 

    26 

    27 const TInt KHuffTerminate=0x0001;

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

    29 

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

    31 //

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

    33 //

    34 	{

    35 	TUint32* l=*aLevel++;

    36 	if (l>aValue)

    37 		{

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

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

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

    41 		*--aPtr=KBranch1|branch0;

    42 		}

    43 	else if (l==aValue)

    44 		{

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

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

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

    48 		}

    49 	else	// l<iNext

    50 		{

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

    52 		TUint term1=*aValue--;

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

    54 		}

    55 	return aPtr;

    56 	}

    57 

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

    59 /** Create a canonical Huffman decoding tree

    60 

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

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

    63 	and must represent a valid huffman code.

    64 	

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

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

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

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

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

    70 		this is zero.

    71 

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

    73 

    74 	@see IsValid()

    75 	@see HuffmanL()

    76 */

    77 	{

    78 	if(!IsValid(aHuffman,aNumCodes))

    79 		Panic(EHuffmanInvalidCoding);

    80 //

    81 	TFixedArray<TInt,KMaxCodeLength> counts;

    82 	counts.Reset();

    83 	TInt codes=0;

    84 	TInt ii;

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

    86 		{

    87 		TInt len=aHuffman[ii];

    88 		aDecodeTree[ii]=len;

    89 		if (--len>=0)

    90 			{

    91 			++counts[len];

    92 			++codes;

    93 			}

    94 		}

    95 //

    96 	TFixedArray<TUint32*,KMaxCodeLength> level;

    97 	TUint32* lit=aDecodeTree+codes;

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

    99 		{

   100 		level[ii]=lit;

   101 		lit-=counts[ii];

   102 		}

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

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

   105 		{

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

   107 		if (len)

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

   109 		}

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

   111 		{

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

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

   114 		}

   115 	else if (codes>1)

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

   117 	}

   118 

   119 // The decoding tree for the externalised code

   120 const TUint32 HuffmanDecoding[]=

   121 	{

   122 	0x0004006c,

   123 	0x00040064,

   124 	0x0004005c,

   125 	0x00040050,

   126 	0x00040044,

   127 	0x0004003c,

   128 	0x00040034,

   129 	0x00040021,

   130 	0x00040023,

   131 	0x00040025,

   132 	0x00040027,

   133 	0x00040029,

   134 	0x00040014,

   135 	0x0004000c,

   136 	0x00040035,

   137 	0x00390037,

   138 	0x00330031,

   139 	0x0004002b,

   140 	0x002f002d,

   141 	0x001f001d,

   142 	0x001b0019,

   143 	0x00040013,

   144 	0x00170015,

   145 	0x0004000d,

   146 	0x0011000f,

   147 	0x000b0009,

   148 	0x00070003,

   149 	0x00050001

   150 	};

   151 

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

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

   154 

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

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

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

   158 	

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

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

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

   162 

   163 	@leave "TBitInput::HuffmanL()"

   164 

   165 	@see ExternalizeL()

   166 */

   167 // See ExternalizeL for a description of the format

   168 	{

   169 	// initialise move-to-front list

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

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

   172 		list[i]=TUint8(i);

   173 	TInt last=0;

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

   175 	TUint32* p=aHuffman;

   176 	const TUint32* end=aHuffman+aNumCodes;

   177 	TInt rl=0;

   178 	while (p+rl<end)

   179 		{

   180 		TInt c=aInput.HuffmanL(HuffmanDecoding);

   181 		if (c<2)

   182 			{

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

   184 			// update he run-length

   185 			rl+=rl+c+1;

   186 			}

   187 		else

   188 			{

   189 			while (rl>0)

   190 				{

   191 				if (p>end)

   192 					{

   193 					Panic(EHuffmanCorruptFile);

   194 					}

   195 				*p++=last;

   196 				--rl;

   197 				}

   198 			--c;

   199 			list[0]=TUint8(last);

   200 			last=list[c];

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

   202 			if (p>end)

   203 				{

   204 				Panic(EHuffmanCorruptFile);

   205 				}

   206 			*p++=last;

   207 			}

   208 		}

   209 	while (rl>0)

   210 		{

   211 		if (p>end)

   212 			{

   213 			Panic(EHuffmanCorruptFile);

   214 			}

   215 		*p++=last;

   216 		--rl;

   217 		}

   218 	}

   219 

   220 // bit-stream input class

   221 

   222 inline TUint reverse(TUint aVal)

   223 //

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

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

   226 //

   227 	{

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

   229 	v^=aVal;

   230 	v&=0xff00ffff;

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

   232 	return aVal^(v>>8);

   233 	}

   234 

   235 TBitInput::TBitInput()

   236 /** Construct a bit stream input object

   237 

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

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

   240 */

   241 	:iCount(0),iRemain(0)

   242 	{}

   243 

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

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

   246 

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

   248 	the specified buffer.

   249 

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

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

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

   253 */

   254 	{

   255 	Set(aPtr,aLength,aOffset);

   256 	}

   257 

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

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

   260 

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

   262 	UnderflowL() will be called.

   263 	

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

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

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

   267 */

   268 	{

   269 	TUint p=(TUint)aPtr;

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

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

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

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

   274 	if (aLength==0)

   275 		iCount=0;

   276 	else

   277 		{

   278 		// read the first few bits of the stream

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

   280 		aOffset=32-aOffset;

   281 		aLength-=aOffset;

   282 		if (aLength<0)

   283 			aOffset+=aLength;

   284 		iCount=aOffset;

   285 		}

   286 	iRemain=aLength;

   287 	iPtr=ptr;

   288 	}

   289 

   290 #ifndef __HUFFMAN_MACHINE_CODED__

   291 

   292 TUint TBitInput::ReadL()

   293 /** Read a single bit from the input

   294 

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

   296 	there are no more bits available.

   297 

   298 	@return The next bit in the stream

   299 

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

   301 		to get more data

   302 */

   303 	{

   304 	TInt c=iCount;

   305 	TUint bits=iBits;

   306 	if (--c<0)

   307 		return ReadL(1);

   308 	iCount=c;

   309 	iBits=bits<<1;

   310 	return bits>>31;

   311 	}

   312 

   313 TUint TBitInput::ReadL(TInt aSize)

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

   315 

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

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

   318 	zero extended to return a 32-bit result.

   319 

   320 	A read of zero bits will always reaturn zero.

   321 	

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

   323 

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

   325 

   326 	@return The bits read from the stream

   327 

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

   329 		to get more data

   330 */

   331 	{

   332 	if (!aSize)

   333 		return 0;

   334 	TUint val=0;

   335 	TUint bits=iBits;

   336 	iCount-=aSize;

   337 	while (iCount<0)

   338 		{

   339 		// need more bits

   340 #ifdef __CPU_X86

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

   342 		if (iCount+aSize!=0)

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

   344 #else

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

   346 #endif

   347 		aSize=-iCount;	// bits still required

   348 		if (iRemain>0)

   349 			{

   350 			bits=reverse(*iPtr++);

   351 			iCount+=32;

   352 			iRemain-=32;

   353 			if (iRemain<0)

   354 				iCount+=iRemain;

   355 			}

   356 		else

   357 			{

   358 			UnderflowL();

   359 			bits=iBits;

   360 			iCount-=aSize;

   361 			}

   362 		}

   363 #ifdef __CPU_X86

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

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

   366 #else

   367 	iBits=bits<<aSize;

   368 #endif

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

   370 	}

   371 

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

   373 /** Read and decode a Huffman Code

   374 

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

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

   377 

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

   379 

   380 	@return The symbol that was decoded

   381 	

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

   383 		to get more data

   384 */

   385 	{

   386 	TUint huff=0;

   387 	do

   388 		{

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

   390 		huff=*aTree;

   391 		if (ReadL()==0)

   392 			huff<<=16;

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

   394 	return huff>>17;

   395 	}

   396 

   397 #endif

   398 

   399 void TBitInput::UnderflowL()

   400 /** Handle an empty input buffer

   401 

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

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

   404 	data using Set().

   405 

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

   407 	(for example) before reseting the input buffer.

   408 

   409 	@leave "KErrUnderflow" The default implementation leaves

   410 */

   411 	{

   412 	Panic(EHuffmanBufferOverflow);

   413 	}

   414