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
10namespace NCompress {
11namespace NRangeCoder {
12
13const int 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 bufferSize) { return Stream.Create(bufferSize); }
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 ReleaseStream() { Stream.ReleaseStream(); }
46
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
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
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
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
106  UInt64 GetProcessedSize() {  return Stream.GetProcessedSize() + _cacheSize + 4; }
107};
108
109class CDecoder
110{
111public:
112  CInBuffer Stream;
113  UInt32 Range;
114  UInt32 Code;
115  bool Create(UInt32 bufferSize) { return Stream.Create(bufferSize); }
116
117  void Normalize()
118  {
119    while (Range < kTopValue)
120    {
121      Code = (Code << 8) | Stream.ReadByte();
122      Range <<= 8;
123    }
124  }
125
126  void SetStream(ISequentialInStream *stream) { Stream.SetStream(stream); }
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
136  void ReleaseStream() { Stream.ReleaseStream(); }
137
138  UInt32 GetThreshold(UInt32 total)
139  {
140    return (Code) / ( Range /= total);
141  }
142
143  void Decode(UInt32 start, UInt32 size)
144  {
145    Code -= start * Range;
146    Range *= size;
147    Normalize();
148  }
149
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
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
200  UInt64 GetProcessedSize() {return Stream.GetProcessedSize(); }
201};
202
203}}
204
205#endif
206