arithmetic_codec.cpp

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

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)
{
  least_probable_bit = 0;
  shift_a = shift_b = 2;                                           // pm = 0.5
}

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

void Static_Bit_Model::set_probability_0(double p0)
{
  if ((p0 < 0.0001)||(p0 > 0.9999)) AC_Error("invalid bit probability");

  if (p0 < 0.5)                                   // define least probable bit
    least_probable_bit = 0;
  else {
    least_probable_bit = 1;
    p0 = 1.0 - p0;
  }
  
  const double ProbThr[64] = {                       // probability thresholds
    1.000000000, 0.436829205, 0.343297135, 0.296716418,
    0.265429157, 0.217670149, 0.171498704, 0.148324226,
    0.132682629, 0.108718131, 0.085722481, 0.074155662,
    0.066335033, 0.054334924, 0.042855429, 0.037076405,
    0.033166108, 0.027161937, 0.021426357, 0.018537866,
    0.016582720, 0.013579645, 0.010712850, 0.009268851,
    0.008291278, 0.006789498, 0.005356344, 0.004634405,
    0.004145619, 0.003394669, 0.002678152, 0.002317198,
    0.002072805, 0.001697315, 0.001339071, 0.001158598,
    0.001036401, 0.000848652, 0.000669534, 0.000579299,
    0.000518200, 0.000424325, 0.000334767, 0.000289649,
    0.000259100, 0.000212162, 0.000167383, 0.000144825,
    0.000129550, 0.000106081, 0.000083692, 0.000072412,
    0.000064775, 0.000053040, 0.000041846, 0.000036206,
    0.000032387, 0.000026520, 0.000020923, 0.000018103,
    0.000016194, 0.000013260, 0.000010461, 0.000009052 };

  unsigned u = 0, n = 64, m = 32;         // find optimal values of bit shifts

  do {
    if (p0 < ProbThr[m])
      u = m;
    else
      n = m;
  } while ((m = (u + n) >> 1) != u);

  shift_a = 2 + (u >> 2);
  shift_b = shift_a + (u & 0x3);
}


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

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

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

void Adaptive_Bit_Model::reset(void)
{
                                       // initialization to equiprobable model
  least_probable_bit  = 0;
  lpb_count = 1;
  bit_count = 2;
  mpb_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 top threshold is reached

  if ((bit_count += update_cycle) >= BM__MaxCount) {
    bit_count = (bit_count + 1) >> 1;
    lpb_count = (lpb_count + 1) >> 1;
    if (lpb_count == bit_count) ++bit_count;
  }
                                                     // test most probable bit
  unsigned mpb_count = bit_count - lpb_count;
  if (mpb_count < lpb_count) {
    mpb_count = lpb_count;
    lpb_count = bit_count - mpb_count;
    least_probable_bit ^= 1;
  }
                                           // compute scaled bit 0 probability
  unsigned scale = 0x80000000U / bit_count;
  mpb_prob = (mpb_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;
    most_probable_symbol = data_symbols - 1;
    delete [] distribution;
    distribution = new unsigned[3*data_symbols];
    rank = distribution + data_symbols;
    data = rank + data_symbols;
    if (distribution == 0) AC_Error("cannot assign model memory");
  }
                           // sort symbols by probability using insertion sort
  unsigned i, k;
  double p = 1.0 / double(data_symbols);     // value for uniform distribution

  if (probability == 0)
    for (k = 0; k < data_symbols; k++) data[k] = k;
  else 
    for (k = 0; k < data_symbols; k++) {
      unsigned s = k;
      double t = probability[k];
      for (i = k; i > 0; i--) {
        if (t >= probability[data[i-1]]) break;
        data[i] = data[i-1];
      }
      data[i] = s;
    }
                               // compute cumulative distribution, first tests
  unsigned c = 0;
  double sum = 0.0, threshold = 0.26;

  for (i = 0; i < data_symbols; i++) {
    k = data[i];
    rank[k] = i;
    if (probability) p = probability[k];
    if ((p < 0.0001) || (p > 0.9999)) AC_Error("invalid symbol probability");
    distribution[i] = unsigned(sum * (1 << DM__LengthShift));
    sum += p;
    while (sum > threshold) {
      first_tests[c++] = i;
      threshold += 0.25;
    }
  }
  if (first_tests[0] == first_tests[1]) --first_tests[0]; 

  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;
    most_probable_symbol = data_symbols - 1;
    delete [] distribution;
    distribution = new unsigned[4*data_symbols];
    symbol_count = distribution + data_symbols;
    rank = symbol_count + data_symbols;
    data = rank + data_symbols;
    if (distribution == 0) AC_Error("cannot assign model memory");
  }

  reset();                                                 // initialize model
}

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

void Adaptive_Data_Model::update(void)
{
                               // halve counts when a top 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);
  }

  unsigned i, k;                                  // update sorting of symbols

  for (k = 1; k < data_symbols; k++)
    if (symbol_count[k] < symbol_count[k-1]) {
      unsigned t = symbol_count[k];
      symbol_count[k]  = symbol_count[k-1];
      unsigned s = data[k];
      data[k] = data[k-1];
      for (i = k - 1; i > 0; i--) {
        if (t >= symbol_count[i-1]) break;
        symbol_count[i]  = symbol_count[i-1];
        data[i] = data[i-1];
      }
      symbol_count[i]  = t;
      data[i] = s;
    }
                               // compute cumulative distribution, first tests
  unsigned sum = 0, c = 0;
  unsigned d = (total_count + 3) >> 2, threshold = d + 1;
  unsigned scale = 0x80000000U / total_count;

  for (i = 0; i < data_symbols; i++) {
    rank[data[i]] = i;
    distribution[i] = (scale * sum) >> (31 - DM__LengthShift);
    sum += symbol_count[i];
    while (sum > threshold) {
      first_tests[c++] = i;
      threshold += d;
    }
  }
  if (first_tests[0] == first_tests[1]) --first_tests[0]; 

                                             // 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++) {
    data[k] = k;
    symbol_count[k] = 1;
  }
  update();
  symbols_until_update = update_cycle = (data_symbols + 6) >> 1;
}

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