1 #include <algorithm>
2
3 #include "All.h"
4 #include "APEInfo.h"
5 #include "UnBitArray.h"
6 #include "BitArray.h"
7
8
9 const uint32 POWERS_OF_TWO_MINUS_ONE_REVERSED[33] = {4294967295u,2147483647u,
10 1073741823u,536870911u,268435455u,134217727u,67108863u,33554431u,16777215u,
11 8388607u,4194303u,2097151u,1048575u,524287u,262143u,131071u,65535u,32767u,
12 16383u,8191u,4095u,2047u,1023u,511u,255u,127u,63u,31u,15u,7u,3u,1u,0u};
13
14 const uint32 K_SUM_MIN_BOUNDARY[32] = {0u,32u,64u,128u,256u,512u,1024u,2048u,
15 4096u,8192u,16384u,32768u,65536u,131072u,262144u,524288u,1048576u,2097152u,
16 4194304u,8388608u,16777216u,33554432u,67108864u,134217728u,268435456u,
17 536870912u,1073741824u,2147483648u,0u,0u,0u,0u};
18
19 const uint32 RANGE_TOTAL_1[65] = {0u,14824u,28224u,39348u,47855u,53994u,58171u,
20 60926u,62682u,63786u,64463u,64878u,65126u,65276u,65365u,65419u,65450u,
21 65469u,65480u,65487u,65491u,65493u,65494u,65495u,65496u,65497u,65498u,
22 65499u,65500u,65501u,65502u,65503u,65504u,65505u,65506u,65507u,65508u,
23 65509u,65510u,65511u,65512u,65513u,65514u,65515u,65516u,65517u,65518u,
24 65519u,65520u,65521u,65522u,65523u,65524u,65525u,65526u,65527u,65528u,
25 65529u,65530u,65531u,65532u,65533u,65534u,65535u,65536u};
26
27 const uint32 RANGE_WIDTH_1[64] = {14824u,13400u,11124u,8507u,6139u,4177u,2755u,
28 1756u,1104u,677u,415u,248u,150u,89u,54u,31u,19u,11u,7u,4u,2u,1u,1u,1u,1u,1u,
29 1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,
30 1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u};
31
32 const uint32 RANGE_TOTAL_2[65] = {0u,19578u,36160u,48417u,56323u,60899u,63265u,
33 64435u,64971u,65232u,65351u,65416u,65447u,65466u,65476u,65482u,65485u,
34 65488u,65490u,65491u,65492u,65493u,65494u,65495u,65496u,65497u,65498u,
35 65499u,65500u,65501u,65502u,65503u,65504u,65505u,65506u,65507u,65508u,
36 65509u,65510u,65511u,65512u,65513u,65514u,65515u,65516u,65517u,65518u,
37 65519u,65520u,65521u,65522u,65523u,65524u,65525u,65526u,65527u,65528u,
38 65529u,65530u,65531u,65532u,65533u,65534u,65535u,65536u};
39
40 const uint32 RANGE_WIDTH_2[64] = {19578u,16582u,12257u,7906u,4576u,2366u,1170u,
41 536u,261u,119u,65u,31u,19u,10u,6u,3u,3u,2u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,
42 1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,
43 1u,1u,1u,1u,1u,1u,1u,1u,1u,1u};
44
45
46 #define RANGE_OVERFLOW_TOTAL_WIDTH 65536
47 #define RANGE_OVERFLOW_SHIFT 16
48
49 #define CODE_BITS 32
50 #define TOP_VALUE ((unsigned int ) 1 << (CODE_BITS - 1))
51 #define SHIFT_BITS (CODE_BITS - 9)
52 #define EXTRA_BITS ((CODE_BITS - 2) % 8 + 1)
53 #define BOTTOM_VALUE (TOP_VALUE >> 8)
54
55 #define MODEL_ELEMENTS 64
56
57
CUnBitArray(CIO * pIO,int nVersion)58 CUnBitArray::CUnBitArray(CIO * pIO, int nVersion)
59 {
60 CreateHelper(pIO, 16384, nVersion);
61 m_nFlushCounter = 0;
62 m_nFinalizeCounter = 0;
63 }
64
65
~CUnBitArray()66 CUnBitArray::~CUnBitArray()
67 {
68 SAFE_ARRAY_DELETE(m_pBitArray)
69 }
70
71
72 unsigned int
DecodeValue(DECODE_VALUE_METHOD DecodeMethod,int nParam1,int nParam2)73 CUnBitArray::DecodeValue(DECODE_VALUE_METHOD DecodeMethod, int nParam1,
74 int nParam2)
75 {
76 switch (DecodeMethod) {
77 case DECODE_VALUE_METHOD_UNSIGNED_INT:
78 return DecodeValueXBits(32);
79 case DECODE_VALUE_METHOD_UNSIGNED_RICE:
80 case DECODE_VALUE_METHOD_X_BITS:
81 break;
82 }
83
84 return 0;
85 }
86
87
88 void
GenerateArray(int * pOutputArray,int nElements,int nBytesRequired)89 CUnBitArray::GenerateArray(int * pOutputArray, int nElements,
90 int nBytesRequired)
91 {
92 GenerateArrayRange(pOutputArray, nElements);
93 }
94
95 __inline unsigned char
GetC()96 CUnBitArray::GetC()
97 {
98 uchar nValue = static_cast<uchar>(m_pBitArray[m_nCurrentBitIndex >> 5]
99 >> (24 - (m_nCurrentBitIndex & 31)));
100 m_nCurrentBitIndex += 8;
101 return nValue;
102 }
103
104
105 __inline int
RangeDecodeFast(int nShift)106 CUnBitArray::RangeDecodeFast(int nShift)
107 {
108 while (m_RangeCoderInfo.range <= BOTTOM_VALUE) {
109 m_RangeCoderInfo.buffer = (m_RangeCoderInfo.buffer << 8)
110 | ((m_pBitArray[m_nCurrentBitIndex >> 5]
111 >> (24 - (m_nCurrentBitIndex & 31))) & 0xFF);
112 m_nCurrentBitIndex += 8;
113 m_RangeCoderInfo.low = (m_RangeCoderInfo.low << 8)
114 | ((m_RangeCoderInfo.buffer >> 1) & 0xFF);
115 m_RangeCoderInfo.range <<= 8;
116 }
117
118 // decode
119 m_RangeCoderInfo.range = m_RangeCoderInfo.range >> nShift;
120 return m_RangeCoderInfo.low / m_RangeCoderInfo.range;
121 }
122
123
RangeDecodeFastWithUpdate(int nShift)124 __inline int CUnBitArray::RangeDecodeFastWithUpdate(int nShift)
125 {
126 while (m_RangeCoderInfo.range <= BOTTOM_VALUE) {
127 m_RangeCoderInfo.buffer = (m_RangeCoderInfo.buffer << 8)
128 | ((m_pBitArray[m_nCurrentBitIndex >> 5]
129 >> (24 - (m_nCurrentBitIndex & 31))) & 0xFF);
130 m_nCurrentBitIndex += 8;
131 m_RangeCoderInfo.low = (m_RangeCoderInfo.low << 8)
132 | ((m_RangeCoderInfo.buffer >> 1) & 0xFF);
133 m_RangeCoderInfo.range <<= 8;
134 }
135
136 // decode
137 m_RangeCoderInfo.range = m_RangeCoderInfo.range >> nShift;
138 int nRetVal = m_RangeCoderInfo.low / m_RangeCoderInfo.range;
139 m_RangeCoderInfo.low -= m_RangeCoderInfo.range * nRetVal;
140 return nRetVal;
141 }
142
143
144 int
DecodeValueRange(UNBIT_ARRAY_STATE & BitArrayState)145 CUnBitArray::DecodeValueRange(UNBIT_ARRAY_STATE & BitArrayState)
146 {
147 // make sure there is room for the data
148 // this is a little slower than ensuring a huge block to start with,
149 // but it's safer
150 if (m_nCurrentBitIndex > m_nRefillBitThreshold)
151 FillBitArray();
152
153 int nValue = 0;
154
155 if (m_nVersion >= 3990) {
156 // figure the pivot value
157 int nPivotValue = max(BitArrayState.nKSum / 32, 1UL);
158
159 // get the overflow
160 int nOverflow = 0;
161
162 // decode
163 uint32 nRangeTotal = RangeDecodeFast(RANGE_OVERFLOW_SHIFT);
164
165 // lookup the symbol (must be a faster way than this)
166 while (nRangeTotal >= RANGE_TOTAL_2[nOverflow + 1])
167 nOverflow++;
168
169 // update
170 m_RangeCoderInfo.low -= m_RangeCoderInfo.range
171 * RANGE_TOTAL_2[nOverflow];
172 m_RangeCoderInfo.range = m_RangeCoderInfo.range
173 * RANGE_WIDTH_2[nOverflow];
174
175 // get the working k
176 if (nOverflow == (MODEL_ELEMENTS - 1)) {
177 nOverflow = RangeDecodeFastWithUpdate(16);
178 nOverflow <<= 16;
179 nOverflow |= RangeDecodeFastWithUpdate(16);
180 }
181
182 // get the value
183 int nBase = 0;
184
185 if (nPivotValue >= (1 << 16)) {
186 int nPivotValueBits = 0;
187 while ((nPivotValue >> nPivotValueBits) > 0)
188 nPivotValueBits++;
189
190 int nSplitFactor = 1 << (nPivotValueBits - 16);
191 int nPivotValueA = (nPivotValue / nSplitFactor) + 1;
192 int nPivotValueB = nSplitFactor;
193
194 while (m_RangeCoderInfo.range <= BOTTOM_VALUE) {
195 m_RangeCoderInfo.buffer = (m_RangeCoderInfo.buffer << 8)
196 | ((m_pBitArray[m_nCurrentBitIndex >> 5]
197 >> (24 - (m_nCurrentBitIndex & 31))) & 0xFF);
198 m_nCurrentBitIndex += 8;
199 m_RangeCoderInfo.low = (m_RangeCoderInfo.low << 8)
200 | ((m_RangeCoderInfo.buffer >> 1) & 0xFF);
201 m_RangeCoderInfo.range <<= 8;
202 }
203 m_RangeCoderInfo.range = m_RangeCoderInfo.range / nPivotValueA;
204 int nBaseA = m_RangeCoderInfo.low / m_RangeCoderInfo.range;
205 m_RangeCoderInfo.low -= m_RangeCoderInfo.range * nBaseA;
206
207 while (m_RangeCoderInfo.range <= BOTTOM_VALUE) {
208 m_RangeCoderInfo.buffer = (m_RangeCoderInfo.buffer << 8)
209 | ((m_pBitArray[m_nCurrentBitIndex >> 5]
210 >> (24 - (m_nCurrentBitIndex & 31))) & 0xFF);
211 m_nCurrentBitIndex += 8;
212 m_RangeCoderInfo.low = (m_RangeCoderInfo.low << 8)
213 | ((m_RangeCoderInfo.buffer >> 1) & 0xFF);
214 m_RangeCoderInfo.range <<= 8;
215 }
216 m_RangeCoderInfo.range = m_RangeCoderInfo.range / nPivotValueB;
217 int nBaseB = m_RangeCoderInfo.low / m_RangeCoderInfo.range;
218 m_RangeCoderInfo.low -= m_RangeCoderInfo.range * nBaseB;
219
220 nBase = nBaseA * nSplitFactor + nBaseB;
221 } else {
222 while (m_RangeCoderInfo.range <= BOTTOM_VALUE) {
223 m_RangeCoderInfo.buffer = (m_RangeCoderInfo.buffer << 8)
224 | ((m_pBitArray[m_nCurrentBitIndex >> 5]
225 >> (24 - (m_nCurrentBitIndex & 31))) & 0xFF);
226 m_nCurrentBitIndex += 8;
227 m_RangeCoderInfo.low = (m_RangeCoderInfo.low << 8)
228 | ((m_RangeCoderInfo.buffer >> 1) & 0xFF);
229 m_RangeCoderInfo.range <<= 8;
230 }
231
232 // decode
233 m_RangeCoderInfo.range = m_RangeCoderInfo.range / nPivotValue;
234 int nBaseLower = m_RangeCoderInfo.low / m_RangeCoderInfo.range;
235 m_RangeCoderInfo.low -= m_RangeCoderInfo.range * nBaseLower;
236
237 nBase = nBaseLower;
238 }
239
240 // build the value
241 nValue = nBase + (nOverflow * nPivotValue);
242 } else {
243 // decode
244 uint32 nRangeTotal = RangeDecodeFast(RANGE_OVERFLOW_SHIFT);
245
246 // lookup the symbol (must be a faster way than this)
247 int nOverflow = 0;
248 while (nRangeTotal >= RANGE_TOTAL_1[nOverflow + 1])
249 nOverflow++;
250
251 // update
252 m_RangeCoderInfo.low -= m_RangeCoderInfo.range
253 * RANGE_TOTAL_1[nOverflow];
254 m_RangeCoderInfo.range = m_RangeCoderInfo.range
255 * RANGE_WIDTH_1[nOverflow];
256
257 // get the working k
258 int nTempK;
259 if (nOverflow == (MODEL_ELEMENTS - 1)) {
260 nTempK = RangeDecodeFastWithUpdate(5);
261 nOverflow = 0;
262 } else
263 nTempK = (BitArrayState.k < 1) ? 0 : BitArrayState.k - 1;
264
265 // figure the extra bits on the left and the left value
266 if (nTempK <= 16 || m_nVersion < 3910) {
267 nValue = RangeDecodeFastWithUpdate(nTempK);
268 } else {
269 int nX1 = RangeDecodeFastWithUpdate(16);
270 int nX2 = RangeDecodeFastWithUpdate(nTempK - 16);
271 nValue = nX1 | (nX2 << 16);
272 }
273
274 // build the value and output it
275 nValue += (nOverflow << nTempK);
276 }
277
278 // update nKSum
279 BitArrayState.nKSum += ((nValue + 1) / 2)
280 - ((BitArrayState.nKSum + 16) >> 5);
281
282 // update k
283 if (BitArrayState.nKSum < K_SUM_MIN_BOUNDARY[BitArrayState.k])
284 BitArrayState.k--;
285 else if (BitArrayState.nKSum >= K_SUM_MIN_BOUNDARY[BitArrayState.k + 1])
286 BitArrayState.k++;
287
288 // output the value (converted to signed)
289 return (nValue & 1) ? (nValue >> 1) + 1 : -(nValue >> 1);
290 }
291
292
293 void
FlushState(UNBIT_ARRAY_STATE & BitArrayState)294 CUnBitArray::FlushState(UNBIT_ARRAY_STATE& BitArrayState)
295 {
296 BitArrayState.k = 10;
297 BitArrayState.nKSum = (1 << BitArrayState.k) * 16;
298 }
299
300 void
FlushBitArray()301 CUnBitArray::FlushBitArray()
302 {
303 AdvanceToByteBoundary();
304 m_nCurrentBitIndex += 8;
305 // ignore the first byte... (slows compression too much to not
306 // output this dummy byte)
307 m_RangeCoderInfo.buffer = GetC();
308 m_RangeCoderInfo.low = m_RangeCoderInfo.buffer >> (8 - EXTRA_BITS);
309 m_RangeCoderInfo.range = (unsigned int) 1 << EXTRA_BITS;
310
311 m_nRefillBitThreshold = (m_nBits - 512);
312 }
313
314
315 void
Finalize()316 CUnBitArray::Finalize()
317 {
318 // normalize
319 while (m_RangeCoderInfo.range <= BOTTOM_VALUE) {
320 m_nCurrentBitIndex += 8;
321 m_RangeCoderInfo.range <<= 8;
322 }
323
324 // used to back-pedal the last two bytes out
325 // this should never have been a problem because we've outputted and normalized beforehand
326 // but stopped doing it as of 3.96 in case it accounted for rare decompression failures
327 if (m_nVersion <= 3950)
328 m_nCurrentBitIndex -= 16;
329 }
330
331
332 void
GenerateArrayRange(int * pOutputArray,int nElements)333 CUnBitArray::GenerateArrayRange(int * pOutputArray, int nElements)
334 {
335 UNBIT_ARRAY_STATE BitArrayState;
336 FlushState(BitArrayState);
337 FlushBitArray();
338
339 for (int z = 0; z < nElements; z++)
340 pOutputArray[z] = DecodeValueRange(BitArrayState);
341
342 Finalize();
343 }
344