Dirac - A Video Codec

Created by the British Broadcasting Corporation.


arith_codec.h

Go to the documentation of this file.
00001 /* ***** BEGIN LICENSE BLOCK *****
00002 *
00003 * $Id: arith_codec.h,v 1.15 2005/04/13 15:06:58 asuraparaju Exp $ $Name: Dirac_0_5_2 $
00004 *
00005 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00006 *
00007 * The contents of this file are subject to the Mozilla Public License
00008 * Version 1.1 (the "License"); you may not use this file except in compliance
00009 * with the License. You may obtain a copy of the License at
00010 * http://www.mozilla.org/MPL/
00011 *
00012 * Software distributed under the License is distributed on an "AS IS" basis,
00013 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License for
00014 * the specific language governing rights and limitations under the License.
00015 *
00016 * The Original Code is BBC Research and Development m_code.
00017 *
00018 * The Initial Developer of the Original Code is the British Broadcasting
00019 * Corporation.
00020 * Portions created by the Initial Developer are Copyright (C) 2004.
00021 * All Rights Reserved.
00022 *
00023 * Contributor(s):    Richard Felton (Original Author),
00024                     Thomas Davies,
00025                     Scott R Ladd
00026 *
00027 * Alternatively, the contents of this file may be used under the terms of
00028 * the GNU General Public License Version 2 (the "GPL"), or the GNU Lesser
00029 * Public License Version 2.1 (the "LGPL"), in which case the provisions of
00030 * the GPL or the LGPL are applicable instead of those above. If you wish to
00031 * allow use of your version of this file only under the terms of the either
00032 * the GPL or LGPL and not to allow others to use your version of this file
00033 * under the MPL, indicate your decision by deleting the provisions above
00034 * and replace them with the notice and other provisions required by the GPL
00035 * or LGPL. If you do not delete the provisions above, a recipient may use
00036 * your version of this file under the terms of any one of the MPL, the GPL
00037 * or the LGPL.
00038 * ***** END LICENSE BLOCK ***** */
00039 
00040 
00041 #ifndef _ARITH_CODEC_H_
00042 #define _ARITH_CODEC_H_
00043 
00052 
00053 #include <libdirac_common/common.h>
00054 #include <libdirac_common/bit_manager.h>
00055 #include <vector>
00056 
00057 #ifdef _MSC_VER // define types for MSVC compiler on Windows
00058     typedef unsigned short    uint16_t;
00059     typedef unsigned _int32    uint32_t;
00060 #else // include header file for types for Linux
00061     #include <inttypes.h>
00062 #endif
00063 
00064 namespace dirac
00065 {
00067 
00072     template<class T> //T is container/array type
00073     class ArithCodec
00074     {
00075     public:
00076 
00078 
00084         ArithCodec(BasicOutputManager * bits_out, size_t number_of_contexts);
00085 
00087 
00093         ArithCodec(BitInputManager * bits_in, size_t number_of_contexts);
00094 
00096 
00099         virtual ~ArithCodec();
00100 
00102 
00110         int Compress(T & in_data);
00111     
00113 
00121         void Decompress(T & out_data, const int num_bytes);
00122 
00123     protected:
00124 
00125         // use explicity type sizes for portability
00126         typedef uint16_t code_t;
00127         typedef uint32_t calc_t;
00128 
00129         // NOTE: These macros imply an unsigned 16-bit operand
00130         static const code_t CODE_MAX     = 0xffff;
00131         static const code_t CODE_MSB     = ((0xffff + 1) >> 1);
00132         static const code_t CODE_2ND_MSB = ((0xffff + 1) >> 2);
00133 
00135 
00140         class ProbInterval
00141         {
00142         public:
00144             ProbInterval()
00145               : m_start(0),
00146                 m_stop(1024)
00147               {}
00148 
00150             ProbInterval( calc_t start , calc_t stop)
00151             {
00152                 m_start  = start;
00153                 m_stop   = stop;
00154             }
00155 
00157             ProbInterval(const ProbInterval& rhs)
00158               : m_start(rhs.m_start),
00159                 m_stop(rhs.m_stop){ }
00160 
00162             ProbInterval & operator = (const ProbInterval& rhs)
00163             {
00164                 m_start  = rhs.m_start;
00165                 m_stop   = rhs.m_stop;
00166                 return *this;
00167             }
00168 
00170             calc_t Start() const { return m_start; }
00171 
00173             calc_t Stop() const  { return m_stop; }
00174 
00176             void SetValues(const calc_t start , const calc_t stop)
00177             { 
00178                 m_start = start;
00179                 m_stop = stop; 
00180             }
00181 
00182         private:
00184             calc_t m_start;    
00185 
00187             calc_t m_stop;
00188 
00189         };
00190 
00192 
00197         class Context
00198         {
00199         public:
00201 
00204             Context()
00205             {
00206                 SetCounts( 1 , 1 );
00207             }
00208 
00210 
00213             Context(int cnt0,int cnt1)
00214             {
00215                 SetCounts( cnt0 , cnt1 );
00216             }
00217 
00219             Context(const Context & cpy)
00220               : m_num0( cpy.m_num0 ),
00221                 m_num1( cpy.m_num1 ),
00222                 m_weight( cpy.m_weight ),
00223                 m_r0( cpy.m_r0 ),
00224                 m_r1( cpy.m_r1 )
00225             {}
00226 
00228             Context & operator=(const Context& rhs)
00229             {
00230                 m_num0 = rhs.m_num0;
00231                 m_num1 = rhs.m_num1;
00232                 m_weight = rhs.m_weight;
00233                 m_r0  = rhs.m_r0;
00234                 m_r1  = rhs.m_r1;
00235                 return *this;
00236             }
00237 
00239             ~Context() {}
00240 
00242 
00245             void SetCounts(const int cnt0, const int cnt1)
00246             {
00247                 m_num0 = cnt0;
00248                 m_num1 = cnt1;
00249                 m_weight = cnt0 + cnt1;
00250                 SetRanges();
00251             }
00252 
00254             calc_t GetCount0() const { return m_num0; }    
00255 
00257             calc_t GetCount1() const { return m_num1; }    
00258 
00260             calc_t Weight() const { return m_weight; }    
00261 
00263 
00267             inline void IncrCount( const bool symbol )
00268             {
00269                 if ( symbol ) 
00270                     m_num1++; 
00271                 else 
00272                     m_num0++;
00273 
00274                 m_weight++;
00275 
00276                 if ( m_weight & 1 )
00277                     SetRanges();
00278             }
00279 
00281             inline void HalveCounts()
00282             {
00283                 m_num0 >>= 1;
00284                 m_num0++;
00285                 m_num1 >>= 1;
00286                 m_num1++;
00287 
00288                 m_weight = m_num0 + m_num1;
00289 
00290                 SetRanges();
00291             }
00292 
00294             const ProbInterval & GetProbInterval( const bool symbol ) const { return (symbol ? m_r1 : m_r0); }
00295 
00297 
00300             bool GetSymbol(const calc_t num, const calc_t factor , ProbInterval & prob_val) const
00301             {
00302                 if (num < m_r0.Stop()*factor)
00303                 {
00304                     prob_val = m_r0;
00305                     return false; //ie zero
00306                 }
00307                 else
00308                 {
00309                     prob_val = m_r1;
00310                     return true; //ie 1
00311                 }
00312             } 
00313 
00314             inline void SetRanges()
00315             {
00316                 // Updates the probability ranges
00317                 
00318                 const calc_t end0( ( m_num0 * 1024 ) / m_weight );
00319 
00320                 m_r0.SetValues( 0 , end0 );
00321                 m_r1.SetValues( end0 , 1024 );    
00322 
00323             }
00324 
00325         private:
00326             calc_t m_num0;
00327             calc_t m_num1;
00328 
00329             calc_t m_weight;
00330             
00331             ProbInterval m_r0;
00332             ProbInterval m_r1;
00333           
00334 
00335         };
00336 
00337     protected:
00338 
00339         //virtual codec functions (to be overridden)
00341 
00343         virtual void InitContexts()=0;                                        
00344 
00346         void Update( const bool symbol , const int context_num );    
00347 
00349         virtual void ResetAll()=0;
00350 
00351         //virtual encode-only functions
00353 
00355         virtual void DoWorkCode(T & in_data) = 0;    
00356 
00357         //core encode-only functions
00359 
00361         void InitEncoder();
00362 
00364         void EncodeProbInterval(const ProbInterval & prob_interval , const calc_t range );
00365 
00367         void EncodeSymbol(const bool symbol, const int context_num);    
00368 
00370         void FlushEncoder(); 
00371 
00374         virtual void DoWorkDecode(T & out_data)=0;    
00375 
00376         // core decode-only functions
00378 
00380         void InitDecoder();                    
00381 
00383         void RemFromStream(const ProbInterval & prob_interval , const calc_t range);
00384 
00386         bool DecodeSymbol( const int context_num );
00387 
00388     private:
00390         int m_bit_count;                        
00391 
00393         int m_max_count;                        
00394 
00396         int m_underflow;                        
00397 
00399         code_t m_code;                    
00400 
00402         code_t m_low_code;                        
00403 
00405         code_t m_high_code;                    
00406 
00407         // Parameters for controlling coding/decoding
00408         // codec_params_type cparams;        
00409 
00411         BitInputManager* m_bit_input;                
00412 
00414         BasicOutputManager* m_bit_output;
00415 
00417         ArithCodec(const ArithCodec & cpy);
00418 
00420         ArithCodec & operator = (const ArithCodec & rhs);
00421 
00422         // For decoder only (could extend to the encoder later)
00423 
00425         char* m_decode_data_ptr;
00426 
00428         char* m_data_ptr;
00429 
00431         int m_input_bits_left;
00432 
00433     private:
00434 
00436         void ReadAllData();
00437 
00439         inline bool InputBit();
00440 
00441 
00442 
00443 
00444     protected:
00445 
00447         std::vector<Context> m_context_list;    
00448     };
00449 
00450     //Implementation - core functions
00452 
00453     template<class T>
00454     ArithCodec<T>::ArithCodec(BitInputManager* bits_in, size_t number_of_contexts)
00455       : m_bit_count( 0 ),
00456         m_bit_input( bits_in ),
00457         m_decode_data_ptr( 0 ),
00458         m_context_list( number_of_contexts )
00459     {
00460         // nothing needed here
00461     }    
00462 
00464     template<class T>
00465     ArithCodec<T>::ArithCodec(BasicOutputManager* bits_out, size_t number_of_contexts)
00466       : m_bit_count( 0 ),
00467         m_bit_output( bits_out ),
00468         m_decode_data_ptr( 0 ),
00469         m_context_list( number_of_contexts )
00470     {
00471         // nothing needed here
00472     }    
00473 
00474     template<class T>
00475     ArithCodec<T>::~ArithCodec()
00476     {
00477         if ( m_decode_data_ptr )
00478             delete[] m_decode_data_ptr;
00479     }
00480 
00481     template<class T>
00482     int ArithCodec<T>::Compress(T &in_data)
00483     {
00484         InitEncoder();                
00485         DoWorkCode(in_data);
00486         FlushEncoder();
00487 
00488         int byte_count( m_bit_count/8);
00489         if ( (byte_count*8)<m_bit_count )
00490             byte_count++;
00491 
00492         return byte_count;
00493     }
00494 
00495     template<class T>
00496     void ArithCodec<T>::Decompress( T &out_data, const int num_bytes )
00497     {
00498         m_max_count = num_bytes;
00499         InitDecoder();
00500         DoWorkDecode( out_data );
00501     }
00502 
00503     template<class T>
00504     void ArithCodec<T>::InitEncoder()
00505     {
00506         // Set the m_code word stuff
00507         m_low_code  = 0;
00508         m_high_code = CODE_MAX;
00509         m_underflow = 0;
00510 
00511         InitContexts();
00512     }
00513 
00514     template<class T>
00515     void ArithCodec<T>::EncodeProbInterval( const ProbInterval& prob_interval , const calc_t range)
00516     {
00517         //formulae given we know we're binary coding    
00518         if ( !prob_interval.Start() ) // prob_interval.Start()=0, so symbol is 0, so m_low_code unchanged 
00519             m_high_code = m_low_code + static_cast<code_t>( ( ( range * prob_interval.Stop() )>>10 ) - 1 );
00520         else //symbol is 1, so m_high_code unchanged
00521             m_low_code += static_cast<code_t>(( range * prob_interval.Start() ) >>10 );                
00522 
00523         do
00524         {
00525             if (( m_high_code & CODE_MSB ) == ( m_low_code & CODE_MSB ))
00526             {
00527                 m_bit_output->OutputBit( m_high_code & CODE_MSB, m_bit_count);
00528                 for (; m_underflow > 0; m_underflow-- )
00529                     m_bit_output->OutputBit(~m_high_code & CODE_MSB, m_bit_count);
00530             }
00531 
00532             else if ( ( m_low_code & CODE_2ND_MSB ) && !( m_high_code & CODE_2ND_MSB ))
00533             {
00534                 m_underflow ++;
00535                 m_low_code  ^= CODE_2ND_MSB;
00536                 m_high_code ^= CODE_2ND_MSB;
00537             }
00538             else return ;
00539 
00540             m_low_code  <<= 1;
00541             m_high_code <<= 1;
00542             m_high_code ++;
00543         }
00544         while ( true );
00545     }
00546 
00547     template<class T>
00548     inline void ArithCodec<T>::EncodeSymbol(const bool symbol, const int context_num)
00549     {
00550         const calc_t range( static_cast<calc_t>( m_high_code - m_low_code ) + 1 );
00551         EncodeProbInterval( m_context_list[context_num].GetProbInterval(symbol) , range );
00552         Update( symbol , context_num );
00553     }
00554 
00555     template<class T>
00556     void ArithCodec<T>::FlushEncoder()
00557     {
00558         // Flushes the output
00559         m_bit_output->OutputBit(m_low_code & CODE_2ND_MSB,m_bit_count);
00560         m_underflow++;
00561 
00562         while ( m_underflow-- > 0 )
00563             m_bit_output->OutputBit(~m_low_code & CODE_2ND_MSB, m_bit_count);
00564     }
00565 
00566     template<class T>
00567     void ArithCodec<T>::InitDecoder()
00568     {
00569         InitContexts();
00570 
00571         m_input_bits_left = 8; 
00572 
00573         ReadAllData();
00574 
00575         //Read in a full word of data
00576         code_t i;
00577         m_code = 0;
00578 
00579         for ( i = 0; i < (8 * sizeof(code_t)); i++ )
00580         {
00581             m_code <<= 1;
00582 
00583             if ( InputBit() )
00584                 m_code++;
00585         }
00586 
00587         m_low_code  = 0;
00588         m_high_code = CODE_MAX;
00589         m_underflow = 0;
00590     }
00591 
00592     template<class T>
00593     void ArithCodec<T>::RemFromStream( const ProbInterval& prob_interval , const calc_t range )
00594     {
00595         if( !prob_interval.Start() )//prob_interval.Start()=0, so symbol is 0, so m_low_code unchanged 
00596             m_high_code = m_low_code + static_cast<code_t>( ( ( range * prob_interval.Stop() )>>10 ) - 1 );
00597 
00598         else//symbol is 1, so m_high_code unchanged
00599             m_low_code += static_cast<code_t>(( range * prob_interval.Start() )>>10 );        
00600 
00601         do
00602         {        
00603             if ( ( m_high_code & CODE_MSB ) == ( m_low_code & CODE_MSB ) )
00604             {
00605                 // Do nothing
00606             }        
00607             else if ( (m_low_code & CODE_2ND_MSB) && !(m_high_code & CODE_2ND_MSB) )
00608             {
00609                 m_code      ^= CODE_2ND_MSB;
00610                 m_low_code  ^= CODE_2ND_MSB;
00611                 m_high_code ^= CODE_2ND_MSB;
00612             }        
00613             else return;
00614 
00615             m_low_code  <<= 1;
00616             m_high_code <<= 1;
00617             m_high_code++;
00618             m_code      <<= 1;
00619 
00620             m_code += InputBit();
00621 
00622         } while ( true );
00623 
00624     }
00625 
00626     template<class T>
00627     inline bool ArithCodec<T>::DecodeSymbol( const int context_num )
00628     {
00629         ProbInterval limits;
00630 
00631         const calc_t count( ( ( static_cast<calc_t>( m_code - m_low_code ) + 1 )<<10 ) - 1 );
00632 
00633         const calc_t range( static_cast<calc_t>( m_high_code - m_low_code ) + 1 );
00634 
00635         bool symbol( m_context_list[context_num].GetSymbol( count , range , limits ) );
00636 
00637         RemFromStream( limits , range );
00638         Update(  symbol , context_num );
00639 
00640         return symbol;
00641     }
00642 
00643     template<class T>
00644     void ArithCodec<T>::ReadAllData()
00645     {
00646        if ( m_decode_data_ptr )
00647            delete[] m_decode_data_ptr;
00648 
00649        m_decode_data_ptr = new char[m_max_count + 2];
00650        m_bit_input->InputBytes( m_decode_data_ptr , m_max_count );
00651 
00652        m_decode_data_ptr[m_max_count] = 0;
00653        m_decode_data_ptr[m_max_count+1] = 0;
00654 
00655        m_data_ptr = m_decode_data_ptr;
00656 
00657     }
00658 
00659     template<class T>
00660     inline bool ArithCodec<T>::InputBit()
00661     {
00662         if (m_input_bits_left == 0)
00663         {
00664             m_data_ptr++;
00665             m_input_bits_left = 8;
00666         }
00667         m_input_bits_left--;
00668 
00669         return bool( ( (*m_data_ptr) >> m_input_bits_left ) & 1 );
00670     }
00671 
00672     template<class T>
00673     inline void ArithCodec<T>::Update( const bool symbol , const int context_num )
00674     {
00675         Context& ctx = m_context_list[context_num];
00676 
00677         ctx.IncrCount( symbol );
00678     
00679         if ( ctx.Weight() >= 1024 )
00680             ctx.HalveCounts();
00681     }
00682 
00683 
00684 }// end dirac namespace
00685 
00686 #endif

© 2004 British Broadcasting Corporation. Dirac code licensed under the Mozilla Public License (MPL) Version 1.1.
HTML documentation generated by Dimitri van Heesch's excellent Doxygen tool.