// 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;
	}