arcode.c

基于嵌入式零树小波编码的C语言程序实现。

#include "arcode.h"

const double ZERO_ENT=-1.0;
const double OneLog2=1.4426950408889634074;

const int CodeValueBits = 16;
const int TopValue      = 65535L;  // 2^CodeValueBits - 1
const long FirstQtr     = 16384L;  // (TopValue + 1) / 4
const long Half         = 32768L;  // 2 * FirstQtr
const long ThirdQtr     = 49152L;  // 3 * FirstQtr

/*--------------------------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------------------------*/
void  HistoBiReset(HistoBi *h, int c0, int c1)
{

	if ((c0+c1)<=h->MaxCount){
		if (c0){
			h->c0 = c0;
		}
		else{
			h->c0 = 1;
		}
		if (c1){
			h->c1 = c1;
		}
		else{
			h->c1 = 1;
		}
	}	
}

/*--------------------------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------------------------*/
HistoBi* HistoBiAlloc(int MaxCount, int c0, int c1)
{
	HistoBi* h;
	if ((h=(HistoBi*)malloc(sizeof(HistoBi)))==NULL){
		return NULL;
	}
	h->MaxCount = MaxCount;
	HistoBiReset(h, c0, c1);

	return h;
}

/*--------------------------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------------------------*/
void HistoBiDealloc(HistoBi *h)
{
	if (h!=NULL){
		free(h);
	}
}

/*--------------------------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------------------------*/
int HistoBiGetCount0(HistoBi *h)
{
	return h->c0;
}

/*--------------------------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------------------------*/
int HistoBiGetCount1(HistoBi *h)
{
	return h->c1;
}

/*--------------------------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------------------------*/
int HistoBiGetTotal(HistoBi *h)
{
	return (h->c0+h->c1);
}

/*--------------------------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------------------------*/
double HistoBiGetProb0(HistoBi *h)
{
	if (h->c0 && h->c1){
		return (double)(h->c0)/(double)(h->c0+h->c1);
	}
	else{
		return ZERO_ENT;
	}
}

/*--------------------------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------------------------*/
double HistoBiGetProb1(HistoBi *h)
{
	if (h->c0 && h->c1){
		return (double)(h->c1)/(double)(h->c0+h->c1);
	}
	else{
		return ZERO_ENT;
	}
}

/*--------------------------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------------------------*/
double HistoBiGetEntropy0(HistoBi *h)
{
	if (h->c0 && h->c1){
		return -log((double)(h->c0)/(double)(h->c0+h->c1)) * OneLog2;
	}
	else{
		return ZERO_ENT;
	}
}

/*--------------------------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------------------------*/
double HistoBiGetEntropy1(HistoBi *h)
{
	if (h->c0 && h->c1){
		return -log((double)(h->c1)/(double)(h->c0+h->c1)) * OneLog2;
	}
	else{
		return ZERO_ENT;
	}
}

/*--------------------------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------------------------*/
int HistoBiGetMin(HistoBi * h)
{
	return (h->c0 < h->c1? h->c0 : h->c1);
}

/*--------------------------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------------------------*/
double HistoBiBitCost(HistoBi *h, int bit)
{
	if (bit){
		return HistoBiGetEntropy1(h);
	}
	else{
		return HistoBiGetEntropy0(h);
	}
}

/*--------------------------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------------------------*/
void HistoBiScale(HistoBi *h)
{
	h->c0 = (h->c0+1) >> 1;
	h->c1 = (h->c1+1) >> 1;
}

/*--------------------------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------------------------*/
void HistoBiUpdate(HistoBi *h, int bit)
{
	if ((h->c0+h->c1) >= h->MaxCount){
		HistoBiScale(h);
	}

	if (bit == 0){
		h->c0++;
	}
	else{
		h->c1++;
	}
}

/*--------------------------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------------------------*/
void HistoBiTestTotal(HistoBi *h)
{
	if ((h->c0+h->c1) == h->MaxCount){
		HistoBiScale(h);
	}
}

/*--------------------------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------------------------*/
void HistoBiTaubScale(HistoBi *h, int MinThre, int TotalThre, int TruncFlag)
{
	assert((MinThre > 0) && (TotalThre > 2));

	if (TruncFlag){
		while ((HistoBiGetMin(h) > MinThre) && (HistoBiGetTotal(h) > TotalThre)){
			/* truncation */
			h->c0 >>= 1;
			h->c1 >>= 1;
		}
	}
	else{
		while ((HistoBiGetMin(h) > MinThre) && (HistoBiGetTotal(h) > TotalThre)){
			/* ceiling */
			HistoBiScale(h);
		}
	}
}


/*--------------------------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------------------------*/
Histo *HistoAlloc(int MaxCount, int nSymbols)
{   
   int i;
   Histo *h;

	if((h=(Histo *)malloc(sizeof(Histo)))==NULL){
		return NULL;
	}

	h->Tree=NULL;
	h->ResetCount = 0;
	h->nSymbols=nSymbols;
   h->TotalFreq=0;

	i=1;
	while(h->nSymbols > i){
		i<<=1;
	}
	
   h->p2half=i>>1;

   if ((h->Tree = (int *)calloc(h->nSymbols, sizeof(int)))==NULL){
      free(h);
      return NULL;
   }

   for (i=0; i<h->nSymbols; i++){
		HistoPutValue(h, 1, i);
	}

	h->MaxCount = MaxCount;

   return h;
}

