spiht3d.c

该文件是小波信源编码SPIHT算法的C语言代码

/*
 *
 * QccPack: Quantization, compression, and coding utilities
 * Copyright (C) 1997-2008  James E. Fowler
 * 
 */

/*
 * ----------------------------------------------------------------------------
 * 
 * Public License for the 3D-SPIHT Algorithm
 * Version 1.1, March 8, 2004
 * 
 * ----------------------------------------------------------------------------
 * 
 * The 3D Set Partitioning In Hierarchical Trees (3D-SPIHT) algorithm is
 * protected by US patents 5,764,807 and 6,674,911, and other patents pending.
 * An implementation of the 3D-SPIHT algorithm is included herein with the
 * gracious permission of Dr. William A. Pearlman, President of PrimaComp,
 * Inc., exclusive holder of patent rights. PrimaComp, Inc., has granted the
 * following license governing the terms and conditions for use, copying,
 * distribution, and modification of the 3D-SPIHT algorithm implementation
 * contained herein (hereafter referred to as "the 3D-SPIHT source code").
 * 
 * 0. Use of the 3D-SPIHT source code, including any executable-program or
 *    linkable-library form resulting from its compilation, is restricted to
 *    solely academic or non-commercial research activities.
 * 
 * 1. Any other use, including, but not limited to, use in the development
 *    of a commercial product, use in a commercial application, or commercial
 *    distribution, is prohibited by this license. Such acts require a separate
 *    license directly from Dr. Pearlman.
 * 
 * 2. For academic and non-commercial purposes, this license does not restrict
 *    use; copying, distribution, and modification are permitted under the
 *    terms of the GNU General Public License as published by the Free Software
 *    Foundation, with the further restriction that the terms of the present
 *    license shall also apply to all subsequent copies, distributions,
 *    or modifications of the 3D-SPIHT source code.
 * 
 * NO WARRANTY
 * 
 * 3. PrimaComp, Inc., dislaims all warranties, expressed or implied, including
 *    without limitation any warranty whatsoever as to the fitness for a
 *    particular use or the merchantability of the 3D-SPIHT source code.
 * 
 * 4. In no event shall PrimaComp, Inc., be liable for any loss of profits,
 *    loss of business, loss of use or loss of data, nor for indirect, special,
 *    incidental or consequential damages of any kind related to use of the
 *    3D-SPIHT source code.
 * 
 * 
 * END OF TERMS AND CONDITIONS
 * 
 * 
 * Persons desiring to license the 3D-SPIHT algorithm for commercial purposes
 * or for uses otherwise prohibited by this license may wish to contact
 * Dr. Pearlman regarding the possibility of negotiating such licenses:
 * 
 *   Dr. William A. Pearlman, President
 *   PrimaComp, Inc.
 *   851 Maxwell Drive
 *   Niskayuna, NY 12309
 *   U.S.A.
 *   
 *   e-mail: [e-mail]
 *   tel.: [phone]
 *   fax: [phone]
 *  
 * ----------------------------------------------------------------------------
 */


#include "libQccPack.h"


#define QCCSPIHT3D_TYPE_A 0
#define QCCSPIHT3D_TYPE_B 1
#define QCCSPIHT3D_TYPE_DELETE 2
#define QCCSPIHT3D_ENCODE 0
#define QCCSPIHT3D_DECODE 1

#define QCCSPIHT_MAXBITPLANES 128

static const int QccSPIHT3DArithmeticContexts[] =
  {
    /*  LIP Context  */
    256, 128, 128,  64, 128,  64,  64,  32,
    128,  64,  64,  32,  64,  32,  32,  16,
    128,  64,  64,  32,  64,  32,  32,  16,
     64,  32,  32,  16,  32,  16,  16,   8,
    128,  64,  64,  32,  64,  32,  32,  16,
    64,  32,  32,  16,  32,  16,  16,   8,
    64,  32,  32,  16,  32,  16,  16,   8,
    32,  16,  16,   8,  16,   8,   8,   4,
    128,  64,  64,  32,  64,  32,  32,  16,
    64,  32,  32,  16,  32,  16,  16,   8,
    64,  32,  32,  16,  32,  16,  16,   8,
    32,  16,  16,   8,  16,   8,   8,   4,
    64,  32,  32,  16,  32,  16,  16,   8,
    32,  16,  16,   8,  16,   8,   8,   4,
    32,  16,  16,   8,  16,   8,   8,   4,
    16,   8,   8,   4,   8,   4,   4,   2,
    128,  64,  64,  32,  64,  32,  32,  16,
    64,  32,  32,  16,  32,  16,  16,   8,
    64,  32,  32,  16,  32,  16,  16,   8,
    32,  16,  16,   8,  16,   8,   8,   4,
    64,  32,  32,  16,  32,  16,  16,   8,
    32,  16,  16,   8,  16,   8,   8,   4,
    32,  16,  16,   8,  16,   8,   8,   4,
    16,   8,   8,   4,   8,   4,   4,   2,
    64,  32,  32,  16,  32,  16,  16,   8,
    32,  16,  16,   8,  16,   8,   8,   4,
    32,  16,  16,   8,  16,   8,   8,   4,
    16,   8,   8,   4,   8,   4,   4,   2,
    32,  16,  16,   8,  16,   8,   8,   4,
    16,   8,   8,   4,   8,   4,   4,   2,
    16,   8,   8,   4,   8,   4,   4,   2,
    8,   4,   4,   2,   4,   2,   2,
    /*  LIS Type A Context  */
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    /*  LIS Type A Offspring Context  */
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    256, 256, 256, 256, 256, 256, 256, 256,
    /*  LIS Type B Context  */
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    /* Sign Context  */
    2,
    /* Refinement Context  */
    2
  };
