FFmpeg
 All Data Structures 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 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(){
141  int i, j;
142 
143  for(i=0; i<64; i++){
144  for(j=0; j<4; j++){ //FIXME check if this is worth the 1 shift we save
145  ff_h264_lps_range[j*2*64+2*i+0]=
146  ff_h264_lps_range[j*2*64+2*i+1]= lps_range[i][j];
147  }
148 
149  ff_h264_mlps_state[128+2*i+0]=
150  h264_mps_state[2 * i + 0] = 2 * mps_state[i] + 0;
151  ff_h264_mlps_state[128+2*i+1]=
152  h264_mps_state[2 * i + 1] = 2 * mps_state[i] + 1;
153 
154  if( i ){
155  h264_lps_state[2*i+0]=
156  ff_h264_mlps_state[128-2*i-1]= 2*lps_state[i]+0;
157  h264_lps_state[2*i+1]=
158  ff_h264_mlps_state[128-2*i-2]= 2*lps_state[i]+1;
159  }else{
160  h264_lps_state[2*i+0]=
161  ff_h264_mlps_state[128-2*i-1]= 1;
162  h264_lps_state[2*i+1]=
163  ff_h264_mlps_state[128-2*i-2]= 0;
164  }
165  }
166  for(i=0; i< 63; i++){
167  ff_h264_last_coeff_flag_offset_8x8[i] = last_coeff_flag_offset_8x8[i];
168  }
169 }
170 
171 #ifdef TEST
172 #define SIZE 10240
173 
174 #include "libavutil/lfg.h"
175 #include "avcodec.h"
176 #include "cabac.h"
177 
178 static inline void put_cabac_bit(CABACContext *c, int b){
179  put_bits(&c->pb, 1, b);
180  for(;c->outstanding_count; c->outstanding_count--){
181  put_bits(&c->pb, 1, 1-b);
182  }
183 }
184 
185 static inline void renorm_cabac_encoder(CABACContext *c){
186  while(c->range < 0x100){
187  //FIXME optimize
188  if(c->low<0x100){
189  put_cabac_bit(c, 0);
190  }else if(c->low<0x200){
191  c->outstanding_count++;
192  c->low -= 0x100;
193  }else{
194  put_cabac_bit(c, 1);
195  c->low -= 0x200;
196  }
197 
198  c->range+= c->range;
199  c->low += c->low;
200  }
201 }
202 
203 static void put_cabac(CABACContext *c, uint8_t * const state, int bit){
204  int RangeLPS= ff_h264_lps_range[2*(c->range&0xC0) + *state];
205 
206  if(bit == ((*state)&1)){
207  c->range -= RangeLPS;
208  *state = h264_mps_state[*state];
209  }else{
210  c->low += c->range - RangeLPS;
211  c->range = RangeLPS;
212  *state= h264_lps_state[*state];
213  }
214 
215  renorm_cabac_encoder(c);
216 }
217 
218 /**
219  * @param bit 0 -> write zero bit, !=0 write one bit
220  */
221 static void put_cabac_bypass(CABACContext *c, int bit){
222  c->low += c->low;
223 
224  if(bit){
225  c->low += c->range;
226  }
227 //FIXME optimize
228  if(c->low<0x200){
229  put_cabac_bit(c, 0);
230  }else if(c->low<0x400){
231  c->outstanding_count++;
232  c->low -= 0x200;
233  }else{
234  put_cabac_bit(c, 1);
235  c->low -= 0x400;
236  }
237 }
238 
239 /**
240  *
241  * @return the number of bytes written
242  */
243 static int put_cabac_terminate(CABACContext *c, int bit){
244  c->range -= 2;
245 
246  if(!bit){
247  renorm_cabac_encoder(c);
248  }else{
249  c->low += c->range;
250  c->range= 2;
251 
252  renorm_cabac_encoder(c);
253 
254  av_assert0(c->low <= 0x1FF);
255  put_cabac_bit(c, c->low>>9);
256  put_bits(&c->pb, 2, ((c->low>>7)&3)|1);
257 
258  flush_put_bits(&c->pb); //FIXME FIXME FIXME XXX wrong
259  }
260 
261  return (put_bits_count(&c->pb)+7)>>3;
262 }
263 
264 int main(void){
265  CABACContext c;
266  uint8_t b[9*SIZE];
267  uint8_t r[9*SIZE];
268  int i;
269  uint8_t state[10]= {0};
270  AVLFG prng;
271 
272  av_lfg_init(&prng, 1);
273  ff_init_cabac_encoder(&c, b, SIZE);
274  ff_init_cabac_states();
275 
276  for(i=0; i<SIZE; i++){
277  if(2*i<SIZE) r[i] = av_lfg_get(&prng) % 7;
278  else r[i] = (i>>8)&1;
279  }
280 
281  for(i=0; i<SIZE; i++){
282 START_TIMER
283  put_cabac_bypass(&c, r[i]&1);
284 STOP_TIMER("put_cabac_bypass")
285  }
286 
287  for(i=0; i<SIZE; i++){
288 START_TIMER
289  put_cabac(&c, state, r[i]&1);
290 STOP_TIMER("put_cabac")
291  }
292 
293  put_cabac_terminate(&c, 1);
294 
295  ff_init_cabac_decoder(&c, b, SIZE);
296 
297  memset(state, 0, sizeof(state));
298 
299  for(i=0; i<SIZE; i++){
300 START_TIMER
301  if( (r[i]&1) != get_cabac_bypass(&c) )
302  av_log(NULL, AV_LOG_ERROR, "CABAC bypass failure at %d\n", i);
303 STOP_TIMER("get_cabac_bypass")
304  }
305 
306  for(i=0; i<SIZE; i++){
307 START_TIMER
308  if( (r[i]&1) != get_cabac(&c, state) )
309  av_log(NULL, AV_LOG_ERROR, "CABAC failure at %d\n", i);
310 STOP_TIMER("get_cabac")
311  }
312  if(!get_cabac_terminate(&c))
313  av_log(NULL, AV_LOG_ERROR, "where's the Terminator?\n");
314 
315  return 0;
316 }
317 
318 #endif /* TEST */
Generated on Sat May 25 2013 03:58:32 for FFmpeg by   doxygen 1.8.2