adaarithcoder.cpp

自适应算术编码的实现

//  AdaArithCoder.cpp :  自适应算术编码器和解码器的类实现
// 
//  Author:    Shen Hongwei
//  Date:      Nov.10, 2005
//  Location:  Beijing, China
// 

#include "StdAfx.h"
#include ".\adaarithcoder.h"

AdaArithCoder::AdaArithCoder(void)
{
}

AdaArithCoder::~AdaArithCoder(void)
{
}

// AdaArithCoder初始化函数
// 参数：
//    BitIO * bit_in:    输入bit流
//    BitIO * bit_out:   输出bit流
// 返回值
//    void
void AdaArithCoder::Init(BitIO * bit_in, BitIO * bit_out)
{	
	Coder::Init(bit_in, bit_out);

	L = 0;
	U = TOP_VALUE;

	TotalCount = 0;
	CumCount[0] = 0;
	for (int i =1; i < tbSize+1; i++) {  // 初始状态为等概率
		TotalCount += 1;
        CumCount[i] = TotalCount;
	}
}

// AdaArithCoder初始化函数
// 参数：
//    BitIO * bit_in:    输入bit流
//    BitIO * bit_out:   输出bit流
//    unsigned long i_leng:  输入文件的长度， by bits
// 返回值:  void
void AdaArithCoder::Init(BitIO * in, BitIO * out, unsigned long i_leng) 
{
	this->Init(in, out);
	this->in_leng = i_leng;
}

// 使用自适应算术编码对输入bit流编码，并写到输出bit流中，直至输入bit流结束
// 参数：   void
// 返回值： int
//      1,  正常结束
//    其他，出错（尚未考虑）
int  AdaArithCoder::Run(void)
{
	unsigned char  symbol;
	unsigned long  count = 0;
	int   Scale3 = 0;
	char  b;
	char  c;

	while (this->bit_reader->ReadAByte(c))
	{
		assert(L<=U);
		memcpy(&symbol, &c, 1);
		count++; 

		TagType oldL=L, oldU=U;
		L = oldL + ((oldU-oldL+1U) * (unsigned long)CumCount[symbol]) / TotalCount;
		U = oldL + ((oldU-oldL+1U) * (unsigned long)CumCount[symbol+1]) / TotalCount - 1U;

		if (count + 1 > this->in_leng)  // 处理被压缩数据的最后一个字符
		{
			b = MSB(L);
			bit_writer->Write(&b, 1);
		    int  Scale3Save = Scale3;
			while(Scale3 > 0)
			{
				char complement = ~b;
				bit_writer->Write(&complement, 1);
				Scale3--;
			}

			for (int i = Scale3 + 1; i<8*this->tagSize; i++)
			{
				L<<=1;
				b = MSB(L);
			    bit_writer->Write(&b, 1);
			}

			b = 0;
			for (int i = 0; i< Scale3Save; i++)
			    bit_writer->Write(&b, 1);

			this->bit_writer->FlushEnd();

			return(1);
		}

		b = MSB(L);
		bool e3flag = this->CheckE3();
		while( MSB(U) == b || e3flag)
		{
			if( !e3flag) {
				bit_writer->Write(&b, 1);
				L <<= 1;
				L &= AND_LSB_MASK;
				U <<= 1;
				U |= LSB_MASK;

				while(Scale3 > 0)
				{
					char complement = ~b;
					bit_writer->Write(&complement, 1);
					Scale3--;
				}
			} else {   // E3 condition holds
				L <<= 1;
				L &= AND_LSB_MASK;
				U <<= 1;
				U |= LSB_MASK;
				L ^= MSB_MASK;
				U ^= MSB_MASK;
				Scale3++;
			}

            b = MSB(L);
			e3flag = this->CheckE3();
		}

		this->Count(symbol);
	}

	this->bit_writer->FlushEnd();

	return (1);
}

// 统计各个字符出现的次数
void AdaArithCoder::Count(unsigned char c)   
{
	if (this->TotalCount >= TOP_VALUE>>2) {
		TotalCount >>= 1;
		for (int i=0; i< this->tbSize+1; i++)
			this->CumCount[i] >>= 1;
	}

	TotalCount ++;
	for (int i=c+1; i<this->tbSize+1; i++)
		this->CumCount[i] ++;

	unsigned long adjust = 0;
	for (int i=1; i< this->tbSize+1; i++) {
		if (this->CumCount[i] <= this->CumCount[i-1])
			adjust++;
		this->CumCount[i] += adjust;
	}

	TotalCount += adjust;
}

// Dummy function for the time being
bool AdaArithCoder::GenNextCode()
{
	return true;
}

// Dummy function for the time being
void AdaArithCoder::SetDebugMode(int mode)
{
	;
}

AdaArithDecoder::AdaArithDecoder(void)
{
}

AdaArithDecoder::~AdaArithDecoder(void)
{
}

