1 // Mtf8.h 2 3 #ifndef ZIP7_INC_COMPRESS_MTF8_H 4 #define ZIP7_INC_COMPRESS_MTF8_H 5 6 #include "../../../C/CpuArch.h" 7 8 namespace NCompress { 9 10 struct CMtf8Encoder 11 { 12 Byte Buf[256]; 13 FindAndMoveCMtf8Encoder14 unsigned FindAndMove(Byte v) throw() 15 { 16 size_t pos; 17 for (pos = 0; Buf[pos] != v; pos++); 18 const unsigned resPos = (unsigned)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 StartInit() { memset(Buf, 0, sizeof(Buf)); } 43 void Add(unsigned pos, Byte val) { Buf[pos] = val; } 44 Byte GetHead() const { return Buf[0]; } 45 Byte GetAndMove(unsigned pos) 46 { 47 Byte res = Buf[pos]; 48 for (; pos >= 8; pos -= 8) 49 { 50 Buf[pos] = Buf[pos - 1]; 51 Buf[pos - 1] = Buf[pos - 2]; 52 Buf[pos - 2] = Buf[pos - 3]; 53 Buf[pos - 3] = Buf[pos - 4]; 54 Buf[pos - 4] = Buf[pos - 5]; 55 Buf[pos - 5] = Buf[pos - 6]; 56 Buf[pos - 6] = Buf[pos - 7]; 57 Buf[pos - 7] = Buf[pos - 8]; 58 } 59 for (; pos > 0; pos--) 60 Buf[pos] = Buf[pos - 1]; 61 Buf[0] = res; 62 return res; 63 } 64 }; 65 */ 66 67 #ifdef MY_CPU_64BIT 68 typedef UInt64 CMtfVar; 69 #define Z7_MTF_MOVS 3 70 #else 71 typedef UInt32 CMtfVar; 72 #define Z7_MTF_MOVS 2 73 #endif 74 75 #define Z7_MTF_MASK ((1 << Z7_MTF_MOVS) - 1) 76 77 78 struct CMtf8Decoder 79 { 80 CMtfVar Buf[256 >> Z7_MTF_MOVS]; 81 StartInitCMtf8Decoder82 void StartInit() { memset(Buf, 0, sizeof(Buf)); } AddCMtf8Decoder83 void Add(unsigned pos, Byte val) { Buf[pos >> Z7_MTF_MOVS] |= ((CMtfVar)val << ((pos & Z7_MTF_MASK) << 3)); } GetHeadCMtf8Decoder84 Byte GetHead() const { return (Byte)Buf[0]; } 85 86 Z7_FORCE_INLINE GetAndMoveCMtf8Decoder87 Byte GetAndMove(unsigned pos) throw() 88 { 89 const UInt32 lim = ((UInt32)pos >> Z7_MTF_MOVS); 90 pos = (pos & Z7_MTF_MASK) << 3; 91 CMtfVar prev = (Buf[lim] >> pos) & 0xFF; 92 93 UInt32 i = 0; 94 95 96 /* 97 if ((lim & 1) != 0) 98 { 99 CMtfVar next = Buf[0]; 100 Buf[0] = (next << 8) | prev; 101 prev = (next >> (Z7_MTF_MASK << 3)); 102 i = 1; 103 lim -= 1; 104 } 105 for (; i < lim; i += 2) 106 { 107 CMtfVar n0 = Buf[i]; 108 CMtfVar n1 = Buf[i + 1]; 109 Buf[i ] = (n0 << 8) | prev; 110 Buf[i + 1] = (n1 << 8) | (n0 >> (Z7_MTF_MASK << 3)); 111 prev = (n1 >> (Z7_MTF_MASK << 3)); 112 } 113 */ 114 115 for (; i < lim; i++) 116 { 117 const CMtfVar n0 = Buf[i]; 118 Buf[i ] = (n0 << 8) | prev; 119 prev = (n0 >> (Z7_MTF_MASK << 3)); 120 } 121 122 123 const CMtfVar next = Buf[i]; 124 const CMtfVar mask = (((CMtfVar)0x100 << pos) - 1); 125 Buf[i] = (next & ~mask) | (((next << 8) | prev) & mask); 126 return (Byte)Buf[0]; 127 } 128 }; 129 130 /* 131 const int kSmallSize = 64; 132 class CMtf8Decoder 133 { 134 Byte SmallBuffer[kSmallSize]; 135 int SmallSize; 136 int Counts[16]; 137 int Size; 138 public: 139 Byte Buf[256]; 140 141 Byte GetHead() const 142 { 143 if (SmallSize > 0) 144 return SmallBuffer[kSmallSize - SmallSize]; 145 return Buf[0]; 146 } 147 148 void Init(int size) 149 { 150 Size = size; 151 SmallSize = 0; 152 for (int i = 0; i < 16; i++) 153 { 154 Counts[i] = ((size >= 16) ? 16 : size); 155 size -= Counts[i]; 156 } 157 } 158 159 void Add(unsigned pos, Byte val) 160 { 161 Buf[pos] = val; 162 } 163 164 Byte GetAndMove(int pos) 165 { 166 if (pos < SmallSize) 167 { 168 Byte *p = SmallBuffer + kSmallSize - SmallSize; 169 Byte res = p[pos]; 170 for (; pos > 0; pos--) 171 p[pos] = p[pos - 1]; 172 SmallBuffer[kSmallSize - SmallSize] = res; 173 return res; 174 } 175 if (SmallSize == kSmallSize) 176 { 177 int i = Size - 1; 178 int g = 16; 179 do 180 { 181 g--; 182 int offset = (g << 4); 183 for (int t = Counts[g] - 1; t >= 0; t--, i--) 184 Buf[i] = Buf[offset + t]; 185 } 186 while (g != 0); 187 188 for (i = kSmallSize - 1; i >= 0; i--) 189 Buf[i] = SmallBuffer[i]; 190 Init(Size); 191 } 192 pos -= SmallSize; 193 int g; 194 for (g = 0; pos >= Counts[g]; g++) 195 pos -= Counts[g]; 196 int offset = (g << 4); 197 Byte res = Buf[offset + pos]; 198 for (pos; pos < 16 - 1; pos++) 199 Buf[offset + pos] = Buf[offset + pos + 1]; 200 201 SmallSize++; 202 SmallBuffer[kSmallSize - SmallSize] = res; 203 204 Counts[g]--; 205 return res; 206 } 207 }; 208 */ 209 210 } 211 212 #endif 213