1 /*

     2 * Copyright (c) 2005-2009 Nokia Corporation and/or its subsidiary(-ies).

     3 * All rights reserved.

     4 * This component and the accompanying materials are made available

     5 * under the terms of the License "Eclipse Public License v1.0"

     6 * which accompanies this distribution, and is available

     7 * at the URL "http://www.eclipse.org/legal/epl-v10.html".

     8 *

     9 * Initial Contributors:

    10 * Nokia Corporation - initial contribution.

    11 *

    12 * Contributors:

    13 *

    14 * Description: 

    15 *

    16 */

    17 

    18 #ifndef BYTE_PAIR_H

    19 #define BYTE_PAIR_H

    20 

    21 #ifdef __VC32__

    22  #ifdef __MSVCDOTNET__

    23   #include <strstream>

    24   #include <iomanip>

    25  #else //!__MSVCDOTNET__

    26   #include <strstrea.h>

    27   #include <iomanip.h>

    28  #endif //__MSVCDOTNET__

    29 #else // !__VC32__

    30 #ifdef __TOOLS2__ 

    31 #include <sstream>

    32 #include <iomanip>

    33 #include <iostream>

    34 using namespace std;

    35 #else

    36  #include <strstream.h>

    37  #include <iomanip.h>

    38  #endif

    39 #endif // __VC32__

    40 

    41 //#include <myassert.h>

    42 //#define DEBUG_ASSERT

    43 #ifdef DEBUG_ASSERT

    44 void myassert(int c);

    45 #else

    46 #define myassert(c) 

    47 #endif

    48 

    49 #include <e32cmn.h> 

    50 typedef struct {

    51     TUint16 Count;

    52     TUint16 Index; 

    53 } TPairCountIndex;

    54 

    55 typedef struct {

    56     TUint16 Pair;

    57     TUint16 Next;

    58     TUint16 Prev;

    59     TUint16 Pos;

    60 } TPair;

    61 typedef struct {

    62     TUint16 Pos;

    63     TUint16 Next;

    64 } TPos;

    65 

    66 const TInt MaxBlockSize = 0x1000;

    67 

    68 const TUint16 PosEnd = 0xffff;

    69 const TUint16 PosHead = 0xfffe;

    70 const TUint8 ByteRemoved = 'R';

    71 const TUint8 ByteMarked = 'M';

    72 const TUint8 ByteHead = 'H';

    73 const TUint8 ByteTail = 'T';

    74 const TUint8 ByteNew = 'N';

    75 class CBytePair {

    76     private:

    77         TBool   iFastCompress;

    78         TInt    marker;

    79         TUint8  Mask[MaxBlockSize];

    80         TUint16 ByteCount[0x100];

    81         TUint16 ByteIndex[0x100];

    82         TUint16 BytePos[MaxBlockSize];

    83         TPairCountIndex PairCount[0x10000];

    84         TPair   PairBuffer[MaxBlockSize*2];

    85         TInt    PairBufferNext;

    86         TPos    PairPos[MaxBlockSize*3];

    87         TUint16 PairPosNext;

    88         TUint16 PairLists[MaxBlockSize/2+2];

    89         TInt    PairListHigh;

    90 

    91         void CountBytes(TUint8* data, TInt size) {

    92             TUint32 *p;

    93             p = (TUint32*)ByteCount;

    94             while (p < (TUint32*)ByteCount + sizeof(ByteCount)/4) {

    95                 *p++ = 0;

    96             }

    97             p = (TUint32*)ByteIndex;

    98             while (p < (TUint32*)ByteIndex + sizeof(ByteIndex)/4) {

    99                 *p++ = 0xffffffff;

   100             }

   101             p = (TUint32*)BytePos;

   102             while (p< (TUint32*)BytePos + sizeof(BytePos)/4) {

   103                 *p++ = 0xffffffff;

   104             }

   105             TUint8* dataEnd = data+size;

   106             int pos = 0;

   107             while(data<dataEnd) {

   108                 BytePos[pos] = ByteIndex[*data];

   109                 ByteIndex[*data] = (TUint16)pos;

   110                 pos ++;

   111                 ++ByteCount[*data++];

   112             }

   113         }

   114         inline void ByteUsed(TInt b) {

   115             ByteCount[b] = 0xffff;

   116         }

   117         int TieBreak(int b1,int b2) {

   118             return -ByteCount[b1]-ByteCount[b2];

   119         }

   120 

   121         void Initialize(TUint8* data, TInt size);

   122         TInt MostCommonPair(TInt& pair);

   123         TInt LeastCommonByte(TInt& byte);

   124         inline void InsertPair(const TUint16 pair, const TUint16 pos) {

   125             //ClockInsert1 = clock();

   126             //cout << "Pair:" << hex << setw(4) << setfill ('0') << pair << endl;

   127             TUint16 count = PairCount[pair].Count;

   128             if (0==count) {

   129                 PairCount[pair].Index = (TUint16)PairBufferNext;

   130                 if (PairLists[1] != PosEnd) {

   131                     PairBuffer[PairLists[1]].Prev = (TUint16)PairBufferNext;

   132                 }

   133                 PairBuffer[PairBufferNext].Next = PairLists[1];

   134                 PairBuffer[PairBufferNext].Prev = PosHead;

   135                 PairLists[1] = (TUint16)PairBufferNext;

   136                 PairBuffer[PairBufferNext].Pair = pair;

   137                 PairBuffer[PairBufferNext].Pos = PairPosNext;

   138                 PairBufferNext ++;

   139                 myassert(PairBufferNext < MaxBlockSize*2);

   140                 PairPos[PairPosNext].Pos = pos; 

   141                 PairPos[PairPosNext].Next = PosEnd;

   142             } else {

   143                 TUint16 index = PairCount[pair].Index;

   144                

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

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

   147                         PairLists[count] = PosEnd;

   148                     } else {

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

   150                     }

   151                 } else {

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

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

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

   155                     } else {

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

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

   158                     }

   159                 }

   160                 

   161                 if (PairLists[count+1] != PosEnd){

   162                     PairBuffer[PairLists[count+1]].Prev = index;

   163                     PairBuffer[index].Next = PairLists[count+1];

   164                     PairBuffer[index].Prev = PosHead;

   165                     PairLists[count+1] = index;

   166                 }else{

   167                     PairLists[count+1] = index;

   168                     PairBuffer[index].Next = PosEnd;

   169                     PairBuffer[index].Prev = PosHead;

   170                 }

   171 

   172                 PairPos[PairPosNext].Pos = pos;

   173                 PairPos[PairPosNext].Next = PairBuffer[index].Pos;

   174                 PairBuffer[index].Pos = PairPosNext;

   175             }

   176             PairPosNext ++;

   177             

   178             myassert(PairPosNext < MaxBlockSize*3);

   179             PairCount[pair].Count ++;

   180             if (PairCount[pair].Count > PairListHigh) 

   181                 PairListHigh = PairCount[pair].Count; 

   182         }

   183         inline void RemovePair(const TUint16 pair, const TUint16 pos){

   184             //ClockRemove1 = clock();

   185             TUint16 count = PairCount[pair].Count;

   186             TUint16 index = PairCount[pair].Index;

   187             if (count == 1 ) {

   188                 PairCount[pair].Count = 0;

   189                 PairCount[pair].Index = PosEnd;

   190                 return;

   191             }

   192             

   193             myassert(index != PosEnd);

   194             TUint16 *posnextp = &PairBuffer[index].Pos;

   195             while (*posnextp != PosEnd){

   196                 if (PairPos[*posnextp].Pos == pos)

   197                     break;

   198                 posnextp = &PairPos[*posnextp].Next;

   199             }

   200             myassert(*posnextp != PosEnd);

   201             *posnextp = PairPos[*posnextp].Next;

   202             

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

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

   205                     PairLists[count] = PosEnd;

   206                 } else {

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

   208                 }

   209             } else {

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

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

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

   213                 } else {

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

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

   216                 }

   217             }

   218             myassert(PairCount[pair].Count > 0);

   219             PairCount[pair].Count --;

   220             if (PairCount[pair].Count == 0)

   221                 PairCount[pair].Index = PosEnd;

   222             

   223             count = PairCount[pair].Count;

   224             if (count > 0) {

   225                 if (PairLists[count] != PosEnd){

   226                     PairBuffer[PairLists[count]].Prev = index;

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

   228                     PairBuffer[index].Prev = PosHead;

   229                     PairLists[count] = index;

   230                 }else{

   231                     PairLists[count] = index;

   232                     PairBuffer[index].Next = PosEnd;

   233                     PairBuffer[index].Prev = PosHead;

   234                 }

   235             }            

   236             while (PairLists[PairListHigh] == PosEnd) {

   237                 PairListHigh --;

   238             }             

   239         }

   240         inline void GetPairBackward (TUint8 *data, TUint16 pos, TUint16 &pairpos, TUint16 &pair) {

   241             myassert(pos <MaxBlockSize);

   242             myassert(Mask[pos] != ByteMarked);

   243             myassert(Mask[pos] != ByteRemoved);

   244             TUint8 b = data[pos];

   245             if (pos == 0) {

   246                 pair = 0;

   247                 pairpos = PosEnd;

   248                 return;

   249             }

   250             pos --;

   251             while ((pos>0) && (Mask[pos] == ByteRemoved)){

   252                 pos --;

   253             }

   254             if ((Mask[pos] == ByteRemoved) || (Mask[pos] == ByteMarked)) {

   255                 pair = 0;

   256                 pairpos = PosEnd;

   257             } else {

   258                 pair = (TUint16)((b << 8) | data[pos]);

   259                 pairpos = pos;

   260             }

   261         }

   262         

   263         inline void GetPairForward (TUint8 *data, TUint16 pos, TInt size, TUint16 &pairpos, TUint16 &pair) {

   264             myassert(Mask[pos] != ByteMarked);

   265             myassert(Mask[pos] != ByteRemoved);

   266             myassert(pos < size);

   267             TUint8 b = data[pos];

   268             pairpos = pos;

   269             pos ++;

   270             while ((pos < size) && (Mask[pos] == ByteRemoved))

   271                 pos++;

   272             if ((pos == size) || (Mask[pos] == ByteMarked)) {

   273                 pair = 0;

   274                 pairpos = PosEnd;

   275             } else {

   276                 pair = (TUint16)(b | (data[pos] << 8));

   277             }

   278         }

   279 #ifdef  __TOOLS2__        

   280         void DumpList(TUint8 *data, TInt size) {

   281             int i, j;

   282             cout << "src: " << dec << size << " bytes"<< endl;

   283             for (i=0;i<size;i+=16){

   284                 cout << endl;

   285                 cout << hex;

   286                 cout << setfill('0') << setw(4) << right << i << " ";

   287                 for (j=0;j<16;j++) {

   288                     cout << setfill ('0') << setw(2) << right << (unsigned int)data[i+j] << " ";

   289                 }

   290                 cout << "    ";

   291                 for (j=0;j<16;j++) {

   292                     char c = isgraph(data[i+j]) ? data[i+j]:'.';

   293                     cout << c;

   294                 }

   295             }

   296             cout << endl;

   297             

   298             for (i=0;i<256;i+=16){

   299                 cout << endl << hex << setfill('0') << setw(2) <<right <<i << " ";

   300                 for (j=0;j<16;j++) {

   301                     cout << setfill ('0') << setw(4) << right << (unsigned int)ByteIndex[i+j] << " ";

   302                 }

   303             }

   304             cout << endl;

   305             for (i=0;i<256;i++){

   306                 cout << "Byte: <" << i << "> Count: " << ByteCount[i];

   307                 TUint16 pos = ByteIndex[i];

   308                 int j = 0;

   309                 while (pos != PosEnd){

   310                     if (j++ % 16 == 0)

   311                         cout << endl << "    ";

   312                     cout << hex << setw(4) << setfill('0') << pos << " ";

   313                     pos = BytePos[pos];

   314                 }

   315                 cout << endl;

   316             }

   317             cout << "buffer lists" << endl;

   318             for (i=PairListHigh; i>=0; i--){

   319                 TUint16 index = PairLists[i];

   320                 if (index == PosEnd)

   321                     continue;

   322                 cout << dec;

   323                 cout << "List " << i << endl;

   324                 while (index != PosEnd){ 

   325                     char b0 = (char)PairBuffer[index].Pair;

   326                     char b1 = (char)(PairBuffer[index].Pair >> 8);

   327                     cout << "    " << setw(4) << setfill('0') << hex << PairBuffer[index].Pair << " " << "<" << (isgraph(b1)? b1:'.') << (isgraph(b0) ? b0 : '.') << ">";  

   328                     TUint16 pos;

   329                     pos = PairBuffer[index].Pos;

   330                     int k = 0;

   331                     while (pos != PosEnd){

   332                         if (k%16 ==0) {

   333                             cout << endl << "        ";

   334                         };

   335                         cout << setw(4) << setfill('0') << PairPos[pos].Pos << " ";

   336                         k ++;

   337                         pos = PairPos[pos].Next;

   338                     }

   339                     cout << endl;

   340                     index = PairBuffer[index].Next;

   341                 }

   342                 

   343             }

   344         }

   345 #endif

   346 	public:

   347         CBytePair(TBool fastCompress) {

   348             iFastCompress = fastCompress; 

   349         }

   350         TInt Compress(TUint8* dst, TUint8* src, TInt size);

   351         TInt Decompress(TUint8* dst, TInt dstSize, TUint8* src, TInt srcSize, TUint8*& srcNext);

   352 };

   353 TInt BytePairCompress(TUint8* dst, TUint8* src, TInt size, CBytePair *aBPE);

   354 

   355 #endif

   356