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

// All rights reserved.

// This component and the accompanying materials are made available

// under the terms of "Eclipse Public License v1.0"

// which accompanies this distribution, and is available

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

//

// Initial Contributors:

// Nokia Corporation - initial contribution.

//

// Contributors:

//

// Description:

// Store database compression code

// 

//

#include "US_STD.H"

#include <s32mem.h>

#ifdef __WINS__

#define __EXTRA_DEFLATE

#endif

// deflation constants

const TInt KDeflateMinLength=3;

const TInt KDeflateMaxLength=258;

const TInt KDeflateMaxDistance=4096;

const TInt KDeflateDistCodeBase=0x200;

// huffman coding/decoding

const TInt KHuffMaxCodeLength=25;

const TInt KHuffTerminate=1;

const TUint KBitsEmpty=0x80000000u;

const TUint KBitsInit=KBitsEmpty>>1;

const TUint KBitsFull=KBitsEmpty>>8;

const TUint KBitsEOF=KBitsEmpty>>9;

const TUint KBitsNext=0x80u;

// encoding storage

const TInt KDeflateMetaCodes=26;

// hashing

const TUint KDeflateHashMultiplier=0xAC4B9B19u;

const TInt KDeflateHashShift=24;

class Huffman

	{

public:

	static void EncodingL(TUint32* aEncoding,TInt aCodes);

	static void Decoding(TUint32* aDecoding,TInt aCodes,TInt aBase=0);

private:

	typedef TUint16 THuff;

	enum {KLeaf=0x8000};

	struct TNode

		{

		THuff iLeft;

		THuff iRight;

		};

	struct TLeaf

		{

		TUint iCount;

		THuff iVal;

		};

private:

	static void Lengths(TUint32* aLengths,const TNode* aNodes,TInt aNode,TInt aLen);

	static TUint32* SubTree(TUint32* aPtr,const TUint32* aValue,TUint32** aLevel);

	};

class THuffEncoder

	{

public:

	THuffEncoder(RWriteStream& aStream);

//

	void EncodeL(TUint aCode,TInt aLength);

	void EncodeL(TUint32 aHuffCode);

	void CompleteL();

private:

	enum {EBufSize=0x100};

private:

	TUint8 iBuf[EBufSize];

	RWriteStream& iStream;

	TUint32 iCode;		// code in production

	TInt iBits;

	TUint8* iWrite;

	};

class HDeflateHash

	{

public:

	inline static HDeflateHash& NewLC(TInt aLinks);

//

	inline TInt First(const TUint8* aPtr,TInt aPos);

	inline TInt Next(TInt aPos,TInt aOffset) const;

private:

	inline HDeflateHash();

	inline static TInt Hash(const TUint8* aPtr);

private:

	typedef TUint16 TOffset;

private:

	TInt iHash[256];

	TOffset iOffset[1];	// or more

	};

class MDeflater

	{

public:

	void DeflateL(const TUint8* aBase,TInt aLength);

private:

	const TUint8* DoDeflateL(const TUint8* aBase,const TUint8* aEnd,HDeflateHash& aHash);

	static TInt Match(const TUint8* aPtr,const TUint8* aEnd,TInt aPos,HDeflateHash& aHas);

	void SegmentL(TInt aLength,TInt aDistance);

	virtual void LitLenL(TInt aCode) =0;

	virtual void OffsetL(TInt aCode) =0;

	virtual void ExtraL(TInt aLen,TUint aBits) =0;

	};

class TInflater

	{

public:

	TInflater(const TUint8* aIn,const CDbStoreCompression::TEncoding& aDecoding);

	TInt Inflate();

	inline const TUint8* Ptr() const;

	inline static TInt BufferSize();

private:

	const TUint8* iIn;

	TUint iBits;

	const TUint8* iRptr;			// partial segment

	TInt iLen;

	const TUint32* iLitLenTree;

	const TUint32* iDistTree;

	TUint8 iOut[KDeflateMaxDistance];	// circular buffer for distance matches

	};

NONSHARABLE_CLASS(TDeflateStats) : public MDeflater

	{

public:

	inline TDeflateStats(CDbStoreCompression::TEncoding& aEncoding);

private:

// from MDeflater

	void LitLenL(TInt aCode);

	void OffsetL(TInt aCode);

	void ExtraL(TInt aLen,TUint aBits);

private:

	CDbStoreCompression::TEncoding& iEncoding;

	};

