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\encode.cpp

    16 *

    17 */

    18 

    19 

    20 #include "huffman.h"

    21 #include "panic.h"

    22 #include <e32base.h>

    23 #include <e32base_private.h>

    24 #include "h_utl.h"

    25 #include <assert.h>

    26 #include "farray.h"

    27 #include <stdlib.h>

    28 

    29 void User::Invariant()

    30 	{

    31 	fprintf(stderr, "User::Invariant() called\n");

    32 	exit(1);

    33 	}

    34 

    35 // local definitions used for Huffman code generation

    36 typedef TUint16 THuff;		/** @internal */

    37 const THuff KLeaf=0x8000;	/** @internal */

    38 struct TNode

    39 /** @internal */

    40 	{

    41 	TUint iCount;

    42 	THuff iLeft;

    43 	THuff iRight;

    44 	};

    45 

    46 void HuffmanLengthsL(TUint32* aLengths,const TNode* aNodes,TInt aNode,TInt aLen)

    47 /** recursive function to calculate the code lengths from the node tree

    48 

    49 	@internal

    50 */

    51 	{

    52 	if (++aLen>Huffman::KMaxCodeLength)

    53 		Panic(EHuffmanBufferOverflow);

    54 

    55 	const TNode& node=aNodes[aNode];

    56 	TUint x=node.iLeft;

    57 	if (x&KLeaf)

    58 		aLengths[x&~KLeaf]=aLen;

    59 	else

    60 		HuffmanLengthsL(aLengths,aNodes,x,aLen);

    61 	x=node.iRight;

    62 	if (x&KLeaf)

    63 		aLengths[x&~KLeaf]=aLen;

    64 	else

    65 		HuffmanLengthsL(aLengths,aNodes,x,aLen);

    66 	}

    67 

    68 void InsertInOrder(TNode* aNodes, TInt aSize, TUint aCount, TInt aVal)

    69 /**	Insert the {aCount,aValue} pair into the already sorted array of nodes

    70 

    71 	@internal

    72 */

    73 	{

    74 	// Uses Insertion sort following a binary search...

    75 	TInt l=0, r=aSize;

    76 	while (l < r)

    77 		{

    78 		TInt m = (l+r) >> 1;

    79 		if (aNodes[m].iCount<aCount)

    80 			r=m;

    81 		else

    82 			l=m+1;

    83 		}

    84 	HMem::Copy(aNodes+l+1,aNodes+l,sizeof(TNode)*(aSize-l));

    85 	aNodes[l].iCount=aCount;

    86 	aNodes[l].iRight=TUint16(aVal);

    87 	}

    88 

    89 void Huffman::HuffmanL(const TUint32 aFrequency[],TInt aNumCodes,TUint32 aHuffman[])

    90 /** Generate a Huffman code

    91 

    92 	This generates a Huffman code for a given set of code frequencies. The output

    93 	is a table of code lengths which can be used to build canonincal encoding tables

    94 	or decoding trees for use with the TBitInput and TBitOutput classes.

    95 

    96 	Entries in the table with a frequency of zero will have a zero code length

    97 	and thus no associated huffman encoding. If each such symbol should have a

    98 	maximum length encoding, they must be given at least a frequency of 1.

    99 

   100 	For an alphabet of n symbols, this algorithm has a transient memory overhead

   101 	of 8n, and a time complexity of O(n*log(n)).

   102 

   103 	@param "const TUint32 aFrequency[]" The table of code frequencies

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

   105 	@param "TUint32 aHuffman[]" The table for the output code-length table. This must be

   106 		the same size as the frequency table, and can safely be the same table

   107 

   108 	@leave "KErrNoMemory" If memory used for code generation cannot be allocated

   109 

   110   	@panic "USER ???" If the number of codes exceeds Huffman::KMaxCodes

   111 */

   112 	{

   113 	if(TUint(aNumCodes)>TUint(KMaxCodes))

   114 		Panic(EHuffmanTooManyCodes);

   115 

   116 	// Sort the values into decreasing order of frequency

   117 	//

   118 	TNode* nodes = new TNode[aNumCodes];

   119 	if(nodes==NULL)

   120 		Panic(EHuffmanOutOfMemory);

   121 

   122 	TInt lCount=0;

   123 

   124 	for (TInt ii=0;ii<aNumCodes;++ii)

   125 		{

   126 		TInt c=aFrequency[ii];

   127 		if (c!=0)

   128 			InsertInOrder(nodes,lCount++,c,ii|KLeaf);

   129 		}

   130 

   131 	// default code length is zero

   132 	HMem::FillZ(aHuffman,aNumCodes*sizeof(TUint32));

   133 

   134 	if (lCount==0)

   135 		{

   136 		// no codes with frequency>0. No code has a length

   137 		}

   138 	else if (lCount==1)

   139 		{

   140 		// special case for a single value (always encode as "0")

   141 		aHuffman[nodes[0].iRight&~KLeaf]=1;

   142 		}

   143 	else

   144 		{

   145 		// Huffman algorithm: pair off least frequent nodes and reorder

   146 		//

   147 		do

   148 			{

   149 			--lCount;

   150 			TUint c=nodes[lCount].iCount + nodes[lCount-1].iCount;

   151 			nodes[lCount].iLeft=nodes[lCount-1].iRight;

   152 			// re-order the leaves now to reflect new combined frequency 'c'

   153 			InsertInOrder(nodes,lCount-1,c,lCount);

   154 			} while (lCount>1);

   155 		// generate code lengths in aHuffman[]

   156 		HuffmanLengthsL(aHuffman,nodes,1,0);

   157 		}

   158 

   159 	delete [] nodes;

   160 

   161 	if(!IsValid(aHuffman,aNumCodes))

   162 		Panic(EHuffmanInvalidCoding);

   163 	}

   164 

   165 TBool Huffman::IsValid(const TUint32 aHuffman[],TInt aNumCodes)

   166 /** Validate a Huffman encoding

   167 

   168 	This verifies that a Huffman coding described by the code lengths is valid.

   169 	In particular, it ensures that no code exceeds the maximum length and

   170 	that it is possible to generate a canonical coding for the specified lengths.

   171 	

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

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

   174 

   175 	@return True if the code is valid, otherwise false

   176 */

   177 	{

   178 	// The code is valid if one of the following holds:

   179 	// (a) the code exactly fills the 'code space'

   180 	// (b) there is only a single symbol with code length 1

   181 	// (c) there are no encoded symbols

   182 	//

   183 	TUint remain=1<<KMaxCodeLength;

   184 	TInt totlen=0;

   185 	for (const TUint32* p=aHuffman+aNumCodes; p>aHuffman;)

   186 		{

   187 		TInt len=*--p;

   188 		if (len>0)

   189 			{

   190 			totlen+=len;

   191 			if (len>KMaxCodeLength)

   192 				return EFalse;

   193 			TUint c=1<<(KMaxCodeLength-len);

   194 			if (c>remain)

   195 				return EFalse;

   196 			remain-=c;

   197 			}

   198 		}

   199 

   200 	return remain==0 || totlen<=1;

   201 	}

   202 

   203 void Huffman::Encoding(const TUint32 aHuffman[],TInt aNumCodes,TUint32 aEncodeTable[])

   204 /** Create a canonical Huffman encoding table

   205 

   206 	This generates the huffman codes used by TBitOutput::HuffmanL() to write huffman

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

   208 	and must represent a valid huffman code.

   209 	

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

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

   212 	@param "TUint32 aEncodeTable[]" The table for the output huffman codes. This must be

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

   214 

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

   216 	

   217 	@see IsValid()

   218 	@see HuffmanL()

   219 */

   220 	{

   221 	__ASSERT_ALWAYS(IsValid(aHuffman,aNumCodes),Panic(EHuffmanInvalidCoding));

   222 

   223 	TFixedArray<TInt,KMaxCodeLength> lenCount;

   224 	lenCount.Reset();

   225 

   226 	TInt ii;

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

   228 		{

   229 		TInt len=aHuffman[ii]-1;

   230 		if (len>=0)

   231 			++lenCount[len];

   232 		}

   233 

   234 	TFixedArray<TUint,KMaxCodeLength> nextCode;

   235 	TUint code=0;

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

   237 		{

   238 		code<<=1;

   239 		nextCode[ii]=code;

   240 		code+=lenCount[ii];

   241 		}

   242 

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

   244 		{

   245 		TInt len=aHuffman[ii];

   246 		if (len==0)

   247 			aEncodeTable[ii]=0;

   248 		else

   249 			{

   250 			aEncodeTable[ii] = (nextCode[len-1]<<(KMaxCodeLength-len))|(len<<KMaxCodeLength);

   251 			++nextCode[len-1];

   252 			}

   253 		}

   254 	}

   255 

   256 /** the encoding table for the externalised code

   257 	@internal

   258 */

   259 const TUint32 HuffmanEncoding[]=

   260 	{

   261 	0x10000000,

   262 	0x1c000000,

   263 	0x12000000,

   264 	0x1d000000,

   265 	0x26000000,

   266 	0x26800000,

   267 	0x2f000000,

   268 	0x37400000,

   269 	0x37600000,

   270 	0x37800000,

   271 	0x3fa00000,

   272 	0x3fb00000,

   273 	0x3fc00000,

   274 	0x3fd00000,

   275 	0x47e00000,

   276 	0x47e80000,

   277 	0x47f00000,

   278 	0x4ff80000,

   279 	0x57fc0000,

   280 	0x5ffe0000,

   281 	0x67ff0000,

   282 	0x77ff8000,

   283 	0x7fffa000,

   284 	0x7fffb000,

   285 	0x7fffc000,

   286 	0x7fffd000,

   287 	0x7fffe000,

   288 	0x87fff000,

   289 	0x87fff800

   290 	};

   291 

   292 void EncodeRunLengthL(TBitOutput& aOutput, TInt aLength)

   293 /** encode 0a as '0' and 0b as '1', return number of symbols created

   294 

   295 	@internal

   296 */

   297 	{

   298 	if (aLength>0)

   299 		{

   300 		EncodeRunLengthL(aOutput,(aLength-1)>>1);

   301 		aOutput.HuffmanL(HuffmanEncoding[1-(aLength&1)]);

   302 		}

   303 	}

   304 

   305 void Huffman::ExternalizeL(TBitOutput& aOutput,const TUint32 aHuffman[],TInt aNumCodes)

   306 /** Store a canonical huffman encoding in compact form

   307 

   308 	As the encoding is canonical, only the code lengths of each code needs to be saved.

   309 

   310 	Due to the nature of code length tables, these can usually be stored very compactly

   311 	by encoding the encoding itself, hence the use of the bit output stream.

   312 	

   313 	@param "TBitOutput& aOutput" The output stream for the encoding

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

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

   316 

   317 	@leave "TBitOutput::HuffmanL()"

   318 */

   319 	{

   320 	// We assume that the code length table is generated by the huffman generator,

   321 	// in which case the maxmimum code length is 27 bits.

   322 	//

   323 	// We apply three transformations to the data:

   324 	// 1. the data goes through a move-to-front coder

   325 	// 2. apply a rle-0 coder which replace runs of '0' with streams of '0a' and '0b'

   326 	// 3. encode the result using a predefined (average) huffman coding

   327 	//

   328 	// This can be done in a single pass over the data, avoiding the need for additional

   329 	// memory.

   330 	//

   331 	// initialise the list for the MTF coder

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

   333 	TInt i;

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

   335 		list[i]=TUint8(i);

   336 	TInt last=0;

   337 

   338 	TInt rl=0;

   339 	const TUint32* p32=aHuffman;

   340 	const TUint32* e32=p32+aNumCodes;

   341 	while (p32<e32)

   342 		{

   343 		TInt c=*p32++;

   344 		if (c==last)

   345 			++rl;	// repeat of last symbol

   346 		else

   347 			{

   348 			// encode run-length

   349 			EncodeRunLengthL(aOutput,rl);

   350 			rl=0;

   351 			// find code in MTF list

   352 			TInt j;

   353 			for (j=1;list[j]!=c;++j)

   354 				;

   355 			// store this code

   356 			aOutput.HuffmanL(HuffmanEncoding[j+1]);

   357 			// adjust list for MTF algorithm

   358 			while (--j>0)

   359 				list[j+1]=list[j];

   360 			list[1]=TUint8(last);

   361 			last=c;

   362 			}

   363 		}

   364 	// encod any remaining run-length

   365 	EncodeRunLengthL(aOutput,rl);

   366 	}

   367 

   368 

   369 TBitOutput::TBitOutput()

   370 /** Construct a bit stream output object

   371 

   372 	Following construction the bit stream is ready for writing bits, but will first call

   373 	OverflowL() as the output buffer is 'full'. A derived class can detect this state as

   374 	Ptr() will return null.

   375 */

   376 	:iCode(0),iBits(-8),iPtr(0),iEnd(0)

   377 	{}

   378 

   379 TBitOutput::TBitOutput(TUint8* aBuf,TInt aSize)

   380 /** Construct a bit stream output object over a buffer

   381 

   382 	Data will be written to the buffer until it is full, at which point OverflowL() will

   383 	be called. This should handle the data and then can Set() again to reset the buffer

   384 	for further output.

   385 	

   386 	@param "TUint8* aBuf" The buffer for output

   387 	@param "TInt aSize" The size of the buffer in bytes

   388 */

   389 	:iCode(0),iBits(-8),iPtr(aBuf),iEnd(aBuf+aSize)

   390 	{}

   391 

   392 void TBitOutput::HuffmanL(TUint aHuffCode)

   393 /** Write a huffman code

   394 

   395 	This expects a huffman code value as generated by Huffman::Encoding()

   396 

   397 	@param "TUint aHuffCode" The huffman code write to the stream

   398 

   399 	@leave "OverflowL()" If the output buffer is full, OverflowL() is called

   400 */

   401 	{

   402 	DoWriteL(aHuffCode<<(32-Huffman::KMaxCodeLength),aHuffCode>>Huffman::KMaxCodeLength);

   403 	}

   404 

   405 void TBitOutput::WriteL(TUint aValue,TInt aLength)

   406 /** Write an arbitrary integer value

   407 

   408 	Write an unsigned integer using the number of bits specified. Only

   409 	the low order bits of the value are written to the output, most

   410 	significant bit first.

   411 

   412 	@param "TUint aValue" The value to write to the stream

   413 	@param "TUint aLength" The number of bits to output

   414 

   415 	@leave "OverflowL()" If the output buffer is full, OverflowL() is called

   416 */

   417 	{

   418 	if (aLength)

   419 		DoWriteL(aValue<<=32-aLength,aLength);

   420 	}

   421 

   422 void TBitOutput::PadL(TUint aPadding)

   423 /** Pad the bitstream to the next byte boundary

   424 

   425 	Terminate the bitstream by padding the last byte with the requested value.

   426 	Following this operation the bitstream can continue to be used, the data will

   427 	start at the next byte.

   428 

   429 	@param "TUint aPadding" The bit value to pad the final byte with

   430 

   431 	@leave "OverflowL()" If the output buffer is full, OverflowL() is called

   432 */

   433 	{

   434 	if (iBits>-8)

   435 		WriteL(aPadding?0xffffffffu:0,-iBits);

   436 	}

   437 

   438 void TBitOutput::DoWriteL(TUint aBits,TInt aSize)

   439 /** Write the higher order bits to the stream

   440 	

   441 	@internal

   442 */

   443 	{

   444 	if (aSize>25)

   445 		{

   446 		// cannot process >25 bits in a single pass

   447 		// so do the top 8 bits first

   448 		ASSERT(aSize<=32);

   449 		DoWriteL(aBits&0xff000000u,8);

   450 		aBits<<=8;

   451 		aSize-=8;

   452 		}

   453 

   454 	TInt bits=iBits;

   455 	TUint code=iCode|(aBits>>(bits+8));

   456 	bits+=aSize;

   457 	if (bits>=0)

   458 		{

   459 		TUint8* p=iPtr;

   460 		do

   461 			{

   462 			if (p==iEnd)

   463 				{

   464 				// run out of buffer space so invoke the overflow handler

   465 				iPtr=p;

   466 				OverflowL();

   467 				p=iPtr;

   468 				ASSERT(p!=iEnd);

   469 				}

   470 			*p++=TUint8(code>>24);

   471 			code<<=8;

   472 			bits-=8;

   473 			} while (bits>=0);

   474 		iPtr=p;

   475 		}

   476 	iCode=code;

   477 	iBits=bits;

   478 	}

   479 

   480 void TBitOutput::OverflowL()

   481 /** Handle a full output buffer

   482 

   483 	This virtual function is called when the output buffer is full. It should deal

   484 	with the data in the buffer before reseting the buffer using Set(), allowing

   485 	further data to be written.

   486 

   487 	A derived class can replace this to write the data to a file (for example)

   488 	before marking the buffer as empty.

   489 

   490 	@leave "KErrOverflow" The default implementation leaves

   491 */

   492 	{

   493 	Panic(EHuffmanBufferOverflow);

   494 	}