diff options
Diffstat (limited to 'ml/dlib/dlib/entropy_encoder')
6 files changed, 976 insertions, 0 deletions
diff --git a/ml/dlib/dlib/entropy_encoder/entropy_encoder_kernel_1.cpp b/ml/dlib/dlib/entropy_encoder/entropy_encoder_kernel_1.cpp new file mode 100644 index 000000000..effcf3123 --- /dev/null +++ b/ml/dlib/dlib/entropy_encoder/entropy_encoder_kernel_1.cpp @@ -0,0 +1,239 @@ +// Copyright (C) 2003 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#ifndef DLIB_ENTROPY_ENCODER_KERNEL_1_CPp_ +#define DLIB_ENTROPY_ENCODER_KERNEL_1_CPp_ +#include "entropy_encoder_kernel_1.h" +#include <iostream> +#include <streambuf> + +namespace dlib +{ + + +// ---------------------------------------------------------------------------------------- + + entropy_encoder_kernel_1:: + entropy_encoder_kernel_1( + ) : + initial_low(0x00000001), + initial_high(0xffffffff), + out(0), + low(initial_low), + high(initial_high), + buf(0), + buf_used(0) + { + } + +// ---------------------------------------------------------------------------------------- + + entropy_encoder_kernel_1:: + ~entropy_encoder_kernel_1 ( + ) + { + try { + if (out != 0) + { + flush(); + } + } catch (...) {} + } + +// ---------------------------------------------------------------------------------------- + + void entropy_encoder_kernel_1:: + clear( + ) + { + if (out != 0) + { + flush(); + } + out = 0; + } + +// ---------------------------------------------------------------------------------------- + + void entropy_encoder_kernel_1:: + set_stream ( + std::ostream& out_ + ) + { + if (out != 0) + { + // if a stream is currently set then flush the buffers to it before + // we switch to the new stream + flush(); + } + + out = &out_; + streambuf = out_.rdbuf(); + + // reset the encoder state + buf_used = 0; + buf = 0; + low = initial_low; + high = initial_high; + } + +// ---------------------------------------------------------------------------------------- + + bool entropy_encoder_kernel_1:: + stream_is_set ( + ) const + { + if (out != 0) + return true; + else + return false; + } + +// ---------------------------------------------------------------------------------------- + + std::ostream& entropy_encoder_kernel_1:: + get_stream ( + ) const + { + return *out; + } + +// ---------------------------------------------------------------------------------------- + + void entropy_encoder_kernel_1:: + encode ( + uint32 low_count, + uint32 high_count, + uint32 total + ) + { + // note that we must add one because of the convention that + // high == the real upper range minus 1 + uint32 r = (high-low+1)/total; + + // note that we must subtract 1 to preserve the convention that + // high == the real upper range - 1 + high = low + r*high_count-1; + low = low + r*low_count; + + + while (true) + { + + // if the highest order bit in high and low is the same + if ( low >= 0x80000000 || high < 0x80000000) + { + // if buf is full then write it out + if (buf_used == 8) + { + if (streambuf->sputn(reinterpret_cast<char*>(&buf),1)==0) + { + throw std::ios_base::failure("error occurred in the entropy_encoder object"); + } + buf = 0; + buf_used = 0; + } + + + // write the high order bit from low into buf + buf <<= 1; + ++buf_used; + if (low&0x80000000) + buf |= 0x1; + + // roll off the bit we just wrote to buf + low <<= 1; + high <<= 1; + high |= 1; // note that it is ok to add one to high here because + // of the convention that high == real upper range - 1. + // so that means that if we want to shift the upper range + // left by one then we must shift a one into high also + // since real upper range == high + 0.999999999... + + // make sure low is never zero + if (low == 0) + low = 1; + } + // if the distance between high and low is small and there aren't + // any bits we can roll off then round low up or high down. + else if (high-low < 0x10000) + { + if (high == 0x80000000) + high = 0x7fffffff; + else + low = 0x80000000; + } + else + { + break; + } + } // while (true) + + } + +// ---------------------------------------------------------------------------------------- + + void entropy_encoder_kernel_1:: + flush ( + ) + { + // flush the next 4 or 5 bytes that are buffered + // thats whatever is contained in buf and then all of low plus any extra + // bits needed to pad that to be an even 4 or 5 bytes + + + if (buf_used != 8) + { + buf <<= (8-buf_used); + buf |= static_cast<unsigned char>(low>>(24+buf_used)); + low <<= (8-buf_used); + } + + if (streambuf->sputn(reinterpret_cast<char*>(&buf),1) == 0) + throw std::ios_base::failure("error occurred in the entropy_encoder object"); + + + + buf = static_cast<unsigned char>((low >> 24)&0xFF); + if (streambuf->sputn(reinterpret_cast<char*>(&buf),1) == 0) + throw std::ios_base::failure("error occurred in the entropy_encoder object"); + + + + + buf = static_cast<unsigned char>((low >> 16)&0xFF); + if (streambuf->sputn(reinterpret_cast<char*>(&buf),1)==0) + throw std::ios_base::failure("error occurred in the entropy_encoder object"); + + + + buf = static_cast<unsigned char>((low >> 8)&0xFF); + if (streambuf->sputn(reinterpret_cast<char*>(&buf),1)==0) + throw std::ios_base::failure("error occurred in the entropy_encoder object"); + + + + if (buf_used != 0) + { + buf = static_cast<unsigned char>((low)&0xFF); + if (streambuf->sputn(reinterpret_cast<char*>(&buf),1)==0) + throw std::ios_base::failure("error occurred in the entropy_encoder object"); + } + + + + // make sure the stream buffer flushes to its I/O channel + streambuf->pubsync(); + + + // reset the encoder state + buf_used = 0; + buf = 0; + low = initial_low; + high = initial_high; + } + +// ---------------------------------------------------------------------------------------- + +} +#endif // DLIB_ENTROPY_ENCODER_KERNEL_1_CPp_ + diff --git a/ml/dlib/dlib/entropy_encoder/entropy_encoder_kernel_1.h b/ml/dlib/dlib/entropy_encoder/entropy_encoder_kernel_1.h new file mode 100644 index 000000000..ccaaf9824 --- /dev/null +++ b/ml/dlib/dlib/entropy_encoder/entropy_encoder_kernel_1.h @@ -0,0 +1,119 @@ +// Copyright (C) 2003 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#ifndef DLIB_ENTROPY_ENCODER_KERNEl_1_ +#define DLIB_ENTROPY_ENCODER_KERNEl_1_ + +#include "../algs.h" +#include "entropy_encoder_kernel_abstract.h" +#include <iosfwd> +#include "../uintn.h" + +namespace dlib +{ + + class entropy_encoder_kernel_1 + { + /*! + GENERAL NOTES + this encoder is implemented using arithmetic coding + + INITIAL VALUE + out == 0 + buf_used == 0 + buf == 0 + initial_low == 0x00000001 (slightly more than zero) + initial_high == 0xffffffff (slightly less than one, 0.99999999976717) + low == initial_low + high == initial_high + + CONVENTION + if (out != 0) + *out == get_stream() + true == stream_is_set() + streambuf == out->rdbuf() + else + false == stream_is_set() + + buf == used to accumulate bits before writing them to out. + buf_used == the number of low order bits in buf that are currently + in use + low == the low end of the range used for arithmetic encoding. + this number is used as a 32bit fixed point real number. + the point is fixed just before the first bit, so it is + always in the range [0,1) + + low is also never allowed to be zero to avoid overflow + in the calculation (high-low+1)/total. + + high == the high end of the range - 1 used for arithmetic encoding. + this number is used as a 32bit fixed point real number. + the point is fixed just before the first bit, so when we + interpret high as a real number then it is always in the + range [0,1) + + the range for arithmetic encoding is always + [low,high + 0.9999999...) the 0.9999999... is why + high == real upper range - 1 + + !*/ + + public: + + entropy_encoder_kernel_1 ( + ); + + virtual ~entropy_encoder_kernel_1 ( + ); + + void clear( + ); + + void set_stream ( + std::ostream& out + ); + + bool stream_is_set ( + ) const; + + std::ostream& get_stream ( + ) const; + + void encode ( + uint32 low_count, + uint32 high_count, + uint32 total + ); + + private: + + void flush ( + ); + /*! + requires + out != 0 (i.e. there is a stream object to flush the data to + !*/ + + // restricted functions + entropy_encoder_kernel_1(entropy_encoder_kernel_1&); // copy constructor + entropy_encoder_kernel_1& operator=(entropy_encoder_kernel_1&); // assignment operator + + // data members + const uint32 initial_low; + const uint32 initial_high; + std::ostream* out; + uint32 low; + uint32 high; + unsigned char buf; + uint32 buf_used; + std::streambuf* streambuf; + + }; + +} + +#ifdef NO_MAKEFILE +#include "entropy_encoder_kernel_1.cpp" +#endif + +#endif // DLIB_ENTROPY_ENCODER_KERNEl_1_ + diff --git a/ml/dlib/dlib/entropy_encoder/entropy_encoder_kernel_2.cpp b/ml/dlib/dlib/entropy_encoder/entropy_encoder_kernel_2.cpp new file mode 100644 index 000000000..4f64a6155 --- /dev/null +++ b/ml/dlib/dlib/entropy_encoder/entropy_encoder_kernel_2.cpp @@ -0,0 +1,233 @@ +// Copyright (C) 2004 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#ifndef DLIB_ENTROPY_ENCODER_KERNEL_2_CPp_ +#define DLIB_ENTROPY_ENCODER_KERNEL_2_CPp_ +#include "entropy_encoder_kernel_2.h" +#include <iostream> +#include <streambuf> + +namespace dlib +{ + + +// ---------------------------------------------------------------------------------------- + + entropy_encoder_kernel_2:: + entropy_encoder_kernel_2( + ) : + initial_low(0x00000001), + initial_high(0xffffffff), + out(0), + low(initial_low), + high(initial_high) + { + } + +// ---------------------------------------------------------------------------------------- + + entropy_encoder_kernel_2:: + ~entropy_encoder_kernel_2 ( + ) + { + try { + if (out != 0) + { + flush(); + } + } catch (...) {} + } + +// ---------------------------------------------------------------------------------------- + + void entropy_encoder_kernel_2:: + clear( + ) + { + if (out != 0) + { + flush(); + } + out = 0; + } + +// ---------------------------------------------------------------------------------------- + + void entropy_encoder_kernel_2:: + set_stream ( + std::ostream& out_ + ) + { + if (out != 0) + { + // if a stream is currently set then flush the buffers to it before + // we switch to the new stream + flush(); + } + + out = &out_; + streambuf = out_.rdbuf(); + + // reset the encoder state + low = initial_low; + high = initial_high; + } + +// ---------------------------------------------------------------------------------------- + + bool entropy_encoder_kernel_2:: + stream_is_set ( + ) const + { + if (out != 0) + return true; + else + return false; + } + +// ---------------------------------------------------------------------------------------- + + std::ostream& entropy_encoder_kernel_2:: + get_stream ( + ) const + { + return *out; + } + +// ---------------------------------------------------------------------------------------- + + void entropy_encoder_kernel_2:: + encode ( + uint32 low_count, + uint32 high_count, + uint32 total + ) + { + // note that we must add one because of the convention that + // high == the real upper range minus 1 + uint32 r = (high-low+1)/total; + + // note that we must subtract 1 to preserve the convention that + // high == the real upper range - 1 + high = low + r*high_count-1; + low = low + r*low_count; + + + + while (true ) + { + + // if high and low don't have the same 8 high order bits + if ((high&0xFF000000) != (low&0xFF000000)) + { + // if the distance between high and low is small and there aren't + // any bits we can roll off then force high and low to have common high + // order bits. + if ((high-low < 0x10000)) + { + if (high-low > 0x1000) + { + high>>=1; + low>>=1; + high = low = high+low; + high += 0xFF; + low -= 0xFF; + } + else /**/ + { + high>>=1; + low>>=1; + high = low = high+low; + } + } + else + { + // there are no bits to roll off and high and low are not + // too close so just quit the loop + break; + } + + } + // else if there are 8 bits we can roll off + else + { + // write the 8 high order bits from low into buf + unsigned char buf = static_cast<unsigned char>(low>>24); + + + // roll off the bits we just wrote to buf + high <<= 8; + low <<= 8; + high |= 0xFF; // note that it is ok to add 0xFF to high here because + // of the convention that high == real upper range - 1. + // so that means that if we want to shift the upper range + // left by one then we must shift a one into high also + // since real upper range == high + 0.999999999... + + // make sure low is never zero + if (low == 0) + low = 1; + + // write buf to the output stream + if (streambuf->sputn(reinterpret_cast<char*>(&buf),1)==0) + { + throw std::ios_base::failure("error occurred in the entropy_encoder object"); + } + + } + + } // while (true) + + } + +// ---------------------------------------------------------------------------------------- + + void entropy_encoder_kernel_2:: + flush ( + ) + { + + // flush low to the output stream + + + unsigned char buf; + + + buf = static_cast<unsigned char>((low >> 24)&0xFF); + if (streambuf->sputn(reinterpret_cast<char*>(&buf),1) == 0) + throw std::ios_base::failure("error occurred in the entropy_encoder object"); + + + + + buf = static_cast<unsigned char>((low >> 16)&0xFF); + if (streambuf->sputn(reinterpret_cast<char*>(&buf),1)==0) + throw std::ios_base::failure("error occurred in the entropy_encoder object"); + + + + buf = static_cast<unsigned char>((low >> 8)&0xFF); + if (streambuf->sputn(reinterpret_cast<char*>(&buf),1)==0) + throw std::ios_base::failure("error occurred in the entropy_encoder object"); + + + buf = static_cast<unsigned char>((low)&0xFF); + if (streambuf->sputn(reinterpret_cast<char*>(&buf),1)==0) + throw std::ios_base::failure("error occurred in the entropy_encoder object"); + + + + + // make sure the stream buffer flushes to its I/O channel + streambuf->pubsync(); + + + // reset the encoder state + low = initial_low; + high = initial_high; + } + +// ---------------------------------------------------------------------------------------- + +} +#endif // DLIB_ENTROPY_ENCODER_KERNEL_2_CPp_ + diff --git a/ml/dlib/dlib/entropy_encoder/entropy_encoder_kernel_2.h b/ml/dlib/dlib/entropy_encoder/entropy_encoder_kernel_2.h new file mode 100644 index 000000000..71a7503c6 --- /dev/null +++ b/ml/dlib/dlib/entropy_encoder/entropy_encoder_kernel_2.h @@ -0,0 +1,112 @@ +// Copyright (C) 2004 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#ifndef DLIB_ENTROPY_ENCODER_KERNEl_2_ +#define DLIB_ENTROPY_ENCODER_KERNEl_2_ + +#include "../algs.h" +#include "entropy_encoder_kernel_abstract.h" +#include <iosfwd> +#include "../uintn.h" + +namespace dlib +{ + + class entropy_encoder_kernel_2 + { + /*! + GENERAL NOTES + this encoder is implemented using "range" coding + + INITIAL VALUE + out == 0 + initial_low == 0x00000001 (slightly more than zero) + initial_high == 0xffffffff (slightly less than one, 0.99999999976717) + low == initial_low + high == initial_high + + CONVENTION + if (out != 0) + *out == get_stream() + true == stream_is_set() + streambuf == out->rdbuf() + else + false == stream_is_set() + + + low == the low end of the range used for arithmetic encoding. + this number is used as a 32bit fixed point real number. + the point is fixed just before the first bit, so it is + always in the range [0,1) + + low is also never allowed to be zero to avoid overflow + in the calculation (high-low+1)/total. + + high == the high end of the range - 1 used for arithmetic encoding. + this number is used as a 32bit fixed point real number. + the point is fixed just before the first bit, so when we + interpret high as a real number then it is always in the + range [0,1) + + the range for arithmetic encoding is always + [low,high + 0.9999999...) the 0.9999999... is why + high == real upper range - 1 + !*/ + + public: + + entropy_encoder_kernel_2 ( + ); + + virtual ~entropy_encoder_kernel_2 ( + ); + + void clear( + ); + + void set_stream ( + std::ostream& out + ); + + bool stream_is_set ( + ) const; + + std::ostream& get_stream ( + ) const; + + void encode ( + uint32 low_count, + uint32 high_count, + uint32 total + ); + + private: + + void flush ( + ); + /*! + requires + out != 0 (i.e. there is a stream object to flush the data to + !*/ + + // restricted functions + entropy_encoder_kernel_2(entropy_encoder_kernel_2&); // copy constructor + entropy_encoder_kernel_2& operator=(entropy_encoder_kernel_2&); // assignment operator + + // data members + const uint32 initial_low; + const uint32 initial_high; + std::ostream* out; + uint32 low; + uint32 high; + std::streambuf* streambuf; + + }; + +} + +#ifdef NO_MAKEFILE +#include "entropy_encoder_kernel_2.cpp" +#endif + +#endif // DLIB_ENTROPY_ENCODER_KERNEl_2_ + diff --git a/ml/dlib/dlib/entropy_encoder/entropy_encoder_kernel_abstract.h b/ml/dlib/dlib/entropy_encoder/entropy_encoder_kernel_abstract.h new file mode 100644 index 000000000..48af93307 --- /dev/null +++ b/ml/dlib/dlib/entropy_encoder/entropy_encoder_kernel_abstract.h @@ -0,0 +1,161 @@ +// Copyright (C) 2003 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#undef DLIB_ENTROPY_ENCODER_KERNEl_ABSTRACT_ +#ifdef DLIB_ENTROPY_ENCODER_KERNEl_ABSTRACT_ + +#include "../algs.h" +#include <iosfwd> +#include "../uintn.h" + +namespace dlib +{ + + class entropy_encoder + { + /*! + INITIAL VALUE + stream_is_set() == false + + + WHAT THIS OBJECT REPRESENTS + This object represents an entropy encoder (could be implemented as an + arithmetic encoder for example). + + Note that all implementations of entropy_encoder and entropy_decoder + are paired. This means that if you use entropy_encoder_kernel_n to + encode something then you must use the corresponding + entropy_decoder_kernel_n to decode it. + + NOTATION: + At any moment each symbol has a certain probability of appearing in + the input stream. These probabilities may change as each symbol is + encountered and the probability model is updated accordingly. + + + let P(i) be a function which gives the probability of seeing the ith + symbol of an N symbol alphabet BEFORE the probability model is updated + to account for the current symbol. ( The domain of P(i) is from 0 to N-1. ) + + for each i: P(i) == COUNT/TOTAL where COUNT and TOTAL are integers. + and TOTAL is the same number for all P(i) but COUNT may vary. + + let LOW_COUNT(i) be the sum of all P(x)*TOTAL from x == 0 to x == i-1 + (note that LOW_COUNT(0) == 0) + let HIGH_COUNT(i) be the sum of all P(x)*TOTAL from x == 0 to x == i + !*/ + + public: + + entropy_encoder ( + ); + /*! + ensures + - #*this is properly initialized + throws + - std::bad_alloc + !*/ + + virtual ~entropy_encoder ( + ); + /*! + ensures + - all memory associated with *this has been released + - if (stream_is_set()) then + - any buffered data in *this will be written to get_stream() + !*/ + + void clear( + ); + /*! + ensures + - #*this has its initial value + - if (stream_is_set()) then + - any buffered data in *this will be written to get_stream() + - clears any memory of all previous calls to encode() from #*this + throws + - std::ios_base::failure + if (stream_is_set() && there was a problem writing to get_stream()) + then this exception will be thrown. #*this will be unusable until + clear() is called and succeeds + - any other exception + if this exception is thrown then #*this is unusable + until clear() is called and succeeds + !*/ + + + void set_stream ( + std::ostream& out + ); + /*! + ensures + - #get_stream() == out + - #stream_is_set() == true + - if (stream_is_set()) then + - any buffered data in *this will be written to get_stream() + - clears any memory of all previous calls to encode() from #*this + throws + - std::ios_base::failure + if (stream_is_set() && there was a problem writing to get_stream()) + then this exception will be thrown. #*this will be unusable until + clear() is called and succeeds + - any other exception + if this exception is thrown then #*this is unusable + until clear() is called and succeeds + !*/ + + bool stream_is_set ( + ) const; + /*! + ensures + - returns true if a stream has been associated with *this by calling + set_stream() + !*/ + + std::ostream& get_stream ( + ) const; + /*! + requires + - stream_is_set() == true + ensures + - returns a reference to the ostream object that *this writes its + encoded data to + !*/ + + void encode ( + uint32 low_count, + uint32 high_count, + uint32 total + ); + /*! + requires + - 0 < total < 65536 (2^16) + - total == TOTAL + - low_count < high_count <= total + - stream_is_set() == true + ensures + - encodes the symbol S where: + - LOW_COUNT(S) == low_count + - HIGH_COUNT(S) == high_count + throws + - std::ios_base::failure + if (there was a problem writing to get_stream()) then + this exception will be thrown. #*this will be unusable until + clear() is called and succeeds + - any other exception + if this exception is thrown then #*this is unusable + until clear() is called and succeeds + !*/ + + + private: + + // restricted functions + entropy_encoder(entropy_encoder&); // copy constructor + entropy_encoder& operator=(entropy_encoder&); // assignment operator + + }; + +} + +#endif // DLIB_ENTROPY_ENCODER_KERNEl_ABSTRACT_ + diff --git a/ml/dlib/dlib/entropy_encoder/entropy_encoder_kernel_c.h b/ml/dlib/dlib/entropy_encoder/entropy_encoder_kernel_c.h new file mode 100644 index 000000000..f11241ecc --- /dev/null +++ b/ml/dlib/dlib/entropy_encoder/entropy_encoder_kernel_c.h @@ -0,0 +1,112 @@ +// Copyright (C) 2003 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#ifndef DLIB_ENTROPY_ENCODER_KERNEl_C_ +#define DLIB_ENTROPY_ENCODER_KERNEl_C_ + +#include "entropy_encoder_kernel_abstract.h" +#include "../algs.h" +#include "../assert.h" +#include <iostream> + +namespace dlib +{ + + template < + typename encoder + > + class entropy_encoder_kernel_c : public encoder + { + + public: + std::ostream& get_stream ( + ) const; + + void encode ( + uint32 low_count, + uint32 high_count, + uint32 total + ); + + void flush ( + ); + + }; + +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + // member function definitions +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + + template < + typename encoder + > + std::ostream& entropy_encoder_kernel_c<encoder>:: + get_stream ( + ) const + { + // make sure requires clause is not broken + DLIB_CASSERT( this->stream_is_set() == true, + "\tstd::ostream& entropy_encoder::get_stream()" + << "\n\tyou must set a stream for this object before you can get it" + << "\n\tthis: " << this + ); + + // call the real function + return encoder::get_stream(); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename encoder + > + void entropy_encoder_kernel_c<encoder>:: + encode ( + uint32 low_count, + uint32 high_count, + uint32 total + ) + { + // make sure requires clause is not broken + DLIB_CASSERT( (0 < total) && (total < 65536) && (low_count < high_count) && (high_count <= total) && + (this->stream_is_set() == true), + "\tvoid entropy_encoder::encode()" + << "\n\trefer to the ensures clause for this function for further information" + << "\n\tthis: " << this + << "\n\ttotal: " << total + << "\n\tlow_count: " << low_count + << "\n\thigh_count: " << high_count + << "\n\tis_stream_set(): " << (this->stream_is_set() ? "true" : "false" ) + ); + + // call the real function + encoder::encode(low_count,high_count,total); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename encoder + > + void entropy_encoder_kernel_c<encoder>:: + flush ( + ) + { + // make sure requires clause is not broken + DLIB_CASSERT( this->stream_is_set() == true, + "\tvoid entropy_encoder::flush()" + << "\n\tyou must set a stream for this object before you can flush to it" + << "\n\tthis: " << this + ); + + // call the real function + encoder::flush(); + } + +// ---------------------------------------------------------------------------------------- + +} + +#endif // DLIB_ENTROPY_ENCODER_KERNEl_C_ + |