// 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_DYNAMIC(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));
		ptr+=len-1;
		}
#endif
	return ptr;
	}

//
// The generic deflation algorithm
//
void MDeflater::DeflateL(const TUint8* aBase,TInt aLength)
	{
	const TUint8* end=aBase+aLength;
	if (aLength>KDeflateMinLength)
		{	// deflation kicks in if there is enough data
		HDeflateHash& hash=HDeflateHash::NewLC(aLength);
		aBase=DoDeflateL(aBase,end,hash);
		CleanupStack::PopAndDestroy();
		}
	while (aBase<end)					// emit remaining bytes
		LitLenL(*aBase++);
	LitLenL(CDbStoreCompression::TEncoding::EEos);	// eos marker
	}

//
// Turn a (length,offset) pair into the deflation codes+extra bits before calling
// the specific LitLen(), Offset() and Extra() functions.
//
void MDeflater::SegmentL(TInt aLength,TInt aDistance)
	{
	__ASSERT(aLength>=KDeflateMinLength && aLength<=KDeflateMaxLength);
	aLength-=KDeflateMinLength;
	TInt extralen=0;
	TUint len=aLength;
	while (len>=8)
		{
		++extralen;
		len>>=1;
		}
	__ASSERT((extralen<<2)+len<CDbStoreCompression::TEncoding::ELengths);
	LitLenL((extralen<<2)+len+CDbStoreCompression::TEncoding::ELiterals);
	if (extralen)
		ExtraL(extralen,TUint(aLength)<<(32-extralen));
//
	__ASSERT(aDistance>0 && aDistance<=KDeflateMaxDistance);
	aDistance--;
	extralen=0;
	TUint dist=aDistance;
	while (dist>=8)
		{
		++extralen;
		dist>>=1;
		}
	__ASSERT((extralen<<2)+dist<CDbStoreCompression::TEncoding::EDistances);
	OffsetL((extralen<<2)+dist);
	if (extralen)
		ExtraL(extralen,TUint(aDistance)<<(32-extralen));
	}

// Class TDeflateStats
//
// This class analyses the data stream to generate the frequency tables 
// for the deflation algorithm

inline TDeflateStats::TDeflateStats(CDbStoreCompression::TEncoding& aEncoding)
	:iEncoding(aEncoding)
	{}

void TDeflateStats::LitLenL(TInt aCode)
	{
	++iEncoding.iLitLen[aCode];
	}

void TDeflateStats::OffsetL(TInt aCode)
	{
	++iEncoding.iDistance[aCode];
	}

void TDeflateStats::ExtraL(TInt,TUint)
	{}

// Class THuffEncoder
//
// This class generates the byte stream of huffman codes, writing them out to the stream

THuffEncoder::THuffEncoder(RWriteStream& aStream)
	:iStream(aStream),iCode(0),iBits(-8),iWrite(iBuf)
	{}

//
// Store a huffman code generated by Huffman::EncodingL()
//
void THuffEncoder::EncodeL(TUint32 aHuffCode)
	{
	EncodeL(aHuffCode<<(32-KHuffMaxCodeLength),aHuffCode>>KHuffMaxCodeLength);
	}

//
// Store aLength bits from the most significant bits of aCode
//
void THuffEncoder::EncodeL(TUint aCode,TInt aLength)
	{
	TInt bits=iBits;
	TUint code=iCode|(aCode>>(bits+8));
	bits+=aLength;
	if (bits>=0)
		{
		TUint8* write=iWrite;
		do
			{
			if (write-EBufSize==iBuf)
				{
				iStream.WriteL(iBuf,EBufSize);
				write=iBuf;
				}
			*write++=TUint8(code>>24);
			code<<=8;
			bits-=8;
			} while (bits>=0);
		iWrite=write;
		}
	iCode=code;
	iBits=bits;
	}

//
// Terminate the huffman coding. The longest code is always 1111111111
//
void THuffEncoder::CompleteL()
	{
	if (iBits>-8)
		EncodeL(0xffffffffu,-iBits);
	if (iWrite>iBuf)
		iStream.WriteL(iBuf,iWrite-iBuf);
	}

// Class TDeflater
//
// Extends MDeflater to provide huffman encoding of the output

//
// construct for encoding
//
inline TDeflater::TDeflater(THuffEncoder& aEncoder,const CDbStoreCompression::TEncoding& aEncoding)
	:iEncoder(aEncoder),iEncoding(aEncoding)
	{}

void TDeflater::LitLenL(TInt aCode)
	{
	iEncoder.EncodeL(iEncoding.iLitLen[aCode]);
	}

void TDeflater::OffsetL(TInt aCode)
	{
	iEncoder.EncodeL(iEncoding.iDistance[aCode]);
	}

void TDeflater::ExtraL(TInt aLen,TUint aBits)
	{
	iEncoder.EncodeL(aBits,aLen);
	}

// Class TInflater
//
// The inflation algorithm, complete with huffman decoding

TInflater::TInflater(const TUint8* aIn,const CDbStoreCompression::TEncoding& aEncoding)
	:iIn(aIn),iBits(KBitsInit),iLen(0),iLitLenTree(aEncoding.iLitLen),iDistTree(aEncoding.iDistance)
	{}

//
// consume all data lag in the history buffer, then decode to fill up the output buffer
//
TInt TInflater::Inflate()
	{
// empty the history buffer into the output
	const TUint8* data=iIn;
	TUint bits=iBits;
	const TUint8* from=iRptr;
	TInt len=iLen;
	TUint8* out=iOut;
	TUint8* const end=out+KDeflateMaxDistance;
	const TUint32* node;
	if (len)
		goto useHistory;
//
	if (bits&KBitsEOF)
		return 0;
//
	node=iLitLenTree;
	while (out<end)
		{
		// get a huffman code
		{
		TUint huff;
		for (;;)
			{
			huff=*node++;
			if ((bits<<=1)&KBitsEmpty)
				bits=*data++|KBitsFull;
			if (bits&KBitsNext)
				{
				if (huff&(KHuffTerminate<<16))
					break;
				}
			else
				{
				if (huff&KHuffTerminate)
					{
					huff<<=16;
					break;
					}
				else
					node=PtrAdd(node,huff);
				}
			}
		TInt val=TInt(huff>>17)-CDbStoreCompression::TEncoding::ELiterals;
		if (val<0)
			{
			*out++=TUint8(val);
			node=iLitLenTree;
			continue;			// another literal/length combo
			}
		if (val==CDbStoreCompression::TEncoding::EEos-CDbStoreCompression::TEncoding::ELiterals)
			{	// eos marker. we're done
			bits=KBitsEOF;
			break;
			}
		// get the extra bits for the code
		TInt code=val&0xff;
		if (code>=8)
			{	// xtra bits
			TInt xtra=(code>>2)-1;
			code-=xtra<<2;
			do
				{
				if ((bits<<=1)&KBitsEmpty)
					bits=*data++|KBitsFull;
				code<<=1;
				if (bits&KBitsNext)
					code|=1;
				} while (--xtra!=0);
			}
		if (val<KDeflateDistCodeBase-CDbStoreCompression::TEncoding::ELiterals)
			{	// length code... get the code
			len=code+KDeflateMinLength;
			__ASSERT(len<=KDeflateMaxLength);
			node=iDistTree;
			continue;			// read the huffman code
			}
		// distance code
		__ASSERT(code<KDeflateMaxDistance);
		from=out-(code+1);
		if (from+KDeflateMaxDistance<end)
			from+=KDeflateMaxDistance;
		}
useHistory:
		TInt tfr=Min(end-out,len);
		len-=tfr;
		do
			{
			*out++=*from++;
			if (from==end)
				from-=KDeflateMaxDistance;
			} while (--tfr!=0);
		node=iLitLenTree;
		};
	iIn=data;
	iBits=bits;
	iRptr=from;
	iLen=len;
	return out-iOut;
	}

inline const TUint8* TInflater::Ptr() const
	{return iOut;}
inline TInt TInflater::BufferSize()
	{return KDeflateMaxDistance;}

// Class HDeflateBuf
//
// This stream buffer applies the analysis or deflation and huffman coding
// on the entire stream data when it is committed

inline HDeflateBuf::HDeflateBuf(MStreamBuf* aHost,CDbStoreCompression::TEncoding& aEncoding,CBufBase* aBuf,TMode aMode)
	:iHost(aHost),iEncoding(aEncoding),iBuf(aBuf),iMode(aMode)
	{Set(*aBuf,0);}

