codec_test.cpp

算术编码的仿真实例

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
//                                                                           -
//                       ****************************                        -
//                        ARITHMETIC CODING EXAMPLES                         -
//                       ****************************                        -
//                                                                           -
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
//                                                                           -
// Functions to test and benchmark the arithmetic coding implementations     -
//                                                                           -
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
//                                                                           -
// Version 1.00  -  April 25, 2004                                           -
//                                                                           -
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
//                                                                           -
//                                  WARNING                                  -
//                                 =========                                 -
//                                                                           -
// The only purpose of this program is to demonstrate the basic principles   -
// of arithmetic coding. 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) 2004 by Amir Said ([e-mail]) &                         -
//                       William A. Pearlman ([e-mail])           -
//                                                                           -
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
//                                                                           -
// Analysis of coding complexity done with a similar program is available at -
//                                                                           -
// A. Said, Comparative Analysis of Arithmetic Coding Comput. Complexity     -
// HP Labs report HPL-2004-75  -  http://www.hpl.hp.com/techreports/         -
//                                                                           -
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -


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

#include <math.h>
#include <stdlib.h>

#include "test_support.h"
#include "arithmetic_codec.h"


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

const unsigned SimulTests = 1000000;


// - - Definitions - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

struct Test_Result
{
  unsigned alphabet_symbols;
  double   encoder_time, decoder_time;
  double   entropy, bits_used, test_symbols;
};


// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// - - Implementations for testing encoder/decoder - - - - - - - - - - - - - -

unsigned Encode_Bit_Buffer(unsigned char bit_buffer[],
                           Static_Bit_Model & model,
                           Arithmetic_Codec & encoder)
{
  encoder.start_encoder();
  for (unsigned k = 0; k < SimulTests; k++)
    encoder.encode(unsigned(bit_buffer[k]), model);
  return 8 * encoder.stop_encoder();
}

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

void Decode_Bit_Buffer(unsigned char bit_buffer[],
                       Static_Bit_Model & model,
                       Arithmetic_Codec & decoder)
{
  decoder.start_decoder();
  for (unsigned k = 0; k < SimulTests; k++)
    bit_buffer[k] = unsigned char(decoder.decode(model));
  decoder.stop_decoder();
}

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

unsigned Encode_Bit_Buffer(unsigned char bit_buffer[],
                           Adaptive_Bit_Model & model,
                           Arithmetic_Codec & encoder)
{
  encoder.start_encoder();
  for (unsigned k = 0; k < SimulTests; k++)
    encoder.encode(unsigned(bit_buffer[k]), model);
  return 8 * encoder.stop_encoder();
}

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

void Decode_Bit_Buffer(unsigned char bit_buffer[],
                       Adaptive_Bit_Model & model,
                       Arithmetic_Codec & decoder)
{
  decoder.start_decoder();
  for (unsigned k = 0; k < SimulTests; k++)
    bit_buffer[k] = unsigned char(decoder.decode(model));
  decoder.stop_decoder();
}

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

unsigned Encode_Data_Buffer(unsigned short data_buffer[],
                            Static_Data_Model & model,
                            Arithmetic_Codec & encoder)
{
  encoder.start_encoder();
  for (unsigned k = 0; k < SimulTests; k++)
    encoder.encode(unsigned(data_buffer[k]), model);
  return 8 * encoder.stop_encoder();
}

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

void Decode_Data_Buffer(unsigned short data_buffer[],
                        Static_Data_Model & model,
                        Arithmetic_Codec & decoder)
{
  decoder.start_decoder();
  for (unsigned k = 0; k < SimulTests; k++)
    data_buffer[k] = unsigned short(decoder.decode(model));
  decoder.stop_decoder();
}

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

unsigned Encode_Data_Buffer(unsigned short data_buffer[],
                            Adaptive_Data_Model & model,
                            Arithmetic_Codec & encoder)
{
  encoder.start_encoder();
  for (unsigned k = 0; k < SimulTests; k++)
    encoder.encode(unsigned(data_buffer[k]), model);
  return 8 * encoder.stop_encoder();
}

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

void Decode_Data_Buffer(unsigned short data_buffer[],
                        Adaptive_Data_Model & model,
                        Arithmetic_Codec & decoder)
{
  decoder.start_decoder();
  for (unsigned k = 0; k < SimulTests; k++)
    data_buffer[k] = unsigned short(decoder.decode(model));
  decoder.stop_decoder();
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  
void Fill_Bit_Buffer(Random_Bit_Source & src,
                     unsigned char bit_buffer[])
{
  src.shuffle_probabilities();
  for (unsigned k = 0; k < SimulTests; k++)
    bit_buffer[k] = unsigned char(src.bit());
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  
void Fill_Data_Buffer(Random_Data_Source & src,
                      unsigned short data_buffer[])
{
  src.shuffle_probabilities();
  for (unsigned k = 0; k < SimulTests; k++)
    data_buffer[k] = unsigned short(src.data());
}

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

void Display_Results(bool first,
                     bool adaptive,
                     Test_Result & pr,
                     double source_time)
{
  if (adaptive)
    puts(" Test with adaptive model\n");
  else {
    if (first)
      puts("\n==============================================================="
        "==========");
    puts(" Test with static model\n");
  }

  printf(" Random  data generated in %5.2f seconds\n", source_time);
  printf(" Encoder test completed in %5.2f seconds\n", pr.encoder_time);
  printf(" Decoder test completed in %5.2f seconds\n", pr.decoder_time);

  printf("\n Used %g bytes for coding %g symbols\n",
    0.125 * pr.bits_used, pr.test_symbols);
    
  printf(" Data source entropy = %8.5f bits/symbol [%d symbols]\n",
    pr.entropy, pr.alphabet_symbols);

  double bit_rate = pr.bits_used / pr.test_symbols;
  printf(" Compression rate    = %8.5f bits/symbol (%9.4f %% redundancy)\n\n",
    bit_rate, 100.0 * (bit_rate - pr.entropy) / pr.entropy);

  printf(" Encoding time  = %8.3f ns/symbol  = %8.3f ns/bit\n",
    1e9 * pr.encoder_time / pr.test_symbols,
    1e9 * pr.encoder_time / pr.bits_used);

  printf(" Decoding time  = %8.3f ns/symbol  = %8.3f ns/bit\n",
    1e9 * pr.decoder_time / pr.test_symbols,
    1e9 * pr.decoder_time / pr.bits_used);

  printf(" Encoding speed = %8.3f Msymbols/s = %8.3f Mbits/s\n",
    1e-6 * pr.test_symbols / pr.encoder_time,