NONSHARABLE_CLASS(TDeflater) : public MDeflater

	{

public:

	inline TDeflater(THuffEncoder& aEncoder,const CDbStoreCompression::TEncoding& aEncoding);

private:

// from MDeflater

	void LitLenL(TInt aCode);

	void OffsetL(TInt aCode);

	void ExtraL(TInt aLen,TUint aBits);

private:

	THuffEncoder& iEncoder;

	const CDbStoreCompression::TEncoding& iEncoding;

	};

NONSHARABLE_CLASS(HDeflateBuf) : public TBufBuf

	{

public:

	enum TMode {EAnalysis,EDeflate};	// mirror CDbStoreCompression enum

public:

	static HDeflateBuf* NewL(MStreamBuf* aHost,CDbStoreCompression::TEncoding& aEncoding,TMode aMode);

private:

	inline HDeflateBuf(MStreamBuf* aHost,CDbStoreCompression::TEncoding& aEncoding,CBufBase* aBuf,TMode aMode);

	virtual inline ~HDeflateBuf();

// from MStreamBuf

	void DoSynchL();

	void DoRelease();

private:

	RWriteStream iHost;

	CDbStoreCompression::TEncoding& iEncoding;

	CBufBase* iBuf;

	TMode iMode;

	};

NONSHARABLE_CLASS(HInflateBuf) : public TBufBuf

	{

public:

	static HInflateBuf* NewL(MStreamBuf* aHost,const CDbStoreCompression::TEncoding& aEncoding);

private:

	inline HInflateBuf(CBufBase* aBuf);

	virtual inline ~HInflateBuf();

// from MStreamBuf

	void DoRelease();

private:

	CBufBase* iBuf;

	};

NONSHARABLE_CLASS(CDbStoreTable::CCompressor) : public CBase, public CCluster::MAlter

	{

public:

	inline CCompressor();

	~CCompressor();

	void ProcessL(CDbStoreTable* aTable);

private:

	TUint8* AlterRecordL(TUint8* aWPtr,const TUint8* aRPtr,TInt aLength);

private:

	CDbStoreTable* iTable;

	RDbRow iRow;

	};

// Class Huffman

//

// This class builds a huffman encoding from a frequency table and builds

// a decoding tree from a code-lengths table

//

// the encoding generated is based on the rule that given two symbols s1 and s2, with 

// code length l1 and l2, and huffman codes h1 and h2:

//

// if l1<l2 then h1<h2 when compared lexicographically

// if l1==l2 and s1<s2 then h1<h2 ditto

//

// This allows the encoding to be stored compactly as a table of code lengths

//

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

//

void Huffman::Lengths(TUint32* aLengths,const TNode* aNodes,TInt aNode,TInt aLen)

	{

	__ASSERT(aLen<KHuffMaxCodeLength);

	++aLen;

	const TNode& node=aNodes[aNode];

	if (node.iLeft&KLeaf)

		aLengths[node.iLeft&~KLeaf]=aLen;

	else

		Lengths(aLengths,aNodes,node.iLeft,aLen);

	if (node.iRight&KLeaf)

		aLengths[node.iRight&~KLeaf]=aLen;

	else

		Lengths(aLengths,aNodes,node.iRight,aLen);

	}

//

// write the subtree below aPtr and return the head

//

TUint32* Huffman::SubTree(TUint32* aPtr,const TUint32* aValue,TUint32** aLevel)

	{

	TUint32* l=*aLevel++;

	if (l>aValue)

		{

		TUint32* sub1=SubTree(aPtr,aValue,aLevel);	// 0-tree first

		aPtr=SubTree(sub1,aValue-(aPtr-sub1)-1,aLevel);			// 1-tree

		TInt branch=(TUint8*)sub1-(TUint8*)aPtr;

		*--aPtr=branch;

		}

	else if (l==aValue)

		{

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

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

		*--aPtr=term0>>16;

		}

	else	// l<iNext

		{

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

		TUint term1=*aValue--;

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

		}

	return aPtr;

	}

//

// Build a huffman encoding table from a symbol frequency table

// aTable contains frequency data on input for aCodes symbols

// aTable contains the huffman encoding on output

//

