// Copyright (c) 2005-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 "byte_pair.h"

#undef ASSERT

#define ASSERT(c)	if(!(c))	\

						{		\

						__BREAKPOINT()	\

						}

const TInt MaxBlockSize = 0x1000;

TUint16 PairCount[0x10000];

TUint16 PairBuffer[MaxBlockSize*2];

TUint16 GlobalPairs[0x10000] = {0};

TUint16 GlobalTokenCounts[0x100] = {0};

TUint16 ByteCount[0x100+4];

void CountBytes(TUint8* data, TInt size)

	{

	memset(ByteCount,0,sizeof(ByteCount));

	TUint8* dataEnd = data+size;

	while(data<dataEnd)

		++ByteCount[*data++];

	}

inline void ByteUsed(TInt b)

	{

	ByteCount[b] = 0xffff;

	}

// 11915620

// 11913551  	return -ByteCount[b1]-ByteCount[b2];

// 11913185

#if 0

int TieBreak(int b1,int b2)

	{

	int i;

	int x = 0;

	for(i=0; i<0x100; i++)

		x += PairCount[(b1<<8)+i];

	int y = 0;

	for(i=b2; i<0x10000; i+=0x100)

		y += PairCount[i];

	return -x-y;

	}

#endif

int TieBreak(int b1,int b2)

	{

	return -ByteCount[b1]-ByteCount[b2];

	}

TInt MostCommonPair(TInt& pair, TUint8* data, TInt size, TInt minFrequency, TInt marker)

	{

	memset(PairCount,0,sizeof(PairCount));

	TUint8* dataEnd = data+size-1;

	TInt pairsFound = 0;

	TInt lastPair = -1;

	while(data<dataEnd)

		{

		TInt b1 = *data++;

		if(b1==marker)

			{

			// skip marker and following byte

			lastPair = -1;

			++data;

			continue;

			}

		TInt b2 = *data;

		if(b2==marker)

			{

			// skip marker and following byte

			lastPair = -1;

			data+=2;

			continue;

			}

		TInt p = (b2<<8)|b1;

		if(p==lastPair)

			{

			// ensure a pair of identical bytes don't get double counted

			lastPair = -1;

			continue;

			}

		lastPair = p;

		++PairCount[p];

		if(PairCount[p]==minFrequency)

			PairBuffer[pairsFound++] = (TUint16)p;

		}

	TInt bestCount = -1;

	TInt bestPair = -1;

	TInt bestTieBreak = 0;

	TInt p;

	while(pairsFound--)

		{

		p = PairBuffer[pairsFound];

		TInt f=PairCount[p];

		if(f>bestCount)

			{

			bestCount = f;

			bestPair = p;

			bestTieBreak = TieBreak(p&0xff,p>>8);

			}

		else if(f==bestCount)

			{

			TInt tieBreak = TieBreak(p&0xff,p>>8);

			if(tieBreak>bestTieBreak)

				{

				bestCount = f;

				bestPair = p;

				bestTieBreak = tieBreak;

				}

			}

		}

	pair = bestPair;

	return bestCount;

	}

TInt LeastCommonByte(TInt& byte)

	{

	TInt bestCount = 0xffff;

	TInt bestByte = -1;

	for(TInt b=0; b<0x100; b++)

		{

		TInt f = ByteCount[b];

		if(f<bestCount)

			{

			bestCount = f;

			bestByte = b;

			}

		}

	byte = bestByte;

	return bestCount;

	}

