calic1decode.cpp

当前公认的最优无损/准无损图像压缩算法之一：calic算法的软件实现。

//                *****************************************
//                *           CALIC算法解码程序           * 
//                *****************************************

//     ************ 
//     *包含库文件* 
//     ************ 

#include <iostream.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys\types.h>
#include <sys\timeb.h>
#include "arithm.h"

//     ************ 
//     *  宏定义  * 
//     ************ 
//RESET:  threshold value at which A,B,and N are halved
#define RESET 128
#define MAXVAL 255
#define NEAR 0
/* - - Definitions - - - - - - - - - - - - - - - - - - - - - - - - - - */

#define CodeValueBits   16

#define TopValue     65535L    /* 2^CodeValueBits - 1 */

#define FirstQtr     16384L    /* (TopValue + 1) / 4 */

#define Half         32768L    /* 2 * FirstQtr */

#define ThirdQtr     49152L    /* 3 * FirstQtr */

#define MaxFrequency  16383L    /* 2^12 - 1 */


/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

//     ************************************
//     *           全局变量初始化         *    
//     ************************************ 
//MAXVAL:   maximum possible image sample value ove all component of a scan
//RUNindex: index for run mode order
//qbpp:     number of bits needed to represent a mapped error value
//bpp:      number of bits needed to represent MAXVAL,with a minimum of 2
//LIMIT:    the value of glimit for a sample encoded in regular mode
//Q:        context determined from Q1,Q2,Q3
//RANGE:    range of prediction error representation
//A[4][256]:256*4 counters for the accumulated preditection error magnitude
//C[4][256]:256*4 counters storing prediction coreection values
//J[0..31]: 32 variables indicating order of run-length codes
//N[4][256]:256*4 counters for frequency of occurrence of each context
//Nn[365..366]:2 counters for negative prediction error for run interruption
//EOLine:   end of line indicator,used in run mode 
//Errval:   prediction error
//EMErrval: Errval mapped to non-negative integers in run interruption mode
//MErrval:  Errval mapped to non-negative integers in regular mode
//--------------------------------------------------------------------------------
//    LinX:当前行号
//    RowX:当前列号
//    *f:指向码流的指针
//    *fp:文件指针   
//    buffer:数值缓冲器
//    output:解码的数值
//    size:当前码流的长度
//    decodode:当前码流的数值
//    decodode2:临时变量
//    flag1:标志位
     
	int LinX=1,RowX=1; 
    int RANGE; 
	int *f;
	int C[4][256],Offset[4][256];
	int N[4][256];
	int Ew=0;
	FILE *fp;
    Adaptive_Model model[40];
	Decoder decod;

/*-----------------------------------------------------------------------------------*/
/* - - Implementations - - - - - - - - - - - - - - - - - - - - - - - - */

