huffman.c

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

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

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

/* = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = */
/*     > > > > >    ANSI C version  2.05  -  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 "huffman.h"


/* - - Definitions - - - - - - - - - - - - - - - - - - - - - - - - - - */

typedef struct
{
  int symbol;
  long count;
} Heap_Node;


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

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

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

static void Heap_Sort(int dim, Heap_Node heap[], int * tree[2])
{
  int l, j, ir, i, nn = 0, new_node = dim - 1;
  long nc;
  Heap_Node t;

  l = (dim >> 1) + 1;  ir = dim;

  for (;;) {

    if (l > 1)
      t = heap[--l];
    else
      if ((++nn) & 1) {
        tree[0][--new_node] = heap[1].symbol;  nc = heap[1].count;
        t = heap[ir];
        if (--ir == 1) {
          tree[1][new_node] = t.symbol;
          return; } }
      else {
        tree[1][new_node] = heap[1].symbol;
        t = heap[1];  t.symbol = new_node;  t.count += nc; }

    i = l;  j = l << 1;
    while (j <= ir) {
      if ((j < ir) && (heap[j].count > heap[j+1].count)) ++j;
      if (t.count > heap[j].count) {
        heap[i] = heap[j];  j += (i = j); }
      else
        j = ir + 1; }

    heap[i] = t;
  }
}


/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
/* - - 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 Encoder_Tree_Run(Encoder * E, int depth, int bit, int node,
                             int word)
{
  int new_node = E->tree[bit][node];
  word = (word << 1) | bit;  ++depth;
  if (new_node >= E->shift) {
    new_node -= E->shift;
    Write_Bit(E, 1);  Write_Bits(E, E->nrep, new_node);
    E->code[new_node] = word;  E->length[new_node] = depth; }
  else {
    Write_Bit(E, 0);
    Encoder_Tree_Run(E, depth, 0, new_node, word);
    Encoder_Tree_Run(E, depth, 1, new_node, word); }
}

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

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->byte_counter = E->bit_buffer = 0;
}

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

void Write_Code(Encoder * E, int M, long F[])
{
  int i;
  Heap_Node * heap;
  char * msg = "< Encoder>: insufficient memory";

  if ((M < 3) || (M > 255))
    Error("invalid number of < Encoder> symbols");

  if (M != E->nsb) {
    if (E->nsb) free((char *) E->code);
    E->nsb = M;  i = E->shift = M - 1;
    for (E->nrep = 0; i > 0; E->nrep++) i >>= 1;
    if ((E->code = (int *) malloc(M * 2 * sizeof(int))) == NULL)
      Error(msg);
    E->length = E->code + M; }

  if ((heap = (Heap_Node *) malloc((M + 1) * sizeof(Heap_Node))) ==
    NULL) Error(msg);
  if ((E->tree[0] = (int *) malloc(M * 2 * sizeof(int))) == NULL)
    Error(msg);
  E->tree[1] = E->tree[0] + M;

  for (i = 0; i < M; i++) {
    heap[i+1].symbol = i + E->shift;
    heap[i+1].count = (F[i] > 0 ? F[i] : 1); }

  Heap_Sort(M, heap, E->tree);

  Write_Bits(E, 8, M);
  Encoder_Tree_Run(E, 0, 0, 0, 0);
  Encoder_Tree_Run(E, 0, 1, 0, 0);

  free((char *) E->tree[0]);  free((char *) heap);
}

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

void Write_Bit(Encoder * E, int bit)
{
  E->bit_buffer >>= 1;
  if (bit) E->bit_buffer |= 0x80;
  if (--E->bit_index == 0) Output_Byte(E);
}

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

void Write_Bits(Encoder * E, int bits, int word)
{
  int m;
  for (m = 1 << (--bits); m > 0; m >>= 1) {
    E->bit_buffer >>= 1;
    if (word & m) E->bit_buffer |= 0x80;
    if (--E->bit_index == 0) Output_Byte(E); }
}

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

void Write_Symbol(Encoder * E, int s)
{
  if (E->length[s] < 2)
    Write_Bit(E, E->code[s]);
  else
    Write_Bits(E, E->length[s], E->code[s]);
}

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

long Stop_Encoder(Encoder * E)
{
  char * msg = "< Encoder > could not write to file";
  ++E->byte_counter;
  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;
}


/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
/* - - Functions of < Decoder >  - - - - - - - - - - - - - - - - - - - */

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

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

static int Decoder_Tree_Run(Decoder * D)
{
  int new_node;
  if (Read_Bit(D)) return D->shift + Read_Bits(D, D->nrep);
  new_node = ++D->nodes;
  D->trans_0[new_node] = Decoder_Tree_Run(D);
  D->trans_1[new_node] = Decoder_Tree_Run(D);
  return new_node;
}

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

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

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

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

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

  D->byte_counter = D->bit_index = 0;
}

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

int Read_Code(Decoder * D)
{
  int i, M = Read_Bits(D, 8);
  char * msg = "< Encoder >: insufficient memory";

  if (M < 3) Error("invalid number of < Huffman_Decoder> symbols");

  if (M != D->nsb) {
    if (D->nsb) free((char *) D->trans_0);
    D->nsb = M;  i = D->shift = M - 1;
    for (D->nrep = 0; i > 0; D->nrep++) i >>= 1;
    if ((D->trans_0 = (int *) malloc(M * 2 * sizeof(int))) == NULL)
      Error(msg);
    D->trans_1 = D->trans_0 + M; }

  D->nodes = 0;
  D->trans_0[0] = Decoder_Tree_Run(D);
  D->trans_1[0] = Decoder_Tree_Run(D);

  return M;
}

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

int Read_Bit(Decoder * D)
{
  int bit;
  if (!D->bit_index) Input_Byte(D);
  bit = D->bit_buffer & 1;  D->bit_buffer >>= 1;  --D->bit_index;
  return bit;
}

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

int Read_Bits(Decoder * D, int bits)
{
  int m, word = 0;
  for (m = 1 << (--bits); m; m >>= 1) {
    if (!D->bit_index) Input_Byte(D);
    if (D->bit_buffer & 1) word |= m;
    D->bit_buffer >>= 1;  --D->bit_index; }
  return word;
}

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

int Read_Symbol(Decoder * D)
{
  int node = 0;
  do {
    if (!D->bit_index) Input_Byte(D);
    node = (D->bit_buffer & 1 ? D->trans_1[node] : D->trans_0[node]);
    D->bit_buffer >>= 1;  --D->bit_index;
  } while (node < D->shift);
  return node - D->shift;
}

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

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

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

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