text: #include <algorithm>
  
  #include "All.h"
  #include "APEInfo.h"
  #include "UnBitArray.h"
  #include "BitArray.h"
  
  
  const uint32 POWERS_OF_TWO_MINUS_ONE_REVERSED[33] = {4294967295u,2147483647u,
  	1073741823u,536870911u,268435455u,134217727u,67108863u,33554431u,16777215u,
  	8388607u,4194303u,2097151u,1048575u,524287u,262143u,131071u,65535u,32767u,
  	16383u,8191u,4095u,2047u,1023u,511u,255u,127u,63u,31u,15u,7u,3u,1u,0u};
  
  const uint32 K_SUM_MIN_BOUNDARY[32] = {0u,32u,64u,128u,256u,512u,1024u,2048u,
  	4096u,8192u,16384u,32768u,65536u,131072u,262144u,524288u,1048576u,2097152u,
  	4194304u,8388608u,16777216u,33554432u,67108864u,134217728u,268435456u,
  	536870912u,1073741824u,2147483648u,0u,0u,0u,0u};
  
  const uint32 RANGE_TOTAL_1[65] = {0u,14824u,28224u,39348u,47855u,53994u,58171u,
  	60926u,62682u,63786u,64463u,64878u,65126u,65276u,65365u,65419u,65450u,
  	65469u,65480u,65487u,65491u,65493u,65494u,65495u,65496u,65497u,65498u,
  	65499u,65500u,65501u,65502u,65503u,65504u,65505u,65506u,65507u,65508u,
  	65509u,65510u,65511u,65512u,65513u,65514u,65515u,65516u,65517u,65518u,
  	65519u,65520u,65521u,65522u,65523u,65524u,65525u,65526u,65527u,65528u,
  	65529u,65530u,65531u,65532u,65533u,65534u,65535u,65536u};
  
  const uint32 RANGE_WIDTH_1[64] = {14824u,13400u,11124u,8507u,6139u,4177u,2755u,
  	1756u,1104u,677u,415u,248u,150u,89u,54u,31u,19u,11u,7u,4u,2u,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,1u,1u,1u,1u,1u,
  	1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u};
  
  const uint32 RANGE_TOTAL_2[65] = {0u,19578u,36160u,48417u,56323u,60899u,63265u,
  	64435u,64971u,65232u,65351u,65416u,65447u,65466u,65476u,65482u,65485u,
  	65488u,65490u,65491u,65492u,65493u,65494u,65495u,65496u,65497u,65498u,
  	65499u,65500u,65501u,65502u,65503u,65504u,65505u,65506u,65507u,65508u,
  	65509u,65510u,65511u,65512u,65513u,65514u,65515u,65516u,65517u,65518u,
  	65519u,65520u,65521u,65522u,65523u,65524u,65525u,65526u,65527u,65528u,
  	65529u,65530u,65531u,65532u,65533u,65534u,65535u,65536u};
  
  const uint32 RANGE_WIDTH_2[64] = {19578u,16582u,12257u,7906u,4576u,2366u,1170u,
  	536u,261u,119u,65u,31u,19u,10u,6u,3u,3u,2u,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,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,1u,
  	1u,1u,1u,1u,1u,1u,1u,1u,1u,1u};
  
  
  #define RANGE_OVERFLOW_TOTAL_WIDTH	65536
  #define RANGE_OVERFLOW_SHIFT		16
  
  #define CODE_BITS 		32
  #define TOP_VALUE		((unsigned int ) 1 << (CODE_BITS - 1))
  #define SHIFT_BITS		(CODE_BITS - 9)
  #define EXTRA_BITS		((CODE_BITS - 2) % 8 + 1)
  #define BOTTOM_VALUE	(TOP_VALUE >> 8)
  
  #define MODEL_ELEMENTS	64
  
  
  CUnBitArray::CUnBitArray(CIO * pIO, int nVersion)
  {
  	CreateHelper(pIO, 16384, nVersion);
  	m_nFlushCounter = 0;
  	m_nFinalizeCounter = 0;
  }
  
  
  CUnBitArray::~CUnBitArray()
  {
  	SAFE_ARRAY_DELETE(m_pBitArray)
  }
  
  
  unsigned int
  CUnBitArray::DecodeValue(DECODE_VALUE_METHOD DecodeMethod, int nParam1,
  	int nParam2)
  {
  	switch (DecodeMethod) {
  		case DECODE_VALUE_METHOD_UNSIGNED_INT:
  			return DecodeValueXBits(32);
  		case DECODE_VALUE_METHOD_UNSIGNED_RICE:
  		case DECODE_VALUE_METHOD_X_BITS:
  			break;
  	}
  
  	return 0;
  }
  
  
  void
  CUnBitArray::GenerateArray(int * pOutputArray, int nElements,
  	int nBytesRequired)
  {
  	GenerateArrayRange(pOutputArray, nElements);
  }
  
  __inline unsigned char
  CUnBitArray::GetC()
  {
  	uchar nValue = static_cast<uchar>(m_pBitArray[m_nCurrentBitIndex >> 5]
  		>> (24 - (m_nCurrentBitIndex & 31)));
  	m_nCurrentBitIndex += 8;
  	return nValue;
  }
  
  
  __inline int
  CUnBitArray::RangeDecodeFast(int nShift)
  {
  	while (m_RangeCoderInfo.range <= BOTTOM_VALUE) {
  		m_RangeCoderInfo.buffer = (m_RangeCoderInfo.buffer << 8)
  			| ((m_pBitArray[m_nCurrentBitIndex >> 5]
  			>> (24 - (m_nCurrentBitIndex & 31))) & 0xFF);
  		m_nCurrentBitIndex += 8;
  		m_RangeCoderInfo.low = (m_RangeCoderInfo.low << 8)
  			| ((m_RangeCoderInfo.buffer >> 1) & 0xFF);
  		m_RangeCoderInfo.range <<= 8;
  	}
  
  	// decode
  	m_RangeCoderInfo.range = m_RangeCoderInfo.range >> nShift;
  	return m_RangeCoderInfo.low / m_RangeCoderInfo.range;
  }
  
  
  __inline int CUnBitArray::RangeDecodeFastWithUpdate(int nShift)
  {
  	while (m_RangeCoderInfo.range <= BOTTOM_VALUE) {
  		m_RangeCoderInfo.buffer = (m_RangeCoderInfo.buffer << 8)
  			| ((m_pBitArray[m_nCurrentBitIndex >> 5]
  			>> (24 - (m_nCurrentBitIndex & 31))) & 0xFF);
  		m_nCurrentBitIndex += 8;
  		m_RangeCoderInfo.low = (m_RangeCoderInfo.low << 8)
  			| ((m_RangeCoderInfo.buffer >> 1) & 0xFF);
  		m_RangeCoderInfo.range <<= 8;
  	}
  
  	// decode
  	m_RangeCoderInfo.range = m_RangeCoderInfo.range >> nShift;
  	int nRetVal = m_RangeCoderInfo.low / m_RangeCoderInfo.range;
  	m_RangeCoderInfo.low -= m_RangeCoderInfo.range * nRetVal;
  	return nRetVal;
  }
  
  
  int
  CUnBitArray::DecodeValueRange(UNBIT_ARRAY_STATE & BitArrayState)
  {
  	// make sure there is room for the data
  	// this is a little slower than ensuring a huge block to start with,
  	// but it's safer
  	if (m_nCurrentBitIndex > m_nRefillBitThreshold)
  		FillBitArray();
  
  	int nValue = 0;
  
  	if (m_nVersion >= 3990) {
  		// figure the pivot value
  		int nPivotValue = max(BitArrayState.nKSum / 32, 1UL);
  
  		// get the overflow
  		int nOverflow = 0;
  
  		// decode
  		uint32 nRangeTotal = RangeDecodeFast(RANGE_OVERFLOW_SHIFT);
  
  		// lookup the symbol (must be a faster way than this)
  		while (nRangeTotal >= RANGE_TOTAL_2[nOverflow + 1])
  			nOverflow++;
  
  		// update
  		m_RangeCoderInfo.low -= m_RangeCoderInfo.range
  			* RANGE_TOTAL_2[nOverflow];
  		m_RangeCoderInfo.range = m_RangeCoderInfo.range
  			* RANGE_WIDTH_2[nOverflow];
  
  		// get the working k
  		if (nOverflow == (MODEL_ELEMENTS - 1)) {
  			nOverflow = RangeDecodeFastWithUpdate(16);
  			nOverflow <<= 16;
  			nOverflow |= RangeDecodeFastWithUpdate(16);
  		}
  
  		// get the value
  		int nBase = 0;
  
  		if (nPivotValue >= (1 << 16)) {
  			int nPivotValueBits = 0;
  			while ((nPivotValue >> nPivotValueBits) > 0)
  				nPivotValueBits++;
  
  			int nSplitFactor = 1 << (nPivotValueBits - 16);
  			int nPivotValueA = (nPivotValue / nSplitFactor) + 1;
  			int nPivotValueB = nSplitFactor;
  
  			while (m_RangeCoderInfo.range <= BOTTOM_VALUE) {
  				m_RangeCoderInfo.buffer = (m_RangeCoderInfo.buffer << 8)
  					| ((m_pBitArray[m_nCurrentBitIndex >> 5]
  					>> (24 - (m_nCurrentBitIndex & 31))) & 0xFF);
  				m_nCurrentBitIndex += 8;
  				m_RangeCoderInfo.low = (m_RangeCoderInfo.low << 8)
  					| ((m_RangeCoderInfo.buffer >> 1) & 0xFF);
  				m_RangeCoderInfo.range <<= 8;
  			}
  			m_RangeCoderInfo.range = m_RangeCoderInfo.range / nPivotValueA;
  			int nBaseA = m_RangeCoderInfo.low / m_RangeCoderInfo.range;
  			m_RangeCoderInfo.low -= m_RangeCoderInfo.range * nBaseA;
  
  			while (m_RangeCoderInfo.range <= BOTTOM_VALUE) {
  				m_RangeCoderInfo.buffer = (m_RangeCoderInfo.buffer << 8)
  					| ((m_pBitArray[m_nCurrentBitIndex >> 5]
  					>> (24 - (m_nCurrentBitIndex & 31))) & 0xFF);
  				m_nCurrentBitIndex += 8;
  				m_RangeCoderInfo.low = (m_RangeCoderInfo.low << 8)
  					| ((m_RangeCoderInfo.buffer >> 1) & 0xFF);
  				m_RangeCoderInfo.range <<= 8;
  			}
  			m_RangeCoderInfo.range = m_RangeCoderInfo.range / nPivotValueB;
  			int nBaseB = m_RangeCoderInfo.low / m_RangeCoderInfo.range;
  			m_RangeCoderInfo.low -= m_RangeCoderInfo.range * nBaseB;
  
  			nBase = nBaseA * nSplitFactor + nBaseB;
  		} else {
  			while (m_RangeCoderInfo.range <= BOTTOM_VALUE) {
  				m_RangeCoderInfo.buffer = (m_RangeCoderInfo.buffer << 8)
  					| ((m_pBitArray[m_nCurrentBitIndex >> 5]
  					>> (24 - (m_nCurrentBitIndex & 31))) & 0xFF);
  				m_nCurrentBitIndex += 8;
  				m_RangeCoderInfo.low = (m_RangeCoderInfo.low << 8)
  					| ((m_RangeCoderInfo.buffer >> 1) & 0xFF);
  				m_RangeCoderInfo.range <<= 8;
  			}
  
  			// decode
  			m_RangeCoderInfo.range = m_RangeCoderInfo.range / nPivotValue;
  			int nBaseLower = m_RangeCoderInfo.low / m_RangeCoderInfo.range;
  			m_RangeCoderInfo.low -= m_RangeCoderInfo.range * nBaseLower;
  
  			nBase = nBaseLower;
  		}
  
  		// build the value
  		nValue = nBase + (nOverflow * nPivotValue);
  	} else {
  		// decode
  		uint32 nRangeTotal = RangeDecodeFast(RANGE_OVERFLOW_SHIFT);
  
  		// lookup the symbol (must be a faster way than this)
  		int nOverflow = 0;
  		while (nRangeTotal >= RANGE_TOTAL_1[nOverflow + 1])
  			nOverflow++;
  
  		// update
  		m_RangeCoderInfo.low -= m_RangeCoderInfo.range
  			* RANGE_TOTAL_1[nOverflow];
  		m_RangeCoderInfo.range = m_RangeCoderInfo.range
  			* RANGE_WIDTH_1[nOverflow];
  
  		// get the working k
  		int nTempK;
  		if (nOverflow == (MODEL_ELEMENTS - 1)) {
  			nTempK = RangeDecodeFastWithUpdate(5);
  			nOverflow = 0;
  		} else
  			nTempK = (BitArrayState.k < 1) ? 0 : BitArrayState.k - 1;
  
  		// figure the extra bits on the left and the left value
  		if (nTempK <= 16 || m_nVersion < 3910) {
  			nValue = RangeDecodeFastWithUpdate(nTempK);
  		} else {
  			int nX1 = RangeDecodeFastWithUpdate(16);
  			int nX2 = RangeDecodeFastWithUpdate(nTempK - 16);
  			nValue = nX1 | (nX2 << 16);
  		}
  
  		// build the value and output it
  		nValue += (nOverflow << nTempK);
  	}
  
  	// update nKSum
  	BitArrayState.nKSum += ((nValue + 1) / 2)
  		- ((BitArrayState.nKSum + 16) >> 5);
  
  	// update k
  	if (BitArrayState.nKSum < K_SUM_MIN_BOUNDARY[BitArrayState.k])
  		BitArrayState.k--;
  	else if (BitArrayState.nKSum >= K_SUM_MIN_BOUNDARY[BitArrayState.k + 1])
  		BitArrayState.k++;
  
  	// output the value (converted to signed)
  	return (nValue & 1) ? (nValue >> 1) + 1 : -(nValue >> 1);
  }
  
  
  void
  CUnBitArray::FlushState(UNBIT_ARRAY_STATE& BitArrayState)
  {
  	BitArrayState.k = 10;
  	BitArrayState.nKSum = (1 << BitArrayState.k) * 16;
  }
  
  void
  CUnBitArray::FlushBitArray()
  {
  	AdvanceToByteBoundary();
  	m_nCurrentBitIndex += 8;
  		// ignore the first byte... (slows compression too much to not
  		// output this dummy byte)
  	m_RangeCoderInfo.buffer = GetC();
  	m_RangeCoderInfo.low = m_RangeCoderInfo.buffer >> (8 - EXTRA_BITS);
  	m_RangeCoderInfo.range = (unsigned int) 1 << EXTRA_BITS;
  
  	m_nRefillBitThreshold = (m_nBits - 512);
  }
  
  
  void
  CUnBitArray::Finalize()
  {
  	// normalize
  	while (m_RangeCoderInfo.range <= BOTTOM_VALUE) {
  		m_nCurrentBitIndex += 8;
  		m_RangeCoderInfo.range <<= 8;
  	}
  
  	// used to back-pedal the last two bytes out
  	// this should never have been a problem because we've outputted and normalized beforehand
  	// but stopped doing it as of 3.96 in case it accounted for rare decompression failures
  	if (m_nVersion <= 3950)
  		m_nCurrentBitIndex -= 16;
  }
  
  
  void
  CUnBitArray::GenerateArrayRange(int * pOutputArray, int nElements)
  {
  	UNBIT_ARRAY_STATE BitArrayState;
  	FlushState(BitArrayState);
  	FlushBitArray();
  
  	for (int z = 0; z < nElements; z++)
  		pOutputArray[z] = DecodeValueRange(BitArrayState);
  
  	Finalize();
  }
  