sl@0: // Copyright (c) 2007-2009 Nokia Corporation and/or its subsidiary(-ies).
sl@0: // All rights reserved.
sl@0: // This component and the accompanying materials are made available
sl@0: // under the terms of the License "Eclipse Public License v1.0"
sl@0: // which accompanies this distribution, and is available
sl@0: // at the URL "http://www.eclipse.org/legal/epl-v10.html".
sl@0: //
sl@0: // Initial Contributors:
sl@0: // Nokia Corporation - initial contribution.
sl@0: //
sl@0: // Contributors:
sl@0: //
sl@0: // Description:
sl@0: // e32\include\byte_pair_compress.h
sl@0: // This header file contains both the prototype and implementation for the byte pair compressor.
sl@0: // This is done to facilitate sharing the code between the e32 test code and the tools.  The
sl@0: // implementation is only included if the macro BYTE_PAIR_COMPRESS_INCLUDE_IMPLEMENTATION is
sl@0: // defined.
sl@0: // 
sl@0: // WARNING: This file contains some APIs which are internal and are subject
sl@0: //          to change without notice. Such APIs should therefore not be used
sl@0: //          outside the Kernel and Hardware Services package.
sl@0: //
sl@0: 
sl@0: #ifndef __BYTE_PAIR_COMPRESS_H__
sl@0: #define __BYTE_PAIR_COMPRESS_H__
sl@0: 
sl@0: #include <e32std.h>
sl@0: 
sl@0: /**
sl@0:  * @internalTechnology
sl@0:  *
sl@0:  * Compress up to 4096 bytes of data usign the byte-pair compression algorithm.
sl@0:  *
sl@0:  * @param aDest Destination buffer, must be at least four times the size of the source data.
sl@0:  * @param aSrc  Source data to compress.
sl@0:  * @param aSize The size of the source data.
sl@0:  */
sl@0: extern TInt BytePairCompress(TUint8* aDest, TUint8* aSrc, TInt aSize);
sl@0: 
sl@0: #ifdef BYTE_PAIR_COMPRESS_INCLUDE_IMPLEMENTATION
sl@0: 
sl@0: const TInt BlockSize = 0x1000;
sl@0: TInt ExtraSave = 0;
sl@0: 
sl@0: TUint16 PairCount[0x10000];
sl@0: TUint16 PairBuffer[BlockSize*2];
sl@0: 
sl@0: TUint16 GlobalPairs[0x10000] = {0};
sl@0: TUint16 GlobalTokenCounts[0x100] = {0};
sl@0: 
sl@0: TUint16 ByteCount[0x100+4];
sl@0: 
sl@0: void CountBytes(TUint8* data, TInt size)
sl@0: 	{
sl@0: 	memset(ByteCount,0,sizeof(ByteCount));
sl@0: 	TUint8* dataEnd = data+size;
sl@0: 	while(data<dataEnd)
sl@0: 		++ByteCount[*data++];
sl@0: 	}
sl@0: 
sl@0: inline void ByteUsed(TInt b)
sl@0: 	{
sl@0: 	ByteCount[b] = 0xffff;
sl@0: 	}
sl@0: 
sl@0: int TieBreak(int b1,int b2)
sl@0: 	{
sl@0: 	return -ByteCount[b1]-ByteCount[b2];
sl@0: 	}
sl@0: 
sl@0: TInt MostCommonPair(TInt& pair, TUint8* data, TInt size, TInt minFrequency, TInt marker)
sl@0: 	{
sl@0: 	memset(PairCount,0,sizeof(PairCount));
sl@0: 	TUint8* dataEnd = data+size-1;
sl@0: 	TInt pairsFound = 0;
sl@0: 	TInt lastPair = -1;
sl@0: 	while(data<dataEnd)
sl@0: 		{
sl@0: 		TInt b1 = *data++;
sl@0: 		if(b1==marker)
sl@0: 			{
sl@0: 			// skip marker and following byte
sl@0: 			lastPair = -1;
sl@0: 			++data;
sl@0: 			continue;
sl@0: 			}
sl@0: 		TInt b2 = *data;
sl@0: 		if(b2==marker)
sl@0: 			{
sl@0: 			// skip marker and following byte
sl@0: 			lastPair = -1;
sl@0: 			data+=2;
sl@0: 			continue;
sl@0: 			}
sl@0: 		TInt p = (b2<<8)|b1;
sl@0: 		if(p==lastPair)
sl@0: 			{
sl@0: 			// ensure a pair of identical bytes don't get double counted
sl@0: 			lastPair = -1;
sl@0: 			continue;
sl@0: 			}
sl@0: 		lastPair = p;
sl@0: 		++PairCount[p];
sl@0: 		if(PairCount[p]==minFrequency)
sl@0: 			PairBuffer[pairsFound++] = (TUint16)p;
sl@0: 		}
sl@0: 
sl@0: 	TInt bestCount = -1;
sl@0: 	TInt bestPair = -1;
sl@0: 	TInt bestTieBreak = 0;
sl@0: 	TInt p;
sl@0: 	while(pairsFound--)
sl@0: 		{
sl@0: 		p = PairBuffer[pairsFound];
sl@0: 		TInt f=PairCount[p];
sl@0: 		if(f>bestCount)
sl@0: 			{
sl@0: 			bestCount = f;
sl@0: 			bestPair = p;
sl@0: 			bestTieBreak = TieBreak(p&0xff,p>>8);
sl@0: 			}
sl@0: 		else if(f==bestCount)
sl@0: 			{
sl@0: 			TInt tieBreak = TieBreak(p&0xff,p>>8);
sl@0: 			if(tieBreak>bestTieBreak)
sl@0: 				{
sl@0: 				bestCount = f;
sl@0: 				bestPair = p;
sl@0: 				bestTieBreak = tieBreak;
sl@0: 				}
sl@0: 			}
sl@0: 		}
sl@0: 	pair = bestPair;
sl@0: 	return bestCount;
sl@0: 	}
sl@0: 
sl@0: TInt LeastCommonByte(TInt& byte)
sl@0: 	{
sl@0: 	TInt bestCount = 0xffff;
sl@0: 	TInt bestByte = -1;
sl@0: 	for(TInt b = 0; b<0x100; b++)
sl@0: 		{
sl@0: 		TInt f = ByteCount[b];
sl@0: 		if(f<bestCount)
sl@0: 			{
sl@0: 			bestCount = f;
sl@0: 			bestByte = b;
sl@0: 			}
sl@0: 		}
sl@0: 	byte = bestByte;
sl@0: 	return bestCount;
sl@0: 	}
sl@0: 
sl@0: TInt BytePairCompress(TUint8* dst, TUint8* src, TInt size)
sl@0: 	{
sl@0: 	TInt originalSize = size;
sl@0: 	TUint8* dst2 = dst+size*2;
sl@0: 	TUint8* in = src;
sl@0: 	TUint8* out = dst;
sl@0: 
sl@0: 	TUint8 tokens[0x100*3];
sl@0: 	TInt tokenCount = 0;
sl@0: 
sl@0: 	CountBytes(in,size);
sl@0: 
sl@0: 	TInt marker = -1;
sl@0: 	TInt overhead = 1+3+LeastCommonByte(marker);
sl@0: 	ByteUsed(marker);
sl@0: 
sl@0: 	TUint8* inEnd = in+size;
sl@0: 	TUint8* outStart = out;
sl@0: 	while(in<inEnd)
sl@0: 		{
sl@0: 		TInt b=*in++;
sl@0: 		if(b==marker)
sl@0: 			*out++ = (TUint8)b;
sl@0: 		*out++ = (TUint8)b;
sl@0: 		}
sl@0: 	size = out-outStart;
sl@0: 
sl@0: 	TInt outToggle = 1;
sl@0: 	in = dst;
sl@0: 	out = dst2;
sl@0: 
sl@0: 	for(TInt r=256; r>0; --r)
sl@0: 		{
sl@0: 		TInt byte;
sl@0: 		TInt byteCount = LeastCommonByte(byte);
sl@0: 		TInt pair;
sl@0: 		TInt pairCount = MostCommonPair(pair,in,size,overhead+1,marker);
sl@0: 		TInt saving = pairCount-byteCount;
sl@0: 		if(saving<=overhead)
sl@0: 			break;
sl@0: 
sl@0: 		overhead = 3;
sl@0: 		if(tokenCount>=32)
sl@0: 			overhead = 2;
sl@0: 
sl@0: 		TUint8* d=tokens+3*tokenCount;
sl@0: 		++tokenCount;
sl@0: 		*d++ = (TUint8)byte;
sl@0: 		ByteUsed(byte);
sl@0: 		*d++ = (TUint8)pair;
sl@0: 		ByteUsed(pair&0xff);
sl@0: 		*d++ = (TUint8)(pair>>8);
sl@0: 		ByteUsed(pair>>8);
sl@0: 		++GlobalPairs[pair];
sl@0: 
sl@0: 		inEnd = in+size;
sl@0: 		outStart = out;
sl@0: 		while(in<inEnd)
sl@0: 			{
sl@0: 			TInt b=*in++;
sl@0: 			if(b==marker)
sl@0: 				{
sl@0: 				*out++ = (TUint8)marker;
sl@0: 				b = *in++;
sl@0: 				}
sl@0: 			else if(b==byte)
sl@0: 				{
sl@0: 				*out++ = (TUint8)marker;
sl@0: 				--byteCount;
sl@0: 				}
sl@0: 			else if(b==(pair&0xff) && in<inEnd && *in==(pair>>8))
sl@0: 				{
sl@0: 				++in;
sl@0: 				b = byte;
sl@0: 				--pairCount;
sl@0: 				}
sl@0: 			*out++ = (TUint8)b;
sl@0: 			}
sl@0: 		ASSERT(!byteCount);
sl@0: 		ASSERT(!pairCount);
sl@0: 		size = out-outStart;
sl@0: 
sl@0: 		outToggle ^= 1;
sl@0: 		if(outToggle)
sl@0: 			{
sl@0: 			in = dst;
sl@0: 			out = dst2;
sl@0: 			}
sl@0: 		else
sl@0: 			{
sl@0: 			in = dst2;
sl@0: 			out = dst;
sl@0: 			}
sl@0: 		}
sl@0: 
sl@0: 	// sort tokens with a bubble sort...
sl@0: 	for(TInt x=0; x<tokenCount-1; x++)
sl@0: 		for(TInt y=x+1; y<tokenCount; y++)
sl@0: 			if(tokens[x*3]>tokens[y*3])
sl@0: 				{
sl@0: 				TInt z = tokens[x*3];
sl@0: 				tokens[x*3] = tokens[y*3];
sl@0: 				tokens[y*3] = (TUint8)z;
sl@0: 				z = tokens[x*3+1];
sl@0: 				tokens[x*3+1] = tokens[y*3+1];
sl@0: 				tokens[y*3+1] = (TUint8)z;
sl@0: 				z = tokens[x*3+2];
sl@0: 				tokens[x*3+2] = tokens[y*3+2];
sl@0: 				tokens[y*3+2] = (TUint8)z;
sl@0: 				}
sl@0: 
sl@0: 	// check for not being able to compress...
sl@0: 	if(size>originalSize)
sl@0: 		{
sl@0: 		*dst++ = 0; // store zero token count
sl@0: 		memcpy(dst,src,originalSize); // store original data
sl@0: 		return originalSize+1;
sl@0: 		}
sl@0: 
sl@0: 	// make sure data is in second buffer (dst2)
sl@0: 	if(in!=dst2)
sl@0: 		memcpy(dst2,dst,size);
sl@0: 
sl@0: 	// store tokens...
sl@0: 	TUint8* originalDst = dst;
sl@0: 	*dst++ = (TUint8)tokenCount;
sl@0: 	if(tokenCount)
sl@0: 		{
sl@0: 		*dst++ = (TUint8)marker;
sl@0: 		if(tokenCount<32)
sl@0: 			{
sl@0: 			memcpy(dst,tokens,tokenCount*3);
sl@0: 			dst += tokenCount*3;
sl@0: 			}
sl@0: 		else
sl@0: 			{
sl@0: 			TUint8* bitMask = dst;
sl@0: 			memset(bitMask,0,32);
sl@0: 			dst += 32;
sl@0: 			TUint8* d=tokens;
sl@0: 			do
sl@0: 				{
sl@0: 				TInt t=*d++;
sl@0: 				bitMask[t>>3] |= (1<<(t&7));
sl@0: 				*dst++ = *d++;
sl@0: 				*dst++ = *d++;
sl@0: 				}
sl@0: 			while(--tokenCount);
sl@0: 			}
sl@0: 		}
sl@0: 	// store data...
sl@0: 	memcpy(dst,dst2,size);
sl@0: 	dst += size;
sl@0: 
sl@0: 	// get stats...
sl@0: 	++GlobalTokenCounts[tokenCount];
sl@0: 
sl@0: 	// return total size of compressed data...
sl@0: 	return dst-originalDst;
sl@0: 	}
sl@0: 
sl@0: #endif
sl@0: #endif