Debian Codegraph @

utils/lzma/SRC/7zip/Compress/RangeCoder/RangeCoder.h

raw
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;
23 bool Create(UInt32 bufferSize) { return Stream.Create(bufferSize); }
24
25 void SetStream(ISequentialOutStream *stream) { Stream.SetStream(stream); }
26 void Init()
27 {
28 Stream.Init();
29 Low = 0;
30 Range = 0xFFFFFFFF;
31 _ffNum = 0;
32 _cache = 0;
33 }
34
35 void FlushData()
36 {
37 // Low += 1;
38 for(int i = 0; i < 5; i++)
39 ShiftLow();
40 }
41
42 HRESULT FlushStream() { return Stream.Flush(); }
43
44 void ReleaseStream() { Stream.ReleaseStream(); }
45
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 */
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
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
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
121 UInt64 GetProcessedSize() { return Stream.GetProcessedSize() + _ffNum; }
122 };
123
124 class CDecoder
125 {
126 public:
127 CInBuffer Stream;
128 UInt32 Range;
129 UInt32 Code;
130 bool Create(UInt32 bufferSize) { return Stream.Create(bufferSize); }
131
132 void Normalize()
133 {
134 while (Range < kTopValue)
135 {
136 Code = (Code << 8) | Stream.ReadByte();
137 Range <<= 8;
138 }
139 }
140
141 void SetStream(ISequentialInStream *stream) { Stream.SetStream(stream); }
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
151 void ReleaseStream() { Stream.ReleaseStream(); }
152
153 UInt32 GetThreshold(UInt32 total)
154 {
155 return (Code) / ( Range /= total);
156 }
157
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
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
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
235 UInt64 GetProcessedSize() {return Stream.GetProcessedSize(); }
236 };
237
238 }}
239
240 #endif