arith_codec.h

/* ***** BEGIN LICENSE BLOCK *****
*
* $Id: arith_codec.h,v 1.2 2005/01/30 05:11:39 gabest Exp $ $Name:  $
*
* Version: MPL 1.1/GPL 2.0/LGPL 2.1
*
* The contents of this file are subject to the Mozilla Public License
* Version 1.1 (the "License"); you may not use this file except in compliance
* with the License. You may obtain a copy of the License at
* http://www.mozilla.org/MPL/
*
* Software distributed under the License is distributed on an "AS IS" basis,
* WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License for
* the specific language governing rights and limitations under the License.
*
* The Original Code is BBC Research and Development m_code.
*
* The Initial Developer of the Original Code is the British Broadcasting
* Corporation.
* Portions created by the Initial Developer are Copyright (C) 2004.
* All Rights Reserved.
*
* Contributor(s):    Richard Felton (Original Author),
                    Thomas Davies,
                    Scott R Ladd
*
* Alternatively, the contents of this file may be used under the terms of
* the GNU General Public License Version 2 (the "GPL"), or the GNU Lesser
* Public License Version 2.1 (the "LGPL"), in which case the provisions of
* the GPL or the LGPL are applicable instead of those above. If you wish to
* allow use of your version of this file only under the terms of the either
* the GPL or LGPL and not to allow others to use your version of this file
* under the MPL, indicate your decision by deleting the provisions above
* and replace them with the notice and other provisions required by the GPL
* or LGPL. If you do not delete the provisions above, a recipient may use
* your version of this file under the terms of any one of the MPL, the GPL
* or the LGPL.
* ***** END LICENSE BLOCK ***** */


#ifndef _ARITH_CODEC_H_
#define _ARITH_CODEC_H_


#include <libdirac_common/common.h>
#include <libdirac_common/bit_manager.h>
#include <vector>

#ifdef _MSC_VER // define types for MSVC compiler on Windows
    typedef unsigned short    uint16_t;
    typedef unsigned _int32    uint32_t;
#else // include header file for types for Linux
    #include <inttypes.h>
#endif

namespace dirac
{

    template<class T> //T is container/array type
    class ArithCodec
    {
    public:


        ArithCodec(BasicOutputManager * bits_out, size_t number_of_contexts);
    

        ArithCodec(BitInputManager * bits_in, size_t number_of_contexts);
    

        virtual ~ArithCodec();
    

        int Compress(T & in_data);
    

        void Decompress(T & out_data, int num_bits);
    
    protected:
    
        // use explicity type sizes for portability
        typedef uint16_t code_t;
        typedef uint32_t calc_t;
    
        // NOTE: These macros imply an unsigned 16-bit operand
        static const code_t CODE_MAX     = 0xffff;
        static const code_t CODE_MSB     = ((0xffff + 1) >> 1);
        static const code_t CODE_2ND_MSB = ((0xffff + 1) >> 2);
    

        class Triple
        {
        public:
            Triple()
              : m_start(0),
                m_stop(0),
                m_weight(0) {}
    
            // value constructor
            Triple(code_t start, code_t stop, code_t weight)
            {
                m_start  = start;
                m_stop   = stop;
                m_weight = weight;
            }
    
            Triple(const Triple& rhs)
              : m_start(rhs.m_start),
                m_stop(rhs.m_stop),
                m_weight(rhs.m_weight) { }
    
            Triple & operator = (const Triple& rhs)
            {
                m_start  = rhs.m_start;
                m_stop   = rhs.m_stop;
                m_weight = rhs.m_weight;
                return *this;
            }
    
            // get the start value    
            code_t Start() const { return m_start; }
    
            // get the stop value    
            code_t Stop() const  { return m_stop; }
    
            // get the weight value    
            code_t Weight() const { return m_weight; }
    
        private:
            code_t m_start;    
    
            code_t m_stop;
    
            code_t m_weight;    
        };
    

        class Context
        {
        public:

            Context()
            {
                SetCounts(1,1);
            }
    

            Context(int cnt0,int cnt1)
            {
                SetCounts(cnt0,cnt1);
            }
    
            Context(const Context & cpy)
              : count0(cpy.count0),
                count1(cpy.count1),
                trip0(cpy.trip0),
                trip1(cpy.trip1)
            {}
    
            Context & operator=(const Context& rhs)
            {
                count0 = rhs.count0;
                count1 = rhs.count1;
                trip0  = rhs.trip0;
                trip1  = rhs.trip1;
                return *this;
            }
    
            ~Context() {}
    

            void SetCounts(int cnt0, int cnt1)
            {
                count0 = cnt0;
                count1 = cnt1;
                SetTriples();
            }
    
            code_t GetCount0() const { return count0; }    
    
