--- a/imgtools/imglib/e32image/deflate/deflate.cpp Wed Jun 16 16:51:40 2010 +0300
+++ b/imgtools/imglib/e32image/deflate/deflate.cpp Wed Jun 23 16:56:47 2010 +0800
@@ -1,327 +1,342 @@
-/*
-* 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 the License "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:
-* e32tools\petran\Szip\deflate.cpp
-*
-*/
-
-
-#include "deflate.h"
-#include "h_utl.h"
-#include "panic.h"
-
-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);
- inline virtual ~MDeflater() { };
-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 TDeflateStats : public MDeflater
- {
-public:
- inline TDeflateStats(TEncoding& aEncoding);
- inline virtual ~TDeflateStats() { }
-private:
-// from MDeflater
- void LitLenL(TInt aCode);
- void OffsetL(TInt aCode);
- void ExtraL(TInt aLen,TUint aBits);
-private:
- TEncoding& iEncoding;
- };
-
-class TDeflater : public MDeflater
- {
-public:
- inline TDeflater(TBitOutput& aOutput,const TEncoding& aEncoding);
- inline virtual ~TDeflater() { };
-private:
-// from MDeflater
- void LitLenL(TInt aCode);
- void OffsetL(TInt aCode);
- void ExtraL(TInt aLen,TUint aBits);
-private:
- TBitOutput& iOutput;
- const TEncoding& iEncoding;
- };
-
-
-// Class HDeflateHash
-
-inline HDeflateHash::HDeflateHash()
- {TInt* p=iHash+256;do *--p=-KDeflateMaxDistance-1; while (p>iHash);}
-
-inline HDeflateHash* HDeflateHash::NewLC(TInt aLinks)
- {
- return new(HMem::Alloc(0,_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;
- }
-
-const TUint8* MDeflater::DoDeflateL(const TUint8* aBase,const TUint8* aEnd,HDeflateHash& aHash)
-//
-// 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* ptr=aBase;
- TInt prev=0; // the previous deflation match
- do
- {
- TInt match=Match(ptr,aEnd,ptr-aBase,aHash);
-// 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;
- if (ptr + 2 < aEnd)
- 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;
- } while (ptr+KDeflateMinLength-1<aEnd);
- if (prev)
- { // emit the stored match
- TInt len=prev>>16;
- SegmentL(len,prev-(len<<16));
- ptr+=len-1;
- }
- return ptr;
- }
-
-void MDeflater::DeflateL(const TUint8* aBase,TInt aLength)
-//
-// The generic deflation algorithm
-//
- {
- const TUint8* end=aBase+aLength;
- if (aLength>KDeflateMinLength)
- { // deflation kicks in if there is enough data
- HDeflateHash* hash=HDeflateHash::NewLC(aLength);
- if(hash==NULL)
- Panic(EHuffmanOutOfMemory);
-
- aBase=DoDeflateL(aBase,end,*hash);
- delete hash;
- }
- while (aBase<end) // emit remaining bytes
- LitLenL(*aBase++);
- LitLenL(TEncoding::EEos); // eos marker
- }
-
-void MDeflater::SegmentL(TInt aLength,TInt aDistance)
-//
-// Turn a (length,offset) pair into the deflation codes+extra bits before calling
-// the specific LitLen(), Offset() and Extra() functions.
-//
- {
- aLength-=KDeflateMinLength;
- TInt extralen=0;
- TUint len=aLength;
- while (len>=8)
- {
- ++extralen;
- len>>=1;
- }
- LitLenL((extralen<<2)+len+TEncoding::ELiterals);
- if (extralen)
- ExtraL(extralen,aLength);
-//
- aDistance--;
- extralen=0;
- TUint dist=aDistance;
- while (dist>=8)
- {
- ++extralen;
- dist>>=1;
- }
- OffsetL((extralen<<2)+dist);
- if (extralen)
- ExtraL(extralen,aDistance);
- }
-
-// Class TDeflateStats
-//
-// This class analyses the data stream to generate the frequency tables
-// for the deflation algorithm
-
-inline TDeflateStats::TDeflateStats(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 TDeflater
-//
-// Extends MDeflater to provide huffman encoding of the output
-
-inline TDeflater::TDeflater(TBitOutput& aOutput,const TEncoding& aEncoding)
-//
-// construct for encoding
-//
- :iOutput(aOutput),iEncoding(aEncoding)
- {}
-
-void TDeflater::LitLenL(TInt aCode)
- {
- iOutput.HuffmanL(iEncoding.iLitLen[aCode]);
- }
-
-void TDeflater::OffsetL(TInt aCode)
- {
- iOutput.HuffmanL(iEncoding.iDistance[aCode]);
- }
-
-void TDeflater::ExtraL(TInt aLen,TUint aBits)
- {
- iOutput.WriteL(aBits,aLen);
- }
-
-void DoDeflateL(const TUint8* aBuf,TInt aLength,TBitOutput& aOutput,TEncoding& aEncoding)
- {
-// analyse the data for symbol frequency
- TDeflateStats analyser(aEncoding);
- analyser.DeflateL(aBuf,aLength);
-
-// generate the required huffman encodings
- Huffman::HuffmanL(aEncoding.iLitLen,TEncoding::ELitLens,aEncoding.iLitLen);
- Huffman::HuffmanL(aEncoding.iDistance,TEncoding::EDistances,aEncoding.iDistance);
-
-// Store the encoding table
- Huffman::ExternalizeL(aOutput,aEncoding.iLitLen,KDeflationCodes);
-
-// generate the tables
- Huffman::Encoding(aEncoding.iLitLen,TEncoding::ELitLens,aEncoding.iLitLen);
- Huffman::Encoding(aEncoding.iDistance,TEncoding::EDistances,aEncoding.iDistance);
-
-// now finally deflate the data with the generated encoding
- TDeflater deflater(aOutput,aEncoding);
- deflater.DeflateL(aBuf,aLength);
- aOutput.PadL(1);
- }
-
-void DeflateL(const TUint8* aBuf, TInt aLength, TBitOutput& aOutput)
- {
- TEncoding* encoding=new TEncoding;
- HMem::FillZ(encoding,sizeof(TEncoding));
- DoDeflateL(aBuf,aLength,aOutput,*encoding);
- }
-
+/*
+* 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 the License "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:
+* e32tools\petran\Szip\deflate.cpp
+*
+*/
+
+
+#include "deflate.h"
+#include "h_utl.h"
+#include "panic.h"
+
+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);
+ inline virtual ~MDeflater() { };
+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 TDeflateStats : public MDeflater
+ {
+public:
+ inline TDeflateStats(TEncoding& aEncoding);
+ inline virtual ~TDeflateStats() { }
+private:
+// from MDeflater
+ void LitLenL(TInt aCode);
+ void OffsetL(TInt aCode);
+ void ExtraL(TInt aLen,TUint aBits);
+private:
+ TEncoding& iEncoding;
+ };
+
+class TDeflater : public MDeflater
+ {
+public:
+ inline TDeflater(TBitOutput& aOutput,const TEncoding& aEncoding);
+ inline virtual ~TDeflater() { };
+private:
+// from MDeflater
+ void LitLenL(TInt aCode);
+ void OffsetL(TInt aCode);
+ void ExtraL(TInt aLen,TUint aBits);
+private:
+ TBitOutput& iOutput;
+ const TEncoding& iEncoding;
+ };
+
+
+// Class HDeflateHash
+
+inline HDeflateHash::HDeflateHash()
+ {TInt* p=iHash+256;do *--p=-KDeflateMaxDistance-1; while (p>iHash);}
+
+inline HDeflateHash* HDeflateHash::NewLC(TInt aLinks)
+ {
+#if __GNUC__ >= 4
+ unsigned n = sizeof(TInt) * 256 + sizeof(TOffset) * Min(aLinks, KDeflateMaxDistance);
+
+ while (n & 0x1f)
+ {
+ n++;
+ }
+
+ void* p = ::operator new(n);
+
+ return new(p) HDeflateHash;
+#else
+ HDeflateHash *dummy = reinterpret_cast<HDeflateHash *>(0) ;
+ TUint offset = reinterpret_cast<TUint>(&(dummy->iOffset[Min(KDeflateMaxDistance , aLinks)])) ;
+ return new (HMem::Alloc(0,offset)) HDeflateHash;
+#endif
+}
+
+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;
+ }
+
+const TUint8* MDeflater::DoDeflateL(const TUint8* aBase,const TUint8* aEnd,HDeflateHash& aHash)
+//
+// 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* ptr=aBase;
+ TInt prev=0; // the previous deflation match
+ do
+ {
+ TInt match=Match(ptr,aEnd,ptr-aBase,aHash);
+// 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;
+ if (ptr + 2 < aEnd)
+ 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;
+ } while (ptr+KDeflateMinLength-1<aEnd);
+ if (prev)
+ { // emit the stored match
+ TInt len=prev>>16;
+ SegmentL(len,prev-(len<<16));
+ ptr+=len-1;
+ }
+ return ptr;
+ }
+
+void MDeflater::DeflateL(const TUint8* aBase,TInt aLength)
+//
+// The generic deflation algorithm
+//
+ {
+ const TUint8* end=aBase+aLength;
+ if (aLength>KDeflateMinLength)
+ { // deflation kicks in if there is enough data
+ HDeflateHash* hash=HDeflateHash::NewLC(aLength);
+ if(hash==NULL)
+ Panic(EHuffmanOutOfMemory);
+
+ aBase=DoDeflateL(aBase,end,*hash);
+ delete hash;
+ }
+ while (aBase<end) // emit remaining bytes
+ LitLenL(*aBase++);
+ LitLenL(TEncoding::EEos); // eos marker
+ }
+
+void MDeflater::SegmentL(TInt aLength,TInt aDistance)
+//
+// Turn a (length,offset) pair into the deflation codes+extra bits before calling
+// the specific LitLen(), Offset() and Extra() functions.
+//
+ {
+ aLength-=KDeflateMinLength;
+ TInt extralen=0;
+ TUint len=aLength;
+ while (len>=8)
+ {
+ ++extralen;
+ len>>=1;
+ }
+ LitLenL((extralen<<2)+len+TEncoding::ELiterals);
+ if (extralen)
+ ExtraL(extralen,aLength);
+//
+ aDistance--;
+ extralen=0;
+ TUint dist=aDistance;
+ while (dist>=8)
+ {
+ ++extralen;
+ dist>>=1;
+ }
+ OffsetL((extralen<<2)+dist);
+ if (extralen)
+ ExtraL(extralen,aDistance);
+ }
+
+// Class TDeflateStats
+//
+// This class analyses the data stream to generate the frequency tables
+// for the deflation algorithm
+
+inline TDeflateStats::TDeflateStats(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 TDeflater
+//
+// Extends MDeflater to provide huffman encoding of the output
+
+inline TDeflater::TDeflater(TBitOutput& aOutput,const TEncoding& aEncoding)
+//
+// construct for encoding
+//
+ :iOutput(aOutput),iEncoding(aEncoding)
+ {}
+
+void TDeflater::LitLenL(TInt aCode)
+ {
+ iOutput.HuffmanL(iEncoding.iLitLen[aCode]);
+ }
+
+void TDeflater::OffsetL(TInt aCode)
+ {
+ iOutput.HuffmanL(iEncoding.iDistance[aCode]);
+ }
+
+void TDeflater::ExtraL(TInt aLen,TUint aBits)
+ {
+ iOutput.WriteL(aBits,aLen);
+ }
+
+void DoDeflateL(const TUint8* aBuf,TInt aLength,TBitOutput& aOutput,TEncoding& aEncoding)
+ {
+// analyse the data for symbol frequency
+ TDeflateStats analyser(aEncoding);
+ analyser.DeflateL(aBuf,aLength);
+
+// generate the required huffman encodings
+ Huffman::HuffmanL(aEncoding.iLitLen,TEncoding::ELitLens,aEncoding.iLitLen);
+ Huffman::HuffmanL(aEncoding.iDistance,TEncoding::EDistances,aEncoding.iDistance);
+
+// Store the encoding table
+ Huffman::ExternalizeL(aOutput,aEncoding.iLitLen,KDeflationCodes);
+
+// generate the tables
+ Huffman::Encoding(aEncoding.iLitLen,TEncoding::ELitLens,aEncoding.iLitLen);
+ Huffman::Encoding(aEncoding.iDistance,TEncoding::EDistances,aEncoding.iDistance);
+
+// now finally deflate the data with the generated encoding
+ TDeflater deflater(aOutput,aEncoding);
+ deflater.DeflateL(aBuf,aLength);
+ aOutput.PadL(1);
+ }
+
+void DeflateL(const TUint8* aBuf, TInt aLength, TBitOutput& aOutput)
+ {
+ TEncoding* encoding=new TEncoding;
+ HMem::FillZ(encoding,sizeof(TEncoding));
+ DoDeflateL(aBuf,aLength,aOutput,*encoding);
+ }
+