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