fmi.cpp

自适应算术编码。这个项目假设读者已经了解基本的算术压缩编码的概念。

#include "fmi.h"

void CFreqModIncr::Initialize(DWORD dwTotal)
{
	m_pdwTable = new DWORD [m_dwTotal = dwTotal];

	for (DWORD dwIndex = 0; dwIndex < dwTotal; dwIndex++)
		m_pdwTable[dwIndex] = 0;

	AdjustFrequencies();
}

void CFreqModIncr::Uninitialize()
{
	delete [] m_pdwTable;
	m_pdwTable = NULL;
}

void CFreqModIncr::PassByIndex(
	DWORD dwIndex,
	DWORD &rdwLeftBound,
	DWORD &rdwRightBound)
{
	DWORD dwAddend = m_dwStartAddend;
	DWORD dwBaseIndex = 0;

	rdwLeftBound = 0;
	rdwRightBound = m_pdwTable[0];

	for (; dwAddend; dwAddend >>= 1)
	{
		DWORD dwMidIndex = dwBaseIndex + dwAddend;
		DWORD dwMidBound = rdwLeftBound + m_pdwTable[dwMidIndex];

		if (dwMidIndex <= dwIndex)
		{
			rdwRightBound = dwMidBound;
			m_pdwTable[dwMidIndex] += m_dwIncrement;
		}
		else if (dwMidIndex < m_dwTotal)
		{
			rdwLeftBound = dwMidBound;
			dwBaseIndex = dwMidIndex;
		}
	}

	if ((m_pdwTable[0] += m_dwIncrement) >= FMI_OVERFLOW_LIMIT)
		ReduceByHalf();
}

DWORD CFreqModIncr::PassByPoint(
	DWORD dwPoint,
	DWORD &rdwLeftBound,
	DWORD &rdwRightBound)
{
	DWORD dwAddend = m_dwStartAddend;
	DWORD dwIndex = 0;

	rdwLeftBound = 0;
	rdwRightBound = m_pdwTable[0];

	for (; dwAddend; dwAddend >>= 1)
	{
		DWORD dwMidIndex = dwIndex + dwAddend;
		DWORD dwMidBound = rdwLeftBound + m_pdwTable[dwMidIndex];

		if (dwMidBound <= dwPoint)
		{
			rdwRightBound = dwMidBound;
			m_pdwTable[dwMidIndex] += m_dwIncrement;
		}
		else if (dwMidIndex < m_dwTotal)
		{
			rdwLeftBound = dwMidBound;
			dwIndex = dwMidIndex;
		}
	}

	if ((m_pdwTable[0] += m_dwIncrement) >= FMI_OVERFLOW_LIMIT)
		ReduceByHalf();

	return dwIndex;
}

//	Private (internal) functionality

void CFreqModIncr::AdjustFrequencies()
{
	DWORD dwValue = 1, dwAddend = 2;

	m_pdwTable[0] += m_dwTotal;

	for (; dwValue < m_dwTotal; dwAddend = (dwValue = dwAddend) << 1)
		for (DWORD dwIndex = dwValue; dwIndex < m_dwTotal; dwIndex += dwAddend)
			m_pdwTable[dwIndex] += dwValue;

	m_dwStartAddend = dwValue >> 1;
}

void CFreqModIncr::ReduceByHalf()
{
	AdjustFrequencies();

	for (DWORD dwIndex = 0; dwIndex < m_dwTotal; dwIndex++)
		m_pdwTable[dwIndex] >>= 1;
}