1#include <algorithm>
2
3#include "All.h"
4#include "APEInfo.h"
5#include "UnBitArray.h"
6#include "BitArray.h"
7
8
9const 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
14const 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
19const 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
27const 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
32const 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
40const 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
58CUnBitArray::CUnBitArray(CIO * pIO, int nVersion)
59{
60	CreateHelper(pIO, 16384, nVersion);
61	m_nFlushCounter = 0;
62	m_nFinalizeCounter = 0;
63}
64
65
66CUnBitArray::~CUnBitArray()
67{
68	SAFE_ARRAY_DELETE(m_pBitArray)
69}
70
71
72unsigned int
73CUnBitArray::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
88void
89CUnBitArray::GenerateArray(int * pOutputArray, int nElements,
90	int nBytesRequired)
91{
92	GenerateArrayRange(pOutputArray, nElements);
93}
94
95__inline unsigned char
96CUnBitArray::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
106CUnBitArray::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
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
144int
145CUnBitArray::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
293void
294CUnBitArray::FlushState(UNBIT_ARRAY_STATE& BitArrayState)
295{
296	BitArrayState.k = 10;
297	BitArrayState.nKSum = (1 << BitArrayState.k) * 16;
298}
299
300void
301CUnBitArray::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
315void
316CUnBitArray::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
332void
333CUnBitArray::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