aricacm.c

EZW算法的编码与解码的实现,使用vc++实现!

/*----------------------------------------------------------------------------*/
/*----------------------------------------------------------------------------*/	
void BasicCoderSetNSymbols(BasicCoder *coder, int nSymbols, int MaxCount)
{
	if (coder->context != NULL){
		ContextDealloc(coder->context);
	}

	coder->nSymbols = nSymbols;
	coder->context= ContextAlloc();
	ContextInitialize(coder->context, nSymbols, MaxCount, 1);
	coder->EndOfStreamSymbol = coder->context->nSymbols-1;
	return;
}

/*----------------------------------------------------------------------------*/
/*----------------------------------------------------------------------------*/	
int BasicCoderDecode(BasicCoder *coder, ArithDecoder *decoder, Boolean update)
{
	int target, symbol;
	
	decoder->range = decoder->high - decoder->low + 1;

	target = ((int)(decoder->value-decoder->low+1)*coder->context->TotalFreq-1)
							/(decoder->range);
		
   symbol = ContextGetSymbol(coder->context, target);
	
	ArithDecoderDecode(decoder, ContextGetCumul(coder->context, symbol-1),
		ContextGetCumul(coder->context, symbol), coder->context->TotalFreq);

	if (update){
		ContextUpdate(coder->context, 1, symbol);
	}

	return symbol;
}

/*----------------------------------------------------------------------------*/
/*----------------------------------------------------------------------------*/	
double BasicCoderGetCost(BasicCoder *coder, int symbol, Boolean update)
{
	double bits;

	bits = ContextGetCost(coder->context, symbol);
	
	if (update){
		ContextUpdate(coder->context, 1, symbol);
	}
	return bits;
}

/*----------------------------------------------------------------------------*/
/*----------------------------------------------------------------------------*/	
void BasicCoderReset(BasicCoder *coder)
{
	ContextInitialize(coder->context, coder->nSymbols, 
				coder->context->MaxCount, 1); 
}

/*----------------------------------------------------------------------------*/
/*----------------------------------------------------------------------------*/	
void BasicCoderWriteNBits(ArithEncoder *encoder, int val, int nbits)
{
	int count, countLeft, countTotal;
	int temp;
	
	while (nbits>8){
		temp = val & 0x0ff;
		
		encoder->range = encoder->high - encoder->low + 1;
		count = temp+1;
		countLeft = temp;
		countTotal = 256;
		ArithEncoderEncode(encoder, countLeft, count, countTotal);
		nbits -= 8;
		val >>= 8;		
	}

	temp = val & ((1<<nbits)-1);
	encoder->range = encoder->high - encoder->low + 1;
	count = temp+1;
	countLeft = temp;
	countTotal = 1<<nbits;
	ArithEncoderEncode(encoder, countLeft, count, countTotal);
		
}

/*----------------------------------------------------------------------------*/
/*----------------------------------------------------------------------------*/	
int BasicCoderReadNBits(ArithDecoder *decoder, int nbits)
{
	int count, countLeft, countTotal;
	int i=0, target, symbol=0;

	while(nbits>8){
 		decoder->range = decoder->high - decoder->low + 1;
		countTotal = 256;
		target = ((int)(decoder->value-decoder->low+1)*countTotal-1)
							/(decoder->range);
		
		count = target+1;
		countLeft = target;
		ArithDecoderDecode(decoder, countLeft, count, countTotal);
		
		symbol += countLeft<<(i*8);
		i++;		
		nbits -=8;
	}
	
	decoder->range = decoder->high - decoder->low + 1;
	countTotal = 1<<nbits;

	target = ((int)(decoder->value-decoder->low+1)*countTotal-1)
						/(decoder->range);
		
	count = target+1;
	countLeft = target;
	ArithDecoderDecode(decoder, countLeft, count, countTotal);
	symbol += countLeft<<(i*8);

	return symbol;
}

