| /* |
| 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; |
| } |
| } |
| /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ |
