# 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.38 2007/04/11 14:36:45 tjdwave Exp $ $Name: Dirac_0_7_0 $
    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 {
    00064
    00065     class Context {
    00066     public:
    00067
    00069
    00072         inline Context();
    00073
    00074         //Class is POD
    00075         //Use built in copy constructor, assignment and destructor.
    00076
    00078
    00079         inline unsigned int GetScaledProb0( ) const{ return m_prob0;}
    00080
    00082         inline void Update( bool symbol ) {
    00083           if (symbol) m_prob0 -= lut[m_prob0>>8];
    00084           else m_prob0 += lut[255-(m_prob0>>8)];
    00085         }
    00086
    00087     private:
    00088
    00089         int m_prob0;
    00090         static const unsigned int lut[256]; //Probability update table
    00091     };
    00092
    00093     Context::Context(): m_prob0( 0x8000 ) {}
    00094
    00095 /*
    00096     void Context::Update( bool symbol )
    00097     {
    00098 //        if ( !symbol )
    00099 //            ++m_count0;
    00100 //        else
    00101 //            ++m_count1;
    00102 //
    00103 //        if ( (m_count0+m_count1)%8==0)
    00104 //        {
    00105 //            if ( (m_count0+m_count1) == 256 )
    00106 //            {
    00107 //                m_count0++;
    00108 //                m_count0 >>= 1;
    00109 //                m_count1++;
    00110 //                m_count1 >>= 1;
    00111 //            }
    00112 //            m_prob0 = m_count0*lookup( m_count0+m_count1 );
    00113 //        }
    00114
    00115         if (symbol) m_prob0 -= lut[m_prob0>>8];
    00116         else m_prob0 += lut[255-(m_prob0>>8)];
    00117
    00118     }
    00119 */
    00120
    00121     class ArithCodecBase {
    00122
    00123     public:
    00124
    00126
    00132         ArithCodecBase(ByteIO* p_byteio, size_t number_of_contexts);
    00133
    00135
    00138         virtual ~ArithCodecBase();
    00139
    00140     protected:
    00141
    00142         //core encode functions
    00144
    00146         void InitEncoder();
    00147
    00149         void EncodeSymbol(const bool symbol, const int context_num);
    00150
    00151         void EncodeUInt(const unsigned int value, const int bin1, const int max_bin);
    00152
    00153         void EncodeSInt(const int value, const int bin1, const int max_bin);
    00154
    00156         void FlushEncoder();
    00157
    00158         int ByteCount() const;
    00159
    00160         // core decode functions
    00162
    00164         void InitDecoder(int num_bytes);
    00165
    00167         bool DecodeSymbol( int context_num );
    00168
    00169         unsigned int DecodeUInt(const int bin1, const int max_bin);
    00170
    00171         int DecodeSInt(const int bin1, const int max_bin);
    00172
    00174         std::vector<Context> m_context_list;
    00175
    00176     private:
    00177
    00179         ArithCodecBase(const ArithCodecBase & cpy);
    00180
    00182         ArithCodecBase & operator = (const ArithCodecBase & rhs);
    00183
    00184
    00185         // Decode functions
    00187
    00189         void ReadAllData(int num_bytes);
    00190
    00192         inline bool InputBit();
    00193
    00194         // Codec data
    00196
    00197  unsigned int m_scount;
    00198
    00200         unsigned int m_low_code;
    00201
    00203         unsigned int m_range;
    00204
    00206         ByteIO *m_byteio;
    00207
    00208         // For encoder only
    00209
    00211         int m_underflow;
    00212
    00214         char* m_decode_data_ptr;
    00215
    00217         char* m_data_ptr;
    00218
    00220         int m_input_bits_left;
    00221
    00223         unsigned int m_code;
    00224
    00225     };
    00226
    00227
    00228     inline bool ArithCodecBase::DecodeSymbol( int context_num )
    00229     {
    00230
    00231         // Determine the next symbol value by placing code within
    00232         // the [low,high] interval.
    00233
    00234         // Fetch the statistical context to be used
    00235         Context& ctx  = m_context_list[context_num];
    00236
    00237         // Decode as per updated specification
    00238         const unsigned int count = m_code - m_low_code ;
    00239         const unsigned int range_x_prob = ( m_range* ctx.GetScaledProb0())>>16;
    00240         const bool symbol = ( count >= range_x_prob );
    00241
    00242         // Rescale the interval
    00243         if( symbol )    //symbol is 1
    00244         {
    00245             m_low_code += range_x_prob;
    00246             m_range -= range_x_prob;
    00247         }
    00248         else            //symbol is 0, so m_low_code unchanged
    00249         {
    00250             m_range = range_x_prob;
    00251         }
    00252
    00253         // Update the statistical context
    00254         ctx.Update( symbol );
    00255
    00256         while ( m_range<=0x4000 )
    00257         {
    00258             if( ( (m_low_code+m_range-1)^m_low_code)>=0x8000 )
    00259             {
    00260                 // Straddle condition
    00261                 // We must have an underflow situation with
    00262                 // low = 0x01... and high = 0x10...
    00263                 // Flip 2nd bit prior to rescaling
    00264                 m_code      ^= 0x4000;
    00265                 m_low_code  ^= 0x4000;
    00266             }
    00267
    00268             // Double low and range, throw away top bit of low
    00269             m_low_code  <<= 1;
    00270             m_range <<= 1;
    00271             m_low_code   &= 0xFFFF;
    00272
    00273             // Shift in another bit of code
    00274             m_code      <<= 1;
    00275             m_code       += InputBit();
    00276             m_code       &= 0xFFFF;
    00277
    00278         }
    00279
    00280         return symbol;
    00281     }
    00282
    00283     inline unsigned int ArithCodecBase::DecodeUInt(const int bin1, const int max_bin) {
    00284         const int info_ctx = (max_bin+1);
    00285         int bin = bin1;
    00286         unsigned int value = 1;
    00287         while (!DecodeSymbol(bin)) {
    00288             value <<= 1;
    00289             if (DecodeSymbol(info_ctx)) value+=1;
    00290             if (bin<max_bin) bin+=1;
    00291         }
    00292         value -= 1;
    00293         return value;
    00294     }
    00295
    00296     inline int ArithCodecBase::DecodeSInt(const int bin1, const int max_bin) {
    00297         int value = 0;
    00298         const int magnitude = DecodeUInt(bin1, max_bin);
    00299         if (magnitude!=0) {
    00300             if (DecodeSymbol(max_bin+2)) value=-magnitude;
    00301             else value=magnitude;
    00302         }
    00303         return value;
    00304     }
    00305
    00306     inline void ArithCodecBase::EncodeSymbol(const bool symbol, const int context_num)
    00307     {
    00308
    00309         // Adjust high and low (rescale interval) based on the symbol we are encoding
    00310
    00311         Context& ctx = m_context_list[context_num];
    00312
    00313         const unsigned int range_x_prob = ( m_range* ctx.GetScaledProb0())>>16;
    00314
    00315         if ( symbol )    //symbol is 1
    00316         {
    00317             m_low_code += range_x_prob;
    00318             m_range -= range_x_prob;
    00319         }
    00320         else             // symbol is 0, so m_low_code unchanged
    00321         {
    00322             m_range = range_x_prob;
    00323         }
    00324
    00325         // Update the statistical context
    00326         ctx.Update( symbol );
    00327
    00328         while ( m_range <= 0x4000 )
    00329         {
    00330             if ( ( (m_low_code+m_range-1)^m_low_code)>=0x8000 )
    00331             {
    00332                 // Straddle condition
    00333                 // We must have an underflow situation with
    00334                 // low = 0x01... and high = 0x10...
    00335
    00336                 m_low_code  ^= 0x4000;
    00337                 m_underflow++;
    00338
    00339             }
    00340             else
    00341             {
    00342                 // Bits agree - output them
    00343                 m_byteio->OutputBit( m_low_code & 0x8000);
    00344                 for (; m_underflow > 0; m_underflow-- )
    00345                     m_byteio->OutputBit(~m_low_code & 0x8000);
    00346             }
    00347
    00348             // Double low value and range
    00349             m_low_code  <<= 1;
    00350             m_range <<= 1;
    00351
    00352             // keep low to 16 bits - throw out top bit
    00353             m_low_code   &= 0xFFFF;
    00354
    00355          }
    00356
    00357     }
    00358
    00359     inline void ArithCodecBase::EncodeUInt(const unsigned int the_int,
    00360                                            const int bin1, const int max_bin) {
    00361         const int value = (the_int+1);
    00362         const int info_ctx = (max_bin+1);
    00363         int bin = bin1;
    00364         int top_bit = 1;
    00365         {
    00366             int max_value = 1;
    00367             while (value>max_value) {
    00368                 top_bit <<= 1;
    00369                 max_value <<= 1;
    00370                 max_value += 1;
    00371             }
    00372         }
    00373         bool stop = (top_bit==1);
    00374         EncodeSymbol(stop, bin);
    00375         while (!stop) {
    00376             top_bit >>= 1;
    00377             EncodeSymbol( (value&top_bit), info_ctx);
    00378             if ( bin < max_bin) bin+=1;
    00379             stop = (top_bit==1);
    00380             EncodeSymbol(stop, bin);
    00381         }
    00382     }
    00383
    00384     inline void ArithCodecBase::EncodeSInt(const int value,
    00385                                            const int bin1, const int max_bin) {
    00386         EncodeUInt(std::abs(value), bin1, max_bin);
    00387         if (value != 0) {
    00388             EncodeSymbol( (value < 0), max_bin+2 );
    00389         }
    00390     }
    00391
    00392
    00394
    00400     template<class T> //T is container/array type
    00401     class ArithCodec
    00402         : public ArithCodecBase
    00403     {
    00404     public:
    00405
    00407
    00413         ArithCodec(ByteIO* p_byteio, size_t number_of_contexts);
    00414
    00415
    00417
    00420         virtual ~ArithCodec() {}
    00421
    00423
    00431         int Compress(T & in_data);
    00432
    00434
    00442         void Decompress(T & out_data, const int num_bytes);
    00443
    00444     protected:
    00445
    00446         //virtual encode-only functions
    00448
    00450         virtual void DoWorkCode(T & in_data) = 0;
    00451
    00454         virtual void DoWorkDecode(T & out_data)=0;
    00455    };
    00456
    00457     //Implementation - core functions
    00459
    00460     template<class T>
    00461     ArithCodec<T>::ArithCodec(ByteIO* p_byteio, size_t number_of_contexts):
    00462         ArithCodecBase(p_byteio, number_of_contexts) {}
    00463
    00464
    00465
    00466     template<class T>
    00467     int ArithCodec<T>::Compress(T &in_data)
    00468     {
    00469         InitEncoder();
    00470         DoWorkCode(in_data);
    00471         FlushEncoder();
    00472         return ByteCount();
    00473     }
    00474
    00475     template<class T>
    00476     void ArithCodec<T>::Decompress( T &out_data, const int num_bytes )
    00477     {
    00478         InitDecoder(num_bytes);
    00479         DoWorkDecode( out_data );
    00480     }
    00481
    00482    inline bool ArithCodecBase::InputBit()
    00483     {
    00484         if (m_input_bits_left == 0)
    00485         {
    00486             m_data_ptr++;
    00487             m_input_bits_left = 8;
    00488         }
    00489         m_input_bits_left--;
    00490         // MSB to LSB
    00491         return bool( ( (*m_data_ptr) >> m_input_bits_left ) & 1 );
    00492     }
    00493
    00494 }// namespace dirac
    00495 #endif
    00496

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