HDeflateBuf* HDeflateBuf::NewL(MStreamBuf* aHost,CDbStoreCompression::TEncoding& aEncoding,TMode aMode)
	{
	CBufBase* buf=CBufFlat::NewL(512);
	CleanupStack::PushL(buf);
	HDeflateBuf* self=new(ELeave) HDeflateBuf(aHost,aEncoding,buf,aMode);
	CleanupStack::Pop();
	return self;
	}

inline HDeflateBuf::~HDeflateBuf()
	{delete iBuf;iHost.Release();}

void HDeflateBuf::DoRelease()
	{
	delete this;
	}

//
// This is where it all happens
//
void HDeflateBuf::DoSynchL()
	{
	if (iMode==EAnalysis)
		{
		TDeflateStats deflater(iEncoding);
		deflater.DeflateL(iBuf->Ptr(0).Ptr(),iBuf->Size());
		}
	else
		{
		THuffEncoder encoder(iHost);
		TDeflater deflater(encoder,iEncoding);
		deflater.DeflateL(iBuf->Ptr(0).Ptr(),iBuf->Size());
		encoder.CompleteL();
		iHost.CommitL();
		}
	}

// Class HInflateBuf
//
// Inflate the input stream. This is not a filter, it reads all the input, inflates it and
// keeps it in a memory buffer.

const TInt KInflateBufSize=0x800;	// 2K

HInflateBuf::HInflateBuf(CBufBase* aBuf)
	:iBuf(aBuf)
	{
	Set(*aBuf,0,ERead);
	}

inline HInflateBuf::~HInflateBuf()
	{delete iBuf;}

void HInflateBuf::DoRelease()
	{
	delete this;
	}

HInflateBuf* HInflateBuf::NewL(MStreamBuf* aHost,const CDbStoreCompression::TEncoding& aEncoding)
	{
	CBufFlat* host=CBufFlat::NewL(256);
	CleanupStack::PushL(host);
	TUint8 buffer[KInflateBufSize];
	for (;;)
		{
		TInt len=aHost->ReadL(buffer,KInflateBufSize);
		if (len)
			host->InsertL(host->Size(),buffer,len);
		if (len<KInflateBufSize)
			break;
		}
	CBufSeg* out=CBufSeg::NewL(256);
	CleanupStack::PushL(out);
	TInflater* inflater=new(ELeave) TInflater(host->Ptr(0).Ptr(),aEncoding);
	CleanupStack::PushL(inflater);
	for (;;)
		{
		TInt len=inflater->Inflate();
		if (len)
			out->InsertL(out->Size(),inflater->Ptr(),len);
		if (len<inflater->BufferSize())
			break;
		}
	HInflateBuf* buf=new(ELeave) HInflateBuf(out);
	CleanupStack::PopAndDestroy();	// inflater
	CleanupStack::Pop();			// out
	CleanupStack::PopAndDestroy();	// host
	aHost->Release();				// don't need this anymore
	return buf;
	}

// Class CDbStoreTable::Compressor
//
// This class processes an entire table for analysis or compression, using the
// CDbStoreRecords::AlterL() functionality and call back to ensure that all clusters
// and BLOBs are read and written.

inline CDbStoreTable::CCompressor::CCompressor()
	{}

CDbStoreTable::CCompressor::~CCompressor()
	{
	if (iTable)
		iTable->Close();
	iRow.Close();
	}

//
// Walk through every cluster in the table
//
void CDbStoreTable::CCompressor::ProcessL(CDbStoreTable* aTable)
	{
	iTable=aTable;
	CDbStoreRecords& rec=aTable->StoreRecordsL();
	for (TClusterId cluster=rec.Head();cluster!=KNullClusterId;cluster=rec.AlterL(cluster,*this))
		;
	}

