arithmetic.c

spiht for linux this is used to decod and encode vedio i wich all enjoy

/*
 * 
 * QccPack: Quantization, compression, and coding libraries
 * Copyright (C) 1997-2009  James E. Fowler
 * 
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 * 
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 * 
 * You should have received a copy of the GNU Library General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 675 Mass Ave, Cambridge,
 * MA 02139, USA.
 * 
 */

#include "libQccPack.h"


static int QccENTArithmeticModelInitialize(QccENTArithmeticModel *model)
{
  if (model == NULL)
    return(0);

  model->num_contexts = 0;
  model->num_symbols = NULL;
  model->translate_symbol_to_index = NULL;
  model->translate_index_to_symbol = NULL;
  model->cumulative_frequencies = NULL;
  model->frequencies = NULL;
  model->low = model->high = 0;
  model->bits_to_follow = 0;
  model->garbage_bits = 0;
  model->target_num_bits = QCCENT_ANYNUMBITS;
  model->adaptive_model = QCCENT_ADAPTIVE;
  model->context_function = NULL;
  model->current_context = 0;
  model->current_code_value = 0;

  return(0);
}


static void QccENTArithmeticFreeArray(int **array, int num_contexts)
{
  int context;
  
  if (array == NULL)
    return;
  
  for (context = 0; context < num_contexts; context++)
    if (array[context] != NULL)
      QccFree(array[context]);
  QccFree(array);
  
}


static int **QccENTArithmeticAllocArray(const int *num_symbols,
                                        int num_contexts)
{
  int **array = NULL;
  int context;
  
  if (num_symbols == NULL)
    return(NULL);

  if ((array = (int **)malloc(sizeof(int *)*num_contexts)) == NULL)
    {
      QccErrorAddMessage("(QccENTArithmeticAllocArray): Error allocating memory");
      return(NULL);
    }
  
  /*  Save an extra space total cumulative frequency  */
  for (context = 0; context < num_contexts; context++)
    if ((array[context] = 
         (int *)malloc(sizeof(int)*(num_symbols[context] + 1))) == NULL)
      {
        QccErrorAddMessage("(QccENTArithmeticAllocArray): Error allocating memory");
        QccENTArithmeticFreeArray(array, num_contexts);
        return(NULL);
      }
  
  return(array);
}


static void QccENTArithmeticFreeModelArrays(QccENTArithmeticModel *model)
{
  if (model == NULL)
    return;

  QccENTArithmeticFreeArray(model->translate_symbol_to_index, 
                            model->num_contexts);
  QccENTArithmeticFreeArray(model->translate_index_to_symbol, 
                            model->num_contexts);
  QccENTArithmeticFreeArray(model->cumulative_frequencies, 
                            model->num_contexts);
  QccENTArithmeticFreeArray(model->frequencies, 
                            model->num_contexts);
}


static int QccENTArithmeticAllocModelArrays(QccENTArithmeticModel *model)
{
  if (model == NULL)
    return(0);
  if (model->num_symbols == NULL)
    return(0);

  if ((model->translate_symbol_to_index = 
       QccENTArithmeticAllocArray(model->num_symbols, model->num_contexts))
      == NULL)
    {
      QccErrorAddMessage("(QccENTArithmeticAllocModelArrays): Error calling QccENTArithmeticAllocArray()");
      QccENTArithmeticFreeModelArrays(model);
      return(0);
    }

  if ((model->translate_index_to_symbol = 
       QccENTArithmeticAllocArray(model->num_symbols, model->num_contexts))
      == NULL)
    {
      QccErrorAddMessage("(QccENTArithmeticAllocModelArrays): Error calling QccENTArithmeticAllocArray()");
      QccENTArithmeticFreeModelArrays(model);
      return(0);
    }

  if ((model->cumulative_frequencies =
       QccENTArithmeticAllocArray(model->num_symbols, model->num_contexts))
      == NULL)
    {
      QccErrorAddMessage("(QccENTArithmeticAllocModelArrays): Error calling QccENTArithmeticAllocArray()");
      QccENTArithmeticFreeModelArrays(model);
      return(0);
    }

  if ((model->frequencies = 
       QccENTArithmeticAllocArray(model->num_symbols, model->num_contexts))
      == NULL)
    {
      QccErrorAddMessage("(QccENTArithmeticAllocModelArrays): Error calling QccENTArithmeticAllocArray()");
      QccENTArithmeticFreeModelArrays(model);
      return(0);
    }

  return(0);
}


static QccENTArithmeticModel
*QccENTArithmeticCreateModel(const int *num_symbols,
                             int num_contexts,
                             QccENTArithmeticGetContext context_function)
{
  QccENTArithmeticModel *new_model = NULL;
  int symbol, context;

  if (num_symbols == NULL)
    return(NULL);

  if ((new_model = 
       (QccENTArithmeticModel *)malloc(sizeof(QccENTArithmeticModel))) == NULL)
    {
      QccErrorAddMessage("(QccENTArithmeticCreateModel): Error allocating memory");
      goto QccError;
    }

  QccENTArithmeticModelInitialize(new_model);

  if ((new_model->num_symbols = 
       (int *)malloc(sizeof(int)*num_contexts)) == NULL)
    {
      QccErrorAddMessage("(QccENTArithmeticCreateModel): Error allocating memory");
      goto QccError;
    }
  /*  Save space for EOF symbol  */
  for (context = 0; context < num_contexts; context++)
    new_model->num_symbols[context] = num_symbols[context] + 1;
  new_model->num_contexts = num_contexts;
  
  if (QccENTArithmeticAllocModelArrays(new_model))
    {
      QccErrorAddMessage("(QccENTArithmeticCreateModel): Error calling QccENTArithmeticAllocModelArrays()");
      goto QccError;
    }
  
  for (context = 0; context < new_model->num_contexts; context++)
    {
      for (symbol = 0; symbol < new_model->num_symbols[context]; symbol++)
        {
          new_model->translate_symbol_to_index[context][symbol] = symbol + 1;
          new_model->translate_index_to_symbol[context][symbol + 1] =
            symbol;
        }

      if (QccENTArithmeticResetModel(new_model, context))
        {
          QccErrorAddMessage("(QccENTArithmeticCreateModel): Error calling QccENTArithmeticResetModel()");
          goto QccError;
        }
    }

  new_model->low = 0;
  new_model->high = QCCENT_TOPVALUE;
  new_model->bits_to_follow = 0;

  new_model->context_function = context_function;
  new_model->current_context = 0;

  return(new_model);

 QccError:
  if (new_model != NULL)
    QccENTArithmeticFreeModel(new_model);
  return(NULL);
}


static int QccENTArithmeticUpdateModel(QccENTArithmeticModel *model,
                                       int symbol_index, int context)
{
  int new_index;
  int cum = 0;
  int symbol1, symbol2;

  if (model == NULL)
    return(0);

  if (model->cumulative_frequencies[context][0] == QCCENT_MAXFREQUENCY)
    for (new_index = model->num_symbols[context]; new_index >= 0; new_index--)
      {
        model->frequencies[context][new_index] =
          (model->frequencies[context][new_index] + 1)/2;
        model->cumulative_frequencies[context][new_index] = cum;
        cum += model->frequencies[context][new_index];
      }

  for (new_index = symbol_index; 
       (model->frequencies[context][new_index] == 
        model->frequencies[context][new_index - 1]);
       new_index--);

  if (new_index < symbol_index)
    {
      symbol1 = model->translate_index_to_symbol[context][new_index];
      symbol2 = model->translate_index_to_symbol[context][symbol_index];
      model->translate_index_to_symbol[context][new_index] = symbol2;
      model->translate_index_to_symbol[context][symbol_index] = symbol1;
      model->translate_symbol_to_index[context][symbol1] = symbol_index;
      model->translate_symbol_to_index[context][symbol2] = new_index;
    }

  model->frequencies[context][new_index] += 1;

  while (new_index > 0)
    {
      new_index--;
      model->cumulative_frequencies[context][new_index] += 1;
    }

  return(0);
}


int QccENTArithmeticSetModelContext(QccENTArithmeticModel *model,
                                    int current_context)
{
  if ((current_context < 0) || (current_context >= model->num_contexts))
    {
      QccErrorAddMessage("(QccENTArithmeticSetModelContext): Invalid context number");
      return(1);
    }

  model->current_context = current_context;

  return(0);
}


void QccENTArithmeticSetModelAdaption(QccENTArithmeticModel *model,
                                      int adaptive)
{
  model->adaptive_model = adaptive;
}


int QccENTArithmeticSetModelProbabilities(QccENTArithmeticModel *model,
                                          const double *probabilities,
                                          int context)
{
  int symbol;
  int cum = 0;
  int freq;
  int max_freq;

  if (model == NULL)
    return(0);
  if (probabilities == NULL)
    return(0);
  
  if (model->adaptive_model == QCCENT_ADAPTIVE)
    {
      QccErrorAddMessage("(QccENTArithmeticSetModelProbabilities): Cannot manually set model probabilities in an adaptive model");
      return(1);
    }

  for (symbol = model->num_symbols[context] - 2; symbol >= 0; symbol--)
    if ((probabilities[symbol] < 0.0) ||
        (probabilities[symbol] > 1.0))
    {
      QccErrorAddMessage("(QccENTArithmeticSetModelProbabilities): Invalid probability encountered");
      return(1);
    }

  max_freq = QCCENT_MAXFREQUENCY - model->num_symbols[context] + 1;

  for (symbol = model->num_symbols[context] - 2; symbol >= 0; symbol--)
    {
      freq = (int)rint(QCCENT_MAXFREQUENCY * probabilities[symbol]);
      
      if (freq > max_freq)
        model->frequencies[context]
          [model->translate_symbol_to_index[context][symbol]] =
          max_freq;
      else
        if (freq <= 0)
          model->frequencies[context]
            [model->translate_symbol_to_index[context][symbol]] = 1;
        else
          model->frequencies[context]
            [model->translate_symbol_to_index[context][symbol]] = freq;
    }

  for (symbol = model->num_symbols[context]; symbol >= 0; symbol--)
    {
      model->cumulative_frequencies[context][symbol] = cum;
      cum += model->frequencies[context][symbol];
    }

  cum = 0;
  if (model->cumulative_frequencies[context][0] >= QCCENT_MAXFREQUENCY)
    for (symbol = model->num_symbols[context]; symbol >= 0; symbol--)
      {
        model->frequencies[context][symbol] =
          (model->frequencies[context][symbol] + 1)/2;
        model->cumulative_frequencies[context][symbol] = cum;
        cum += model->frequencies[context][symbol];
      }

  return(0);
}


int QccENTArithmeticResetModel(QccENTArithmeticModel *model,
                               int context)
{
  int symbol;
  
  for (symbol = 0; symbol <= model->num_symbols[context]; symbol++)
    {
      model->frequencies[context][symbol] = 1;
      model->cumulative_frequencies[context][symbol] =
        model->num_symbols[context] - symbol;
    }

  model->frequencies[context][0] = 0;
  
  return(0);
}


void QccENTArithmeticFreeModel(QccENTArithmeticModel *model)
{
  if (model == NULL)
    return;

  QccENTArithmeticFreeModelArrays(model);
  if (model->num_symbols != NULL)
    QccFree(model->num_symbols);    
  QccFree(model);

}


static int 
QccENTArithmeticOutputBitPlusFollowingOppositeBits(int bit_value, 
                                                   QccENTArithmeticModel 
                                                   *model,
                                                   QccBitBuffer *output_buffer)
{
  if (QccBitBufferPutBit(output_buffer, bit_value))
    {
      QccErrorAddMessage("(QccENTArithmeticOutputBitPlusFollowingOppositeBits): Error calling QccBitBufferPutBit()");
      return(1);
    }
  if (model->target_num_bits != QCCENT_ANYNUMBITS)
    if (output_buffer->bit_cnt >= model->target_num_bits)
      return(2);
  while (model->bits_to_follow > 0)
    {
      if (QccBitBufferPutBit(output_buffer, !bit_value))
        {
          QccErrorAddMessage("(QccENTArithmeticOutputBitPlusFollowingOppositeBits): Error calling QccBitBufferPutBit()");
          return(1);
        }
      if (model->target_num_bits != QCCENT_ANYNUMBITS)
        if (output_buffer->bit_cnt >= model->target_num_bits)
          return(2);
      model->bits_to_follow--;
    }

  return(0);
}


static int QccENTArithmeticEncodeSymbol(int symbol_index, int context,
                                        QccENTArithmeticModel *model, 
                                        QccBitBuffer *output_buffer)
{
  int return_value;
  long range;

  range = (long)(model->high - model->low) + 1;
  model->high = model->low +
    (range * model->cumulative_frequencies[context][symbol_index - 1]) /
    model->cumulative_frequencies[context][0] - 1;
  model->low = model->low +
    (range * model->cumulative_frequencies[context][symbol_index]) /
    model->cumulative_frequencies[context][0];

  for (;;)
    {
      if (model->high < QCCENT_HALFVALUE)
        {
          return_value =
            QccENTArithmeticOutputBitPlusFollowingOppositeBits(0, model,
                                                               output_buffer);
          if (return_value == 2)
            return(2);
          else
            if (return_value == 1)
              {
                QccErrorAddMessage("(QccENTArithmeticEncodeSymbol): Error calling QccENTArithmeticOutputBitPlusFollowingOppositeBits()");
                return(1);
              }
        }
      else if (model->low >= QCCENT_HALFVALUE)
        {
          return_value =
            QccENTArithmeticOutputBitPlusFollowingOppositeBits(1, model,