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.13 2005/02/08 14:02:24 tjdwave Exp $ $Name: Dirac_0_5_1 $
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 
00141         class Triple
00142         {
00143         public:
00145             Triple()
00146               : m_start(0),
00147                 m_stop(0),
00148                 m_weight(0) {}
00149 
00151             Triple(code_t start, code_t stop, code_t weight)
00152             {
00153                 m_start  = start;
00154                 m_stop   = stop;
00155                 m_weight = weight;
00156             }
00157 
00159             Triple(const Triple& rhs)
00160               : m_start(rhs.m_start),
00161                 m_stop(rhs.m_stop),
00162                 m_weight(rhs.m_weight) { }
00163 
00165             Triple & operator = (const Triple& rhs)
00166             {
00167                 m_start  = rhs.m_start;
00168                 m_stop   = rhs.m_stop;
00169                 m_weight = rhs.m_weight;
00170                 return *this;
00171             }
00172 
00174             code_t Start() const { return m_start; }
00175 
00177             code_t Stop() const  { return m_stop; }
00178 
00180             code_t Weight() const { return m_weight; }
00181 
00183             void SetValues(const code_t start , const code_t stop , const code_t wt)
00184             { 
00185                 m_start = start;
00186                 m_stop = stop; 
00187                 m_weight = wt;
00188             }
00189 
00190         private:
00192             code_t m_start;    
00193 
00195             code_t m_stop;
00196 
00198             code_t m_weight;    
00199         };
00200 
00202 
00207         class Context
00208         {
00209         public:
00211 
00214             Context()
00215             {
00216                 SetCounts(1,1);
00217             }
00218 
00220 
00223             Context(int cnt0,int cnt1)
00224             {
00225                 SetCounts(cnt0,cnt1);
00226             }
00227 
00229             Context(const Context & cpy)
00230               : count0( cpy.count0 ),
00231                 count1( cpy.count1 ),
00232                 trip0( cpy.trip0 ),
00233                 trip1( cpy.trip1 )
00234             {}
00235 
00237             Context & operator=(const Context& rhs)
00238             {
00239                 count0 = rhs.count0;
00240                 count1 = rhs.count1;
00241                 trip0  = rhs.trip0;
00242                 trip1  = rhs.trip1;
00243                 return *this;
00244             }
00245 
00247             ~Context() {}
00248 
00250 
00253             void SetCounts(int cnt0, int cnt1)
00254             {
00255                 count0 = cnt0;
00256                 count1 = cnt1;
00257                 SetTriples();
00258             }
00259 
00261             code_t GetCount0() const { return count0; }    
00262 
00264             code_t GetCount1() const { return count1; }    
00265 
00267 
00272             void IncrCount( const bool symbol , const int amnt )
00273             {
00274                 if ( symbol ) 
00275                     count1 += amnt; 
00276                 else 
00277                     count0 += amnt;
00278 
00279                 SetTriples();
00280             }
00281 
00283 
00287             void IncrCount( const bool symbol )
00288             {
00289                 if ( symbol ) 
00290                     count1++; 
00291                 else 
00292                     count0++;
00293 
00294                 SetTriples();
00295             }
00296 
00298             void HalveCounts()
00299             {
00300                 count0 >>= 1;
00301                 count0++;
00302                 count1 >>= 1;
00303                 count1++;
00304 
00305                 SetTriples();
00306             }
00307 
00309             code_t Weight() const { return trip0.Weight(); }
00310 
00312             const Triple & GetTriple( const bool symbol ) const { return (symbol ? trip1 : trip0); }
00313 
00315 
00321             bool GetSymbol(const calc_t num, const calc_t factor , Triple & trip_val) const
00322             {
00323                 if (num < trip0.Stop()*factor)
00324                 {
00325                     trip_val = trip0;
00326                     return false; //ie zero
00327                 }
00328                 else
00329                 {
00330                     trip_val = trip1;
00331                     return true; //ie 1
00332                 }
00333             } 
00334 
00335 
00336         private:
00337             code_t count0;
00338             code_t count1;
00339 
00340             Triple trip0;
00341             Triple trip1;
00342 
00343             void SetTriples()
00344             {
00345                 // updates triples given counts
00346                 code_t wt( count0 + count1 );
00347 
00348                 trip0.SetValues( 0 , count0 , wt );
00349                 trip1.SetValues( count0 , wt , wt );    
00350             }
00351         };
00352 
00353     protected:
00354 
00355         //virtual codec functions (to be overridden)
00357 
00359         virtual void InitContexts()=0;                                        
00360 
00362         virtual void Update( const bool symbol , const int context_num )=0;    
00363 
00365         virtual void ResetAll()=0;                                            
00366 
00367         //virtual encode-only functions
00369 
00371         virtual void DoWorkCode(T & in_data) = 0;    
00372 
00373         //core encode-only functions
00375 
00377         void InitEncoder();
00378 
00380         void EncodeTriple(const Triple & c , const calc_t range );
00381 
00383         void EncodeSymbol(const bool symbol, const int context_num);    
00384 
00386         void FlushEncoder(); 
00387 
00390         virtual void DoWorkDecode(T & out_data)=0;    
00391 
00392         // core decode-only functions
00394 
00396         void InitDecoder();                    
00397 
00399         void RemFromStream(const Triple & trip , const calc_t range);
00400 
00402         bool DecodeSymbol( const int context_num );
00403 
00404     private:
00406         int m_bit_count;                        
00407 
00409         int m_max_count;                        
00410 
00412         int m_underflow;                        
00413 
00415         code_t m_code;                    
00416 
00418         code_t m_low_code;                        
00419 
00421         code_t m_high_code;                    
00422 
00423         // Parameters for controlling coding/decoding
00424         // codec_params_type cparams;        
00425 
00427         BitInputManager* m_bit_input;                
00428 
00430         BasicOutputManager* m_bit_output;
00431 
00433         ArithCodec(const ArithCodec & cpy);
00434 
00436         ArithCodec & operator = (const ArithCodec & rhs);
00437 
00438         // For decoder only (could extend to the encoder later)
00439 
00441         char* m_decode_data_ptr;
00442 
00444         char* m_data_ptr;
00445 
00447         int m_input_bits_left;
00448 
00449     private:
00450 
00452         void ReadAllData();
00453 
00455         inline bool InputBit();
00456 
00457     protected:
00458 
00460         std::vector<Context> m_context_list;    
00461     };
00462 
00463     //Implementation - core functions
00465 
00466     template<class T>
00467     ArithCodec<T>::ArithCodec(BitInputManager* bits_in, size_t number_of_contexts)
00468       : m_bit_count( 0 ),
00469         m_bit_input( bits_in ),
00470         m_decode_data_ptr( 0 ),
00471         m_context_list( number_of_contexts )
00472     {
00473         // nothing needed here
00474     }    
00475 
00477     template<class T>
00478     ArithCodec<T>::ArithCodec(BasicOutputManager* bits_out, size_t number_of_contexts)
00479       : m_bit_count( 0 ),
00480         m_bit_output( bits_out ),
00481         m_decode_data_ptr( 0 ),
00482         m_context_list( number_of_contexts )
00483     {
00484         // nothing needed here
00485     }    
00486 
00487     template<class T>
00488     ArithCodec<T>::~ArithCodec()
00489     {
00490         if ( m_decode_data_ptr )
00491             delete[] m_decode_data_ptr;
00492     }
00493 
00494     template<class T>
00495     int ArithCodec<T>::Compress(T &in_data)
00496     {
00497         InitEncoder();                
00498         DoWorkCode(in_data);
00499         FlushEncoder();
00500 
00501         int byte_count( m_bit_count/8);
00502         if ( (byte_count*8)<m_bit_count )
00503             byte_count++;
00504 
00505         return byte_count;
00506     }
00507 
00508     template<class T>
00509     void ArithCodec<T>::Decompress( T &out_data, const int num_bytes )
00510     {
00511         m_max_count = num_bytes;
00512         InitDecoder();
00513         DoWorkDecode( out_data );
00514     }
00515 
00516     template<class T>
00517     void ArithCodec<T>::InitEncoder()
00518     {
00519         // Set the m_code word stuff
00520         m_low_code  = 0;
00521         m_high_code = CODE_MAX;
00522         m_underflow = 0;
00523 
00524         InitContexts();
00525     }
00526 
00527     template<class T>
00528     void ArithCodec<T>::EncodeTriple( const Triple &trip , const calc_t range)
00529     {
00530         //formulae given we know we're binary coding    
00531         if ( !trip.Start() ) // trip.Start()=0, so symbol is 0, so m_low_code unchanged 
00532             m_high_code = m_low_code + static_cast<code_t>(( range * trip.Stop() ) / trip.Weight() - 1 );
00533         else //symbol is 1, so m_high_code unchanged
00534             m_low_code += static_cast<code_t>(( range * trip.Start() ) / trip.Weight() );                
00535 
00536         do
00537         {
00538             if (( m_high_code & CODE_MSB ) == ( m_low_code & CODE_MSB ))
00539             {
00540                 m_bit_output->OutputBit( m_high_code & CODE_MSB, m_bit_count);
00541                 for (; m_underflow > 0; m_underflow-- )
00542                     m_bit_output->OutputBit(~m_high_code & CODE_MSB, m_bit_count);
00543             }
00544 
00545             else if ( ( m_low_code & CODE_2ND_MSB ) && !( m_high_code & CODE_2ND_MSB ))
00546             {
00547                 m_underflow ++;
00548                 m_low_code  ^= CODE_2ND_MSB;
00549                 m_high_code ^= CODE_2ND_MSB;
00550             }
00551             else return ;
00552 
00553             m_low_code  <<= 1;
00554             m_high_code <<= 1;
00555             m_high_code ++;
00556         }
00557         while ( true );
00558     }
00559 
00560     template<class T>
00561     inline void ArithCodec<T>::EncodeSymbol(const bool symbol, const int context_num)
00562     {
00563         const calc_t range( static_cast<calc_t>( m_high_code - m_low_code ) + 1 );
00564         EncodeTriple( m_context_list[context_num].GetTriple(symbol) , range );
00565         Update( symbol , context_num );
00566     }
00567 
00568     template<class T>
00569     void ArithCodec<T>::FlushEncoder()
00570     {
00571         // Flushes the output
00572         m_bit_output->OutputBit(m_low_code & CODE_2ND_MSB,m_bit_count);
00573         m_underflow++;
00574 
00575         while ( m_underflow-- > 0 )
00576             m_bit_output->OutputBit(~m_low_code & CODE_2ND_MSB, m_bit_count);
00577     }
00578 
00579     template<class T>
00580     void ArithCodec<T>::InitDecoder()
00581     {
00582         InitContexts();
00583 
00584         m_input_bits_left = 8; 
00585 
00586         ReadAllData();
00587 
00588         //Read in a full word of data
00589         code_t i;
00590         m_code = 0;
00591 
00592         for ( i = 0; i < (8 * sizeof(code_t)); i++ )
00593         {
00594             m_code <<= 1;
00595 
00596             if ( InputBit() )
00597                 m_code++;
00598         }
00599 
00600         m_low_code  = 0;
00601         m_high_code = CODE_MAX;
00602         m_underflow = 0;
00603     }
00604 
00605     template<class T>
00606     void ArithCodec<T>::RemFromStream( const Triple &trip , const calc_t range )
00607     {
00608         if( !trip.Start() )//trip.Start()=0, so symbol is 0, so m_low_code unchanged 
00609             m_high_code = m_low_code + static_cast<code_t>(( range * trip.Stop() ) / trip.Weight() - 1 );
00610 
00611         else//symbol is 1, so m_high_code unchanged
00612             m_low_code += static_cast<code_t>(( range * trip.Start() ) / trip.Weight() );        
00613 
00614         do
00615         {        
00616             if ( ( m_high_code & CODE_MSB ) == ( m_low_code & CODE_MSB ) )
00617             {
00618                 // Do nothing
00619             }        
00620             else if ( (m_low_code & CODE_2ND_MSB) && !(m_high_code & CODE_2ND_MSB) )
00621             {
00622                 m_code      ^= CODE_2ND_MSB;
00623                 m_low_code  ^= CODE_2ND_MSB;
00624                 m_high_code ^= CODE_2ND_MSB;
00625             }        
00626             else return;
00627 
00628             m_low_code  <<= 1;
00629             m_high_code <<= 1;
00630             m_high_code++;
00631             m_code      <<= 1;
00632 
00633             m_code += InputBit();
00634 
00635         } while ( true );
00636 
00637     }
00638 
00639     template<class T>
00640     inline bool ArithCodec<T>::DecodeSymbol( const int context_num )
00641     {
00642         Triple limits;
00643 
00644         const Context& c( m_context_list[context_num] );
00645         const calc_t count( ( static_cast<calc_t>( m_code - m_low_code ) + 1 ) * c.Weight() - 1 );
00646 
00647         const calc_t range( static_cast<calc_t>( m_high_code - m_low_code ) + 1 );
00648 
00649         bool symbol( m_context_list[context_num].GetSymbol( count , range , limits ) );
00650 
00651         RemFromStream( limits , range );
00652         Update(  symbol , context_num );
00653 
00654         return symbol;
00655     }
00656 
00657     template<class T>
00658     void ArithCodec<T>::ReadAllData()
00659     {
00660        if ( m_decode_data_ptr )
00661            delete[] m_decode_data_ptr;
00662 
00663        m_decode_data_ptr = new char[m_max_count + 2];
00664        m_bit_input->InputBytes( m_decode_data_ptr , m_max_count );
00665 
00666        m_decode_data_ptr[m_max_count] = 0;
00667        m_decode_data_ptr[m_max_count+1] = 0;
00668 
00669        m_data_ptr = m_decode_data_ptr;
00670 
00671     }
00672 
00673     template<class T>
00674     inline bool ArithCodec<T>::InputBit()
00675     {
00676         if (m_input_bits_left == 0)
00677         {
00678             m_data_ptr++;
00679             m_input_bits_left = 8;
00680         }
00681         m_input_bits_left--;
00682 
00683         return bool( ( (*m_data_ptr) >> m_input_bits_left ) & 1 );
00684     }
00685 
00686 }// end dirac namespace
00687 
00688 #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.