//
// Compress every blob, and transfer the record from aRPtr to aWPtr
//
TUint8* CDbStoreTable::CCompressor::AlterRecordL(TUint8* aWPtr,const TUint8* aRPtr,TInt aLength)
	{
	if (iTable->Def().Columns().HasLongColumns())
		{
		iTable->CopyToRowL(iRow,TPtrC8(aRPtr,aLength));
		CDbBlobSpace* blobs=iTable->BlobsL();
		TDbColNo col=1;
		HDbColumnSet::TIteratorC iter=iTable->Def().Columns().Begin();
		const HDbColumnSet::TIteratorC end=iTable->Def().Columns().End();
		do
			{
			if (!TDbCol::IsLong(iter->Type()))
				continue;
			TDbBlob& blob=CONST_CAST(TDbBlob&,TDbColumnC(iRow,col).Blob());
			if (blob.IsInline())
				continue;
			// do what has to be done...?
			TUint8* data=(TUint8*)User::AllocLC(blob.Size());
			blobs->ReadLC(blob.Id(),iter->Type())->ReadL(data,blob.Size());
			CleanupStack::PopAndDestroy();	// stream buffer
			// re-write the Blob to compress it
			blobs->DeleteL(blob.Id());
			blob.SetId(blobs->CreateL(iter->Type(),data,blob.Size()));
			CleanupStack::PopAndDestroy();	// data
			} while (++col,++iter<end);
		iTable->CopyFromRow(aWPtr,iRow);
		}
	else
		Mem::Copy(aWPtr,aRPtr,aLength);
	return aWPtr+aLength;
	}

// Class CDbStoreCompression
//
// This class manages the compression for the database, applying filters as appropriate
// It also defines the extrenalisation format for the huffman trees

const TInt KDeflationCodes=3*(CDbStoreCompression::TEncoding::ELitLens+CDbStoreCompression::TEncoding::EDistances);

inline CDbStoreCompression::CDbStoreCompression()
//	:iState(EAnalysis)
	{}

CDbStoreCompression* CDbStoreCompression::NewL()
	{
	return new(ELeave) CDbStoreCompression;
	}

//
// Build huffman codings from the freqeuncy tables
//
void CDbStoreCompression::EncodeL()
	{
	//Check the comments in CDbStoreCompression::InternalizeL().
	//The implementation there is very similar to this one and is commented why the "array overrun" 
	//case is impossible.
	__ASSERT(iState==EAnalysis);
	TUint32* p=iEncoding[0].iLitLen;
	TUint32* end=p+KDeflationCodes;
	do
		{
		Huffman::EncodingL(p,TEncoding::ELitLens);
		p+=TEncoding::ELitLens;
		//coverity[overrun-local]
		Huffman::EncodingL(p,TEncoding::EDistances);
		//coverity[overrun-local]
		p+=TEncoding::EDistances;
		} while (p<end);
	iState=EEncoding;
	}

//
// Store the encoding tables as a sequence of code lengths
// The code lengths (0-25) are themselves huffman coded, and the meta coding is stored first
//
void CDbStoreCompression::ExternalizeL(RWriteStream& aStream) const
	{
	__ASSERT(iState==EEncoding);
	const TUint32* base=iEncoding[0].iLitLen;
	const TUint32* end=base+KDeflationCodes;
	TUint32 codes[KDeflateMetaCodes];
	Mem::FillZ(codes,sizeof(codes));
	const TUint32* p=base;
	do ++codes[*p++>>KHuffMaxCodeLength]; while (p<end);
	Huffman::EncodingL(codes,KDeflateMetaCodes);
// save the meta encoding
	p=codes+KDeflateMetaCodes;
	do
		{
		TUint c0=*--p;
		TUint c1=*--p;
		c0>>=KHuffMaxCodeLength;
		c1>>=KHuffMaxCodeLength;
		aStream.WriteUint8L((c0<<4)|c1);
		} while (p>codes);
// write the encoding
	THuffEncoder encoder(aStream);
	p=base;
	do encoder.EncodeL(codes[*p++>>KHuffMaxCodeLength]); while (p<end);
	encoder.CompleteL();
	}

