e32tools/e32lib/e32image/deflate/deflate.cpp
changeset 0 044383f39525
equal deleted inserted replaced
-1:000000000000 0:044383f39525
       
     1 // Copyright (c) 1998-2009 Nokia Corporation and/or its subsidiary(-ies).
       
     2 // All rights reserved.
       
     3 // This component and the accompanying materials are made available
       
     4 // under the terms of "Eclipse Public License v1.0"
       
     5 // which accompanies this distribution, and is available
       
     6 // at the URL "http://www.eclipse.org/legal/epl-v10.html".
       
     7 //
       
     8 // Initial Contributors:
       
     9 // Nokia Corporation - initial contribution.
       
    10 //
       
    11 // Contributors:
       
    12 //
       
    13 // Description:
       
    14 // e32tools\petran\Szip\deflate.cpp
       
    15 // 
       
    16 //
       
    17 
       
    18 #include "deflate.h"
       
    19 #include "h_utl.h"
       
    20 #include "panic.h"
       
    21 
       
    22 class HDeflateHash
       
    23 	{
       
    24 public:
       
    25 	inline static HDeflateHash* NewLC(TInt aLinks);
       
    26 //
       
    27 	inline TInt First(const TUint8* aPtr,TInt aPos);
       
    28 	inline TInt Next(TInt aPos,TInt aOffset) const;
       
    29 private:
       
    30 	inline HDeflateHash();
       
    31 	inline static TInt Hash(const TUint8* aPtr);
       
    32 private:
       
    33 	typedef TUint16 TOffset;
       
    34 private:
       
    35 	TInt iHash[256];
       
    36 	TOffset iOffset[1];	// or more
       
    37 	};
       
    38 
       
    39 class MDeflater
       
    40 	{
       
    41 public:
       
    42 	void DeflateL(const TUint8* aBase,TInt aLength);
       
    43 	inline virtual ~MDeflater() { }; 
       
    44 private:
       
    45 	const TUint8* DoDeflateL(const TUint8* aBase,const TUint8* aEnd,HDeflateHash& aHash);
       
    46 	static TInt Match(const TUint8* aPtr,const TUint8* aEnd,TInt aPos,HDeflateHash& aHas);
       
    47 	void SegmentL(TInt aLength,TInt aDistance);
       
    48 	virtual void LitLenL(TInt aCode) =0;
       
    49 	virtual void OffsetL(TInt aCode) =0;
       
    50 	virtual void ExtraL(TInt aLen,TUint aBits) =0;
       
    51 	};
       
    52 
       
    53 class TDeflateStats : public MDeflater
       
    54 	{
       
    55 public:
       
    56 	inline TDeflateStats(TEncoding& aEncoding);
       
    57 	inline virtual ~TDeflateStats() { } 
       
    58 private:
       
    59 // from MDeflater
       
    60 	void LitLenL(TInt aCode);
       
    61 	void OffsetL(TInt aCode);
       
    62 	void ExtraL(TInt aLen,TUint aBits);
       
    63 private:
       
    64 	TEncoding& iEncoding;
       
    65 	};
       
    66 
       
    67 class TDeflater : public MDeflater
       
    68 	{
       
    69 public:
       
    70 	inline TDeflater(TBitOutput& aOutput,const TEncoding& aEncoding);
       
    71 	inline virtual ~TDeflater() { }; 
       
    72 private:
       
    73 // from MDeflater
       
    74 	void LitLenL(TInt aCode);
       
    75 	void OffsetL(TInt aCode);
       
    76 	void ExtraL(TInt aLen,TUint aBits);
       
    77 private:
       
    78 	TBitOutput& iOutput;
       
    79 	const TEncoding& iEncoding;
       
    80 	};
       
    81 
       
    82 
       
    83 // Class HDeflateHash
       
    84 
       
    85 inline HDeflateHash::HDeflateHash()
       
    86 	{TInt* p=iHash+256;do *--p=-KDeflateMaxDistance-1; while (p>iHash);}
       
    87 
       
    88 inline HDeflateHash* HDeflateHash::NewLC(TInt aLinks)
       
    89 	{
       
    90 	return new(HMem::Alloc(0,_FOFF(HDeflateHash,iOffset[Min(aLinks,KDeflateMaxDistance)]))) HDeflateHash;
       
    91 	}
       
    92 
       
    93 inline TInt HDeflateHash::Hash(const TUint8* aPtr)
       
    94 	{
       
    95 	TUint x=aPtr[0]|(aPtr[1]<<8)|(aPtr[2]<<16);
       
    96 	return (x*KDeflateHashMultiplier)>>KDeflateHashShift;
       
    97 	}
       
    98 
       
    99 inline TInt HDeflateHash::First(const TUint8* aPtr,TInt aPos)
       
   100 	{
       
   101 	TInt h=Hash(aPtr);
       
   102 	TInt offset=Min(aPos-iHash[h],KDeflateMaxDistance<<1);
       
   103 	iHash[h]=aPos;
       
   104 	iOffset[aPos&(KDeflateMaxDistance-1)]=TOffset(offset);
       
   105 	return offset;
       
   106 	}
       
   107 
       
   108 inline TInt HDeflateHash::Next(TInt aPos,TInt aOffset) const
       
   109 	{return aOffset+iOffset[(aPos-aOffset)&(KDeflateMaxDistance-1)];}
       
   110 
       
   111 
       
   112 // Class TDeflater
       
   113 //
       
   114 // generic deflation algorithm, can do either statistics and the encoder
       
   115 
       
   116 TInt MDeflater::Match(const TUint8* aPtr,const TUint8* aEnd,TInt aPos,HDeflateHash& aHash)
       
   117 	{
       
   118 	TInt offset=aHash.First(aPtr,aPos);
       
   119 	if (offset>KDeflateMaxDistance)
       
   120 		return 0;
       
   121 	TInt match=0;
       
   122 	aEnd=Min(aEnd,aPtr+KDeflateMaxLength);
       
   123 	TUint8 c=*aPtr;
       
   124 	do
       
   125 		{
       
   126 		const TUint8* p=aPtr-offset;
       
   127 		if (p[match>>16]==c)
       
   128 			{	// might be a better match
       
   129 			const TUint8* m=aPtr;
       
   130 			for (;;)
       
   131 				{
       
   132 				if (*p++!=*m++)
       
   133 					break;
       
   134 				if (m<aEnd)
       
   135 					continue;
       
   136 				return ((m-aPtr)<<16)|offset;
       
   137 				}
       
   138 			TInt l=m-aPtr-1;
       
   139 			if (l>match>>16)
       
   140 				{
       
   141 				match=(l<<16)|offset;
       
   142 				c=m[-1];
       
   143 				}
       
   144 			}
       
   145 		offset=aHash.Next(aPos,offset);
       
   146 		} while (offset<=KDeflateMaxDistance);
       
   147 	return match;
       
   148 	}
       
   149 
       
   150 const TUint8* MDeflater::DoDeflateL(const TUint8* aBase,const TUint8* aEnd,HDeflateHash& aHash)
       
   151 //
       
   152 // Apply the deflation algorithm to the data [aBase,aEnd)
       
   153 // Return a pointer after the last byte that was deflated (which may not be aEnd)
       
   154 //
       
   155 	{
       
   156 	const TUint8* ptr=aBase;
       
   157 	TInt prev=0;		// the previous deflation match
       
   158 	do
       
   159 		{
       
   160 		TInt match=Match(ptr,aEnd,ptr-aBase,aHash);
       
   161 // Extra deflation applies two optimisations which double the time taken
       
   162 // 1. If we have a match at p, then test for a better match at p+1 before using it
       
   163 // 2. When we have a match, add the hash links for all the data which will be skipped 
       
   164 		if (match>>16 < prev>>16)
       
   165 			{	// use the previous match--it was better
       
   166 			TInt len=prev>>16;
       
   167 			SegmentL(len,prev-(len<<16));
       
   168 			// fill in missing hash entries for better compression
       
   169 			const TUint8* e=ptr+len-2;
       
   170 			do 
       
   171 				{
       
   172 				++ptr;
       
   173 				if (ptr + 2 < aEnd)
       
   174 					aHash.First(ptr,ptr-aBase);
       
   175 				} while (ptr<e);
       
   176 			prev=0;
       
   177 			}
       
   178 		else if (match<=(KDeflateMinLength<<16))
       
   179 			LitLenL(*ptr);			// no deflation match here
       
   180 		else
       
   181 			{	// save this match and test the next position
       
   182 			if (prev)	// we had a match at ptr-1, but this is better
       
   183 				LitLenL(ptr[-1]);
       
   184 			prev=match;
       
   185 			}
       
   186 		++ptr;
       
   187 		} while (ptr+KDeflateMinLength-1<aEnd);
       
   188 	if (prev)
       
   189 		{		// emit the stored match
       
   190 		TInt len=prev>>16;
       
   191 		SegmentL(len,prev-(len<<16));
       
   192 		ptr+=len-1;
       
   193 		}
       
   194 	return ptr;
       
   195 	}
       
   196 
       
   197 void MDeflater::DeflateL(const TUint8* aBase,TInt aLength)
       
   198 //
       
   199 // The generic deflation algorithm
       
   200 //
       
   201 	{
       
   202 	const TUint8* end=aBase+aLength;
       
   203 	if (aLength>KDeflateMinLength)
       
   204 		{	// deflation kicks in if there is enough data
       
   205 		HDeflateHash* hash=HDeflateHash::NewLC(aLength);
       
   206 		if(hash==NULL)
       
   207 			Panic(EHuffmanOutOfMemory);
       
   208 
       
   209 		aBase=DoDeflateL(aBase,end,*hash);
       
   210 		delete hash;
       
   211 		}
       
   212 	while (aBase<end)					// emit remaining bytes
       
   213 		LitLenL(*aBase++);
       
   214 	LitLenL(TEncoding::EEos);	// eos marker
       
   215 	}
       
   216 
       
   217 void MDeflater::SegmentL(TInt aLength,TInt aDistance)
       
   218 //
       
   219 // Turn a (length,offset) pair into the deflation codes+extra bits before calling
       
   220 // the specific LitLen(), Offset() and Extra() functions.
       
   221 //
       
   222 	{
       
   223 	aLength-=KDeflateMinLength;
       
   224 	TInt extralen=0;
       
   225 	TUint len=aLength;
       
   226 	while (len>=8)
       
   227 		{
       
   228 		++extralen;
       
   229 		len>>=1;
       
   230 		}
       
   231 	LitLenL((extralen<<2)+len+TEncoding::ELiterals);
       
   232 	if (extralen)
       
   233 		ExtraL(extralen,aLength);
       
   234 //
       
   235 	aDistance--;
       
   236 	extralen=0;
       
   237 	TUint dist=aDistance;
       
   238 	while (dist>=8)
       
   239 		{
       
   240 		++extralen;
       
   241 		dist>>=1;
       
   242 		}
       
   243 	OffsetL((extralen<<2)+dist);
       
   244 	if (extralen)
       
   245 		ExtraL(extralen,aDistance);
       
   246 	}
       
   247 
       
   248 // Class TDeflateStats
       
   249 //
       
   250 // This class analyses the data stream to generate the frequency tables 
       
   251 // for the deflation algorithm
       
   252 
       
   253 inline TDeflateStats::TDeflateStats(TEncoding& aEncoding)
       
   254 	:iEncoding(aEncoding)
       
   255 	{}
       
   256 
       
   257 void TDeflateStats::LitLenL(TInt aCode)
       
   258 	{
       
   259 	++iEncoding.iLitLen[aCode];
       
   260 	}
       
   261 
       
   262 void TDeflateStats::OffsetL(TInt aCode)
       
   263 	{
       
   264 	++iEncoding.iDistance[aCode];
       
   265 	}
       
   266 
       
   267 void TDeflateStats::ExtraL(TInt,TUint)
       
   268 	{}
       
   269 
       
   270 // Class TDeflater
       
   271 //
       
   272 // Extends MDeflater to provide huffman encoding of the output
       
   273 
       
   274 inline TDeflater::TDeflater(TBitOutput& aOutput,const TEncoding& aEncoding)
       
   275 //
       
   276 // construct for encoding
       
   277 //
       
   278 	:iOutput(aOutput),iEncoding(aEncoding)
       
   279 	{}
       
   280 
       
   281 void TDeflater::LitLenL(TInt aCode)
       
   282 	{
       
   283 	iOutput.HuffmanL(iEncoding.iLitLen[aCode]);
       
   284 	}
       
   285 
       
   286 void TDeflater::OffsetL(TInt aCode)
       
   287 	{
       
   288 	iOutput.HuffmanL(iEncoding.iDistance[aCode]);
       
   289 	}
       
   290 
       
   291 void TDeflater::ExtraL(TInt aLen,TUint aBits)
       
   292 	{
       
   293 	iOutput.WriteL(aBits,aLen);
       
   294 	}
       
   295 
       
   296 void DoDeflateL(const TUint8* aBuf,TInt aLength,TBitOutput& aOutput,TEncoding& aEncoding)
       
   297 	{
       
   298 // analyse the data for symbol frequency 
       
   299 	TDeflateStats analyser(aEncoding);
       
   300 	analyser.DeflateL(aBuf,aLength);
       
   301 	
       
   302 // generate the required huffman encodings
       
   303 	Huffman::HuffmanL(aEncoding.iLitLen,TEncoding::ELitLens,aEncoding.iLitLen);
       
   304 	Huffman::HuffmanL(aEncoding.iDistance,TEncoding::EDistances,aEncoding.iDistance);
       
   305 
       
   306 // Store the encoding table
       
   307 	Huffman::ExternalizeL(aOutput,aEncoding.iLitLen,KDeflationCodes);
       
   308 
       
   309 // generate the tables
       
   310 	Huffman::Encoding(aEncoding.iLitLen,TEncoding::ELitLens,aEncoding.iLitLen);
       
   311 	Huffman::Encoding(aEncoding.iDistance,TEncoding::EDistances,aEncoding.iDistance);
       
   312 
       
   313 // now finally deflate the data with the generated encoding
       
   314 	TDeflater deflater(aOutput,aEncoding);
       
   315 	deflater.DeflateL(aBuf,aLength);
       
   316 	aOutput.PadL(1);
       
   317 	}
       
   318 
       
   319 void DeflateL(const TUint8* aBuf, TInt aLength, TBitOutput& aOutput)
       
   320 	{
       
   321 	TEncoding* encoding=new TEncoding;
       
   322 	HMem::FillZ(encoding,sizeof(TEncoding));
       
   323 	DoDeflateL(aBuf,aLength,aOutput,*encoding);
       
   324 	}
       
   325