1 // Copyright (c) 2004-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 //

    15 

    16 #include <fstream>

    17 #include <cassert>

    18 

    19 #include "e32imagedefs.h"

    20 #include "errorhandler.h"

    21 #include "farray.h"

    22 #include "huffman.h"

    23 

    24 const TInt KDeflateMinLength=3;

    25 const TInt KDeflateMaxLength=KDeflateMinLength-1 + (1<<KDeflateLengthMag);

    26 const TInt KDeflateMaxDistance=(1<<KDeflateDistanceMag);

    27 

    28 // hashing

    29 const TUint KDeflateHashMultiplier=0xAC4B9B19u;

    30 const TInt KDeflateHashShift=24;

    31 

    32 /**

    33 Class HDeflateHash

    34 @internalComponent

    35 @released

    36 */

    37 class HDeflateHash

    38 {

    39 	public:

    40 		inline static HDeflateHash* NewLC(TInt aLinks);

    41 //

    42 		inline TInt First(const TUint8* aPtr,TInt aPos);

    43 		inline TInt Next(TInt aPos,TInt aOffset) const;

    44 	private:

    45 		inline HDeflateHash();

    46 		inline static TInt Hash(const TUint8* aPtr);

    47 	private:

    48 		typedef TUint16 TOffset;

    49 	private:

    50 		TInt iHash[256];

    51 		TOffset iOffset[1];	// or more

    52 };

    53 

    54 /**

    55 Class MDeflater

    56 @internalComponent

    57 @released

    58 */

    59 class MDeflater

    60 {

    61 	public:

    62 		void DeflateL(const TUint8* aBase,TInt aLength);

    63 	private:

    64 		const TUint8* DoDeflateL(const TUint8* aBase,const TUint8* aEnd,HDeflateHash& aHash);

    65 		static TInt Match(const TUint8* aPtr,const TUint8* aEnd,TInt aPos,HDeflateHash& aHas);

    66 		void SegmentL(TInt aLength,TInt aDistance);

    67 		virtual void LitLenL(TInt aCode) =0;

    68 		virtual void OffsetL(TInt aCode) =0;

    69 		virtual void ExtraL(TInt aLen,TUint aBits) =0;

    70 };

    71 

    72 /**

    73 Class TDeflateStats

    74 @internalComponent

    75 @released

    76 */

    77 class TDeflateStats : public MDeflater

    78 {

    79 	public:

    80 		inline TDeflateStats(TEncoding& aEncoding);

    81 	private:

    82 		// from MDeflater

    83 		void LitLenL(TInt aCode);

    84 		void OffsetL(TInt aCode);

    85 		void ExtraL(TInt aLen,TUint aBits);

    86 	private:

    87 		TEncoding& iEncoding;

    88 };

    89 

    90 /**

    91 Class TDeflater

    92 @internalComponent

    93 @released

    94 */

    95 class TDeflater : public MDeflater

    96 {

    97 	public:

    98 		inline TDeflater(TBitOutput& aOutput,const TEncoding& aEncoding);

    99 	private:

   100 		// from MDeflater

   101 		void LitLenL(TInt aCode);

   102 		void OffsetL(TInt aCode);

   103 		void ExtraL(TInt aLen,TUint aBits);

   104 	private:

   105 		TBitOutput& iOutput;

   106 		const TEncoding& iEncoding;

   107 };

   108 

   109 

   110 /**

   111 Constructor for class HDeflateHash

   112 @internalComponent

   113 @released

   114 */

   115 inline HDeflateHash::HDeflateHash()

   116 {TInt* p=iHash+256;do *--p=-KDeflateMaxDistance-1; while (p>iHash);}

   117 

   118 /**

   119 @Leave - OutOfMemory

   120 This function allocates memory for HDeflateHash

   121 @param aLinks

   122 @return pointer to allocated memory

   123 @internalComponent

   124 @released

   125 */

   126 inline HDeflateHash* HDeflateHash::NewLC(TInt aLinks)

   127 {

   128 	//return new(HMem::Alloc(0,_FOFF(HDeflateHash,iOffset[Min(aLinks,KDeflateMaxDistance)]))) HDeflateHash;

   129 	return new(new char[_FOFF(HDeflateHash,iOffset[Min(aLinks,KDeflateMaxDistance)])]) HDeflateHash;

   130 }

   131 

   132 /**

   133 Hash function for HDeflateHash

   134 @param aPtr

   135 @return Hash value

   136 @internalComponent

   137 @released

   138 */

   139 inline TInt HDeflateHash::Hash(const TUint8* aPtr)

   140 {

   141 	TUint x=aPtr[0]|(aPtr[1]<<8)|(aPtr[2]<<16);

   142 	return (x*KDeflateHashMultiplier)>>KDeflateHashShift;

   143 }

   144 

   145 /**

   146 Function First

   147 @param aPtr

   148 @param aPos

   149 @internalComponent

   150 @released

   151 */

   152 inline TInt HDeflateHash::First(const TUint8* aPtr,TInt aPos)

   153 {

   154 	TInt h=Hash(aPtr);

   155 	TInt offset=Min(aPos-iHash[h],KDeflateMaxDistance<<1);

   156 	iHash[h]=aPos;

   157 	iOffset[aPos&(KDeflateMaxDistance-1)]=TOffset(offset);

   158 	return offset;

   159 }

   160 

   161 /**

   162 Function Next

   163 @param aPtr

   164 @param aPos

   165 @internalComponent

   166 @released

   167 */

   168 inline TInt HDeflateHash::Next(TInt aPos,TInt aOffset) const

   169 {return aOffset+iOffset[(aPos-aOffset)&(KDeflateMaxDistance-1)];}

   170 

   171 

   172 // Class TDeflater

   173 //

   174 // generic deflation algorithm, can do either statistics and the encoder

   175 

   176 /**

   177 Function Match

   178 @param aPtr

   179 @param aEnd

   180 @param aPos

   181 @param aHash

   182 @internalComponent

   183 @released

   184 */

   185 TInt MDeflater::Match(const TUint8* aPtr,const TUint8* aEnd,TInt aPos,HDeflateHash& aHash)

   186 {

   187 	TInt offset=aHash.First(aPtr,aPos);

   188 	if (offset>KDeflateMaxDistance)

   189 		return 0;

   190 	TInt match=0;

   191 	aEnd=Min(aEnd,aPtr+KDeflateMaxLength);

   192 	TUint8 c=*aPtr;

   193 	do

   194 	{

   195 		const TUint8* p=aPtr-offset;

   196 		if (p[match>>16]==c)

   197 		{	// might be a better match

   198 			const TUint8* m=aPtr;

   199 			for (;;)

   200 			{

   201 				if (*p++!=*m++)

   202 					break;

   203 				if (m<aEnd)

   204 					continue;

   205 				return ((m-aPtr)<<16)|offset;

   206 			}

   207 			TInt l=m-aPtr-1;

   208 			if (l>match>>16)

   209 			{

   210 				match=(l<<16)|offset;

   211 				c=m[-1];

   212 			}

   213 		}

   214 		offset=aHash.Next(aPos,offset);

   215 	} while (offset<=KDeflateMaxDistance);

   216 	return match;

   217 }

   218 

   219 /*

   220 Apply the deflation algorithm to the data [aBase,aEnd)

   221 Return a pointer after the last byte that was deflated (which may not be aEnd)

   222 @param aBase

   223 @param aEnd

   224 @param aHash

   225 @internalComponent

   226 @released

   227 */

   228 const TUint8* MDeflater::DoDeflateL(const TUint8* aBase,const TUint8* aEnd,HDeflateHash& aHash)

   229 {

   230 	const TUint8* ptr=aBase;

   231 	TInt prev=0;		// the previous deflation match

   232 	do

   233 	{

   234 		TInt match=Match(ptr,aEnd,ptr-aBase,aHash);

   235 // Extra deflation applies two optimisations which double the time taken

   236 // 1. If we have a match at p, then test for a better match at p+1 before using it

   237 // 2. When we have a match, add the hash links for all the data which will be skipped 

   238 		if (match>>16 < prev>>16)

   239 		{	// use the previous match--it was better

   240 			TInt len=prev>>16;

   241 			SegmentL(len,prev-(len<<16));

   242 			// fill in missing hash entries for better compression

   243 			const TUint8* e=ptr+len-2;

   244 			do

   245 			{

   246 				++ptr;

   247 				if (ptr + 2 < aEnd)

   248 				  aHash.First(ptr,ptr-aBase);

   249 			} while (ptr<e);

   250 			prev=0;

   251 		}

   252 		else if (match<=(KDeflateMinLength<<16))

   253 			LitLenL(*ptr);			// no deflation match here

   254 		else

   255 		{	// save this match and test the next position

   256 			if (prev)	// we had a match at ptr-1, but this is better

   257 				LitLenL(ptr[-1]);

   258 			prev=match;

   259 		}

   260 		++ptr;

   261 	} while (ptr+KDeflateMinLength-1<aEnd);

   262 	if (prev)

   263 	{		// emit the stored match

   264 		TInt len=prev>>16;

   265 		SegmentL(len,prev-(len<<16));

   266 		ptr+=len-1;

   267 	}

   268 	return ptr;

   269 }

   270 

   271 /*

   272 The generic deflation algorithm

   273 @param aBase

   274 @param aLength

   275 @internalComponent

   276 @released

   277 */

   278 void MDeflater::DeflateL(const TUint8* aBase,TInt aLength)

   279 {

   280 	const TUint8* end=aBase+aLength;

   281 	if (aLength>KDeflateMinLength)

   282 	{	// deflation kicks in if there is enough data

   283 		HDeflateHash* hash=HDeflateHash::NewLC(aLength);

   284 

   285 		aBase=DoDeflateL(aBase,end,*hash);

   286 		delete hash;

   287 	}

   288 	while (aBase<end)					// emit remaining bytes

   289 		LitLenL(*aBase++);

   290 	LitLenL(TEncoding::EEos);	// eos marker

   291 }

   292 

   293 /*

   294 Turn a (length,offset) pair into the deflation codes+extra bits before calling the specific

   295 LitLen(), Offset() and Extra() functions.

   296 @param aLength

   297 @param aDistance

   298 @internalComponent

   299 @released

   300 */

   301 void MDeflater::SegmentL(TInt aLength,TInt aDistance)

   302 {

   303 	aLength-=KDeflateMinLength;

   304 	TInt extralen=0;

   305 	TUint len=aLength;

   306 	while (len>=8)

   307 	{

   308 		++extralen;

   309 		len>>=1;

   310 	}

   311 	LitLenL((extralen<<2)+len+TEncoding::ELiterals);

   312 	if (extralen)

   313 		ExtraL(extralen,aLength);

   314 //

   315 	aDistance--;

   316 	extralen=0;

   317 	TUint dist=aDistance;

   318 	while (dist>=8)

   319 	{

   320 		++extralen;

   321 		dist>>=1;

   322 	}

   323 	OffsetL((extralen<<2)+dist);

   324 	if (extralen)

   325 		ExtraL(extralen,aDistance);

   326 }

   327 

   328 /**

   329 Class TDeflateStats

   330 This class analyses the data stream to generate the frequency tables 

   331 for the deflation algorithm

   332 @internalComponent

   333 @released

   334 */

   335 inline TDeflateStats::TDeflateStats(TEncoding& aEncoding)

   336 	:iEncoding(aEncoding)

   337 	{}

   338 /*

   339 Function LitLenL

   340 @Leave

   341 @param aCode

   342 @internalComponent

   343 @released

   344 */

   345 void TDeflateStats::LitLenL(TInt aCode)

   346 	{

   347 	++iEncoding.iLitLen[aCode];

   348 	}

   349 

   350 /*

   351 @Leave ArrayIndexOutOfBounds

   352 Finction OffsetL

   353 @param aCode

   354 @internalComponent

   355 @released

   356 */

   357 void TDeflateStats::OffsetL(TInt aCode)

   358 	{

   359 	++iEncoding.iDistance[aCode];

   360 	}

   361 

   362 /*

   363 Function ExtraL

   364 @Leave

   365 @internalComponent

   366 @released

   367 */void TDeflateStats::ExtraL(TInt,TUint)

   368 	{}

   369 

   370 /**

   371 Constructor of Class TDeflater

   372 Extends MDeflater to provide huffman encoding of the output

   373 @internalComponent

   374 @released

   375 */

   376 inline TDeflater::TDeflater(TBitOutput& aOutput,const TEncoding& aEncoding)

   377 //

   378 // construct for encoding

   379 //

   380 	:iOutput(aOutput),iEncoding(aEncoding)

   381 	{}

   382 

   383 /*

   384 Function LitLenL

   385 @Leave

   386 @param aCode 

   387 @internalComponent

   388 @released

   389 */

   390 void TDeflater::LitLenL(TInt aCode)

   391 	{

   392 	iOutput.HuffmanL(iEncoding.iLitLen[aCode]);

   393 	}

   394 

   395 /*

   396 Function OffsetL

   397 @Leave

   398 @param aCdoe 

   399 @internalComponent

   400 @released

   401 */

   402 void TDeflater::OffsetL(TInt aCode)

   403 	{

   404 	iOutput.HuffmanL(iEncoding.iDistance[aCode]);

   405 	}

   406 

   407 /*

   408 Function ExtraL

   409 @Leave

   410 @param  aLen

   411 @param aBits

   412 @internalComponent

   413 @released

   414 */

   415 void TDeflater::ExtraL(TInt aLen,TUint aBits)

   416 	{

   417 	iOutput.WriteL(aBits,aLen);

   418 	}

   419 /*

   420 Function DoDeflateL

   421 @Leave

   422 @param aBuf

   423 @param aLength

   424 @param aOutput

   425 @param aEncoding

   426 @internalComponent

   427 @released

   428 */

   429 void DoDeflateL(const TUint8* aBuf,TInt aLength,TBitOutput& aOutput,TEncoding& aEncoding)

   430 	{

   431 // analyse the data for symbol frequency 

   432 	TDeflateStats analyser(aEncoding);

   433 	analyser.DeflateL(aBuf,aLength);

   434 	

   435 // generate the required huffman encodings

   436 	Huffman::HuffmanL(aEncoding.iLitLen,TEncoding::ELitLens,aEncoding.iLitLen);

   437 	Huffman::HuffmanL(aEncoding.iDistance,TEncoding::EDistances,aEncoding.iDistance);

   438 

   439 // Store the encoding table

   440 	Huffman::ExternalizeL(aOutput,aEncoding.iLitLen,KDeflationCodes);

   441 

   442 // generate the tables

   443 	Huffman::Encoding(aEncoding.iLitLen,TEncoding::ELitLens,aEncoding.iLitLen);

   444 	Huffman::Encoding(aEncoding.iDistance,TEncoding::EDistances,aEncoding.iDistance);

   445 

   446 // now finally deflate the data with the generated encoding

   447 	TDeflater deflater(aOutput,aEncoding);

   448 	deflater.DeflateL(aBuf,aLength);

   449 	aOutput.PadL(1);

   450 	}

   451 

   452 /*

   453 Function DeflateL

   454 @Leave

   455 @param aBuf

   456 @param aLength

   457 @param aOutput 

   458 @internalComponent

   459 @released

   460 */

   461 void DeflateL(const TUint8* aBuf, TInt aLength, TBitOutput& aOutput)

   462 	{

   463 	TEncoding* encoding=new TEncoding;

   464 	memset(encoding,0,sizeof(TEncoding));

   465 	DoDeflateL(aBuf,aLength,aOutput,*encoding);

   466 	delete encoding;

   467 	}

   468 /*

   469 Function DeflateCompress

   470 @param bytes

   471 @param size

   472 @param os

   473 @internalComponent

   474 @released

   475 */

   476 void DeflateCompress(char *bytes,size_t size, std::ofstream & os)

   477 	{

   478 	TFileOutput* output=new TFileOutput(os);

   479 	output->iDataCount = 0;

   480 	DeflateL((TUint8*)bytes,size,*output);

   481 	output->FlushL();

   482 	delete output;

   483 	}

   484