//
// Internalize a previous saved encoding
//
void CDbStoreCompression::InternalizeL(RReadStream& aStream)
	{
	__ASSERT(iState!=EEncoding);
//
// read the meta encoding
	TUint32 decode[KDeflateMetaCodes];
	TUint32* p=decode+KDeflateMetaCodes;
	do
		{
		TUint8 c=aStream.ReadUint8L();
		*--p=c>>4;
		*--p=c&0xf;
		} while (p>decode);
	Huffman::Decoding(decode,KDeflateMetaCodes);
// decode the encoding
	p=iEncoding[0].iLitLen;
	TUint32* end=p+KDeflationCodes;
	TUint bits=KBitsInit;
	do
		{
		const TUint32* node=decode;
		TUint huff;
		for (;;)
			{
			huff=*node++;
			if ((bits<<=1)&KBitsEmpty)
				bits=aStream.ReadUint8L()|KBitsFull;
			if (bits&KBitsNext)
				{
				if (huff&(KHuffTerminate<<16))
					break;
				}
			else
				{
				if (huff&KHuffTerminate)
					{
					huff<<=16;
					break;
					}
				else
					node=PtrAdd(node,huff);
				}
			}
		*p++=huff>>17;
		} while (p<end);
// convert the length tables into huffman decoding trees
	//The iEncoding data member is an array of 3 elements of TEncoding type.
	//The TEncoding layout is: TUint32 iLitLen[ELitLens], TUint32 iDistance[EDistances].
	//Then the in-memory presentation of iEncoding is:
	//               ELitLens     EDistances
	//iEncoding[0]   ........     ........ 
	//iEncoding[1]   ........     ........ 
	//iEncoding[2]   ........     ........
	//
	//Bellow, in the loop:
	// p+=TEncoding::ELitLens;   - moves the pointer to the beginning of iDistance data
	// p+=TEncoding::EDistances; - moves the pointer to the beginning of iLitLen data of the next element of iEncoding.
	//The loop will process the data until "p<end", and "end" is defined as:
	// p=iEncoding[0].iLitLen;
	// TUint32* end=p+KDeflationCodes;
	//KDeflationCodes value is: 3*(CDbStoreCompression::TEncoding::ELitLens+CDbStoreCompression::TEncoding::EDistances),
	//so that is the end of the iEncoding array.
	//Conclusion: the code incrementing the "p" pointer in the loop bellow won't cause array overrun. 
	p=iEncoding[0].iLitLen;
	do
		{
		Huffman::Decoding(p,TEncoding::ELitLens);
		p+=TEncoding::ELitLens;
		//coverity[overrun-local]
		Huffman::Decoding(p,TEncoding::EDistances,KDeflateDistCodeBase);
		//coverity[overrun-local]
		p+=TEncoding::EDistances;
		} while (p<end);
	if (iState==EAnalysis)
		iState=EDecoding;
	}

//
// Apply an inflation filter to a read stream
//
MStreamBuf* CDbStoreCompression::FilterL(MStreamBuf* aHost,TUint32,RDbStoreReadStream::TType aType)
	{
	if (iState==EDecoding || iState==EInflating)
		return HInflateBuf::NewL(aHost,iEncoding[aType]);
	return aHost;
	}

//
// Apply a statistics or inflation filter to a write stream
//
MStreamBuf* CDbStoreCompression::FilterL(MStreamBuf* aHost,TUint32,RDbStoreWriteStream::TType aType)
	{
	TState s=iState;
	if (s==EDecoding)
		__LEAVE(KErrWrite);		// read-only database
	else if (s!=EInflating)
		{
		__ASSERT(TInt(EAnalysis)==TInt(HDeflateBuf::EAnalysis));
		__ASSERT(TInt(EEncoding)==TInt(HDeflateBuf::EDeflate));
		return HDeflateBuf::NewL(aHost,iEncoding[aType],HDeflateBuf::TMode(s));
		}
	return aHost;
	}

// Class CDbStoreDatabase
//
// Compression related code is maintained in this source file

//
// Iterate across all tables applying analysis or compression to them
//
void CDbStoreDatabase::CompressTablesL()
	{
	TSglQueIterC<CDbStoreDef> iter(SchemaL());
	const CDbStoreDef* def;
	while ((def=iter++)!=0)
		{
		CDbStoreTable::CCompressor* comp=new(ELeave) CDbStoreTable::CCompressor;
		CleanupStack::PushL(comp);
		comp->ProcessL(STATIC_CAST(CDbStoreTable*,TableL(*def)));
		CleanupStack::PopAndDestroy();	// comp
		}
	}

