--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/persistentstorage/dbms/ustor/US_COMP.CPP Fri Jan 22 11:06:30 2010 +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);
+ }