/*----------------------------------------------------------------------------*/
/*----------------------------------------------------------------------------*/	
/* BasicEsacpeCoder - from G.Davis code */
/*----------------------------------------------------------------------------*/
/*----------------------------------------------------------------------------*/	
BasicEscapeCoder *BasicEscapeCoderAlloc(int nSymbols, int MaxCount, 
													 int EscapeDecreamentStart, int Thres)
{
	BasicEscapeCoder *coder;
	int i;

	if ((coder=(BasicEscapeCoder *)malloc(sizeof(BasicEscapeCoder)))==NULL){
		return NULL;
	}
	
	/* does not count the escape code */
	coder->nSymbols = nSymbols;
	coder->context = ContextAlloc();	
	coder->escape = ContextAlloc();

	/* include the escape code */
	ContextInitialize(coder->context, nSymbols+1, MaxCount, 0);
	/* only the escape code has some initial count */
	ContextUpdate(coder->context, nSymbols+1, nSymbols);
	/* every symbol in the escape context has a count of 1 */
	ContextInitialize(coder->escape, nSymbols, MaxCount, 1);

	/* novel symbol array to keep track the seen symbols */
	coder->NovelSymbol = (char *)malloc(coder->nSymbols*sizeof(char));
	if (coder->NovelSymbol == NULL){
		CoderError("Fail to allocate novel symbol array.\n");
	}

	for (i=0; i<coder->nSymbols;i++){
		coder->NovelSymbol[i] = 0;
	}

	/* in case it is used */
	coder->EndOfStreamSymbol = coder->context->nSymbols-2;
	/* escape code is the last symbol */
	coder->EscapeSymbol = coder->context->nSymbols-1;

	coder->EscapeDecreamentStart = EscapeDecreamentStart;
	coder->EscapeDecreament = EscapeDecreamentStart;
	coder->nNovelSymbols = coder->nSymbols;
	coder->Thres = Thres;

	return coder;
}

/*----------------------------------------------------------------------------*/
/*----------------------------------------------------------------------------*/	
void BasicEscapeCoderDealloc(BasicEscapeCoder *coder)
{
	if (coder != NULL){
		ContextDealloc(coder->context);
		ContextDealloc(coder->escape);
		free(coder->NovelSymbol);
		free(coder);
	}
}

/*----------------------------------------------------------------------------*/
/*----------------------------------------------------------------------------*/	
double BasicEscapeCoderEncode(BasicEscapeCoder *coder, ArithEncoder *encoder, 
										int symbol, Boolean update)
{
	double bitsEsc=0, bitsSym=0;

	if (encoder!=NULL){

		encoder->range = encoder->high - encoder->low + 1;
		
		if (coder->NovelSymbol[symbol]==1){
			/* seen symbol */
			bitsSym = ContextGetCost(coder->context, symbol);
						
			ArithEncoderEncode(encoder, ContextGetCumul(coder->context, symbol-1),
				ContextGetCumul(coder->context, symbol), coder->context->TotalFreq);
			
			if(update){
				ContextUpdate(coder->context, 1, symbol);
			}
		}
		else{
			/* novel symbol - send escape code */
			bitsEsc = ContextGetCost(coder->context, coder->EscapeSymbol);

			ArithEncoderEncode(encoder, ContextGetCumul(coder->context, 
				coder->EscapeSymbol-1), ContextGetCumul(coder->context, 
				coder->EscapeSymbol), coder->context->TotalFreq);

			encoder->range = encoder->high - encoder->low + 1;
			
			/* send symbol using escape context */
			bitsSym = ContextGetCost(coder->context, symbol);

			ArithEncoderEncode(encoder, ContextGetCumul(coder->escape, symbol-1), 
			ContextGetCumul(coder->escape, symbol), coder->escape->TotalFreq);

			if (update){
				/* head start for new symbol */
				ContextUpdate(coder->context, 1, symbol);

				if(ContextGetProb(coder->context, coder->EscapeSymbol) > 
					coder->EscapeDecreament){
					ContextUpdate(coder->context, -coder->EscapeDecreament, 
						coder->EscapeSymbol);
					
					if (coder->EscapeDecreament < coder->Thres){
						coder->EscapeDecreament++;
					}
				}
				/* remove the symbol from the escape context */
				ContextUpdate(coder->escape, -1, symbol);
				coder->NovelSymbol[symbol] = 1;
				coder->nNovelSymbols--;
			}
		}
	}
	return (bitsEsc+bitsSym);
}

