1 #include "All.h"
2 #include "APEInfo.h"
3 #include "UnBitArray.h"
4 #include "BitArray.h"
5
6 namespace APE
7 {
8
9 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};
10
11 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};
12
13 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};
14 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};
15
16 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};
17 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,};
18
19 #define RANGE_OVERFLOW_TOTAL_WIDTH 65536
20 #define RANGE_OVERFLOW_SHIFT 16
21
22 #define CODE_BITS 32
23 #define TOP_VALUE ((unsigned int ) 1 << (CODE_BITS - 1))
24 #define SHIFT_BITS (CODE_BITS - 9)
25 #define EXTRA_BITS ((CODE_BITS - 2) % 8 + 1)
26 #define BOTTOM_VALUE (TOP_VALUE >> 8)
27
28 #define MODEL_ELEMENTS 64
29
30 /***********************************************************************************
31 Construction
32 ***********************************************************************************/
CUnBitArray(CIO * pIO,intn nVersion,intn nFurthestReadByte)33 CUnBitArray::CUnBitArray(CIO * pIO, intn nVersion, intn nFurthestReadByte) :
34 CUnBitArrayBase(nFurthestReadByte)
35 {
36 CreateHelper(pIO, 16384, nVersion);
37 m_nFlushCounter = 0;
38 m_nFinalizeCounter = 0;
39 }
40
~CUnBitArray()41 CUnBitArray::~CUnBitArray()
42 {
43 SAFE_ARRAY_DELETE(m_pBitArray)
44 }
45
DecodeValue(DECODE_VALUE_METHOD DecodeMethod,int nParam1,int nParam2)46 unsigned int CUnBitArray::DecodeValue(DECODE_VALUE_METHOD DecodeMethod, int nParam1, int nParam2)
47 {
48 switch (DecodeMethod)
49 {
50 case DECODE_VALUE_METHOD_UNSIGNED_INT:
51 return DecodeValueXBits(32);
52 }
53
54 return 0;
55 }
56
GenerateArray(int * pOutputArray,int nElements,intn nBytesRequired)57 void CUnBitArray::GenerateArray(int * pOutputArray, int nElements, intn nBytesRequired)
58 {
59 GenerateArrayRange(pOutputArray, nElements);
60 }
61
DecodeByte()62 inline uint32 CUnBitArray::DecodeByte()
63 {
64 EnsureBitsAvailable(8, true);
65
66 // read byte
67 uint32 nByte = ((m_pBitArray[m_nCurrentBitIndex >> 5] >> (24 - (m_nCurrentBitIndex & 31))) & 0xFF);
68 m_nCurrentBitIndex += 8;
69 return nByte;
70 }
71
RangeDecodeFast(int nShift)72 inline int CUnBitArray::RangeDecodeFast(int nShift)
73 {
74 while (m_RangeCoderInfo.range <= BOTTOM_VALUE)
75 {
76 m_RangeCoderInfo.buffer = (m_RangeCoderInfo.buffer << 8) | DecodeByte();
77 m_RangeCoderInfo.low = (m_RangeCoderInfo.low << 8) | ((m_RangeCoderInfo.buffer >> 1) & 0xFF);
78 m_RangeCoderInfo.range <<= 8;
79
80 // check for end of life
81 if (m_RangeCoderInfo.range == 0)
82 return 0;
83 }
84
85 // decode
86 m_RangeCoderInfo.range = m_RangeCoderInfo.range >> nShift;
87
88 return m_RangeCoderInfo.low / m_RangeCoderInfo.range;
89 }
90
RangeDecodeFastWithUpdate(int nShift)91 inline int CUnBitArray::RangeDecodeFastWithUpdate(int nShift)
92 {
93 // update range
94 while (m_RangeCoderInfo.range <= BOTTOM_VALUE)
95 {
96 // if the decoder's range falls to zero, it means the input bitstream is corrupt
97 if (m_RangeCoderInfo.range == 0)
98 {
99 ASSERT(false);
100 throw(1);
101 }
102
103 // read byte and update range
104 m_RangeCoderInfo.buffer = (m_RangeCoderInfo.buffer << 8) | DecodeByte();
105 m_RangeCoderInfo.low = (m_RangeCoderInfo.low << 8) | ((m_RangeCoderInfo.buffer >> 1) & 0xFF);
106 m_RangeCoderInfo.range <<= 8;
107 }
108
109 // decode
110 m_RangeCoderInfo.range = m_RangeCoderInfo.range >> nShift;
111 int nResult = m_RangeCoderInfo.low / m_RangeCoderInfo.range;
112 m_RangeCoderInfo.low -= m_RangeCoderInfo.range * nResult;
113 return nResult;
114 }
115
DecodeValueRange(UNBIT_ARRAY_STATE & BitArrayState)116 int CUnBitArray::DecodeValueRange(UNBIT_ARRAY_STATE & BitArrayState)
117 {
118 int nValue = 0;
119
120 if (m_nVersion >= 3990)
121 {
122 // figure the pivot value
123 int nPivotValue = ape_max(BitArrayState.nKSum / 32, (uint32)1);
124
125 // get the overflow
126 int nOverflow = 0;
127 {
128 // decode
129 int nRangeTotal = RangeDecodeFast(RANGE_OVERFLOW_SHIFT);
130
131 // lookup the symbol (must be a faster way than this)
132 while (nRangeTotal >= int(RANGE_TOTAL_2[nOverflow + 1])) { nOverflow++; }
133
134 // update
135 m_RangeCoderInfo.low -= m_RangeCoderInfo.range * RANGE_TOTAL_2[nOverflow];
136 m_RangeCoderInfo.range = m_RangeCoderInfo.range * RANGE_WIDTH_2[nOverflow];
137
138 // get the working k
139 if (nOverflow == (MODEL_ELEMENTS - 1))
140 {
141 nOverflow = RangeDecodeFastWithUpdate(16);
142 nOverflow <<= 16;
143 nOverflow |= RangeDecodeFastWithUpdate(16);
144 }
145 }
146
147 // get the value
148 int nBase = 0;
149 {
150 int nShift = 0;
151 if (nPivotValue >= (1 << 16))
152 {
153 int nPivotValueBits = 0;
154 while ((nPivotValue >> nPivotValueBits) > 0) { nPivotValueBits++; }
155 int nSplitFactor = 1 << (nPivotValueBits - 16);
156
157 int nPivotValueA = (nPivotValue / nSplitFactor) + 1;
158 int nPivotValueB = nSplitFactor;
159
160 while (m_RangeCoderInfo.range <= BOTTOM_VALUE)
161 {
162 m_RangeCoderInfo.buffer = (m_RangeCoderInfo.buffer << 8) | DecodeByte();
163 m_RangeCoderInfo.low = (m_RangeCoderInfo.low << 8) | ((m_RangeCoderInfo.buffer >> 1) & 0xFF);
164 m_RangeCoderInfo.range <<= 8;
165 }
166 m_RangeCoderInfo.range = m_RangeCoderInfo.range / nPivotValueA;
167 int nBaseA = m_RangeCoderInfo.low / m_RangeCoderInfo.range;
168 m_RangeCoderInfo.low -= m_RangeCoderInfo.range * nBaseA;
169
170 while (m_RangeCoderInfo.range <= BOTTOM_VALUE)
171 {
172 m_RangeCoderInfo.buffer = (m_RangeCoderInfo.buffer << 8) | DecodeByte();
173 m_RangeCoderInfo.low = (m_RangeCoderInfo.low << 8) | ((m_RangeCoderInfo.buffer >> 1) & 0xFF);
174 m_RangeCoderInfo.range <<= 8;
175 }
176 m_RangeCoderInfo.range = m_RangeCoderInfo.range / nPivotValueB;
177 int nBaseB = m_RangeCoderInfo.low / m_RangeCoderInfo.range;
178 m_RangeCoderInfo.low -= m_RangeCoderInfo.range * nBaseB;
179
180 nBase = nBaseA * nSplitFactor + nBaseB;
181 }
182 else
183 {
184 while (m_RangeCoderInfo.range <= BOTTOM_VALUE)
185 {
186 m_RangeCoderInfo.buffer = (m_RangeCoderInfo.buffer << 8) | DecodeByte();
187 m_RangeCoderInfo.low = (m_RangeCoderInfo.low << 8) | ((m_RangeCoderInfo.buffer >> 1) & 0xFF);
188 m_RangeCoderInfo.range <<= 8;
189
190 // check for end of life!
191 if (m_RangeCoderInfo.range == 0)
192 return 0;
193 }
194
195 // decode
196 m_RangeCoderInfo.range = m_RangeCoderInfo.range / nPivotValue;
197 int nBaseLower = m_RangeCoderInfo.low / m_RangeCoderInfo.range;
198 m_RangeCoderInfo.low -= m_RangeCoderInfo.range * nBaseLower;
199
200 nBase = nBaseLower;
201 }
202 }
203
204 // build the value
205 nValue = nBase + (nOverflow * nPivotValue);
206 }
207 else
208 {
209 // decode
210 int nRangeTotal = RangeDecodeFast(RANGE_OVERFLOW_SHIFT);
211
212 // lookup the symbol (must be a faster way than this)
213 int nOverflow = 0;
214 while (nRangeTotal >= int(RANGE_TOTAL_1[nOverflow + 1])) { nOverflow++; }
215
216 // update
217 m_RangeCoderInfo.low -= m_RangeCoderInfo.range * RANGE_TOTAL_1[nOverflow];
218 m_RangeCoderInfo.range = m_RangeCoderInfo.range * RANGE_WIDTH_1[nOverflow];
219
220 // get the working k
221 int nTempK;
222 if (nOverflow == (MODEL_ELEMENTS - 1))
223 {
224 nTempK = RangeDecodeFastWithUpdate(5);
225 nOverflow = 0;
226 }
227 else
228 {
229 nTempK = (BitArrayState.k < 1) ? 0 : BitArrayState.k - 1;
230 }
231
232 // figure the extra bits on the left and the left value
233 if (nTempK <= 16 || m_nVersion < 3910)
234 {
235 nValue = RangeDecodeFastWithUpdate(nTempK);
236 }
237 else
238 {
239 int nX1 = RangeDecodeFastWithUpdate(16);
240 int nX2 = RangeDecodeFastWithUpdate(nTempK - 16);
241 nValue = nX1 | (nX2 << 16);
242 }
243
244 // build the value and output it
245 nValue += (nOverflow << nTempK);
246 }
247
248 // update nKSum
249 BitArrayState.nKSum += ((nValue + 1) / 2) - ((BitArrayState.nKSum + 16) >> 5);
250
251 // update k
252 if (BitArrayState.nKSum < K_SUM_MIN_BOUNDARY[BitArrayState.k])
253 BitArrayState.k--;
254 else if (BitArrayState.nKSum >= K_SUM_MIN_BOUNDARY[BitArrayState.k + 1])
255 BitArrayState.k++;
256
257 // output the value (converted to signed)
258 return (nValue & 1) ? (nValue >> 1) + 1 : -(nValue >> 1);
259 }
260
FlushState(UNBIT_ARRAY_STATE & BitArrayState)261 void CUnBitArray::FlushState(UNBIT_ARRAY_STATE & BitArrayState)
262 {
263 BitArrayState.k = 10;
264 BitArrayState.nKSum = (1 << BitArrayState.k) * 16;
265 }
266
FlushBitArray()267 void CUnBitArray::FlushBitArray()
268 {
269 AdvanceToByteBoundary();
270 DecodeValueXBits(8); // ignore the first byte... (slows compression too much to not output this dummy byte)
271 m_RangeCoderInfo.buffer = DecodeValueXBits(8);
272 m_RangeCoderInfo.low = m_RangeCoderInfo.buffer >> (8 - EXTRA_BITS);
273 m_RangeCoderInfo.range = (unsigned int) 1 << EXTRA_BITS;
274 }
275
Finalize()276 void CUnBitArray::Finalize()
277 {
278 // normalize
279 while (m_RangeCoderInfo.range <= BOTTOM_VALUE)
280 {
281 m_nCurrentBitIndex += 8;
282 m_RangeCoderInfo.range <<= 8;
283 if (m_RangeCoderInfo.range == 0)
284 return; // end of life!
285 }
286
287 // used to back-pedal the last two bytes out
288 // this should never have been a problem because we've outputted and normalized beforehand
289 // but stopped doing it as of 3.96 in case it accounted for rare decompression failures
290 if (m_nVersion <= 3950)
291 m_nCurrentBitIndex -= 16;
292 }
293
GenerateArrayRange(int * pOutputArray,int nElements)294 void CUnBitArray::GenerateArrayRange(int * pOutputArray, int nElements)
295 {
296 UNBIT_ARRAY_STATE BitArrayState;
297 FlushState(BitArrayState);
298 FlushBitArray();
299
300 for (int z = 0; z < nElements; z++)
301 {
302 pOutputArray[z] = DecodeValueRange(BitArrayState);
303 }
304
305 Finalize();
306 }
307
308 }
309