diff -r 820b22e13ff1 -r 39c28ec933dd imgtools/imglib/compress/byte_pair.cpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/imgtools/imglib/compress/byte_pair.cpp	Mon May 10 19:54:49 2010 +0100
@@ -0,0 +1,571 @@
+/*
+* 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::Initialize(TUint8* data, TInt size)
+{
+    TUint32 *p;
+    p = (TUint32*)PairCount;
+    while(p < (TUint32*)PairCount+0x10000) {
+        *p = 0xffff0000;
+        p ++;
+    }
+    p = (TUint32*)PairBuffer;
+    while (p < (TUint32*)PairBuffer + sizeof(PairBuffer) / 4) {
+        *p = 0xffffffff;
+        p++;
+    }
+    PairBufferNext = 0;
+    p = (TUint32*)PairPos;
+    while (p < (TUint32*)PairPos + sizeof(PairPos) /4 ) {
+        *p = 0xffffffff;
+        p ++;
+    }
+    PairPosNext = 0;
+    p = (TUint32*)PairLists;
+    while (p < (TUint32*)PairLists + sizeof(PairLists) / 4) {
+        *p = 0xffffffff;
+        p ++;
+    }
+    PairListHigh = 0;
+    
+    CountBytes(data,size);
+    marker = -1;
+    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)
+{
+    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;
+            }
+    }
+    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;
+    TInt overhead;
+
+    TUint8 * dst2 = dst + size*2;
+    memcpy (dst2, src, size);
+    Initialize (dst2, size);
+    //DumpList(dst2, size);
+    for(TInt r=256; r>0; --r)
+    {   
+        TInt byte;
+        TInt byteCount = LeastCommonByte(byte);
+        if (iFastCompress && byteCount) break;
+        //if(byteCount) break;
+        TInt pair;
+        TInt pairCount = MostCommonPair(pair);
+        TInt saving = pairCount-byteCount;
+
+        //cout << "byte: <" << hex << setw(2) << setfill('0') <<  byte << ">"  << byteCount << endl;
+        //cout << "pair: <" << hex << setw(4) << setfill('0') <<  pair << ">" << pairCount << endl;
+        overhead = 3;
+        if(tokenCount>=32)
+            overhead = 2;
+        if(saving<=overhead)
+            break;
+
+        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];
+
+            //clock_t ClockReplace1 ,ClockReplace2;
+            TUint16 index = PairCount[pair].Index;
+            TUint16 count = PairCount[pair].Count;
+            TUint16 posindex = PairBuffer[index].Pos;
+            TUint16 headpos, tailpos, tmppos, 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);
+                    }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;
+
+        //cout << "Pair: <" << pair << "> completed" << endl;
+        //DumpList(dst2,size);
+        //for (int i=0;i<100;i++)
+          //  cout << " ";
+        //cout << endl;
+    }
+
+    // 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
+    {
+        *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;
+}
+
+
+TInt BytePairCompress(TUint8* dst, TUint8* src, TInt size, CBytePair *aBPE)
+{
+    TUint8 PakBuffer[MaxBlockSize*4];
+    TUint8 UnpakBuffer[MaxBlockSize];
+    ASSERT(size<=MaxBlockSize);
+    TInt compressedSize = aBPE->Compress(PakBuffer,src,size);
+    TUint8* pakEnd;
+    TInt us = aBPE->Decompress(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;
+}