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 #define COMPILE_TIME_ASSERT(e)	\

    33 	switch (0)					\

    34 	{							\

    35 	case 0:						\

    36 	case e:						\

    37 		;						\

    38 	}

    39 

    40 /**

    41 Class HDeflateHash

    42 @internalComponent

    43 @released

    44 */

    45 class HDeflateHash

    46 {

    47 	public:

    48 		inline static HDeflateHash* NewLC(TInt aLinks);

    49 //

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

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

    52 	private:

    53 		inline HDeflateHash();

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

    55 	private:

    56 		typedef TUint16 TOffset;

    57 	private:

    58 		TInt iHash[256];

    59 		TOffset iOffset[1];	// or more

    60 };

    61 

    62 /**

    63 Class MDeflater

    64 @internalComponent

    65 @released

    66 */

    67 class MDeflater

    68 {

    69 	public:

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

    71 	private:

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

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

    74 		void SegmentL(TInt aLength,TInt aDistance);

    75 		virtual void LitLenL(TInt aCode) =0;

    76 		virtual void OffsetL(TInt aCode) =0;

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

    78 };

    79 

    80 /**

    81 Class TDeflateStats

    82 @internalComponent

    83 @released

    84 */

    85 class TDeflateStats : public MDeflater

    86 {

    87 	public:

    88 		inline TDeflateStats(TEncoding& aEncoding);

    89 	private:

    90 		// from MDeflater

    91 		void LitLenL(TInt aCode);

    92 		void OffsetL(TInt aCode);

    93 		void ExtraL(TInt aLen,TUint aBits);

    94 	private:

    95 		TEncoding& iEncoding;

    96 };

    97 

    98 /**

    99 Class TDeflater

   100 @internalComponent

   101 @released

   102 */

   103 class TDeflater : public MDeflater

   104 {

   105 	public:

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

   107 	private:

   108 		// from MDeflater

   109 		void LitLenL(TInt aCode);

   110 		void OffsetL(TInt aCode);

   111 		void ExtraL(TInt aLen,TUint aBits);

   112 	private:

   113 		TBitOutput& iOutput;

   114 		const TEncoding& iEncoding;

   115 };

   116 

   117 

   118 /**

   119 Constructor for class HDeflateHash

   120 @internalComponent

   121 @released

   122 */

   123 inline HDeflateHash::HDeflateHash()

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

   125 

   126 /**

   127 @Leave - OutOfMemory

   128 This function allocates memory for HDeflateHash

   129 @param aLinks

   130 @return pointer to allocated memory

   131 @internalComponent

   132 @released

   133 */

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

   135 {

   136 #if __GNUC__ >= 4

   137 	// Try to detect if the class' layout has changed.

   138 	COMPILE_TIME_ASSERT( sizeof(HDeflateHash) == 1028 );

   139 	COMPILE_TIME_ASSERT( sizeof(TOffset) == 2 );

   140 	COMPILE_TIME_ASSERT( offsetof(HDeflateHash, iHash) < offsetof(HDeflateHash, iOffset) );

   141 

   142 	// Compute the size of the class, including rounding it up to a multiple of 4

   143 	// bytes.

   144 

   145 	unsigned n = sizeof(TInt) * 256 + sizeof(TOffset) * Min(aLinks, KDeflateMaxDistance);

   146 

   147 	while (n & 0x1f)

   148 	{

   149 		n++;	

   150 	}

   151 

   152 	// Allocate the raw memory ...

   153 	void* p = ::operator new(n);

   154 

   155 	// ... And create the object in that memory.

   156 	return new(p) HDeflateHash;

   157 #else

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

   159 #endif

   160 }

   161 

   162 /**

   163 Hash function for HDeflateHash

   164 @param aPtr

   165 @return Hash value

   166 @internalComponent

   167 @released

   168 */

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

   170 {

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

   172 	return (x*KDeflateHashMultiplier)>>KDeflateHashShift;

   173 }

   174 

   175 /**

   176 Function First

   177 @param aPtr

   178 @param aPos

   179 @internalComponent

   180 @released

   181 */

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

   183 {

   184 	TInt h=Hash(aPtr);

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

   186 	iHash[h]=aPos;

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

   188 	return offset;

   189 }

   190 

   191 /**

   192 Function Next

   193 @param aPtr

   194 @param aPos

   195 @internalComponent

   196 @released

   197 */

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

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

   200 

   201 

   202 // Class TDeflater

   203 //

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

   205 

   206 /**

   207 Function Match

   208 @param aPtr

   209 @param aEnd

   210 @param aPos

   211 @param aHash

   212 @internalComponent

   213 @released

   214 */

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

   216 {

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

   218 	if (offset>KDeflateMaxDistance)

   219 		return 0;

   220 	TInt match=0;

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

   222 	TUint8 c=*aPtr;

   223 	do

   224 	{

   225 		const TUint8* p=aPtr-offset;

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

   227 		{	// might be a better match

   228 			const TUint8* m=aPtr;

   229 			for (;;)

   230 			{

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

   232 					break;

   233 				if (m<aEnd)

   234 					continue;

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

   236 			}

   237 			TInt l=m-aPtr-1;

   238 			if (l>match>>16)

   239 			{

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

   241 				c=m[-1];

   242 			}

   243 		}

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

   245 	} while (offset<=KDeflateMaxDistance);

   246 	return match;

   247 }

   248 

   249 /*

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

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

   252 @param aBase

   253 @param aEnd

   254 @param aHash

   255 @internalComponent

   256 @released

   257 */

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

   259 {

   260 	const TUint8* ptr=aBase;

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

   262 	do

   263 	{

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

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

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

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

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

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

   270 			TInt len=prev>>16;

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

   272 			// fill in missing hash entries for better compression

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

   274 			do

   275 			{

   276 				++ptr;

   277 				if (ptr + 2 < aEnd)

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

   279 			} while (ptr<e);

   280 			prev=0;

   281 		}

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

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

   284 		else

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

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

   287 				LitLenL(ptr[-1]);

   288 			prev=match;

   289 		}

   290 		++ptr;

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

   292 	if (prev)

   293 	{		// emit the stored match

   294 		TInt len=prev>>16;

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

   296 		ptr+=len-1;

   297 	}

   298 	return ptr;

   299 }

   300 

   301 /*

   302 The generic deflation algorithm

   303 @param aBase

   304 @param aLength

   305 @internalComponent

   306 @released

   307 */

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

   309 {

   310 	const TUint8* end=aBase+aLength;

   311 	if (aLength>KDeflateMinLength)

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

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

   314 

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

   316 		delete hash;

   317 	}

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

   319 		LitLenL(*aBase++);

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

   321 }

   322 

   323 /*

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

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

   326 @param aLength

   327 @param aDistance

   328 @internalComponent

   329 @released

   330 */

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

   332 {

   333 	aLength-=KDeflateMinLength;

   334 	TInt extralen=0;

   335 	TUint len=aLength;

   336 	while (len>=8)

   337 	{

   338 		++extralen;

   339 		len>>=1;

   340 	}

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

   342 	if (extralen)

   343 		ExtraL(extralen,aLength);

   344 //

   345 	aDistance--;

   346 	extralen=0;

   347 	TUint dist=aDistance;

   348 	while (dist>=8)

   349 	{

   350 		++extralen;

   351 		dist>>=1;

   352 	}

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

   354 	if (extralen)

   355 		ExtraL(extralen,aDistance);

   356 }

   357 

   358 /**

   359 Class TDeflateStats

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

   361 for the deflation algorithm

   362 @internalComponent

   363 @released

   364 */

   365 inline TDeflateStats::TDeflateStats(TEncoding& aEncoding)

   366 	:iEncoding(aEncoding)

   367 	{}

   368 /*

   369 Function LitLenL

   370 @Leave

   371 @param aCode

   372 @internalComponent

   373 @released

   374 */

   375 void TDeflateStats::LitLenL(TInt aCode)

   376 	{

   377 	++iEncoding.iLitLen[aCode];

   378 	}

   379 

   380 /*

   381 @Leave ArrayIndexOutOfBounds

   382 Finction OffsetL

   383 @param aCode

   384 @internalComponent

   385 @released

   386 */

   387 void TDeflateStats::OffsetL(TInt aCode)

   388 	{

   389 	++iEncoding.iDistance[aCode];

   390 	}

   391 

   392 /*

   393 Function ExtraL

   394 @Leave

   395 @internalComponent

   396 @released

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

   398 	{}

   399 

   400 /**

   401 Constructor of Class TDeflater

   402 Extends MDeflater to provide huffman encoding of the output

   403 @internalComponent

   404 @released

   405 */

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

   407 //

   408 // construct for encoding

   409 //

   410 	:iOutput(aOutput),iEncoding(aEncoding)

   411 	{}

   412 

   413 /*

   414 Function LitLenL

   415 @Leave

   416 @param aCode 

   417 @internalComponent

   418 @released

   419 */

   420 void TDeflater::LitLenL(TInt aCode)

   421 	{

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

   423 	}

   424 

   425 /*

   426 Function OffsetL

   427 @Leave

   428 @param aCdoe 

   429 @internalComponent

   430 @released

   431 */

   432 void TDeflater::OffsetL(TInt aCode)

   433 	{

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

   435 	}

   436 

   437 /*

   438 Function ExtraL

   439 @Leave

   440 @param  aLen

   441 @param aBits

   442 @internalComponent

   443 @released

   444 */

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

   446 	{

   447 	iOutput.WriteL(aBits,aLen);

   448 	}

   449 /*

   450 Function DoDeflateL

   451 @Leave

   452 @param aBuf

   453 @param aLength

   454 @param aOutput

   455 @param aEncoding

   456 @internalComponent

   457 @released

   458 */

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

   460 	{

   461 // analyse the data for symbol frequency 

   462 	TDeflateStats analyser(aEncoding);

   463 	analyser.DeflateL(aBuf,aLength);

   464 	

   465 // generate the required huffman encodings

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

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

   468 

   469 // Store the encoding table

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

   471 

   472 // generate the tables

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

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

   475 

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

   477 	TDeflater deflater(aOutput,aEncoding);

   478 	deflater.DeflateL(aBuf,aLength);

   479 	aOutput.PadL(1);

   480 	}

   481 

   482 /*

   483 Function DeflateL

   484 @Leave

   485 @param aBuf

   486 @param aLength

   487 @param aOutput 

   488 @internalComponent

   489 @released

   490 */

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

   492 	{

   493 	TEncoding* encoding=new TEncoding;

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

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

   496 	delete encoding;

   497 	}

   498 /*

   499 Function DeflateCompress

   500 @param bytes

   501 @param size

   502 @param os

   503 @internalComponent

   504 @released

   505 */

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

   507 	{

   508 	TFileOutput* output=new TFileOutput(os);

   509 	output->iDataCount = 0;

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

   511 	output->FlushL();

   512 	delete output;

   513 	}

   514