// Copyright (C) 2003 Davis E. King (davis@dlib.net) // License: Boost Software License See LICENSE.txt for the full license. #undef DLIB_CONDITIONING_CLASS_KERNEl_ABSTRACT_ #ifdef DLIB_CONDITIONING_CLASS_KERNEl_ABSTRACT_ #include "../algs.h" namespace dlib { template < unsigned long alphabet_size > class conditioning_class { /*! REQUIREMENTS ON alphabet_size 1 < alphabet_size < 65536 INITIAL VALUE get_total() == 1 get_count(X) == 0 : for all valid values of X except alphabet_size-1 get_count(alphabet_size-1) == 1 WHAT THIS OBJECT REPRESENTS This object represents a conditioning class used for arithmetic style compression. It maintains the cumulative counts which are needed by the entropy_coder and entropy_decoder objects. At any moment a conditioning_class object represents a set of alphabet_size symbols. Each symbol is associated with an integer called its count. All symbols start out with a count of zero except for alphabet_size-1. This last symbol will always have a count of at least one. It is intended to be used as an escape into a lower context when coding and so it must never have a zero probability or the decoder won't be able to identify the escape symbol. NOTATION: Let MAP(i) be a function which maps integers to symbols. MAP(i) is one to one and onto. Its domain is 1 to alphabet_size inclusive. Let RMAP(s) be the inverse of MAP(i). ( i.e. RMAP(MAP(i)) == i and MAP(RMAP(s)) == s ) Let COUNT(i) give the count for the symbol MAP(i). ( i.e. COUNT(i) == get_count(MAP(i)) ) Let LOW_COUNT(s) == the sum of COUNT(x) for x == 1 to x == RMAP(s)-1 (note that the sum of COUNT(x) for x == 1 to x == 0 is 0) Let HIGH_COUNT(s) == LOW_COUNT(s) + get_count(s) Basically what this is saying is just that you shoudln't assume you know what order the symbols are placed in when calculating the cumulative sums. The specific mapping provided by the MAP() function is unspecified. THREAD SAFETY This object can be used safely in a multithreaded program as long as the global state is not shared between conditioning classes which run on different threads. GLOBAL_STATE_TYPE The global_state_type obejct allows instances of the conditioning_class object to share any kind of global state the implementer desires. However, the global_state_type object exists primarily to facilitate the sharing of a memory pool between many instances of a conditioning_class object. But note that it is not required that there be any kind of memory pool at all, it is just a possibility. !*/ public: class global_state_type { global_state_type ( ); /*! ensures - #*this is properly initialized throws - std::bad_alloc !*/ // my contents are implementation specific. }; conditioning_class ( global_state_type& global_state ); /*! ensures - #*this is properly initialized - &#get_global_state() == &global_state throws - std::bad_alloc !*/ ~conditioning_class ( ); /*! ensures - all memory associated with *this has been released !*/ void clear( ); /*! ensures - #*this has its initial value throws - std::bad_alloc !*/ bool increment_count ( unsigned long symbol, unsigned short amount = 1 ); /*! requires - 0 <= symbol < alphabet_size - 0 < amount < 32768 ensures - if (sufficient memory is available to complete this operation) then - returns true - if (get_total()+amount < 65536) then - #get_count(symbol) == get_count(symbol) + amount - else - #get_count(symbol) == get_count(symbol)/2 + amount - if (get_count(alphabet_size-1) == 1) then - #get_count(alphabet_size-1) == 1 - else - #get_count(alphabet_size-1) == get_count(alphabet_size-1)/2 - for all X where (X != symbol)&&(X != alpahbet_size-1): #get_count(X) == get_count(X)/2 - else - returns false !*/ unsigned long get_count ( unsigned long symbol ) const; /*! requires - 0 <= symbol < alphabet_size ensures - returns the count for the specified symbol !*/ unsigned long get_total ( ) const; /*! ensures - returns the sum of get_count(X) for all valid values of X (i.e. returns the sum of the counts for all the symbols) !*/ unsigned long get_range ( unsigned long symbol, unsigned long& low_count, unsigned long& high_count, unsigned long& total_count ) const; /*! requires - 0 <= symbol < alphabet_size ensures - returns get_count(symbol) - if (get_count(symbol) != 0) then - #total_count == get_total() - #low_count == LOW_COUNT(symbol) - #high_count == HIGH_COUNT(symbol) - #low_count < #high_count <= #total_count !*/ void get_symbol ( unsigned long target, unsigned long& symbol, unsigned long& low_count, unsigned long& high_count ) const; /*! requires - 0 <= target < get_total() ensures - LOW_COUNT(#symbol) <= target < HIGH_COUNT(#symbol) - #low_count == LOW_COUNT(#symbol) - #high_count == HIGH_COUNT(#symbol) - #low_count < #high_count <= get_total() !*/ global_state_type& get_global_state ( ); /*! ensures - returns a reference to the global state used by *this !*/ unsigned long get_memory_usage ( ) const; /*! ensures - returns the number of bytes of memory allocated by all conditioning_class objects that share the global state given by get_global_state() !*/ static unsigned long get_alphabet_size ( ); /*! ensures - returns alphabet_size !*/ private: // restricted functions conditioning_class(conditioning_class&); // copy constructor conditioning_class& operator=(conditioning_class&); // assignment operator }; } #endif // DLIB_CONDITIONING_CLASS_KERNEl_ABSTRACT_