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