summaryrefslogtreecommitdiff
path: root/libs/assimp/contrib/Open3DGC/o3dgcArithmeticCodec.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'libs/assimp/contrib/Open3DGC/o3dgcArithmeticCodec.cpp')
-rw-r--r--libs/assimp/contrib/Open3DGC/o3dgcArithmeticCodec.cpp862
1 files changed, 862 insertions, 0 deletions
diff --git a/libs/assimp/contrib/Open3DGC/o3dgcArithmeticCodec.cpp b/libs/assimp/contrib/Open3DGC/o3dgcArithmeticCodec.cpp
new file mode 100644
index 0000000..2ae70fa
--- /dev/null
+++ b/libs/assimp/contrib/Open3DGC/o3dgcArithmeticCodec.cpp
@@ -0,0 +1,862 @@
+/*
+Copyright (c) 2004 Amir Said (said@ieee.org) & William A. Pearlman (pearlw@ecse.rpi.edu)
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without modification,
+are permitted provided that the following conditions are met:
+
+- Redistributions of source code must retain the above copyright notice, this list
+ of conditions and the following disclaimer.
+
+- Redistributions in binary form must reproduce the above copyright notice, this list of
+ conditions and the following disclaimer in the documentation and/or other materials
+ provided with the distribution.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY
+EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
+THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
+OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
+IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
+IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY
+OF SUCH DAMAGE.
+
+*/
+// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
+// -
+// **************************** -
+// ARITHMETIC CODING EXAMPLES -
+// **************************** -
+// -
+// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
+// -
+// Fast arithmetic coding implementation -
+// -> 32-bit variables, 32-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 "o3dgcArithmeticCodec.h"
+
+namespace o3dgc
+{
+ // - - 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);
+ getchar();
+ 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-significant 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 = M.bit_0_prob * (length >> BM__LengthShift); // 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 = M.bit_0_prob * (length >> BM__LengthShift); // 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 = M.bit_0_prob * (length >> BM__LengthShift); // 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 = M.bit_0_prob * (length >> BM__LengthShift); // 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 x, init_base = base;
+ // compute products
+ if (data == M.last_symbol) {
+ x = M.distribution[data] * (length >> DM__LengthShift);
+ base += x; // update interval
+ length -= x; // no product needed
+ }
+ else {
+ x = M.distribution[data] * (length >>= DM__LengthShift);
+ base += x; // update interval
+ length = M.distribution[data+1] * length - 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 = length;
+
+ if (M.decoder_table) { // use table look-up for faster decoding
+
+ unsigned dv = value / (length >>= DM__LengthShift);
+ 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 = M.distribution[s] * length;
+ if (s != M.last_symbol) y = M.distribution[s+1] * length;
+ }
+
+ else { // decode using only multiplications
+
+ x = s = 0;
+ length >>= DM__LengthShift;
+ unsigned m = (n = M.data_symbols) >> 1;
+ // decode via bisection search
+ do {
+ unsigned z = 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 x, init_base = base;
+ // compute products
+ if (data == M.last_symbol) {
+ x = M.distribution[data] * (length >> DM__LengthShift);
+ base += x; // update interval
+ length -= x; // no product needed
+ }
+ else {
+ x = M.distribution[data] * (length >>= DM__LengthShift);
+ base += x; // update interval
+ length = M.distribution[data+1] * length - 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 = length;
+
+ if (M.decoder_table) { // use table look-up for faster decoding
+
+ unsigned dv = value / (length >>= DM__LengthShift);
+ 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 = M.distribution[s] * length;
+ if (s != M.last_symbol) {
+ y = M.distribution[s+1] * length;
+ }
+ }
+
+ else { // decode using only multiplications
+
+ x = s = 0;
+ length >>= DM__LengthShift;
+ unsigned m = (n = M.data_symbols) >> 1;
+ // decode via bisection search
+ do {
+ unsigned z = 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
+
+ ++M.symbol_count[s];
+ if (--M.symbols_until_update == 0) M.update(false); // periodic model update
+
+ return s;
+ }
+
+
+ // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
+ // - - Other Arithmetic_Codec implementations - - - - - - - - - - - - - - - -
+
+ Arithmetic_Codec::Arithmetic_Codec(void)
+ {
+ mode = buffer_size = 0;
+ new_buffer = code_buffer = 0;
+ }
+
+ Arithmetic_Codec::Arithmetic_Codec(unsigned max_code_bytes,
+ unsigned char * user_buffer)
+ {
+ mode = buffer_size = 0;
+ new_buffer = code_buffer = 0;
+ set_buffer(max_code_bytes, user_buffer);
+ }
+
+ Arithmetic_Codec::~Arithmetic_Codec(void)
+ {
+ delete [] new_buffer;
+ }
+
+ // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
+
+ void Arithmetic_Codec::set_buffer(unsigned max_code_bytes,
+ unsigned char * user_buffer)
+ {
+ // test for reasonable sizes
+ if (!max_code_bytes)// || (max_code_bytes > 0x10000000U)) // updated by K. Mammou
+ {
+ AC_Error("invalid codec buffer size");
+ }
+ if (mode != 0) AC_Error("cannot set buffer while encoding or decoding");
+
+ if (user_buffer != 0) { // user provides memory buffer
+ buffer_size = max_code_bytes;
+ code_buffer = user_buffer; // set buffer for compressed data
+ delete [] new_buffer; // free anything previously assigned
+ new_buffer = 0;
+ return;
+ }
+
+ if (max_code_bytes <= buffer_size) return; // enough available
+
+ buffer_size = max_code_bytes; // assign new memory
+ delete [] new_buffer; // free anything previously assigned
+ new_buffer = new unsigned char[buffer_size+16]; // 16 extra bytes
+ code_buffer = new_buffer; // set buffer for compressed data
+ }
+
+ // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
+
+ void Arithmetic_Codec::start_encoder(void)
+ {
+ if (mode != 0) AC_Error("cannot start encoder");
+ if (buffer_size == 0) AC_Error("no code buffer set");
+
+ mode = 1;
+ base = 0; // initialize encoder variables: interval and pointer
+ length = AC__MaxLength;
+ ac_pointer = code_buffer; // pointer to next data byte
+ }
+
+ // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
+
+ void Arithmetic_Codec::start_decoder(void)
+ {
+ if (mode != 0) AC_Error("cannot start decoder");
+ if (buffer_size == 0) AC_Error("no code buffer set");
+
+ // initialize decoder: interval, pointer, initial code value
+ mode = 2;
+ length = AC__MaxLength;
+ ac_pointer = code_buffer + 3;
+ value = (unsigned(code_buffer[0]) << 24)|(unsigned(code_buffer[1]) << 16) |
+ (unsigned(code_buffer[2]) << 8)| unsigned(code_buffer[3]);
+ }
+
+ // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
+
+ void Arithmetic_Codec::read_from_file(FILE * code_file)
+ {
+ unsigned shift = 0, code_bytes = 0;
+ int file_byte;
+ // read variable-length header with number of code bytes
+ do {
+ if ((file_byte = getc(code_file)) == EOF)
+ AC_Error("cannot read code from file");
+ code_bytes |= unsigned(file_byte & 0x7F) << shift;
+ shift += 7;
+ } while (file_byte & 0x80);
+ // read compressed data
+ if (code_bytes > buffer_size) AC_Error("code buffer overflow");
+ if (fread(code_buffer, 1, code_bytes, code_file) != code_bytes)
+ AC_Error("cannot read code from file");
+
+ start_decoder(); // initialize decoder
+ }
+
+ // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
+
+ unsigned Arithmetic_Codec::stop_encoder(void)
+ {
+ if (mode != 1) AC_Error("invalid to stop encoder");
+ mode = 0;
+
+ unsigned init_base = base; // done encoding: set final data bytes
+
+ if (length > 2 * AC__MinLength) {
+ base += AC__MinLength; // base offset
+ length = AC__MinLength >> 1; // set new length for 1 more byte
+ }
+ else {
+ base += AC__MinLength >> 1; // base offset
+ length = AC__MinLength >> 9; // set new length for 2 more bytes
+ }
+
+ if (init_base > base) propagate_carry(); // overflow = carry
+
+ renorm_enc_interval(); // renormalization = output last bytes
+
+ unsigned code_bytes = unsigned(ac_pointer - code_buffer);
+ if (code_bytes > buffer_size) AC_Error("code buffer overflow");
+
+ return code_bytes; // number of bytes used
+ }
+
+ // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
+
+ unsigned Arithmetic_Codec::write_to_file(FILE * code_file)
+ {
+ unsigned header_bytes = 0, code_bytes = stop_encoder(), nb = code_bytes;
+
+ // write variable-length header with number of code bytes
+ do {
+ int file_byte = int(nb & 0x7FU);
+ if ((nb >>= 7) > 0) file_byte |= 0x80;
+ if (putc(file_byte, code_file) == EOF)
+ AC_Error("cannot write compressed data to file");
+ header_bytes++;
+ } while (nb);
+ // write compressed data
+ if (fwrite(code_buffer, 1, code_bytes, code_file) != code_bytes)
+ AC_Error("cannot write compressed data to file");
+
+ return code_bytes + header_bytes; // bytes used
+ }
+
+ // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
+
+ void Arithmetic_Codec::stop_decoder(void)
+ {
+ if (mode != 2) AC_Error("invalid to stop decoder");
+ mode = 0;
+ }
+
+
+ // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
+ // - Static bit model implementation - - - - - - - - - - - - - - - - - - - - -
+
+ Static_Bit_Model::Static_Bit_Model(void)
+ {
+ bit_0_prob = 1U << (BM__LengthShift - 1); // p0 = 0.5
+ }
+
+ // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
+
+ void Static_Bit_Model::set_probability_0(double p0)
+ {
+ if ((p0 < 0.0001)||(p0 > 0.9999)) AC_Error("invalid bit probability");
+ bit_0_prob = unsigned(p0 * (1 << BM__LengthShift));
+ }
+
+
+ // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
+ // - Adaptive bit model implementation - - - - - - - - - - - - - - - - - - - -
+
+ Adaptive_Bit_Model::Adaptive_Bit_Model(void)
+ {
+ reset();
+ }
+
+ // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
+
+ void Adaptive_Bit_Model::reset(void)
+ {
+ // initialization to equiprobable model
+ bit_0_count = 1;
+ bit_count = 2;
+ bit_0_prob = 1U << (BM__LengthShift - 1);
+ update_cycle = bits_until_update = 4; // start with frequent updates
+ }
+
+ // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
+
+ void Adaptive_Bit_Model::update(void)
+ {
+ // halve counts when a threshold is reached
+
+ if ((bit_count += update_cycle) > BM__MaxCount) {
+ bit_count = (bit_count + 1) >> 1;
+ bit_0_count = (bit_0_count + 1) >> 1;
+ if (bit_0_count == bit_count) ++bit_count;
+ }
+ // compute scaled bit 0 probability
+ unsigned scale = 0x80000000U / bit_count;
+ bit_0_prob = (bit_0_count * scale) >> (31 - BM__LengthShift);
+
+ // set frequency of model updates
+ update_cycle = (5 * update_cycle) >> 2;
+ if (update_cycle > 64) update_cycle = 64;
+ bits_until_update = update_cycle;
+ }
+
+
+ // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
+ // - - Static data model implementation - - - - - - - - - - - - - - - - - - -
+
+ Static_Data_Model::Static_Data_Model(void)
+ {
+ data_symbols = 0;
+ distribution = 0;
+ }
+
+ Static_Data_Model::~Static_Data_Model(void)
+ {
+ delete [] distribution;
+ }
+
+ // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
+
+ void Static_Data_Model::set_distribution(unsigned number_of_symbols,
+ const double probability[])
+ {
+ if ((number_of_symbols < 2) || (number_of_symbols > (1 << 11)))
+ AC_Error("invalid number of data symbols");
+
+ if (data_symbols != number_of_symbols) { // assign memory for data model
+ data_symbols = number_of_symbols;
+ last_symbol = data_symbols - 1;
+ delete [] distribution;
+ // define size of table for fast decoding
+ if (data_symbols > 16) {
+ unsigned table_bits = 3;
+ while (data_symbols > (1U << (table_bits + 2))) ++table_bits;
+ table_size = 1 << table_bits;
+ table_shift = DM__LengthShift - table_bits;
+ distribution = new unsigned[data_symbols+table_size+2];
+ decoder_table = distribution + data_symbols;
+ }
+ else { // small alphabet: no table needed
+ decoder_table = 0;
+ table_size = table_shift = 0;
+ distribution = new unsigned[data_symbols];
+ }
+ }
+ // compute cumulative distribution, decoder table
+ unsigned s = 0;
+ double sum = 0.0, p = 1.0 / double(data_symbols);
+
+ for (unsigned k = 0; k < data_symbols; k++) {
+ if (probability) p = probability[k];
+ if ((p < 0.0001) || (p > 0.9999)) AC_Error("invalid symbol probability");
+ distribution[k] = unsigned(sum * (1 << DM__LengthShift));
+ sum += p;
+ if (table_size == 0) continue;
+ unsigned w = distribution[k] >> table_shift;
+ while (s < w) decoder_table[++s] = k - 1;
+ }
+
+ if (table_size != 0) {
+ decoder_table[0] = 0;
+ while (s <= table_size) decoder_table[++s] = data_symbols - 1;
+ }
+
+ if ((sum < 0.9999) || (sum > 1.0001)) AC_Error("invalid probabilities");
+ }
+
+ // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
+ // - - Adaptive data model implementation - - - - - - - - - - - - - - - - - -
+
+ Adaptive_Data_Model::Adaptive_Data_Model(void)
+ {
+ data_symbols = 0;
+ distribution = 0;
+ }
+
+ Adaptive_Data_Model::Adaptive_Data_Model(unsigned number_of_symbols)
+ {
+ data_symbols = 0;
+ distribution = 0;
+ set_alphabet(number_of_symbols);
+ }
+
+ Adaptive_Data_Model::~Adaptive_Data_Model(void)
+ {
+ delete [] distribution;
+ }
+
+ // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
+
+ void Adaptive_Data_Model::set_alphabet(unsigned number_of_symbols)
+ {
+ if ((number_of_symbols < 2) || (number_of_symbols > (1 << 11)))
+ AC_Error("invalid number of data symbols");
+
+ if (data_symbols != number_of_symbols) { // assign memory for data model
+ data_symbols = number_of_symbols;
+ last_symbol = data_symbols - 1;
+ delete [] distribution;
+ // define size of table for fast decoding
+ if (data_symbols > 16) {
+ unsigned table_bits = 3;
+ while (data_symbols > (1U << (table_bits + 2))) ++table_bits;
+ table_size = 1 << table_bits;
+ table_shift = DM__LengthShift - table_bits;
+ distribution = new unsigned[2*data_symbols+table_size+2];
+ decoder_table = distribution + 2 * data_symbols;
+ }
+ else { // small alphabet: no table needed
+ decoder_table = 0;
+ table_size = table_shift = 0;
+ distribution = new unsigned[2*data_symbols];
+ }
+ symbol_count = distribution + data_symbols;
+ }
+
+ reset(); // initialize model
+ }
+
+ // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
+
+ void Adaptive_Data_Model::update(bool from_encoder)
+ {
+ // halve counts when a threshold is reached
+
+ if ((total_count += update_cycle) > DM__MaxCount) {
+ total_count = 0;
+ for (unsigned n = 0; n < data_symbols; n++)
+ total_count += (symbol_count[n] = (symbol_count[n] + 1) >> 1);
+ }
+ assert(total_count > 0);
+ // compute cumulative distribution, decoder table
+ unsigned k, sum = 0, s = 0;
+ unsigned scale = 0x80000000U / total_count;
+
+ if (from_encoder || (table_size == 0))
+ for (k = 0; k < data_symbols; k++) {
+ distribution[k] = (scale * sum) >> (31 - DM__LengthShift);
+ sum += symbol_count[k];
+ }
+ else {
+ assert(decoder_table);
+ for (k = 0; k < data_symbols; k++) {
+ distribution[k] = (scale * sum) >> (31 - DM__LengthShift);
+ sum += symbol_count[k];
+ unsigned w = distribution[k] >> table_shift;
+ while (s < w) decoder_table[++s] = k - 1;
+ }
+ decoder_table[0] = 0;
+ while (s <= table_size) decoder_table[++s] = data_symbols - 1;
+ }
+ // set frequency of model updates
+ update_cycle = (5 * update_cycle) >> 2;
+ unsigned max_cycle = (data_symbols + 6) << 3;
+ if (update_cycle > max_cycle) update_cycle = max_cycle;
+ symbols_until_update = update_cycle;
+ }
+
+ // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
+
+ void Adaptive_Data_Model::reset(void)
+ {
+ if (data_symbols == 0) return;
+
+ // restore probability estimates to uniform distribution
+ total_count = 0;
+ update_cycle = data_symbols;
+ for (unsigned k = 0; k < data_symbols; k++) symbol_count[k] = 1;
+ update(false);
+ symbols_until_update = update_cycle = (data_symbols + 6) >> 1;
+ }
+}
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
generated by cgit v1.2.1 (git 2.18.0) at 2024-11-01 23:22:18 +0000