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