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.36 2007/03/01 09:24:32 tjdwave Exp $ $Name:  $
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 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                     Peter Bleackley,
00027                     Steve Bearcroft,
00028                     Anuradha Suraparaju,
00029                     Tim Borer (major refactor February 2006)
00030                     Andrew Kennedy
00031 *
00032 * Alternatively, the contents of this file may be used under the terms of
00033 * the GNU General Public License Version 2 (the "GPL"), or the GNU Lesser
00034 * Public License Version 2.1 (the "LGPL"), in which case the provisions of
00035 * the GPL or the LGPL are applicable instead of those above. If you wish to
00036 * allow use of your version of this file only under the terms of the either
00037 * the GPL or LGPL and not to allow others to use your version of this file
00038 * under the MPL, indicate your decision by deleting the provisions above
00039 * and replace them with the notice and other provisions required by the GPL
00040 * or LGPL. If you do not delete the provisions above, a recipient may use
00041 * your version of this file under the terms of any one of the MPL, the GPL
00042 * or the LGPL.
00043 * ***** END LICENSE BLOCK ***** */
00044 
00045 
00046 #ifndef _ARITH_CODEC_H_
00047 #define _ARITH_CODEC_H_
00048 
00057 
00058 #include <libdirac_common/common.h>
00059 #include <libdirac_byteio/byteio.h>
00060 #include <vector>
00061 
00062 namespace dirac
00063 {
00065 
00069     class ContextLookupTable {
00070         public:
00071 
00073 
00077             ContextLookupTable();
00078 
00080             inline static unsigned int lookup(int weight);
00081         private:
00082             static unsigned int table[256];
00083     };
00084 
00085     class Context: private ContextLookupTable {
00086     public:
00087 
00089 
00092         inline Context();
00093 
00094         //Class is POD
00095         //Use built in copy constructor, assignment and destructor.
00096 
00098         //  The probability of a binary input/output symbol is estimated
00099         //  from past counts of 0 and 1 for symbols in the same context.
00100         //  Probability is estimated as:
00101         //      probability of 0 = count0/(count0+count1)
00102         //  Probability is re-calculated for every symbol.
00103         //  To avoid the division a lookup table is used.
00104         //  This is a fixed point implementation so probability is scaled to
00105         //  a range of 0 to 2**16.
00106         //  The value of (count0+count1) is known as "weight".
00107         //  The lookup table precalculates the values of:
00108         //      lookup(weight) = ((1<<16)+weight/2)/weight
00109         //  The probability calculation becomes:
00110         //      probability of = count0 * lookup(weight)
00111         inline unsigned int GetScaledProb0( ) const{ return m_prob0;}
00112 
00114         inline void Update( bool symbol );
00115 
00116     private:
00117 
00118         int m_count0;
00119         int m_count1;
00120         int m_prob0;
00121     };
00122     
00123         Context::Context():
00124         m_count0(1), m_count1(1), m_prob0( 0x8000 ) {}
00125 
00126 
00127     void Context::Update( bool symbol )
00128     {
00129         if ( !symbol )
00130             ++m_count0;
00131         else
00132             ++m_count1;
00133 
00134         if ( (m_count0+m_count1)%8==0)
00135         {
00136             if ( (m_count0+m_count1) == 256 )
00137             {
00138                 m_count0++;
00139                 m_count0 >>= 1;
00140                 m_count1++;
00141                 m_count1 >>= 1;
00142             }
00143             m_prob0 = m_count0*lookup( m_count0+m_count1 );
00144         }
00145             
00146 
00147     }
00148 
00149     unsigned int ContextLookupTable::lookup(int weight) {
00150         return table[weight];
00151     }
00152     
00153 
00154     class ArithCodecBase {
00155 
00156     public:
00157 
00159 
00165         ArithCodecBase(ByteIO* p_byteio, size_t number_of_contexts);
00166 
00168 
00171         virtual ~ArithCodecBase();
00172 
00173     protected:
00174 
00175         //core encode functions
00177 
00179         void InitEncoder();
00180 
00182         void EncodeSymbol(const bool symbol, const int context_num);
00183 
00184         void EncodeUInt(const unsigned int value, const int bin1, const int max_bin);
00185 
00186         void EncodeSInt(const int value, const int bin1, const int max_bin);
00187 
00189         void FlushEncoder();
00190 
00191         int ByteCount() const;     
00192 
00193         // core decode functions
00195 
00197         void InitDecoder(int num_bytes);                    
00198 
00200         bool DecodeSymbol( int context_num );
00201 
00202         unsigned int DecodeUInt(const int bin1, const int max_bin);
00203 
00204         int DecodeSInt(const int bin1, const int max_bin);
00205         
00207         std::vector<Context> m_context_list;
00208 
00209     private:
00210         
00212         ArithCodecBase(const ArithCodecBase & cpy);
00213 
00215         ArithCodecBase & operator = (const ArithCodecBase & rhs);
00216              
00217                      
00218         // Decode functions
00220 
00222         void ReadAllData(int num_bytes);
00223 
00225         inline bool InputBit();
00226 
00227         // Codec data
00229  
00230  unsigned int m_scount;
00231  
00233         unsigned int m_low_code;
00234         
00236         unsigned int m_range;
00237 
00239         ByteIO *m_byteio;
00240 
00241         // For encoder only
00242 
00244         int m_underflow;
00245 
00247         char* m_decode_data_ptr;
00248 
00250         char* m_data_ptr;
00251 
00253         int m_input_bits_left;
00254 
00256         unsigned int m_code;
00257 
00258     };
00259 
00260 
00261     inline bool ArithCodecBase::DecodeSymbol( int context_num )
00262     {
00263  
00264         // Determine the next symbol value by placing code within
00265         // the [low,high] interval.
00266 
00267         // Fetch the statistical context to be used
00268         Context& ctx  = m_context_list[context_num];
00269 
00270         // Decode as per updated specification
00271         const unsigned int count = m_code - m_low_code + 1; 
00272         const unsigned int range_x_prob = ( m_range* ctx.GetScaledProb0())>>16;
00273         bool symbol = ( count > range_x_prob );
00274 
00275         // Rescale the interval
00276         if( symbol )    //symbol is 1
00277         {
00278             m_low_code += range_x_prob;
00279             m_range -= range_x_prob;
00280         }
00281         else            //symbol is 0, so m_low_code unchanged
00282         {
00283             m_range = range_x_prob;
00284         }
00285 
00286         // Update the statistical context
00287         ctx.Update( symbol );
00288 
00289         while ( m_range<=0x4000 )
00290         {
00291             if( ( (m_low_code+m_range-1)^m_low_code)>=0x8000 )
00292             {
00293                 // Straddle condition
00294                 // We must have an underflow situation with
00295                 // low = 0x01... and high = 0x10...
00296                 // Flip 2nd bit prior to rescaling
00297                 m_code      ^= 0x4000;
00298                 m_low_code  ^= 0x4000;
00299             }
00300 
00301             // Double low and range, throw away top bit of low
00302             m_low_code  <<= 1;
00303             m_range <<= 1;
00304             m_low_code   &= 0xFFFF;
00305 
00306             // Shift in another bit of code
00307             m_code      <<= 1;
00308             m_code       += InputBit();
00309             m_code       &= 0xFFFF;
00310       
00311         }
00312 
00313         return symbol;
00314     }
00315 
00316     inline unsigned int ArithCodecBase::DecodeUInt(const int bin1, const int max_bin) {
00317         const int info_ctx = (max_bin+1);
00318         int bin = bin1;
00319         unsigned int value = 1;
00320         while (!DecodeSymbol(bin)) {
00321             value <<= 1;
00322             if (DecodeSymbol(info_ctx)) value+=1;
00323             if (bin<max_bin) bin+=1;
00324         }
00325         value -= 1;
00326         return value;
00327     }
00328 
00329     inline int ArithCodecBase::DecodeSInt(const int bin1, const int max_bin) {
00330         int value = 0;
00331         const int magnitude = DecodeUInt(bin1, max_bin);
00332         if (magnitude!=0) {
00333             if (DecodeSymbol(max_bin+2)) value=-magnitude;
00334             else value=magnitude;
00335         }
00336         return value;
00337     }
00338 
00339     inline void ArithCodecBase::EncodeSymbol(const bool symbol, const int context_num)
00340     {
00341 
00342         // Adjust high and low (rescale interval) based on the symbol we are encoding
00343 
00344         Context& ctx = m_context_list[context_num];
00345 
00346         const unsigned int range_x_prob = ( m_range* ctx.GetScaledProb0())>>16;
00347 
00348         if ( symbol )    //symbol is 1
00349         {
00350             m_low_code += range_x_prob;
00351             m_range -= range_x_prob;  
00352         }
00353         else             // symbol is 0, so m_low_code unchanged
00354         {
00355             m_range = range_x_prob;
00356         }
00357         
00358         // Update the statistical context
00359         ctx.Update( symbol );
00360 
00361         while ( m_range <= 0x4000 )
00362         { 
00363             if ( ( (m_low_code+m_range-1)^m_low_code)>=0x8000 )
00364             {    
00365                 // Straddle condition
00366                 // We must have an underflow situation with
00367                 // low = 0x01... and high = 0x10...
00368 
00369                 m_low_code  ^= 0x4000;
00370                 m_underflow++;
00371 
00372             }
00373             else
00374             {
00375                 // Bits agree - output them
00376                 m_byteio->OutputBit( m_low_code & 0x8000);
00377                 for (; m_underflow > 0; m_underflow-- )
00378                     m_byteio->OutputBit(~m_low_code & 0x8000);
00379             }
00380 
00381             // Double low value and range
00382             m_low_code  <<= 1;
00383             m_range <<= 1;
00384             
00385             // keep low to 16 bits - throw out top bit
00386             m_low_code   &= 0xFFFF;
00387 
00388          }
00389        
00390     }
00391 
00392     inline void ArithCodecBase::EncodeUInt(const unsigned int the_int,
00393                                            const int bin1, const int max_bin) {
00394         const int value = (the_int+1);
00395         const int info_ctx = (max_bin+1);
00396         int bin = bin1;
00397         int top_bit = 1;
00398         {
00399             int max_value = 1;
00400             while (value>max_value) {
00401                 top_bit <<= 1;
00402                 max_value <<= 1;
00403                 max_value += 1;
00404             }
00405         }
00406         bool stop = (top_bit==1);
00407         EncodeSymbol(stop, bin);
00408         while (!stop) {
00409             top_bit >>= 1;
00410             EncodeSymbol( (value&top_bit), info_ctx);
00411             if ( bin < max_bin) bin+=1;
00412             stop = (top_bit==1);
00413             EncodeSymbol(stop, bin);
00414         }
00415     }
00416 
00417     inline void ArithCodecBase::EncodeSInt(const int value,
00418                                            const int bin1, const int max_bin) {
00419         EncodeUInt(std::abs(value), bin1, max_bin);
00420         if (value != 0) {
00421             EncodeSymbol( (value < 0), max_bin+2 );
00422         }
00423     }
00424 
00425 
00427 
00433     template<class T> //T is container/array type
00434     class ArithCodec
00435         : public ArithCodecBase
00436     {
00437     public:
00438 
00440 
00446         ArithCodec(ByteIO* p_byteio, size_t number_of_contexts);
00447 
00448       
00450 
00453         virtual ~ArithCodec() {}
00454 
00456 
00464         int Compress(T & in_data);
00465     
00467 
00475         void Decompress(T & out_data, const int num_bytes);
00476 
00477     protected:
00478 
00479         //virtual encode-only functions
00481 
00483         virtual void DoWorkCode(T & in_data) = 0; 
00484 
00487         virtual void DoWorkDecode(T & out_data)=0;
00488    };
00489 
00490     //Implementation - core functions
00492 
00493     template<class T>
00494     ArithCodec<T>::ArithCodec(ByteIO* p_byteio, size_t number_of_contexts):
00495         ArithCodecBase(p_byteio, number_of_contexts) {}
00496 
00497 
00498 
00499     template<class T>
00500     int ArithCodec<T>::Compress(T &in_data)
00501     {
00502         InitEncoder();                
00503         DoWorkCode(in_data);
00504         FlushEncoder();
00505         return ByteCount();
00506     }
00507 
00508     template<class T>
00509     void ArithCodec<T>::Decompress( T &out_data, const int num_bytes )
00510     {
00511         InitDecoder(num_bytes);
00512         DoWorkDecode( out_data );
00513     }
00514 
00515    inline bool ArithCodecBase::InputBit()
00516     {
00517         if (m_input_bits_left == 0)
00518         {
00519             m_data_ptr++;
00520             m_input_bits_left = 8;
00521         }
00522         m_input_bits_left--;
00523         // MSB to LSB
00524         return bool( ( (*m_data_ptr) >> m_input_bits_left ) & 1 );
00525     }
00526 
00527 }// namespace dirac
00528 #endif
00529 

© 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.