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