sl@0: // Copyright (c) 1998-2009 Nokia Corporation and/or its subsidiary(-ies).
sl@0: // All rights reserved.
sl@0: // This component and the accompanying materials are made available
sl@0: // under the terms of the License "Eclipse Public License v1.0"
sl@0: // which accompanies this distribution, and is available
sl@0: // at the URL "http://www.eclipse.org/legal/epl-v10.html".
sl@0: //
sl@0: // Initial Contributors:
sl@0: // Nokia Corporation - initial contribution.
sl@0: //
sl@0: // Contributors:
sl@0: //
sl@0: // Description:
sl@0: // e32\include\e32huffman.h
sl@0: // 
sl@0: //
sl@0: 
sl@0: #include <e32std.h>
sl@0: 
sl@0: /** @file
sl@0: 	@internalTechnology
sl@0: */
sl@0: 
sl@0: /** Bit output stream.
sl@0: 	Good for writing bit streams for packed, compressed or huffman data algorithms.
sl@0: 
sl@0: 	This class must be derived from and OverflowL() reimplemented if the bitstream data
sl@0: 	cannot be generated into a single memory buffer.
sl@0: */
sl@0: class TBitOutput
sl@0: 	{
sl@0: public:
sl@0: 	IMPORT_C TBitOutput();
sl@0: 	IMPORT_C TBitOutput(TUint8* aBuf,TInt aSize);
sl@0: 	inline void Set(TUint8* aBuf,TInt aSize);
sl@0: 	inline const TUint8* Ptr() const;
sl@0: 	inline TInt BufferedBits() const;
sl@0: //
sl@0: 	IMPORT_C void WriteL(TUint aValue, TInt aLength);
sl@0: 	IMPORT_C void HuffmanL(TUint aHuffCode);
sl@0: 	IMPORT_C void PadL(TUint aPadding);
sl@0: private:
sl@0: 	void DoWriteL(TUint aBits, TInt aSize);
sl@0: 	virtual void OverflowL();
sl@0: private:
sl@0: 	TUint iCode;		// code in production
sl@0: 	TInt iBits;
sl@0: 	TUint8* iPtr;
sl@0: 	TUint8* iEnd;
sl@0: 	};
sl@0: 
sl@0: /** Set the memory buffer to use for output
sl@0: 
sl@0: 	Data will be written to this buffer until it is full, at which point OverflowL() will
sl@0: 	be called. This should handle the data and then can Set() again to reset the buffer
sl@0: 	for further output.
sl@0: 	
sl@0: 	@param aBuf The buffer for output
sl@0: 	@param aSize The size of the buffer in bytes
sl@0: */
sl@0: inline void TBitOutput::Set(TUint8* aBuf,TInt aSize)
sl@0: 	{iPtr=aBuf;iEnd=aBuf+aSize;}
sl@0: 	
sl@0: /** Get the current write position in the output buffer
sl@0: 
sl@0: 	In conjunction with the address of the buffer, which should be known to the
sl@0: 	caller, this describes the data in the bitstream.
sl@0: */
sl@0: inline const TUint8* TBitOutput::Ptr() const
sl@0: 	{return iPtr;}
sl@0: 	
sl@0: /** Get the number of bits that are buffered
sl@0: 
sl@0: 	This reports the number of bits that have not yet been written into the
sl@0: 	output buffer. It will always lie in the range 0..7. Use PadL() to
sl@0: 	pad the data out to the next byte and write it to the buffer.
sl@0: */
sl@0: inline TInt TBitOutput::BufferedBits() const
sl@0: 	{return iBits+8;}
sl@0: 
sl@0: 
sl@0: /** Bit input stream. Good for reading bit streams for packed, compressed or huffman
sl@0: 	data algorithms.
sl@0: */
sl@0: class TBitInput
sl@0: 	{
sl@0: public:
sl@0: 	IMPORT_C TBitInput();
sl@0: 	IMPORT_C TBitInput(const TUint8* aPtr, TInt aLength, TInt aOffset=0);
sl@0: 	IMPORT_C void Set(const TUint8* aPtr, TInt aLength, TInt aOffset=0);
sl@0: //
sl@0: 	IMPORT_C TUint ReadL();
sl@0: 	IMPORT_C TUint ReadL(TInt aSize);
sl@0: 	IMPORT_C TUint HuffmanL(const TUint32* aTree);
sl@0: private:
sl@0: 	virtual void UnderflowL();
sl@0: private:
sl@0: 	TInt iCount;
sl@0: 	TUint iBits;
sl@0: 	TInt iRemain;
sl@0: 	const TUint32* iPtr;
sl@0: 	};
sl@0: 
sl@0: /** Huffman code toolkit.
sl@0: 
sl@0: 	This class builds a huffman encoding from a frequency table and builds
sl@0: 	a decoding tree from a code-lengths table
sl@0: 
sl@0: 	The encoding generated is based on the rule that given two symbols s1 and s2, with 
sl@0: 	code length l1 and l2, and huffman codes h1 and h2:
sl@0: 
sl@0: 		if l1<l2 then h1<h2 when compared lexicographically
sl@0: 		if l1==l2 and s1<s2 then h1<h2 ditto
sl@0: 
sl@0: 	This allows the encoding to be stored compactly as a table of code lengths
sl@0: */
sl@0: class Huffman
sl@0: 	{
sl@0: public:
sl@0: 	enum {KMaxCodeLength=27};
sl@0: 	enum {KMetaCodes=KMaxCodeLength+1};
sl@0: 	enum {KMaxCodes=0x8000};
sl@0: public:
sl@0: 	IMPORT_C static void HuffmanL(const TUint32 aFrequency[],TInt aNumCodes,TUint32 aHuffman[]);
sl@0: 	IMPORT_C static void Encoding(const TUint32 aHuffman[],TInt aNumCodes,TUint32 aEncodeTable[]);
sl@0: 	IMPORT_C static void Decoding(const TUint32 aHuffman[],TInt aNumCodes,TUint32 aDecodeTree[],TInt aSymbolBase=0);
sl@0: 	IMPORT_C static TBool IsValid(const TUint32 aHuffman[],TInt aNumCodes);
sl@0: //
sl@0: 	IMPORT_C static void ExternalizeL(TBitOutput& aOutput,const TUint32 aHuffman[],TInt aNumCodes);
sl@0: 	IMPORT_C static void InternalizeL(TBitInput& aInput,TUint32 aHuffman[],TInt aNumCodes);
sl@0: 	};