arithmetic_codec.cpp

算术编码快速算法文档和源代码

    length = AC__MinLength >> 1;             // set new length for 1 more byte
  }
  else {
    base  += AC__MinLength >> 1;                                // base offset
    length = AC__MinLength >> 9;            // set new length for 2 more bytes
  }

  if (init_base > base) propagate_carry();                 // overflow = carry

  renorm_enc_interval();                // renormalization = output last bytes

  unsigned code_bytes = unsigned(ac_pointer - code_buffer);
  if (code_bytes > buffer_size) AC_Error("code buffer overflow");

  return code_bytes;                                   // number of bytes used
}

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

unsigned Arithmetic_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)
      AC_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)
    AC_Error("cannot write compressed data to file");

  return code_bytes + header_bytes;                              // bytes used
}

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

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


// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// - Static bit model implementation - - - - - - - - - - - - - - - - - - - - -

Static_Bit_Model::Static_Bit_Model(void)
{
  bit_0_prob = 1U << (BM__LengthShift - 1);                        // p0 = 0.5
}

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

void Static_Bit_Model::set_probability_0(double p0)
{
  if ((p0 < 0.0001)||(p0 > 0.9999)) AC_Error("invalid bit probability");
  bit_0_prob = unsigned(p0 * (1 << BM__LengthShift));
}


// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// - Adaptive bit model implementation - - - - - - - - - - - - - - - - - - - -

Adaptive_Bit_Model::Adaptive_Bit_Model(void)
{
  reset();
}

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

void Adaptive_Bit_Model::reset(void)
{
                                       // initialization to equiprobable model
  bit_0_count = 1;
  bit_count   = 2;
  bit_0_prob  = 1U << (BM__LengthShift - 1);
  update_cycle = bits_until_update = 4;         // start with frequent updates
}

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

void Adaptive_Bit_Model::update(void)
{
                                   // halve counts when a threshold is reached

  if ((bit_count += update_cycle) > BM__MaxCount) {
    bit_count = (bit_count + 1) >> 1;
    bit_0_count = (bit_0_count + 1) >> 1;
    if (bit_0_count == bit_count) ++bit_count;
  }
                                           // compute scaled bit 0 probability
  unsigned scale = 0x80000000U / bit_count;
  bit_0_prob = (bit_0_count * scale) >> (31 - BM__LengthShift);

                                             // set frequency of model updates
  update_cycle = (5 * update_cycle) >> 2;
  if (update_cycle > 64) update_cycle = 64;
  bits_until_update = update_cycle;
}


// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// - - Static data model implementation  - - - - - - - - - - - - - - - - - - -

Static_Data_Model::Static_Data_Model(void)
{
  data_symbols = 0;
  distribution = 0;
}

Static_Data_Model::~Static_Data_Model(void)
{
  delete [] distribution;
}

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

void Static_Data_Model::set_distribution(unsigned number_of_symbols,
                                         const double probability[])
{
  if ((number_of_symbols < 2) || (number_of_symbols > (1 << 11)))
    AC_Error("invalid number of data symbols");

  if (data_symbols != number_of_symbols) {     // assign memory for data model
    data_symbols = number_of_symbols;
    last_symbol = data_symbols - 1;
    delete [] distribution;
                                     // define size of table for fast decoding
    if (data_symbols > 16) {
      unsigned table_bits = 3;
      while (data_symbols > (1U << (table_bits + 2))) ++table_bits;
      table_size  = (1 << table_bits) + 4;
      table_shift = DM__LengthShift - table_bits;
      distribution = new unsigned[data_symbols+table_size+6];
      decoder_table = distribution + data_symbols;
    }
    else {                                  // small alphabet: no table needed
      decoder_table = 0;
      table_size = table_shift = 0;
      distribution = new unsigned[data_symbols];
    }
    if (distribution == 0) AC_Error("cannot assign model memory");
  }
                             // compute cumulative distribution, decoder table
  unsigned s = 0;
  double sum = 0.0, p = 1.0 / double(data_symbols);

  for (unsigned k = 0; k < data_symbols; k++) {
    if (probability) p = probability[k];
    if ((p < 0.0001) || (p > 0.9999)) AC_Error("invalid symbol probability");
    distribution[k] = unsigned(sum * (1 << DM__LengthShift));
    sum += p;
    if (table_size == 0) continue;
    unsigned w = distribution[k] >> table_shift;
    while (s < w) decoder_table[++s] = k - 1;
  }

  if (table_size != 0) {
    decoder_table[0] = 0;
    while (s <= table_size) decoder_table[++s] = data_symbols - 1;
  }

  if ((sum < 0.9999) || (sum > 1.0001)) AC_Error("invalid probabilities");
}

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