TInt Pak(TUint8* dst, TUint8* src, TInt size)

	{

	TInt originalSize = size;

	TUint8* dst2 = dst+size*2;

	TUint8* in = src;

	TUint8* out = dst;

	TUint8 tokens[0x100*3];

	TInt tokenCount = 0;

	CountBytes(in,size);

	TInt marker = -1;

	TInt overhead = 1+3+LeastCommonByte(marker);

	ByteUsed(marker);

	TUint8* inEnd = in+size;

	TUint8* outStart = out;

	while(in<inEnd)

		{

		TInt b=*in++;

		if(b==marker)

			*out++ = (TUint8)b;

		*out++ = (TUint8)b;

		}

	size = out-outStart;

	TInt outToggle = 1;

	in = dst;

	out = dst2;

	for(TInt r=256; r>0; --r)

		{

		TInt byte;

		TInt byteCount = LeastCommonByte(byte);

		TInt pair;

		TInt pairCount = MostCommonPair(pair,in,size,overhead+1,marker);

		TInt saving = pairCount-byteCount;

		if(saving<=overhead)

			break;

		overhead = 3;

		if(tokenCount>=32)

			overhead = 2;

		TUint8* d=tokens+3*tokenCount;

		++tokenCount;

		*d++ = (TUint8)byte;

		ByteUsed(byte);

		*d++ = (TUint8)pair;

		ByteUsed(pair&0xff);

		*d++ = (TUint8)(pair>>8);

		ByteUsed(pair>>8);

		++GlobalPairs[pair];

		inEnd = in+size;

		outStart = out;

		while(in<inEnd)

			{

			TInt b=*in++;

			if(b==marker)

				{

				*out++ = (TUint8)marker;

				b = *in++;

				}

			else if(b==byte)

				{

				*out++ = (TUint8)marker;

				--byteCount;

				}

			else if(b==(pair&0xff) && in<inEnd && *in==(pair>>8))

				{

				++in;

				b = byte;

				--pairCount;

				}

			*out++ = (TUint8)b;

			}

		ASSERT(!byteCount);

		ASSERT(!pairCount);

		size = out-outStart;

		outToggle ^= 1;

		if(outToggle)

			{

			in = dst;

			out = dst2;

			}

		else

			{

			in = dst2;

			out = dst;

			}

		}

	// sort tokens with a bubble sort...

	for(TInt x=0; x<tokenCount-1; x++)

		for(TInt y=x+1; y<tokenCount; y++)

			if(tokens[x*3]>tokens[y*3])

				{

				TInt z = tokens[x*3];

				tokens[x*3] = tokens[y*3];

				tokens[y*3] = (TUint8)z;

				z = tokens[x*3+1];

				tokens[x*3+1] = tokens[y*3+1];

				tokens[y*3+1] = (TUint8)z;

				z = tokens[x*3+2];

				tokens[x*3+2] = tokens[y*3+2];

				tokens[y*3+2] = (TUint8)z;

				}

	// check for not being able to compress...

	if(size>originalSize)

		{

		*dst++ = 0; // store zero token count

		memcpy(dst,src,originalSize); // store original data

		return originalSize+1;

		}

	// make sure data is in second buffer (dst2)

	if(in!=dst2)

		memcpy(dst2,dst,size);

	// store tokens...

	TUint8* originalDst = dst;

	*dst++ = (TUint8)tokenCount;

	if(tokenCount)

		{

		*dst++ = (TUint8)marker;

		if(tokenCount<32)

			{

			memcpy(dst,tokens,tokenCount*3);

			dst += tokenCount*3;

			}

		else

			{

			TUint8* bitMask = dst;

			memset(bitMask,0,32);

			dst += 32;

			TUint8* d=tokens;

			do

				{

				TInt t=*d++;

				bitMask[t>>3] |= (1<<(t&7));

				*dst++ = *d++;

				*dst++ = *d++;

				}

			while(--tokenCount);

			}

		}

	// store data...

	memcpy(dst,dst2,size);

	dst += size;

	// get stats...

	++GlobalTokenCounts[tokenCount];

	// return total size of compressed data...

	return dst-originalDst;

	}

