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 "get_bits.h"
31 #include "cabac.h"
32 #include "cabac_functions.h"
33 
34 uint8_t ff_h264_cabac_tables[512 + 4*2*64 + 4*64 + 63] = {
35  9,8,7,7,6,6,6,6,5,5,5,5,5,5,5,5,
36  4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
37  3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,
38  3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,
39  2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
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  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,
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  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,
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 };
56 
57 static const uint8_t lps_range[64][4]= {
58 {128,176,208,240}, {128,167,197,227}, {128,158,187,216}, {123,150,178,205},
59 {116,142,169,195}, {111,135,160,185}, {105,128,152,175}, {100,122,144,166},
60 { 95,116,137,158}, { 90,110,130,150}, { 85,104,123,142}, { 81, 99,117,135},
61 { 77, 94,111,128}, { 73, 89,105,122}, { 69, 85,100,116}, { 66, 80, 95,110},
62 { 62, 76, 90,104}, { 59, 72, 86, 99}, { 56, 69, 81, 94}, { 53, 65, 77, 89},
63 { 51, 62, 73, 85}, { 48, 59, 69, 80}, { 46, 56, 66, 76}, { 43, 53, 63, 72},
64 { 41, 50, 59, 69}, { 39, 48, 56, 65}, { 37, 45, 54, 62}, { 35, 43, 51, 59},
65 { 33, 41, 48, 56}, { 32, 39, 46, 53}, { 30, 37, 43, 50}, { 29, 35, 41, 48},
66 { 27, 33, 39, 45}, { 26, 31, 37, 43}, { 24, 30, 35, 41}, { 23, 28, 33, 39},
67 { 22, 27, 32, 37}, { 21, 26, 30, 35}, { 20, 24, 29, 33}, { 19, 23, 27, 31},
68 { 18, 22, 26, 30}, { 17, 21, 25, 28}, { 16, 20, 23, 27}, { 15, 19, 22, 25},
69 { 14, 18, 21, 24}, { 14, 17, 20, 23}, { 13, 16, 19, 22}, { 12, 15, 18, 21},
70 { 12, 14, 17, 20}, { 11, 14, 16, 19}, { 11, 13, 15, 18}, { 10, 12, 15, 17},
71 { 10, 12, 14, 16}, { 9, 11, 13, 15}, { 9, 11, 12, 14}, { 8, 10, 12, 14},
72 { 8, 9, 11, 13}, { 7, 9, 11, 12}, { 7, 9, 10, 12}, { 7, 8, 10, 11},
73 { 6, 8, 9, 11}, { 6, 7, 9, 10}, { 6, 7, 8, 9}, { 2, 2, 2, 2},
74 };
75 
76 static uint8_t h264_lps_state[2*64];
77 static uint8_t h264_mps_state[2*64];
78 
79 static const uint8_t mps_state[64]= {
80  1, 2, 3, 4, 5, 6, 7, 8,
81  9,10,11,12,13,14,15,16,
82  17,18,19,20,21,22,23,24,
83  25,26,27,28,29,30,31,32,
84  33,34,35,36,37,38,39,40,
85  41,42,43,44,45,46,47,48,
86  49,50,51,52,53,54,55,56,
87  57,58,59,60,61,62,62,63,
88 };
89 
90 static const uint8_t lps_state[64]= {
91  0, 0, 1, 2, 2, 4, 4, 5,
92  6, 7, 8, 9, 9,11,11,12,
93  13,13,15,15,16,16,18,18,
94  19,19,21,21,22,22,23,24,
95  24,25,26,26,27,27,28,29,
96  29,30,30,30,31,32,32,33,
97  33,33,34,34,35,35,35,36,
98  36,36,37,37,37,38,38,63,
99 };
100 
102  0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
103  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
104  3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
105  5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8
106 };
107 
108 /**
109  *
110  * @param buf_size size of buf in bits
111  */
113  init_put_bits(&c->pb, buf, buf_size);
114 
115  c->low= 0;
116  c->range= 0x1FE;
117  c->outstanding_count= 0;
118  c->pb.bit_left++; //avoids firstBitFlag
119 }
120 
121 /**
122  *
123  * @param buf_size size of buf in bits
124  */
125 void ff_init_cabac_decoder(CABACContext *c, const uint8_t *buf, int buf_size){
126  c->bytestream_start=
127  c->bytestream= buf;
128  c->bytestream_end= buf + buf_size;
129 
130 #if CABAC_BITS == 16
131  c->low = (*c->bytestream++)<<18;
132  c->low+= (*c->bytestream++)<<10;
133 #else
134  c->low = (*c->bytestream++)<<10;
135 #endif
136  c->low+= ((*c->bytestream++)<<2) + 2;
137  c->range= 0x1FE;
138 }
139 
141 {
142  int i, j;
143 
144  for(i=0; i<64; i++){
145  for(j=0; j<4; j++){ //FIXME check if this is worth the 1 shift we save
146  ff_h264_lps_range[j*2*64+2*i+0]=
147  ff_h264_lps_range[j*2*64+2*i+1]= lps_range[i][j];
148  }
149 
150  ff_h264_mlps_state[128+2*i+0]=
151  h264_mps_state[2 * i + 0] = 2 * mps_state[i] + 0;
152  ff_h264_mlps_state[128+2*i+1]=
153  h264_mps_state[2 * i + 1] = 2 * mps_state[i] + 1;
154 
155  if( i ){
156  h264_lps_state[2*i+0]=
157  ff_h264_mlps_state[128-2*i-1]= 2*lps_state[i]+0;
158  h264_lps_state[2*i+1]=
159  ff_h264_mlps_state[128-2*i-2]= 2*lps_state[i]+1;
160  }else{
161  h264_lps_state[2*i+0]=
162  ff_h264_mlps_state[128-2*i-1]= 1;
163  h264_lps_state[2*i+1]=
164  ff_h264_mlps_state[128-2*i-2]= 0;
165  }
166  }
167  for(i=0; i< 63; i++){
169  }
170 }
171 
172 #ifdef TEST
173 #define SIZE 10240
174 
175 #include "libavutil/lfg.h"
176 #include "avcodec.h"
177 #include "cabac.h"
178 
179 static inline void put_cabac_bit(CABACContext *c, int b){
180  put_bits(&c->pb, 1, b);
181  for(;c->outstanding_count; c->outstanding_count--){
182  put_bits(&c->pb, 1, 1-b);
183  }
184 }
185 
186 static inline void renorm_cabac_encoder(CABACContext *c){
187  while(c->range < 0x100){
188  //FIXME optimize
189  if(c->low<0x100){
190  put_cabac_bit(c, 0);
191  }else if(c->low<0x200){
192  c->outstanding_count++;
193  c->low -= 0x100;
194  }else{
195  put_cabac_bit(c, 1);
196  c->low -= 0x200;
197  }
198 
199  c->range+= c->range;
200  c->low += c->low;
201  }
202 }
203 
204 static void put_cabac(CABACContext *c, uint8_t * const state, int bit){
205  int RangeLPS= ff_h264_lps_range[2*(c->range&0xC0) + *state];
206 
207  if(bit == ((*state)&1)){
208  c->range -= RangeLPS;
210  }else{
211  c->low += c->range - RangeLPS;
212  c->range = RangeLPS;
214  }
215 
216  renorm_cabac_encoder(c);
217 }
218 
219 /**
220  * @param bit 0 -> write zero bit, !=0 write one bit
221  */
222 static void put_cabac_bypass(CABACContext *c, int bit){
223  c->low += c->low;
224 
225  if(bit){
226  c->low += c->range;
227  }
228 //FIXME optimize
229  if(c->low<0x200){
230  put_cabac_bit(c, 0);
231  }else if(c->low<0x400){
232  c->outstanding_count++;
233  c->low -= 0x200;
234  }else{
235  put_cabac_bit(c, 1);
236  c->low -= 0x400;
237  }
238 }
239 
240 /**
241  *
242  * @return the number of bytes written
243  */
244 static int put_cabac_terminate(CABACContext *c, int bit){
245  c->range -= 2;
246 
247  if(!bit){
248  renorm_cabac_encoder(c);
249  }else{
250  c->low += c->range;
251  c->range= 2;
252 
253  renorm_cabac_encoder(c);
254 
255  av_assert0(c->low <= 0x1FF);
256  put_cabac_bit(c, c->low>>9);
257  put_bits(&c->pb, 2, ((c->low>>7)&3)|1);
258 
259  flush_put_bits(&c->pb); //FIXME FIXME FIXME XXX wrong
260  }
261 
262  return (put_bits_count(&c->pb)+7)>>3;
263 }
264 
265 int main(void){
266  CABACContext c;
267  uint8_t b[9*SIZE];
268  uint8_t r[9*SIZE];
269  int i;
270  uint8_t state[10]= {0};
271  AVLFG prng;
272 
273  av_lfg_init(&prng, 1);
274  ff_init_cabac_encoder(&c, b, SIZE);
276 
277  for(i=0; i<SIZE; i++){
278  if(2*i<SIZE) r[i] = av_lfg_get(&prng) % 7;
279  else r[i] = (i>>8)&1;
280  }
281 
282  for(i=0; i<SIZE; i++){
284  put_cabac_bypass(&c, r[i]&1);
285 STOP_TIMER("put_cabac_bypass")
286  }
287 
288  for(i=0; i<SIZE; i++){
290  put_cabac(&c, state, r[i]&1);
291 STOP_TIMER("put_cabac")
292  }
293 
294  put_cabac_terminate(&c, 1);
295 
296  ff_init_cabac_decoder(&c, b, SIZE);
297 
298  memset(state, 0, sizeof(state));
299 
300  for(i=0; i<SIZE; i++){
302  if( (r[i]&1) != get_cabac_bypass(&c) )
303  av_log(NULL, AV_LOG_ERROR, "CABAC bypass failure at %d\n", i);
304 STOP_TIMER("get_cabac_bypass")
305  }
306 
307  for(i=0; i<SIZE; i++){
309  if( (r[i]&1) != get_cabac(&c, state) )
310  av_log(NULL, AV_LOG_ERROR, "CABAC failure at %d\n", i);
311 STOP_TIMER("get_cabac")
312  }
313  if(!get_cabac_terminate(&c))
314  av_log(NULL, AV_LOG_ERROR, "where's the Terminator?\n");
315 
316  return 0;
317 }
318 
319 #endif /* TEST */
Definition: lfg.h:25
static const uint8_t lps_range[64][4]
Definition: cabac.c:57
const uint8_t * bytestream_end
Definition: cabac.h:48
static uint8_t *const ff_h264_lps_range
static uint8_t *const ff_h264_mlps_state
uint8_t ff_h264_cabac_tables[512+4 *2 *64+4 *64+63]
Definition: cabac.c:34
static int av_unused get_cabac(CABACContext *c, uint8_t *const state)
#define av_assert0(cond)
assert() equivalent, that is always enabled.
Definition: avassert.h:37
const uint8_t * bytestream
Definition: cabac.h:47
static uint8_t h264_mps_state[2 *64]
Definition: cabac.c:77
uint8_t
static uint8_t h264_lps_state[2 *64]
Definition: cabac.c:76
#define SIZE
Definition: golomb-test.c:31
#define b
Definition: input.c:42
bitstream reader API header.
const char * r
Definition: vf_curves.c:94
void av_log(void *avcl, int level, const char *fmt,...)
Definition: log.c:246
void ff_init_cabac_states(void)
Definition: cabac.c:140
static void put_bits(J2kEncoderContext *s, int val, int n)
put n times val bit
Definition: j2kenc.c:160
static int put_bits_count(PutBitContext *s)
Definition: put_bits.h:73
const uint8_t * bytestream_start
Definition: cabac.h:46
Context Adaptive Binary Arithmetic Coder inline functions.
void ff_init_cabac_encoder(CABACContext *c, uint8_t *buf, int buf_size)
Definition: cabac.c:112
static int av_unused get_cabac_terminate(CABACContext *c)
static const uint8_t last_coeff_flag_offset_8x8[63]
Definition: cabac.c:101
NULL
Definition: eval.c:55
int bit_left
Definition: put_bits.h:43
#define START_TIMER
Definition: timer.h:74
int outstanding_count
Definition: cabac.h:45
#define AV_LOG_ERROR
Something went wrong and cannot losslessly be recovered.
Definition: log.h:148
static unsigned int av_lfg_get(AVLFG *c)
Get the next random unsigned 32-bit number using an ALFG.
Definition: lfg.h:38
void * buf
Definition: avisynth_c.h:594
static const uint8_t mps_state[64]
Definition: cabac.c:79
int range
Definition: cabac.h:44
synthesis window for stochastic i
av_cold void av_lfg_init(AVLFG *c, unsigned int seed)
Definition: lfg.c:30
PutBitContext pb
Definition: cabac.h:49
static uint32_t state
Definition: trasher.c:27
static const uint8_t lps_state[64]
Definition: cabac.c:90
static int av_unused get_cabac_bypass(CABACContext *c)
int low
Definition: cabac.h:43
static void flush_put_bits(PutBitContext *s)
Pad the end of the output stream with zeros.
Definition: put_bits.h:81
common internal and external API header
static double c[64]
static void init_put_bits(PutBitContext *s, uint8_t *buffer, int buffer_size)
Initialize the PutBitContext s.
Definition: put_bits.h:54
#define STOP_TIMER(id)
Definition: timer.h:75
void ff_init_cabac_decoder(CABACContext *c, const uint8_t *buf, int buf_size)
Definition: cabac.c:125
static uint8_t *const ff_h264_last_coeff_flag_offset_8x8
int main(int argc, char **argv)
Definition: main.c:22
Context Adaptive Binary Arithmetic Coder.