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