TInt Unpak(TUint8* dst, TInt dstSize, TUint8* src, TInt srcSize, TUint8*& srcNext)

	{

	TUint8* dstStart = dst;

	TUint8* dstEnd = dst+dstSize;

	TUint8* srcEnd = src+srcSize;

	TUint32 LUT[0x100/2];

	TUint8* LUT0 = (TUint8*)LUT;

	TUint8* LUT1 = LUT0+0x100;

	TUint8 stack[0x100];

	TUint8* stackStart = stack+sizeof(stack);

	TUint8* sp = stackStart;

	TUint32 marker = ~0u;

	TInt numTokens;

	TUint32 p1;

	TUint32 p2;

	TUint32* l = (TUint32*)LUT;

	TUint32 b = 0x03020100;

	TUint32 step = 0x04040404;

	do

		{

		*l++ = b;

		b += step;

		}

	while(b>step);

	if(src>=srcEnd)

		goto error;

	numTokens = *src++;

	if(numTokens)

		{

		if(src>=srcEnd)

			goto error;

		marker = *src++;

		LUT0[marker] = (TUint8)~marker;

		if(numTokens<32)

			{

			TUint8* tokenEnd = src+3*numTokens;

			if(tokenEnd>srcEnd)

				goto error;

			do

				{

				TInt b = *src++;

				TInt p1 = *src++;

				TInt p2 = *src++;

				LUT0[b] = (TUint8)p1;

				LUT1[b] = (TUint8)p2;

				}

			while(src<tokenEnd);

			}

		else

			{

			TUint8* bitMask = src;

			src += 32;

			if(src>srcEnd)

				goto error;

			TInt b=0;

			do

				{

				TUint8 mask = bitMask[b>>3];

				if(mask&(1<<(b&7)))

					{

					if(src>srcEnd)

						goto error;

					TInt p1 = *src++;

					if(src>srcEnd)

						goto error;

					TInt p2 = *src++;

					LUT0[b] = (TUint8)p1;

					LUT1[b] = (TUint8)p2;		

					--numTokens;

					}

				++b;

				}

			while(b<0x100);

			if(numTokens)

				goto error;

			}

		}

	if(src>=srcEnd)

		goto error;

	b = *src++;

	if(dst>=dstEnd)

		goto error;

	p1 = LUT0[b];

	if(p1!=b)

		goto not_single;

next:

	if(src>=srcEnd)

		goto done_s;

	b = *src++;

	*dst++ = (TUint8)p1;

	if(dst>=dstEnd)

		goto done_d;

	p1 = LUT0[b];

	if(p1==b)

		goto next;

not_single:

	if(b==marker)

		goto do_marker;

do_pair:

	p2 = LUT1[b];

	b = p1;

	p1 = LUT0[b];

	if(sp<=stack)

		goto error;

	*--sp = (TUint8)p2;

recurse:

	if(b!=p1)

		goto do_pair;

	if(sp==stackStart)

		goto next;

	b = *sp++;

	if(dst>=dstEnd)

		goto error;

	*dst++ = (TUint8)p1;

	p1 = LUT0[b];

	goto recurse;

do_marker:

	if(src>=srcEnd)

		goto error;

	p1 = *src++;

	goto next;

error:

	srcNext = 0;

	return KErrCorrupt;

done_s:

	*dst++ = (TUint8)p1;

	srcNext = src;

	return dst-dstStart;

done_d:

	if(dst>=dstEnd)

		--src;

	srcNext = src;

	return dst-dstStart;

	}

TUint8 PakBuffer[MaxBlockSize*4];

TUint8 UnpakBuffer[MaxBlockSize];

TInt BytePairCompress(TUint8* dst, TUint8* src, TInt size)

	{

	ASSERT(size<=MaxBlockSize);

	TInt compressedSize = Pak(PakBuffer,src,size);

	TUint8* pakEnd;

	TInt us = Unpak(UnpakBuffer,MaxBlockSize,PakBuffer,compressedSize,pakEnd);

	ASSERT(us==size)

	ASSERT(pakEnd==PakBuffer+compressedSize)

	ASSERT(!memcmp(src,UnpakBuffer,size))

	if(compressedSize>=size)

		return KErrTooBig;

	memcpy(dst,PakBuffer,compressedSize);

	return compressedSize;

	}