?? arithmetic_codec.cpp
字號:
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// -
// **************************** -
// ARITHMETIC CODING EXAMPLES -
// **************************** -
// -
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// -
// Fast arithmetic coding implementation -
// -> 32-bit variables, 64-bit product, periodic updates, table decoding -
// -
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// -
// 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 <stdlib.h>
#include "arithmetic_codec.h"
// - - Constants - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
const unsigned AC__MinLength = 0x01000000U; // threshold for renormalization
const unsigned AC__MaxLength = 0xFFFFFFFFU; // maximum AC interval length
const unsigned AC__LengthShift = 32; // bit shift to scale the length
const double AC__ProbScaling = 1.0 + double(0xFFFFFFFFU);
// Maximum symbol counts for adaptive models
const unsigned BM__MaxCount = 1 << 14; // for bit models
const unsigned DM__MaxCount = 1 << 17; // for data models
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// - - Static functions - - - - - - - - - - - - - - - - - - - - - - - - - - -
// upper 32-bit result of 32x32-bit product
inline unsigned Product_64(unsigned l, unsigned c)
{
_asm {
mov eax,l
mul c
mov eax,edx
}
} // return value in register EAX
// division of 64-bit (after scaling) by a 32-bit number
inline unsigned Division_64(unsigned dvh, unsigned dvr)
{
_asm {
xor eax,eax
not eax
mov edx,dvh
div dvr
}
} // return value in register EAX
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)
{
unsigned char * p; // carry propagation on compressed data buffer
for (p = ac_pointer - 1; *p == 0xFFU; p--) *p = 0;
++*p;
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
inline void Arithmetic_Codec::renorm_enc_interval(void)
{
do { // output and discard top byte
*ac_pointer++ = (unsigned char)(base >> 24);
base <<= 8;
} while ((length <<= 8) < AC__MinLength); // length multiplied by 256
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
inline void Arithmetic_Codec::renorm_dec_interval(void)
{
do { // read least-signif. byte
value = (value << 8) | unsigned(*++ac_pointer);
} while ((length <<= 8) < AC__MinLength); // length multiplied by 256
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
void Arithmetic_Codec::put_bit(unsigned bit)
{
#ifdef _DEBUG
if (mode != 1) AC_Error("encoder not initialized");
#endif
length >>= 1; // halve interval
if (bit) {
unsigned init_base = base;
base += length; // move base
if (init_base > base) propagate_carry(); // overflow = carry
}
if (length < AC__MinLength) renorm_enc_interval(); // renormalization
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
unsigned Arithmetic_Codec::get_bit(void)
{
#ifdef _DEBUG
if (mode != 2) AC_Error("decoder not initialized");
#endif
length >>= 1; // halve interval
unsigned bit = (value >= length); // decode bit
if (bit) value -= length; // move base
if (length < AC__MinLength) renorm_dec_interval(); // renormalization
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 init_base = base;
base += data * (length >>= bits); // new interval base and length
if (init_base > base) propagate_carry(); // overflow = carry
if (length < AC__MinLength) renorm_enc_interval(); // renormalization
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
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 = value / (length >>= bits); // decode symbol, change length
value -= length * s; // update interval
if (length < AC__MinLength) renorm_dec_interval(); // renormalization
return s;
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
void Arithmetic_Codec::encode(unsigned bit,
Static_Bit_Model & M)
{
#ifdef _DEBUG
if (mode != 1) AC_Error("encoder not initialized");
#endif
unsigned x = Product_64(length, M.bit_0_prob); // product l x p0
// update interval
if (bit == 0)
length = x;
else {
unsigned init_base = base;
base += x;
length -= x;
if (init_base > base) propagate_carry(); // overflow = carry
}
if (length < AC__MinLength) renorm_enc_interval(); // renormalization
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
unsigned Arithmetic_Codec::decode(Static_Bit_Model & M)
{
#ifdef _DEBUG
if (mode != 2) AC_Error("decoder not initialized");
#endif
unsigned x = Product_64(length, M.bit_0_prob); // product l x p0
unsigned bit = (value >= x); // decision
// update & shift interval
if (bit == 0)
length = x;
else {
value -= x; // shifted interval base = 0
length -= x;
}
if (length < AC__MinLength) renorm_dec_interval(); // renormalization
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
unsigned x = Product_64(length, M.bit_0_prob); // product l x p0
// update interval
if (bit == 0) {
length = x;
++M.bit_0_count;
}
else {
unsigned init_base = base;
base += x;
length -= x;
if (init_base > base) propagate_carry(); // overflow = carry
}
if (length < AC__MinLength) renorm_enc_interval(); // renormalization
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
unsigned x = Product_64(length, M.bit_0_prob); // product l x p0
unsigned bit = (value >= x); // decision
// update interval
if (bit == 0) {
length = x;
++M.bit_0_count;
}
else {
value -= x;
length -= x;
}
if (length < AC__MinLength) renorm_dec_interval(); // renormalization
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
unsigned init_base = base;
unsigned x = Product_64(length, M.distribution[data]); // compute products
base += x; // update interval
length = Product_64(length, M.distribution[data+1]) - 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;
if (M.decoder_table) { // use table look-up for faster decoding
unsigned dv = Division_64(value, length);
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 = Product_64(length, M.distribution[s]);
y = Product_64(length, M.distribution[s+1]);
}
else { // decode using only multiplications
x = s = 0;
y = length - 1;
unsigned m = (n = M.data_symbols) >> 1;
// decode via bisection search
do {
unsigned z = Product_64(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 init_base = base;
unsigned x = Product_64(length, M.distribution[data]); // compute products
base += x; // update interval
length = Product_64(length, M.distribution[data+1]) - 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;
if (M.decoder_table) { // use table look-up for faster decoding
unsigned dv = Division_64(value, length);
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 = Product_64(length, M.distribution[s]);
y = Product_64(length, M.distribution[s+1]);
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -