Project

General

Profile

Download (9.14 KB) Statistics
| Branch: | Tag: | Revision:

root/software/libpackjpg/source/aricoder.h @ 058717b0

525a7e92 David Sorber
#ifndef ARICODER_H
#define ARICODER_H

#include "bitops.h"

#include <algorithm>
#include <cstdint>
#include <memory>
#include <vector>

// defines for coder
constexpr uint32_t CODER_USE_BITS = 31; // Must never be above 31.
constexpr uint32_t CODER_LIMIT100 = uint32_t(1 << CODER_USE_BITS);
constexpr uint32_t CODER_LIMIT025 = CODER_LIMIT100 / 4;
constexpr uint32_t CODER_LIMIT050 = (CODER_LIMIT100 / 4) * 2;
constexpr uint32_t CODER_LIMIT075 = (CODER_LIMIT100 / 4) * 3;
constexpr uint32_t CODER_MAXSCALE = CODER_LIMIT025 - 1;
constexpr uint32_t ESCAPE_SYMBOL = CODER_LIMIT025;

// symbol struct, used in arithmetic coding
struct symbol {
uint32_t low_count;
uint32_t high_count;
uint32_t scale;
};

// table struct, used in in statistical models,
// holding all info needed for one context
struct table {
// counts for each symbol contained in the table
std::vector<uint16_t> counts;
// links to higher order contexts
std::vector<table*> links;
// accumulated counts
uint32_t scale = uint32_t(0);

/* -----------------------------------------------
Recursively deletes all the tables pointed to in links.
----------------------------------------------- */
~table() {
for (auto& link : links) {
if (link != nullptr) {
delete link;
}
}
}

/* -----------------------------------------------
Checks if counts exist, creating it if it does not.
----------------------------------------------- */
inline void check_counts() {
// check if counts are available
if (counts.empty()) {
// setup counts for current table
counts.resize(2, uint16_t(1));
// set scale
scale = uint32_t(2);
}
}

/* -----------------------------------------------
Resizes the table by rightshifting each count by 1.
----------------------------------------------- */
inline void rescale_table() {
// Do nothing if counts is not set:
if (!counts.empty()) {
// Scale the table by bitshifting each count, be careful not to set any count zero:
counts[0] = std::max(uint16_t(1), uint16_t(counts[0] >> 1));
counts[1] = std::max(uint16_t(1), uint16_t(counts[1] >> 1));
scale = counts[0] + counts[1];
}
}

/* -----------------------------------------------
Recursively runs rescale_table on this and all linked contexts.
----------------------------------------------- */
inline void recursive_flush() {
for (auto& link : links) {
if (link != nullptr) {
link->recursive_flush();
}
}
// rescale specific table
rescale_table();
}
};

// special table struct, used in in model_s,
// holding additional info for a speedier 'totalize_table'
struct table_s {
// counts for each symbol contained in the table
std::vector<uint16_t> counts;
// links to higher order contexts
std::vector<table_s*> links;
// speedup info
uint16_t max_count = uint16_t(0);
uint16_t max_symbol = uint16_t(0);

/* -----------------------------------------------
Recursively deletes all the tables pointed to in links.
----------------------------------------------- */
~table_s() {
for (auto& link : links) {
if (link != nullptr) {
delete link;
}
}
}

/* -----------------------------------------------
Resizes the table by rightshifting each count by 1.
----------------------------------------------- */
inline void rescale_table() {
// Nothing to do if counts has not been set.
if (counts.empty()) return;

// now scale the table by bitshifting each count
int lst_symbol = max_symbol;
int i;
for (i = 0; i < lst_symbol; i++) {
counts[i] >>= 1; // Counts will not become negative since it is an unsigned type.
}

// also rescale tables max count
max_count >>= 1;

// seek for new last symbol
for (i = lst_symbol - 1; i >= 0; i--) {
if (counts[i] > 0) {
break;
}
}
max_symbol = i + 1;
}

/* -----------------------------------------------
Recursively runs rescale_table on this and all linked contexts.
----------------------------------------------- */
inline void recursive_flush() {
for (auto& link : links) {
if (link != nullptr) {
link->recursive_flush();
}
}

// rescale specific table
rescale_table();
}
};

class ArithmeticBitWriter {
public:
template <std::uint8_t bit>
void write_bit();

void write_n_zero_bits(std::size_t n);

void write_n_one_bits(std::size_t n);

void pad();

std::vector<std::uint8_t> get_data() const;


private:
std::vector<std::uint8_t> data_;
std::uint8_t curr_byte_ = 0;
std::size_t curr_bit_ = 0;
};


/* -----------------------------------------------
class for arithmetic coding of data to/from iostream
----------------------------------------------- */

class ArithmeticEncoder
{
public:
ArithmeticEncoder(Writer& writer);
~ArithmeticEncoder();
void encode( symbol* s );

void finalize();
private:
// i/o variables
bool finalized = false;
Writer& writer_;
std::unique_ptr<ArithmeticBitWriter> bitwriter_ = std::make_unique<ArithmeticBitWriter>();
// arithmetic coding variables
unsigned int ccode = 0;
unsigned int clow = 0;
unsigned int chigh = CODER_LIMIT100 - 1;
unsigned int cstep = 0;
unsigned int nrbits = 0;
};

class ArithmeticDecoder {
public:
ArithmeticDecoder(Reader& reader);
~ArithmeticDecoder() {}
unsigned int decode_count( symbol* s );
void decode( symbol* s );
private:
unsigned char read_bit();
// i/o variables
Reader& reader_;
unsigned char bbyte = 0;
unsigned char cbit = 0;
// arithmetic coding variables
unsigned int ccode = 0;
unsigned int clow = 0;
unsigned int chigh = CODER_LIMIT100 - 1;
unsigned int cstep = 0;
};


/* -----------------------------------------------
universal statistical model for arithmetic coding
----------------------------------------------- */
class model_s
{
public:
model_s( int max_s, int max_c, int max_o, int c_lim );
~model_s();
void update_model( int symbol );
void shift_context( int c );
void flush_model();
void exclude_symbols(int c);
int convert_int_to_symbol( int c, symbol *s );
void get_symbol_scale( symbol *s );
int convert_symbol_to_int(uint32_t count, symbol *s);
private:

inline void totalize_table(table_s* context);

const int max_symbol;
const int max_context;
const int max_order;
const int max_count;

int current_order;
int sb0_count;
std::vector<uint32_t> totals;
bool* scoreboard;
std::vector<table_s*> contexts;
};


/* -----------------------------------------------
binary statistical model for arithmetic coding
----------------------------------------------- */
class model_b
{
public:
model_b( int max_c, int max_o, int c_lim );
~model_b();
void update_model( int symbol );
void shift_context( int c );
void flush_model();
int convert_int_to_symbol( int c, symbol *s );
void get_symbol_scale( symbol *s );
int convert_symbol_to_int(uint32_t count, symbol *s);
private:
const int max_context;
const int max_order;
const int max_count;
std::vector<table*> contexts;
};

// Base case for shifting an arbitrary number of contexts into the model.
template <typename M>
static void shift_model(M) {}

// Shift an arbitrary number of contexts into the model (at most max_c contexts).
template <typename M, typename C, typename... Cargs>
static void shift_model(M model, C context, Cargs ... contextList) {
model->shift_context(context);
shift_model(model, contextList...);
}

/* -----------------------------------------------
generic model_s encoder function
----------------------------------------------- */
static inline void encode_ari( ArithmeticEncoder* encoder, model_s* model, int c )
{
symbol s;
int esc;
do {
esc = model->convert_int_to_symbol( c, &s );
encoder->encode( &s );
} while ( esc );
model->update_model( c );
}

/* -----------------------------------------------
generic model_s decoder function
----------------------------------------------- */
static inline int decode_ari( ArithmeticDecoder* decoder, model_s* model )
{
symbol s;
uint32_t count;
int c;
do{
model->get_symbol_scale( &s );
count = decoder->decode_count( &s );
c = model->convert_symbol_to_int( count, &s );
decoder->decode( &s );
} while ( c == ESCAPE_SYMBOL );
model->update_model( c );
return c;
}

/* -----------------------------------------------
generic model_b encoder function
----------------------------------------------- */
static inline void encode_ari( ArithmeticEncoder* encoder, model_b* model, int c )
{
symbol s;
model->convert_int_to_symbol( c, &s );
encoder->encode( &s );
model->update_model( c );
}

/* -----------------------------------------------
generic model_b decoder function
----------------------------------------------- */
static inline int decode_ari( ArithmeticDecoder* decoder, model_b* model )
{
symbol s;
model->get_symbol_scale( &s );
uint32_t count = decoder->decode_count( &s );
int c = model->convert_symbol_to_int( count, &s );
decoder->decode( &s );
model->update_model( c );
return c;
}

#endif