            code_t GetCount1() const { return count1; }    
    

            void IncrCount(bool symbol, int amnt)
            {
                if ( symbol ) 
                    count1 += amnt; 
                else 
                    count0 += amnt;
    
                SetTriples();
            }
    
            void HalveCounts()
            {
                count0 >>= 1;
                count0++;
                count1 >>= 1;
                count1++;
    
                SetTriples();
            }
    
            code_t Weight() const { return trip0.Weight(); }
    
            const Triple & GetTriple( const bool symbol ) const { return (symbol ? trip1 : trip0); }
    

            bool GetSymbol(const code_t num, Triple & trip_val) const
            {
                if (num < trip0.Stop())
                {
                    trip_val = trip0;
                    return false; //ie zero
                }
                else
                {
                    trip_val = trip1;
                    return true; //ie 1
                }
            } 
    
        private:
            code_t count0;
            code_t count1;
    
            Triple trip0;
            Triple trip1;
    
            void SetTriples()
            {
                //updates triples given counts
                trip0 = Triple(0, trip0.Start() + count0, count0 + count1);    
                trip1 = Triple(trip0.Stop(), trip1.Start() + count1, trip0.Weight());    
            }
        };
    
    protected:
    
        //std::vector<Context> & ContextList() { return m_context_list; }
    
        //virtual codec functions (to be overridden)
    
        virtual void InitContexts()=0;                                        
    
        virtual void Update( const bool symbol , const int context_num )=0;    
    
        virtual void Resize(const int context_num)=0;                        
    
        virtual void ResetAll()=0;                                            
    
        virtual int ChooseContext(const T &data, const int bin_number) const =0;
    
        virtual int ChooseContext(const T &data) const=0;                         
    
        //virtual encode-only functions
    
        virtual void DoWorkCode(T & in_data) = 0;    
    
        //core encode-only functions
    
        void InitEncoder();
    
        void EncodeTriple(const Triple & c);
    
        void EncodeSymbol(const bool symbol, const int context_num);    
    
        void FlushEncoder(); 
    
        void FlushDecoder(); 
    
        virtual void DoWorkDecode(T & out_data, int num_bits)=0;    
    
        // core decode-only functions
    
        void InitDecoder();                    
    
        void RemFromStream(const Triple & c);
    
        void SetCurrentCount(const int context_num); 
    
        void DecodeSymbol(bool& symbol, int context_num); 
    
    private:
        int m_bit_count;                        
    
        int m_max_count;                        
    
        int m_underflow;                        
    
        code_t m_code;                    
    
        code_t m_count;                        
    
        code_t m_low_code;                        
    
        code_t m_high_code;                    
    
        // Parameters for controlling coding/decoding
        // codec_params_type cparams;        
    
        BitInputManager* m_bit_input;                
    
        BasicOutputManager* m_bit_output;
    
        //private, bodyless copy constructor: class should not be copied
        ArithCodec(const ArithCodec & cpy);
    
        //private, bodyless copy operator=: class should not be assigned
        ArithCodec & operator = (const ArithCodec & rhs);
    
    
    protected:
    
        std::vector<Context> m_context_list;    
    };
    
    //Implementation - core functions
    
    template<class T>
    ArithCodec<T>::ArithCodec(BitInputManager* bits_in, size_t number_of_contexts)
      : m_bit_count(0),
        m_bit_input(bits_in),
        m_context_list(number_of_contexts)
    {
        // nothing needed here
    }    
    
    template<class T>
    ArithCodec<T>::ArithCodec(BasicOutputManager* bits_out, size_t number_of_contexts)
      : m_bit_count(0),
        m_bit_output(bits_out),
        m_context_list(number_of_contexts)
    {
        // nothing needed here
    }    
    
    template<class T>
    ArithCodec<T>::~ArithCodec()
    {
        // nothing needed here
    }
    
    template<class T>
    int ArithCodec<T>::Compress(T &in_data)
    {
        InitEncoder();                
        DoWorkCode(in_data);
        FlushEncoder();
        return m_bit_count;
    }
    
    template<class T>
    void ArithCodec<T>::Decompress(T &out_data, int num_bits)
    {
        m_max_count=num_bits;
        InitDecoder();
        DoWorkDecode(out_data,num_bits);
        FlushDecoder();        
        m_bit_input->FlushInput();
    }
    
    template<class T>
    void ArithCodec<T>::InitEncoder()
    {
        // Set the m_code word stuff
        m_low_code  = 0;
        m_high_code = CODE_MAX;
        m_underflow = 0;
    }
    
