arithm.c

常用的无损压缩算法源代码

/* = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = */

/*     A R I T H M E T I C   C O D E   I M P L E M E N T A T I O N     */

/* = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = */
/*     > > > > >    ANSI C version  4.03  -  05/30/95    < < < < <     */

/*   Amir Said - [e-mail]                            */
/*   Faculty of Electrical Engineering                                 */
/*   University of Campinas (UNICAMP) - Campinas, SP 13081, Brazil     */

/*   William A. Pearlman - [e-mail]                       */
/*   Dept. of Electrical, Computer, and Systems Engineering            */
/*   Rensselaer Polytechnic Institute - Troy, NY 12180, USA            */


/* - - Inclusion - - - - - - - - - - - - - - - - - - - - - - - - - - - */

#include "arithm.h"


/* - - 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  4095L    /* 2^12 - 1 */


/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
/* - - 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 < Decoder >  - - - - - - - - - - - - - - - - - - - */

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 += 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;

  for (i = 1; i <= CodeValueBits; i++) {
    if (!D->bit_index) Input_Byte(D);
    D->value += D->value + (D->bit_buffer & 1);
    D->bit_buffer >>= 1;  --D->bit_index; }
}

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

void Stop_Decoder(Decoder * D)
{
  fclose(D->in_file);
}

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

int Read_Symbol(Decoder * D, Adaptive_Model * M)
{
  int symbol = Select_Symbol(M, D->value, &(D->low), &(D->high));
  Update_Decoder(D);
  return symbol;
}

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

int Read_Bits(Decoder * D, int bits)
{
  long lm1 = D->low - 1, range = D->high - lm1, prod = range;
  int word = (int) ((((D->value - lm1) << bits) - 1) / range);

  prod *= word;
  D->high = lm1 + ((prod + range) >> bits);
  D->low += prod >> bits;
  Update_Decoder(D);
  return word;
}

/* = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = */

/* end of file < arithm.c > */