diff options
Diffstat (limited to 'libs/assimp/contrib/Open3DGC/o3dgcArithmeticCodec.cpp')
| -rw-r--r-- | libs/assimp/contrib/Open3DGC/o3dgcArithmeticCodec.cpp | 862 |
1 files changed, 0 insertions, 862 deletions
diff --git a/libs/assimp/contrib/Open3DGC/o3dgcArithmeticCodec.cpp b/libs/assimp/contrib/Open3DGC/o3dgcArithmeticCodec.cpp deleted file mode 100644 index 2ae70fa..0000000 --- a/libs/assimp/contrib/Open3DGC/o3dgcArithmeticCodec.cpp +++ /dev/null @@ -1,862 +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 - 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; - } -} -/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ |