FFmpeg
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
cabac.c
Go to the documentation of this file.
1 /*
2  * H.26L/H.264/AVC/JVT/14496-10/... encoder/decoder
3  * Copyright (c) 2003 Michael Niedermayer <michaelni@gmx.at>
4  *
5  * This file is part of FFmpeg.
6  *
7  * FFmpeg is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public
9  * License as published by the Free Software Foundation; either
10  * version 2.1 of the License, or (at your option) any later version.
11  *
12  * FFmpeg is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15  * Lesser General Public License for more details.
16  *
17  * You should have received a copy of the GNU Lesser General Public
18  * License along with FFmpeg; if not, write to the Free Software
19  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20  */
21 
22 /**
23  * @file
24  * Context Adaptive Binary Arithmetic Coder.
25  */
26 
27 #include <string.h>
28 
29 #include "libavutil/common.h"
30 #include "libavutil/timer.h"
31 #include "get_bits.h"
32 #include "cabac.h"
33 #include "cabac_functions.h"
34 
35 const uint8_t ff_h264_cabac_tables[512 + 4*2*64 + 4*64 + 63] = {
36  9,8,7,7,6,6,6,6,5,5,5,5,5,5,5,5,
37  4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
38  3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,
39  3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,
40  2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
41  2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
42  2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
43  2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
44  1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
45  1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
46  1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
47  1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
48  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
49  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
50  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
51  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
52  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
53  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
54  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
55  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
56  // LPS range
57  -128, -128, -128, -128, -128, -128, 123, 123,
58  116, 116, 111, 111, 105, 105, 100, 100,
59  95, 95, 90, 90, 85, 85, 81, 81,
60  77, 77, 73, 73, 69, 69, 66, 66,
61  62, 62, 59, 59, 56, 56, 53, 53,
62  51, 51, 48, 48, 46, 46, 43, 43,
63  41, 41, 39, 39, 37, 37, 35, 35,
64  33, 33, 32, 32, 30, 30, 29, 29,
65  27, 27, 26, 26, 24, 24, 23, 23,
66  22, 22, 21, 21, 20, 20, 19, 19,
67  18, 18, 17, 17, 16, 16, 15, 15,
68  14, 14, 14, 14, 13, 13, 12, 12,
69  12, 12, 11, 11, 11, 11, 10, 10,
70  10, 10, 9, 9, 9, 9, 8, 8,
71  8, 8, 7, 7, 7, 7, 7, 7,
72  6, 6, 6, 6, 6, 6, 2, 2,
73  -80, -80, -89, -89, -98, -98, -106, -106,
74  -114, -114, -121, -121, -128, -128, 122, 122,
75  116, 116, 110, 110, 104, 104, 99, 99,
76  94, 94, 89, 89, 85, 85, 80, 80,
77  76, 76, 72, 72, 69, 69, 65, 65,
78  62, 62, 59, 59, 56, 56, 53, 53,
79  50, 50, 48, 48, 45, 45, 43, 43,
80  41, 41, 39, 39, 37, 37, 35, 35,
81  33, 33, 31, 31, 30, 30, 28, 28,
82  27, 27, 26, 26, 24, 24, 23, 23,
83  22, 22, 21, 21, 20, 20, 19, 19,
84  18, 18, 17, 17, 16, 16, 15, 15,
85  14, 14, 14, 14, 13, 13, 12, 12,
86  12, 12, 11, 11, 11, 11, 10, 10,
87  9, 9, 9, 9, 9, 9, 8, 8,
88  8, 8, 7, 7, 7, 7, 2, 2,
89  -48, -48, -59, -59, -69, -69, -78, -78,
90  -87, -87, -96, -96, -104, -104, -112, -112,
91  -119, -119, -126, -126, 123, 123, 117, 117,
92  111, 111, 105, 105, 100, 100, 95, 95,
93  90, 90, 86, 86, 81, 81, 77, 77,
94  73, 73, 69, 69, 66, 66, 63, 63,
95  59, 59, 56, 56, 54, 54, 51, 51,
96  48, 48, 46, 46, 43, 43, 41, 41,
97  39, 39, 37, 37, 35, 35, 33, 33,
98  32, 32, 30, 30, 29, 29, 27, 27,
99  26, 26, 25, 25, 23, 23, 22, 22,
100  21, 21, 20, 20, 19, 19, 18, 18,
101  17, 17, 16, 16, 15, 15, 15, 15,
102  14, 14, 13, 13, 12, 12, 12, 12,
103  11, 11, 11, 11, 10, 10, 10, 10,
104  9, 9, 9, 9, 8, 8, 2, 2,
105  -16, -16, -29, -29, -40, -40, -51, -51,
106  -61, -61, -71, -71, -81, -81, -90, -90,
107  -98, -98, -106, -106, -114, -114, -121, -121,
108  -128, -128, 122, 122, 116, 116, 110, 110,
109  104, 104, 99, 99, 94, 94, 89, 89,
110  85, 85, 80, 80, 76, 76, 72, 72,
111  69, 69, 65, 65, 62, 62, 59, 59,
112  56, 56, 53, 53, 50, 50, 48, 48,
113  45, 45, 43, 43, 41, 41, 39, 39,
114  37, 37, 35, 35, 33, 33, 31, 31,
115  30, 30, 28, 28, 27, 27, 25, 25,
116  24, 24, 23, 23, 22, 22, 21, 21,
117  20, 20, 19, 19, 18, 18, 17, 17,
118  16, 16, 15, 15, 14, 14, 14, 14,
119  13, 13, 12, 12, 12, 12, 11, 11,
120  11, 11, 10, 10, 9, 9, 2, 2,
121  // mlps state
122  127, 126, 77, 76, 77, 76, 75, 74,
123  75, 74, 75, 74, 73, 72, 73, 72,
124  73, 72, 71, 70, 71, 70, 71, 70,
125  69, 68, 69, 68, 67, 66, 67, 66,
126  67, 66, 65, 64, 65, 64, 63, 62,
127  61, 60, 61, 60, 61, 60, 59, 58,
128  59, 58, 57, 56, 55, 54, 55, 54,
129  53, 52, 53, 52, 51, 50, 49, 48,
130  49, 48, 47, 46, 45, 44, 45, 44,
131  43, 42, 43, 42, 39, 38, 39, 38,
132  37, 36, 37, 36, 33, 32, 33, 32,
133  31, 30, 31, 30, 27, 26, 27, 26,
134  25, 24, 23, 22, 23, 22, 19, 18,
135  19, 18, 17, 16, 15, 14, 13, 12,
136  11, 10, 9, 8, 9, 8, 5, 4,
137  5, 4, 3, 2, 1, 0, 0, 1,
138  2, 3, 4, 5, 6, 7, 8, 9,
139  10, 11, 12, 13, 14, 15, 16, 17,
140  18, 19, 20, 21, 22, 23, 24, 25,
141  26, 27, 28, 29, 30, 31, 32, 33,
142  34, 35, 36, 37, 38, 39, 40, 41,
143  42, 43, 44, 45, 46, 47, 48, 49,
144  50, 51, 52, 53, 54, 55, 56, 57,
145  58, 59, 60, 61, 62, 63, 64, 65,
146  66, 67, 68, 69, 70, 71, 72, 73,
147  74, 75, 76, 77, 78, 79, 80, 81,
148  82, 83, 84, 85, 86, 87, 88, 89,
149  90, 91, 92, 93, 94, 95, 96, 97,
150  98, 99, 100, 101, 102, 103, 104, 105,
151  106, 107, 108, 109, 110, 111, 112, 113,
152  114, 115, 116, 117, 118, 119, 120, 121,
153  122, 123, 124, 125, 124, 125, 126, 127,
154  // last_coeff_flag_offset_8x8
155  0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
156  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
157  3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
158  5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8
159 };
160 
161 /**
162  *
163  * @param buf_size size of buf in bits
164  */
165 void ff_init_cabac_encoder(CABACContext *c, uint8_t *buf, int buf_size){
166  init_put_bits(&c->pb, buf, buf_size);
167 
168  c->low= 0;
169  c->range= 0x1FE;
170  c->outstanding_count= 0;
171  c->pb.bit_left++; //avoids firstBitFlag
172 }
173 
174 /**
175  *
176  * @param buf_size size of buf in bits
177  */
178 int ff_init_cabac_decoder(CABACContext *c, const uint8_t *buf, int buf_size){
179  c->bytestream_start=
180  c->bytestream= buf;
181  c->bytestream_end= buf + buf_size;
182 
183 #if CABAC_BITS == 16
184  c->low = (*c->bytestream++)<<18;
185  c->low+= (*c->bytestream++)<<10;
186  // Keep our fetches on a 2-byte boundry as this should avoid ever having to
187  // do unaligned loads if the compiler (or asm) optimises the double byte
188  // load into a single instruction
189  if(((uintptr_t)c->bytestream & 1) == 0) {
190  c->low += (1 << 9);
191  }
192  else {
193  c->low += ((*c->bytestream++) << 2) + 2;
194  }
195 #else
196  c->low = (*c->bytestream++)<<10;
197  c->low+= ((*c->bytestream++)<<2) + 2;
198 #endif
199  c->range= 0x1FE;
200  if ((c->range<<(CABAC_BITS+1)) < c->low)
201  return AVERROR_INVALIDDATA;
202  return 0;
203 }
204 
205 #ifdef TEST
206 #define SIZE 10240
207 
208 #include "libavutil/lfg.h"
209 #include "avcodec.h"
210 
211 static inline void put_cabac_bit(CABACContext *c, int b){
212  put_bits(&c->pb, 1, b);
213  for(;c->outstanding_count; c->outstanding_count--){
214  put_bits(&c->pb, 1, 1-b);
215  }
216 }
217 
218 static inline void renorm_cabac_encoder(CABACContext *c){
219  while(c->range < 0x100){
220  //FIXME optimize
221  if(c->low<0x100){
222  put_cabac_bit(c, 0);
223  }else if(c->low<0x200){
224  c->outstanding_count++;
225  c->low -= 0x100;
226  }else{
227  put_cabac_bit(c, 1);
228  c->low -= 0x200;
229  }
230 
231  c->range+= c->range;
232  c->low += c->low;
233  }
234 }
235 
236 static void put_cabac(CABACContext *c, uint8_t * const state, int bit){
237  int RangeLPS= ff_h264_lps_range[2*(c->range&0xC0) + *state];
238 
239  if(bit == ((*state)&1)){
240  c->range -= RangeLPS;
241  *state = ff_h264_mlps_state[128 + *state];
242  }else{
243  c->low += c->range - RangeLPS;
244  c->range = RangeLPS;
245  *state= ff_h264_mlps_state[127 - *state];
246  }
247 
248  renorm_cabac_encoder(c);
249 }
250 
251 /**
252  * @param bit 0 -> write zero bit, !=0 write one bit
253  */
254 static void put_cabac_bypass(CABACContext *c, int bit){
255  c->low += c->low;
256 
257  if(bit){
258  c->low += c->range;
259  }
260 //FIXME optimize
261  if(c->low<0x200){
262  put_cabac_bit(c, 0);
263  }else if(c->low<0x400){
264  c->outstanding_count++;
265  c->low -= 0x200;
266  }else{
267  put_cabac_bit(c, 1);
268  c->low -= 0x400;
269  }
270 }
271 
272 /**
273  *
274  * @return the number of bytes written
275  */
276 static int put_cabac_terminate(CABACContext *c, int bit){
277  c->range -= 2;
278 
279  if(!bit){
280  renorm_cabac_encoder(c);
281  }else{
282  c->low += c->range;
283  c->range= 2;
284 
285  renorm_cabac_encoder(c);
286 
287  av_assert0(c->low <= 0x1FF);
288  put_cabac_bit(c, c->low>>9);
289  put_bits(&c->pb, 2, ((c->low>>7)&3)|1);
290 
291  flush_put_bits(&c->pb); //FIXME FIXME FIXME XXX wrong
292  }
293 
294  return (put_bits_count(&c->pb)+7)>>3;
295 }
296 
297 int main(void){
298  CABACContext c;
299  uint8_t b[9*SIZE];
300  uint8_t r[9*SIZE];
301  int i, ret = 0;
302  uint8_t state[10]= {0};
303  AVLFG prng;
304 
305  av_lfg_init(&prng, 1);
306  ff_init_cabac_encoder(&c, b, SIZE);
307 
308  for(i=0; i<SIZE; i++){
309  if(2*i<SIZE) r[i] = av_lfg_get(&prng) % 7;
310  else r[i] = (i>>8)&1;
311  }
312 
313  for(i=0; i<SIZE; i++){
314  put_cabac_bypass(&c, r[i]&1);
315  }
316 
317  for(i=0; i<SIZE; i++){
318  put_cabac(&c, state, r[i]&1);
319  }
320 
321  i= put_cabac_terminate(&c, 1);
322  b[i++] = av_lfg_get(&prng);
323  b[i ] = av_lfg_get(&prng);
324 
325  ff_init_cabac_decoder(&c, b, SIZE);
326 
327  memset(state, 0, sizeof(state));
328 
329  for(i=0; i<SIZE; i++){
330  if( (r[i]&1) != get_cabac_bypass(&c) ) {
331  av_log(NULL, AV_LOG_ERROR, "CABAC bypass failure at %d\n", i);
332  ret = 1;
333  }
334  }
335 
336  for(i=0; i<SIZE; i++){
337  if( (r[i]&1) != get_cabac_noinline(&c, state) ) {
338  av_log(NULL, AV_LOG_ERROR, "CABAC failure at %d\n", i);
339  ret = 1;
340  }
341  }
342  if(!get_cabac_terminate(&c)) {
343  av_log(NULL, AV_LOG_ERROR, "where's the Terminator?\n");
344  ret = 1;
345  }
346 
347  return ret;
348 }
349 
350 #endif /* TEST */
AVLFG
Definition: lfg.h:25
NULL
#define NULL
Definition: coverity.c:32
AVERROR_INVALIDDATA
#define AVERROR_INVALIDDATA
Invalid data found when processing input.
Definition: error.h:59
put_bits
static void put_bits(Jpeg2000EncoderContext *s, int val, int n)
put n times val bit
Definition: j2kenc.c:168
CABACContext::bytestream_end
const uint8_t * bytestream_end
Definition: cabac.h:49
b
const char * b
Definition: vf_curves.c:109
CABAC_BITS
#define CABAC_BITS
Definition: cabac.h:40
get_cabac_noinline
static int av_noinline av_unused get_cabac_noinline(CABACContext *c, uint8_t *const state)
Definition: cabac_functions.h:131
av_assert0
#define av_assert0(cond)
assert() equivalent, that is always enabled.
Definition: avassert.h:37
CABACContext::bytestream
const uint8_t * bytestream
Definition: cabac.h:48
uint8_t
uint8_t
Definition: audio_convert.c:194
SIZE
#define SIZE
Definition: golomb-test.c:31
get_bits.h
bitstream reader API header.
timer.h
high precision timer, useful to profile code
av_log
#define av_log(a,...)
Definition: tableprint_vlc.h:28
AV_LOG_ERROR
#define AV_LOG_ERROR
Something went wrong and cannot losslessly be recovered.
Definition: log.h:176
r
const char * r
Definition: vf_curves.c:107
put_bits_count
static int put_bits_count(PutBitContext *s)
Definition: put_bits.h:85
CABACContext::bytestream_start
const uint8_t * bytestream_start
Definition: cabac.h:47
ff_init_cabac_decoder
int ff_init_cabac_decoder(CABACContext *c, const uint8_t *buf, int buf_size)
Definition: cabac.c:178
cabac_functions.h
Context Adaptive Binary Arithmetic Coder inline functions.
ff_init_cabac_encoder
void ff_init_cabac_encoder(CABACContext *c, uint8_t *buf, int buf_size)
Definition: cabac.c:165
get_cabac_terminate
static int av_unused get_cabac_terminate(CABACContext *c)
Definition: cabac_functions.h:179
avcodec.h
Libavcodec external API header.
PutBitContext::bit_left
int bit_left
Definition: put_bits.h:37
CABACContext::outstanding_count
int outstanding_count
Definition: cabac.h:46
av_lfg_get
static unsigned int av_lfg_get(AVLFG *c)
Get the next random unsigned 32-bit number using an ALFG.
Definition: lfg.h:38
buf
void * buf
Definition: avisynth_c.h:553
CABACContext::range
int range
Definition: cabac.h:45
ff_h264_cabac_tables
const uint8_t ff_h264_cabac_tables[512+4 *2 *64+4 *64+63]
Definition: cabac.c:35
av_lfg_init
av_cold void av_lfg_init(AVLFG *c, unsigned int seed)
Definition: lfg.c:30
CABACContext::pb
PutBitContext pb
Definition: cabac.h:50
get_cabac_bypass
static int av_unused get_cabac_bypass(CABACContext *c)
Definition: cabac_functions.h:140
CABACContext::low
int low
Definition: cabac.h:44
flush_put_bits
static void flush_put_bits(PutBitContext *s)
Pad the end of the output stream with zeros.
Definition: put_bits.h:101
common.h
common internal and external API header
c
static double c[64]
Definition: vsrc_mptestsrc.c:87
init_put_bits
static void init_put_bits(PutBitContext *s, uint8_t *buffer, int buffer_size)
Initialize the PutBitContext s.
Definition: put_bits.h:48
ff_h264_lps_range
static const uint8_t *const ff_h264_lps_range
Definition: cabac_functions.h:50
state
static struct @205 state
main
int main(int argc, char **argv)
Definition: main.c:22
ff_h264_mlps_state
static const uint8_t *const ff_h264_mlps_state
Definition: cabac_functions.h:51
cabac.h
Context Adaptive Binary Arithmetic Coder.
Generated on Mon Feb 15 2016 15:20:37 for FFmpeg by   doxygen 1.8.6