binary_codec.cpp

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

#endif

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

  int data = C.decd_table[bit_buffer>>C.table_shift];        // table decoding

  if (data >= 0)
    bit_buffer <<= C.length[data];                                     // done
  else {
    bit_buffer <<= C.table_bits;                 // codeword longer than table
    do {                                                     // read more bits
      data = C.tree[bit_buffer>>31][-data];
      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 = C.decd_table[bit_buffer>>C.table_shift];        // table decoding

  if (data >= 0)
    bit_buffer <<= C.length[data];                                     // done
  else {
    bit_buffer <<= C.table_bits;                 // codeword longer than table
    do {                                                     // read more bits
      data = C.tree[bit_buffer>>31][-data];
      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;
}

#endif


// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// - - Other Binary_Codec implementations  - - - - - - - - - - - - - - - - - -

Binary_Codec::Binary_Codec(void)
{
  mode = buffer_size = 0;
  new_buffer = code_buffer = 0;
}

Binary_Codec::Binary_Codec(unsigned max_code_bytes,
                           unsigned char * user_buffer)
{
  mode = buffer_size = 0;
  new_buffer = code_buffer = 0;
  set_buffer(max_code_bytes, user_buffer);
}

Binary_Codec::~Binary_Codec(void)
{
  delete [] new_buffer;
}

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

void Binary_Codec::set_buffer(unsigned max_code_bytes,
                              unsigned char * user_buffer)
{
                                                  // test for reasonable sizes
  if ((max_code_bytes < 16) || (max_code_bytes > 0x1000000U))
    HC_Error("invalid codec buffer size");
  if (mode != 0) HC_Error("cannot set buffer while encoding or decoding");

  if (user_buffer != 0) {                       // user provides memory buffer
    buffer_size = max_code_bytes;
    code_buffer = user_buffer;               // set buffer for compressed data
    delete [] new_buffer;                 // free anything previously assigned
    new_buffer = 0;
    return;
  }

  if (max_code_bytes <= buffer_size) return;               // enough available

  buffer_size = max_code_bytes;                           // assign new memory
  delete [] new_buffer;                   // free anything previously assigned
  if ((new_buffer = new unsigned char[buffer_size+8]) == 0)   // 8 extra bytes
    HC_Error("cannot assign memory for compressed data buffer");
  code_buffer = new_buffer;                  // set buffer for compressed data
}

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

void Binary_Codec::start_encoder(void)
{
  if (mode != 0) HC_Error("cannot start encoder");
  if (buffer_size == 0) HC_Error("no code buffer set");

  mode         =  1;             // initialize encoder bit-buffer and pointers
  bit_buffer   =  0;
  bit_position = 32;
  bc_pointer   = code_buffer;                     // pointer to next data byte
}

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

void Binary_Codec::start_decoder(void)
{
  if (mode != 0) HC_Error("cannot start decoder");
  if (buffer_size == 0) HC_Error("no code buffer set");

  mode         =  2;             // initialize decoder bit-buffer and pointers
  bit_buffer   =  0;
  bit_position = 32;
  bc_pointer   = code_buffer;                     // pointer to next data byte
}

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

void Binary_Codec::read_from_file(FILE * code_file)
{
  unsigned shift = 0, code_bytes = 0;
  int file_byte;
                      // read variable-length header with number of code bytes
  do {
    if ((file_byte = getc(code_file)) == EOF)
      HC_Error("cannot read code from file");
    code_bytes |= unsigned(file_byte & 0x7F) << shift;
    shift += 7;
  } while (file_byte & 0x80);
                                                       // read compressed data
  if (code_bytes > buffer_size) HC_Error("code buffer overflow");
  if (fread(code_buffer, 1, code_bytes, code_file) != code_bytes)
    HC_Error("cannot read code from file");

  start_decoder();                                       // initialize decoder
}

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

unsigned Binary_Codec::stop_encoder(void)
{
  if (mode != 1) HC_Error("invalid to stop encoder");

  mode = 0;                  // done encoding: set final data byte, reset mode

  if (bit_position < 32) *bc_pointer++ = (unsigned char) (bit_buffer >> 24);

  unsigned code_bytes = unsigned(bc_pointer - code_buffer);
  if (code_bytes > buffer_size) HC_Error("code buffer overflow");

  return code_bytes;                                   // number of bytes used
}

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

unsigned Binary_Codec::write_to_file(FILE * code_file)
{
  unsigned header_bytes = 0, code_bytes = stop_encoder(), nb = code_bytes;

                     // write variable-length header with number of code bytes
  do {
    int file_byte = int(nb & 0x7FU);
    if ((nb >>= 7) > 0) file_byte |= 0x80;
    if (putc(file_byte, code_file) == EOF)
      HC_Error("cannot write compressed data to file");
    header_bytes++;
  } while (nb);
                                                      // write compressed data
  if (fwrite(code_buffer, 1, code_bytes, code_file) != code_bytes)
    HC_Error("cannot write compressed data to file");

  return code_bytes + header_bytes;                              // bytes used
}

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

void Binary_Codec::stop_decoder(void)
{
  if (mode != 2) HC_Error("invalid to stop decoder");
  mode = 0;
}


// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// - - Static Huffman code implementation  - - - - - - - - - - - - - - - - - -

Static_Huffman_Code::Static_Huffman_Code(void)                  // constructor
{
  code_data    = 0;
  data_symbols = 0;
}

Static_Huffman_Code::~Static_Huffman_Code(void)                  // destructor
{
  delete [] code_data;
}

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

void Static_Huffman_Code::set_distribution(unsigned number_of_symbols,
                                           const double probability[])
{
  if ((number_of_symbols < 3) || (number_of_symbols > (1 << 16)))
    HC_Error("invalid number of data symbols");

  if (data_symbols != number_of_symbols) {      // assign memory for code data

    data_symbols = number_of_symbols;
    delete [] code_data;                    // free previously assigned memory

    for (table_bits = 2; (1U << table_bits) < data_symbols; ++table_bits);

    unsigned table_size = 1U << ++table_bits;
    table_shift = 32 - table_bits;
                                                   // single memory assignment
    if ((code_data = new int[table_size+4*data_symbols]) == 0)
      HC_Error("cannot assign Huffman code memory");

    decd_table = code_data;                    // define pointers to code data
    tree[0] = code_data + table_size;
    tree[1] = tree[0]   + data_symbols;
    length  = (unsigned *) (tree[1] + data_symbols);
    codeword = length + data_symbols;
  }

  unsigned n, * symbol_count = codeword;        // temporarily use this memory
  if (probability == 0)
    for (n = 0; n < data_symbols; n++)
      symbol_count[n] = 1;
  else
    for (n = 0; n < data_symbols; n++)                  // convert to integers
      symbol_count[n] = unsigned(1.0 + 1e6 * probability[n]);

                                                     // construct optimal code
  Form_Huffman_Tree(data_symbols, symbol_count, tree[0], tree[1]);
  Set_Huffman_Code(table_bits, tree, decd_table, codeword, length);
}


// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// - - Adaptive data model implementation  - - - - - - - - - - - - - - - - - -

Adaptive_Huffman_Code::Adaptive_Huffman_Code(void)             // constructors
{
  code_data    = 0;
  data_symbols = 0;
}

Adaptive_Huffman_Code::Adaptive_Huffman_Code(unsigned number_of_symbols)
{
  code_data    = 0;
  data_symbols = 0;
  set_alphabet(number_of_symbols);
}

Adaptive_Huffman_Code::~Adaptive_Huffman_Code(void)             // destructors
{
  delete [] code_data;
}

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

void Adaptive_Huffman_Code::set_alphabet(unsigned number_of_symbols)
{
  if ((number_of_symbols < 3) || (number_of_symbols > (1 << 12)))
    HC_Error("invalid number of data symbols");

  if (data_symbols != number_of_symbols) {     // assign memory for code data

    data_symbols = number_of_symbols;
    delete [] code_data;                    // free previously assigned memory

    for (table_bits = 2; (1U << table_bits) < data_symbols; ++table_bits);

    unsigned table_size = 1U << ++table_bits;
    table_shift = 32 - table_bits;
                                                   // single memory assignment
    if ((code_data = new int[table_size+5*data_symbols]) == 0)
      HC_Error("cannot assign Huffman code memory");

    decd_table = code_data;                    // define pointers to code data
    tree[0] = code_data + table_size;
    tree[1] = tree[0]   + data_symbols;
    length  = (unsigned *) (tree[1] + data_symbols);
    codeword = length + data_symbols;
    symbol_count = codeword + data_symbols;
  }

  reset();
}

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

void Adaptive_Huffman_Code::update(bool encoder)
{
  total_count += update_cycle;
  while (total_count >= HC__MaxCount)
    for (unsigned n = total_count = 0; n < data_symbols; n++)
      total_count += (symbol_count[n] = (symbol_count[n] + 1) >> 1);

                                                // compute optimal Hufman code
  Form_Huffman_Tree(data_symbols, symbol_count, tree[0], tree[1]);
  if (encoder)
    Set_Huffman_Code(tree, codeword, length);              // no decoder table
  else
    Set_Huffman_Code(table_bits, tree, decd_table, codeword, length);

  if (update_cycle < (data_symbols << 4))
    update_cycle = 1 + ((5 * update_cycle) >> 2);
  symbols_until_update = update_cycle;
}

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

void Adaptive_Huffman_Code::reset(void)
{                                                      // uniform distribution
  total_count = 0;
  for (unsigned k = 0; k < data_symbols; k++) symbol_count[k] = 1;
  update_cycle = symbols_until_update = data_symbols;
  update(false);
}

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */