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 
101 static const uint8_t last_coeff_flag_offset_8x8[63] = {
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  */
112 void ff_init_cabac_encoder(CABACContext *c, uint8_t *buf, int buf_size){
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 
140 void ff_init_cabac_states(void)
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++){
168  ff_h264_last_coeff_flag_offset_8x8[i] = last_coeff_flag_offset_8x8[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;
209  *state = h264_mps_state[*state];
210  }else{
211  c->low += c->range - RangeLPS;
212  c->range = RangeLPS;
213  *state= h264_lps_state[*state];
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);
275  ff_init_cabac_states();
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++){
283 START_TIMER
284  put_cabac_bypass(&c, r[i]&1);
285 STOP_TIMER("put_cabac_bypass")
286  }
287 
288  for(i=0; i<SIZE; i++){
289 START_TIMER
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++){
301 START_TIMER
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++){
308 START_TIMER
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 */
AVLFG
Definition: lfg.h:25
av_lfg_init
void av_lfg_init(AVLFG *c, unsigned int seed)
Definition: lfg.c:30
lps_range
static const uint8_t lps_range[64][4]
Definition: cabac.c:57
CABACContext::bytestream_end
const uint8_t * bytestream_end
Definition: cabac.h:48
ff_h264_lps_range
static uint8_t *const ff_h264_lps_range
Definition: cabac_functions.h:41
ff_h264_mlps_state
static uint8_t *const ff_h264_mlps_state
Definition: cabac_functions.h:42
ff_h264_cabac_tables
uint8_t ff_h264_cabac_tables[512+4 *2 *64+4 *64+63]
Definition: cabac.c:34
get_cabac
static int av_unused get_cabac(CABACContext *c, uint8_t *const state)
Definition: cabac_functions.h:110
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:47
h264_mps_state
static uint8_t h264_mps_state[2 *64]
Definition: cabac.c:77
h264_lps_state
static uint8_t h264_lps_state[2 *64]
Definition: cabac.c:76
SIZE
#define SIZE
Definition: golomb-test.c:31
b
#define b
Definition: input.c:42
get_bits.h
bitstream reader API header.
r
const char * r
Definition: vf_curves.c:94
av_log
void av_log(void *avcl, int level, const char *fmt,...)
Send the specified message to the log if the level is less than or equal to the current av_log_level...
Definition: log.c:246
ff_init_cabac_states
void ff_init_cabac_states(void)
Definition: cabac.c:140
put_bits
static void put_bits(J2kEncoderContext *s, int val, int n)
put n times val bit
Definition: j2kenc.c:160
put_bits_count
static int put_bits_count(PutBitContext *s)
Definition: put_bits.h:73
CABACContext::bytestream_start
const uint8_t * bytestream_start
Definition: cabac.h:46
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:112
get_cabac_terminate
static int av_unused get_cabac_terminate(CABACContext *c)
Definition: cabac_functions.h:152
last_coeff_flag_offset_8x8
static const uint8_t last_coeff_flag_offset_8x8[63]
Definition: cabac.c:101
NULL
NULL
Definition: eval.c:55
PutBitContext::bit_left
int bit_left
Definition: put_bits.h:43
START_TIMER
#define START_TIMER
Definition: timer.h:74
CABACContext::outstanding_count
int outstanding_count
Definition: cabac.h:45
AV_LOG_ERROR
#define AV_LOG_ERROR
Something went wrong and cannot losslessly be recovered.
Definition: log.h:148
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:594
mps_state
static const uint8_t mps_state[64]
Definition: cabac.c:79
CABACContext::range
int range
Definition: cabac.h:44
i
synthesis window for stochastic i
Definition: code Kat/hpsmodel.m:34
CABACContext::pb
PutBitContext pb
Definition: cabac.h:49
state
static uint32_t state
Definition: trasher.c:27
lps_state
static const uint8_t lps_state[64]
Definition: cabac.c:90
get_cabac_bypass
static int av_unused get_cabac_bypass(CABACContext *c)
Definition: cabac_functions.h:114
CABACContext::low
int low
Definition: cabac.h:43
flush_put_bits
static void flush_put_bits(PutBitContext *s)
Pad the end of the output stream with zeros.
Definition: put_bits.h:81
common.h
common internal and external API header
c
static double c[64]
Definition: vsrc_mptestsrc.c:88
init_put_bits
static void init_put_bits(PutBitContext *s, uint8_t *buffer, int buffer_size)
Initialize the PutBitContext s.
Definition: put_bits.h:54
STOP_TIMER
#define STOP_TIMER(id)
Definition: timer.h:75
ff_init_cabac_decoder
void ff_init_cabac_decoder(CABACContext *c, const uint8_t *buf, int buf_size)
Definition: cabac.c:125
ff_h264_last_coeff_flag_offset_8x8
static uint8_t *const ff_h264_last_coeff_flag_offset_8x8
Definition: cabac_functions.h:43
main
int main(int argc, char **argv)
Definition: main.c:22
cabac.h
Context Adaptive Binary Arithmetic Coder.
Generated on Tue May 7 2024 06:51:45 for FFmpeg by   doxygen 1.8.11