Created by the British Broadcasting Corporation.
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.