/*--------------------------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------------------------*/
int HistoCopy(Histo *s, Histo *d)
{
   int i;

   if (s==NULL || d==NULL && (s->nSymbols!=d->nSymbols)){
      return 0;
   }

	d->ResetCount  = s->ResetCount;
	d->nSymbols    = s->nSymbols;
   d->TotalFreq   = s->TotalFreq;
   d->p2half      = s->p2half;
   d->MaxCount    = s->MaxCount;

   for (i=0; i<d->nSymbols; i++){
		d->Tree[i] = s->Tree[i];
	}	

   return 1;
}

/*--------------------------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------------------------*/
void HistoReset(Histo *h)
{
   int i;

   for (i=0; i<h->nSymbols; i++){
      h->Tree[i] = 0;
   }
   h->TotalFreq=0;

   for (i=0; i<h->nSymbols; i++){
		HistoPutValue(h, 1, i);
	}
}

/*--------------------------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------------------------*/
void HistoDealloc(Histo *h)
{
   if (h!=NULL){
      if (h->Tree!=NULL){
         free(h->Tree);
         h->Tree=NULL;
      }
		free(h);
	}
}

/*--------------------------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------------------------*/
int HistoGetCumul(Histo *h, int ix)
{
   int sum;

	if (ix<0){
		return 0;
	}

	sum = h->Tree[0];

   while(ix>0){
      sum += h->Tree[ix];
      ix = ix & (ix-1);		
   }

   return sum;
}


/*--------------------------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------------------------*/
void HistoPutValue(Histo *h, int val, int ix)
{
   assert(ix>=0);

	if (ix==0){
		h->Tree[0]+=val;
	}
	else{
		while(ix < h->nSymbols){
			h->Tree[ix] += val;
			ix = 2*ix - (ix & (ix-1));
		}
	}

   h->TotalFreq+=val;
}

/*--------------------------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------------------------*/
int HistoGetProb(Histo *h, int ix)
{
   int val, parent;

	assert(ix>=0 && ix<h->nSymbols);

	val = h->Tree[ix];

   if (ix>0){
      parent= ix & (ix-1);
      ix = ix-1;
      while (parent != ix ){
         val -= h->Tree[ix];
         ix = ix & (ix -1);
      }
   }

   return val;
}

/*--------------------------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------------------------*/
void HistoScaleDown(Histo *h)
{
   int i;
	
   for (i=h->nSymbols-1; i>=0; i--){
		HistoPutValue(h, -HistoGetProb(h, i)/2, i);
   }
	h->ResetCount++;
}

/*--------------------------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------------------------*/
int HistoGetSymbol(Histo *h, int CumFreq)
{
   int baseIx, testIx, half;

   if (CumFreq<h->Tree[0]){
      return 0;
   }
   
	CumFreq = CumFreq - h->Tree[0] + 1;
	baseIx=0;
   half = h->p2half;

   while (half>0){
      testIx = baseIx+half;

		/* 26/09/02 - the first condition has to be tested first */
		if (testIx < h->nSymbols){
			if (CumFreq > h->Tree[testIx] ){
				baseIx = testIx;
				CumFreq -= h->Tree[testIx];
			}
      }
      half>>=1;
   }
   return baseIx+1;
}

/*--------------------------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------------------------*/
void HistoUpdate(Histo *h, int val, int ix)
{
   if (h->TotalFreq > h->MaxCount){
      HistoScaleDown(h);
   }

   HistoPutValue(h, val, ix);
}
/*--------------------------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------------------------*/


/*--------------------------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------------------------*/
/* Arithmetic Encoder Functions */
/*--------------------------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------------------------*/
static void AREncoderBitPlusFollow(AREncoder *ar, int b)
{
	ar->BitBuffer >>= 1;
	
	if (b){
		ar->BitBuffer |= 0x80;
	}
  
	if (!(--ar->BitIndex)) {
		ar->ByteCounter++;  
		ar->BitIndex = 8;
		
		if (putc(ar->BitBuffer, ar->f) == EOF){ 
			ARCoderError("Fail to write.");
		}
	}
	
	while (ar->BitsToFollow > 0){
		ar->BitsToFollow--;  
		ar->BitBuffer >>= 1;
		
		if (!b){ 
			ar->BitBuffer |= 0x80;
		}
		if (!(--ar->BitIndex)){
			ar->ByteCounter++;  
			ar->BitIndex = 8;
			if (putc(ar->BitBuffer, ar->f) == EOF){ 
				ARCoderError("Fail to write.");
			}
		}
	}
}

/*--------------------------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------------------------*/
static void AREncoderUpdateInterval(AREncoder *ar)
{
	++ar->SymbolCounter;

	for (;;){

		if (ar->High < Half){
			AREncoderBitPlusFollow(ar, 0);
		}
		else if (ar->Low >= Half) {
				AREncoderBitPlusFollow(ar, 1);
				ar->Low -= Half;  
				ar->High -= Half; 
		}
		else if ((ar->Low >= FirstQtr) && (ar->High < ThirdQtr)){
			ar->BitsToFollow++;  
			ar->Low -= FirstQtr;  
			ar->High -= FirstQtr; 
		}
		else{
			break;
		}