imgtools/imglib/e32image/deflate/huffman.h
author Alex Gilkes <alex.gilkes@nokia.com>
Tue, 27 Oct 2009 16:36:35 +0000
changeset 0 044383f39525
permissions -rw-r--r--
Convert Build package from SFL to EPL
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
0
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
     1
/*
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
     2
* Copyright (c) 1998-2009 Nokia Corporation and/or its subsidiary(-ies).
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
     3
* All rights reserved.
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
     4
* This component and the accompanying materials are made available
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
     5
* under the terms of the License "Eclipse Public License v1.0"
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
     6
* which accompanies this distribution, and is available
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
     7
* at the URL "http://www.eclipse.org/legal/epl-v10.html".
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
     8
*
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
     9
* Initial Contributors:
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    10
* Nokia Corporation - initial contribution.
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    11
*
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    12
* Contributors:
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    13
*
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    14
* Description: 
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    15
* e32tools\petran\Szip\huffman.h
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    16
*
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    17
*/
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    18
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    19
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    20
#ifndef __HUFFMAN_H__
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    21
#define __HUFFMAN_H__
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    22
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    23
#include <e32std.h>
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    24
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    25
/** Bit output stream.
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    26
	Good for writing bit streams for packed, compressed or huffman data algorithms.
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    27
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    28
	This class must be derived from and OverflowL() reimplemented if the bitstream data
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    29
	cannot be generated into a single memory buffer.
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    30
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    31
	@since 8.0
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    32
	@library euser.lib
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    33
*/
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    34
class TBitOutput
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    35
	{
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    36
public:
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    37
	TBitOutput();
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    38
	TBitOutput(TUint8* aBuf,TInt aSize);
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    39
	inline virtual ~TBitOutput() { } 
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    40
	inline void Set(TUint8* aBuf,TInt aSize);
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    41
	inline const TUint8* Ptr() const;
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    42
	inline TInt BufferedBits() const;
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    43
//
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    44
	void WriteL(TUint aValue, TInt aLength);
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    45
	void HuffmanL(TUint aHuffCode);
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    46
	void PadL(TUint aPadding);
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    47
private:
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    48
	void DoWriteL(TUint aBits, TInt aSize);
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    49
	virtual void OverflowL();
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    50
private:
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    51
	TUint iCode;		// code in production
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    52
	TInt iBits;
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    53
	TUint8* iPtr;
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    54
	TUint8* iEnd;
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    55
	};
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    56
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    57
/** Set the memory buffer to use for output
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    58
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    59
	Data will be written to this buffer until it is full, at which point OverflowL() will
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    60
	be called. This should handle the data and then can Set() again to reset the buffer
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    61
	for further output.
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    62
	
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    63
	@param "TUint8* aBuf" The buffer for output
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    64
	@param "TInt aSize" The size of the buffer in bytes
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    65
*/
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    66
inline void TBitOutput::Set(TUint8* aBuf,TInt aSize)
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    67
	{iPtr=aBuf;iEnd=aBuf+aSize;}
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    68
/** Get the current write position in the output buffer
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    69
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    70
	In conjunction with the address of the buffer, which should be known to the
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    71
	caller, this describes the data in the bitstream.
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    72
*/
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    73
inline const TUint8* TBitOutput::Ptr() const
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    74
	{return iPtr;}
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    75
/** Get the number of bits that are buffered
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    76
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    77
	This reports the number of bits that have not yet been written into the
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    78
	output buffer. It will always lie in the range 0..7. Use PadL() to
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    79
	pad the data out to the next byte and write it to the buffer.
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    80
*/
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    81
inline TInt TBitOutput::BufferedBits() const
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    82
	{return iBits+8;}
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    83
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    84
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    85
/** Bit input stream.
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    86
	Good for reading bit streams for packed, compressed or huffman data algorithms.
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    87
	@since 8.0
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    88
	@library euser.lib
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    89
*/
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    90
class TBitInput
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    91
	{
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    92
public:
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    93
	TBitInput();
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    94
	TBitInput(const TUint8* aPtr, TInt aLength, TInt aOffset=0);
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    95
	void Set(const TUint8* aPtr, TInt aLength, TInt aOffset=0);
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    96
 	inline virtual ~TBitInput() { } 
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    97
	TUint ReadL();
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    98
	TUint ReadL(TInt aSize);
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
    99
	TUint HuffmanL(const TUint32* aTree);
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   100
private:
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   101
	virtual void UnderflowL();
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   102
private:
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   103
	TInt iCount;
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   104
	TUint iBits;
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   105
	TInt iRemain;
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   106
	const TUint32* iPtr;
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   107
	};
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   108
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   109
/** Huffman code toolkit.
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   110
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   111
	This class builds a huffman encoding from a frequency table and builds
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   112
	a decoding tree from a code-lengths table
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   113
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   114
	The encoding generated is based on the rule that given two symbols s1 and s2, with 
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   115
	code length l1 and l2, and huffman codes h1 and h2:
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   116
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   117
		if l1<l2 then h1<h2 when compared lexicographically
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   118
		if l1==l2 and s1<s2 then h1<h2 ditto
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   119
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   120
	This allows the encoding to be stored compactly as a table of code lengths
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   121
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   122
	@since 8.0
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   123
	@library euser.lib
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   124
*/
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   125
class Huffman
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   126
	{
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   127
public:
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   128
	enum {KMaxCodeLength=27};
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   129
	enum {KMetaCodes=KMaxCodeLength+1};
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   130
	enum {KMaxCodes=0x8000};
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   131
public:
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   132
	static void HuffmanL(const TUint32 aFrequency[],TInt aNumCodes,TUint32 aHuffman[]);
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   133
	static void Encoding(const TUint32 aHuffman[],TInt aNumCodes,TUint32 aEncodeTable[]);
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   134
	static void Decoding(const TUint32 aHuffman[],TInt aNumCodes,TUint32 aDecodeTree[],TInt aSymbolBase=0);
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   135
	static TBool IsValid(const TUint32 aHuffman[],TInt aNumCodes);
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   136
//
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   137
	static void ExternalizeL(TBitOutput& aOutput,const TUint32 aHuffman[],TInt aNumCodes);
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   138
	static void InternalizeL(TBitInput& aInput,TUint32 aHuffman[],TInt aNumCodes);
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   139
	};
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   140
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   141
#endif
044383f39525 Convert Build package from SFL to EPL
Alex Gilkes <alex.gilkes@nokia.com>
parents:
diff changeset
   142