void Huffman::EncodingL(TUint32* aTable,TInt aCodes)

	{

//

// step 1. Sort the values into decreasing order of frequency

//

	TLeaf* leaves=new(ELeave) TLeaf[aCodes];

	CleanupArrayDeletePushL(leaves);

	TInt lCount=0;

	TInt ii;

	for (ii=0;ii<aCodes;++ii)

		{

		TUint c=aTable[ii];

		if (c==0)

			continue;	// no coding for ii

		TInt jj;

		for (jj=0;jj<lCount;++jj)

			{

			if (leaves[jj].iCount<=c)

				break;

			}

		Mem::Move(leaves+jj+1,leaves+jj,sizeof(TLeaf)*(lCount-jj));

		leaves[jj].iCount=c;

		leaves[jj].iVal=THuff(ii|KLeaf);

		lCount++;

		}

//

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

// result is the code lengths in aTable[]

//

	if (lCount==1)	// special case for a single value (always encode as "0")

		aTable[leaves[0].iVal&~KLeaf]=1;

	else if (lCount>1)

		{	//	don't encode for empty coding: leaves in order now

		TInt max=0;

		TNode* nodes=new(ELeave) TNode[lCount-1];

		while (--lCount>0)

			{

			TNode& node=nodes[max];

			node.iLeft=leaves[lCount-1].iVal;

			node.iRight=leaves[lCount].iVal;

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

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

			TInt jj=lCount;

			while (--jj>0)

				{

				if (leaves[jj-1].iCount>=c)

					break;

				}

			Mem::Move(leaves+jj+1,leaves+jj,sizeof(TLeaf)*(lCount-1-jj));

			// update new leaf

			leaves[jj].iCount=c;

			leaves[jj].iVal=THuff(max);

			max++;

			}

		Lengths(aTable,nodes,leaves[0].iVal,0);

		delete[] nodes;

		}

	CleanupStack::PopAndDestroy();		// leaves

//

// step 3: Generate the coding based on the code lengths

//

	TInt lenCount[KHuffMaxCodeLength];

	Mem::FillZ(lenCount,sizeof(lenCount));

	for (ii=aCodes;--ii>=0;)

		{

		TInt len=aTable[ii]-1;

		if (len>=0)

			++lenCount[len];

		}

	TUint nextCode[KHuffMaxCodeLength];

	TUint code=0;

	for (ii=0;ii<KHuffMaxCodeLength;++ii)

		{

		nextCode[ii]=code;

		code=(code+lenCount[ii])<<1;

		}

	for (ii=0;ii<aCodes;++ii)

		{

		TInt len=aTable[ii];

		if (len)

			{

			aTable[ii] = (nextCode[len-1]<<(KHuffMaxCodeLength-len))|(len<<KHuffMaxCodeLength);

			++nextCode[len-1];

			}

		}

	}

//

// generate the decoding tree from the huffman code length data

// output alphabet is [aBase,aBase+aCodes)

//

void Huffman::Decoding(TUint32* aDecoding,TInt aCodes,TInt aBase)

	{

	TInt counts[KHuffMaxCodeLength];

	Mem::FillZ(counts,sizeof(counts));

	TInt codes=0;

	TInt ii=aCodes;

	while (--ii>=0)

		{

		TUint len=aDecoding[ii];

		__ASSERT(len<=(TUint)KHuffMaxCodeLength);

		if (len)

			{

			++counts[len-1];

			++codes;

			}

		}

//

	TUint32* level[KHuffMaxCodeLength];

	TUint32* lit=aDecoding+codes;

	for (ii=0;ii<KHuffMaxCodeLength;++ii)

		{

		level[ii]=lit;

		lit-=counts[ii];

		}

	aBase=(aBase<<17)+(KHuffTerminate<<16);

	for (ii=0;ii<aCodes;++ii)

		{

		TUint len=TUint8(aDecoding[ii]);

		if (len)

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

		}

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

		*aDecoding>>=16;	// 0-terminate at root

	else if (codes>1)

		{

		__DEBUG(TUint32* p=) SubTree(aDecoding+codes-1,aDecoding+codes-1,level);

		__ASSERT(p==aDecoding);

		}

	}

// Class HDeflateHash

inline HDeflateHash::HDeflateHash()

	{TInt* p=iHash+256;do *--p=-KDeflateMaxDistance-1; while (p>iHash);}

