--- a/imgtools/imglib/compress/byte_pair.cpp Wed Jun 16 16:51:40 2010 +0300
+++ b/imgtools/imglib/compress/byte_pair.cpp Wed Jun 23 16:56:47 2010 +0800
@@ -1,571 +1,638 @@
-/*
-* 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;
-}
+/*
+* 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
+ {
+ *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;
+}