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 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;
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);
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 */