/*----------------------------------------------------------------------------*/	
/*----------------------------------------------------------------------------*/	
int BasicEscapeCoderDecode(BasicEscapeCoder *coder, ArithDecoder *decoder, 
									Boolean update)
{
	int target, symbol;

	decoder->range = decoder->high - decoder->low + 1;

	target = ((int)(decoder->value-decoder->low+1)*coder->context->TotalFreq - 1)
							/(decoder->range);

	symbol = ContextGetSymbol(coder->context, target);

	ArithDecoderDecode(decoder, ContextGetCumul(coder->context, symbol-1),
		ContextGetCumul(coder->context, symbol), coder->context->TotalFreq);

	if (symbol == coder->EscapeSymbol){
		/* escape code */
		decoder->range = decoder->high - decoder->low + 1;

		target = ((int)(decoder->value-decoder->low+1)*coder->escape->TotalFreq - 1)
								/(decoder->range);

		symbol = ContextGetSymbol(coder->escape, target);
		
		ArithDecoderDecode(decoder, ContextGetCumul(coder->escape, symbol-1),
			ContextGetCumul(coder->escape, symbol), coder->escape->TotalFreq);

		if (update){
			
			ContextUpdate(coder->context, 1, symbol);
			
			if (ContextGetProb(coder->context, coder->EscapeSymbol) > 
				coder->EscapeDecreament){
				ContextUpdate(coder->context, -coder->EscapeDecreament, 
					coder->EscapeSymbol);
				if (coder->EscapeDecreament < coder->Thres){
					coder->EscapeDecreament++;
				}
			}
			
			/* remove symbol from escape context */
			ContextUpdate(coder->escape, -1, symbol);
			coder->NovelSymbol[symbol] = 1;
			coder->nNovelSymbols--;
		}

	}
	else{
		if (update){
			ContextUpdate(coder->context, 1, symbol);
		}

	}
	return symbol;
}

/*----------------------------------------------------------------------------*/	
/*----------------------------------------------------------------------------*/	
void BasicEscapeCoderReset(BasicEscapeCoder *coder)
{
	int i;

	ContextInitialize(coder->context, coder->nSymbols+1, 
				coder->context->MaxCount, 0);
	
	ContextUpdate(coder->context, coder->nSymbols+1, coder->nSymbols);
	
	ContextInitialize(coder->escape, coder->nSymbols, 
				coder->escape->MaxCount, 1);
	
	for (i=0; i<coder->nSymbols;i++){
		coder->NovelSymbol[i] = 0;
	}

	coder->EscapeDecreament = coder->EscapeDecreamentStart;
	coder->nNovelSymbols = coder->nNovelSymbols;

}

/*----------------------------------------------------------------------------*/	
/*----------------------------------------------------------------------------*/	
double BasicEscapeCoderGetCost(BasicEscapeCoder *coder, int symbol, 
										 Boolean update)
{
	double cost;

	if (coder->NovelSymbol[symbol]==1){
		cost = ContextGetCost(coder->context, symbol);
		
		if (update){
			ContextUpdate(coder->context, 1, symbol);
		}
	}
	else{
		cost = ContextGetCost(coder->context, coder->EscapeSymbol) +
				 ContextGetCost(coder->escape, symbol);

		if (update){
			coder->NovelSymbol[symbol]=1;
			coder->nNovelSymbols--;
			ContextUpdate(coder->context, 1, symbol);
			
			if(ContextGetProb(coder->context, coder->EscapeSymbol) > 
				coder->EscapeDecreament){
				ContextUpdate(coder->context, -coder->EscapeDecreament, 
					coder->EscapeSymbol);
				if (coder->EscapeDecreament < coder->Thres){
					coder->EscapeDecreament++;
				}
			}
			ContextUpdate(coder->escape, -1, symbol);
		}
	}

	return cost;
}

