Algorithm 版 (精华区)

发信人: lofe ()感激生活(), 信区: Algorithm
标  题: Comp -- model-1.c (续)
发信站: 哈工大紫丁香 (Sun Sep  3 16:01:58 2000), 转信


/*
  
   * Listing 9 -- model-1.c
  
   *
  
   * This is the modeling module for an order 0 fixed context
  
   * data compression program.  This is a relatively simple model.
  
   * The totals for all of the symbols are stored in an array accessed
  
   * under the name "totals".  This array has valid indices from -1
  
   * to 256.  The reason for having a -1 element is because the EOF
  
   * symbols is included in the table, and it has a value of -1.
  
   *
  
   * The total count for all the symbols is stored in totals[256], and
  
   * the low and high counts for symbol c are found in totals[c] and
  
   * totals[c+1].  The major performance problem with this is that
  
   * the update_model() routine on the average will have to increment
  
   * 128 totals, a very high cost operation.
  
   */
  
  #include <stdio.h>
  
  #include <stdlib.h>
  
  #include "coder.h"
  
  #include "model.h"

  
  /*
  
   * In order to create an array with indices -1 through 256, I have
  
   * to do this funny declaration.  totals[-1] == storage[0].
  
   */
  
  short int storage[ 258 ];
  
  short int *totals = storage + 1;

  
  /*
  
   * When the model is first started up, each symbols has a count of
  
   * 1, which means a low value of c+1, and a high value of c+2.
  
   */
  
  void initialize_model()
  
{
  
      short int i;

  
      for ( i = -1 ; i <= 256 ; i++ )
  
          totals[ i ] = i + 1;
  
}

  
  /*
  
   * Updating the model means incrementing every single count from
  
   * the high value for the symbol on up to the total.  Then, there
  
   * is a complication.  If the cumulative total has gone up to
  
   * the maximum value, we need to rescale.  Fortunately, the rescale
  
   * operation is relatively rare.
  
   */
  
  void update_model( int symbol )
  
{
  
      int i;

  
      for ( symbol++ ; symbol <= 256; symbol++ )
  
          totals[ symbol ]++;
  
      if ( totals[ 256 ] == MAXIMUM_SCALE )
  
      {
  
          for ( i = 0 ; i <= 256 ; i++ )
  
   {
  
              totals[ i ] /= 2;
  
              if ( totals[ i ] <= totals[ i-1 ] )
  
                  totals[ i ] = totals[ i-1 ] + 1;
  
   }
  
      }
  
}

  
  /*
  
   * Finding the low count, high count, and scale for a symbol
  
   * is really easy, because of the way the totals are stored.
  
   * This is the one redeeming feature of the data structure used
  
   * in this implementation.  Note that this routine returns an
  
   * int, but it is not used in this routine.  The return value
  
   * from convert_int_to_symbol is used in model-2.c.
  
   */
  
  int convert_int_to_symbol( int c, SYMBOL *s )
  
{
  
      s->scale = totals[ 256 ];
  
      s->low_count = totals[ c ];
  
      s->high_count = totals[ c+1 ];
  
      return( 0 );
  
}

  
  /*
  
   * Getting the scale for the current context is easy.
  
   */
  
  void get_symbol_scale( SYMBOL *s )
  
{
  
      s->scale = totals[ 256 ];
  
}

  
  /*
  
   * During decompression, we have to search through the table until
  
   * we find the symbol that straddles the "count" parameter.  When
  
   * it is found, it is returned. The reason for also setting the
  
   * high count and low count is so that symbol can be properly removed
  
   * from the arithmetic coded input.
  
   */
  
  int convert_symbol_to_int( int count, SYMBOL *s)
  
{
  
      int c;

  
      for ( c = 255; count < totals[ c ] ; c-- )
  
   ;
  
      s->high_count = totals[ c+1 ];
  
      s->low_count = totals[ c ];
  
      return( c );
  
}

  
  
--
          _____________________________
          Every problem has a solution.

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

--
☆ 来源:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: haojs.bbs@bbs.whnet.]
※ 修改:·lofe 於 09月03日16:06:35 修改本文·[FROM: 202.118.226.15]