- Main Page
- Namespaces
- Classes
- Files
- Directories

- File List
- File Members

# arith_codec.h

    00001 /* ***** BEGIN LICENSE BLOCK *****
    00002 *
    00003 * $Id: arith_codec.h,v 1.2 2005/01/30 05:11:39 gabest 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 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
    00124         void Decompress(T & out_data, int num_bits);
    00125
    00126     protected:
    00127
    00128         // use explicity type sizes for portability
    00129         typedef uint16_t code_t;
    00130         typedef uint32_t calc_t;
    00131
    00132         // NOTE: These macros imply an unsigned 16-bit operand
    00133         static const code_t CODE_MAX     = 0xffff;
    00134         static const code_t CODE_MSB     = ((0xffff + 1) >> 1);
    00135         static const code_t CODE_2ND_MSB = ((0xffff + 1) >> 2);
    00136
    00138
    00144         class Triple
    00145         {
    00146         public:
    00148             Triple()
    00149               : m_start(0),
    00150                 m_stop(0),
    00151                 m_weight(0) {}
    00152
    00153             // value constructor
    00154             Triple(code_t start, code_t stop, code_t weight)
    00155             {
    00156                 m_start  = start;
    00157                 m_stop   = stop;
    00158                 m_weight = weight;
    00159             }
    00160
    00162             Triple(const Triple& rhs)
    00163               : m_start(rhs.m_start),
    00164                 m_stop(rhs.m_stop),
    00165                 m_weight(rhs.m_weight) { }
    00166
    00168             Triple & operator = (const Triple& rhs)
    00169             {
    00170                 m_start  = rhs.m_start;
    00171                 m_stop   = rhs.m_stop;
    00172                 m_weight = rhs.m_weight;
    00173                 return *this;
    00174             }
    00175
    00176             // get the start value
    00177             code_t Start() const { return m_start; }
    00178
    00179             // get the stop value
    00180             code_t Stop() const  { return m_stop; }
    00181
    00182             // get the weight value
    00183             code_t Weight() const { return m_weight; }
    00184
    00185         private:
    00187             code_t m_start;
    00188
    00190             code_t m_stop;
    00191
    00193             code_t m_weight;
    00194         };
    00195
    00197
    00202         class Context
    00203         {
    00204         public:
    00206
    00209             Context()
    00210             {
    00211                 SetCounts(1,1);
    00212             }
    00213
    00215
    00218             Context(int cnt0,int cnt1)
    00219             {
    00220                 SetCounts(cnt0,cnt1);
    00221             }
    00222
    00224             Context(const Context & cpy)
    00225               : count0(cpy.count0),
    00226                 count1(cpy.count1),
    00227                 trip0(cpy.trip0),
    00228                 trip1(cpy.trip1)
    00229             {}
    00230
    00232             Context & operator=(const Context& rhs)
    00233             {
    00234                 count0 = rhs.count0;
    00235                 count1 = rhs.count1;
    00236                 trip0  = rhs.trip0;
    00237                 trip1  = rhs.trip1;
    00238                 return *this;
    00239             }
    00240
    00242             ~Context() {}
    00243
    00245
    00248             void SetCounts(int cnt0, int cnt1)
    00249             {
    00250                 count0 = cnt0;
    00251                 count1 = cnt1;
    00252                 SetTriples();
    00253             }
    00254
    00256             code_t GetCount0() const { return count0; }
    00257
    00259             code_t GetCount1() const { return count1; }
    00260
    00262
    00268             void IncrCount(bool symbol, int amnt)
    00269             {
    00270                 if ( symbol )
    00271                     count1 += amnt;
    00272                 else
    00273                     count0 += amnt;
    00274
    00275                 SetTriples();
    00276             }
    00277
    00279             void HalveCounts()
    00280             {
    00281                 count0 >>= 1;
    00282                 count0++;
    00283                 count1 >>= 1;
    00284                 count1++;
    00285
    00286                 SetTriples();
    00287             }
    00288
    00290             code_t Weight() const { return trip0.Weight(); }
    00291
    00293             const Triple & GetTriple( const bool symbol ) const { return (symbol ? trip1 : trip0); }
    00294
    00296
    00302             bool GetSymbol(const code_t num, Triple & trip_val) const
    00303             {
    00304                 if (num < trip0.Stop())
    00305                 {
    00306                     trip_val = trip0;
    00307                     return false; //ie zero
    00308                 }
    00309                 else
    00310                 {
    00311                     trip_val = trip1;
    00312                     return true; //ie 1
    00313                 }
    00314             }
    00315
    00316         private:
    00317             code_t count0;
    00318             code_t count1;
    00319
    00320             Triple trip0;
    00321             Triple trip1;
    00322
    00323             void SetTriples()
    00324             {
    00325                 //updates triples given counts
    00326                 trip0 = Triple(0, trip0.Start() + count0, count0 + count1);
    00327                 trip1 = Triple(trip0.Stop(), trip1.Start() + count1, trip0.Weight());
    00328             }
    00329         };
    00330
    00331     protected:
    00332
    00334         //std::vector<Context> & ContextList() { return m_context_list; }
    00335
    00336         //virtual codec functions (to be overridden)
    00338
    00340         virtual void InitContexts()=0;
    00341
    00343         virtual void Update( const bool symbol , const int context_num )=0;
    00344
    00346         virtual void Resize(const int context_num)=0;
    00347
    00349         virtual void ResetAll()=0;
    00350
    00352         virtual int ChooseContext(const T &data, const int bin_number) const =0;
    00353
    00355         virtual int ChooseContext(const T &data) const=0;
    00356
    00357         //virtual encode-only functions
    00359
    00361         virtual void DoWorkCode(T & in_data) = 0;
    00362
    00363         //core encode-only functions
    00365
    00367         void InitEncoder();
    00368
    00370         void EncodeTriple(const Triple & c);
    00371
    00373         void EncodeSymbol(const bool symbol, const int context_num);
    00374
    00376         void FlushEncoder();
    00377
    00379         void FlushDecoder();
    00380
    00382         virtual void DoWorkDecode(T & out_data, int num_bits)=0;
    00383
    00384         // core decode-only functions
    00386
    00388         void InitDecoder();
    00389
    00391         void RemFromStream(const Triple & c);
    00392
    00394         void SetCurrentCount(const int context_num);
    00395
    00397         void DecodeSymbol(bool& symbol, int context_num);
    00398
    00399     private:
    00401         int m_bit_count;
    00402
    00404         int m_max_count;
    00405
    00407         int m_underflow;
    00408
    00410         code_t m_code;
    00411
    00413         code_t m_count;
    00414
    00416         code_t m_low_code;
    00417
    00419         code_t m_high_code;
    00420
    00421         // Parameters for controlling coding/decoding
    00422         // codec_params_type cparams;
    00423
    00425         BitInputManager* m_bit_input;
    00426
    00428         BasicOutputManager* m_bit_output;
    00429
    00430         //private, bodyless copy constructor: class should not be copied
    00431         ArithCodec(const ArithCodec & cpy);
    00432
    00433         //private, bodyless copy operator=: class should not be assigned
    00434         ArithCodec & operator = (const ArithCodec & rhs);
    00435
    00436
    00437     protected:
    00438
    00440         std::vector<Context> m_context_list;
    00441     };
    00442
    00443     //Implementation - core functions
    00445
    00446     template<class T>
    00447     ArithCodec<T>::ArithCodec(BitInputManager* bits_in, size_t number_of_contexts)
    00448       : m_bit_count(0),
    00449         m_bit_input(bits_in),
    00450         m_context_list(number_of_contexts)
    00451     {
    00452         // nothing needed here
    00453     }
    00454
    00456     template<class T>
    00457     ArithCodec<T>::ArithCodec(BasicOutputManager* bits_out, size_t number_of_contexts)
    00458       : m_bit_count(0),
    00459         m_bit_output(bits_out),
    00460         m_context_list(number_of_contexts)
    00461     {
    00462         // nothing needed here
    00463     }
    00464
    00465     template<class T>
    00466     ArithCodec<T>::~ArithCodec()
    00467     {
    00468         // nothing needed here
    00469     }
    00470
    00471     template<class T>
    00472     int ArithCodec<T>::Compress(T &in_data)
    00473     {
    00474         InitEncoder();
    00475         DoWorkCode(in_data);
    00476         FlushEncoder();
    00477         return m_bit_count;
    00478     }
    00479
    00480     template<class T>
    00481     void ArithCodec<T>::Decompress(T &out_data, int num_bits)
    00482     {
    00483         m_max_count=num_bits;
    00484         InitDecoder();
    00485         DoWorkDecode(out_data,num_bits);
    00486         FlushDecoder();
    00487         m_bit_input->FlushInput();
    00488     }
    00489
    00490     template<class T>
    00491     void ArithCodec<T>::InitEncoder()
    00492     {
    00493         // Set the m_code word stuff
    00494         m_low_code  = 0;
    00495         m_high_code = CODE_MAX;
    00496         m_underflow = 0;
    00497     }
    00498
    00499     template<class T>
    00500     void ArithCodec<T>::EncodeTriple(const Triple &c)
    00501     {
    00502         // Rescale m_high_code and m_low_code for the new symbol
    00503         calc_t range( static_cast<calc_t>(m_high_code - m_low_code) + 1 );
    00504
    00505         //formulae given we know we're binary coding
    00506         if (!c.Start()) // c.Start()=0, so symbol is 0, so m_low_code unchanged
    00507             m_high_code = m_low_code + static_cast<code_t>(( range * c.Stop() ) / c.Weight() - 1 );
    00508         else //symbol is 1, so m_high_code unchanged
    00509             m_low_code += static_cast<code_t>(( range * c.Start() ) / c.Weight() );
    00510
    00511         do
    00512         {
    00513             if (( m_high_code & CODE_MSB ) == ( m_low_code & CODE_MSB ))
    00514             {
    00515                 m_bit_output->OutputBit( m_high_code & CODE_MSB, m_bit_count);
    00516                 while ( m_underflow > 0 )
    00517                 {
    00518                     m_bit_output->OutputBit(~m_high_code & CODE_MSB, m_bit_count);
    00519                     m_underflow--;
    00520                 }
    00521             }
    00522
    00523             else if ( ( m_low_code & CODE_2ND_MSB ) && !( m_high_code & CODE_2ND_MSB ))
    00524             {
    00525                 m_underflow += 1;
    00526                 m_low_code  &= (CODE_2ND_MSB) - 1;
    00527                 m_high_code |= CODE_2ND_MSB;
    00528             }
    00529             else return ;
    00530
    00531             m_low_code  <<= 1;
    00532             m_high_code <<= 1;
    00533             m_high_code  |= 1;
    00534         }
    00535         while(true);
    00536     }
    00537
    00538     template<class T>
    00539     inline void ArithCodec<T>::EncodeSymbol(const bool symbol, const int context_num)
    00540     {
    00541         EncodeTriple(m_context_list[context_num].GetTriple(symbol));
    00542         Update( symbol , context_num );
    00543     }
    00544
    00545     template<class T>
    00546     void ArithCodec<T>::FlushEncoder()
    00547     {
    00548         // Flushes the output
    00549         m_bit_output->OutputBit(m_low_code & CODE_2ND_MSB,m_bit_count);
    00550         m_underflow++;
    00551
    00552         while ( m_underflow-- > 0 )
    00553             m_bit_output->OutputBit(~m_low_code & CODE_2ND_MSB, m_bit_count);
    00554     }
    00555
    00556     template<class T>
    00557     void ArithCodec<T>::InitDecoder()
    00558     {
    00559         //Read in a full word of data
    00560            code_t i;
    00561         m_code = 0;
    00562
    00563         for ( i = 0; i < (8 * sizeof(code_t)); i++ )
    00564         {
    00565             m_code <<= 1;
    00566
    00567             if (m_bit_input->InputBit(m_bit_count,m_max_count))
    00568                 m_code++;
    00569         }
    00570
    00571         m_low_code  = 0;
    00572         m_high_code = CODE_MAX;
    00573         m_underflow = 0;
    00574     }
    00575
    00576     template<class T>
    00577     void ArithCodec<T>::RemFromStream( const Triple &c )
    00578     {
    00579
    00580         calc_t range( static_cast<calc_t>( m_high_code - m_low_code ) + 1 );
    00581
    00582         if(!c.Start())//c.Start()=0, so symbol is 0, so m_low_code unchanged
    00583             m_high_code = m_low_code + static_cast<code_t>(( range * c.Stop() ) / c.Weight() - 1 );
    00584
    00585         else//symbol is 1, so m_high_code unchanged
    00586             m_low_code += static_cast<code_t>(( range * c.Start() ) / c.Weight() );
    00587
    00588         do
    00589         {
    00590             if ( ( m_high_code & CODE_MSB ) == ( m_low_code & CODE_MSB ) )
    00591             {
    00592                 // Do nothing
    00593             }
    00594             else if ((m_low_code & CODE_2ND_MSB) == CODE_2ND_MSB  && (m_high_code & CODE_2ND_MSB) == 0 )
    00595             {
    00596                 m_code      ^= CODE_2ND_MSB;
    00597                 m_low_code  &= (CODE_2ND_MSB) - 1;
    00598                 m_high_code |= CODE_2ND_MSB;
    00599             }
    00600             else return;
    00601
    00602             m_low_code  <<= 1;
    00603             m_high_code <<= 1;
    00604             m_high_code  |= 1;
    00605             m_code      <<= 1;
    00606
    00607             if ( m_bit_input->InputBit( m_bit_count , m_max_count ) )
    00608                 m_code++;
    00609
    00610         } while (1);
    00611
    00612     }
    00613
    00614     template<class T>
    00615     void ArithCodec<T>::SetCurrentCount(const int context_num)
    00616     {
    00617         calc_t range;
    00618         range = static_cast<calc_t>( m_high_code - m_low_code ) + 1;
    00619         m_count = static_cast<code_t>(
    00620                                       ( ( static_cast<calc_t>( m_code - m_low_code ) + 1 ) * m_context_list[context_num].Weight() - 1 )
    00621                                       / range );
    00622     }
    00623
    00624     template<class T>
    00625     void ArithCodec<T>::DecodeSymbol(bool& symbol, const int context_num)
    00626     {
    00627         Triple limits;
    00628         SetCurrentCount( context_num );
    00629         symbol = m_context_list[context_num].GetSymbol( m_count , limits );
    00630         RemFromStream( limits );
    00631         Update(  symbol , context_num );
    00632     }
    00633
    00634     template<class T>
    00635     void ArithCodec<T>::FlushDecoder()
    00636     {
    00637         // Flushes the input
    00638         while(m_bit_count < m_max_count)
    00639             m_bit_input->InputBit( m_bit_count , m_max_count );
    00640     }
    00641
    00642 } //namespace dirac
    00643 #endif