Created by the British Broadcasting Corporation.
00001 /* ***** BEGIN LICENSE BLOCK ***** 00002 * 00003 * $Id: arith_codec.h,v 1.29 2006/06/13 09:07:25 timborer 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 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 { 00065 00069 class ContextLookupTable { 00070 public: 00071 00073 00077 ContextLookupTable(); 00078 00080 inline static unsigned int lookup(int weight); 00081 private: 00082 static unsigned int table[256]; 00083 }; 00084 00085 class Context: private ContextLookupTable { 00086 public: 00087 00089 00092 inline Context(); 00093 00094 //Class is POD 00095 //Use built in copy constructor, assignment and destructor. 00096 00098 inline void SetCounts( unsigned int cnt0, unsigned int cnt1); 00099 00101 inline unsigned int Weight() const; 00102 00104 inline void HalveCounts(); 00105 00107 inline unsigned int GetScaledProb0( ) const; 00108 00110 inline void Update( bool symbol ); 00111 00112 private: 00113 00114 int m_count0; 00115 int m_count1; 00116 }; 00117 00118 class ArithCodecBase { 00119 00120 public: 00121 00123 00129 ArithCodecBase(ByteIO* p_byteio, size_t number_of_contexts); 00130 00132 00135 virtual ~ArithCodecBase(); 00136 00137 protected: 00138 00139 //virtual codec functions (to be overridden) 00141 00143 virtual void InitContexts()=0; 00144 00146 virtual void ResetAll()=0; 00147 00148 //core encode functions 00150 00152 void InitEncoder(); 00153 00155 void EncodeSymbol(const bool symbol, const int context_num); 00156 00157 void EncodeUInt(const unsigned int value, const int bin1, const int max_bin); 00158 00159 void EncodeSInt(const int value, const int bin1, const int max_bin); 00160 00162 void FlushEncoder(); 00163 00164 int ByteCount() const; 00165 00166 // core decode functions 00168 00170 void InitDecoder(int num_bytes); 00171 00173 bool DecodeSymbol( int context_num ); 00174 00175 unsigned int DecodeUInt(const int bin1, const int max_bin); 00176 00177 int DecodeSInt(const int bin1, const int max_bin); 00178 00180 std::vector<Context> m_context_list; 00181 00182 private: 00183 00185 ArithCodecBase(const ArithCodecBase & cpy); 00186 00188 ArithCodecBase & operator = (const ArithCodecBase & rhs); 00189 00190 // Encode functions 00192 00194 inline void ShiftBitOut(); 00195 00197 inline void OutputBits(); 00198 00199 // Decode functions 00201 00203 void ReadAllData(int num_bytes); 00204 00206 inline void ShiftBitIn(); 00207 00209 inline bool InputBit(); 00210 00211 // NOTE: These constants imply an unsigned 16-bit operand 00212 static const unsigned int CODE_MAX = 0xFFFF; 00213 static const unsigned int CODE_MSB = 0x8000; 00214 static const unsigned int CODE_2ND_MSB = 0x4000; 00215 00216 // Codec data 00218 00220 unsigned int m_low_code; 00221 00223 unsigned int m_high_code; 00224 00226 ByteIO *m_byteio; 00227 00228 // For encoder only 00229 00231 int m_underflow; 00232 00234 char* m_decode_data_ptr; 00235 00237 char* m_data_ptr; 00238 00240 int m_input_bits_left; 00241 00243 unsigned int m_code; 00244 00245 }; 00246 00247 00248 00249 inline bool ArithCodecBase::DecodeSymbol( int context_num ) 00250 { 00251 // NB: loops could be while loops predicated on the break conditions 00252 // However, each loop reads in a bit, so the max number of bits 00253 // input is the coding word-length - 16 here. This means the 00254 // iterations can be bounded (and the loop unrolled if desired). 00255 // Admittedly, this syntax is pig-ugly and while loops would be 00256 // prettier. 00257 00258 // Shift bits in until MSBs are different. 00259 for (int i=0; i<16; ++i ) 00260 { 00261 // Shift bits in until MSBs are different. 00262 if ( (m_high_code^m_low_code)>=CODE_MSB ) 00263 break; 00264 ShiftBitIn(); 00265 } 00266 00267 for (int i=0; i<16; ++i ) 00268 { 00269 if ( !(m_low_code & CODE_2ND_MSB) || (m_high_code & CODE_2ND_MSB) ) 00270 break; 00271 00272 // If we're here, we have high = 10xxxxx and low = 01xxxxx, 00273 // so we're straddling 1/2-way point - a condition known as 00274 // underflow. We flip the 2nd highest bit. Combined with the 00275 // subsequent bitshift, this has the effect of doubling the 00276 // [low,high] interval width about 1/2 00277 m_code ^= CODE_2ND_MSB; 00278 m_low_code ^= CODE_2ND_MSB; 00279 m_high_code ^= CODE_2ND_MSB; 00280 ShiftBitIn(); 00281 } 00282 00283 // Determine the next symbol value by placing code within 00284 // the [low,high] interval. 00285 00286 // Fetch the statistical context to be used 00287 Context& ctx = m_context_list[context_num]; 00288 00289 // Decode as per updated specification 00290 const unsigned int count = m_code - m_low_code + 1; 00291 const unsigned int range_prob = 00292 ((m_high_code - m_low_code + 1) * ctx.GetScaledProb0())>>16; 00293 bool symbol = ( count > range_prob ); 00294 00295 // Update the statistical context 00296 ctx.Update( symbol ); 00297 00298 // Rescale the interval 00299 if( symbol ) //symbol is 1, so m_high_code unchanged 00300 m_low_code += range_prob; 00301 else //symbol is 0, so m_low_code unchanged 00302 m_high_code = m_low_code + range_prob - 1; 00303 00304 return symbol; 00305 } 00306 00307 inline unsigned int ArithCodecBase::DecodeUInt(const int bin1, const int max_bin) { 00308 const int info_ctx = (max_bin+1); 00309 int bin = bin1; 00310 unsigned int value = 1; 00311 while (!DecodeSymbol(bin)) { 00312 value <<= 1; 00313 if (DecodeSymbol(info_ctx)) value+=1; 00314 if (bin<max_bin) bin+=1; 00315 } 00316 value -= 1; 00317 return value; 00318 } 00319 00320 inline int ArithCodecBase::DecodeSInt(const int bin1, const int max_bin) { 00321 int value = 0; 00322 const int magnitude = DecodeUInt(bin1, max_bin); 00323 if (magnitude!=0) { 00324 if (DecodeSymbol(max_bin+2)) value=-magnitude; 00325 else value=magnitude; 00326 } 00327 return value; 00328 } 00329 00330 inline void ArithCodecBase::EncodeSymbol(const bool symbol, const int context_num) 00331 { 00332 // NB: loops could be while loops predicated on the break conditions 00333 // However, each loop reads in a bit, so the max number of bits 00334 // input is the coding word-length - 16 here. This means the 00335 // iterations can be bounded (and the loop unrolled if desired). 00336 // Admittedly, this syntax is pig-ugly and while loops would be 00337 // prettier. 00338 00339 // Delete 2nd MSBs until they are the same to prevent underflow 00340 for (int i=0; i<16; ++i ) 00341 { 00342 if ( !(m_low_code & CODE_2ND_MSB) || (m_high_code & CODE_2ND_MSB) ) 00343 break; 00344 00345 // If we're here, we have high = 10xxxxx and low = 01xxxxx, 00346 // so we're straddling 1/2-way point - a condition known as 00347 // underflow. We flip the 2nd highest bit. Combined with the 00348 // subsequent bitshift, this has the effect of doubling the 00349 // [low,high] interval width about 1/2 00350 m_underflow += 1; 00351 m_low_code ^= CODE_2ND_MSB; 00352 m_high_code ^= CODE_2ND_MSB; 00353 ShiftBitOut(); 00354 } 00355 00356 // Adjust high and low (rescale interval) based on the symbol we are encoding 00357 00358 Context& ctx = m_context_list[context_num]; 00359 00360 const unsigned int range_prob = 00361 ((m_high_code - m_low_code + 1) * ctx.GetScaledProb0())>>16; 00362 00363 if ( symbol ) //symbol is 1, so m_high_code unchanged 00364 m_low_code += range_prob; 00365 else // symbol is 0, so m_low_code unchanged 00366 m_high_code = m_low_code + range_prob - 1 ; 00367 00368 // Update the statistical context 00369 ctx.Update( symbol ); 00370 00371 // Shift bits out until MSBs are different. 00372 for (int i=0; i<16; ++i ) 00373 { 00374 if ( (m_high_code^m_low_code)>=CODE_MSB ) 00375 break; 00376 OutputBits(); 00377 ShiftBitOut(); 00378 } 00379 } 00380 00381 inline void ArithCodecBase::EncodeUInt(const unsigned int the_int, 00382 const int bin1, const int max_bin) { 00383 const int value = (the_int+1); 00384 const int info_ctx = (max_bin+1); 00385 int bin = bin1; 00386 int top_bit = 1; 00387 { 00388 int max_value = 1; 00389 while (value>max_value) { 00390 top_bit <<= 1; 00391 max_value <<= 1; 00392 max_value += 1; 00393 } 00394 } 00395 bool stop = (top_bit==1); 00396 EncodeSymbol(stop, bin); 00397 while (!stop) { 00398 top_bit >>= 1; 00399 EncodeSymbol( (value&top_bit), info_ctx); 00400 if ( bin < max_bin) bin+=1; 00401 stop = (top_bit==1); 00402 EncodeSymbol(stop, bin); 00403 } 00404 } 00405 00406 inline void ArithCodecBase::EncodeSInt(const int value, 00407 const int bin1, const int max_bin) { 00408 EncodeUInt(std::abs(value), bin1, max_bin); 00409 if (value != 0) { 00410 EncodeSymbol( (value < 0), max_bin+2 ); 00411 } 00412 } 00413 00414 00416 00422 template<class T> //T is container/array type 00423 class ArithCodec 00424 : public ArithCodecBase 00425 { 00426 public: 00427 00429 00435 ArithCodec(ByteIO* p_byteio, size_t number_of_contexts); 00436 00437 00439 00442 virtual ~ArithCodec() {} 00443 00445 00453 int Compress(T & in_data); 00454 00456 00464 void Decompress(T & out_data, const int num_bytes); 00465 00466 protected: 00467 00468 //virtual encode-only functions 00470 00472 virtual void DoWorkCode(T & in_data) = 0; 00473 00476 virtual void DoWorkDecode(T & out_data)=0; 00477 }; 00478 00479 //Implementation - core functions 00481 00482 template<class T> 00483 ArithCodec<T>::ArithCodec(ByteIO* p_byteio, size_t number_of_contexts): 00484 ArithCodecBase(p_byteio, number_of_contexts) {} 00485 00486 00487 00488 template<class T> 00489 int ArithCodec<T>::Compress(T &in_data) 00490 { 00491 InitEncoder(); 00492 DoWorkCode(in_data); 00493 FlushEncoder(); 00494 return ByteCount(); 00495 } 00496 00497 template<class T> 00498 void ArithCodec<T>::Decompress( T &out_data, const int num_bytes ) 00499 { 00500 InitDecoder(num_bytes); 00501 DoWorkDecode( out_data ); 00502 } 00503 00504 void ArithCodecBase::ShiftBitOut() 00505 { 00506 // Shift out top-most bit and increment high value 00507 m_high_code <<= 1; 00508 m_high_code &= CODE_MAX; 00509 m_high_code += 1; 00510 m_low_code <<= 1; 00511 m_low_code &= CODE_MAX; 00512 } 00513 00514 void ArithCodecBase::OutputBits() 00515 { 00516 m_byteio->OutputBit( m_high_code & CODE_MSB); 00517 for (; m_underflow > 0; m_underflow-- ) 00518 m_byteio->OutputBit(~m_high_code & CODE_MSB); 00519 } 00520 00521 inline void ArithCodecBase::ShiftBitIn() 00522 { 00523 m_high_code <<= 1; 00524 m_high_code &= CODE_MAX; 00525 m_high_code += 1; 00526 m_low_code <<= 1; 00527 m_low_code &= CODE_MAX; 00528 m_code <<= 1; 00529 m_code &= CODE_MAX; 00530 m_code += InputBit(); 00531 } 00532 00533 inline bool ArithCodecBase::InputBit() 00534 { 00535 if (m_input_bits_left == 0) 00536 { 00537 m_data_ptr++; 00538 m_input_bits_left = 8; 00539 } 00540 m_input_bits_left--; 00541 #if 1 00542 // MSB to LSB 00543 return bool( ( (*m_data_ptr) >> m_input_bits_left ) & 1 ); 00544 #else 00545 // LSB to MSB 00546 bool val = *m_data_ptr & 0x01; 00547 *m_data_ptr >>= 1; 00548 return val; 00549 #endif 00550 } 00551 00552 Context::Context(): 00553 m_count0(1), m_count1(1) {} 00554 00555 void Context::SetCounts( unsigned int cnt0, unsigned int cnt1) 00556 { 00557 m_count0 = cnt0; 00558 m_count1 = cnt1; 00559 } 00560 00561 unsigned int Context::Weight() const 00562 { 00563 return m_count0+m_count1; 00564 } 00565 00566 void Context::HalveCounts() 00567 { 00568 m_count0 >>= 1; 00569 ++m_count0; 00570 m_count1 >>= 1; 00571 ++m_count1; 00572 } 00573 00574 // The probability of a binary input/output symbol is estimated 00575 // from past counts of 0 and 1 for symbols in the same context. 00576 // Probability is estimated as: 00577 // probability of 0 = count0/(count0+count1) 00578 // Probability is re-calculated for every symbol. 00579 // To avoid the division a lookup table is used. 00580 // This is a fixed point implementation so probability is scaled to 00581 // a range of 0 to 2**16. 00582 // The value of (count0+count1) is known as "weight". 00583 // The lookup table precalculates the values of: 00584 // lookup(weight) = ((1<<16)+weight/2)/weight 00585 // The probability calculation becomes: 00586 // probability of = count0 * lookup(weight) 00587 int unsigned Context::GetScaledProb0() const 00588 { 00589 return m_count0*lookup(m_count0+m_count1); 00590 } 00591 00592 void Context::Update( bool symbol ) 00593 { 00594 if ( !symbol ) 00595 ++m_count0; 00596 else 00597 ++m_count1; 00598 if ( Weight() >= 256 ) 00599 HalveCounts(); 00600 } 00601 00602 unsigned int ContextLookupTable::lookup(int weight) { 00603 return table[weight]; 00604 } 00605 00606 }// end dirac namespace 00607 00608 #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.