Adaptive_Data_Model::Adaptive_Data_Model(void)
{
  data_symbols = 0;
  distribution = 0;
}

Adaptive_Data_Model::Adaptive_Data_Model(unsigned number_of_symbols)
{
  data_symbols = 0;
  distribution = 0;
  set_alphabet(number_of_symbols);
}

Adaptive_Data_Model::~Adaptive_Data_Model(void)
{
  delete [] distribution;
}

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

void Adaptive_Data_Model::set_alphabet(unsigned number_of_symbols)
{
  if ((number_of_symbols < 2) || (number_of_symbols > (1 << 11)))
    AC_Error("invalid number of data symbols");

  if (data_symbols != number_of_symbols) {     // assign memory for data model
    data_symbols = number_of_symbols;
    last_symbol = data_symbols - 1;
    delete [] distribution;
                                     // define size of table for fast decoding
    if (data_symbols > 16) {
      unsigned table_bits = 3;
      while (data_symbols > (1U << (table_bits + 2))) ++table_bits;
      table_size  = (1 << table_bits) + 4;
      table_shift = DM__LengthShift - table_bits;
      distribution = new unsigned[2*data_symbols+table_size+6];
      decoder_table = distribution + 2 * data_symbols;
    }
    else {                                  // small alphabet: no table needed
      decoder_table = 0;
      table_size = table_shift = 0;
      distribution = new unsigned[2*data_symbols];
    }
    symbol_count = distribution + data_symbols;
    if (distribution == 0) AC_Error("cannot assign model memory");
  }

  reset();                                                 // initialize model
}

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

void Adaptive_Data_Model::update(bool from_encoder)
{
                                   // halve counts when a threshold is reached

  if ((total_count += update_cycle) > DM__MaxCount) {
    total_count = 0;
    for (unsigned n = 0; n < data_symbols; n++)
      total_count += (symbol_count[n] = (symbol_count[n] + 1) >> 1);
  }
                             // compute cumulative distribution, decoder table
  unsigned k, sum = 0, s = 0;
  unsigned scale = 0x80000000U / total_count;

  if (from_encoder || (table_size == 0))
    for (k = 0; k < data_symbols; k++) {
      distribution[k] = (scale * sum) >> (31 - DM__LengthShift);
      sum += symbol_count[k];
    }
  else {
    for (k = 0; k < data_symbols; k++) {
      distribution[k] = (scale * sum) >> (31 - DM__LengthShift);
      sum += symbol_count[k];
      unsigned w = distribution[k] >> table_shift;
      while (s < w) decoder_table[++s] = k - 1;
    }
    decoder_table[0] = 0;
    while (s <= table_size) decoder_table[++s] = data_symbols - 1;
  }
                                             // set frequency of model updates
  update_cycle = (5 * update_cycle) >> 2;
  unsigned max_cycle = (data_symbols + 6) << 3;
  if (update_cycle > max_cycle) update_cycle = max_cycle;
  symbols_until_update = update_cycle;
}

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

void Adaptive_Data_Model::reset(void)
{
  if (data_symbols == 0) return;

                      // restore probability estimates to uniform distribution
  total_count = 0;
  update_cycle = data_symbols;
  for (unsigned k = 0; k < data_symbols; k++) symbol_count[k] = 1;
  update(false);
  symbols_until_update = update_cycle = (data_symbols + 6) >> 1;
}

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