Algorithm 版 (精华区)

发信人: lofe ()感激生活(), 信区: Algorithm
标  题: Comp -- coder.c
发信站: 哈工大紫丁香 (Sun Sep  3 08:31:45 2000), 转信

/*
  
   * Listing 2 -- coder.c
  
   *
  
   * This file contains the code needed to accomplish arithmetic
  
   * coding of a symbol.  All the routines in this module need
  
   * to know in order to accomplish coding is what the probabilities
  
   * and scales of the symbol counts are.  This information is
  
   * generally passed in a SYMBOL structure.
  
   *
  
   * This code was first published by Ian H. Witten, Radford M. Neal,
  
   * and John G. Cleary in "Communications of the ACM" in June 1987,
  
   * and has been modified slightly for this article.  The code
  
   * is  published here with permission.
  
   */

  
  #include <stdio.h>
  
  #include "coder.h"
  
  #include "bitio.h"

  
  /*
  
   * These four variables define the current state of the arithmetic
  
   * coder/decoder.  They are assumed to be 16 bits long.  Note that
  
   * by declaring them as short ints, they will actually be 16 bits
  
   * on most 80X86 and 680X0 machines, as well as VAXen.
  
   */
  
  static unsigned short int code;  /* The present input code value       */
  
  static unsigned short int low;   /* Start of the current code range    */
  
  static unsigned short int high;  /* End of the current code range      */
  
  long underflow_bits;             /* Number of underflow bits pending   */

  
  /*
  
   * This routine must be called to initialize the encoding process.
  
   * The high register is initialized to all 1s, and it is assumed that
  
   * it has an infinite string of 1s to be shifted into the lower bit
  
   * positions when needed.
  
   */
  
  void initialize_arithmetic_encoder()
  
{
  
      low = 0;
  
      high = 0xffff;
  
      underflow_bits = 0;
  
}

  
  /*
  
   * This routine is called to encode a symbol.  The symbol is passed
  
   * in the SYMBOL structure as a low count, a high count, and a range,
  
   * instead of the more conventional probability ranges.  The encoding
  
   * process takes two steps.  First, the values of high and low are
  
   * updated to take into account the range restriction created by the
  
   * new symbol.  Then, as many bits as possible are shifted out to
  
   * the output stream.  Finally, high and low are stable again and
  
   * the routine returns.
  
   */
  
  void encode_symbol( FILE *stream, SYMBOL *s )
  
{
  
      long range;
  
  /*
  
   * These three lines rescale high and low for the new symbol.
  
   */
  
      range = (long) ( high-low ) + 1;
  
      high = low + (unsigned short int )
  
                   (( range * s->high_count ) / s->scale - 1 );
  
      low = low + (unsigned short int )
  
                   (( range * s->low_count ) / s->scale );
  
  /*
  
   * This loop turns out new bits until high and low are far enough
  
   * apart to have stabilized.
  
   */
  
      for ( ; ; )
  
      {
  
  /*
  
   * If this test passes, it means that the MSDigits match, and can
  
   * be sent to the output stream.
  
   */
  
          if ( ( high & 0x8000 ) == ( low & 0x8000 ) )
  
          {
  
              output_bit( stream, high & 0x8000 );
  
              while ( underflow_bits > 0 )
  
              {
  
                  output_bit( stream, ~high & 0x8000 );
  
                  underflow_bits--;
  
              }
  
          }
  
  /*
  
   * If this test passes, the numbers are in danger of underflow, because
  
   * the MSDigits don't match, and the 2nd digits are just one apart.
  
   */
  
          else if ( ( low & 0x4000 ) && !( high & 0x4000 ))
  
          {
  
              underflow_bits += 1;
  
              low &= 0x3fff;
  
              high |= 0x4000;
  
          }
  
          else
  
              return ;
  
          low <<= 1;
  
          high <<= 1;
  
          high |= 1;
  
      }
  
}

  
  /*
  
   * At the end of the encoding process, there are still significant
  
   * bits left in the high and low registers.  We output two bits,
  
   * plus as many underflow bits as are necessary.
  
   */
  
  void flush_arithmetic_encoder( FILE *stream )
  
{
  
      output_bit( stream, low & 0x4000 );
  
      underflow_bits++;
  
      while ( underflow_bits-- > 0 )
  
          output_bit( stream, ~low & 0x4000 );
  
}

  
  /*
  
   * When decoding, this routine is called to figure out which symbol
  
   * is presently waiting to be decoded.  This routine expects to get
  
   * the current model scale in the s->scale parameter, and it returns
  
   * a count that corresponds to the present floating point code:
  
   *
  
   *  code = count / s->scale
  
   */
  
  short int get_current_count( SYMBOL *s )
  
{
  
      long range;
  
      short int count;

  
      range = (long) ( high - low ) + 1;
  
      count = (short int)
  
              ((((long) ( code - low ) + 1 ) * s->scale-1 ) / range );
  
      return( count );
  
}

  
  /*
  
   * This routine is called to initialize the state of the arithmetic
  
   * decoder.  This involves initializing the high and low registers
  
   * to their conventional starting values, plus reading the first
  
   * 16 bits from the input stream into the code value.
  
   */
  
  void initialize_arithmetic_decoder( FILE *stream )
  
{
  
      int i;

  
      code = 0;
  
      for ( i = 0 ; i < 16 ; i++ )
  
      {
  
          code <<= 1;
  
          code += input_bit( stream );
  
      }
  
      low = 0;
  
      high = 0xffff;
  
}

  
  /*
  
   * Just figuring out what the present symbol is doesn't remove
  
   * it from the input bit stream.  After the character has been
  
   * decoded, this routine has to be called to remove it from the
  
   * input stream.
  
   */
  
  void remove_symbol_from_stream( FILE *stream, SYMBOL *s )
  
{
  
      long range;

  
  /*
  
   * First, the range is expanded to account for the symbol removal.
  
   */
  
      range = (long)( high - low ) + 1;
  
      high = low + (unsigned short int)
  
                   (( range * s->high_count ) / s->scale - 1 );
  
      low = low + (unsigned short int)
  
                   (( range * s->low_count ) / s->scale );
  
  /*
  
   * Next, any possible bits are shipped out.
  
   */
  
      for ( ; ; )
  
      {
  
  /*
  
   * If the MSDigits match, the bits will be shifted out.
  
   */
  
          if ( ( high & 0x8000 ) == ( low & 0x8000 ) )
  
          {
  
          }
  
  /*
  
   * Else, if underflow is threatining, shift out the 2nd MSDigit.
  
   */
  
          else if ((low & 0x4000) == 0x4000  && (high & 0x4000) == 0 )
  
          {
  
              code ^= 0x4000;
  
              low   &= 0x3fff;
  
              high  |= 0x4000;
  
          }
  
  /*
  
   * Otherwise, nothing can be shifted out, so I return.
  
   */
  
          else
  
              return;
  
          low <<= 1;
  
          high <<= 1;
  
          high |= 1;
  
          code <<= 1;
  
          code += input_bit( stream );
  
      }
  
}


  
  
--
          _____________________________
          Every problem has a solution.

optooff@mail.hust.edu.cn
www.netease.com/~hansen
※ 修改:．haojs 于 Sep  3 08:29:21 修改本文．[FROM: bbs.hit.edu.cn]
--
※ 转寄:．武汉白云黄鹤站 bbs.whnet.edu.cn．[FROM: bbs.hit.edu.cn]

--
☆ 来源:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: haojs.bbs@bbs.whnet.]