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