Created by the British Broadcasting Corporation.
00001 /* ***** BEGIN LICENSE BLOCK ***** 00002 * 00003 * $Id: arith_codec.h,v 1.15 2005/04/13 15:06:58 asuraparaju Exp $ $Name: Dirac_0_5_2 $ 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 00140 class ProbInterval 00141 { 00142 public: 00144 ProbInterval() 00145 : m_start(0), 00146 m_stop(1024) 00147 {} 00148 00150 ProbInterval( calc_t start , calc_t stop) 00151 { 00152 m_start = start; 00153 m_stop = stop; 00154 } 00155 00157 ProbInterval(const ProbInterval& rhs) 00158 : m_start(rhs.m_start), 00159 m_stop(rhs.m_stop){ } 00160 00162 ProbInterval & operator = (const ProbInterval& rhs) 00163 { 00164 m_start = rhs.m_start; 00165 m_stop = rhs.m_stop; 00166 return *this; 00167 } 00168 00170 calc_t Start() const { return m_start; } 00171 00173 calc_t Stop() const { return m_stop; } 00174 00176 void SetValues(const calc_t start , const calc_t stop) 00177 { 00178 m_start = start; 00179 m_stop = stop; 00180 } 00181 00182 private: 00184 calc_t m_start; 00185 00187 calc_t m_stop; 00188 00189 }; 00190 00192 00197 class Context 00198 { 00199 public: 00201 00204 Context() 00205 { 00206 SetCounts( 1 , 1 ); 00207 } 00208 00210 00213 Context(int cnt0,int cnt1) 00214 { 00215 SetCounts( cnt0 , cnt1 ); 00216 } 00217 00219 Context(const Context & cpy) 00220 : m_num0( cpy.m_num0 ), 00221 m_num1( cpy.m_num1 ), 00222 m_weight( cpy.m_weight ), 00223 m_r0( cpy.m_r0 ), 00224 m_r1( cpy.m_r1 ) 00225 {} 00226 00228 Context & operator=(const Context& rhs) 00229 { 00230 m_num0 = rhs.m_num0; 00231 m_num1 = rhs.m_num1; 00232 m_weight = rhs.m_weight; 00233 m_r0 = rhs.m_r0; 00234 m_r1 = rhs.m_r1; 00235 return *this; 00236 } 00237 00239 ~Context() {} 00240 00242 00245 void SetCounts(const int cnt0, const int cnt1) 00246 { 00247 m_num0 = cnt0; 00248 m_num1 = cnt1; 00249 m_weight = cnt0 + cnt1; 00250 SetRanges(); 00251 } 00252 00254 calc_t GetCount0() const { return m_num0; } 00255 00257 calc_t GetCount1() const { return m_num1; } 00258 00260 calc_t Weight() const { return m_weight; } 00261 00263 00267 inline void IncrCount( const bool symbol ) 00268 { 00269 if ( symbol ) 00270 m_num1++; 00271 else 00272 m_num0++; 00273 00274 m_weight++; 00275 00276 if ( m_weight & 1 ) 00277 SetRanges(); 00278 } 00279 00281 inline void HalveCounts() 00282 { 00283 m_num0 >>= 1; 00284 m_num0++; 00285 m_num1 >>= 1; 00286 m_num1++; 00287 00288 m_weight = m_num0 + m_num1; 00289 00290 SetRanges(); 00291 } 00292 00294 const ProbInterval & GetProbInterval( const bool symbol ) const { return (symbol ? m_r1 : m_r0); } 00295 00297 00300 bool GetSymbol(const calc_t num, const calc_t factor , ProbInterval & prob_val) const 00301 { 00302 if (num < m_r0.Stop()*factor) 00303 { 00304 prob_val = m_r0; 00305 return false; //ie zero 00306 } 00307 else 00308 { 00309 prob_val = m_r1; 00310 return true; //ie 1 00311 } 00312 } 00313 00314 inline void SetRanges() 00315 { 00316 // Updates the probability ranges 00317 00318 const calc_t end0( ( m_num0 * 1024 ) / m_weight ); 00319 00320 m_r0.SetValues( 0 , end0 ); 00321 m_r1.SetValues( end0 , 1024 ); 00322 00323 } 00324 00325 private: 00326 calc_t m_num0; 00327 calc_t m_num1; 00328 00329 calc_t m_weight; 00330 00331 ProbInterval m_r0; 00332 ProbInterval m_r1; 00333 00334 00335 }; 00336 00337 protected: 00338 00339 //virtual codec functions (to be overridden) 00341 00343 virtual void InitContexts()=0; 00344 00346 void Update( const bool symbol , const int context_num ); 00347 00349 virtual void ResetAll()=0; 00350 00351 //virtual encode-only functions 00353 00355 virtual void DoWorkCode(T & in_data) = 0; 00356 00357 //core encode-only functions 00359 00361 void InitEncoder(); 00362 00364 void EncodeProbInterval(const ProbInterval & prob_interval , const calc_t range ); 00365 00367 void EncodeSymbol(const bool symbol, const int context_num); 00368 00370 void FlushEncoder(); 00371 00374 virtual void DoWorkDecode(T & out_data)=0; 00375 00376 // core decode-only functions 00378 00380 void InitDecoder(); 00381 00383 void RemFromStream(const ProbInterval & prob_interval , const calc_t range); 00384 00386 bool DecodeSymbol( const int context_num ); 00387 00388 private: 00390 int m_bit_count; 00391 00393 int m_max_count; 00394 00396 int m_underflow; 00397 00399 code_t m_code; 00400 00402 code_t m_low_code; 00403 00405 code_t m_high_code; 00406 00407 // Parameters for controlling coding/decoding 00408 // codec_params_type cparams; 00409 00411 BitInputManager* m_bit_input; 00412 00414 BasicOutputManager* m_bit_output; 00415 00417 ArithCodec(const ArithCodec & cpy); 00418 00420 ArithCodec & operator = (const ArithCodec & rhs); 00421 00422 // For decoder only (could extend to the encoder later) 00423 00425 char* m_decode_data_ptr; 00426 00428 char* m_data_ptr; 00429 00431 int m_input_bits_left; 00432 00433 private: 00434 00436 void ReadAllData(); 00437 00439 inline bool InputBit(); 00440 00441 00442 00443 00444 protected: 00445 00447 std::vector<Context> m_context_list; 00448 }; 00449 00450 //Implementation - core functions 00452 00453 template<class T> 00454 ArithCodec<T>::ArithCodec(BitInputManager* bits_in, size_t number_of_contexts) 00455 : m_bit_count( 0 ), 00456 m_bit_input( bits_in ), 00457 m_decode_data_ptr( 0 ), 00458 m_context_list( number_of_contexts ) 00459 { 00460 // nothing needed here 00461 } 00462 00464 template<class T> 00465 ArithCodec<T>::ArithCodec(BasicOutputManager* bits_out, size_t number_of_contexts) 00466 : m_bit_count( 0 ), 00467 m_bit_output( bits_out ), 00468 m_decode_data_ptr( 0 ), 00469 m_context_list( number_of_contexts ) 00470 { 00471 // nothing needed here 00472 } 00473 00474 template<class T> 00475 ArithCodec<T>::~ArithCodec() 00476 { 00477 if ( m_decode_data_ptr ) 00478 delete[] m_decode_data_ptr; 00479 } 00480 00481 template<class T> 00482 int ArithCodec<T>::Compress(T &in_data) 00483 { 00484 InitEncoder(); 00485 DoWorkCode(in_data); 00486 FlushEncoder(); 00487 00488 int byte_count( m_bit_count/8); 00489 if ( (byte_count*8)<m_bit_count ) 00490 byte_count++; 00491 00492 return byte_count; 00493 } 00494 00495 template<class T> 00496 void ArithCodec<T>::Decompress( T &out_data, const int num_bytes ) 00497 { 00498 m_max_count = num_bytes; 00499 InitDecoder(); 00500 DoWorkDecode( out_data ); 00501 } 00502 00503 template<class T> 00504 void ArithCodec<T>::InitEncoder() 00505 { 00506 // Set the m_code word stuff 00507 m_low_code = 0; 00508 m_high_code = CODE_MAX; 00509 m_underflow = 0; 00510 00511 InitContexts(); 00512 } 00513 00514 template<class T> 00515 void ArithCodec<T>::EncodeProbInterval( const ProbInterval& prob_interval , const calc_t range) 00516 { 00517 //formulae given we know we're binary coding 00518 if ( !prob_interval.Start() ) // prob_interval.Start()=0, so symbol is 0, so m_low_code unchanged 00519 m_high_code = m_low_code + static_cast<code_t>( ( ( range * prob_interval.Stop() )>>10 ) - 1 ); 00520 else //symbol is 1, so m_high_code unchanged 00521 m_low_code += static_cast<code_t>(( range * prob_interval.Start() ) >>10 ); 00522 00523 do 00524 { 00525 if (( m_high_code & CODE_MSB ) == ( m_low_code & CODE_MSB )) 00526 { 00527 m_bit_output->OutputBit( m_high_code & CODE_MSB, m_bit_count); 00528 for (; m_underflow > 0; m_underflow-- ) 00529 m_bit_output->OutputBit(~m_high_code & CODE_MSB, m_bit_count); 00530 } 00531 00532 else if ( ( m_low_code & CODE_2ND_MSB ) && !( m_high_code & CODE_2ND_MSB )) 00533 { 00534 m_underflow ++; 00535 m_low_code ^= CODE_2ND_MSB; 00536 m_high_code ^= CODE_2ND_MSB; 00537 } 00538 else return ; 00539 00540 m_low_code <<= 1; 00541 m_high_code <<= 1; 00542 m_high_code ++; 00543 } 00544 while ( true ); 00545 } 00546 00547 template<class T> 00548 inline void ArithCodec<T>::EncodeSymbol(const bool symbol, const int context_num) 00549 { 00550 const calc_t range( static_cast<calc_t>( m_high_code - m_low_code ) + 1 ); 00551 EncodeProbInterval( m_context_list[context_num].GetProbInterval(symbol) , range ); 00552 Update( symbol , context_num ); 00553 } 00554 00555 template<class T> 00556 void ArithCodec<T>::FlushEncoder() 00557 { 00558 // Flushes the output 00559 m_bit_output->OutputBit(m_low_code & CODE_2ND_MSB,m_bit_count); 00560 m_underflow++; 00561 00562 while ( m_underflow-- > 0 ) 00563 m_bit_output->OutputBit(~m_low_code & CODE_2ND_MSB, m_bit_count); 00564 } 00565 00566 template<class T> 00567 void ArithCodec<T>::InitDecoder() 00568 { 00569 InitContexts(); 00570 00571 m_input_bits_left = 8; 00572 00573 ReadAllData(); 00574 00575 //Read in a full word of data 00576 code_t i; 00577 m_code = 0; 00578 00579 for ( i = 0; i < (8 * sizeof(code_t)); i++ ) 00580 { 00581 m_code <<= 1; 00582 00583 if ( InputBit() ) 00584 m_code++; 00585 } 00586 00587 m_low_code = 0; 00588 m_high_code = CODE_MAX; 00589 m_underflow = 0; 00590 } 00591 00592 template<class T> 00593 void ArithCodec<T>::RemFromStream( const ProbInterval& prob_interval , const calc_t range ) 00594 { 00595 if( !prob_interval.Start() )//prob_interval.Start()=0, so symbol is 0, so m_low_code unchanged 00596 m_high_code = m_low_code + static_cast<code_t>( ( ( range * prob_interval.Stop() )>>10 ) - 1 ); 00597 00598 else//symbol is 1, so m_high_code unchanged 00599 m_low_code += static_cast<code_t>(( range * prob_interval.Start() )>>10 ); 00600 00601 do 00602 { 00603 if ( ( m_high_code & CODE_MSB ) == ( m_low_code & CODE_MSB ) ) 00604 { 00605 // Do nothing 00606 } 00607 else if ( (m_low_code & CODE_2ND_MSB) && !(m_high_code & CODE_2ND_MSB) ) 00608 { 00609 m_code ^= CODE_2ND_MSB; 00610 m_low_code ^= CODE_2ND_MSB; 00611 m_high_code ^= CODE_2ND_MSB; 00612 } 00613 else return; 00614 00615 m_low_code <<= 1; 00616 m_high_code <<= 1; 00617 m_high_code++; 00618 m_code <<= 1; 00619 00620 m_code += InputBit(); 00621 00622 } while ( true ); 00623 00624 } 00625 00626 template<class T> 00627 inline bool ArithCodec<T>::DecodeSymbol( const int context_num ) 00628 { 00629 ProbInterval limits; 00630 00631 const calc_t count( ( ( static_cast<calc_t>( m_code - m_low_code ) + 1 )<<10 ) - 1 ); 00632 00633 const calc_t range( static_cast<calc_t>( m_high_code - m_low_code ) + 1 ); 00634 00635 bool symbol( m_context_list[context_num].GetSymbol( count , range , limits ) ); 00636 00637 RemFromStream( limits , range ); 00638 Update( symbol , context_num ); 00639 00640 return symbol; 00641 } 00642 00643 template<class T> 00644 void ArithCodec<T>::ReadAllData() 00645 { 00646 if ( m_decode_data_ptr ) 00647 delete[] m_decode_data_ptr; 00648 00649 m_decode_data_ptr = new char[m_max_count + 2]; 00650 m_bit_input->InputBytes( m_decode_data_ptr , m_max_count ); 00651 00652 m_decode_data_ptr[m_max_count] = 0; 00653 m_decode_data_ptr[m_max_count+1] = 0; 00654 00655 m_data_ptr = m_decode_data_ptr; 00656 00657 } 00658 00659 template<class T> 00660 inline bool ArithCodec<T>::InputBit() 00661 { 00662 if (m_input_bits_left == 0) 00663 { 00664 m_data_ptr++; 00665 m_input_bits_left = 8; 00666 } 00667 m_input_bits_left--; 00668 00669 return bool( ( (*m_data_ptr) >> m_input_bits_left ) & 1 ); 00670 } 00671 00672 template<class T> 00673 inline void ArithCodec<T>::Update( const bool symbol , const int context_num ) 00674 { 00675 Context& ctx = m_context_list[context_num]; 00676 00677 ctx.IncrCount( symbol ); 00678 00679 if ( ctx.Weight() >= 1024 ) 00680 ctx.HalveCounts(); 00681 } 00682 00683 00684 }// end dirac namespace 00685 00686 #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.