/*----------------------------------------------------------------------------*/	
/*----------------------------------------------------------------------------*/	
void BasicEscapeCoderSetNSymbols(BasicEscapeCoder *coder, int nSymbols, 
											int MaxCount, int EscapeDecreamentStart,
											int Thres)
{
	int i;

	if (coder->context != NULL){
		ContextDealloc(coder->context);
	}

	if (coder->escape != NULL){
		ContextDealloc(coder->escape);
	}
	
	if (coder->NovelSymbol != NULL){
		free(coder->NovelSymbol);
	}

	/* does not count the escape code */
	coder->nSymbols = nSymbols;
	coder->context = ContextAlloc();	
	coder->escape = ContextAlloc();

	/* include the escape code */
	ContextInitialize(coder->context, nSymbols+1, MaxCount, 0);
	/* only the escape code has some initial count */
	ContextUpdate(coder->context, nSymbols+1, nSymbols);
	/* every symbol in the escape context has a count of 1 */
	ContextInitialize(coder->escape, nSymbols, MaxCount, 1);

	/* novel symbol array to keep track the seen symbols */
	coder->NovelSymbol = (char *)malloc(coder->nSymbols*sizeof(char));
	if (coder->NovelSymbol == NULL){
		CoderError("Fail to allocate novel symbol array.\n");
	}

	for (i=0; i<coder->nSymbols;i++){
		coder->NovelSymbol[i] = 0;
	}

	/* in case it is used */
	coder->EndOfStreamSymbol = coder->context->nSymbols-2;
	/* escape code is the last symbol */
	coder->EscapeSymbol = coder->context->nSymbols-1;
	coder->EscapeDecreamentStart = EscapeDecreamentStart;
	coder->EscapeDecreament = coder->EscapeDecreamentStart;
	coder->Thres = Thres;

}

/*----------------------------------------------------------------------------*/	
/*----------------------------------------------------------------------------*/	
/* same as BasicCoderWriteNBits and BasicCoderReadNBits - should be used
 * from now on to streamlined the name.
 */
void CoderWriteNBits(ArithEncoder *encoder, int val, int nbits)
{
	int count, countLeft, countTotal;
	int temp;
	
	while (nbits>8){
		temp = val & 0x0ff;
		
		encoder->range = encoder->high - encoder->low + 1;
		count = temp+1;
		countLeft = temp;
		countTotal = 256;
		ArithEncoderEncode(encoder, countLeft, count, countTotal);
		nbits -= 8;
		val >>= 8;		
	}
	
	temp = val & ((1<<nbits)-1);
	encoder->range = encoder->high - encoder->low + 1;
	count = temp+1;
	countLeft = temp;
	countTotal = 1<<nbits;
	ArithEncoderEncode(encoder, countLeft, count, countTotal);

}

/*----------------------------------------------------------------------------*/	
/*----------------------------------------------------------------------------*/	
int CoderReadNBits(ArithDecoder *decoder, int nbits)
{
	int count, countLeft, countTotal;
	int i=0, target, symbol=0;
	
	while(nbits>8){
		decoder->range = decoder->high - decoder->low + 1;
		countTotal = 256;
		target = ((int)(decoder->value-decoder->low+1)*countTotal-1)
			/(decoder->range);
		
		count = target+1;
		countLeft = target;
		ArithDecoderDecode(decoder, countLeft, count, countTotal);
		
		symbol += countLeft<<(i*8);
		i++;		
		nbits -=8;
	}
	
	decoder->range = decoder->high - decoder->low + 1;
	countTotal = 1<<nbits;
	
	target = ((int)(decoder->value-decoder->low+1)*countTotal-1)
						/(decoder->range);
	
	count = target+1;
	countLeft = target;
	ArithDecoderDecode(decoder, countLeft, count, countTotal);
	symbol += countLeft<<(i*8);
	
	return symbol;

}

/*----------------------------------------------------------------------------*/
/*----------------------------------------------------------------------------*/	
void CoderWarning(char *fmt, ...)
{
	va_list argptr;
	
	va_start( argptr, fmt );
	printf( "CoderWarning: " );
	vprintf( fmt, argptr );
	va_end( argptr );
	exit( -1 );
}

/*----------------------------------------------------------------------------*/
/*----------------------------------------------------------------------------*/	
void CoderError(char *fmt, ...)
{
	va_list argptr;
	
	va_start( argptr, fmt );
	printf( "CoderError: " );
	vprintf( fmt, argptr );
	va_end( argptr );
	exit( -1 );
}
/*----------------------------------------------------------------------------*/
/*----------------------------------------------------------------------------*/