    template<class T>
    void ArithCodec<T>::EncodeTriple(const Triple &c)
    {
        // Rescale m_high_code and m_low_code for the new symbol
        calc_t range( static_cast<calc_t>(m_high_code - m_low_code) + 1 );
    
        //formulae given we know we're binary coding    
        if (!c.Start()) // c.Start()=0, so symbol is 0, so m_low_code unchanged 
            m_high_code = m_low_code + static_cast<code_t>(( range * c.Stop() ) / c.Weight() - 1 );
        else //symbol is 1, so m_high_code unchanged
            m_low_code += static_cast<code_t>(( range * c.Start() ) / c.Weight() );                
    
        do
        {
            if (( m_high_code & CODE_MSB ) == ( m_low_code & CODE_MSB ))
            {
                m_bit_output->OutputBit( m_high_code & CODE_MSB, m_bit_count);
                while ( m_underflow > 0 )
                {
                    m_bit_output->OutputBit(~m_high_code & CODE_MSB, m_bit_count);
                    m_underflow--;
                }
            }
    
            else if ( ( m_low_code & CODE_2ND_MSB ) && !( m_high_code & CODE_2ND_MSB ))
            {
                m_underflow += 1;
                m_low_code  &= (CODE_2ND_MSB) - 1;
                m_high_code |= CODE_2ND_MSB;
            }
            else return ;
    
            m_low_code  <<= 1;
            m_high_code <<= 1;
            m_high_code  |= 1;
        }
        while(true);
    }
    
    template<class T>
    inline void ArithCodec<T>::EncodeSymbol(const bool symbol, const int context_num)
    {
        EncodeTriple(m_context_list[context_num].GetTriple(symbol));
        Update( symbol , context_num );
    }
    
    template<class T>
    void ArithCodec<T>::FlushEncoder()
    {
        // Flushes the output
        m_bit_output->OutputBit(m_low_code & CODE_2ND_MSB,m_bit_count);
        m_underflow++;
    
        while ( m_underflow-- > 0 )
            m_bit_output->OutputBit(~m_low_code & CODE_2ND_MSB, m_bit_count);
    }
    
    template<class T>
    void ArithCodec<T>::InitDecoder()
    {
        //Read in a full word of data
           code_t i;
        m_code = 0;
    
        for ( i = 0; i < (8 * sizeof(code_t)); i++ )
        {
            m_code <<= 1;
    
            if (m_bit_input->InputBit(m_bit_count,m_max_count))
                m_code++;
        }
    
        m_low_code  = 0;
        m_high_code = CODE_MAX;
        m_underflow = 0;
    }
    
    template<class T>
    void ArithCodec<T>::RemFromStream( const Triple &c )
    {
       
        calc_t range( static_cast<calc_t>( m_high_code - m_low_code ) + 1 );
    
        if(!c.Start())//c.Start()=0, so symbol is 0, so m_low_code unchanged 
            m_high_code = m_low_code + static_cast<code_t>(( range * c.Stop() ) / c.Weight() - 1 );
    
        else//symbol is 1, so m_high_code unchanged
            m_low_code += static_cast<code_t>(( range * c.Start() ) / c.Weight() );        
    
        do
        {        
            if ( ( m_high_code & CODE_MSB ) == ( m_low_code & CODE_MSB ) )
            {
                // Do nothing
            }        
            else if ((m_low_code & CODE_2ND_MSB) == CODE_2ND_MSB  && (m_high_code & CODE_2ND_MSB) == 0 )
            {
                m_code      ^= CODE_2ND_MSB;
                m_low_code  &= (CODE_2ND_MSB) - 1;
                m_high_code |= CODE_2ND_MSB;
            }        
            else return;
    
            m_low_code  <<= 1;
            m_high_code <<= 1;
            m_high_code  |= 1;
            m_code      <<= 1;
    
            if ( m_bit_input->InputBit( m_bit_count , m_max_count ) )
                m_code++; 
    
        } while (1);
    
    }
    
    template<class T>
    void ArithCodec<T>::SetCurrentCount(const int context_num)
    {
        calc_t range;
        range = static_cast<calc_t>( m_high_code - m_low_code ) + 1;
        m_count = static_cast<code_t>( 
                                      ( ( static_cast<calc_t>( m_code - m_low_code ) + 1 ) * m_context_list[context_num].Weight() - 1 ) 
                                      / range );
    }
    
    template<class T>
    void ArithCodec<T>::DecodeSymbol(bool& symbol, const int context_num)
    {
        Triple limits;    
        SetCurrentCount( context_num );
        symbol = m_context_list[context_num].GetSymbol( m_count , limits );        
        RemFromStream( limits );
        Update(  symbol , context_num );
    }
    
    template<class T>
    void ArithCodec<T>::FlushDecoder()
    {
        // Flushes the input
        while(m_bit_count < m_max_count)
            m_bit_input->InputBit( m_bit_count , m_max_count );
    }
    
} //namespace dirac
#endif

---