1 // Compress/RangeCoder/RangeCoder.h 2 3 #ifndef __COMPRESS_RANGECODER_H 4 #define __COMPRESS_RANGECODER_H 5 6 #include "../../Common/InBuffer.h" 7 #include "../../Common/OutBuffer.h" 8 9 namespace NCompress { 10 namespace NRangeCoder { 11 12 const int kNumTopBits = 24; 13 const UInt32 kTopValue = (1 << kNumTopBits); 14 15 class CEncoder 16 { 17 UInt32 _ffNum; 18 Byte _cache; 19 public: 20 UInt64 Low; 21 UInt32 Range; 22 COutBuffer Stream; Create(UInt32 bufferSize)23 bool Create(UInt32 bufferSize) { return Stream.Create(bufferSize); } 24 SetStream(ISequentialOutStream * stream)25 void SetStream(ISequentialOutStream *stream) { Stream.SetStream(stream); } Init()26 void Init() 27 { 28 Stream.Init(); 29 Low = 0; 30 Range = 0xFFFFFFFF; 31 _ffNum = 0; 32 _cache = 0; 33 } 34 FlushData()35 void FlushData() 36 { 37 // Low += 1; 38 for(int i = 0; i < 5; i++) 39 ShiftLow(); 40 } 41 FlushStream()42 HRESULT FlushStream() { return Stream.Flush(); } 43 ReleaseStream()44 void ReleaseStream() { Stream.ReleaseStream(); } 45 Encode(UInt32 start,UInt32 size,UInt32 total)46 void Encode(UInt32 start, UInt32 size, UInt32 total) 47 { 48 Low += start * (Range /= total); 49 Range *= size; 50 while (Range < kTopValue) 51 { 52 Range <<= 8; 53 ShiftLow(); 54 } 55 } 56 57 /* 58 void EncodeDirectBitsDiv(UInt32 value, UInt32 numTotalBits) 59 { 60 Low += value * (Range >>= numTotalBits); 61 Normalize(); 62 } 63 64 void EncodeDirectBitsDiv2(UInt32 value, UInt32 numTotalBits) 65 { 66 if (numTotalBits <= kNumBottomBits) 67 EncodeDirectBitsDiv(value, numTotalBits); 68 else 69 { 70 EncodeDirectBitsDiv(value >> kNumBottomBits, (numTotalBits - kNumBottomBits)); 71 EncodeDirectBitsDiv(value & ((1 << kBottomValueBits) - 1), kNumBottomBits); 72 } 73 } 74 */ ShiftLow()75 void ShiftLow() 76 { 77 if (Low < (UInt32)0xFF000000 || UInt32(Low >> 32) == 1) 78 { 79 Stream.WriteByte(Byte(_cache + Byte(Low >> 32))); 80 for (;_ffNum != 0; _ffNum--) 81 Stream.WriteByte(Byte(0xFF + Byte(Low >> 32))); 82 _cache = Byte(UInt32(Low) >> 24); 83 } 84 else 85 _ffNum++; 86 Low = UInt32(Low) << 8; 87 } 88 EncodeDirectBits(UInt32 value,int numTotalBits)89 void EncodeDirectBits(UInt32 value, int numTotalBits) 90 { 91 for (int i = numTotalBits - 1; i >= 0; i--) 92 { 93 Range >>= 1; 94 if (((value >> i) & 1) == 1) 95 Low += Range; 96 if (Range < kTopValue) 97 { 98 Range <<= 8; 99 ShiftLow(); 100 } 101 } 102 } 103 EncodeBit(UInt32 size0,UInt32 numTotalBits,UInt32 symbol)104 void EncodeBit(UInt32 size0, UInt32 numTotalBits, UInt32 symbol) 105 { 106 UInt32 newBound = (Range >> numTotalBits) * size0; 107 if (symbol == 0) 108 Range = newBound; 109 else 110 { 111 Low += newBound; 112 Range -= newBound; 113 } 114 while (Range < kTopValue) 115 { 116 Range <<= 8; 117 ShiftLow(); 118 } 119 } 120 GetProcessedSize()121 UInt64 GetProcessedSize() { return Stream.GetProcessedSize() + _ffNum; } 122 }; 123 124 class CDecoder 125 { 126 public: 127 CInBuffer Stream; 128 UInt32 Range; 129 UInt32 Code; Create(UInt32 bufferSize)130 bool Create(UInt32 bufferSize) { return Stream.Create(bufferSize); } 131 Normalize()132 void Normalize() 133 { 134 while (Range < kTopValue) 135 { 136 Code = (Code << 8) | Stream.ReadByte(); 137 Range <<= 8; 138 } 139 } 140 SetStream(ISequentialInStream * stream)141 void SetStream(ISequentialInStream *stream) { Stream.SetStream(stream); } Init()142 void Init() 143 { 144 Stream.Init(); 145 Code = 0; 146 Range = 0xFFFFFFFF; 147 for(int i = 0; i < 5; i++) 148 Code = (Code << 8) | Stream.ReadByte(); 149 } 150 ReleaseStream()151 void ReleaseStream() { Stream.ReleaseStream(); } 152 GetThreshold(UInt32 total)153 UInt32 GetThreshold(UInt32 total) 154 { 155 return (Code) / ( Range /= total); 156 } 157 Decode(UInt32 start,UInt32 size)158 void Decode(UInt32 start, UInt32 size) 159 { 160 Code -= start * Range; 161 Range *= size; 162 Normalize(); 163 } 164 165 /* 166 UInt32 DecodeDirectBitsDiv(UInt32 numTotalBits) 167 { 168 Range >>= numTotalBits; 169 UInt32 threshold = Code / Range; 170 Code -= threshold * Range; 171 172 Normalize(); 173 return threshold; 174 } 175 176 UInt32 DecodeDirectBitsDiv2(UInt32 numTotalBits) 177 { 178 if (numTotalBits <= kNumBottomBits) 179 return DecodeDirectBitsDiv(numTotalBits); 180 UInt32 result = DecodeDirectBitsDiv(numTotalBits - kNumBottomBits) << kNumBottomBits; 181 return (result | DecodeDirectBitsDiv(kNumBottomBits)); 182 } 183 */ 184 DecodeDirectBits(int numTotalBits)185 UInt32 DecodeDirectBits(int numTotalBits) 186 { 187 UInt32 range = Range; 188 UInt32 code = Code; 189 UInt32 result = 0; 190 for (int i = numTotalBits; i != 0; i--) 191 { 192 range >>= 1; 193 /* 194 result <<= 1; 195 if (code >= range) 196 { 197 code -= range; 198 result |= 1; 199 } 200 */ 201 UInt32 t = (code - range) >> 31; 202 code -= range & (t - 1); 203 result = (result << 1) | (1 - t); 204 205 if (range < kTopValue) 206 { 207 code = (code << 8) | Stream.ReadByte(); 208 range <<= 8; 209 } 210 } 211 Range = range; 212 Code = code; 213 return result; 214 } 215 DecodeBit(UInt32 size0,UInt32 numTotalBits)216 UInt32 DecodeBit(UInt32 size0, UInt32 numTotalBits) 217 { 218 UInt32 newBound = (Range >> numTotalBits) * size0; 219 UInt32 symbol; 220 if (Code < newBound) 221 { 222 symbol = 0; 223 Range = newBound; 224 } 225 else 226 { 227 symbol = 1; 228 Code -= newBound; 229 Range -= newBound; 230 } 231 Normalize(); 232 return symbol; 233 } 234 GetProcessedSize()235 UInt64 GetProcessedSize() {return Stream.GetProcessedSize(); } 236 }; 237 238 }} 239 240 #endif 241