Mercurial > vba-linux

     1 // Mtf8.h

     2 

     3 #ifndef __COMPRESS_MTF8_H

     4 #define __COMPRESS_MTF8_H

     5 

     6 #include "../../Common/Types.h"

     7 

     8 namespace NCompress {

     9 

    10 struct CMtf8Encoder

    11 {

    12   Byte Buf[256];

    13 

    14   int FindAndMove(Byte v)

    15   {

    16     int pos;

    17     for (pos = 0; Buf[pos] != v; pos++);

    18     int resPos = pos;

    19     for (; pos >= 8; pos -= 8)

    20     {

    21       Buf[pos] = Buf[pos - 1];

    22       Buf[pos - 1] = Buf[pos - 2];

    23       Buf[pos - 2] = Buf[pos - 3];

    24       Buf[pos - 3] = Buf[pos - 4];

    25       Buf[pos - 4] = Buf[pos - 5];

    26       Buf[pos - 5] = Buf[pos - 6];

    27       Buf[pos - 6] = Buf[pos - 7];

    28       Buf[pos - 7] = Buf[pos - 8];

    29     }

    30     for (; pos > 0; pos--)

    31       Buf[pos] = Buf[pos - 1];

    32     Buf[0] = v;

    33     return resPos;

    34   }

    35 };

    36 

    37 /*

    38 struct CMtf8Decoder

    39 {

    40   Byte Buf[256];

    41 

    42   void Init(int) {};

    43   Byte GetHead() const { return Buf[0]; }

    44   Byte GetAndMove(int pos)

    45   {

    46     Byte res = Buf[pos];

    47     for (; pos >= 8; pos -= 8)

    48     {

    49       Buf[pos] = Buf[pos - 1];

    50       Buf[pos - 1] = Buf[pos - 2];

    51       Buf[pos - 2] = Buf[pos - 3];

    52       Buf[pos - 3] = Buf[pos - 4];

    53       Buf[pos - 4] = Buf[pos - 5];

    54       Buf[pos - 5] = Buf[pos - 6];

    55       Buf[pos - 6] = Buf[pos - 7];

    56       Buf[pos - 7] = Buf[pos - 8];

    57     }

    58     for (; pos > 0; pos--)

    59       Buf[pos] = Buf[pos - 1];

    60     Buf[0] = res;

    61     return res;

    62   }

    63 };

    64 */

    65 

    66 #ifdef _WIN64

    67 #define MODE_64BIT

    68 #endif

    69 

    70 #ifdef MODE_64BIT

    71 typedef UInt64 CMtfVar;

    72 #define MTF_MOVS 3

    73 #else

    74 typedef UInt32 CMtfVar;

    75 #define MTF_MOVS 2

    76 #endif

    77 

    78 #define MTF_MASK ((1 << MTF_MOVS) - 1)

    79 

    80 

    81 struct CMtf8Decoder

    82 {

    83   CMtfVar Buf[256 >> MTF_MOVS];

    84 

    85   void StartInit() { memset(Buf, 0, sizeof(Buf)); }

    86   void Add(unsigned int pos, Byte val) { Buf[pos >> MTF_MOVS] |= ((CMtfVar)val << ((pos & MTF_MASK) << 3));  }

    87   Byte GetHead() const { return (Byte)Buf[0]; }

    88   Byte GetAndMove(unsigned int pos)

    89   {

    90     UInt32 lim = ((UInt32)pos >> MTF_MOVS);

    91     pos = (pos & MTF_MASK) << 3;

    92     CMtfVar prev = (Buf[lim] >> pos) & 0xFF;

    93 

    94     UInt32 i = 0;

    95     if ((lim & 1) != 0)

    96     {

    97       CMtfVar next = Buf[0];

    98       Buf[0] = (next << 8) | prev;

    99       prev = (next >> (MTF_MASK << 3));

   100       i = 1;

   101       lim -= 1;

   102     }

   103     for (; i < lim; i += 2)

   104     {

   105       CMtfVar next = Buf[i];

   106       Buf[i] = (next << 8) | prev;

   107       prev = (next >> (MTF_MASK << 3));

   108       next = Buf[i + 1];

   109       Buf[i + 1] = (next << 8) | prev;

   110       prev = (next >> (MTF_MASK << 3));

   111     }

   112     CMtfVar next = Buf[i];

   113     CMtfVar mask = (((CMtfVar)0x100 << pos) - 1);

   114     Buf[i] = (next & ~mask) | (((next << 8) | prev) & mask);

   115     return (Byte)Buf[0];

   116   }

   117 };

   118 

   119 /*

   120 const int kSmallSize = 64;

   121 class CMtf8Decoder

   122 {

   123   Byte SmallBuffer[kSmallSize];

   124   int SmallSize;

   125   Byte Counts[16];

   126   int Size;

   127 public:

   128   Byte Buf[256];

   129 

   130   Byte GetHead() const

   131   {

   132     if (SmallSize > 0)

   133       return SmallBuffer[kSmallSize - SmallSize];

   134     return Buf[0];

   135   }

   136 

   137   void Init(int size)

   138   {

   139     Size = size;

   140     SmallSize = 0;

   141     for (int i = 0; i < 16; i++)

   142     {

   143       Counts[i] = ((size >= 16) ? 16 : size);

   144       size -= Counts[i];

   145     }

   146   }

   147 

   148   Byte GetAndMove(int pos)

   149   {

   150     if (pos < SmallSize)

   151     {

   152       Byte *p = SmallBuffer + kSmallSize - SmallSize;

   153       Byte res = p[pos];

   154       for (; pos > 0; pos--)

   155         p[pos] = p[pos - 1];

   156       SmallBuffer[kSmallSize - SmallSize] = res;

   157       return res;

   158     }

   159     if (SmallSize == kSmallSize)

   160     {

   161       int i = Size - 1;

   162       int g = 16;

   163       do

   164       {

   165         g--;

   166         int offset = (g << 4);

   167         for (int t = Counts[g] - 1; t >= 0; t--, i--)

   168           Buf[i] = Buf[offset + t];

   169       }

   170       while(g != 0);

   171       

   172       for (i = kSmallSize - 1; i >= 0; i--)

   173         Buf[i] = SmallBuffer[i];

   174       Init(Size);

   175     }

   176     pos -= SmallSize;

   177     int g;

   178     for (g = 0; pos >= Counts[g]; g++)

   179       pos -= Counts[g];

   180     int offset = (g << 4);

   181     Byte res = Buf[offset + pos];

   182     for (pos; pos < 16 - 1; pos++)

   183       Buf[offset + pos] = Buf[offset + pos + 1];

   184     

   185     SmallSize++;

   186     SmallBuffer[kSmallSize - SmallSize] = res;

   187 

   188     Counts[g]--;

   189     return res;

   190   }

   191 };

   192 */

   193 

   194 }

   195 

   196 #endif
author	Robert McIntyre <rlm@mit.edu>
date	Sat, 03 Mar 2012 10:31:27 -0600
parents
children