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.8 2004/08/19 11:45:32 asuraparaju Exp $ $Name: Dirac_0_4_3 $ 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 00065 00070 template<class T> //T is container/array type 00071 class ArithCodec 00072 { 00073 public: 00074 00076 00081 ArithCodec(BasicOutputManager * bits_out, size_t number_of_contexts); 00082 00084 00089 ArithCodec(BitInputManager * bits_in, size_t number_of_contexts); 00090 00092 00095 virtual ~ArithCodec(); 00096 00098 00104 int Compress(T & in_data); 00105 00107 00115 void Decompress(T & out_data, int num_bits); 00116 00117 protected: 00118 00119 // use explicity type sizes for portability 00120 typedef uint16_t code_t; 00121 typedef uint32_t calc_t; 00122 00123 // NOTE: These macros imply an unsigned 16-bit operand 00124 static const code_t CODE_MAX = 0xffff; 00125 static const code_t CODE_MSB = ((0xffff + 1) >> 1); 00126 static const code_t CODE_2ND_MSB = ((0xffff + 1) >> 2); 00127 00129 00134 class Triple 00135 { 00136 public: 00138 Triple() 00139 : m_start(0), 00140 m_stop(0), 00141 m_weight(0) {} 00142 00143 // value constructor 00144 Triple(code_t start, code_t stop, code_t weight) 00145 { 00146 m_start = start; 00147 m_stop = stop; 00148 m_weight = weight; 00149 } 00150 00152 Triple(const Triple& rhs) 00153 : m_start(rhs.m_start), 00154 m_stop(rhs.m_stop), 00155 m_weight(rhs.m_weight) { } 00156 00158 Triple & operator = (const Triple& rhs) 00159 { 00160 m_start = rhs.m_start; 00161 m_stop = rhs.m_stop; 00162 m_weight = rhs.m_weight; 00163 return *this; 00164 } 00165 00166 // get the start value 00167 code_t Start() const { return m_start; } 00168 00169 // get the stop value 00170 code_t Stop() const { return m_stop; } 00171 00172 // get the weight value 00173 code_t Weight() const { return m_weight; } 00174 00175 private: 00177 code_t m_start; 00178 00180 code_t m_stop; 00181 00183 code_t m_weight; 00184 }; 00185 00187 00191 class Context 00192 { 00193 public: 00195 00198 Context() 00199 { 00200 SetCounts(1,1); 00201 } 00202 00204 00207 Context(int cnt0,int cnt1) 00208 { 00209 SetCounts(cnt0,cnt1); 00210 } 00211 00213 Context(const Context & cpy) 00214 : count0(cpy.count0), 00215 count1(cpy.count1), 00216 trip0(cpy.trip0), 00217 trip1(cpy.trip1) 00218 {} 00219 00221 Context & operator=(const Context& rhs) 00222 { 00223 count0 = rhs.count0; 00224 count1 = rhs.count1; 00225 trip0 = rhs.trip0; 00226 trip1 = rhs.trip1; 00227 return *this; 00228 } 00229 00231 ~Context() {} 00232 00234 00237 void SetCounts(int cnt0, int cnt1) 00238 { 00239 count0 = cnt0; 00240 count1 = cnt1; 00241 SetTriples(); 00242 } 00243 00245 code_t GetCount0() const { return count0; } 00246 00248 code_t GetCount1() const { return count1; } 00249 00251 00256 void IncrCount(bool Symbol, int amnt) 00257 { 00258 if (Symbol) 00259 count1 += amnt; 00260 else 00261 count0 += amnt; 00262 00263 SetTriples(); 00264 } 00265 00267 void HalveCounts() 00268 { 00269 count0 >>= 1; 00270 count0++; 00271 count1 >>= 1; 00272 count1++; 00273 00274 SetTriples(); 00275 } 00276 00278 code_t Weight() const { return trip0.Weight(); } 00279 00281 const Triple & GetTriple( const bool symbol ) const { return (symbol ? trip1 : trip0); } 00282 00284 00289 bool GetSymbol(const code_t num, Triple & trip_val) const 00290 { 00291 if (num < trip0.Stop()) 00292 { 00293 trip_val = trip0; 00294 return false; //ie zero 00295 } 00296 else 00297 { 00298 trip_val = trip1; 00299 return true; //ie 1 00300 } 00301 } 00302 00303 private: 00304 code_t count0; 00305 code_t count1; 00306 00307 Triple trip0; 00308 Triple trip1; 00309 00310 void SetTriples() 00311 { 00312 //updates triples given counts 00313 trip0 = Triple(0, trip0.Start() + count0, count0 + count1); 00314 trip1 = Triple(trip0.Stop(), trip1.Start() + count1, trip0.Weight()); 00315 } 00316 }; 00317 00318 protected: 00319 00321 //std::vector<Context> & ContextList() { return m_context_list; } 00322 00323 //virtual codec functions (to be overridden) 00325 00327 virtual void InitContexts()=0; 00328 00330 virtual void Update( const bool symbol , const int context_num )=0; 00331 00333 virtual void Resize(const int context_num)=0; 00334 00336 virtual void ResetAll()=0; 00337 00339 virtual int ChooseContext(const T &data, const int bin_number) const =0; 00340 00342 virtual int ChooseContext(const T &data) const=0; 00343 00344 //virtual encode-only functions 00346 00348 virtual void DoWorkCode(T & in_data) = 0; 00349 00350 //core encode-only functions 00352 00354 void InitEncoder(); 00355 00357 void EncodeTriple(const Triple & c); 00358 00360 void EncodeSymbol(const bool symbol, const int context_num); 00361 00363 void FlushEncoder(); 00364 00366 void FlushDecoder(); 00367 00370 virtual void DoWorkDecode(T & out_data, int num_bits)=0; 00371 00372 // core decode-only functions 00374 00376 void InitDecoder(); 00377 00379 void RemFromStream(const Triple & c); 00380 00382 void SetCurrentCount(const int context_num); 00383 00385 void DecodeSymbol(bool& symbol, int context_num); 00386 00387 private: 00389 int m_bit_count; 00390 00392 int m_max_count; 00393 00395 long m_underflow; 00396 00398 code_t m_code; 00399 00401 code_t m_count; 00402 00404 code_t m_low_code; 00405 00407 code_t m_high_code; 00408 00409 // Parameters for controlling coding/decoding 00410 // codec_params_type cparams; 00411 00413 BitInputManager* m_bit_input; 00414 00416 BasicOutputManager* m_bit_output; 00417 00418 //private, bodyless copy constructor: class should not be copied 00419 ArithCodec(const ArithCodec & cpy); 00420 00421 //private, bodyless copy operator=: class should not be assigned 00422 ArithCodec & operator = (const ArithCodec & rhs); 00423 00424 00425 protected: 00426 00428 std::vector<Context> m_context_list; 00429 }; 00430 00431 //Implementation - core functions 00433 00434 template<class T> 00435 ArithCodec<T>::ArithCodec(BitInputManager* bits_in, size_t number_of_contexts) 00436 : m_bit_count(0), 00437 m_bit_input(bits_in), 00438 m_context_list(number_of_contexts) 00439 { 00440 // nothing needed here 00441 } 00442 00444 template<class T> 00445 ArithCodec<T>::ArithCodec(BasicOutputManager* bits_out, size_t number_of_contexts) 00446 : m_bit_count(0), 00447 m_bit_output(bits_out), 00448 m_context_list(number_of_contexts) 00449 { 00450 // nothing needed here 00451 } 00452 00453 template<class T> 00454 ArithCodec<T>::~ArithCodec() 00455 { 00456 // nothing needed here 00457 } 00458 00459 template<class T> 00460 int ArithCodec<T>::Compress(T &in_data) 00461 { 00462 InitEncoder(); 00463 DoWorkCode(in_data); 00464 FlushEncoder(); 00465 return m_bit_count; 00466 } 00467 00468 template<class T> 00469 void ArithCodec<T>::Decompress(T &out_data, int num_bits) 00470 { 00471 m_max_count=num_bits; 00472 InitDecoder(); 00473 DoWorkDecode(out_data,num_bits); 00474 FlushDecoder(); 00475 m_bit_input->FlushInput(); 00476 } 00477 00478 template<class T> 00479 void ArithCodec<T>::InitEncoder() 00480 { 00481 // Set the m_code word stuff 00482 m_low_code = 0; 00483 m_high_code = CODE_MAX; 00484 m_underflow = 0; 00485 } 00486 00487 template<class T> 00488 void ArithCodec<T>::EncodeTriple(const Triple &c) 00489 { 00490 calc_t range; 00491 00492 // Rescale m_high_code and m_low_code for the new symbol 00493 range=(calc_t)(m_high_code - m_low_code) + 1; 00494 00495 //formulae given we know we're binary coding 00496 if (!c.Start()) // c.Start()=0, so symbol is 0, so m_low_code unchanged 00497 m_high_code = m_low_code + (code_t)(( range * c.Stop() ) / c.Weight() - 1 ); 00498 else //symbol is 1, so m_high_code unchanged 00499 m_low_code += (code_t)(( range * c.Start() ) / c.Weight() ); 00500 00501 // This loop turns out new bits until m_high_code and m_low_code are far enough apart to have stabilized. 00502 do 00503 { 00504 // If this test passes, it means that the MSDigits match, and can be sent to the output stream. 00505 if (( m_high_code & CODE_MSB ) == ( m_low_code & CODE_MSB )) 00506 { 00507 m_bit_output->OutputBit( m_high_code & CODE_MSB, m_bit_count); 00508 while ( m_underflow > 0 ) 00509 { 00510 m_bit_output->OutputBit(~m_high_code & CODE_MSB, m_bit_count); 00511 m_underflow--; 00512 } 00513 } 00514 // If this test passes, we're in danger of underflow 00515 else if ( ( m_low_code & CODE_2ND_MSB ) && !( m_high_code & CODE_2ND_MSB )) 00516 { 00517 m_underflow += 1; 00518 m_low_code &= (CODE_2ND_MSB) - 1; 00519 m_high_code |= CODE_2ND_MSB; 00520 } 00521 else return ; 00522 00523 m_low_code <<= 1; 00524 m_high_code <<= 1; 00525 m_high_code |= 1; 00526 } 00527 while(true); 00528 } 00529 00530 template<class T> 00531 inline void ArithCodec<T>::EncodeSymbol(const bool symbol, const int context_num) 00532 { 00533 EncodeTriple(m_context_list[context_num].GetTriple(symbol)); 00534 Update( symbol , context_num ); 00535 } 00536 00537 template<class T> 00538 void ArithCodec<T>::FlushEncoder() 00539 { 00540 // Flushes the output 00541 m_bit_output->OutputBit(m_low_code & CODE_2ND_MSB,m_bit_count); 00542 m_underflow++; 00543 00544 while ( m_underflow-- > 0 ) 00545 m_bit_output->OutputBit(~m_low_code & CODE_2ND_MSB, m_bit_count); 00546 } 00547 00548 template<class T> 00549 void ArithCodec<T>::InitDecoder() 00550 { 00551 //Read in a full word of data 00552 code_t i; 00553 m_code = 0; 00554 00555 for ( i = 0; i < (8 * sizeof(code_t)); i++ ) 00556 { 00557 m_code <<= 1; 00558 00559 if (m_bit_input->InputBit(m_bit_count,m_max_count)) 00560 m_code++; 00561 } 00562 00563 m_low_code = 0; 00564 m_high_code = CODE_MAX; 00565 m_underflow = 0; 00566 } 00567 00568 template<class T> 00569 void ArithCodec<T>::RemFromStream(const Triple &c) 00570 { 00571 calc_t range; 00572 00573 //First, the range is expanded to account for the symbol removal. 00574 range=(calc_t)( m_high_code - m_low_code ) + 1; 00575 00576 if(!c.Start())//c.Start()=0, so symbol is 0, so m_low_code unchanged 00577 m_high_code = m_low_code + (code_t)(( range * c.Stop() ) / c.Weight() - 1 ); 00578 else//symbol is 1, so m_high_code unchanged 00579 m_low_code+=(code_t)(( range * c.Start() ) / c.Weight() ); 00580 00581 do 00582 { 00583 //If the MSDigits match, the bits will be shifted out. 00584 if ( ( m_high_code & CODE_MSB ) == ( m_low_code & CODE_MSB ) ) 00585 { 00586 // do nothing 00587 } 00588 //Else, if underflow is threatening, shift out the 2nd MSDigit. 00589 else if ((m_low_code & CODE_2ND_MSB) == CODE_2ND_MSB && (m_high_code & CODE_2ND_MSB) == 0 ) 00590 { 00591 m_code ^= CODE_2ND_MSB; 00592 m_low_code &= (CODE_2ND_MSB) - 1; 00593 m_high_code |= CODE_2ND_MSB; 00594 } 00595 //Otherwise, nothing can be shifted out, so return. 00596 else return; 00597 00598 m_low_code <<= 1; 00599 m_high_code <<= 1; 00600 m_high_code |= 1; 00601 m_code <<= 1; 00602 00603 if ( m_bit_input->InputBit( m_bit_count , m_max_count ) ) 00604 m_code++; 00605 00606 } while (1); 00607 00608 } 00609 00610 template<class T> 00611 void ArithCodec<T>::SetCurrentCount(const int context_num) 00612 { 00613 calc_t range; 00614 range = (long) ( m_high_code - m_low_code ) + 1; 00615 m_count=(code_t)((((long) ( m_code - m_low_code ) + 1 ) * m_context_list[context_num].Weight() - 1 ) / range ); 00616 } 00617 00618 template<class T> 00619 void ArithCodec<T>::DecodeSymbol(bool& symbol, const int context_num) 00620 { 00621 Triple limits; 00622 SetCurrentCount( context_num ); 00623 symbol = m_context_list[context_num].GetSymbol( m_count , limits ); 00624 RemFromStream( limits ); 00625 Update( symbol , context_num ); 00626 } 00627 00628 template<class T> 00629 void ArithCodec<T>::FlushDecoder() 00630 { 00631 // Flushes the input 00632 while(m_bit_count < m_max_count) 00633 m_bit_input->InputBit(m_bit_count, m_max_count); 00634 } 00635 00636 #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.