arith.c

linux下将各类格式图片转换工具

/*
 *  arith.c:		Adaptive arithmetic coding and decoding
 *
 *  Written by:		Ullrich Hafner
 *  
 *  This file is part of FIASCO (獸籸actal 獻籱age 獳籲d 玈籩quence 獵O籨ec)
 *  Copyright (C) 1994-2000 Ullrich Hafner <[e-mail]>
 */

/*
 *  $Date: 2000/06/14 20:49:37 $
 *  $Author: hafner $
 *  $Revision: 5.1 $
 *  $State: Exp $
 */

#include "config.h"

#include "types.h"
#include "macros.h"
#include "error.h"

#include "bit-io.h"
#include "misc.h"
#include "arith.h"

/******************************************************************************

				public code
  
******************************************************************************/

arith_t *
alloc_encoder (bitfile_t *output)
/*
 *  Arithmetic coder constructor:
 *  Initialize the arithmetic coder.
 *  
 *  Return value:
 *	A pointer to the new coder structure
 */
{
   arith_t *arith = Calloc (1, sizeof (arith_t));

   assert (output);
   
   arith->low       = LOW;
   arith->high      = HIGH;
   arith->underflow = 0;
   arith->file 	    = output;

   return arith;
}

void
free_encoder (arith_t *arith)
/*
 *  Arithmetic encoder destructor.
 *  Flush the arithmetic coder. Append all remaining bits to the
 *  output stream. Append zero bits to get the output file byte aligned.
 *  
 *  No return value.
 */
{
   u_word_t   low;			/* start of the current code range  */
   u_word_t   high;			/* end of the current code range    */
   u_word_t   underflow;		/* number of underflow bits pending */
   bitfile_t *output;
   
   assert (arith);

   low       = arith->low;
   high      = arith->high;
   underflow = arith->underflow;
   output    = arith->file;
   
   low = high;

   RESCALE_OUTPUT_INTERVAL;

   OUTPUT_BYTE_ALIGN (output);

   Free (arith);
}

real_t
encode_symbol (unsigned symbol, arith_t *arith, model_t *model)
/*
 *  Encode the given 'symbol' using the given probability 'model'.
 *  The current state of the arithmetic coder is given by 'arith'.
 *  Output bits are appended to the stream 'output'.
 *
 *  The model is updated after encoding the symbol (if neccessary the
 *  symbol counts are rescaled).
 *  
 *  Return value:
 *	information content of the encoded symbol.
 *
 *  Side effects:
 *	'model' is updated (probability distribution)
 *	'arith' is updated (coder state)
 */
{
   u_word_t   low_count;		/* lower bound of 'symbol' interval */
   u_word_t   high_count;		/* upper bound of 'symbol' interval */
   u_word_t   scale;			/* range of all 'm' symbol intervals */
   unsigned   range;			/* range of current interval */
   unsigned   index;			/* index of probability model */
   u_word_t   low;			/* start of the current code range  */
   u_word_t   high;			/* end of the current code range    */
   u_word_t   underflow;		/* number of underflow bits pending */
   bitfile_t *output;			/* output file */
   
   assert (model && arith);

   /*
    * Get interval values
    */
   low       = arith->low;
   high      = arith->high;
   underflow = arith->underflow;
   output    = arith->file;

   assert (high > low);
   
   if (model->order > 0)		/* order-'n' model*/
   {
      unsigned power;			/* multiplicator */
      unsigned i;

      /*
       *  Compute index of the probability model to use.
       *  See init_model() for more details.
       */
      power = 1;			/* multiplicator */
      index = 0;			/* address of prob. model */
	 
      for (i = 0; i < model->order; i++) /* genarate a M-nary number */
      {
	 index += model->context [i] * power;	
	 power *= model->symbols;
      }

      index *= model->symbols + 1;	/* we need space for M + 1 elements */

      for (i = 0; i < model->order - 1; i++)
	 model->context [i] = model->context [i + 1];
      model->context [i] = symbol;
   }
   else
      index = 0;

   scale      = model->totals [index + model->symbols];
   low_count  = model->totals [index + symbol];
   high_count = model->totals [index + symbol + 1];

   /*
    *  Compute the new interval depending on the input 'symbol'.
    */
   range = (high - low) + 1;
   high  = low + (u_word_t) ((range * high_count) / scale - 1);
   low   = low + (u_word_t) ((range * low_count) / scale);
   
   RESCALE_OUTPUT_INTERVAL;
   
   if (model->scale > 0)		/* adaptive model */
   {
      unsigned i;

      /*
       *  Update probability model
       */
      for (i = symbol + 1; i <= model->symbols; i++)
	 model->totals [index + i]++;
      if (model->totals [index + model->symbols] > model->scale) /* scaling */
      {
	 for (i = 1; i <= model->symbols; i++)
	 {
	    model->totals [index + i] >>= 1;
	    if (model->totals [index + i] <= model->totals [index + i - 1])
	       model->totals [index + i] = model->totals [index + i - 1] + 1;
	 }
      }
   }

   /*
    *  Store interval values
    */
   arith->low  	    = low;
   arith->high 	    = high;
   arith->underflow = underflow;
   
   return - log2 ((high_count - low_count) / (real_t) scale);
}

