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