/*

* 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 the License "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"

#define __BREAKPOINT()

#undef ASSERT

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

{		\

    __BREAKPOINT()	\

}

#include <ctime>

clock_t ClockCompress = 0;

//#define DEBUG_ASSERT

#ifdef DEBUG_ASSERT

void myassert(int c) {

    if (!(c)) {

        cout <<"myassertion failed" << endl;

    }

}

#endif

void CBytePair::SortN(TUint16 *a, TInt n)

{

    //bubble sort

    TInt i,j;

    TUint16 tmp;

    for (i=0;i<n-1;i++){

        for (j=i+1;j<=n-1;j++){

            if (a[j]<a[i]) {

                tmp = a[j];

                a[j]=a[i];

                a[i]=tmp;

            }

        }

    }

}

void CBytePair::InsertN(TUint16 *a, TInt n, TUint16 v)

{

    TInt i;

    for (i=n-1;i>=0;i--){

        if (a[i] > v)

            a[i+1]=a[i];

        else{

            break;

        }

    }

    a[i+1] = v;

}

TInt CBytePair::PosN(TUint16 index, TInt n){

    myassert(n<=PairCount[PairBuffer[index].Pair].Count);

    TUint16 FirstN[1+3+0x1000/256+1];

    TInt i = 0;

    TUint16 posindex;

    posindex = PairBuffer[index].Pos;

    while (i<n) {

        FirstN[i] = PairPos[posindex].Pos;

        posindex = PairPos[posindex].Next;

        i++;

    }

    SortN(FirstN, n);

    while (posindex!=PosEnd){

        InsertN(FirstN, n, PairPos[posindex].Pos);

        posindex=PairPos[posindex].Next;

    }

    return FirstN[n-1];

}

void CBytePair::Initialize(TUint8* data, TInt size)

{

#if defined(WIN32)

    TUint32 *p = reinterpret_cast<TUint32*>(PairCount);

    TUint32 *end = p + 0x10000;

    while(p < end) {

        *p++ = 0xffff0000;

    }

#else

    for(int i = 0 ; i < 0x10000 ; i ++){

	PairCount[i].Count = 0 ;

	PairCount[i].Index = 0xffff;

    }	

#endif

    memset(reinterpret_cast<char*>(PairBuffer),0xff, sizeof(PairBuffer)); 

    PairBufferNext = 0;

    memset(reinterpret_cast<char*>(PairPos),0xff, sizeof(PairPos)); 

    PairPosNext = 0;

    memset(reinterpret_cast<char*>(PairLists),0xff, sizeof(PairLists)); 

    PairListHigh = 0;

    CountBytes(data,size);

    marker = -1;

    markerCount = LeastCommonByte(marker);

    ByteUsed(marker);

    TUint8 *pData, *pMask;

    TUint16 pair;

    pData=data, pMask=Mask; 

    if (*pData == marker)

        *pMask = ByteMarked;

    else if (*(pData+1) == marker)

        *pMask = ByteTail;

    else { 

        *pMask = ByteHead;

        pair = (TUint16)(*pData | *(pData+1) << 8);

        InsertPair(pair, 0);

    }

    for (pData++, pMask++; pData < data+size-1; pData++, pMask++) {

        if (*pData == marker){

            *pMask = ByteMarked;

            continue;

        }

        if (*(pData+1) == marker){

            *pMask = ByteTail;

            continue;

        }

        if ((*pData == *(pData+1)) && (*pData == *(pData-1))&& (*(pMask-1) == ByteHead)){

            *pMask = ByteTail;

            continue;

        }

        *pMask = ByteHead;

        pair = (TUint16)(*pData | *(pData+1) << 8);

        InsertPair(pair,(TUint16)(pData-data));

    }

    if (*pData == marker)

        *pMask = ByteMarked;

    else 

        *pMask = ByteTail;

}

TInt CBytePair::MostCommonPair(TInt& pair, TInt minFrequency)

{

    TUint16 index = PairLists[PairListHigh];

    TUint16 tmpindex = index; 

    TUint16 p = PairBuffer[index].Pair;

    TInt tieBreak, bestTieBreak;

    bestTieBreak = -ByteCount[p&0xff] - ByteCount[p>>8];

    while(PairBuffer[tmpindex].Next != PosEnd) {

            tmpindex = PairBuffer[tmpindex].Next;

            p = PairBuffer[tmpindex].Pair;

            tieBreak = -ByteCount[p&0xff]-ByteCount[p>>8];

            if(tieBreak>bestTieBreak)

            {

                index = tmpindex;

                bestTieBreak = tieBreak;

            }

            else if(tieBreak==bestTieBreak){

                if (minFrequency > PairListHigh)

                    break;

                if (PosN(tmpindex, minFrequency) > PosN(index,minFrequency)){

                    index = tmpindex;

                }

            }

    }

    pair = PairBuffer[index].Pair;

    return PairListHigh;

}

TInt CBytePair::LeastCommonByte(TInt& byte)

{

    TInt bestCount = 0xffff;

    TInt bestByte = -1;

    TInt b;

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

    {

        TInt f = ByteCount[b];

        if(f<bestCount)

        {

            bestCount = f;

            bestByte = b;

        }

    }

    byte = bestByte;

    return bestCount;

}

TInt CBytePair::Compress(TUint8* dst, TUint8* src, TInt size)

{

    clock_t ClockStart = clock();

    TUint8 tokens[0x100*3];

    TInt tokenCount = 0;

    TUint8 * dst2 = dst + size*2;

    memcpy (dst2, src, size);

    Initialize (dst2, size);

    TInt overhead = 1+3+markerCount;

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

    {   

        TInt byte;

        TInt byteCount = LeastCommonByte(byte);

        TInt pair;

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

        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);

            TUint16 index = PairCount[pair].Index;

            TUint16 count = PairCount[pair].Count;

            TUint16 posindex = PairBuffer[index].Pos;

            TUint16 headpos, tailpos, tmppos, tmpposprev, bytepos;

            TUint16 tmppair;

            // Remove pairs

            while (posindex != PosEnd) {

                headpos = PairPos[posindex].Pos;

                tailpos = (TUint16)(headpos + 1);

                while (Mask[tailpos] == ByteRemoved){

                    tailpos ++;

                    myassert(tailpos < MaxBlockSize);

                }

                GetPairBackward(dst2, headpos, tmppos, tmppair);

                if ((tmppos != PosEnd) && (Mask[tmppos] == ByteHead)) {

                    RemovePair(tmppair, tmppos);

                    Mask[tmppos] = ByteTail;

                }

                if (Mask[tailpos] == ByteHead) {

                    GetPairForward(dst2, tailpos, size, tmppos, tmppair);

                    myassert(tmppos!=PosEnd);

                    RemovePair(tmppair, tmppos);

                    Mask[tmppos] = ByteTail;

                }

                posindex = PairPos[posindex].Next;

            }

            if (byteCount) {

                bytepos = ByteIndex[byte];

                while(bytepos != PosEnd){

                    if (Mask[bytepos] == ByteRemoved) {

                        bytepos = BytePos[bytepos];

                        continue;

                    }

                    GetPairBackward(dst2, bytepos, tmppos, tmppair);

                    if ((tmppos != PosEnd) && (Mask[tmppos] == ByteHead)) {

                        RemovePair(tmppair, tmppos);

                        Mask[tmppos] = ByteTail;

                    }

                    if (Mask[bytepos] == ByteHead) {

                        GetPairForward(dst2, bytepos, size, tmppos, tmppair);

                        myassert(tmppos!=PosEnd);

                        RemovePair(tmppair, tmppos);

                        Mask[tmppos] = ByteTail;

                    }

                    bytepos = BytePos[bytepos];

                }

            }

            // Update buffer

            posindex = PairBuffer[index].Pos;

            while (posindex != PosEnd){

                headpos = PairPos[posindex].Pos;

                tailpos = (TUint16)(headpos + 1);

                while (Mask[tailpos] == ByteRemoved){

                    tailpos ++;

                    myassert(tailpos < MaxBlockSize);

                }

                dst2[headpos] = (TUint8)byte;

                dst2[tailpos] = 0xff;

                Mask[headpos] = ByteNew;

                Mask[tailpos] = ByteRemoved;

                posindex = PairPos[posindex].Next;

            }

            if (byteCount) {

                bytepos = ByteIndex[byte];

                while(bytepos != PosEnd) {

                    Mask[bytepos] = ByteMarked;

                    bytepos = BytePos[bytepos];

                }

            }

            // Insert new pairs

            posindex = PairBuffer[index].Pos;

            TUint16 firstpos, lastpos;

            while (posindex != PosEnd){

                firstpos = PairPos[posindex].Pos;

                lastpos = firstpos;

                if (Mask[firstpos] == ByteNew) {

                    while ((firstpos > 0) && ((Mask[firstpos] == ByteNew) || (Mask[firstpos] == ByteRemoved)))

                        firstpos --;

                    while (Mask[firstpos] != ByteNew)

                        firstpos ++;

                    while ((lastpos < MaxBlockSize-1) && ((Mask[lastpos] == ByteNew)||(Mask[lastpos] == ByteRemoved)))

                        lastpos ++;

                    while (Mask[lastpos] != ByteNew)

                        lastpos --;

                    GetPairForward(dst2, lastpos, size, tmppos, tmppair);

                    if (tmppos != PosEnd) {

                        Mask[lastpos] = ByteHead;

                        InsertPair(tmppair, tmppos);

                        // Potential new pair after the new one

                        tmppos = (TUint16)(lastpos+1);

                        while(Mask[tmppos]==ByteRemoved) 

                            tmppos ++;

                        if (Mask[tmppos]==ByteTail){

                            tmpposprev = tmppos;

                            tmppos ++;

                            while (tmppos<size){

                                if (Mask[tmppos]==ByteRemoved){

                                    tmppos++;

                                    continue;

                                }

                                if (Mask[tmppos]==ByteMarked)

                                    break;

                                if (dst2[tmppos]!=dst2[tmpposprev])

                                    break;

                                if (Mask[tmpposprev]==ByteTail){

                                    //myassert(Mask[tmppos]==ByteHead);

                                    InsertPair((TUint16)(dst2[tmppos]|dst2[tmppos]<<8), tmpposprev);

                                    Mask[tmpposprev]=ByteHead;

                                }else{

                                    myassert(Mask[tmpposprev]==ByteHead);

                                    RemovePair((TUint16)(dst2[tmppos]|dst2[tmppos]<<8), tmpposprev);

                                    Mask[tmpposprev]=ByteTail;

                                }

                                tmpposprev = tmppos;

                                tmppos ++;

                            }

                        }

                    }else {

                        Mask[lastpos] = ByteTail;

                    }

                    GetPairBackward(dst2, firstpos, tmppos, tmppair);

                    if (tmppos != PosEnd) {

                        Mask[tmppos] = ByteHead;

                        InsertPair(tmppair, tmppos);

                    }

                    while (firstpos < lastpos) {

                        tmppair = (TUint16)(dst2[firstpos] | dst2[firstpos]<<8);

                        InsertPair(tmppair, firstpos);

                        Mask[firstpos] = ByteHead;

                        tmppos = (TUint16)(firstpos + 1);

                        while (Mask[tmppos] == ByteRemoved)

                            tmppos ++;

                        myassert(tmppos <= lastpos);

                        if (tmppos == lastpos)

                            break;

                        Mask[tmppos] = ByteTail;

                        firstpos = (TUint16)(tmppos + 1);

                        while ((firstpos < lastpos) && (Mask[firstpos] == ByteRemoved))

                            firstpos ++;

                    }

                }

                posindex = PairPos[posindex].Next;

            }

            // Remove the pair from PairLists

            if (PairBuffer[index].Prev == PosHead){

                if (PairBuffer[index].Next == PosEnd) {

                    PairLists[count] = PosEnd;

                } else {

                    PairLists[count] = PairBuffer[index].Next;

                    PairBuffer[PairBuffer[index].Next].Prev = PosHead;

                }

            } else {

                if (PairBuffer[index].Next == PosEnd){

                    PairBuffer[PairBuffer[index].Prev].Next = PosEnd;

                } else {

                    PairBuffer[PairBuffer[index].Prev].Next = PairBuffer[index].Next;

                    PairBuffer[PairBuffer[index].Next].Prev = PairBuffer[index].Prev;

                }

            }

            while (PairLists[PairListHigh] == PosEnd)

                PairListHigh --;

            myassert(PairListHigh >= 1);

            PairBuffer[index].Next = PosEnd;

            PairBuffer[index].Prev = PosEnd;

            PairCount[pair].Count = 0;

            PairCount[pair].Index = PosEnd;

    }

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

            }

    TUint8* originalDst = dst;

    *dst++ = (TUint8)tokenCount;

    TInt tmpTokenCount = 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);

        }

    }

    if (tmpTokenCount == 0) {

        memcpy(dst,dst2,size);

        dst += size;

    } else {

        TUint16 pos = 0;

        for (TUint8 *p=dst2; p < dst2+size; p++, pos++) {

            if (Mask[pos] == ByteRemoved)

                continue;

            if (Mask[pos]== ByteMarked){

                *dst++ = (TUint8)marker;

            }

            *dst++ = *p;

        }

    }

    ClockCompress += clock() - ClockStart;

    return (dst-originalDst);

}

TInt CBytePair::Decompress(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

    {