static void Error(char * s)
{
  fprintf(stderr, "\a -> Error: %s", s);
  fprintf(stderr, "\n Execution terminated...\n\n");
  exit(1);
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
/* - - Functions of < Adaptive_Model > - - - - - - - - - - - - - - - - */

void Create_Model(Adaptive_Model * M, int ns)
{
  M->numb_symb = 0;
  Set_New_Model(M, ns);
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

void Reset_Model(Adaptive_Model * M)
{
  Set_New_Model(M, M->numb_symb);
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

void Set_New_Model(Adaptive_Model * M, int ns)
{
  int i, cum;

  if ((ns < 2) || (ns > MaxSymbols))
    Error("invalid < Adaptive_Model > definition");

  if (M->numb_symb != ns) {
    if (M->numb_symb) free((char *) M->freq);
    M->numb_symb = ns;  i = ns + 1;
    if ((M->freq = (int *) malloc(4 * i * sizeof(int))) == NULL)
      Error("< Adaptive_Model >: insufficient memory");
    M->cum_freq = M->freq + i;  M->symb_to_index = M->cum_freq + i;
    M->index_to_symb = M->symb_to_index + i; }

  for (i = 0; i < ns; i++) {
    M->symb_to_index[i] = i + 1;  M->index_to_symb[i+1] = i; }

  M->freq[0] = 0;
  for (i = 1; i <= ns; i++) M->freq[i] = 1;

  for (cum = 0, i = ns; i >= 0; i--) {
    M->cum_freq[i] = cum;  cum += M->freq[i]; }
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

void Dispose_Model(Adaptive_Model * M)
{
  if (M->numb_symb) {
    free((char *) M->freq);  M->numb_symb = 0; }
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

static void Update_Model(Adaptive_Model * M, int index)
{
  int i, cum, symb_i, symb_index;

  if (M->cum_freq[0] == MaxFrequency)
    for (cum = 0, i = M->numb_symb; i >= 0; i--) {
      M->freq[i] = (M->freq[i] + 1) >> 1;
      M->cum_freq[i] = cum;  cum += M->freq[i]; }

  for (i = index; M->freq[i] == M->freq[i-1]; i--) ;

  if (i < index) {
    symb_i = M->index_to_symb[i];
    symb_index = M->index_to_symb[index];
    M->index_to_symb[i] = symb_index;
    M->index_to_symb[index] = symb_i;
    M->symb_to_index[symb_i] = index;
    M->symb_to_index[symb_index] = i; }

  M->freq[i]++;
  while (i) M->cum_freq[--i]++;
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

static int Select_Symbol(Adaptive_Model * M, long value,
                         long * l, long * h)
{
  int index, cum, symbol;
  long range;

  if ((value < *l) || (value > *h))
    Error("invalid < Adaptive_Model > value");

  range = *h - *l + 1;
  cum = (int) (((value - *l + 1) * M->cum_freq[0] - 1) / range);

  for (index = 1; M->cum_freq[index] > cum; index++);

  *h = *l + (range * M->cum_freq[index-1]) / M->cum_freq[0] - 1;
  *l = *l + (range * M->cum_freq[index]) / M->cum_freq[0];

  symbol = M->index_to_symb[index];
  Update_Model(M, index);

  return symbol;
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

static void New_Interval(Adaptive_Model * M, int symb, long * l, long * h)
{
  int index;
  long range;

  if ((symb < 0) || (symb >= M->numb_symb))
    Error("invalid < Adaptive_Model > symbol");

  index = M->symb_to_index[symb];  range = *h - *l + 1;

  *h = *l + (range * M->cum_freq[index-1]) / M->cum_freq[0] - 1;
  *l = *l + (range * M->cum_freq[index]) / M->cum_freq[0];

  Update_Model(M, index);
}


/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
/* - - Functions of < Encoder >  - - - - - - - - - - - - - - - - - - - */

static void Output_Byte(Encoder * E)
{
  E->byte_counter++;  E->bit_index = 8;
  if (putc(E->bit_buffer, E->out_file) == EOF)
    Error("< Encoder > cannot write to file");
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

static void Bit_Plus_Follow(Encoder * E, int b)
{
  E->bit_buffer >>= 1;
  if (b) E->bit_buffer |= 0x80;
  if (--E->bit_index == 0) Output_Byte(E);
  while (E->bits_to_follow > 0) {
    E->bit_buffer >>= 1;  --E->bits_to_follow;
    if (!b) E->bit_buffer |= 0x80;
    if (--E->bit_index == 0) Output_Byte(E); }
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

static void Update_Encoder(Encoder * E)
{
  for (;;) {
    if (E->high < Half)
      Bit_Plus_Follow(E, 0);
    else
      if (E->low >= Half) {
        Bit_Plus_Follow(E, 1);
        E->low -=  Half;  E->high -= Half; }
      else
        if ((E->low >= FirstQtr) && (E->high < ThirdQtr)) {
          E->bits_to_follow++;  E->low -= FirstQtr;
          E->high -= FirstQtr; }
        else
          break;
    E->low <<= 1;  E->high += E->high + 1; }
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

long Bytes_Used(Encoder * E)
{
  return E->byte_counter;
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

void Start_Encoder(Encoder * E, char * file_name)
{
  char * msg = "< Encoder > cannot write to file";

  if ((E->out_file = fopen(file_name, "wb")) == NULL) Error(msg);

  E->bit_index = 8;  E->bit_buffer = E->bits_to_follow = 0;
  E->byte_counter = E->low = 0;  E->high = TopValue;
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

long Stop_Encoder(Encoder * E)
{
  char * msg = "< Encoder > cannot write to file";
  ++E->bits_to_follow;  ++E->byte_counter;
  Bit_Plus_Follow(E, E->low >= FirstQtr);
  if (putc(E->bit_buffer >> E->bit_index, E->out_file) == EOF)
    Error(msg);
  if (fclose(E->out_file) == EOF) Error(msg);
  return E->byte_counter;
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

void Write_Symbol(Encoder * E, Adaptive_Model * M, int s)
{
  New_Interval(M, s, &(E->low), &(E->high));
  Update_Encoder(E);
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

void Write_Bits(Encoder * E, int bits, int word)
{
  long lm1 = E->low - 1, range = E->high - lm1, prod = range;
  word &= (1 << bits) - 1;  prod *= word;
  E->high = lm1 + ((prod + range) >> bits);
  E->low += prod >> bits;
  Update_Encoder(E);
}


/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
/* - - Functions of < decododer >  - - - - - - - - - - - - - - - - - - - */

static void Input_Byte(Decoder *D)
{
  if ((D->bit_buffer = getc(D->in_file)) == EOF)
    if (++D->extra_bits > CodeValueBits - 2)
      Error("< Decoder > attempted to read past end of file");
  ++D->byte_counter;  D->bit_index = 8;
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

static void Update_Decoder(Decoder *D) 
{
  for (;;) {
    if (D->high >= Half)
      if (D->low >= Half) {
        D->value -= Half;  D->low -= Half;  D->high -= Half; }
      else
        if ((D->low >= FirstQtr) && (D->high < ThirdQtr)) {
          D->value -= FirstQtr;  D->low -= FirstQtr;
          D->high -= FirstQtr; }
        else
          break;

    if (!D->bit_index) Input_Byte(D);
    D->low <<= 1;  D->high =2*D->high + 1;
    D->value += D->value + (D->bit_buffer & 1);
    D->bit_buffer >>= 1;  --D->bit_index; }
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

long Bytes_Read(Decoder * D)
{
  return D->byte_counter;
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

void Start_Decoder(Decoder * D, char * file_name)
{
  int i;
  char * msg = "< decoder > cannot read file";

  if ((D->in_file = fopen(file_name, "rb")) == NULL) Error(msg);

  D->value = D->low = D->bit_index = D->extra_bits = 0;
  D->high = TopValue;  D->byte_counter = 0;