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