inline HDeflateHash& HDeflateHash::NewLC(TInt aLinks)

	{

	__ASSERT(!(KDeflateMaxDistance&(KDeflateMaxDistance-1)));	// ensure power of two

	return *new(User::AllocLC(_FOFF(HDeflateHash,iOffset[Min(aLinks,KDeflateMaxDistance)]))) HDeflateHash;

	}

inline TInt HDeflateHash::Hash(const TUint8* aPtr)

	{

	TUint x=aPtr[0]|(aPtr[1]<<8)|(aPtr[2]<<16);

	return (x*KDeflateHashMultiplier)>>KDeflateHashShift;

	}

inline TInt HDeflateHash::First(const TUint8* aPtr,TInt aPos)

	{

	TInt h=Hash(aPtr);

	TInt offset=Min(aPos-iHash[h],KDeflateMaxDistance<<1);

	iHash[h]=aPos;

	iOffset[aPos&(KDeflateMaxDistance-1)]=TOffset(offset);

	return offset;

	}

inline TInt HDeflateHash::Next(TInt aPos,TInt aOffset) const

	{return aOffset+iOffset[(aPos-aOffset)&(KDeflateMaxDistance-1)];}

// Class TDeflater

//

// generic deflation algorithm, can do either statistics and the encoder

TInt MDeflater::Match(const TUint8* aPtr,const TUint8* aEnd,TInt aPos,HDeflateHash& aHash)

	{

	TInt offset=aHash.First(aPtr,aPos);

	if (offset>KDeflateMaxDistance)

		return 0;

	TInt match=0;

	aEnd=Min(aEnd,aPtr+KDeflateMaxLength);

	TUint8 c=*aPtr;

	do

		{

		const TUint8* p=aPtr-offset;

		if (p[match>>16]==c)

			{	// might be a better match

			const TUint8* m=aPtr;

			for (;;)

				{

				if (*p++!=*m++)

					break;

				if (m<aEnd)

					continue;

				return ((m-aPtr)<<16)|offset;

				}

			TInt l=m-aPtr-1;

			if (l>match>>16)

				{

				match=(l<<16)|offset;

				c=m[-1];

				}

			}

		offset=aHash.Next(aPos,offset);

		} while (offset<=KDeflateMaxDistance);

	return match;

	}

//

// Apply the deflation algorithm to the data [aBase,aEnd)

// Return a pointer after the last byte that was deflated (which may not be aEnd)

//

const TUint8* MDeflater::DoDeflateL(const TUint8* aBase,const TUint8* aEnd,HDeflateHash& aHash)

	{

	__ASSERT(aEnd-aBase>KDeflateMinLength);

//

	const TUint8* ptr=aBase;

#ifdef __EXTRA_DEFLATE

	TInt prev=0;		// the previous deflation match

#endif

	do

		{

		TInt match=Match(ptr,aEnd,ptr-aBase,aHash);

#ifdef __EXTRA_DEFLATE

// Extra deflation applies two optimisations which double the time taken

// 1. If we have a match at p, then test for a better match at p+1 before using it

// 2. When we have a match, add the hash links for all the data which will be skipped 

		if (match>>16 < prev>>16)

			{	// use the previous match--it was better

			TInt len=prev>>16;

			SegmentL(len,prev-(len<<16));

			// fill in missing hash entries for better compression

			const TUint8* e=ptr+len-2;

			do

				{

				++ptr;

				aHash.First(ptr,ptr-aBase);

				} while (ptr<e);

			prev=0;

			}

		else if (match<=(KDeflateMinLength<<16))

			LitLenL(*ptr);			// no deflation match here

		else

			{	// save this match and test the next position

			if (prev)	// we had a match at ptr-1, but this is better

				LitLenL(ptr[-1]);

			prev=match;

			}

		++ptr;

#else

// Basic deflation will store any match found, and not update the hash links for the

// data which is skipped

		if (match<=(KDeflateMinLength<<16))		// no match

			LitLenL(*ptr++);

		else

			{	// store the match

			TInt len=match>>16;

			SegmentL(len,match-(len<<16));

			ptr+=len;

			}

#endif

		} while (ptr+KDeflateMinLength-1<aEnd);

#ifdef __EXTRA_DEFLATE

	if (prev)

		{		// emit the stored match

		TInt len=prev>>16;

		SegmentL(len,prev-(len<<16));