Mercurial > vba-linux

annotate src/win32/7zip/7z/CPP/7zip/Compress/Mtf8.h @ 1:f9f4f1b99eed

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