--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/imgtools/imglib/compress/byte_pair.h Mon May 10 19:54:49 2010 +0100
@@ -0,0 +1,356 @@
+/*
+* 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:
+*
+*/
+
+#ifndef BYTE_PAIR_H
+#define BYTE_PAIR_H
+
+#ifdef __VC32__
+ #ifdef __MSVCDOTNET__
+ #include <strstream>
+ #include <iomanip>
+ #else //!__MSVCDOTNET__
+ #include <strstrea.h>
+ #include <iomanip.h>
+ #endif //__MSVCDOTNET__
+#else // !__VC32__
+#ifdef __TOOLS2__
+#include <sstream>
+#include <iomanip>
+#include <iostream>
+using namespace std;
+#else
+ #include <strstream.h>
+ #include <iomanip.h>
+ #endif
+#endif // __VC32__
+
+//#include <myassert.h>
+//#define DEBUG_ASSERT
+#ifdef DEBUG_ASSERT
+void myassert(int c);
+#else
+#define myassert(c)
+#endif
+
+#include <e32cmn.h>
+typedef struct {
+ TUint16 Count;
+ TUint16 Index;
+} TPairCountIndex;
+
+typedef struct {
+ TUint16 Pair;
+ TUint16 Next;
+ TUint16 Prev;
+ TUint16 Pos;
+} TPair;
+typedef struct {
+ TUint16 Pos;
+ TUint16 Next;
+} TPos;
+
+const TInt MaxBlockSize = 0x1000;
+
+const TUint16 PosEnd = 0xffff;
+const TUint16 PosHead = 0xfffe;
+const TUint8 ByteRemoved = 'R';
+const TUint8 ByteMarked = 'M';
+const TUint8 ByteHead = 'H';
+const TUint8 ByteTail = 'T';
+const TUint8 ByteNew = 'N';
+class CBytePair {
+ private:
+ TBool iFastCompress;
+ TInt marker;
+ TUint8 Mask[MaxBlockSize];
+ TUint16 ByteCount[0x100];
+ TUint16 ByteIndex[0x100];
+ TUint16 BytePos[MaxBlockSize];
+ TPairCountIndex PairCount[0x10000];
+ TPair PairBuffer[MaxBlockSize*2];
+ TInt PairBufferNext;
+ TPos PairPos[MaxBlockSize*3];
+ TUint16 PairPosNext;
+ TUint16 PairLists[MaxBlockSize/2+2];
+ TInt PairListHigh;
+
+ void CountBytes(TUint8* data, TInt size) {
+ TUint32 *p;
+ p = (TUint32*)ByteCount;
+ while (p < (TUint32*)ByteCount + sizeof(ByteCount)/4) {
+ *p++ = 0;
+ }
+ p = (TUint32*)ByteIndex;
+ while (p < (TUint32*)ByteIndex + sizeof(ByteIndex)/4) {
+ *p++ = 0xffffffff;
+ }
+ p = (TUint32*)BytePos;
+ while (p< (TUint32*)BytePos + sizeof(BytePos)/4) {
+ *p++ = 0xffffffff;
+ }
+ TUint8* dataEnd = data+size;
+ int pos = 0;
+ while(data<dataEnd) {
+ BytePos[pos] = ByteIndex[*data];
+ ByteIndex[*data] = (TUint16)pos;
+ pos ++;
+ ++ByteCount[*data++];
+ }
+ }
+ inline void ByteUsed(TInt b) {
+ ByteCount[b] = 0xffff;
+ }
+ int TieBreak(int b1,int b2) {
+ return -ByteCount[b1]-ByteCount[b2];
+ }
+
+ void Initialize(TUint8* data, TInt size);
+ TInt MostCommonPair(TInt& pair);
+ TInt LeastCommonByte(TInt& byte);
+ inline void InsertPair(const TUint16 pair, const TUint16 pos) {
+ //ClockInsert1 = clock();
+ //cout << "Pair:" << hex << setw(4) << setfill ('0') << pair << endl;
+ TUint16 count = PairCount[pair].Count;
+ if (0==count) {
+ PairCount[pair].Index = (TUint16)PairBufferNext;
+ if (PairLists[1] != PosEnd) {
+ PairBuffer[PairLists[1]].Prev = (TUint16)PairBufferNext;
+ }
+ PairBuffer[PairBufferNext].Next = PairLists[1];
+ PairBuffer[PairBufferNext].Prev = PosHead;
+ PairLists[1] = (TUint16)PairBufferNext;
+ PairBuffer[PairBufferNext].Pair = pair;
+ PairBuffer[PairBufferNext].Pos = PairPosNext;
+ PairBufferNext ++;
+ myassert(PairBufferNext < MaxBlockSize*2);
+ PairPos[PairPosNext].Pos = pos;
+ PairPos[PairPosNext].Next = PosEnd;
+ } else {
+ TUint16 index = PairCount[pair].Index;
+
+ if (PairBuffer[index].Next == PosEnd){
+ if (PairBuffer[index].Prev == PosHead){
+ PairLists[count] = PosEnd;
+ } else {
+ PairBuffer[PairBuffer[index].Prev].Next = PosEnd;
+ }
+ } else {
+ if (PairBuffer[index].Prev == PosHead){
+ PairLists[count] = PairBuffer[index].Next;
+ PairBuffer[PairBuffer[index].Next].Prev = PosHead;
+ } else {
+ PairBuffer[PairBuffer[index].Prev].Next = PairBuffer[index].Next;
+ PairBuffer[PairBuffer[index].Next].Prev = PairBuffer[index].Prev;
+ }
+ }
+
+ if (PairLists[count+1] != PosEnd){
+ PairBuffer[PairLists[count+1]].Prev = index;
+ PairBuffer[index].Next = PairLists[count+1];
+ PairBuffer[index].Prev = PosHead;
+ PairLists[count+1] = index;
+ }else{
+ PairLists[count+1] = index;
+ PairBuffer[index].Next = PosEnd;
+ PairBuffer[index].Prev = PosHead;
+ }
+
+ PairPos[PairPosNext].Pos = pos;
+ PairPos[PairPosNext].Next = PairBuffer[index].Pos;
+ PairBuffer[index].Pos = PairPosNext;
+ }
+ PairPosNext ++;
+
+ myassert(PairPosNext < MaxBlockSize*3);
+ PairCount[pair].Count ++;
+ if (PairCount[pair].Count > PairListHigh)
+ PairListHigh = PairCount[pair].Count;
+ }
+ inline void RemovePair(const TUint16 pair, const TUint16 pos){
+ //ClockRemove1 = clock();
+ TUint16 count = PairCount[pair].Count;
+ TUint16 index = PairCount[pair].Index;
+ if (count == 1 ) {
+ PairCount[pair].Count = 0;
+ PairCount[pair].Index = PosEnd;
+ return;
+ }
+
+ myassert(index != PosEnd);
+ TUint16 *posnextp = &PairBuffer[index].Pos;
+ while (*posnextp != PosEnd){
+ if (PairPos[*posnextp].Pos == pos)
+ break;
+ posnextp = &PairPos[*posnextp].Next;
+ }
+ myassert(*posnextp != PosEnd);
+ *posnextp = PairPos[*posnextp].Next;
+
+ if (PairBuffer[index].Next == PosEnd){
+ if (PairBuffer[index].Prev == PosHead){
+ PairLists[count] = PosEnd;
+ } else {
+ PairBuffer[PairBuffer[index].Prev].Next = PosEnd;
+ }
+ } else {
+ if (PairBuffer[index].Prev == PosHead){
+ PairLists[count] = PairBuffer[index].Next;
+ PairBuffer[PairBuffer[index].Next].Prev = PosHead;
+ } else {
+ PairBuffer[PairBuffer[index].Prev].Next = PairBuffer[index].Next;
+ PairBuffer[PairBuffer[index].Next].Prev = PairBuffer[index].Prev;
+ }
+ }
+ myassert(PairCount[pair].Count > 0);
+ PairCount[pair].Count --;
+ if (PairCount[pair].Count == 0)
+ PairCount[pair].Index = PosEnd;
+
+ count = PairCount[pair].Count;
+ if (count > 0) {
+ if (PairLists[count] != PosEnd){
+ PairBuffer[PairLists[count]].Prev = index;
+ PairBuffer[index].Next = PairLists[count];
+ PairBuffer[index].Prev = PosHead;
+ PairLists[count] = index;
+ }else{
+ PairLists[count] = index;
+ PairBuffer[index].Next = PosEnd;
+ PairBuffer[index].Prev = PosHead;
+ }
+ }
+ while (PairLists[PairListHigh] == PosEnd) {
+ PairListHigh --;
+ }
+ }
+ inline void GetPairBackward (TUint8 *data, TUint16 pos, TUint16 &pairpos, TUint16 &pair) {
+ myassert(pos <MaxBlockSize);
+ myassert(Mask[pos] != ByteMarked);
+ myassert(Mask[pos] != ByteRemoved);
+ TUint8 b = data[pos];
+ if (pos == 0) {
+ pair = 0;
+ pairpos = PosEnd;
+ return;
+ }
+ pos --;
+ while ((pos>0) && (Mask[pos] == ByteRemoved)){
+ pos --;
+ }
+ if ((Mask[pos] == ByteRemoved) || (Mask[pos] == ByteMarked)) {
+ pair = 0;
+ pairpos = PosEnd;
+ } else {
+ pair = (TUint16)((b << 8) | data[pos]);
+ pairpos = pos;
+ }
+ }
+
+ inline void GetPairForward (TUint8 *data, TUint16 pos, TInt size, TUint16 &pairpos, TUint16 &pair) {
+ myassert(Mask[pos] != ByteMarked);
+ myassert(Mask[pos] != ByteRemoved);
+ myassert(pos < size);
+ TUint8 b = data[pos];
+ pairpos = pos;
+ pos ++;
+ while ((pos < size) && (Mask[pos] == ByteRemoved))
+ pos++;
+ if ((pos == size) || (Mask[pos] == ByteMarked)) {
+ pair = 0;
+ pairpos = PosEnd;
+ } else {
+ pair = (TUint16)(b | (data[pos] << 8));
+ }
+ }
+#ifdef __TOOLS2__
+ void DumpList(TUint8 *data, TInt size) {
+ int i, j;
+ cout << "src: " << dec << size << " bytes"<< endl;
+ for (i=0;i<size;i+=16){
+ cout << endl;
+ cout << hex;
+ cout << setfill('0') << setw(4) << right << i << " ";
+ for (j=0;j<16;j++) {
+ cout << setfill ('0') << setw(2) << right << (unsigned int)data[i+j] << " ";
+ }
+ cout << " ";
+ for (j=0;j<16;j++) {
+ char c = isgraph(data[i+j]) ? data[i+j]:'.';
+ cout << c;
+ }
+ }
+ cout << endl;
+
+ for (i=0;i<256;i+=16){
+ cout << endl << hex << setfill('0') << setw(2) <<right <<i << " ";
+ for (j=0;j<16;j++) {
+ cout << setfill ('0') << setw(4) << right << (unsigned int)ByteIndex[i+j] << " ";
+ }
+ }
+ cout << endl;
+ for (i=0;i<256;i++){
+ cout << "Byte: <" << i << "> Count: " << ByteCount[i];
+ TUint16 pos = ByteIndex[i];
+ int j = 0;
+ while (pos != PosEnd){
+ if (j++ % 16 == 0)
+ cout << endl << " ";
+ cout << hex << setw(4) << setfill('0') << pos << " ";
+ pos = BytePos[pos];
+ }
+ cout << endl;
+ }
+ cout << "buffer lists" << endl;
+ for (i=PairListHigh; i>=0; i--){
+ TUint16 index = PairLists[i];
+ if (index == PosEnd)
+ continue;
+ cout << dec;
+ cout << "List " << i << endl;
+ while (index != PosEnd){
+ char b0 = (char)PairBuffer[index].Pair;
+ char b1 = (char)(PairBuffer[index].Pair >> 8);
+ cout << " " << setw(4) << setfill('0') << hex << PairBuffer[index].Pair << " " << "<" << (isgraph(b1)? b1:'.') << (isgraph(b0) ? b0 : '.') << ">";
+ TUint16 pos;
+ pos = PairBuffer[index].Pos;
+ int k = 0;
+ while (pos != PosEnd){
+ if (k%16 ==0) {
+ cout << endl << " ";
+ };
+ cout << setw(4) << setfill('0') << PairPos[pos].Pos << " ";
+ k ++;
+ pos = PairPos[pos].Next;
+ }
+ cout << endl;
+ index = PairBuffer[index].Next;
+ }
+
+ }
+ }
+#endif
+ public:
+ CBytePair(TBool fastCompress) {
+ iFastCompress = fastCompress;
+ }
+ TInt Compress(TUint8* dst, TUint8* src, TInt size);
+ TInt Decompress(TUint8* dst, TInt dstSize, TUint8* src, TInt srcSize, TUint8*& srcNext);
+};
+TInt BytePairCompress(TUint8* dst, TUint8* src, TInt size, CBytePair *aBPE);
+
+#endif
+