CPP/7zip/Compress/Mtf8.h

   1 // Mtf8.h\r
   2 \r
   3 #ifndef __COMPRESS_MTF8_H\r
   4 #define __COMPRESS_MTF8_H\r
   5 \r
   6 #include "../../../C/CpuArch.h"\r
   7 \r
   8 #include "../../Common/Types.h"\r
   9 \r
  10 namespace NCompress {\r
  11 \r
  12 struct CMtf8Encoder\r
  13 {\r
  14   Byte Buf[256];\r
  15 \r
  16   int FindAndMove(Byte v)\r
  17   {\r
  18     int pos;\r
  19     for (pos = 0; Buf[pos] != v; pos++);\r
  20     int resPos = pos;\r
  21     for (; pos >= 8; pos -= 8)\r
  22     {\r
  23       Buf[pos] = Buf[pos - 1];\r
  24       Buf[pos - 1] = Buf[pos - 2];\r
  25       Buf[pos - 2] = Buf[pos - 3];\r
  26       Buf[pos - 3] = Buf[pos - 4];\r
  27       Buf[pos - 4] = Buf[pos - 5];\r
  28       Buf[pos - 5] = Buf[pos - 6];\r
  29       Buf[pos - 6] = Buf[pos - 7];\r
  30       Buf[pos - 7] = Buf[pos - 8];\r
  31     }\r
  32     for (; pos > 0; pos--)\r
  33       Buf[pos] = Buf[pos - 1];\r
  34     Buf[0] = v;\r
  35     return resPos;\r
  36   }\r
  37 };\r
  38 \r
  39 /*\r
  40 struct CMtf8Decoder\r
  41 {\r
  42   Byte Buf[256];\r
  43 \r
  44   void Init(int) {};\r
  45   Byte GetHead() const { return Buf[0]; }\r
  46   Byte GetAndMove(int pos)\r
  47   {\r
  48     Byte res = Buf[pos];\r
  49     for (; pos >= 8; pos -= 8)\r
  50     {\r
  51       Buf[pos] = Buf[pos - 1];\r
  52       Buf[pos - 1] = Buf[pos - 2];\r
  53       Buf[pos - 2] = Buf[pos - 3];\r
  54       Buf[pos - 3] = Buf[pos - 4];\r
  55       Buf[pos - 4] = Buf[pos - 5];\r
  56       Buf[pos - 5] = Buf[pos - 6];\r
  57       Buf[pos - 6] = Buf[pos - 7];\r
  58       Buf[pos - 7] = Buf[pos - 8];\r
  59     }\r
  60     for (; pos > 0; pos--)\r
  61       Buf[pos] = Buf[pos - 1];\r
  62     Buf[0] = res;\r
  63     return res;\r
  64   }\r
  65 };\r
  66 */\r
  67 \r
  68 #ifdef MY_CPU_64BIT\r
  69 typedef UInt64 CMtfVar;\r
  70 #define MTF_MOVS 3\r
  71 #else\r
  72 typedef UInt32 CMtfVar;\r
  73 #define MTF_MOVS 2\r
  74 #endif\r
  75 \r
  76 #define MTF_MASK ((1 << MTF_MOVS) - 1)\r
  77 \r
  78 \r
  79 struct CMtf8Decoder\r
  80 {\r
  81   CMtfVar Buf[256 >> MTF_MOVS];\r
  82 \r
  83   void StartInit() { memset(Buf, 0, sizeof(Buf)); }\r
  84   void Add(unsigned int pos, Byte val) { Buf[pos >> MTF_MOVS] |= ((CMtfVar)val << ((pos & MTF_MASK) << 3));  }\r
  85   Byte GetHead() const { return (Byte)Buf[0]; }\r
  86   Byte GetAndMove(unsigned int pos)\r
  87   {\r
  88     UInt32 lim = ((UInt32)pos >> MTF_MOVS);\r
  89     pos = (pos & MTF_MASK) << 3;\r
  90     CMtfVar prev = (Buf[lim] >> pos) & 0xFF;\r
  91 \r
  92     UInt32 i = 0;\r
  93     if ((lim & 1) != 0)\r
  94     {\r
  95       CMtfVar next = Buf[0];\r
  96       Buf[0] = (next << 8) | prev;\r
  97       prev = (next >> (MTF_MASK << 3));\r
  98       i = 1;\r
  99       lim -= 1;\r
 100     }\r
 101     for (; i < lim; i += 2)\r
 102     {\r
 103       CMtfVar n0 = Buf[i];\r
 104       CMtfVar n1 = Buf[i + 1];\r
 105       Buf[i    ] = (n0 << 8) | prev;\r
 106       Buf[i + 1] = (n1 << 8) | (n0 >> (MTF_MASK << 3));\r
 107       prev = (n1 >> (MTF_MASK << 3));\r
 108     }\r
 109     CMtfVar next = Buf[i];\r
 110     CMtfVar mask = (((CMtfVar)0x100 << pos) - 1);\r
 111     Buf[i] = (next & ~mask) | (((next << 8) | prev) & mask);\r
 112     return (Byte)Buf[0];\r
 113   }\r
 114 };\r
 115 \r
 116 /*\r
 117 const int kSmallSize = 64;\r
 118 class CMtf8Decoder\r
 119 {\r
 120   Byte SmallBuffer[kSmallSize];\r
 121   int SmallSize;\r
 122   Byte Counts[16];\r
 123   int Size;\r
 124 public:\r
 125   Byte Buf[256];\r
 126 \r
 127   Byte GetHead() const\r
 128   {\r
 129     if (SmallSize > 0)\r
 130       return SmallBuffer[kSmallSize - SmallSize];\r
 131     return Buf[0];\r
 132   }\r
 133 \r
 134   void Init(int size)\r
 135   {\r
 136     Size = size;\r
 137     SmallSize = 0;\r
 138     for (int i = 0; i < 16; i++)\r
 139     {\r
 140       Counts[i] = ((size >= 16) ? 16 : size);\r
 141       size -= Counts[i];\r
 142     }\r
 143   }\r
 144 \r
 145   Byte GetAndMove(int pos)\r
 146   {\r
 147     if (pos < SmallSize)\r
 148     {\r
 149       Byte *p = SmallBuffer + kSmallSize - SmallSize;\r
 150       Byte res = p[pos];\r
 151       for (; pos > 0; pos--)\r
 152         p[pos] = p[pos - 1];\r
 153       SmallBuffer[kSmallSize - SmallSize] = res;\r
 154       return res;\r
 155     }\r
 156     if (SmallSize == kSmallSize)\r
 157     {\r
 158       int i = Size - 1;\r
 159       int g = 16;\r
 160       do\r
 161       {\r
 162         g--;\r
 163         int offset = (g << 4);\r
 164         for (int t = Counts[g] - 1; t >= 0; t--, i--)\r
 165           Buf[i] = Buf[offset + t];\r
 166       }\r
 167       while(g != 0);\r
 168       \r
 169       for (i = kSmallSize - 1; i >= 0; i--)\r
 170         Buf[i] = SmallBuffer[i];\r
 171       Init(Size);\r
 172     }\r
 173     pos -= SmallSize;\r
 174     int g;\r
 175     for (g = 0; pos >= Counts[g]; g++)\r
 176       pos -= Counts[g];\r
 177     int offset = (g << 4);\r
 178     Byte res = Buf[offset + pos];\r
 179     for (pos; pos < 16 - 1; pos++)\r
 180       Buf[offset + pos] = Buf[offset + pos + 1];\r
 181     \r
 182     SmallSize++;\r
 183     SmallBuffer[kSmallSize - SmallSize] = res;\r
 184 \r
 185     Counts[g]--;\r
 186     return res;\r
 187   }\r
 188 };\r
 189 */\r
 190 \r
 191 }\r
 192 \r
 193 #endif\r