void
encode_array (bitfile_t *output, const unsigned *data, const unsigned *context,
	      const unsigned *c_symbols, unsigned n_context, unsigned n_data,
	      unsigned scaling)
/*
 *  Arithmetic coding of #'n_data' symbols given in the array 'data'.
 *  If 'n_context' > 1 then a number (context [n]) is assigned to every
 *  data element n, specifying which context (i.e. number of symbols given by
 *  c_symbols [context [n]] and adaptive probability model) must be used.
 *  Rescale probability models if range > 'scaling'.
 *
 *  No return value.
 */
{
   u_word_t **totals;			/* probability model */

   if (!n_context)
      n_context = 1;			/* always use one context */

   assert (output && c_symbols && data);
   assert (n_context == 1 || context);
   
   /*
    *  Allocate probability models, start with uniform distribution
    */
   totals = Calloc (n_context, sizeof (u_word_t *));
   {
      unsigned c;
      
      for (c = 0; c < n_context; c++)
      {
	 unsigned i;
      
	 totals [c]    = Calloc (c_symbols [c] + 1, sizeof (u_word_t));
	 totals [c][0] = 0;
      
	 for (i = 0; i < c_symbols [c]; i++)
	    totals [c][i + 1] = totals [c][i] + 1;
      }
   }

   /*
    *  Encode array elements
    */
   {
      u_word_t low  	 = 0;		/* Start of the current code range */
      u_word_t high 	 = 0xffff;	/* End of the current code range */
      u_word_t underflow = 0;		/* Number of underflow bits pending */
      unsigned n;
      
      for (n = 0; n < n_data; n++)
      {
	 u_word_t low_count;		/* lower bound of 'symbol' interval */
	 u_word_t high_count;		/* upper bound of 'symbol' interval */
	 u_word_t scale;		/* range of all 'm' symbol intervals */
	 unsigned range;		/* current range */
	 int	  d;			/* current data symbol */
	 int	  c;			/* context of current data symbol */

	 d = data [n];
	 c = n_context > 1 ? context [n] : 0; 
      
	 scale	    = totals [c][c_symbols [c]];
	 low_count  = totals [c][d];
	 high_count = totals [c][d + 1];

	 /*
	  * Rescale high and low for the new symbol.
	  */
	 range = (high - low) + 1;
	 high  = low + (u_word_t) ((range * high_count) / scale - 1);
	 low   = low + (u_word_t) ((range * low_count) / scale);
	 RESCALE_OUTPUT_INTERVAL;
      
	 /*
	  *  Update probability models
	  */
	 {
	    unsigned i;

	    for (i = d + 1; i < c_symbols [c] + 1; i++)
	       totals [c][i]++;
	 
	    if (totals [c][c_symbols [c]] > scaling) /* scaling */
	       for (i = 1; i < c_symbols [c] + 1; i++)
	       {
		  totals [c][i] >>= 1;
		  if (totals [c][i] <= totals [c][i - 1])
		     totals [c][i] = totals [c][i - 1] + 1;
	       }
	 }
      }
      /*
       *  Flush arithmetic encoder
       */
      low = high;
      RESCALE_OUTPUT_INTERVAL;
      OUTPUT_BYTE_ALIGN (output);
   }
   
   /*
    *  Cleanup ...
    */
   {
      unsigned c;
      for (c = 0; c < n_context; c++)
	 Free (totals [c]);
      Free (totals);
   }
}

arith_t *
alloc_decoder (bitfile_t *input)
/*
 *  Arithmetic decoder constructor:
 *  Initialize the arithmetic decoder with the first
 *  16 input bits from the stream 'input'.
 *  
 *  Return value:
 *	A pointer to the new decoder structure
 */

{
   arith_t *arith = Calloc (1, sizeof (arith_t));
   
   assert (input);
   
   arith->low  = LOW;
   arith->high = HIGH;
   arith->code = get_bits (input, 16);
   arith->file = input;

   return arith;
}

void
free_decoder (arith_t *arith)
/*
 *  Arithmetic decoder destructor:
 *  Flush the arithmetic decoder, i.e., read bits to get the input
 *  file byte aligned. 
 *  
 *  No return value.
 *
 *  Side effects:
 *	structure 'arith' is discarded.
 */
{
   assert (arith);

   INPUT_BYTE_ALIGN (arith->file);

   Free (arith);
}

unsigned
decode_symbol (arith_t *arith, model_t *model)
/*
 *  Decode the next symbol - the state of the arithmetic decoder
 *  is given in 'arith'. Read refinement bits from the stream 'input'