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