kernel/eka/euser/us_encode.cpp
author John Imhofe
Mon, 19 Oct 2009 15:55:17 +0100
changeset 0 a41df078684a
permissions -rw-r--r--
Convert Kernelhwsrv package from SFL to EPL kernel\eka\compsupp is subject to the ARM EABI LICENSE userlibandfileserver\fatfilenameconversionplugins\unicodeTables is subject to the Unicode license kernel\eka\kernel\zlib is subject to the zlib license
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
0
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
     1
// Copyright (c) 1998-2009 Nokia Corporation and/or its subsidiary(-ies).
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
     2
// All rights reserved.
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
     3
// This component and the accompanying materials are made available
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
     4
// under the terms of the License "Eclipse Public License v1.0"
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
     5
// which accompanies this distribution, and is available
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
     6
// at the URL "http://www.eclipse.org/legal/epl-v10.html".
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
     7
//
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
     8
// Initial Contributors:
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
     9
// Nokia Corporation - initial contribution.
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    10
//
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    11
// Contributors:
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    12
//
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    13
// Description:
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    14
// e32\euser\us_encode.cpp
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    15
// 
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    16
//
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    17
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    18
#include "e32huffman.h"
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    19
#include <e32base.h>
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    20
#include <e32base_private.h>
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    21
#include <e32panic.h>
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    22
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    23
_LIT(KCat,"Huffman");
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    24
// local definitions used for Huffman code generation
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    25
typedef TUint16 THuff;		/** @internal */
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    26
const THuff KLeaf=0x8000;	/** @internal */
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    27
struct TNode
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    28
/** @internal */
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    29
	{
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    30
	TUint iCount;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    31
	THuff iLeft;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    32
	THuff iRight;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    33
	};
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    34
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    35
/** recursive function to calculate the code lengths from the node tree
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    36
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    37
	@internalComponent
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    38
*/
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    39
void HuffmanLengthsL(TUint32* aLengths,const TNode* aNodes,TInt aNode,TInt aLen)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    40
	{
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    41
	if (++aLen>Huffman::KMaxCodeLength)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    42
		User::Leave(KErrOverflow);
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    43
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    44
	const TNode& node=aNodes[aNode];
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    45
	TUint x=node.iLeft;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    46
	if (x&KLeaf)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    47
		aLengths[x&~KLeaf]=aLen;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    48
	else
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    49
		HuffmanLengthsL(aLengths,aNodes,x,aLen);
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    50
	x=node.iRight;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    51
	if (x&KLeaf)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    52
		aLengths[x&~KLeaf]=aLen;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    53
	else
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    54
		HuffmanLengthsL(aLengths,aNodes,x,aLen);
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    55
	}
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    56
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    57
/**	Insert the {aCount,aValue} pair into the already sorted array of nodes
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    58
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    59
	@internalComponent
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    60
*/
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    61
void InsertInOrder(TNode* aNodes, TInt aSize, TUint aCount, TInt aVal)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    62
	{
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    63
	// Uses Insertion sort following a binary search...
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    64
	TInt l=0, r=aSize;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    65
	while (l < r)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    66
		{
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    67
		TInt m = (l+r) >> 1;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    68
		if (aNodes[m].iCount<aCount)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    69
			r=m;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    70
		else
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    71
			l=m+1;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    72
		}
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    73
	Mem::Copy(aNodes+l+1,aNodes+l,sizeof(TNode)*(aSize-l));
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    74
	aNodes[l].iCount=aCount;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    75
	aNodes[l].iRight=TUint16(aVal);
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    76
	}
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    77
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    78
/** Generate a Huffman code
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    79
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    80
	This generates a Huffman code for a given set of code frequencies. The output
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    81
	is a table of code lengths which can be used to build canonincal encoding tables
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    82
	or decoding trees for use with the TBitInput and TBitOutput classes.
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    83
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    84
	Entries in the table with a frequency of zero will have a zero code length
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    85
	and thus no associated huffman encoding. If each such symbol should have a
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    86
	maximum length encoding, they must be given at least a frequency of 1.
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    87
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    88
	For an alphabet of n symbols, this algorithm has a transient memory overhead
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    89
	of 8n, and a time complexity of O(n*log(n)).
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    90
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    91
	@param aFrequency The table of code frequencies
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    92
	@param aNumCodes The number of codes in the table
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    93
	@param aHuffman The table for the output code-length table. This must be
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    94
		the same size as the frequency table, and can safely be the same table
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    95
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    96
	@leave KErrNoMemory If memory used for code generation cannot be allocated
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    97
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    98
  	@panic "USER ???" If the number of codes exceeds Huffman::KMaxCodes
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
    99
*/
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   100
EXPORT_C void Huffman::HuffmanL(const TUint32 aFrequency[],TInt aNumCodes,TUint32 aHuffman[])
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   101
	{
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   102
	__ASSERT_ALWAYS(TUint(aNumCodes)<=TUint(KMaxCodes),User::Panic(KCat,EHuffmanTooManyCodes));
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   103
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   104
	// Sort the values into decreasing order of frequency
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   105
	//
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   106
	TNode* nodes = new(ELeave) TNode[aNumCodes];
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   107
	CleanupArrayDeletePushL(nodes);
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   108
	TInt lCount=0;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   109
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   110
	for (TInt ii=0;ii<aNumCodes;++ii)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   111
		{
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   112
		TInt c=aFrequency[ii];
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   113
		if (c!=0)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   114
			InsertInOrder(nodes,lCount++,c,ii|KLeaf);
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   115
		}
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   116
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   117
	// default code length is zero
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   118
	Mem::FillZ(aHuffman,aNumCodes*sizeof(TUint32));
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   119
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   120
	if (lCount==0)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   121
		{
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   122
		// no codes with frequency>0. No code has a length
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   123
		}
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   124
	else if (lCount==1)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   125
		{
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   126
		// special case for a single value (always encode as "0")
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   127
		aHuffman[nodes[0].iRight&~KLeaf]=1;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   128
		}
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   129
	else
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   130
		{
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   131
		// Huffman algorithm: pair off least frequent nodes and reorder
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   132
		//
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   133
		do
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   134
			{
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   135
			--lCount;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   136
			TUint c=nodes[lCount].iCount + nodes[lCount-1].iCount;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   137
			nodes[lCount].iLeft=nodes[lCount-1].iRight;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   138
			// re-order the leaves now to reflect new combined frequency 'c'
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   139
			InsertInOrder(nodes,lCount-1,c,lCount);
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   140
			} while (lCount>1);
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   141
		// generate code lengths in aHuffman[]
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   142
		HuffmanLengthsL(aHuffman,nodes,1,0);
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   143
		}
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   144
	CleanupStack::PopAndDestroy(nodes);
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   145
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   146
	__ASSERT_DEBUG(IsValid(aHuffman,aNumCodes),User::Panic(KCat,EHuffmanInvalidCoding));
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   147
	}
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   148
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   149
/** Validate a Huffman encoding
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   150
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   151
	This verifies that a Huffman coding described by the code lengths is valid.
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   152
	In particular, it ensures that no code exceeds the maximum length and
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   153
	that it is possible to generate a canonical coding for the specified lengths.
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   154
	
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   155
	@param aHuffman The table of code lengths as generated by Huffman::HuffmanL()
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   156
	@param aNumCodes The number of codes in the table
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   157
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   158
	@return True if the code is valid, otherwise false
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   159
*/
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   160
EXPORT_C TBool Huffman::IsValid(const TUint32 aHuffman[],TInt aNumCodes)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   161
	{
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   162
	// The code is valid if one of the following holds:
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   163
	// (a) the code exactly fills the 'code space'
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   164
	// (b) there is only a single symbol with code length 1
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   165
	// (c) there are no encoded symbols
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   166
	//
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   167
	TUint remain=1<<KMaxCodeLength;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   168
	TInt totlen=0;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   169
	for (const TUint32* p=aHuffman+aNumCodes; p>aHuffman;)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   170
		{
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   171
		TInt len=*--p;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   172
		if (len>0)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   173
			{
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   174
			totlen+=len;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   175
			if (len>KMaxCodeLength)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   176
				return EFalse;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   177
			TUint c=1<<(KMaxCodeLength-len);
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   178
			if (c>remain)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   179
				return EFalse;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   180
			remain-=c;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   181
			}
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   182
		}
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   183
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   184
	return remain==0 || totlen<=1;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   185
	}
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   186
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   187
/** Create a canonical Huffman encoding table
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   188
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   189
	This generates the huffman codes used by TBitOutput::HuffmanL() to write huffman
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   190
	encoded data. The input is table of code lengths, as generated by Huffman::HuffmanL()
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   191
	and must represent a valid huffman code.
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   192
	
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   193
	@param aHuffman The table of code lengths as generated by Huffman::HuffmanL()
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   194
	@param aNumCodes The number of codes in the table
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   195
	@param aEncodeTable The table for the output huffman codes. This must be
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   196
		the same size as the code-length table, and can safely be the same table
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   197
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   198
	@panic "USER ???" If the provided code is not a valid Huffman coding
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   199
	
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   200
	@see IsValid()
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   201
	@see HuffmanL()
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   202
*/
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   203
EXPORT_C void Huffman::Encoding(const TUint32 aHuffman[],TInt aNumCodes,TUint32 aEncodeTable[])
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   204
	{
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   205
	__ASSERT_ALWAYS(IsValid(aHuffman,aNumCodes),User::Panic(KCat,EHuffmanInvalidCoding));
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   206
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   207
	TFixedArray<TInt,KMaxCodeLength> lenCount;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   208
	lenCount.Reset();
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   209
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   210
	TInt ii;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   211
	for (ii=0;ii<aNumCodes;++ii)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   212
		{
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   213
		TInt len=aHuffman[ii]-1;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   214
		if (len>=0)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   215
			++lenCount[len];
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   216
		}
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   217
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   218
	TFixedArray<TUint,KMaxCodeLength> nextCode;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   219
	TUint code=0;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   220
	for (ii=0;ii<KMaxCodeLength;++ii)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   221
		{
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   222
		code<<=1;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   223
		nextCode[ii]=code;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   224
		code+=lenCount[ii];
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   225
		}
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   226
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   227
	for (ii=0;ii<aNumCodes;++ii)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   228
		{
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   229
		TInt len=aHuffman[ii];
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   230
		if (len==0)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   231
			aEncodeTable[ii]=0;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   232
		else
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   233
			{
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   234
			aEncodeTable[ii] = (nextCode[len-1]<<(KMaxCodeLength-len))|(len<<KMaxCodeLength);
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   235
			++nextCode[len-1];
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   236
			}
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   237
		}
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   238
	}
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   239
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   240
/** the encoding table for the externalised code
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   241
	@internalComponent
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   242
*/
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   243
const TUint32 HuffmanEncoding[]=
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   244
	{
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   245
	0x10000000,
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   246
	0x1c000000,
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   247
	0x12000000,
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   248
	0x1d000000,
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   249
	0x26000000,
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   250
	0x26800000,
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   251
	0x2f000000,
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   252
	0x37400000,
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   253
	0x37600000,
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   254
	0x37800000,
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   255
	0x3fa00000,
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   256
	0x3fb00000,
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   257
	0x3fc00000,
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   258
	0x3fd00000,
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   259
	0x47e00000,
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   260
	0x47e80000,
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   261
	0x47f00000,
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   262
	0x4ff80000,
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   263
	0x57fc0000,
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   264
	0x5ffe0000,
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   265
	0x67ff0000,
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   266
	0x77ff8000,
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   267
	0x7fffa000,
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   268
	0x7fffb000,
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   269
	0x7fffc000,
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   270
	0x7fffd000,
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   271
	0x7fffe000,
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   272
	0x87fff000,
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   273
	0x87fff800
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   274
	};
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   275
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   276
/** encode 0a as '0' and 0b as '1', return number of symbols created
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   277
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   278
	@internalComponent
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   279
*/
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   280
void EncodeRunLengthL(TBitOutput& aOutput, TInt aLength)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   281
	{
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   282
	if (aLength>0)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   283
		{
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   284
		EncodeRunLengthL(aOutput,(aLength-1)>>1);
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   285
		aOutput.HuffmanL(HuffmanEncoding[1-(aLength&1)]);
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   286
		}
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   287
	}
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   288
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   289
/** Store a canonical huffman encoding in compact form
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   290
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   291
	As the encoding is canonical, only the code lengths of each code needs to be saved.
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   292
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   293
	Due to the nature of code length tables, these can usually be stored very compactly
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   294
	by encoding the encoding itself, hence the use of the bit output stream.
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   295
	
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   296
	@param aOutput The output stream for the encoding
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   297
	@param aHuffman The table of code lengths as generated by Huffman::HuffmanL()
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   298
	@param aNumCodes The number of huffman codes in the table
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   299
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   300
	@leave TBitOutput::HuffmanL()
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   301
*/
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   302
EXPORT_C void Huffman::ExternalizeL(TBitOutput& aOutput,const TUint32 aHuffman[],TInt aNumCodes)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   303
	{
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   304
	// We assume that the code length table is generated by the huffman generator,
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   305
	// in which case the maxmimum code length is 27 bits.
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   306
	//
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   307
	// We apply three transformations to the data:
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   308
	// 1. the data goes through a move-to-front coder
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   309
	// 2. apply a rle-0 coder which replace runs of '0' with streams of '0a' and '0b'
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   310
	// 3. encode the result using a predefined (average) huffman coding
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   311
	//
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   312
	// This can be done in a single pass over the data, avoiding the need for additional
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   313
	// memory.
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   314
	//
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   315
	// initialise the list for the MTF coder
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   316
	TFixedArray<TUint8,Huffman::KMetaCodes> list;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   317
	TInt i;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   318
	for (i=0;i<list.Count();++i)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   319
		list[i]=TUint8(i);
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   320
	TInt last=0;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   321
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   322
	TInt rl=0;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   323
	const TUint32* p32=aHuffman;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   324
	const TUint32* e32=p32+aNumCodes;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   325
	while (p32<e32)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   326
		{
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   327
		TInt c=*p32++;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   328
		if (c==last)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   329
			++rl;	// repeat of last symbol
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   330
		else
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   331
			{
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   332
			// encode run-length
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   333
			EncodeRunLengthL(aOutput,rl);
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   334
			rl=0;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   335
			// find code in MTF list
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   336
			TInt j;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   337
			for (j=1;list[j]!=c;++j)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   338
				;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   339
			// store this code
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   340
			aOutput.HuffmanL(HuffmanEncoding[j+1]);
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   341
			// adjust list for MTF algorithm
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   342
			while (--j>0)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   343
				list[j+1]=list[j];
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   344
			list[1]=TUint8(last);
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   345
			last=c;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   346
			}
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   347
		}
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   348
	// encod any remaining run-length
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   349
	EncodeRunLengthL(aOutput,rl);
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   350
	}
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   351
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   352
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   353
/** Construct a bit stream output object
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   354
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   355
	Following construction the bit stream is ready for writing bits, but will first call
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   356
	OverflowL() as the output buffer is 'full'. A derived class can detect this state as
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   357
	Ptr() will return null.
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   358
*/
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   359
EXPORT_C TBitOutput::TBitOutput()
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   360
	:iCode(0),iBits(-8),iPtr(0),iEnd(0)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   361
	{}
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   362
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   363
/** Construct a bit stream output object over a buffer
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   364
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   365
	Data will be written to the buffer until it is full, at which point OverflowL() will
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   366
	be called. This should handle the data and then can Set() again to reset the buffer
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   367
	for further output.
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   368
	
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   369
	@param aBuf The buffer for output
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   370
	@param aSize The size of the buffer in bytes
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   371
*/
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   372
EXPORT_C TBitOutput::TBitOutput(TUint8* aBuf,TInt aSize)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   373
	:iCode(0),iBits(-8),iPtr(aBuf),iEnd(aBuf+aSize)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   374
	{}
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   375
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   376
/** Write a huffman code
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   377
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   378
	This expects a huffman code value as generated by Huffman::Encoding()
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   379
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   380
	@param aHuffCode The huffman code write to the stream
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   381
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   382
	@leave OverflowL() If the output buffer is full, OverflowL() is called
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   383
*/
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   384
EXPORT_C void TBitOutput::HuffmanL(TUint aHuffCode)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   385
	{
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   386
	DoWriteL(aHuffCode<<(32-Huffman::KMaxCodeLength),aHuffCode>>Huffman::KMaxCodeLength);
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   387
	}
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   388
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   389
/** Write an arbitrary integer value
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   390
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   391
	Write an unsigned integer using the number of bits specified. Only
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   392
	the low order bits of the value are written to the output, most
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   393
	significant bit first.
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   394
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   395
	@param aValue The value to write to the stream
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   396
	@param aLength The number of bits to output
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   397
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   398
	@leave OverflowL() If the output buffer is full, OverflowL() is called
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   399
*/
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   400
EXPORT_C void TBitOutput::WriteL(TUint aValue,TInt aLength)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   401
	{
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   402
	if (aLength)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   403
		DoWriteL(aValue<<=32-aLength,aLength);
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   404
	}
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   405
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   406
/** Pad the bitstream to the next byte boundary
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   407
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   408
	Terminate the bitstream by padding the last byte with the requested value.
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   409
	Following this operation the bitstream can continue to be used, the data will
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   410
	start at the next byte.
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   411
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   412
	@param aPadding The bit value to pad the final byte with
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   413
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   414
	@leave OverflowL() If the output buffer is full, OverflowL() is called
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   415
*/
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   416
EXPORT_C void TBitOutput::PadL(TUint aPadding)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   417
	{
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   418
	if (iBits>-8)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   419
		WriteL(aPadding?0xffffffffu:0,-iBits);
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   420
	}
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   421
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   422
/** Write the higher order bits to the stream
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   423
	
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   424
	@internalComponent
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   425
*/
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   426
void TBitOutput::DoWriteL(TUint aBits,TInt aSize)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   427
	{
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   428
	if (aSize>25)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   429
		{
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   430
		// cannot process >25 bits in a single pass
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   431
		// so do the top 8 bits first
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   432
		ASSERT(aSize<=32);
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   433
		DoWriteL(aBits&0xff000000u,8);
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   434
		aBits<<=8;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   435
		aSize-=8;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   436
		}
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   437
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   438
	TInt bits=iBits;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   439
	TUint code=iCode|(aBits>>(bits+8));
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   440
	bits+=aSize;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   441
	if (bits>=0)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   442
		{
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   443
		TUint8* p=iPtr;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   444
		do
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   445
			{
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   446
			if (p==iEnd)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   447
				{
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   448
				// run out of buffer space so invoke the overflow handler
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   449
				iPtr=p;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   450
				OverflowL();
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   451
				p=iPtr;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   452
				ASSERT(p!=iEnd);
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   453
				}
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   454
			*p++=TUint8(code>>24);
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   455
			code<<=8;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   456
			bits-=8;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   457
			} while (bits>=0);
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   458
		iPtr=p;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   459
		}
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   460
	iCode=code;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   461
	iBits=bits;
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   462
	}
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   463
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   464
/** Handle a full output buffer
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   465
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   466
	This virtual function is called when the output buffer is full. It should deal
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   467
	with the data in the buffer before reseting the buffer using Set(), allowing
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   468
	further data to be written.
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   469
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   470
	A derived class can replace this to write the data to a file (for example)
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   471
	before marking the buffer as empty.
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   472
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   473
	@leave KErrOverflow The default implementation leaves
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   474
*/
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   475
void TBitOutput::OverflowL()
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   476
	{
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   477
	User::Leave(KErrOverflow);
a41df078684a Convert Kernelhwsrv package from SFL to EPL
John Imhofe
parents:
diff changeset
   478
	}