--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/toolsandutils/e32tools/elf2e32/source/deflatecompress.cpp	Tue Feb 02 01:39:43 2010 +0200
@@ -0,0 +1,514 @@
+// Copyright (c) 2004-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:
+//
+
+#include <fstream>
+#include <cassert>
+
+#include "e32imagedefs.h"
+#include "errorhandler.h"
+#include "farray.h"
+#include "huffman.h"
+
+const TInt KDeflateMinLength=3;
+const TInt KDeflateMaxLength=KDeflateMinLength-1 + (1<<KDeflateLengthMag);
+const TInt KDeflateMaxDistance=(1<<KDeflateDistanceMag);
+
+// hashing
+const TUint KDeflateHashMultiplier=0xAC4B9B19u;
+const TInt KDeflateHashShift=24;
+
+#define COMPILE_TIME_ASSERT(e)	\
+	switch (0)					\
+	{							\
+	case 0:						\
+	case e:						\
+		;						\
+	}
+
+/**
+Class HDeflateHash
+@internalComponent
+@released
+*/
+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
+@internalComponent
+@released
+*/
+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 TDeflateStats
+@internalComponent
+@released
+*/
+class TDeflateStats : public MDeflater
+{
+	public:
+		inline TDeflateStats(TEncoding& aEncoding);
+	private:
+		// from MDeflater
+		void LitLenL(TInt aCode);
+		void OffsetL(TInt aCode);
+		void ExtraL(TInt aLen,TUint aBits);
+	private:
+		TEncoding& iEncoding;
+};
+
+/**
+Class TDeflater
+@internalComponent
+@released
+*/
+class TDeflater : public MDeflater
+{
+	public:
+		inline TDeflater(TBitOutput& aOutput,const TEncoding& aEncoding);
+	private:
+		// from MDeflater
+		void LitLenL(TInt aCode);
+		void OffsetL(TInt aCode);
+		void ExtraL(TInt aLen,TUint aBits);
+	private:
+		TBitOutput& iOutput;
+		const TEncoding& iEncoding;
+};
+
+
+/**
+Constructor for class HDeflateHash
+@internalComponent
+@released
+*/
+inline HDeflateHash::HDeflateHash()
+{TInt* p=iHash+256;do *--p=-KDeflateMaxDistance-1; while (p>iHash);}
+
+/**
+@Leave - OutOfMemory
+This function allocates memory for HDeflateHash
+@param aLinks
+@return pointer to allocated memory
+@internalComponent
+@released
+*/
+inline HDeflateHash* HDeflateHash::NewLC(TInt aLinks)
+{
+#if __GNUC__ >= 4
+	// Try to detect if the class' layout has changed.
+	COMPILE_TIME_ASSERT( sizeof(HDeflateHash) == 1028 );
+	COMPILE_TIME_ASSERT( sizeof(TOffset) == 2 );
+	COMPILE_TIME_ASSERT( offsetof(HDeflateHash, iHash) < offsetof(HDeflateHash, iOffset) );
+
+	// Compute the size of the class, including rounding it up to a multiple of 4
+	// bytes.
+
+	unsigned n = sizeof(TInt) * 256 + sizeof(TOffset) * Min(aLinks, KDeflateMaxDistance);
+
+	while (n & 0x1f)
+	{
+		n++;	
+	}
+
+	// Allocate the raw memory ...
+	void* p = ::operator new(n);
+
+	// ... And create the object in that memory.
+	return new(p) HDeflateHash;
+#else
+	return new(new char[_FOFF(HDeflateHash,iOffset[Min(aLinks,KDeflateMaxDistance)])]) HDeflateHash;
+#endif
+}
+
+/**
+Hash function for HDeflateHash
+@param aPtr
+@return Hash value
+@internalComponent
+@released
+*/
+inline TInt HDeflateHash::Hash(const TUint8* aPtr)
+{
+	TUint x=aPtr[0]|(aPtr[1]<<8)|(aPtr[2]<<16);
+	return (x*KDeflateHashMultiplier)>>KDeflateHashShift;
+}
+
+/**
+Function First
+@param aPtr
+@param aPos
+@internalComponent
+@released
+*/
+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;
+}
+
+/**
+Function Next
+@param aPtr
+@param aPos
+@internalComponent
+@released
+*/
+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
+
+/**
+Function Match
+@param aPtr
+@param aEnd
+@param aPos
+@param aHash
+@internalComponent
+@released
+*/
+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)
+@param aBase
+@param aEnd
+@param aHash
+@internalComponent
+@released
+*/
+const TUint8* MDeflater::DoDeflateL(const TUint8* aBase,const TUint8* aEnd,HDeflateHash& aHash)
+{
+	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;
+}
+
+/*
+The generic deflation algorithm
+@param aBase
+@param aLength
+@internalComponent
+@released
+*/
+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);
+		delete hash;
+	}
+	while (aBase<end)					// emit remaining bytes
+		LitLenL(*aBase++);
+	LitLenL(TEncoding::EEos);	// eos marker
+}
+
+/*
+Turn a (length,offset) pair into the deflation codes+extra bits before calling the specific
+LitLen(), Offset() and Extra() functions.
+@param aLength
+@param aDistance
+@internalComponent
+@released
+*/
+void MDeflater::SegmentL(TInt aLength,TInt aDistance)
+{
+	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
+@internalComponent
+@released
+*/
+inline TDeflateStats::TDeflateStats(TEncoding& aEncoding)
+	:iEncoding(aEncoding)
+	{}
+/*
+Function LitLenL
+@Leave
+@param aCode
+@internalComponent
+@released
+*/
+void TDeflateStats::LitLenL(TInt aCode)
+	{
+	++iEncoding.iLitLen[aCode];
+	}
+
+/*
+@Leave ArrayIndexOutOfBounds
+Finction OffsetL
+@param aCode
+@internalComponent
+@released
+*/
+void TDeflateStats::OffsetL(TInt aCode)
+	{
+	++iEncoding.iDistance[aCode];
+	}
+
+/*
+Function ExtraL
+@Leave
+@internalComponent
+@released
+*/void TDeflateStats::ExtraL(TInt,TUint)
+	{}
+
+/**
+Constructor of Class TDeflater
+Extends MDeflater to provide huffman encoding of the output
+@internalComponent
+@released
+*/
+inline TDeflater::TDeflater(TBitOutput& aOutput,const TEncoding& aEncoding)
+//
+// construct for encoding
+//
+	:iOutput(aOutput),iEncoding(aEncoding)
+	{}
+
+/*
+Function LitLenL
+@Leave
+@param aCode 
+@internalComponent
+@released
+*/
+void TDeflater::LitLenL(TInt aCode)
+	{
+	iOutput.HuffmanL(iEncoding.iLitLen[aCode]);
+	}
+
+/*
+Function OffsetL
+@Leave
+@param aCdoe 
+@internalComponent
+@released
+*/
+void TDeflater::OffsetL(TInt aCode)
+	{
+	iOutput.HuffmanL(iEncoding.iDistance[aCode]);
+	}
+
+/*
+Function ExtraL
+@Leave
+@param  aLen
+@param aBits
+@internalComponent
+@released
+*/
+void TDeflater::ExtraL(TInt aLen,TUint aBits)
+	{
+	iOutput.WriteL(aBits,aLen);
+	}
+/*
+Function DoDeflateL
+@Leave
+@param aBuf
+@param aLength
+@param aOutput
+@param aEncoding
+@internalComponent
+@released
+*/
+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);
+	}
+
+/*
+Function DeflateL
+@Leave
+@param aBuf
+@param aLength
+@param aOutput 
+@internalComponent
+@released
+*/
+void DeflateL(const TUint8* aBuf, TInt aLength, TBitOutput& aOutput)
+	{
+	TEncoding* encoding=new TEncoding;
+	memset(encoding,0,sizeof(TEncoding));
+	DoDeflateL(aBuf,aLength,aOutput,*encoding);
+	delete encoding;
+	}
+/*
+Function DeflateCompress
+@param bytes
+@param size
+@param os
+@internalComponent
+@released
+*/
+void DeflateCompress(char *bytes,size_t size, std::ofstream & os)
+	{
+	TFileOutput* output=new TFileOutput(os);
+	output->iDataCount = 0;
+	DeflateL((TUint8*)bytes,size,*output);
+	output->FlushL();
+	delete output;
+	}
+