?? arithmetic_codec.cpp
字號(hào):
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// -
// **************************** -
// ARITHMETIC CODING EXAMPLES -
// **************************** -
// -
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// -
// Fast arithmetic coding implementation -
// -> 32-bit variables, 32-bit product, periodic updates, sorted symbols -
// -
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// -
// 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
// Maximum values for binary models
const unsigned BM__LengthShift = 13; // length bits discarded before mult.
const unsigned BM__MaxCount = 1 << BM__LengthShift; // for adaptive models
// Maximum values for general models
const unsigned DM__LengthShift = 15; // length bits discarded before mult.
const unsigned DM__MaxCount = 1 << DM__LengthShift; // for adaptive models
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// - - 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)
{
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
// multiplication approximated by two bit shifts and two additions
unsigned x = length - (length >> M.shift_a) - (length >> M.shift_b);
// update interval
if (M.least_probable_bit ^ (bit != 0))
length = x; // simplest case is the most common
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
// multiplication approximated by two bit shifts and two additions
unsigned x = length - (length >> M.shift_a) - (length >> M.shift_b);
unsigned mpb = (value < x); // decision
// update & shift interval
if (mpb)
length = x;
else {
value -= x; // shifted interval base = 0
length -= x;
}
if (length < AC__MinLength) renorm_dec_interval(); // renormalization
return mpb ^ M.least_probable_bit; // return decoded bit
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
void Arithmetic_Codec::encode(unsigned bit,
Adaptive_Bit_Model & M)
{
#ifdef _DEBUG
if (mode != 1) AC_Error("encoder not initialized");
#endif
unsigned x = M.mpb_prob * (length >> BM__LengthShift); // product l x pm
// update interval
if (M.least_probable_bit ^ (bit != 0))
length = x; // simplest case is the most common
else {
++M.lpb_count;
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 = M.mpb_prob * (length >> BM__LengthShift); // product l x pm
unsigned mpb = (value < x); // decision
// update interval
if (mpb)
length = x;
else {
++M.lpb_count;
value -= x;
length -= x;
}
if (length < AC__MinLength) renorm_dec_interval(); // renormalization
if (--M.bits_until_update) return mpb ^ M.least_probable_bit; // return bit
unsigned bit = mpb ^ M.least_probable_bit; // save bit value before changes
M.update(); // periodic model update
return bit; // return decoded bit
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
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 x, init_base = base, s = M.rank[data]; // symbol = rank
// compute products
if (s == M.most_probable_symbol) {
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -