📄 arithmetic_codec.cpp
字号:
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// -
// **************************** -
// ARITHMETIC CODING EXAMPLES -
// **************************** -
// -
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// -
// Fast arithmetic coding implementation -
// -> double-precision floating-point arithmetic -
// -
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// -
// 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 (said@ieee.org) & -
// William A. Pearlman (pearlw@ecse.rpi.edu) -
// -
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// -
// A description of the arithmetic coding method used here is available in -
// -
// Lossless Compression Handbook, ed. K. Sayood -
// Chapter 5: Arithmetic Coding (A. Said), pp. 101-152, Academic Press, 2003 -
// -
// A. Said, Introduction to Arithetic Coding Theory and Practice -
// HP Labs report HPL-2004-76 - http://www.hpl.hp.com/techreports/ -
// -
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// - - Inclusion - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
#include <math.h>
#include <stdlib.h>
#include "arithmetic_codec.h"
// - - Constants - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// This encoder saves data 2 bytes a time: renormalization factor = 2^16
const double AC__OutputFactor = double(0x10000); // D = 2^16
const double AC__MinLength = 1.0 / double(0x10000); // 1/D = 2^-16
const double AC__LeastSignifBit = 1.0 / double(0x1000000) / double(0x1000000);
const double AC__Leakage = 2.0 * AC__LeastSignifBit;
const unsigned BM__MaxCount = 1 << 14; // Maximum bit count for Bit_Model
const unsigned DM__MaxCount = 1 << 17; // Maximum symbol count for Data_Model
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// - - Static functions - - - - - - - - - - - - - - - - - - - - - - - - - - -
static void AC_Error(const char * msg)
{
fprintf(stderr, "\n\n -> Arithmetic coding error: ");
fputs(msg, stderr);
fputs("\n Execution terminated!\n", stderr);
exit(1);
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// - - Coding implementations - - - - - - - - - - - - - - - - - - - - - - - -
inline void Arithmetic_Codec::propagate_carry(void)
{
base -= 1.0; // carry propagation on compressed data buffer
unsigned char * p;
for (p = ac_pointer - 1; *p == 0xFFU; p--) *p = 0;
++*p;
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
inline void Arithmetic_Codec::renorm_enc_interval(void)
{
// rescale arithmetic encoder interval, output data bytes
do {
unsigned a = unsigned(base *= AC__OutputFactor);
*ac_pointer++ = (unsigned char) (a >> 8);
*ac_pointer++ = (unsigned char) (a & 0xFF);
base -= double(a);
} while ((length *= AC__OutputFactor) <= AC__MinLength);
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
inline void Arithmetic_Codec::renorm_dec_interval(void)
{
// rescale arithmetic decoder interval, input data bytes
do {
unsigned a = unsigned(base *= AC__OutputFactor);
base -= double(a);
value = (AC__OutputFactor * value - double(a)) + AC__LeastSignifBit *
(256.0 * double(ac_pointer[0]) + double(ac_pointer[1]));
ac_pointer += 2;
} while ((length *= AC__OutputFactor) <= AC__MinLength);
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
void Arithmetic_Codec::put_bit(unsigned bit)
{
#ifdef _DEBUG
if (mode != 1) AC_Error("encoder not initialized");
#endif
// encode assuming p0 = p1 = 1/2
double x = 0.5 * length; // compute middle point
if (bit == 0) // update interval base and length
length = x;
else {
base += x;
length -= x;
if (base >= 1.0) propagate_carry(); // check if carry bit
}
if ((length -= AC__Leakage) <= AC__MinLength) // if renormalization time
renorm_enc_interval();
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
unsigned Arithmetic_Codec::get_bit(void)
{
#ifdef _DEBUG
if (mode != 2) AC_Error("decoder not initialized");
#endif
double x = 0.5 * length; // compute interval middle point
unsigned bit = (value + AC__LeastSignifBit >= base + x); // decode bit value
if (bit == 0) // update interval base and length
length = x;
else {
base += x;
length -= x;
if (base >= 1.0) { // decoder does not propagate carry
base -= 1.0; // shift interval
value -= 1.0;
}
}
if ((length -= AC__Leakage) <= AC__MinLength) // if renormalization time
renorm_dec_interval();
return bit; // return data bit value
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
void Arithmetic_Codec::put_bits(unsigned data,
unsigned bits)
{
#ifdef _DEBUG
if (mode != 1) AC_Error("encoder not initialized");
if ((bits < 1) || (bits > 20)) AC_Error("invalid number of bits");
if (data >= (1U << bits)) AC_Error("invalid data");
#endif
unsigned symbols = 1U << bits; // alphabet size
double y, d = length / symbols; // assume uniform distribution
// compute products
if (data == symbols - 1)
y = base + length; // avoid multiplication by 1
else
y = base + d * (data + 1);
// set new interval
base += d * data;
length = y - base;
if (base >= 1.0) propagate_carry(); // check if carry bit
if ((length -= AC__Leakage) <= AC__MinLength) // if renormalization time
renorm_enc_interval();
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
unsigned Arithmetic_Codec::get_bits(unsigned bits)
{
#ifdef _DEBUG
if (mode != 2) AC_Error("decoder not initialized");
if ((bits < 1) || (bits > 20)) AC_Error("invalid number of bits");
#endif
unsigned s = 0, n = 1U << bits, m = n >> 1;
double x = base, y = base + length, d = length / n;
double shifted_value = value + AC__LeastSignifBit;
// bissection search of index in arithmetic coding interval
do {
double z = base + d * m;
if (z > shifted_value) {
y = z; // code value is smaller
n = m;
}
else {
x = z; // code value is larger or equal
s = m;
}
} while ((m = (s + n) >> 1) != s);
// set new interval
base = x;
length = y - x;
if (base >= 1.0) { // decoder does not propagate carry
base -= 1.0; // shift interval
value -= 1.0;
}
if ((length -= AC__Leakage) <= AC__MinLength) // if renormalization time
renorm_dec_interval();
return s;
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
void Arithmetic_Codec::encode(unsigned bit,
Static_Bit_Model & M)
{
#ifdef _DEBUG
if (mode != 1) AC_Error("encoder not initialized");
#endif
double x = length * M.bit_0_prob; // compute product l x p0
if (bit == 0) // update interval base and length
length = x;
else {
base += x;
length -= x;
if (base >= 1.0) propagate_carry(); // check if carry bit
}
if ((length -= AC__Leakage) <= AC__MinLength) // if renormalization time
renorm_enc_interval();
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
unsigned Arithmetic_Codec::decode(Static_Bit_Model & M)
{
#ifdef _DEBUG
if (mode != 2) AC_Error("decoder not initialized");
#endif
double x = length * M.bit_0_prob; // compute interval-division point
unsigned bit = (value + AC__LeastSignifBit >= base + x); // decode bit value
if (bit == 0) // update interval base and length
length = x;
else {
base += x;
length -= x;
if (base >= 1.0) { // decoder does not propagate carry
base -= 1.0; // shift interval
value -= 1.0;
}
}
if ((length -= AC__Leakage) <= AC__MinLength) // if renormalization time
renorm_dec_interval();
return bit; // return data bit value
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
void Arithmetic_Codec::encode(unsigned bit,
Adaptive_Bit_Model & M)
{
#ifdef _DEBUG
if (mode != 1) AC_Error("encoder not initialized");
#endif
double x = length * M.bit_0_prob; // compute product l x p0
if (bit == 0) { // update interval length and base
length = x;
++M.bit_0_count;
}
else {
base += x;
length -= x;
if (base >= 1.0) propagate_carry(); // check if carry bit
}
if ((length -= AC__Leakage) <= AC__MinLength) // if renormalization time
renorm_enc_interval();
if (--M.bits_until_update == 0) M.update(); // periodic model update
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
unsigned Arithmetic_Codec::decode(Adaptive_Bit_Model & M)
{
#ifdef _DEBUG
if (mode != 2) AC_Error("decoder not initialized");
#endif
double x = length * M.bit_0_prob; // compute interval-division point
unsigned bit = (value + AC__LeastSignifBit >= base + x); // decode bit value
if (bit == 0) { // update interval length and base
length = x;
++M.bit_0_count;
}
else {
base += x;
length -= x;
if (base >= 1.0) { // decoder does not propagate carry
base -= 1.0; // shift interval
value -= 1.0;
}
}
if ((length -= AC__Leakage) <= AC__MinLength) // if renormalization time
renorm_dec_interval();
if (--M.bits_until_update == 0) M.update(); // periodic model update
return bit; // return data bit value
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
void Arithmetic_Codec::encode(unsigned data,
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
double y;
// compute products
if (data == M.data_symbols - 1)
y = base + length; // avoid multiplication by 1
else
y = base + length * M.distribution[data+1];
// set new interval
base += length * M.distribution[data];
length = y - base;
if (base >= 1.0) propagate_carry(); // check if carry bit
if ((length -= AC__Leakage) <= AC__MinLength) // if renormalization time
renorm_enc_interval();
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
unsigned Arithmetic_Codec::decode(Static_Data_Model & M)
{
#ifdef _DEBUG
if (mode != 2) AC_Error("decoder not initialized");
#endif
unsigned s = 0, n = M.data_symbols, m = n >> 1;
double x = base, y = base + length;
double shifted_value = value + AC__LeastSignifBit;
// bissection search of index in arithmetic coding interval
do {
double z = base + length * M.distribution[m];
if (z > shifted_value) {
y = z; // code value is smaller
n = m;
}
else {
x = z; // code value is larger or equal
s = m;
}
} while ((m = (s + n) >> 1) != s);
// set new interval
base = x;
length = y - x;
if (base >= 1.0) { // decoder does not propagate carry
base -= 1.0; // shift interval
value -= 1.0;
}
if ((length -= AC__Leakage) <= AC__MinLength) // if renormalization time
renorm_dec_interval();
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
double y;
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -