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 "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: // Store database compression code
sl@0: // 
sl@0: //
sl@0: 
sl@0: #include "US_STD.H"
sl@0: #include <s32mem.h>
sl@0: 
sl@0: #ifdef __WINS__
sl@0: #define __EXTRA_DEFLATE
sl@0: #endif
sl@0: 
sl@0: // deflation constants
sl@0: const TInt KDeflateMinLength=3;
sl@0: const TInt KDeflateMaxLength=258;
sl@0: const TInt KDeflateMaxDistance=4096;
sl@0: const TInt KDeflateDistCodeBase=0x200;
sl@0: // huffman coding/decoding
sl@0: const TInt KHuffMaxCodeLength=25;
sl@0: const TInt KHuffTerminate=1;
sl@0: const TUint KBitsEmpty=0x80000000u;
sl@0: const TUint KBitsInit=KBitsEmpty>>1;
sl@0: const TUint KBitsFull=KBitsEmpty>>8;
sl@0: const TUint KBitsEOF=KBitsEmpty>>9;
sl@0: const TUint KBitsNext=0x80u;
sl@0: // encoding storage
sl@0: const TInt KDeflateMetaCodes=26;
sl@0: // hashing
sl@0: const TUint KDeflateHashMultiplier=0xAC4B9B19u;
sl@0: const TInt KDeflateHashShift=24;
sl@0: 
sl@0: class Huffman
sl@0: 	{
sl@0: public:
sl@0: 	static void EncodingL(TUint32* aEncoding,TInt aCodes);
sl@0: 	static void Decoding(TUint32* aDecoding,TInt aCodes,TInt aBase=0);
sl@0: private:
sl@0: 	typedef TUint16 THuff;
sl@0: 	enum {KLeaf=0x8000};
sl@0: 	struct TNode
sl@0: 		{
sl@0: 		THuff iLeft;
sl@0: 		THuff iRight;
sl@0: 		};
sl@0: 	struct TLeaf
sl@0: 		{
sl@0: 		TUint iCount;
sl@0: 		THuff iVal;
sl@0: 		};
sl@0: private:
sl@0: 	static void Lengths(TUint32* aLengths,const TNode* aNodes,TInt aNode,TInt aLen);
sl@0: 	static TUint32* SubTree(TUint32* aPtr,const TUint32* aValue,TUint32** aLevel);
sl@0: 	};
sl@0: 
sl@0: class THuffEncoder
sl@0: 	{
sl@0: public:
sl@0: 	THuffEncoder(RWriteStream& aStream);
sl@0: //
sl@0: 	void EncodeL(TUint aCode,TInt aLength);
sl@0: 	void EncodeL(TUint32 aHuffCode);
sl@0: 	void CompleteL();
sl@0: private:
sl@0: 	enum {EBufSize=0x100};
sl@0: private:
sl@0: 	TUint8 iBuf[EBufSize];
sl@0: 	RWriteStream& iStream;
sl@0: 	TUint32 iCode;		// code in production
sl@0: 	TInt iBits;
sl@0: 	TUint8* iWrite;
sl@0: 	};
sl@0: 
sl@0: class HDeflateHash
sl@0: 	{
sl@0: public:
sl@0: 	inline static HDeflateHash& NewLC(TInt aLinks);
sl@0: //
sl@0: 	inline TInt First(const TUint8* aPtr,TInt aPos);
sl@0: 	inline TInt Next(TInt aPos,TInt aOffset) const;
sl@0: private:
sl@0: 	inline HDeflateHash();
sl@0: 	inline static TInt Hash(const TUint8* aPtr);
sl@0: private:
sl@0: 	typedef TUint16 TOffset;
sl@0: private:
sl@0: 	TInt iHash[256];
sl@0: 	TOffset iOffset[1];	// or more
sl@0: 	};
sl@0: 
sl@0: class MDeflater
sl@0: 	{
sl@0: public:
sl@0: 	void DeflateL(const TUint8* aBase,TInt aLength);
sl@0: private:
sl@0: 	const TUint8* DoDeflateL(const TUint8* aBase,const TUint8* aEnd,HDeflateHash& aHash);
sl@0: 	static TInt Match(const TUint8* aPtr,const TUint8* aEnd,TInt aPos,HDeflateHash& aHas);
sl@0: 	void SegmentL(TInt aLength,TInt aDistance);
sl@0: 	virtual void LitLenL(TInt aCode) =0;
sl@0: 	virtual void OffsetL(TInt aCode) =0;
sl@0: 	virtual void ExtraL(TInt aLen,TUint aBits) =0;
sl@0: 	};
sl@0: 
sl@0: class TInflater
sl@0: 	{
sl@0: public:
sl@0: 	TInflater(const TUint8* aIn,const CDbStoreCompression::TEncoding& aDecoding);
sl@0: 	TInt Inflate();
sl@0: 	inline const TUint8* Ptr() const;
sl@0: 	inline static TInt BufferSize();
sl@0: private:
sl@0: 	const TUint8* iIn;
sl@0: 	TUint iBits;
sl@0: 	const TUint8* iRptr;			// partial segment
sl@0: 	TInt iLen;
sl@0: 	const TUint32* iLitLenTree;
sl@0: 	const TUint32* iDistTree;
sl@0: 	TUint8 iOut[KDeflateMaxDistance];	// circular buffer for distance matches
sl@0: 	};
sl@0: 
sl@0: NONSHARABLE_CLASS(TDeflateStats) : public MDeflater
sl@0: 	{
sl@0: public:
sl@0: 	inline TDeflateStats(CDbStoreCompression::TEncoding& aEncoding);
sl@0: private:
sl@0: // from MDeflater
sl@0: 	void LitLenL(TInt aCode);
sl@0: 	void OffsetL(TInt aCode);
sl@0: 	void ExtraL(TInt aLen,TUint aBits);
sl@0: private:
sl@0: 	CDbStoreCompression::TEncoding& iEncoding;
sl@0: 	};
sl@0: 
sl@0: NONSHARABLE_CLASS(TDeflater) : public MDeflater
sl@0: 	{
sl@0: public:
sl@0: 	inline TDeflater(THuffEncoder& aEncoder,const CDbStoreCompression::TEncoding& aEncoding);
sl@0: private:
sl@0: // from MDeflater
sl@0: 	void LitLenL(TInt aCode);
sl@0: 	void OffsetL(TInt aCode);
sl@0: 	void ExtraL(TInt aLen,TUint aBits);
sl@0: private:
sl@0: 	THuffEncoder& iEncoder;
sl@0: 	const CDbStoreCompression::TEncoding& iEncoding;
sl@0: 	};
sl@0: 
sl@0: NONSHARABLE_CLASS(HDeflateBuf) : public TBufBuf
sl@0: 	{
sl@0: public:
sl@0: 	enum TMode {EAnalysis,EDeflate};	// mirror CDbStoreCompression enum
sl@0: public:
sl@0: 	static HDeflateBuf* NewL(MStreamBuf* aHost,CDbStoreCompression::TEncoding& aEncoding,TMode aMode);
sl@0: private:
sl@0: 	inline HDeflateBuf(MStreamBuf* aHost,CDbStoreCompression::TEncoding& aEncoding,CBufBase* aBuf,TMode aMode);
sl@0: 	virtual inline ~HDeflateBuf();
sl@0: // from MStreamBuf
sl@0: 	void DoSynchL();
sl@0: 	void DoRelease();
sl@0: private:
sl@0: 	RWriteStream iHost;
sl@0: 	CDbStoreCompression::TEncoding& iEncoding;
sl@0: 	CBufBase* iBuf;
sl@0: 	TMode iMode;
sl@0: 	};
sl@0: 
sl@0: NONSHARABLE_CLASS(HInflateBuf) : public TBufBuf
sl@0: 	{
sl@0: public:
sl@0: 	static HInflateBuf* NewL(MStreamBuf* aHost,const CDbStoreCompression::TEncoding& aEncoding);
sl@0: private:
sl@0: 	inline HInflateBuf(CBufBase* aBuf);
sl@0: 	virtual inline ~HInflateBuf();
sl@0: // from MStreamBuf
sl@0: 	void DoRelease();
sl@0: private:
sl@0: 	CBufBase* iBuf;
sl@0: 	};
sl@0: 
sl@0: NONSHARABLE_CLASS(CDbStoreTable::CCompressor) : public CBase, public CCluster::MAlter
sl@0: 	{
sl@0: public:
sl@0: 	inline CCompressor();
sl@0: 	~CCompressor();
sl@0: 	void ProcessL(CDbStoreTable* aTable);
sl@0: private:
sl@0: 	TUint8* AlterRecordL(TUint8* aWPtr,const TUint8* aRPtr,TInt aLength);
sl@0: private:
sl@0: 	CDbStoreTable* iTable;
sl@0: 	RDbRow iRow;
sl@0: 	};
sl@0: 
sl@0: // Class Huffman
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: //
sl@0: // recursive function to calculate the code lengths from the node tree
sl@0: //
sl@0: void Huffman::Lengths(TUint32* aLengths,const TNode* aNodes,TInt aNode,TInt aLen)
sl@0: 	{
sl@0: 	__ASSERT(aLen<KHuffMaxCodeLength);
sl@0: 	++aLen;
sl@0: 	const TNode& node=aNodes[aNode];
sl@0: 	if (node.iLeft&KLeaf)
sl@0: 		aLengths[node.iLeft&~KLeaf]=aLen;
sl@0: 	else
sl@0: 		Lengths(aLengths,aNodes,node.iLeft,aLen);
sl@0: 	if (node.iRight&KLeaf)
sl@0: 		aLengths[node.iRight&~KLeaf]=aLen;
sl@0: 	else
sl@0: 		Lengths(aLengths,aNodes,node.iRight,aLen);
sl@0: 	}
sl@0: 
sl@0: //
sl@0: // write the subtree below aPtr and return the head
sl@0: //
sl@0: TUint32* Huffman::SubTree(TUint32* aPtr,const TUint32* aValue,TUint32** aLevel)
sl@0: 	{
sl@0: 	TUint32* l=*aLevel++;
sl@0: 	if (l>aValue)
sl@0: 		{
sl@0: 		TUint32* sub1=SubTree(aPtr,aValue,aLevel);	// 0-tree first
sl@0: 		aPtr=SubTree(sub1,aValue-(aPtr-sub1)-1,aLevel);			// 1-tree
sl@0: 		TInt branch=(TUint8*)sub1-(TUint8*)aPtr;
sl@0: 		*--aPtr=branch;
sl@0: 		}
sl@0: 	else if (l==aValue)
sl@0: 		{
sl@0: 		TUint term0=*aValue--;						// 0-term
sl@0: 		aPtr=SubTree(aPtr,aValue,aLevel);			// 1-tree
sl@0: 		*--aPtr=term0>>16;
sl@0: 		}
sl@0: 	else	// l<iNext
sl@0: 		{
sl@0: 		TUint term0=*aValue--;						// 0-term
sl@0: 		TUint term1=*aValue--;
sl@0: 		*--aPtr=(term1>>16<<16)|(term0>>16);
sl@0: 		}
sl@0: 	return aPtr;
sl@0: 	}
sl@0: 
sl@0: //
sl@0: // Build a huffman encoding table from a symbol frequency table
sl@0: // aTable contains frequency data on input for aCodes symbols
sl@0: // aTable contains the huffman encoding on output
sl@0: //
sl@0: void Huffman::EncodingL(TUint32* aTable,TInt aCodes)
sl@0: 	{
sl@0: //
sl@0: // step 1. Sort the values into decreasing order of frequency
sl@0: //
sl@0: 	TLeaf* leaves=new(ELeave) TLeaf[aCodes];
sl@0: 	CleanupArrayDeletePushL(leaves);
sl@0: 	TInt lCount=0;
sl@0: 	TInt ii;
sl@0: 	for (ii=0;ii<aCodes;++ii)
sl@0: 		{
sl@0: 		TUint c=aTable[ii];
sl@0: 		if (c==0)
sl@0: 			continue;	// no coding for ii
sl@0: 		TInt jj;
sl@0: 		for (jj=0;jj<lCount;++jj)
sl@0: 			{
sl@0: 			if (leaves[jj].iCount<=c)
sl@0: 				break;
sl@0: 			}
sl@0: 		Mem::Move(leaves+jj+1,leaves+jj,sizeof(TLeaf)*(lCount-jj));
sl@0: 		leaves[jj].iCount=c;
sl@0: 		leaves[jj].iVal=THuff(ii|KLeaf);
sl@0: 		lCount++;
sl@0: 		}
sl@0: //
sl@0: // Huffman algorithm: pair off least frequent nodes and reorder
sl@0: // result is the code lengths in aTable[]
sl@0: //
sl@0: 	if (lCount==1)	// special case for a single value (always encode as "0")
sl@0: 		aTable[leaves[0].iVal&~KLeaf]=1;
sl@0: 	else if (lCount>1)
sl@0: 		{	//	don't encode for empty coding: leaves in order now
sl@0: 		TInt max=0;
sl@0: 		TNode* nodes=new(ELeave) TNode[lCount-1];
sl@0: 		while (--lCount>0)
sl@0: 			{
sl@0: 			TNode& node=nodes[max];
sl@0: 			node.iLeft=leaves[lCount-1].iVal;
sl@0: 			node.iRight=leaves[lCount].iVal;
sl@0: 			// re-order the leaves now to reflect new combined frequency
sl@0: 			TUint c=leaves[lCount-1].iCount+leaves[lCount].iCount;
sl@0: 			TInt jj=lCount;
sl@0: 			while (--jj>0)
sl@0: 				{
sl@0: 				if (leaves[jj-1].iCount>=c)
sl@0: 					break;
sl@0: 				}
sl@0: 			Mem::Move(leaves+jj+1,leaves+jj,sizeof(TLeaf)*(lCount-1-jj));
sl@0: 			// update new leaf
sl@0: 			leaves[jj].iCount=c;
sl@0: 			leaves[jj].iVal=THuff(max);
sl@0: 			max++;
sl@0: 			}
sl@0: 		Lengths(aTable,nodes,leaves[0].iVal,0);
sl@0: 		delete[] nodes;
sl@0: 		}
sl@0: 	CleanupStack::PopAndDestroy();		// leaves
sl@0: //
sl@0: // step 3: Generate the coding based on the code lengths
sl@0: //
sl@0: 	TInt lenCount[KHuffMaxCodeLength];
sl@0: 	Mem::FillZ(lenCount,sizeof(lenCount));
sl@0: 
sl@0: 	for (ii=aCodes;--ii>=0;)
sl@0: 		{
sl@0: 		TInt len=aTable[ii]-1;
sl@0: 		if (len>=0)
sl@0: 			++lenCount[len];
sl@0: 		}
sl@0: 
sl@0: 	TUint nextCode[KHuffMaxCodeLength];
sl@0: 	TUint code=0;
sl@0: 	for (ii=0;ii<KHuffMaxCodeLength;++ii)
sl@0: 		{
sl@0: 		nextCode[ii]=code;
sl@0: 		code=(code+lenCount[ii])<<1;
sl@0: 		}
sl@0: 
sl@0: 	for (ii=0;ii<aCodes;++ii)
sl@0: 		{
sl@0: 		TInt len=aTable[ii];
sl@0: 		if (len)
sl@0: 			{
sl@0: 			aTable[ii] = (nextCode[len-1]<<(KHuffMaxCodeLength-len))|(len<<KHuffMaxCodeLength);
sl@0: 			++nextCode[len-1];
sl@0: 			}
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: //
sl@0: // generate the decoding tree from the huffman code length data
sl@0: // output alphabet is [aBase,aBase+aCodes)
sl@0: //
sl@0: void Huffman::Decoding(TUint32* aDecoding,TInt aCodes,TInt aBase)
sl@0: 	{
sl@0: 	TInt counts[KHuffMaxCodeLength];
sl@0: 	Mem::FillZ(counts,sizeof(counts));
sl@0: 	TInt codes=0;
sl@0: 	TInt ii=aCodes;
sl@0: 	while (--ii>=0)
sl@0: 		{
sl@0: 		TUint len=aDecoding[ii];
sl@0: 		__ASSERT(len<=(TUint)KHuffMaxCodeLength);
sl@0: 		if (len)
sl@0: 			{
sl@0: 			++counts[len-1];
sl@0: 			++codes;
sl@0: 			}
sl@0: 		}
sl@0: //
sl@0: 	TUint32* level[KHuffMaxCodeLength];
sl@0: 	TUint32* lit=aDecoding+codes;
sl@0: 	for (ii=0;ii<KHuffMaxCodeLength;++ii)
sl@0: 		{
sl@0: 		level[ii]=lit;
sl@0: 		lit-=counts[ii];
sl@0: 		}
sl@0: 	aBase=(aBase<<17)+(KHuffTerminate<<16);
sl@0: 	for (ii=0;ii<aCodes;++ii)
sl@0: 		{
sl@0: 		TUint len=TUint8(aDecoding[ii]);
sl@0: 		if (len)
sl@0: 			*--level[len-1]|=(ii<<17)+aBase;
sl@0: 		}
sl@0: 	if (codes==1)	// codes==1 special case: tree is not complete
sl@0: 		*aDecoding>>=16;	// 0-terminate at root
sl@0: 	else if (codes>1)
sl@0: 		{
sl@0: 		__DEBUG(TUint32* p=) SubTree(aDecoding+codes-1,aDecoding+codes-1,level);
sl@0: 		__ASSERT(p==aDecoding);
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: // Class HDeflateHash
sl@0: 
sl@0: inline HDeflateHash::HDeflateHash()
sl@0: 	{TInt* p=iHash+256;do *--p=-KDeflateMaxDistance-1; while (p>iHash);}
sl@0: 
sl@0: inline HDeflateHash& HDeflateHash::NewLC(TInt aLinks)
sl@0: 	{
sl@0: 	__ASSERT(!(KDeflateMaxDistance&(KDeflateMaxDistance-1)));	// ensure power of two
sl@0: 	return *new(User::AllocLC(_FOFF(HDeflateHash,iOffset[Min(aLinks,KDeflateMaxDistance)]))) HDeflateHash;
sl@0: 	}
sl@0: 
sl@0: inline TInt HDeflateHash::Hash(const TUint8* aPtr)
sl@0: 	{
sl@0: 	TUint x=aPtr[0]|(aPtr[1]<<8)|(aPtr[2]<<16);
sl@0: 	return (x*KDeflateHashMultiplier)>>KDeflateHashShift;
sl@0: 	}
sl@0: 
sl@0: inline TInt HDeflateHash::First(const TUint8* aPtr,TInt aPos)
sl@0: 	{
sl@0: 	TInt h=Hash(aPtr);
sl@0: 	TInt offset=Min(aPos-iHash[h],KDeflateMaxDistance<<1);
sl@0: 	iHash[h]=aPos;
sl@0: 	iOffset[aPos&(KDeflateMaxDistance-1)]=TOffset(offset);
sl@0: 	return offset;
sl@0: 	}
sl@0: 
sl@0: inline TInt HDeflateHash::Next(TInt aPos,TInt aOffset) const
sl@0: 	{return aOffset+iOffset[(aPos-aOffset)&(KDeflateMaxDistance-1)];}
sl@0: 
sl@0: 
sl@0: // Class TDeflater
sl@0: //
sl@0: // generic deflation algorithm, can do either statistics and the encoder
sl@0: 
sl@0: TInt MDeflater::Match(const TUint8* aPtr,const TUint8* aEnd,TInt aPos,HDeflateHash& aHash)
sl@0: 	{
sl@0: 	TInt offset=aHash.First(aPtr,aPos);
sl@0: 	if (offset>KDeflateMaxDistance)
sl@0: 		return 0;
sl@0: 	TInt match=0;
sl@0: 	aEnd=Min(aEnd,aPtr+KDeflateMaxLength);
sl@0: 	TUint8 c=*aPtr;
sl@0: 	do
sl@0: 		{
sl@0: 		const TUint8* p=aPtr-offset;
sl@0: 		if (p[match>>16]==c)
sl@0: 			{	// might be a better match
sl@0: 			const TUint8* m=aPtr;
sl@0: 			for (;;)
sl@0: 				{
sl@0: 				if (*p++!=*m++)
sl@0: 					break;
sl@0: 				if (m<aEnd)
sl@0: 					continue;
sl@0: 				return ((m-aPtr)<<16)|offset;
sl@0: 				}
sl@0: 			TInt l=m-aPtr-1;
sl@0: 			if (l>match>>16)
sl@0: 				{
sl@0: 				match=(l<<16)|offset;
sl@0: 				c=m[-1];
sl@0: 				}
sl@0: 			}
sl@0: 		offset=aHash.Next(aPos,offset);
sl@0: 		} while (offset<=KDeflateMaxDistance);
sl@0: 	return match;
sl@0: 	}
sl@0: 
sl@0: //
sl@0: // Apply the deflation algorithm to the data [aBase,aEnd)
sl@0: // Return a pointer after the last byte that was deflated (which may not be aEnd)
sl@0: //
sl@0: const TUint8* MDeflater::DoDeflateL(const TUint8* aBase,const TUint8* aEnd,HDeflateHash& aHash)
sl@0: 	{
sl@0: 	__ASSERT(aEnd-aBase>KDeflateMinLength);
sl@0: //
sl@0: 	const TUint8* ptr=aBase;
sl@0: #ifdef __EXTRA_DEFLATE
sl@0: 	TInt prev=0;		// the previous deflation match
sl@0: #endif
sl@0: 	do
sl@0: 		{
sl@0: 		TInt match=Match(ptr,aEnd,ptr-aBase,aHash);
sl@0: #ifdef __EXTRA_DEFLATE
sl@0: // Extra deflation applies two optimisations which double the time taken
sl@0: // 1. If we have a match at p, then test for a better match at p+1 before using it
sl@0: // 2. When we have a match, add the hash links for all the data which will be skipped 
sl@0: 		if (match>>16 < prev>>16)
sl@0: 			{	// use the previous match--it was better
sl@0: 			TInt len=prev>>16;
sl@0: 			SegmentL(len,prev-(len<<16));
sl@0: 			// fill in missing hash entries for better compression
sl@0: 			const TUint8* e=ptr+len-2;
sl@0: 			do
sl@0: 				{
sl@0: 				++ptr;
sl@0: 				aHash.First(ptr,ptr-aBase);
sl@0: 				} while (ptr<e);
sl@0: 			prev=0;
sl@0: 			}
sl@0: 		else if (match<=(KDeflateMinLength<<16))
sl@0: 			LitLenL(*ptr);			// no deflation match here
sl@0: 		else
sl@0: 			{	// save this match and test the next position
sl@0: 			if (prev)	// we had a match at ptr-1, but this is better
sl@0: 				LitLenL(ptr[-1]);
sl@0: 			prev=match;
sl@0: 			}
sl@0: 		++ptr;
sl@0: #else
sl@0: // Basic deflation will store any match found, and not update the hash links for the
sl@0: // data which is skipped
sl@0: 		if (match<=(KDeflateMinLength<<16))		// no match
sl@0: 			LitLenL(*ptr++);
sl@0: 		else
sl@0: 			{	// store the match
sl@0: 			TInt len=match>>16;
sl@0: 			SegmentL(len,match-(len<<16));
sl@0: 			ptr+=len;
sl@0: 			}
sl@0: #endif
sl@0: 		} while (ptr+KDeflateMinLength-1<aEnd);
sl@0: #ifdef __EXTRA_DEFLATE
sl@0: 	if (prev)
sl@0: 		{		// emit the stored match
sl@0: 		TInt len=prev>>16;
sl@0: 		SegmentL(len,prev-(len<<16));
sl@0: 		ptr+=len-1;
sl@0: 		}
sl@0: #endif
sl@0: 	return ptr;
sl@0: 	}
sl@0: 
sl@0: //
sl@0: // The generic deflation algorithm
sl@0: //
sl@0: void MDeflater::DeflateL(const TUint8* aBase,TInt aLength)
sl@0: 	{
sl@0: 	const TUint8* end=aBase+aLength;
sl@0: 	if (aLength>KDeflateMinLength)
sl@0: 		{	// deflation kicks in if there is enough data
sl@0: 		HDeflateHash& hash=HDeflateHash::NewLC(aLength);
sl@0: 		aBase=DoDeflateL(aBase,end,hash);
sl@0: 		CleanupStack::PopAndDestroy();
sl@0: 		}
sl@0: 	while (aBase<end)					// emit remaining bytes
sl@0: 		LitLenL(*aBase++);
sl@0: 	LitLenL(CDbStoreCompression::TEncoding::EEos);	// eos marker
sl@0: 	}
sl@0: 
sl@0: //
sl@0: // Turn a (length,offset) pair into the deflation codes+extra bits before calling
sl@0: // the specific LitLen(), Offset() and Extra() functions.
sl@0: //
sl@0: void MDeflater::SegmentL(TInt aLength,TInt aDistance)
sl@0: 	{
sl@0: 	__ASSERT(aLength>=KDeflateMinLength && aLength<=KDeflateMaxLength);
sl@0: 	aLength-=KDeflateMinLength;
sl@0: 	TInt extralen=0;
sl@0: 	TUint len=aLength;
sl@0: 	while (len>=8)
sl@0: 		{
sl@0: 		++extralen;
sl@0: 		len>>=1;
sl@0: 		}
sl@0: 	__ASSERT((extralen<<2)+len<CDbStoreCompression::TEncoding::ELengths);
sl@0: 	LitLenL((extralen<<2)+len+CDbStoreCompression::TEncoding::ELiterals);
sl@0: 	if (extralen)
sl@0: 		ExtraL(extralen,TUint(aLength)<<(32-extralen));
sl@0: //
sl@0: 	__ASSERT(aDistance>0 && aDistance<=KDeflateMaxDistance);
sl@0: 	aDistance--;
sl@0: 	extralen=0;
sl@0: 	TUint dist=aDistance;
sl@0: 	while (dist>=8)
sl@0: 		{
sl@0: 		++extralen;
sl@0: 		dist>>=1;
sl@0: 		}
sl@0: 	__ASSERT((extralen<<2)+dist<CDbStoreCompression::TEncoding::EDistances);
sl@0: 	OffsetL((extralen<<2)+dist);
sl@0: 	if (extralen)
sl@0: 		ExtraL(extralen,TUint(aDistance)<<(32-extralen));
sl@0: 	}
sl@0: 
sl@0: // Class TDeflateStats
sl@0: //
sl@0: // This class analyses the data stream to generate the frequency tables 
sl@0: // for the deflation algorithm
sl@0: 
sl@0: inline TDeflateStats::TDeflateStats(CDbStoreCompression::TEncoding& aEncoding)
sl@0: 	:iEncoding(aEncoding)
sl@0: 	{}
sl@0: 
sl@0: void TDeflateStats::LitLenL(TInt aCode)
sl@0: 	{
sl@0: 	++iEncoding.iLitLen[aCode];
sl@0: 	}
sl@0: 
sl@0: void TDeflateStats::OffsetL(TInt aCode)
sl@0: 	{
sl@0: 	++iEncoding.iDistance[aCode];
sl@0: 	}
sl@0: 
sl@0: void TDeflateStats::ExtraL(TInt,TUint)
sl@0: 	{}
sl@0: 
sl@0: // Class THuffEncoder
sl@0: //
sl@0: // This class generates the byte stream of huffman codes, writing them out to the stream
sl@0: 
sl@0: THuffEncoder::THuffEncoder(RWriteStream& aStream)
sl@0: 	:iStream(aStream),iCode(0),iBits(-8),iWrite(iBuf)
sl@0: 	{}
sl@0: 
sl@0: //
sl@0: // Store a huffman code generated by Huffman::EncodingL()
sl@0: //
sl@0: void THuffEncoder::EncodeL(TUint32 aHuffCode)
sl@0: 	{
sl@0: 	EncodeL(aHuffCode<<(32-KHuffMaxCodeLength),aHuffCode>>KHuffMaxCodeLength);
sl@0: 	}
sl@0: 
sl@0: //
sl@0: // Store aLength bits from the most significant bits of aCode
sl@0: //
sl@0: void THuffEncoder::EncodeL(TUint aCode,TInt aLength)
sl@0: 	{
sl@0: 	TInt bits=iBits;
sl@0: 	TUint code=iCode|(aCode>>(bits+8));
sl@0: 	bits+=aLength;
sl@0: 	if (bits>=0)
sl@0: 		{
sl@0: 		TUint8* write=iWrite;
sl@0: 		do
sl@0: 			{
sl@0: 			if (write-EBufSize==iBuf)
sl@0: 				{
sl@0: 				iStream.WriteL(iBuf,EBufSize);
sl@0: 				write=iBuf;
sl@0: 				}
sl@0: 			*write++=TUint8(code>>24);
sl@0: 			code<<=8;
sl@0: 			bits-=8;
sl@0: 			} while (bits>=0);
sl@0: 		iWrite=write;
sl@0: 		}
sl@0: 	iCode=code;
sl@0: 	iBits=bits;
sl@0: 	}
sl@0: 
sl@0: //
sl@0: // Terminate the huffman coding. The longest code is always 1111111111
sl@0: //
sl@0: void THuffEncoder::CompleteL()
sl@0: 	{
sl@0: 	if (iBits>-8)
sl@0: 		EncodeL(0xffffffffu,-iBits);
sl@0: 	if (iWrite>iBuf)
sl@0: 		iStream.WriteL(iBuf,iWrite-iBuf);
sl@0: 	}
sl@0: 
sl@0: // Class TDeflater
sl@0: //
sl@0: // Extends MDeflater to provide huffman encoding of the output
sl@0: 
sl@0: //
sl@0: // construct for encoding
sl@0: //
sl@0: inline TDeflater::TDeflater(THuffEncoder& aEncoder,const CDbStoreCompression::TEncoding& aEncoding)
sl@0: 	:iEncoder(aEncoder),iEncoding(aEncoding)
sl@0: 	{}
sl@0: 
sl@0: void TDeflater::LitLenL(TInt aCode)
sl@0: 	{
sl@0: 	iEncoder.EncodeL(iEncoding.iLitLen[aCode]);
sl@0: 	}
sl@0: 
sl@0: void TDeflater::OffsetL(TInt aCode)
sl@0: 	{
sl@0: 	iEncoder.EncodeL(iEncoding.iDistance[aCode]);
sl@0: 	}
sl@0: 
sl@0: void TDeflater::ExtraL(TInt aLen,TUint aBits)
sl@0: 	{
sl@0: 	iEncoder.EncodeL(aBits,aLen);
sl@0: 	}
sl@0: 
sl@0: // Class TInflater
sl@0: //
sl@0: // The inflation algorithm, complete with huffman decoding
sl@0: 
sl@0: TInflater::TInflater(const TUint8* aIn,const CDbStoreCompression::TEncoding& aEncoding)
sl@0: 	:iIn(aIn),iBits(KBitsInit),iLen(0),iLitLenTree(aEncoding.iLitLen),iDistTree(aEncoding.iDistance)
sl@0: 	{}
sl@0: 
sl@0: //
sl@0: // consume all data lag in the history buffer, then decode to fill up the output buffer
sl@0: //
sl@0: TInt TInflater::Inflate()
sl@0: 	{
sl@0: // empty the history buffer into the output
sl@0: 	const TUint8* data=iIn;
sl@0: 	TUint bits=iBits;
sl@0: 	const TUint8* from=iRptr;
sl@0: 	TInt len=iLen;
sl@0: 	TUint8* out=iOut;
sl@0: 	TUint8* const end=out+KDeflateMaxDistance;
sl@0: 	const TUint32* node;
sl@0: 	if (len)
sl@0: 		goto useHistory;
sl@0: //
sl@0: 	if (bits&KBitsEOF)
sl@0: 		return 0;
sl@0: //
sl@0: 	node=iLitLenTree;
sl@0: 	while (out<end)
sl@0: 		{
sl@0: 		// get a huffman code
sl@0: 		{
sl@0: 		TUint huff;
sl@0: 		for (;;)
sl@0: 			{
sl@0: 			huff=*node++;
sl@0: 			if ((bits<<=1)&KBitsEmpty)
sl@0: 				bits=*data++|KBitsFull;
sl@0: 			if (bits&KBitsNext)
sl@0: 				{
sl@0: 				if (huff&(KHuffTerminate<<16))
sl@0: 					break;
sl@0: 				}
sl@0: 			else
sl@0: 				{
sl@0: 				if (huff&KHuffTerminate)
sl@0: 					{
sl@0: 					huff<<=16;
sl@0: 					break;
sl@0: 					}
sl@0: 				else
sl@0: 					node=PtrAdd(node,huff);
sl@0: 				}
sl@0: 			}
sl@0: 		TInt val=TInt(huff>>17)-CDbStoreCompression::TEncoding::ELiterals;
sl@0: 		if (val<0)
sl@0: 			{
sl@0: 			*out++=TUint8(val);
sl@0: 			node=iLitLenTree;
sl@0: 			continue;			// another literal/length combo
sl@0: 			}
sl@0: 		if (val==CDbStoreCompression::TEncoding::EEos-CDbStoreCompression::TEncoding::ELiterals)
sl@0: 			{	// eos marker. we're done
sl@0: 			bits=KBitsEOF;
sl@0: 			break;
sl@0: 			}
sl@0: 		// get the extra bits for the code
sl@0: 		TInt code=val&0xff;
sl@0: 		if (code>=8)
sl@0: 			{	// xtra bits
sl@0: 			TInt xtra=(code>>2)-1;
sl@0: 			code-=xtra<<2;
sl@0: 			do
sl@0: 				{
sl@0: 				if ((bits<<=1)&KBitsEmpty)
sl@0: 					bits=*data++|KBitsFull;
sl@0: 				code<<=1;
sl@0: 				if (bits&KBitsNext)
sl@0: 					code|=1;
sl@0: 				} while (--xtra!=0);
sl@0: 			}
sl@0: 		if (val<KDeflateDistCodeBase-CDbStoreCompression::TEncoding::ELiterals)
sl@0: 			{	// length code... get the code
sl@0: 			len=code+KDeflateMinLength;
sl@0: 			__ASSERT(len<=KDeflateMaxLength);
sl@0: 			node=iDistTree;
sl@0: 			continue;			// read the huffman code
sl@0: 			}
sl@0: 		// distance code
sl@0: 		__ASSERT(code<KDeflateMaxDistance);
sl@0: 		from=out-(code+1);
sl@0: 		if (from+KDeflateMaxDistance<end)
sl@0: 			from+=KDeflateMaxDistance;
sl@0: 		}
sl@0: useHistory:
sl@0: 		TInt tfr=Min(end-out,len);
sl@0: 		len-=tfr;
sl@0: 		do
sl@0: 			{
sl@0: 			*out++=*from++;
sl@0: 			if (from==end)
sl@0: 				from-=KDeflateMaxDistance;
sl@0: 			} while (--tfr!=0);
sl@0: 		node=iLitLenTree;
sl@0: 		};
sl@0: 	iIn=data;
sl@0: 	iBits=bits;
sl@0: 	iRptr=from;
sl@0: 	iLen=len;
sl@0: 	return out-iOut;
sl@0: 	}
sl@0: 
sl@0: inline const TUint8* TInflater::Ptr() const
sl@0: 	{return iOut;}
sl@0: inline TInt TInflater::BufferSize()
sl@0: 	{return KDeflateMaxDistance;}
sl@0: 
sl@0: // Class HDeflateBuf
sl@0: //
sl@0: // This stream buffer applies the analysis or deflation and huffman coding
sl@0: // on the entire stream data when it is committed
sl@0: 
sl@0: inline HDeflateBuf::HDeflateBuf(MStreamBuf* aHost,CDbStoreCompression::TEncoding& aEncoding,CBufBase* aBuf,TMode aMode)
sl@0: 	:iHost(aHost),iEncoding(aEncoding),iBuf(aBuf),iMode(aMode)
sl@0: 	{Set(*aBuf,0);}
sl@0: 
sl@0: HDeflateBuf* HDeflateBuf::NewL(MStreamBuf* aHost,CDbStoreCompression::TEncoding& aEncoding,TMode aMode)
sl@0: 	{
sl@0: 	CBufBase* buf=CBufFlat::NewL(512);
sl@0: 	CleanupStack::PushL(buf);
sl@0: 	HDeflateBuf* self=new(ELeave) HDeflateBuf(aHost,aEncoding,buf,aMode);
sl@0: 	CleanupStack::Pop();
sl@0: 	return self;
sl@0: 	}
sl@0: 
sl@0: inline HDeflateBuf::~HDeflateBuf()
sl@0: 	{delete iBuf;iHost.Release();}
sl@0: 
sl@0: void HDeflateBuf::DoRelease()
sl@0: 	{
sl@0: 	delete this;
sl@0: 	}
sl@0: 
sl@0: //
sl@0: // This is where it all happens
sl@0: //
sl@0: void HDeflateBuf::DoSynchL()
sl@0: 	{
sl@0: 	if (iMode==EAnalysis)
sl@0: 		{
sl@0: 		TDeflateStats deflater(iEncoding);
sl@0: 		deflater.DeflateL(iBuf->Ptr(0).Ptr(),iBuf->Size());
sl@0: 		}
sl@0: 	else
sl@0: 		{
sl@0: 		THuffEncoder encoder(iHost);
sl@0: 		TDeflater deflater(encoder,iEncoding);
sl@0: 		deflater.DeflateL(iBuf->Ptr(0).Ptr(),iBuf->Size());
sl@0: 		encoder.CompleteL();
sl@0: 		iHost.CommitL();
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: // Class HInflateBuf
sl@0: //
sl@0: // Inflate the input stream. This is not a filter, it reads all the input, inflates it and
sl@0: // keeps it in a memory buffer.
sl@0: 
sl@0: const TInt KInflateBufSize=0x800;	// 2K
sl@0: 
sl@0: HInflateBuf::HInflateBuf(CBufBase* aBuf)
sl@0: 	:iBuf(aBuf)
sl@0: 	{
sl@0: 	Set(*aBuf,0,ERead);
sl@0: 	}
sl@0: 
sl@0: inline HInflateBuf::~HInflateBuf()
sl@0: 	{delete iBuf;}
sl@0: 
sl@0: void HInflateBuf::DoRelease()
sl@0: 	{
sl@0: 	delete this;
sl@0: 	}
sl@0: 
sl@0: HInflateBuf* HInflateBuf::NewL(MStreamBuf* aHost,const CDbStoreCompression::TEncoding& aEncoding)
sl@0: 	{
sl@0: 	CBufFlat* host=CBufFlat::NewL(256);
sl@0: 	CleanupStack::PushL(host);
sl@0: 	TUint8 buffer[KInflateBufSize];
sl@0: 	for (;;)
sl@0: 		{
sl@0: 		TInt len=aHost->ReadL(buffer,KInflateBufSize);
sl@0: 		if (len)
sl@0: 			host->InsertL(host->Size(),buffer,len);
sl@0: 		if (len<KInflateBufSize)
sl@0: 			break;
sl@0: 		}
sl@0: 	CBufSeg* out=CBufSeg::NewL(256);
sl@0: 	CleanupStack::PushL(out);
sl@0: 	TInflater* inflater=new(ELeave) TInflater(host->Ptr(0).Ptr(),aEncoding);
sl@0: 	CleanupStack::PushL(inflater);
sl@0: 	for (;;)
sl@0: 		{
sl@0: 		TInt len=inflater->Inflate();
sl@0: 		if (len)
sl@0: 			out->InsertL(out->Size(),inflater->Ptr(),len);
sl@0: 		if (len<inflater->BufferSize())
sl@0: 			break;
sl@0: 		}
sl@0: 	HInflateBuf* buf=new(ELeave) HInflateBuf(out);
sl@0: 	CleanupStack::PopAndDestroy();	// inflater
sl@0: 	CleanupStack::Pop();			// out
sl@0: 	CleanupStack::PopAndDestroy();	// host
sl@0: 	aHost->Release();				// don't need this anymore
sl@0: 	return buf;
sl@0: 	}
sl@0: 
sl@0: // Class CDbStoreTable::Compressor
sl@0: //
sl@0: // This class processes an entire table for analysis or compression, using the
sl@0: // CDbStoreRecords::AlterL() functionality and call back to ensure that all clusters
sl@0: // and BLOBs are read and written.
sl@0: 
sl@0: inline CDbStoreTable::CCompressor::CCompressor()
sl@0: 	{}
sl@0: 
sl@0: CDbStoreTable::CCompressor::~CCompressor()
sl@0: 	{
sl@0: 	if (iTable)
sl@0: 		iTable->Close();
sl@0: 	iRow.Close();
sl@0: 	}
sl@0: 
sl@0: //
sl@0: // Walk through every cluster in the table
sl@0: //
sl@0: void CDbStoreTable::CCompressor::ProcessL(CDbStoreTable* aTable)
sl@0: 	{
sl@0: 	iTable=aTable;
sl@0: 	CDbStoreRecords& rec=aTable->StoreRecordsL();
sl@0: 	for (TClusterId cluster=rec.Head();cluster!=KNullClusterId;cluster=rec.AlterL(cluster,*this))
sl@0: 		;
sl@0: 	}
sl@0: 
sl@0: //
sl@0: // Compress every blob, and transfer the record from aRPtr to aWPtr
sl@0: //
sl@0: TUint8* CDbStoreTable::CCompressor::AlterRecordL(TUint8* aWPtr,const TUint8* aRPtr,TInt aLength)
sl@0: 	{
sl@0: 	if (iTable->Def().Columns().HasLongColumns())
sl@0: 		{
sl@0: 		iTable->CopyToRowL(iRow,TPtrC8(aRPtr,aLength));
sl@0: 		CDbBlobSpace* blobs=iTable->BlobsL();
sl@0: 		TDbColNo col=1;
sl@0: 		HDbColumnSet::TIteratorC iter=iTable->Def().Columns().Begin();
sl@0: 		const HDbColumnSet::TIteratorC end=iTable->Def().Columns().End();
sl@0: 		do
sl@0: 			{
sl@0: 			if (!TDbCol::IsLong(iter->Type()))
sl@0: 				continue;
sl@0: 			TDbBlob& blob=CONST_CAST(TDbBlob&,TDbColumnC(iRow,col).Blob());
sl@0: 			if (blob.IsInline())
sl@0: 				continue;
sl@0: 			// do what has to be done...?
sl@0: 			TUint8* data=(TUint8*)User::AllocLC(blob.Size());
sl@0: 			blobs->ReadLC(blob.Id(),iter->Type())->ReadL(data,blob.Size());
sl@0: 			CleanupStack::PopAndDestroy();	// stream buffer
sl@0: 			// re-write the Blob to compress it
sl@0: 			blobs->DeleteL(blob.Id());
sl@0: 			blob.SetId(blobs->CreateL(iter->Type(),data,blob.Size()));
sl@0: 			CleanupStack::PopAndDestroy();	// data
sl@0: 			} while (++col,++iter<end);
sl@0: 		iTable->CopyFromRow(aWPtr,iRow);
sl@0: 		}
sl@0: 	else
sl@0: 		Mem::Copy(aWPtr,aRPtr,aLength);
sl@0: 	return aWPtr+aLength;
sl@0: 	}
sl@0: 
sl@0: // Class CDbStoreCompression
sl@0: //
sl@0: // This class manages the compression for the database, applying filters as appropriate
sl@0: // It also defines the extrenalisation format for the huffman trees
sl@0: 
sl@0: const TInt KDeflationCodes=3*(CDbStoreCompression::TEncoding::ELitLens+CDbStoreCompression::TEncoding::EDistances);
sl@0: 
sl@0: inline CDbStoreCompression::CDbStoreCompression()
sl@0: //	:iState(EAnalysis)
sl@0: 	{}
sl@0: 
sl@0: CDbStoreCompression* CDbStoreCompression::NewL()
sl@0: 	{
sl@0: 	return new(ELeave) CDbStoreCompression;
sl@0: 	}
sl@0: 
sl@0: //
sl@0: // Build huffman codings from the freqeuncy tables
sl@0: //
sl@0: void CDbStoreCompression::EncodeL()
sl@0: 	{
sl@0: 	//Check the comments in CDbStoreCompression::InternalizeL().
sl@0: 	//The implementation there is very similar to this one and is commented why the "array overrun" 
sl@0: 	//case is impossible.
sl@0: 	__ASSERT(iState==EAnalysis);
sl@0: 	TUint32* p=iEncoding[0].iLitLen;
sl@0: 	TUint32* end=p+KDeflationCodes;
sl@0: 	do
sl@0: 		{
sl@0: 		Huffman::EncodingL(p,TEncoding::ELitLens);
sl@0: 		p+=TEncoding::ELitLens;
sl@0: 		//coverity[overrun-local]
sl@0: 		Huffman::EncodingL(p,TEncoding::EDistances);
sl@0: 		//coverity[overrun-local]
sl@0: 		p+=TEncoding::EDistances;
sl@0: 		} while (p<end);
sl@0: 	iState=EEncoding;
sl@0: 	}
sl@0: 
sl@0: //
sl@0: // Store the encoding tables as a sequence of code lengths
sl@0: // The code lengths (0-25) are themselves huffman coded, and the meta coding is stored first
sl@0: //
sl@0: void CDbStoreCompression::ExternalizeL(RWriteStream& aStream) const
sl@0: 	{
sl@0: 	__ASSERT(iState==EEncoding);
sl@0: 	const TUint32* base=iEncoding[0].iLitLen;
sl@0: 	const TUint32* end=base+KDeflationCodes;
sl@0: 	TUint32 codes[KDeflateMetaCodes];
sl@0: 	Mem::FillZ(codes,sizeof(codes));
sl@0: 	const TUint32* p=base;
sl@0: 	do ++codes[*p++>>KHuffMaxCodeLength]; while (p<end);
sl@0: 	Huffman::EncodingL(codes,KDeflateMetaCodes);
sl@0: // save the meta encoding
sl@0: 	p=codes+KDeflateMetaCodes;
sl@0: 	do
sl@0: 		{
sl@0: 		TUint c0=*--p;
sl@0: 		TUint c1=*--p;
sl@0: 		c0>>=KHuffMaxCodeLength;
sl@0: 		c1>>=KHuffMaxCodeLength;
sl@0: 		aStream.WriteUint8L((c0<<4)|c1);
sl@0: 		} while (p>codes);
sl@0: // write the encoding
sl@0: 	THuffEncoder encoder(aStream);
sl@0: 	p=base;
sl@0: 	do encoder.EncodeL(codes[*p++>>KHuffMaxCodeLength]); while (p<end);
sl@0: 	encoder.CompleteL();
sl@0: 	}
sl@0: 
sl@0: //
sl@0: // Internalize a previous saved encoding
sl@0: //
sl@0: void CDbStoreCompression::InternalizeL(RReadStream& aStream)
sl@0: 	{
sl@0: 	__ASSERT(iState!=EEncoding);
sl@0: //
sl@0: // read the meta encoding
sl@0: 	TUint32 decode[KDeflateMetaCodes];
sl@0: 	TUint32* p=decode+KDeflateMetaCodes;
sl@0: 	do
sl@0: 		{
sl@0: 		TUint8 c=aStream.ReadUint8L();
sl@0: 		*--p=c>>4;
sl@0: 		*--p=c&0xf;
sl@0: 		} while (p>decode);
sl@0: 	Huffman::Decoding(decode,KDeflateMetaCodes);
sl@0: // decode the encoding
sl@0: 	p=iEncoding[0].iLitLen;
sl@0: 	TUint32* end=p+KDeflationCodes;
sl@0: 	TUint bits=KBitsInit;
sl@0: 	do
sl@0: 		{
sl@0: 		const TUint32* node=decode;
sl@0: 		TUint huff;
sl@0: 		for (;;)
sl@0: 			{
sl@0: 			huff=*node++;
sl@0: 			if ((bits<<=1)&KBitsEmpty)
sl@0: 				bits=aStream.ReadUint8L()|KBitsFull;
sl@0: 			if (bits&KBitsNext)
sl@0: 				{
sl@0: 				if (huff&(KHuffTerminate<<16))
sl@0: 					break;
sl@0: 				}
sl@0: 			else
sl@0: 				{
sl@0: 				if (huff&KHuffTerminate)
sl@0: 					{
sl@0: 					huff<<=16;
sl@0: 					break;
sl@0: 					}
sl@0: 				else
sl@0: 					node=PtrAdd(node,huff);
sl@0: 				}
sl@0: 			}
sl@0: 		*p++=huff>>17;
sl@0: 		} while (p<end);
sl@0: // convert the length tables into huffman decoding trees
sl@0: 	//The iEncoding data member is an array of 3 elements of TEncoding type.
sl@0: 	//The TEncoding layout is: TUint32 iLitLen[ELitLens], TUint32 iDistance[EDistances].
sl@0: 	//Then the in-memory presentation of iEncoding is:
sl@0: 	//               ELitLens     EDistances
sl@0: 	//iEncoding[0]   ........     ........ 
sl@0: 	//iEncoding[1]   ........     ........ 
sl@0: 	//iEncoding[2]   ........     ........
sl@0: 	//
sl@0: 	//Bellow, in the loop:
sl@0: 	// p+=TEncoding::ELitLens;   - moves the pointer to the beginning of iDistance data
sl@0: 	// p+=TEncoding::EDistances; - moves the pointer to the beginning of iLitLen data of the next element of iEncoding.
sl@0: 	//The loop will process the data until "p<end", and "end" is defined as:
sl@0: 	// p=iEncoding[0].iLitLen;
sl@0: 	// TUint32* end=p+KDeflationCodes;
sl@0: 	//KDeflationCodes value is: 3*(CDbStoreCompression::TEncoding::ELitLens+CDbStoreCompression::TEncoding::EDistances),
sl@0: 	//so that is the end of the iEncoding array.
sl@0: 	//Conclusion: the code incrementing the "p" pointer in the loop bellow won't cause array overrun. 
sl@0: 	p=iEncoding[0].iLitLen;
sl@0: 	do
sl@0: 		{
sl@0: 		Huffman::Decoding(p,TEncoding::ELitLens);
sl@0: 		p+=TEncoding::ELitLens;
sl@0: 		//coverity[overrun-local]
sl@0: 		Huffman::Decoding(p,TEncoding::EDistances,KDeflateDistCodeBase);
sl@0: 		//coverity[overrun-local]
sl@0: 		p+=TEncoding::EDistances;
sl@0: 		} while (p<end);
sl@0: 	if (iState==EAnalysis)
sl@0: 		iState=EDecoding;
sl@0: 	}
sl@0: 
sl@0: //
sl@0: // Apply an inflation filter to a read stream
sl@0: //
sl@0: MStreamBuf* CDbStoreCompression::FilterL(MStreamBuf* aHost,TUint32,RDbStoreReadStream::TType aType)
sl@0: 	{
sl@0: 	if (iState==EDecoding || iState==EInflating)
sl@0: 		return HInflateBuf::NewL(aHost,iEncoding[aType]);
sl@0: 	return aHost;
sl@0: 	}
sl@0: 
sl@0: //
sl@0: // Apply a statistics or inflation filter to a write stream
sl@0: //
sl@0: MStreamBuf* CDbStoreCompression::FilterL(MStreamBuf* aHost,TUint32,RDbStoreWriteStream::TType aType)
sl@0: 	{
sl@0: 	TState s=iState;
sl@0: 	if (s==EDecoding)
sl@0: 		__LEAVE(KErrWrite);		// read-only database
sl@0: 	else if (s!=EInflating)
sl@0: 		{
sl@0: 		__ASSERT(TInt(EAnalysis)==TInt(HDeflateBuf::EAnalysis));
sl@0: 		__ASSERT(TInt(EEncoding)==TInt(HDeflateBuf::EDeflate));
sl@0: 		return HDeflateBuf::NewL(aHost,iEncoding[aType],HDeflateBuf::TMode(s));
sl@0: 		}
sl@0: 	return aHost;
sl@0: 	}
sl@0: 
sl@0: // Class CDbStoreDatabase
sl@0: //
sl@0: // Compression related code is maintained in this source file
sl@0: 
sl@0: //
sl@0: // Iterate across all tables applying analysis or compression to them
sl@0: //
sl@0: void CDbStoreDatabase::CompressTablesL()
sl@0: 	{
sl@0: 	TSglQueIterC<CDbStoreDef> iter(SchemaL());
sl@0: 	const CDbStoreDef* def;
sl@0: 	while ((def=iter++)!=0)
sl@0: 		{
sl@0: 		CDbStoreTable::CCompressor* comp=new(ELeave) CDbStoreTable::CCompressor;
sl@0: 		CleanupStack::PushL(comp);
sl@0: 		comp->ProcessL(STATIC_CAST(CDbStoreTable*,TableL(*def)));
sl@0: 		CleanupStack::PopAndDestroy();	// comp
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: //
sl@0: // Compress or decompress the whole database
sl@0: //
sl@0: void CDbStoreDatabase::CompressL(TStreamId aStreamId,TZipType aZip)
sl@0: 	{
sl@0: 	__ASSERT(iStore);
sl@0: 	iSchemaId=aStreamId;
sl@0: // read the databse header for encryption information
sl@0: 	RStoreReadStream strm;
sl@0: 	strm.OpenLC(Store(),aStreamId);
sl@0: 	ReadHeaderL(strm);
sl@0: 	CleanupStack::PopAndDestroy();	// strm
sl@0: 	InitPagePoolL();
sl@0: //
sl@0: 	if (iVersion==EDbStoreCompressed)
sl@0: 		{
sl@0: 		iCompression->Inflate();
sl@0: 		if (aZip==EDeflate)
sl@0: 			__LEAVE(KErrArgument);		// already compressed
sl@0: 		}
sl@0: 	else if (aZip==EInflate)
sl@0: 		__LEAVE(KErrArgument);		// not compressed
sl@0: 	else
sl@0: 		{	// deflate pass #1: analyse the database
sl@0: 		CompressionL();				// construct the compression filter
sl@0: 		Transaction().DDLBeginLC();
sl@0: 		CompressTablesL();
sl@0: 		iClusterCache->FlushL();		// force through the stats buffer
sl@0: 		ReplaceSchemaL();				// force through the stats buffer
sl@0: 		CleanupStack::PopAndDestroy();	// rollback after analysis!
sl@0: 		iCompression->EncodeL();
sl@0: 		}
sl@0: // now inflate or deflate the data
sl@0: 	Transaction().DDLBeginLC();
sl@0: 	CompressTablesL();
sl@0: 	iVersion=TUint8(aZip==EDeflate ? EDbStoreCompressed : EDbStoreVersion2);
sl@0: 	Transaction().DDLCommitL();
sl@0: 	CleanupStack::Pop();		// rollback not required
sl@0: 	}
sl@0: 
sl@0: void CDbStoreDatabase::CompressL(CStreamStore* aStore,TStreamId aStreamId,TZipType aZip)
sl@0: 	{
sl@0: 	//It looks like there is a potential memory leak in the next 4 lines of code, because:
sl@0: 	//1) CDbStoreDatabase* self=NewLC(aStore) - new CDbStoreDatabase object is created on the heap
sl@0: 	//2) CDbObject* db=self->InterfaceL() - new CDbObject is created on the heap 
sl@0: 	//3) CleanupStack::Pop() - the CDbStoreDatabase object from (1) - out from the cleanup stack
sl@0: 	//4) db->PushL() - the CDbObject from (2) - in the cleanup stack
sl@0: 	//If one of the DDLPrepareL() or CompressL() leaves, looks like the CDbStoreDatabase object from (1) will be leaked.
sl@0: 	//This is not a correct guess, becuse:
sl@0: 	// -  CDbObject* db=self->InterfaceL() - this call creates a new CInterface object 
sl@0: 	//                                       on the heap. The CInterface() constructor will store the "this" pointer 
sl@0: 	//                                       passed from the InterfaceL() (so the "self" pointer),
sl@0: 	//	                                     into its "iDatabase" private data member.
sl@0: 	//                                       In which case, the returned CDbObject, of CInterface type, will have
sl@0: 	//                                       its "iDatabase" data member initialized.
sl@0: 	//                                       The inheritance tree is:
sl@0: 	//                                           CBase <-- CDbObject <-- CDbDatabase <-- CInterface
sl@0: 	// - db->PushL() - this call puts on the cleanup stack CDbObject::Destroy().
sl@0: 	//                                       The "db" object which real type is CInterface with "iDatabase" data member
sl@0: 	//                                       initialized with "self", is on the cleanup stack.
sl@0: 	// - If one of the next "L" functions leaves, then CDbObject::Destroy() will be executed.
sl@0: 	// - CDbObject::Destroy() will call CInterface::~CInterface() - CBase is at the root of the inheritance tree, with
sl@0: 	//                                       virtual ~CBase() destructor.
sl@0: 	// - CInterface::~CInterface() implementation calls Database().Close(), so that is CDbStoreDatabase::Close() called on 
sl@0: 	//                                       the "self" pointer.
sl@0: 	// - The CDbStoreDatabase::Close() will call "delete this" when its reference count reaches 0.
sl@0: 	//                                       The reference counter is increased by 1 in the InterfaceL() chain of calls.
sl@0: 	// -------- Conclusion ---------
sl@0: 	// No memory leak will occur in the next lines of code. Coverity errors - disabled.
sl@0: 	CDbStoreDatabase* self=NewLC(aStore);
sl@0: 	//coverity[alloc_fn]
sl@0: 	//coverity[var_assign]
sl@0: 	CDbObject* db=self->InterfaceL();	// a reference to the database is required
sl@0: 	CleanupStack::Pop();	// self
sl@0: 	//coverity[noescape]
sl@0: 	db->PushL();
sl@0: 	//coverity[noescape]
sl@0: 	self->Transaction().DDLPrepareL(*db);
sl@0: 	self->CompressL(aStreamId,aZip);
sl@0: 	CleanupStack::PopAndDestroy();	// db
sl@0: 	//coverity[leaked_storage]
sl@0: 	}
sl@0: 
sl@0: // Class RDbStoreDatabase
sl@0: 
sl@0: EXPORT_C void RDbStoreDatabase::CompressL(CStreamStore& aStore,TStreamId aId)
sl@0: 	{
sl@0: 	CDbStoreDatabase::CompressL(&aStore,aId,CDbStoreDatabase::EDeflate);
sl@0: 	}
sl@0: 
sl@0: EXPORT_C void RDbStoreDatabase::DecompressL(CStreamStore& aStore,TStreamId aId)
sl@0: 	{
sl@0: 	CDbStoreDatabase::CompressL(&aStore,aId,CDbStoreDatabase::EInflate);
sl@0: 	}