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
10namespace NCompress {
11namespace NRangeCoder {
12
13const unsigned kNumTopBits = 24;
14const UInt32 kTopValue = (1 << kNumTopBits);
15
16class CEncoder
17{
18  UInt32 _cacheSize;
19  Byte _cache;
20public:
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
107class CDecoder
108{
109public:
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