Project

General

Profile

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

root/software/libpackjpg/lib_src/aricoder.h @ ffb481f4

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