#define QCCSPIHT3D_LIP_CONTEXT 0
#define QCCSPIHT3D_LIS_TYPEA_CONTEXT (QCCSPIHT3D_LIP_CONTEXT + 255)
#define QCCSPIHT3D_LIS_TYPEA_OFFSPRING_CONTEXT \
(QCCSPIHT3D_LIS_TYPEA_CONTEXT + 256)
#define QCCSPIHT3D_LIS_TYPEB_CONTEXT \
(QCCSPIHT3D_LIS_TYPEA_OFFSPRING_CONTEXT + 256)
#define QCCSPIHT3D_SIGN_CONTEXT (QCCSPIHT3D_LIS_TYPEB_CONTEXT + 256)
#define QCCSPIHT3D_REFINEMENT_CONTEXT (QCCSPIHT3D_SIGN_CONTEXT + 1)
#define QCCSPIHT3D_NUM_CONTEXTS (QCCSPIHT3D_REFINEMENT_CONTEXT + 1)


typedef struct
{
  int frame;
  int row;
  int col;
  unsigned char type;
  unsigned char state;
} QccSPIHT3DCoefficientBlock;


static QccSPIHT3DCoefficientBlock
*QccSPIHT3DGetCoefficientBlockFromNode(QccListNode *node)
{
  return((QccSPIHT3DCoefficientBlock *)(node->value));
}


static void QccSPIHT3DRefineCoefficient(double *coefficient,
                                        int bit,
                                        double threshold)
{
  *coefficient +=
    (bit) ? (threshold / 2) : (-threshold / 2);
}


static void QccSPIHT3DListClean(QccList *list)
{
  QccListNode *current_list_node;
  QccListNode *next_list_node;
  QccSPIHT3DCoefficientBlock *current_coefficient_block;
  
  current_list_node = list->start;
  while (current_list_node != NULL)
    {
      next_list_node = current_list_node->next;
      
      current_coefficient_block =
        QccSPIHT3DGetCoefficientBlockFromNode(current_list_node);
      
      if (current_coefficient_block->type == QCCSPIHT3D_TYPE_DELETE)
        QccListDeleteNode(list, current_list_node);
      
      current_list_node = next_list_node;
    }
}


static int QccSPIHT3DInputOutput(QccBitBuffer *buffer,
                                 int *symbol,
                                 int method,
                                 QccENTArithmeticModel *model,
                                 int target_bit_cnt)
{
  
  if (method == QCCSPIHT3D_ENCODE)
    {
      if (model == NULL)
        {
          if (QccBitBufferPutBit(buffer, *symbol))
            {
              QccErrorAddMessage("(QccSPIHT3DInputOutput): Error calling QccBitBufferPutBit()");
              return(1);
            }
        }
      else
        {
          if (QccENTArithmeticEncode(symbol, 1,
                                     model, buffer))
            {
              QccErrorAddMessage("(QccSPIHT3DInputOutput): Error calling QccENTArithmeticEncode()");
              return(1);
            }
        }
      if (buffer->bit_cnt >= target_bit_cnt)
        {
          QccBitBufferFlush(buffer);
          return(1);
        }
    }
  else
    if (model == NULL)
      {
        if (QccBitBufferGetBit(buffer, symbol))
          {
            QccErrorAddMessage("(QccSPIHT3DInputOutput): Error calling QccBitBufferGetBit()");
            return(1);
          }
      }
    else
      if (QccENTArithmeticDecode(buffer,
                                 model,
                                 symbol, 1))
        {
          QccErrorAddMessage("(QccSPIHT3DInputOutput): Error calling QccENTArithmeticDecode()");
          return(1);
        }
  
  return(0);
}


int QccSPIHT3DEncodeHeader(QccBitBuffer *buffer, 
                           int transform_type,
                           int zerotree_type,
                           int temporal_num_levels,
                           int spatial_num_levels,
                           int num_frames,
                           int num_rows,
                           int num_cols,
                           double image_mean,
                           int max_coefficient_bits,
                           int arithmetic_coded)
{
  int return_value;
  
  if (QccBitBufferPutBit(buffer, transform_type))
    {
      QccErrorAddMessage("(QccSPIHT3DEncodeHeader): Error calling QccBitBufferPutBit()");
      goto Error;