1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/win32/7zip/7z/CPP/7zip/Compress/Mtf8.h	Sat Mar 03 10:31:27 2012 -0600
     1.3 @@ -0,0 +1,196 @@
     1.4 +// Mtf8.h
     1.5 +
     1.6 +#ifndef __COMPRESS_MTF8_H
     1.7 +#define __COMPRESS_MTF8_H
     1.8 +
     1.9 +#include "../../Common/Types.h"
    1.10 +
    1.11 +namespace NCompress {
    1.12 +
    1.13 +struct CMtf8Encoder
    1.14 +{
    1.15 +  Byte Buf[256];
    1.16 +
    1.17 +  int FindAndMove(Byte v)
    1.18 +  {
    1.19 +    int pos;
    1.20 +    for (pos = 0; Buf[pos] != v; pos++);
    1.21 +    int resPos = pos;
    1.22 +    for (; pos >= 8; pos -= 8)
    1.23 +    {
    1.24 +      Buf[pos] = Buf[pos - 1];
    1.25 +      Buf[pos - 1] = Buf[pos - 2];
    1.26 +      Buf[pos - 2] = Buf[pos - 3];
    1.27 +      Buf[pos - 3] = Buf[pos - 4];
    1.28 +      Buf[pos - 4] = Buf[pos - 5];
    1.29 +      Buf[pos - 5] = Buf[pos - 6];
    1.30 +      Buf[pos - 6] = Buf[pos - 7];
    1.31 +      Buf[pos - 7] = Buf[pos - 8];
    1.32 +    }
    1.33 +    for (; pos > 0; pos--)
    1.34 +      Buf[pos] = Buf[pos - 1];
    1.35 +    Buf[0] = v;
    1.36 +    return resPos;
    1.37 +  }
    1.38 +};
    1.39 +
    1.40 +/*
    1.41 +struct CMtf8Decoder
    1.42 +{
    1.43 +  Byte Buf[256];
    1.44 +
    1.45 +  void Init(int) {};
    1.46 +  Byte GetHead() const { return Buf[0]; }
    1.47 +  Byte GetAndMove(int pos)
    1.48 +  {
    1.49 +    Byte res = Buf[pos];
    1.50 +    for (; pos >= 8; pos -= 8)
    1.51 +    {
    1.52 +      Buf[pos] = Buf[pos - 1];
    1.53 +      Buf[pos - 1] = Buf[pos - 2];
    1.54 +      Buf[pos - 2] = Buf[pos - 3];
    1.55 +      Buf[pos - 3] = Buf[pos - 4];
    1.56 +      Buf[pos - 4] = Buf[pos - 5];
    1.57 +      Buf[pos - 5] = Buf[pos - 6];
    1.58 +      Buf[pos - 6] = Buf[pos - 7];
    1.59 +      Buf[pos - 7] = Buf[pos - 8];
    1.60 +    }
    1.61 +    for (; pos > 0; pos--)
    1.62 +      Buf[pos] = Buf[pos - 1];
    1.63 +    Buf[0] = res;
    1.64 +    return res;
    1.65 +  }
    1.66 +};
    1.67 +*/
    1.68 +
    1.69 +#ifdef _WIN64
    1.70 +#define MODE_64BIT
    1.71 +#endif
    1.72 +
    1.73 +#ifdef MODE_64BIT
    1.74 +typedef UInt64 CMtfVar;
    1.75 +#define MTF_MOVS 3
    1.76 +#else
    1.77 +typedef UInt32 CMtfVar;
    1.78 +#define MTF_MOVS 2
    1.79 +#endif
    1.80 +
    1.81 +#define MTF_MASK ((1 << MTF_MOVS) - 1)
    1.82 +
    1.83 +
    1.84 +struct CMtf8Decoder
    1.85 +{
    1.86 +  CMtfVar Buf[256 >> MTF_MOVS];
    1.87 +
    1.88 +  void StartInit() { memset(Buf, 0, sizeof(Buf)); }
    1.89 +  void Add(unsigned int pos, Byte val) { Buf[pos >> MTF_MOVS] |= ((CMtfVar)val << ((pos & MTF_MASK) << 3));  }
    1.90 +  Byte GetHead() const { return (Byte)Buf[0]; }
    1.91 +  Byte GetAndMove(unsigned int pos)
    1.92 +  {
    1.93 +    UInt32 lim = ((UInt32)pos >> MTF_MOVS);
    1.94 +    pos = (pos & MTF_MASK) << 3;
    1.95 +    CMtfVar prev = (Buf[lim] >> pos) & 0xFF;
    1.96 +
    1.97 +    UInt32 i = 0;
    1.98 +    if ((lim & 1) != 0)
    1.99 +    {
   1.100 +      CMtfVar next = Buf[0];
   1.101 +      Buf[0] = (next << 8) | prev;
   1.102 +      prev = (next >> (MTF_MASK << 3));
   1.103 +      i = 1;
   1.104 +      lim -= 1;
   1.105 +    }
   1.106 +    for (; i < lim; i += 2)
   1.107 +    {
   1.108 +      CMtfVar next = Buf[i];
   1.109 +      Buf[i] = (next << 8) | prev;
   1.110 +      prev = (next >> (MTF_MASK << 3));
   1.111 +      next = Buf[i + 1];
   1.112 +      Buf[i + 1] = (next << 8) | prev;
   1.113 +      prev = (next >> (MTF_MASK << 3));
   1.114 +    }
   1.115 +    CMtfVar next = Buf[i];
   1.116 +    CMtfVar mask = (((CMtfVar)0x100 << pos) - 1);
   1.117 +    Buf[i] = (next & ~mask) | (((next << 8) | prev) & mask);
   1.118 +    return (Byte)Buf[0];
   1.119 +  }
   1.120 +};
   1.121 +
   1.122 +/*
   1.123 +const int kSmallSize = 64;
   1.124 +class CMtf8Decoder
   1.125 +{
   1.126 +  Byte SmallBuffer[kSmallSize];
   1.127 +  int SmallSize;
   1.128 +  Byte Counts[16];
   1.129 +  int Size;
   1.130 +public:
   1.131 +  Byte Buf[256];
   1.132 +
   1.133 +  Byte GetHead() const
   1.134 +  {
   1.135 +    if (SmallSize > 0)
   1.136 +      return SmallBuffer[kSmallSize - SmallSize];
   1.137 +    return Buf[0];
   1.138 +  }
   1.139 +
   1.140 +  void Init(int size)
   1.141 +  {
   1.142 +    Size = size;
   1.143 +    SmallSize = 0;
   1.144 +    for (int i = 0; i < 16; i++)
   1.145 +    {
   1.146 +      Counts[i] = ((size >= 16) ? 16 : size);
   1.147 +      size -= Counts[i];
   1.148 +    }
   1.149 +  }
   1.150 +
   1.151 +  Byte GetAndMove(int pos)
   1.152 +  {
   1.153 +    if (pos < SmallSize)
   1.154 +    {
   1.155 +      Byte *p = SmallBuffer + kSmallSize - SmallSize;
   1.156 +      Byte res = p[pos];
   1.157 +      for (; pos > 0; pos--)
   1.158 +        p[pos] = p[pos - 1];
   1.159 +      SmallBuffer[kSmallSize - SmallSize] = res;
   1.160 +      return res;
   1.161 +    }
   1.162 +    if (SmallSize == kSmallSize)
   1.163 +    {
   1.164 +      int i = Size - 1;
   1.165 +      int g = 16;
   1.166 +      do
   1.167 +      {
   1.168 +        g--;
   1.169 +        int offset = (g << 4);
   1.170 +        for (int t = Counts[g] - 1; t >= 0; t--, i--)
   1.171 +          Buf[i] = Buf[offset + t];
   1.172 +      }
   1.173 +      while(g != 0);
   1.174 +      
   1.175 +      for (i = kSmallSize - 1; i >= 0; i--)
   1.176 +        Buf[i] = SmallBuffer[i];
   1.177 +      Init(Size);
   1.178 +    }
   1.179 +    pos -= SmallSize;
   1.180 +    int g;
   1.181 +    for (g = 0; pos >= Counts[g]; g++)
   1.182 +      pos -= Counts[g];
   1.183 +    int offset = (g << 4);
   1.184 +    Byte res = Buf[offset + pos];
   1.185 +    for (pos; pos < 16 - 1; pos++)
   1.186 +      Buf[offset + pos] = Buf[offset + pos + 1];
   1.187 +    
   1.188 +    SmallSize++;
   1.189 +    SmallBuffer[kSmallSize - SmallSize] = res;
   1.190 +
   1.191 +    Counts[g]--;
   1.192 +    return res;
   1.193 +  }
   1.194 +};
   1.195 +*/
   1.196 +
   1.197 +}
   1.198 +
   1.199 +#endif