haiku.git

#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();
}