binary_codec.cpp

惠普实验室的经典代码。用于huffman编码的快速实现

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
//                                                                           -
//                       *************************                           -
//                        HUFFMAN CODING EXAMPLES                            -
//                       *************************                           -
//                                                                           -
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
//                                                                           -
//   Implementation of periodic-adaptive and static Huffman codes            -
//                                                                           -
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
//                                                                           -
// Version 1.00  -  January 24, 2005                                         -
//                                                                           -
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
//                                                                           -
//                                  WARNING                                  -
//                                 =========                                 -
//                                                                           -
// The only purpose of this program is to demonstrate the basic principles   -
// of Huffman codes. It is provided as is, without any express or implied    -
// warranty, without even the warranty of fitness for any particular         -
// purpose, or that the implementations are correct.                         -
//                                                                           -
// Permission to copy and redistribute this code is hereby granted, provided -
// that this warning and copyright notices are not removed or altered.       -
//                                                                           -
// Copyright (c) 2005 by Amir Said ([e-mail]) &                         -
//                       William A. Pearlman ([e-mail])           -
//                                                                           -
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -


// - - Inclusion - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

#include <stdlib.h>
#include <string.h>
#include "binary_codec.h"


// - - Constants - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

// #define TREE_DECODE

const unsigned HC__MaxCount = 1 << 15;  // Max. symbol count for adaptive code


// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// - - Static functions  - - - - - - - - - - - - - - - - - - - - - - - - - - -

static void HC_Error(const char * msg)
{
  fprintf(stderr, "\n\n -> Huffman/binary coding error: ");
  fputs(msg, stderr);
  fputs("\n Execution terminated!\n", stderr);
  exit(1);
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

static void Form_Huffman_Tree(int number_of_symbols,
                              unsigned original_count[],
                              int left_branch[],
                              int right_branch[])
{
  int tc, ts, i, n, nc, it = 0, k = (number_of_symbols >> 1) + 1;
  int * count = right_branch - 1, * symbol = left_branch - 1;

  for (n = k - 1; n < number_of_symbols; n++) {     // second half of the heap
    symbol[n+1] = n;
    count[n+1]  = original_count[n];
  }

  for (;;) {
    if (k > 1) {
      ts = (--k) - 1;                                // add first half to heap
      tc = original_count[ts];
    }
    else
      if ((++it) & 1) {
        tc = count[n];
        ts = symbol[n];
        left_branch[--n] = symbol[1];                  // set-up merging nodes
        if (n == 1) break;
        nc = count[1];
      }
      else {
        right_branch[n] = symbol[1];                 // finalize merging nodes
        ts = -n;
        tc = nc + count[1];
      }
    for (int j = (i = k) << 1; j <= n; j += (i = j)) {            // heap sort
      if ((j < n) && (count[j] > count[j+1])) ++j;
      if (tc <= count[j]) break;
      symbol[i] = symbol[j];
      count[i]  = count[j];
    }
    symbol[i] = ts;
    count[i]  = tc;
  }
  right_branch[1] = ts;
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

static void Set_Huffman_Code(int * tree[2],
                             unsigned codeword[],
                             unsigned codeword_length[])
{
  int stack[32], node, depth = 0, current_code = 0;

  for (stack[0] = 1; depth >= 0;) {       // transverse tree setting codewords

    if ((node = tree[current_code&1][stack[depth]]) < 0)
      do {
        current_code <<= 1;
        stack[++depth] = -node;
      } while ((node = tree[0][-node]) < 0);

    codeword[node] = current_code;              // set codeword to leaf symbol
    codeword_length[node] = depth + 1;

    while (current_code & 1) {                                    // backtrack
      current_code >>= 1;
      if (--depth < 0) break;
    }
    current_code |= 1;
  }
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

static void Set_Huffman_Code(int table_bits,
                             int * tree[2],
                             int decoder_table[],
                             unsigned codeword[],
                             unsigned codeword_length[])
{
  int stack[32], node, depth = 0, current_code = 0;

  for (stack[0] = 1; depth >= 0;) {       // transverse tree setting codewords

    if ((node = tree[current_code&1][stack[depth]]) < 0)
      do {
        if (depth + 1 == table_bits) decoder_table[current_code] = node;
        current_code <<= 1;
        stack[++depth] = -node;
      } while ((node = tree[0][-node]) < 0);

    codeword[node] = current_code;              // set codeword to leaf symbol
    int nb = codeword_length[node] = depth + 1;

    if (nb <= table_bits)                      // add entries to decoder table
      if (nb == table_bits)
        decoder_table[current_code] = node;
      else {
        int db = table_bits - nb, sc = current_code << db;
        for (int k = 1 << db; k;) decoder_table[sc+--k] = node;
      }

    while (current_code & 1) {                                    // backtrack
      current_code >>= 1;
      if (--depth < 0) break;
    }
    current_code |= 1;
  }
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// - - Coding implementations  - - - - - - - - - - - - - - - - - - - - - - - -

unsigned Binary_Codec::get_bit(void)
{
#ifdef _DEBUG
  if (mode != 2) HC_Error("decoder not initialized");
#endif
                                            // refill bit buffer (32-bit word)
  while (bit_position >= 8) {
    bit_buffer |= unsigned(*bc_pointer++) << (bit_position -= 8);
  }
                       // next data bit is most-significant bit in 32-bit word
  ++bit_position;
  unsigned data = bit_buffer >> 31;
  bit_buffer <<= 1;
  return data;
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

unsigned Binary_Codec::get_bits(unsigned bits)
{
#ifdef _DEBUG
  if (mode != 2) HC_Error("decoder not initialized");
  if ((bits < 1) || (bits > 24)) HC_Error("invalid number of bits");
#endif
                                            // refill bit buffer (32-bit word)
  while (bit_position >= 8) {
    bit_buffer |= unsigned(*bc_pointer++) << (bit_position -= 8);
  }
                    // next data bits are most-significant bits in 32-bit word
  bit_position += bits;
  unsigned data = bit_buffer >> (32 - bits);
  bit_buffer <<= bits;
  return data;
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

void Binary_Codec::put_bit(unsigned bit)
{
#ifdef _DEBUG
  if (mode != 1) HC_Error("encoder not initialized");
#endif
                      // save data bit in most-significant bits of 32-bit word
  --bit_position;
  if (bit) bit_buffer |= 1U << bit_position;
  if (bit_position <= 24)                    // empty bit buffer (32-bit word)
    do {
      *bc_pointer++ = (unsigned char) (bit_buffer >> 24);
      bit_buffer <<= 8;
    } while ((bit_position += 8) <= 24);
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

void Binary_Codec::put_bits(unsigned data,
                            unsigned bits)
{
#ifdef _DEBUG
  if (mode != 1) HC_Error("encoder not initialized");
  if ((bits < 1) || (bits > 24)) HC_Error("invalid number of bits");
  if (data >= (1U << bits)) HC_Error("invalid data");
#endif
                     // save data bits in most-significant bits of 32-bit word
  bit_buffer |= data << (bit_position -= bits);
  if (bit_position <= 24)                    // empty bit buffer (32-bit word)
    do {
      *bc_pointer++ = (unsigned char) (bit_buffer >> 24);
      bit_buffer <<= 8;
    } while ((bit_position += 8) <= 24);
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

void Binary_Codec::encode(unsigned data,
                          Static_Huffman_Code & C)
{
#ifdef _DEBUG
  if (mode != 1) HC_Error("encoder not initialized");
  if (data >= C.data_symbols) HC_Error("invalid data symbol");
#endif

  bit_buffer |= C.codeword[data] << (bit_position -= C.length[data]);  // code
  if (bit_position <= 24)
    do {                                                   // save bytes ready
      *bc_pointer++ = (unsigned char) (bit_buffer >> 24);
      bit_buffer <<= 8;
    } while ((bit_position += 8) <= 24);
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

void Binary_Codec::encode(unsigned data,
                          Adaptive_Huffman_Code & C)
{
#ifdef _DEBUG
  if (mode != 1) HC_Error("encoder not initialized");
  if (data >= C.data_symbols) HC_Error("invalid data symbol");
#endif

  bit_buffer |= C.codeword[data] << (bit_position -= C.length[data]);  // code
  if (bit_position <= 24)
    do {                                                   // save bytes ready
      *bc_pointer++ = (unsigned char) (bit_buffer >> 24);
      bit_buffer <<= 8;
    } while ((bit_position += 8) <= 24);

  ++C.symbol_count[data];                          // update symbol statistics
  if (--C.symbols_until_update == 0) C.update(true);    // periodic adaptation
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

#ifdef TREE_DECODE

unsigned Binary_Codec::decode(Static_Huffman_Code & C)
{
#ifdef _DEBUG
  if (mode != 2) HC_Error("decoder not initialized");
#endif

  while (bit_position >= 8)                                     // fill buffer
    bit_buffer |= unsigned(*bc_pointer++) << (bit_position -= 8);

  int data = -1;

  do {
    data = C.tree[bit_buffer>>31][-data];               // bit-by-bit decoding
    bit_buffer <<= 1;
  } while (data < 0);

  bit_position += C.length[data];

  return data;
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

unsigned Binary_Codec::decode(Adaptive_Huffman_Code & C)
{
#ifdef _DEBUG
  if (mode != 2) HC_Error("decoder not initialized");
#endif

  while (bit_position >= 8)                                     // fill buffer
    bit_buffer |= unsigned(*bc_pointer++) << (bit_position -= 8);

  int data = -1;

  do {
    data = C.tree[bit_buffer>>31][-data];               // bit-by-bit decoding
    bit_buffer <<= 1;
  } while (data < 0);

  bit_position += C.length[data];

  ++C.symbol_count[data];                          // update symbol statistics
  if (--C.symbols_until_update == 0) C.update(false);   // periodic adaptation

  return data;
}

#else

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

unsigned Binary_Codec::decode(Static_Huffman_Code & C)
{
#ifdef _DEBUG
  if (mode != 2) HC_Error("decoder not initialized");