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