# Dirac - A Video Codec

Created by the British Broadcasting Corporation.

arith_codec.h
Go to the documentation of this file.
1 /* ***** BEGIN LICENSE BLOCK *****
2 *
3 * $Id: arith_codec.h,v 1.40 2007/11/16 04:48:44 asuraparaju Exp $ $Name: Dirac_1_0_2 $
4 *
5 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
6 *
7 * The contents of this file are subject to the Mozilla Public License
8 * Version 1.1 (the "License"); you may not use this file except in compliance
9 * with the License. You may obtain a copy of the License at
10 * http://www.mozilla.org/MPL/
11 *
12 * Software distributed under the License is distributed on an "AS IS" basis,
13 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License for
14 * the specific language governing rights and limitations under the License.
15 *
16 * The Original Code is BBC Research and Development code.
17 *
18 * The Initial Developer of the Original Code is the British Broadcasting
19 * Corporation.
20 * Portions created by the Initial Developer are Copyright (C) 2004.
21 * All Rights Reserved.
22 *
23 * Contributor(s): Richard Felton (Original Author),
24 Thomas Davies,
25 Scott R Ladd,
26 Peter Bleackley,
27 Steve Bearcroft,
28 Anuradha Suraparaju,
29 Tim Borer (major refactor February 2006)
30 Andrew Kennedy
31 *
32 * Alternatively, the contents of this file may be used under the terms of
33 * the GNU General Public License Version 2 (the "GPL"), or the GNU Lesser
34 * Public License Version 2.1 (the "LGPL"), in which case the provisions of
35 * the GPL or the LGPL are applicable instead of those above. If you wish to
36 * allow use of your version of this file only under the terms of the either
37 * the GPL or LGPL and not to allow others to use your version of this file
38 * under the MPL, indicate your decision by deleting the provisions above
39 * and replace them with the notice and other provisions required by the GPL
40 * or LGPL. If you do not delete the provisions above, a recipient may use
41 * your version of this file under the terms of any one of the MPL, the GPL
42 * or the LGPL.
43 * ***** END LICENSE BLOCK ***** */
44
45
46 #ifndef _ARITH_CODEC_H_
47 #define _ARITH_CODEC_H_
48
57
58 #include <libdirac_common/common.h>
59 #include <libdirac_byteio/byteio.h>
60 #include <vector>
61
62 namespace dirac
63 {
64
65 class Context {
66 public:
67
69
72 inline Context();
73
74 //Class is POD
75 //Use built in copy constructor, assignment and destructor.
76
78
79 inline unsigned int GetScaledProb0( ) const{ return m_prob0;}
80
82 inline void Update( bool symbol ) {
83 if (symbol) m_prob0 -= lut[m_prob0>>8];
84 else m_prob0 += lut[255-(m_prob0>>8)];
85 }
86
87 private:
88
89 int m_prob0;
90 static const unsigned int lut[256]; //Probability update table
91 };
92
93 Context::Context(): m_prob0( 0x8000 ) {}
94
95 class ArithCodecBase {
96
97 public:
98
100
106 ArithCodecBase(ByteIO* p_byteio, size_t number_of_contexts);
107
109
112 virtual ~ArithCodecBase();
113
114 protected:
115
116 //core encode functions
118
120 void InitEncoder();
121
123 void EncodeSymbol(const bool symbol, const int context_num);
124
125 void EncodeUInt(const unsigned int value, const int bin1, const int max_bin);
126
127 void EncodeSInt(const int value, const int bin1, const int max_bin);
128
130 void FlushEncoder();
131
132 int ByteCount() const;
133
134 // core decode functions
136
138 void InitDecoder(int num_bytes);
139
141 bool DecodeSymbol( int context_num );
142
143 unsigned int DecodeUInt(const int bin1, const int max_bin);
144
145 int DecodeSInt(const int bin1, const int max_bin);
146
148 std::vector<Context> m_context_list;
149
150 private:
151
153 ArithCodecBase(const ArithCodecBase & cpy);
154
156 ArithCodecBase & operator = (const ArithCodecBase & rhs);
157
158
159 // Decode functions
161
163 void ReadAllData(int num_bytes);
164
166 inline bool InputBit();
167
168 // Codec data
170
171 unsigned int m_scount;
172
174 unsigned int m_low_code;
175
177 unsigned int m_range;
178
180 ByteIO *m_byteio;
181
182 // For encoder only
183
185 int m_underflow;
186
188 char* m_decode_data_ptr;
189
191 char* m_data_ptr;
192
194 int m_input_bits_left;
195
197 unsigned int m_code;
198
199 };
200
201
202 inline bool ArithCodecBase::DecodeSymbol( int context_num )
203 {
204
205 // Determine the next symbol value by placing code within
206 // the [low,high] interval.
207
208 // Fetch the statistical context to be used
209 Context& ctx = m_context_list[context_num];
210
211 // Decode as per updated specification
212 const unsigned int count = m_code - m_low_code ;
213 const unsigned int range_x_prob = ( m_range* ctx.GetScaledProb0())>>16;
214 const bool symbol = ( count >= range_x_prob );
215
216 // Rescale the interval
217 if( symbol ) //symbol is 1
218 {
219 m_low_code += range_x_prob;
220 m_range -= range_x_prob;
221 }
222 else //symbol is 0, so m_low_code unchanged
223 {
224 m_range = range_x_prob;
225 }
226
227 // Update the statistical context
228 ctx.Update( symbol );
229
230 while ( m_range<=0x4000 )
231 {
232 if( ( (m_low_code+m_range-1)^m_low_code)>=0x8000 )
233 {
234 // Straddle condition
235 // We must have an underflow situation with
236 // low = 0x01... and high = 0x10...
237 // Flip 2nd bit prior to rescaling
238 m_code ^= 0x4000;
239 m_low_code ^= 0x4000;
240 }
241
242 // Double low and range, throw away top bit of low
243 m_low_code <<= 1;
244 m_range <<= 1;
245 m_low_code &= 0xFFFF;
246
247 // Shift in another bit of code
248 m_code <<= 1;
249 m_code += InputBit();
250 m_code &= 0xFFFF;
251
252 }
253
254 return symbol;
255 }
256
257 inline unsigned int ArithCodecBase::DecodeUInt(const int bin1, const int max_bin) {
258 const int info_ctx = (max_bin+1);
259 int bin = bin1;
260 unsigned int value = 1;
261 while (!DecodeSymbol(bin)) {
262 value <<= 1;
263 if (DecodeSymbol(info_ctx)) value+=1;
264 if (bin<max_bin) bin+=1;
265 }
266 value -= 1;
267 return value;
268 }
269
270 inline int ArithCodecBase::DecodeSInt(const int bin1, const int max_bin) {
271 int value = 0;
272 const int magnitude = DecodeUInt(bin1, max_bin);
273 if (magnitude!=0) {
274 if (DecodeSymbol(max_bin+2)) value=-magnitude;
275 else value=magnitude;
276 }
277 return value;
278 }
279
280 inline void ArithCodecBase::EncodeSymbol(const bool symbol, const int context_num)
281 {
282
283 // Adjust high and low (rescale interval) based on the symbol we are encoding
284
285 Context& ctx = m_context_list[context_num];
286
287 const unsigned int range_x_prob = ( m_range* ctx.GetScaledProb0())>>16;
288
289 if ( symbol ) //symbol is 1
290 {
291 m_low_code += range_x_prob;
292 m_range -= range_x_prob;
293 }
294 else // symbol is 0, so m_low_code unchanged
295 {
296 m_range = range_x_prob;
297 }
298
299 // Update the statistical context
300 ctx.Update( symbol );
301
302 while ( m_range <= 0x4000 )
303 {
304 if ( ( (m_low_code+m_range-1)^m_low_code)>=0x8000 )
305 {
306 // Straddle condition
307 // We must have an underflow situation with
308 // low = 0x01... and high = 0x10...
309
310 m_low_code ^= 0x4000;
311 m_underflow++;
312
313 }
314 else
315 {
316 // Bits agree - output them
317 m_byteio->WriteBit( m_low_code & 0x8000);
318 for (; m_underflow > 0; m_underflow-- )
319 m_byteio->WriteBit(~m_low_code & 0x8000);
320 }
321
322 // Double low value and range
323 m_low_code <<= 1;
324 m_range <<= 1;
325
326 // keep low to 16 bits - throw out top bit
327 m_low_code &= 0xFFFF;
328
329 }
330 }
331
332 inline void ArithCodecBase::EncodeUInt(const unsigned int the_int,
333 const int bin1, const int max_bin) {
334 const int value = (the_int+1);
335 const int info_ctx = (max_bin+1);
336 int bin = bin1;
337 int top_bit = 1;
338 {
339 int max_value = 1;
340 while (value>max_value) {
341 top_bit <<= 1;
342 max_value <<= 1;
343 max_value += 1;
344 }
345 }
346 bool stop = (top_bit==1);
347 EncodeSymbol(stop, bin);
348 while (!stop) {
349 top_bit >>= 1;
350 EncodeSymbol( (value&top_bit), info_ctx);
351 if ( bin < max_bin) bin+=1;
352 stop = (top_bit==1);
353 EncodeSymbol(stop, bin);
354 }
355 }
356
357 inline void ArithCodecBase::EncodeSInt(const int value,
358 const int bin1, const int max_bin) {
359 EncodeUInt(std::abs(value), bin1, max_bin);
360 if (value != 0) {
361 EncodeSymbol( (value < 0), max_bin+2 );
362 }
363 }
364
365
367
373 template<class T> //T is container/array type
374 class ArithCodec
375 : public ArithCodecBase
376 {
377 public:
378
380
386 ArithCodec(ByteIO* p_byteio, size_t number_of_contexts);
387
388
390
393 virtual ~ArithCodec() {}
394
396
404 int Compress(T & in_data);
405
407
415 void Decompress(T & out_data, const int num_bytes);
416
417 protected:
418
419 //virtual encode-only functions
421
423 virtual void DoWorkCode(T & in_data) = 0;
424
427 virtual void DoWorkDecode(T & out_data)=0;
428 };
429
430 //Implementation - core functions
432
433 template<class T>
434 ArithCodec<T>::ArithCodec(ByteIO* p_byteio, size_t number_of_contexts):
435 ArithCodecBase(p_byteio, number_of_contexts) {}
436
437
438
439 template<class T>
440 int ArithCodec<T>::Compress(T &in_data)
441 {
442 InitEncoder();
443 DoWorkCode(in_data);
444 FlushEncoder();
445 return ByteCount();
446 }
447
448 template<class T>
449 void ArithCodec<T>::Decompress( T &out_data, const int num_bytes )
450 {
451 InitDecoder(num_bytes);
452 DoWorkDecode( out_data );
453 }
454
455 inline bool ArithCodecBase::InputBit()
456 {
457 if (m_input_bits_left == 0)
458 {
459 m_data_ptr++;
460 m_input_bits_left = 8;
461 }
462 m_input_bits_left--;
463 // MSB to LSB
464 return bool( ( (*m_data_ptr) >> m_input_bits_left ) & 1 );
465 }
466
467 }// namespace dirac
468 #endif
469

© 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.