arithmatic.cpp

一个国人自己实现图像库的程序（有参考价值）

/* 次序O的静态算术编码 */

//===================================================================

// 1 . 统计0x00--0xFF每个字符出现的个数并转化成上下限值
//	   X的上下限为Limit[X]---Limit[X+1]
//	   Limit[257] 存放数据总长
void  fooCount (BYTE * DataBuffer, DWORD  BufferLen,
				DWORD  Limit[258]) ;

//===================================================================

// 2 . 0次序算术压缩
void  fooArithCompress (BYTE  * InBuffer , DWORD InBufLen,
						BYTE  * OutBuffer, DWORD Limit[258],
						DWORD * ByteWrite,
						BYTE  * BitWrite ) ;

//===================================================================

//===================================================================

// 1 . 统计0x00--0xFF每个字符出现的个数并转化成上下限值
//	   X的上下限为Limit[X]---Limit[X+1]
//	   Limit[257] 存放数据总长
void  fooCount (BYTE * DataBuffer, DWORD  BufferLen,
				DWORD  Limit[258])
{
	DWORD	Array[256], count ;
	
	ZeroMemory (Array, sizeof (DWORD) * 256) ;
	for (count = 0 ; count < BufferLen ; count++)
		Array[DataBuffer[count]]++ ;

	Limit[0] = 0 ;
	for (count = 0 ; count < 256 ; count++) 
		Limit[count + 1] = Limit[count] + Array[count] ;
	Limit[257] = BufferLen ;
}

//===================================================================

// 2 . 0-次序算术压缩
void  fooArithCompress (BYTE  * InBuffer , DWORD InBufLen,
						BYTE  * OutBuffer, DWORD Limit[258],
						DWORD * ByteWrite,
						BYTE  * BitWrite )
{
	WORD	low  = 0,
			high = 0xFFFF ;
	WORD	underflow_bits = 0 ;	// 下溢位
	DWORD	range, count ;
	BYTE	data ;
	DWORD	byte = 0 ; // Write byte pointer
	BYTE	bit  = 0 ; // Write bit  pointer

	for (count = 0 ; count < InBufLen ; count++)
	{
		data = InBuffer[count] ;
		
		// Update high and low limit
		range = (DWORD)(high - low) + 1 ;
		high  = low + (WORD) ((range * Limit[data+1]) / Limit[257] - 1) ;
		low   = low + (WORD) ((range * Limit[data  ]) / Limit[257]) ;

		// 循环直到
		while (true)
		{
			// 最高位相等, 输出
			if ( (high & 0x8000) == (low & 0x8000) )
			{
				if (high & 0x8000)
					fooSetBit (&OutBuffer[byte], 7-bit) ;
				bit++ ;
				if (bit == 8)
				{
					bit = 0 ;
					byte++ ;
				}
				while (underflow_bits > 0)
				{
					if (~high & 0x8000)
						fooSetBit (&OutBuffer[byte], 7-bit) ;
					bit++ ;
					if (bit == 8)
					{
						bit = 0 ;
						byte++ ;
					}
					underflow_bits-- ;
				}
			}
			// 若上限次高为0, 并且下限次高为1, 则有下溢危险
			else if ( (low & 0x4000) && !(high & 0x4000) )
			{
				underflow_bits++ ;
				low  &= 0x3FFF ;
				high |= 0x4000 ;
			}
			// 稳定, 循环结束, 读下一字符
			else
				break ; // Jump out while

			low  <<= 1 ;
			high <<= 1 ;
			high  |= 1 ;
		} // end of while
	} // end of for

		// 结束工作
/*	    output_bit( stream, low & 0x4000 );
    underflow_bits++;
    while ( underflow_bits-- > 0 )
        output_bit( stream, ~low & 0x4000 );
	fooSetBit (&OutBuffer[byte], 7-bit) ;
					bit++ ;
					if (bit == 8)
					{
						bit = 0 ;
						byte++ ;
					}
					underflow_bits-- ; */

	if (ByteWrite != NULL)
		*ByteWrite = byte ;
	if (BitWrite  != NULL)
		*BitWrite  = bit ;
}

//===================================================================

// 3 . 0次序算术解压缩
void  fooArithDecode (BYTE  * InBuffer , DWORD InBufLen,
					  BYTE  * OutBuffer, DWORD Limit[258],
					  DWORD * ByteWrite)
{
	DWORD	count, range ;
	DWORD	WriteP = 0 ; // OutBuffer Write pointer
	BYTE	data ;
	WORD	code = 0, low, high ;
	DWORD	byte = 0 ; // InBuffer byte pointer
	BYTE	bit  = 0 ; // InBuffer bit  pointer

		// Init , Read first 16-bits from InBuffer
	for (count = 0 ; count < 16 ; count++)
	{
		code <<= 1 ;
		code  += (WORD) fooTestBit (InBuffer[byte], 7 - bit) ;
		bit++ ;
		if (bit == 8)
		{
			bit = 0 ;
			byte++ ;
		}
	}
	low  = 0 ;
	high = 0xFFFF ; // End of Init

	// Decode
	while (true)
	{
		if (byte >= InBufLen)
			break ;
		range = (DWORD)(high - low) + 1 ;
		count  = (WORD)((((DWORD)(code-low) + 1) * Limit[257] - 1) / range) ;
		for (data = 255 ; count < Limit[data] ; data--) 
			;
		
		// Remove code
		range = (DWORD)(high - low) + 1 ;
		high  = low + (WORD) ((range * Limit[data+1]) / Limit[257] - 1) ;
		low   = low + (WORD) ((range * Limit[data  ]) / Limit[257]) ;

		// 循环直到
		while (true)
		{
				// 最高位相等, 输出
			if ( (high & 0x8000) == (low & 0x8000) ) {}
			else if ((low & 0x4000) == 0x4000  && (high & 0x4000) == 0 )
			{
				code ^= 0x4000;
				low   &= 0x3fff;
				high  |= 0x4000;
			}
			else
				return;
			
			low <<= 1;
			high <<= 1;
			high |= 1;
			code <<= 1;
			code += (WORD) fooTestBit (InBuffer[byte], 7 - bit) ;
			bit++ ;
			if (bit == 8)
			{
				bit = 0 ;
				byte++ ;
			}
		} // end of while

		OutBuffer[WriteP++] = data ;

	} // end of for
	if (ByteWrite != NULL)
		*ByteWrite = WriteP ;
}