rlm@1: // Mtf8.h
rlm@1: 
rlm@1: #ifndef __COMPRESS_MTF8_H
rlm@1: #define __COMPRESS_MTF8_H
rlm@1: 
rlm@1: #include "../../Common/Types.h"
rlm@1: 
rlm@1: namespace NCompress {
rlm@1: 
rlm@1: struct CMtf8Encoder
rlm@1: {
rlm@1:   Byte Buf[256];
rlm@1: 
rlm@1:   int FindAndMove(Byte v)
rlm@1:   {
rlm@1:     int pos;
rlm@1:     for (pos = 0; Buf[pos] != v; pos++);
rlm@1:     int resPos = pos;
rlm@1:     for (; pos >= 8; pos -= 8)
rlm@1:     {
rlm@1:       Buf[pos] = Buf[pos - 1];
rlm@1:       Buf[pos - 1] = Buf[pos - 2];
rlm@1:       Buf[pos - 2] = Buf[pos - 3];
rlm@1:       Buf[pos - 3] = Buf[pos - 4];
rlm@1:       Buf[pos - 4] = Buf[pos - 5];
rlm@1:       Buf[pos - 5] = Buf[pos - 6];
rlm@1:       Buf[pos - 6] = Buf[pos - 7];
rlm@1:       Buf[pos - 7] = Buf[pos - 8];
rlm@1:     }
rlm@1:     for (; pos > 0; pos--)
rlm@1:       Buf[pos] = Buf[pos - 1];
rlm@1:     Buf[0] = v;
rlm@1:     return resPos;
rlm@1:   }
rlm@1: };
rlm@1: 
rlm@1: /*
rlm@1: struct CMtf8Decoder
rlm@1: {
rlm@1:   Byte Buf[256];
rlm@1: 
rlm@1:   void Init(int) {};
rlm@1:   Byte GetHead() const { return Buf[0]; }
rlm@1:   Byte GetAndMove(int pos)
rlm@1:   {
rlm@1:     Byte res = Buf[pos];
rlm@1:     for (; pos >= 8; pos -= 8)
rlm@1:     {
rlm@1:       Buf[pos] = Buf[pos - 1];
rlm@1:       Buf[pos - 1] = Buf[pos - 2];
rlm@1:       Buf[pos - 2] = Buf[pos - 3];
rlm@1:       Buf[pos - 3] = Buf[pos - 4];
rlm@1:       Buf[pos - 4] = Buf[pos - 5];
rlm@1:       Buf[pos - 5] = Buf[pos - 6];
rlm@1:       Buf[pos - 6] = Buf[pos - 7];
rlm@1:       Buf[pos - 7] = Buf[pos - 8];
rlm@1:     }
rlm@1:     for (; pos > 0; pos--)
rlm@1:       Buf[pos] = Buf[pos - 1];
rlm@1:     Buf[0] = res;
rlm@1:     return res;
rlm@1:   }
rlm@1: };
rlm@1: */
rlm@1: 
rlm@1: #ifdef _WIN64
rlm@1: #define MODE_64BIT
rlm@1: #endif
rlm@1: 
rlm@1: #ifdef MODE_64BIT
rlm@1: typedef UInt64 CMtfVar;
rlm@1: #define MTF_MOVS 3
rlm@1: #else
rlm@1: typedef UInt32 CMtfVar;
rlm@1: #define MTF_MOVS 2
rlm@1: #endif
rlm@1: 
rlm@1: #define MTF_MASK ((1 << MTF_MOVS) - 1)
rlm@1: 
rlm@1: 
rlm@1: struct CMtf8Decoder
rlm@1: {
rlm@1:   CMtfVar Buf[256 >> MTF_MOVS];
rlm@1: 
rlm@1:   void StartInit() { memset(Buf, 0, sizeof(Buf)); }
rlm@1:   void Add(unsigned int pos, Byte val) { Buf[pos >> MTF_MOVS] |= ((CMtfVar)val << ((pos & MTF_MASK) << 3));  }
rlm@1:   Byte GetHead() const { return (Byte)Buf[0]; }
rlm@1:   Byte GetAndMove(unsigned int pos)
rlm@1:   {
rlm@1:     UInt32 lim = ((UInt32)pos >> MTF_MOVS);
rlm@1:     pos = (pos & MTF_MASK) << 3;
rlm@1:     CMtfVar prev = (Buf[lim] >> pos) & 0xFF;
rlm@1: 
rlm@1:     UInt32 i = 0;
rlm@1:     if ((lim & 1) != 0)
rlm@1:     {
rlm@1:       CMtfVar next = Buf[0];
rlm@1:       Buf[0] = (next << 8) | prev;
rlm@1:       prev = (next >> (MTF_MASK << 3));
rlm@1:       i = 1;
rlm@1:       lim -= 1;
rlm@1:     }
rlm@1:     for (; i < lim; i += 2)
rlm@1:     {
rlm@1:       CMtfVar next = Buf[i];
rlm@1:       Buf[i] = (next << 8) | prev;
rlm@1:       prev = (next >> (MTF_MASK << 3));
rlm@1:       next = Buf[i + 1];
rlm@1:       Buf[i + 1] = (next << 8) | prev;
rlm@1:       prev = (next >> (MTF_MASK << 3));
rlm@1:     }
rlm@1:     CMtfVar next = Buf[i];
rlm@1:     CMtfVar mask = (((CMtfVar)0x100 << pos) - 1);
rlm@1:     Buf[i] = (next & ~mask) | (((next << 8) | prev) & mask);
rlm@1:     return (Byte)Buf[0];
rlm@1:   }
rlm@1: };
rlm@1: 
rlm@1: /*
rlm@1: const int kSmallSize = 64;
rlm@1: class CMtf8Decoder
rlm@1: {
rlm@1:   Byte SmallBuffer[kSmallSize];
rlm@1:   int SmallSize;
rlm@1:   Byte Counts[16];
rlm@1:   int Size;
rlm@1: public:
rlm@1:   Byte Buf[256];
rlm@1: 
rlm@1:   Byte GetHead() const
rlm@1:   {
rlm@1:     if (SmallSize > 0)
rlm@1:       return SmallBuffer[kSmallSize - SmallSize];
rlm@1:     return Buf[0];
rlm@1:   }
rlm@1: 
rlm@1:   void Init(int size)
rlm@1:   {
rlm@1:     Size = size;
rlm@1:     SmallSize = 0;
rlm@1:     for (int i = 0; i < 16; i++)
rlm@1:     {
rlm@1:       Counts[i] = ((size >= 16) ? 16 : size);
rlm@1:       size -= Counts[i];
rlm@1:     }
rlm@1:   }
rlm@1: 
rlm@1:   Byte GetAndMove(int pos)
rlm@1:   {
rlm@1:     if (pos < SmallSize)
rlm@1:     {
rlm@1:       Byte *p = SmallBuffer + kSmallSize - SmallSize;
rlm@1:       Byte res = p[pos];
rlm@1:       for (; pos > 0; pos--)
rlm@1:         p[pos] = p[pos - 1];
rlm@1:       SmallBuffer[kSmallSize - SmallSize] = res;
rlm@1:       return res;
rlm@1:     }
rlm@1:     if (SmallSize == kSmallSize)
rlm@1:     {
rlm@1:       int i = Size - 1;
rlm@1:       int g = 16;
rlm@1:       do
rlm@1:       {
rlm@1:         g--;
rlm@1:         int offset = (g << 4);
rlm@1:         for (int t = Counts[g] - 1; t >= 0; t--, i--)
rlm@1:           Buf[i] = Buf[offset + t];
rlm@1:       }
rlm@1:       while(g != 0);
rlm@1:       
rlm@1:       for (i = kSmallSize - 1; i >= 0; i--)
rlm@1:         Buf[i] = SmallBuffer[i];
rlm@1:       Init(Size);
rlm@1:     }
rlm@1:     pos -= SmallSize;
rlm@1:     int g;
rlm@1:     for (g = 0; pos >= Counts[g]; g++)
rlm@1:       pos -= Counts[g];
rlm@1:     int offset = (g << 4);
rlm@1:     Byte res = Buf[offset + pos];
rlm@1:     for (pos; pos < 16 - 1; pos++)
rlm@1:       Buf[offset + pos] = Buf[offset + pos + 1];
rlm@1:     
rlm@1:     SmallSize++;
rlm@1:     SmallBuffer[kSmallSize - SmallSize] = res;
rlm@1: 
rlm@1:     Counts[g]--;
rlm@1:     return res;
rlm@1:   }
rlm@1: };
rlm@1: */
rlm@1: 
rlm@1: }
rlm@1: 
rlm@1: #endif