arithmetic_codec.cpp

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

                              Static_Data_Model & M)
{
#ifdef _DEBUG
  if (mode != 1) AC_Error("encoder not initialized");
  if (data >= M.data_symbols) AC_Error("invalid data symbol");
#endif

  unsigned x, init_base = base;
                                                           // compute products
  if (data == M.last_symbol) {
    x = M.distribution[data] * (length >> DM__LengthShift);
    base   += x;                                            // update interval
    length -= x;                                          // no product needed
  }
  else {
    x = M.distribution[data] * (length >>= DM__LengthShift);
    base   += x;                                            // update interval
    length  = M.distribution[data+1] * length - x;
  }
             
  if (init_base > base) propagate_carry();                 // overflow = carry

  if (length < AC__MinLength) renorm_enc_interval();        // renormalization
}

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

unsigned Arithmetic_Codec::decode(Static_Data_Model & M)
{
#ifdef _DEBUG
  if (mode != 2) AC_Error("decoder not initialized");
#endif

  unsigned n, s, x, y = length;

  if (M.decoder_table) {              // use table look-up for faster decoding

    unsigned dv = value / (length >>= DM__LengthShift);
    unsigned t = dv >> M.table_shift;

    s = M.decoder_table[t];         // initial decision based on table look-up
    n = M.decoder_table[t+1] + 1;

    while (n > s + 1) {                        // finish with bisection search
      unsigned m = (s + n) >> 1;
      if (M.distribution[m] > dv) n = m; else s = m;
    }
                                                           // compute products
    x = M.distribution[s] * length;
    if (s != M.last_symbol) y = M.distribution[s+1] * length;
  }

  else {                                  // decode using only multiplications

    x = s = 0;
    length >>= DM__LengthShift;
    unsigned m = (n = M.data_symbols) >> 1;
                                                // decode via bisection search
    do {
      unsigned z = length * M.distribution[m];
      if (z > value) {
        n = m;
        y = z;                                             // value is smaller
      }
      else {
        s = m;
        x = z;                                     // value is larger or equal
      }
    } while ((m = (s + n) >> 1) != s);
  }

  value -= x;                                               // update interval
  length = y - x;

  if (length < AC__MinLength) renorm_dec_interval();        // renormalization

  return s;
}

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

void Arithmetic_Codec::encode(unsigned data,
                              Adaptive_Data_Model & M)
{
#ifdef _DEBUG
  if (mode != 1) AC_Error("encoder not initialized");
  if (data >= M.data_symbols) AC_Error("invalid data symbol");
#endif

  unsigned x, init_base = base;
                                                           // compute products
  if (data == M.last_symbol) {
    x = M.distribution[data] * (length >> DM__LengthShift);
    base   += x;                                            // update interval
    length -= x;                                          // no product needed
  }
  else {
    x = M.distribution[data] * (length >>= DM__LengthShift);
    base   += x;                                            // update interval
    length  = M.distribution[data+1] * length - x;
  }

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

  if (length < AC__MinLength) renorm_enc_interval();        // renormalization

  ++M.symbol_count[data];
  if (--M.symbols_until_update == 0) M.update(true);  // periodic model update
}

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

unsigned Arithmetic_Codec::decode(Adaptive_Data_Model & M)
{
#ifdef _DEBUG
  if (mode != 2) AC_Error("decoder not initialized");
#endif

  unsigned n, s, x, y = length;

  if (M.decoder_table) {              // use table look-up for faster decoding

    unsigned dv = value / (length >>= DM__LengthShift);
    unsigned t = dv >> M.table_shift;

    s = M.decoder_table[t];         // initial decision based on table look-up
    n = M.decoder_table[t+1] + 1;

    while (n > s + 1) {                        // finish with bisection search
      unsigned m = (s + n) >> 1;
      if (M.distribution[m] > dv) n = m; else s = m;
    }
                                                           // compute products
    x = M.distribution[s] * length;
    if (s != M.last_symbol) y = M.distribution[s+1] * length;
  }

  else {                                  // decode using only multiplications

    x = s = 0;
    length >>= DM__LengthShift;
    unsigned m = (n = M.data_symbols) >> 1;
                                                // decode via bisection search
    do {
      unsigned z = length * M.distribution[m];
      if (z > value) {
        n = m;
        y = z;                                             // value is smaller
      }
      else {
        s = m;
        x = z;                                     // value is larger or equal
      }
    } while ((m = (s + n) >> 1) != s);
  }

  value -= x;                                               // update interval
  length = y - x;

  if (length < AC__MinLength) renorm_dec_interval();        // renormalization

  ++M.symbol_count[s];
  if (--M.symbols_until_update == 0) M.update(false);  // periodic model update

  return s;
}


// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// - - Other Arithmetic_Codec implementations  - - - - - - - - - - - - - - - -

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

Arithmetic_Codec::Arithmetic_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);
}

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

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

void Arithmetic_Codec::set_buffer(unsigned max_code_bytes,
                                  unsigned char * user_buffer)
{
                                                  // test for reasonable sizes
  if ((max_code_bytes < 16) || (max_code_bytes > 0x1000000U))
    AC_Error("invalid codec buffer size");
  if (mode != 0) AC_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+16]) == 0) // 16 extra bytes
    AC_Error("cannot assign memory for compressed data buffer");
  code_buffer = new_buffer;                  // set buffer for compressed data
}

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

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

  mode   = 1;
  base   = 0;            // initialize encoder variables: interval and pointer
  length = AC__MaxLength;
  ac_pointer = code_buffer;                       // pointer to next data byte
}

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

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

                  // initialize decoder: interval, pointer, initial code value
  mode   = 2;
  length = AC__MaxLength;
  ac_pointer = code_buffer + 3;
  value = (unsigned(code_buffer[0]) << 24)|(unsigned(code_buffer[1]) << 16) |
          (unsigned(code_buffer[2]) <<  8)| unsigned(code_buffer[3]);
}

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

void Arithmetic_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)
      AC_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) AC_Error("code buffer overflow");
  if (fread(code_buffer, 1, code_bytes, code_file) != code_bytes)
    AC_Error("cannot read code from file");

  start_decoder();                                       // initialize decoder
}

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

unsigned Arithmetic_Codec::stop_encoder(void)
{
  if (mode != 1) AC_Error("invalid to stop encoder");
  mode = 0;

  unsigned init_base = base;            // done encoding: set final data bytes

  if (length > 2 * AC__MinLength) {
    base  += AC__MinLength;                                     // base offset