summaryrefslogtreecommitdiffstats
path: root/src/3rdparty/assimp/contrib/Open3DGC/o3dgcArithmeticCodec.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/3rdparty/assimp/contrib/Open3DGC/o3dgcArithmeticCodec.cpp')
-rw-r--r--src/3rdparty/assimp/contrib/Open3DGC/o3dgcArithmeticCodec.cpp865
1 files changed, 0 insertions, 865 deletions
diff --git a/src/3rdparty/assimp/contrib/Open3DGC/o3dgcArithmeticCodec.cpp b/src/3rdparty/assimp/contrib/Open3DGC/o3dgcArithmeticCodec.cpp
deleted file mode 100644
index 3597ec39a..000000000
--- a/src/3rdparty/assimp/contrib/Open3DGC/o3dgcArithmeticCodec.cpp
+++ /dev/null
@@ -1,865 +0,0 @@
-/*
-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
- if ((new_buffer = new unsigned char[buffer_size+16]) == 0) // 16 extra bytes
- AC_Error("cannot assign memory for compressed data buffer");
- 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];
- }
- if (distribution == 0) AC_Error("cannot assign model memory");
- }
- // 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;
- if (distribution == 0) AC_Error("cannot assign model memory");
- }
-
- 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.3 (git 2.25.1) at 2024-05-10 21:13:35 +0000