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