diff -r 000000000000 -r bde4ae8d615e os/persistentdata/persistentstorage/dbms/ustor/US_COMP.CPP
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/os/persistentdata/persistentstorage/dbms/ustor/US_COMP.CPP	Fri Jun 15 03:10:57 2012 +0200
@@ -0,0 +1,1259 @@
+// 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));
+		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);
+	}