// AdaArithDecoder初始化函数
// 参数：
//    BitIO * bit_in:    输入bit流
//    BitIO * bit_out:   输出bit流
// 返回值
//    void
void AdaArithDecoder::Init(BitIO * bit_in, BitIO * bit_out)
{	
	Coder::Init(bit_in, bit_out);

	L = 0;
	U = TOP_VALUE;
	TotalCount = 0;
	CumCount[0] = 0;
	for (int i =1; i < tbSize+1; i++) {  // 初始状态为等概率
		TotalCount += 1;
        CumCount[i] = TotalCount;
	}
}

// AdaArithDecoder初始化函数
// 参数：
//    BitIO * bit_in:    输入bit流
//    BitIO * bit_out:   输出bit流
//    unsigned long i_leng:  输入文件的长度， by bits
// 返回值:  void
void AdaArithDecoder::Init(BitIO * in, BitIO * out, unsigned long i_leng) 
{
	this->Init(in, out);
	this->in_leng = i_leng;  // in_leng是数据未被压缩时的长度，by bytes
}

bool AdaArithDecoder::ReadATag(TagType & tag)
{
	char c[sizeof(tag)];

	for (int i=sizeof(tag)-1; i>=0; i--) 
	{
    	if (bit_reader->ReadAInversedByte(c[i]) == false)
		    return false;
	}

	memcpy(&tag, c, sizeof(tag));

	return true;
}

// 使用自适应算术编码对输入bit流解码，并写到输出bit流中，直至输入bit流结束
// 参数：   void
// 返回值： int
//      1,  正常结束
//    其他，出错（尚未考虑）
int  AdaArithDecoder::Run(void)
{
	char symbol;
	int  Scale3 = 0;
	unsigned long count = 0;

	TagType tag;
	if (this->ReadATag(tag) == false)
		return -1;

	while (1)
	{
		int k=0;
		TagType tag_count;
		tag_count = ((tag - L + 1U)*(unsigned long)(TotalCount) - 1U)/(unsigned long)((U-L+1U));
		assert(tag_count <= TotalCount);

		while ( tag_count >= CumCount[k])
			k++;

		k--;

		assert(k<=255&&k>=0);

		unsigned char x = k;
		char value = x;
		// this->CompareWithOriginal(&value); // for debug
		this->bit_writer->Write((char*)&x, 8);
		count++;
		if (count == this->in_leng)
		{	
			this->bit_writer->FlushEnd();
			return(1);
		}

		TagType oldL=L, oldU=U;
		L = (TagType)(oldL + ((oldU-oldL+1U)* (unsigned long)CumCount[x]) / TotalCount);
		U = (TagType) (oldL + ((oldU-oldL+1U)* (unsigned long)CumCount[x+1]) / TotalCount - 1U);
		
		this->Count(x);

		char b = MSB(L);
		bool e3flag = this->CheckE3();
		while( b == MSB(U) || e3flag)
		{
			if( !e3flag) {
				L <<= 1;
				L &= AND_LSB_MASK;
				U <<= 1;
				U |= LSB_MASK;
				tag <<= 1;
				if (this->bit_reader->ReadABit((char*)&tag,0) == -1 )
					return 0;
			} else {   // E3 condition holds
				L <<= 1;
				L &= AND_LSB_MASK;
				U <<= 1;
				U |= LSB_MASK;
				tag <<= 1;
				if (this->bit_reader->ReadABit((char*)&tag,0) == -1 )
					return 0;
				L ^= MSB_MASK;
				U ^= MSB_MASK;
				tag ^= MSB_MASK;
			}

            b = MSB(L);
			e3flag = this->CheckE3();
		}
	}

	this->bit_writer->FlushEnd();

	return (1);
}

// 统计各个字符出现的次数
void AdaArithDecoder::Count(unsigned char c)   
{
	if (this->TotalCount >= TOP_VALUE>>2) {
		TotalCount >>= 1;
		for (int i=0; i< this->tbSize+1; i++)
			this->CumCount[i] >>= 1;
	}

	TotalCount ++;
	for (int i=c+1; i<this->tbSize+1; i++)
		this->CumCount[i] ++;

	unsigned long adjust = 0;
	for (int i=1; i< this->tbSize+1; i++) {
		if (this->CumCount[i] <= this->CumCount[i-1])
			adjust++;
		this->CumCount[i] += adjust;
	}

	TotalCount += adjust;
}

void AdaArithDecoder::CompareWithOriginal(char * value)  // for debug
{
	static flag=0;
	static fstream fs_in;	
	static long count = 1;

	if (!flag) {
    	fs_in.open("e:\\tmp\\05.mpga", ios_base::in | ios_base::binary);    // becomes "r" (open existing file for reading)
		flag = 1;
	}

	count++;
	char c;
	fs_in.get(c);
	// shw add for debug
	if (value[0] != c) {
		printf("!!! count = %d\n", count);
		getchar();
		exit(0);
	}
	assert(value[0]==c);
}

// Dummy function for the time being
bool AdaArithDecoder::GenNextCode()
{
	return true;
}

// Dummy function for the time being
void AdaArithDecoder::SetDebugMode(int mode)
{
	;
}