//
// Compress or decompress the whole database
//
void CDbStoreDatabase::CompressL(TStreamId aStreamId,TZipType aZip)
	{
	__ASSERT(iStore);
	iSchemaId=aStreamId;
// read the databse header for encryption information
	RStoreReadStream strm;
	strm.OpenLC(Store(),aStreamId);
	ReadHeaderL(strm);
	CleanupStack::PopAndDestroy();	// strm
	InitPagePoolL();
//
	if (iVersion==EDbStoreCompressed)
		{
		iCompression->Inflate();
		if (aZip==EDeflate)
			__LEAVE(KErrArgument);		// already compressed
		}
	else if (aZip==EInflate)
		__LEAVE(KErrArgument);		// not compressed
	else
		{	// deflate pass #1: analyse the database
		CompressionL();				// construct the compression filter
		Transaction().DDLBeginLC();
		CompressTablesL();
		iClusterCache->FlushL();		// force through the stats buffer
		ReplaceSchemaL();				// force through the stats buffer
		CleanupStack::PopAndDestroy();	// rollback after analysis!
		iCompression->EncodeL();
		}
// now inflate or deflate the data
	Transaction().DDLBeginLC();
	CompressTablesL();
	iVersion=TUint8(aZip==EDeflate ? EDbStoreCompressed : EDbStoreVersion2);
	Transaction().DDLCommitL();
	CleanupStack::Pop();		// rollback not required
	}

void CDbStoreDatabase::CompressL(CStreamStore* aStore,TStreamId aStreamId,TZipType aZip)
	{
	//It looks like there is a potential memory leak in the next 4 lines of code, because:
	//1) CDbStoreDatabase* self=NewLC(aStore) - new CDbStoreDatabase object is created on the heap
	//2) CDbObject* db=self->InterfaceL() - new CDbObject is created on the heap 
	//3) CleanupStack::Pop() - the CDbStoreDatabase object from (1) - out from the cleanup stack
	//4) db->PushL() - the CDbObject from (2) - in the cleanup stack
	//If one of the DDLPrepareL() or CompressL() leaves, looks like the CDbStoreDatabase object from (1) will be leaked.
	//This is not a correct guess, becuse:
	// -  CDbObject* db=self->InterfaceL() - this call creates a new CInterface object 
	//                                       on the heap. The CInterface() constructor will store the "this" pointer 
	//                                       passed from the InterfaceL() (so the "self" pointer),
	//	                                     into its "iDatabase" private data member.
	//                                       In which case, the returned CDbObject, of CInterface type, will have
	//                                       its "iDatabase" data member initialized.
	//                                       The inheritance tree is:
	//                                           CBase <-- CDbObject <-- CDbDatabase <-- CInterface
	// - db->PushL() - this call puts on the cleanup stack CDbObject::Destroy().
	//                                       The "db" object which real type is CInterface with "iDatabase" data member
	//                                       initialized with "self", is on the cleanup stack.
	// - If one of the next "L" functions leaves, then CDbObject::Destroy() will be executed.
	// - CDbObject::Destroy() will call CInterface::~CInterface() - CBase is at the root of the inheritance tree, with
	//                                       virtual ~CBase() destructor.
	// - CInterface::~CInterface() implementation calls Database().Close(), so that is CDbStoreDatabase::Close() called on 
	//                                       the "self" pointer.
	// - The CDbStoreDatabase::Close() will call "delete this" when its reference count reaches 0.
	//                                       The reference counter is increased by 1 in the InterfaceL() chain of calls.
	// -------- Conclusion ---------
	// No memory leak will occur in the next lines of code. Coverity errors - disabled.
	CDbStoreDatabase* self=NewLC(aStore);
	//coverity[alloc_fn]
	//coverity[var_assign]
	CDbObject* db=self->InterfaceL();	// a reference to the database is required
	CleanupStack::Pop();	// self
	//coverity[noescape]
	db->PushL();
	//coverity[noescape]
	self->Transaction().DDLPrepareL(*db);
	self->CompressL(aStreamId,aZip);
	CleanupStack::PopAndDestroy();	// db
	//coverity[leaked_storage]
	}

// Class RDbStoreDatabase

EXPORT_C void RDbStoreDatabase::CompressL(CStreamStore& aStore,TStreamId aId)
	{
	CDbStoreDatabase::CompressL(&aStore,aId,CDbStoreDatabase::EDeflate);
	}

EXPORT_C void RDbStoreDatabase::DecompressL(CStreamStore& aStore,TStreamId aId)
	{
	CDbStoreDatabase::CompressL(&aStore,aId,CDbStoreDatabase::EInflate);
	}