Created by the British Broadcasting Corporation.
00001 /* ***** BEGIN LICENSE BLOCK ***** 00002 * 00003 * $Id: arith_codec.h,v 1.36 2007/03/01 09:24:32 tjdwave 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 // The probability of a binary input/output symbol is estimated 00099 // from past counts of 0 and 1 for symbols in the same context. 00100 // Probability is estimated as: 00101 // probability of 0 = count0/(count0+count1) 00102 // Probability is re-calculated for every symbol. 00103 // To avoid the division a lookup table is used. 00104 // This is a fixed point implementation so probability is scaled to 00105 // a range of 0 to 2**16. 00106 // The value of (count0+count1) is known as "weight". 00107 // The lookup table precalculates the values of: 00108 // lookup(weight) = ((1<<16)+weight/2)/weight 00109 // The probability calculation becomes: 00110 // probability of = count0 * lookup(weight) 00111 inline unsigned int GetScaledProb0( ) const{ return m_prob0;} 00112 00114 inline void Update( bool symbol ); 00115 00116 private: 00117 00118 int m_count0; 00119 int m_count1; 00120 int m_prob0; 00121 }; 00122 00123 Context::Context(): 00124 m_count0(1), m_count1(1), m_prob0( 0x8000 ) {} 00125 00126 00127 void Context::Update( bool symbol ) 00128 { 00129 if ( !symbol ) 00130 ++m_count0; 00131 else 00132 ++m_count1; 00133 00134 if ( (m_count0+m_count1)%8==0) 00135 { 00136 if ( (m_count0+m_count1) == 256 ) 00137 { 00138 m_count0++; 00139 m_count0 >>= 1; 00140 m_count1++; 00141 m_count1 >>= 1; 00142 } 00143 m_prob0 = m_count0*lookup( m_count0+m_count1 ); 00144 } 00145 00146 00147 } 00148 00149 unsigned int ContextLookupTable::lookup(int weight) { 00150 return table[weight]; 00151 } 00152 00153 00154 class ArithCodecBase { 00155 00156 public: 00157 00159 00165 ArithCodecBase(ByteIO* p_byteio, size_t number_of_contexts); 00166 00168 00171 virtual ~ArithCodecBase(); 00172 00173 protected: 00174 00175 //core encode functions 00177 00179 void InitEncoder(); 00180 00182 void EncodeSymbol(const bool symbol, const int context_num); 00183 00184 void EncodeUInt(const unsigned int value, const int bin1, const int max_bin); 00185 00186 void EncodeSInt(const int value, const int bin1, const int max_bin); 00187 00189 void FlushEncoder(); 00190 00191 int ByteCount() const; 00192 00193 // core decode functions 00195 00197 void InitDecoder(int num_bytes); 00198 00200 bool DecodeSymbol( int context_num ); 00201 00202 unsigned int DecodeUInt(const int bin1, const int max_bin); 00203 00204 int DecodeSInt(const int bin1, const int max_bin); 00205 00207 std::vector<Context> m_context_list; 00208 00209 private: 00210 00212 ArithCodecBase(const ArithCodecBase & cpy); 00213 00215 ArithCodecBase & operator = (const ArithCodecBase & rhs); 00216 00217 00218 // Decode functions 00220 00222 void ReadAllData(int num_bytes); 00223 00225 inline bool InputBit(); 00226 00227 // Codec data 00229 00230 unsigned int m_scount; 00231 00233 unsigned int m_low_code; 00234 00236 unsigned int m_range; 00237 00239 ByteIO *m_byteio; 00240 00241 // For encoder only 00242 00244 int m_underflow; 00245 00247 char* m_decode_data_ptr; 00248 00250 char* m_data_ptr; 00251 00253 int m_input_bits_left; 00254 00256 unsigned int m_code; 00257 00258 }; 00259 00260 00261 inline bool ArithCodecBase::DecodeSymbol( int context_num ) 00262 { 00263 00264 // Determine the next symbol value by placing code within 00265 // the [low,high] interval. 00266 00267 // Fetch the statistical context to be used 00268 Context& ctx = m_context_list[context_num]; 00269 00270 // Decode as per updated specification 00271 const unsigned int count = m_code - m_low_code + 1; 00272 const unsigned int range_x_prob = ( m_range* ctx.GetScaledProb0())>>16; 00273 bool symbol = ( count > range_x_prob ); 00274 00275 // Rescale the interval 00276 if( symbol ) //symbol is 1 00277 { 00278 m_low_code += range_x_prob; 00279 m_range -= range_x_prob; 00280 } 00281 else //symbol is 0, so m_low_code unchanged 00282 { 00283 m_range = range_x_prob; 00284 } 00285 00286 // Update the statistical context 00287 ctx.Update( symbol ); 00288 00289 while ( m_range<=0x4000 ) 00290 { 00291 if( ( (m_low_code+m_range-1)^m_low_code)>=0x8000 ) 00292 { 00293 // Straddle condition 00294 // We must have an underflow situation with 00295 // low = 0x01... and high = 0x10... 00296 // Flip 2nd bit prior to rescaling 00297 m_code ^= 0x4000; 00298 m_low_code ^= 0x4000; 00299 } 00300 00301 // Double low and range, throw away top bit of low 00302 m_low_code <<= 1; 00303 m_range <<= 1; 00304 m_low_code &= 0xFFFF; 00305 00306 // Shift in another bit of code 00307 m_code <<= 1; 00308 m_code += InputBit(); 00309 m_code &= 0xFFFF; 00310 00311 } 00312 00313 return symbol; 00314 } 00315 00316 inline unsigned int ArithCodecBase::DecodeUInt(const int bin1, const int max_bin) { 00317 const int info_ctx = (max_bin+1); 00318 int bin = bin1; 00319 unsigned int value = 1; 00320 while (!DecodeSymbol(bin)) { 00321 value <<= 1; 00322 if (DecodeSymbol(info_ctx)) value+=1; 00323 if (bin<max_bin) bin+=1; 00324 } 00325 value -= 1; 00326 return value; 00327 } 00328 00329 inline int ArithCodecBase::DecodeSInt(const int bin1, const int max_bin) { 00330 int value = 0; 00331 const int magnitude = DecodeUInt(bin1, max_bin); 00332 if (magnitude!=0) { 00333 if (DecodeSymbol(max_bin+2)) value=-magnitude; 00334 else value=magnitude; 00335 } 00336 return value; 00337 } 00338 00339 inline void ArithCodecBase::EncodeSymbol(const bool symbol, const int context_num) 00340 { 00341 00342 // Adjust high and low (rescale interval) based on the symbol we are encoding 00343 00344 Context& ctx = m_context_list[context_num]; 00345 00346 const unsigned int range_x_prob = ( m_range* ctx.GetScaledProb0())>>16; 00347 00348 if ( symbol ) //symbol is 1 00349 { 00350 m_low_code += range_x_prob; 00351 m_range -= range_x_prob; 00352 } 00353 else // symbol is 0, so m_low_code unchanged 00354 { 00355 m_range = range_x_prob; 00356 } 00357 00358 // Update the statistical context 00359 ctx.Update( symbol ); 00360 00361 while ( m_range <= 0x4000 ) 00362 { 00363 if ( ( (m_low_code+m_range-1)^m_low_code)>=0x8000 ) 00364 { 00365 // Straddle condition 00366 // We must have an underflow situation with 00367 // low = 0x01... and high = 0x10... 00368 00369 m_low_code ^= 0x4000; 00370 m_underflow++; 00371 00372 } 00373 else 00374 { 00375 // Bits agree - output them 00376 m_byteio->OutputBit( m_low_code & 0x8000); 00377 for (; m_underflow > 0; m_underflow-- ) 00378 m_byteio->OutputBit(~m_low_code & 0x8000); 00379 } 00380 00381 // Double low value and range 00382 m_low_code <<= 1; 00383 m_range <<= 1; 00384 00385 // keep low to 16 bits - throw out top bit 00386 m_low_code &= 0xFFFF; 00387 00388 } 00389 00390 } 00391 00392 inline void ArithCodecBase::EncodeUInt(const unsigned int the_int, 00393 const int bin1, const int max_bin) { 00394 const int value = (the_int+1); 00395 const int info_ctx = (max_bin+1); 00396 int bin = bin1; 00397 int top_bit = 1; 00398 { 00399 int max_value = 1; 00400 while (value>max_value) { 00401 top_bit <<= 1; 00402 max_value <<= 1; 00403 max_value += 1; 00404 } 00405 } 00406 bool stop = (top_bit==1); 00407 EncodeSymbol(stop, bin); 00408 while (!stop) { 00409 top_bit >>= 1; 00410 EncodeSymbol( (value&top_bit), info_ctx); 00411 if ( bin < max_bin) bin+=1; 00412 stop = (top_bit==1); 00413 EncodeSymbol(stop, bin); 00414 } 00415 } 00416 00417 inline void ArithCodecBase::EncodeSInt(const int value, 00418 const int bin1, const int max_bin) { 00419 EncodeUInt(std::abs(value), bin1, max_bin); 00420 if (value != 0) { 00421 EncodeSymbol( (value < 0), max_bin+2 ); 00422 } 00423 } 00424 00425 00427 00433 template<class T> //T is container/array type 00434 class ArithCodec 00435 : public ArithCodecBase 00436 { 00437 public: 00438 00440 00446 ArithCodec(ByteIO* p_byteio, size_t number_of_contexts); 00447 00448 00450 00453 virtual ~ArithCodec() {} 00454 00456 00464 int Compress(T & in_data); 00465 00467 00475 void Decompress(T & out_data, const int num_bytes); 00476 00477 protected: 00478 00479 //virtual encode-only functions 00481 00483 virtual void DoWorkCode(T & in_data) = 0; 00484 00487 virtual void DoWorkDecode(T & out_data)=0; 00488 }; 00489 00490 //Implementation - core functions 00492 00493 template<class T> 00494 ArithCodec<T>::ArithCodec(ByteIO* p_byteio, size_t number_of_contexts): 00495 ArithCodecBase(p_byteio, number_of_contexts) {} 00496 00497 00498 00499 template<class T> 00500 int ArithCodec<T>::Compress(T &in_data) 00501 { 00502 InitEncoder(); 00503 DoWorkCode(in_data); 00504 FlushEncoder(); 00505 return ByteCount(); 00506 } 00507 00508 template<class T> 00509 void ArithCodec<T>::Decompress( T &out_data, const int num_bytes ) 00510 { 00511 InitDecoder(num_bytes); 00512 DoWorkDecode( out_data ); 00513 } 00514 00515 inline bool ArithCodecBase::InputBit() 00516 { 00517 if (m_input_bits_left == 0) 00518 { 00519 m_data_ptr++; 00520 m_input_bits_left = 8; 00521 } 00522 m_input_bits_left--; 00523 // MSB to LSB 00524 return bool( ( (*m_data_ptr) >> m_input_bits_left ) & 1 ); 00525 } 00526 00527 }// namespace dirac 00528 #endif 00529
© 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.