2 * H.26L/H.264/AVC/JVT/14496-10/... encoder/decoder
3 * Copyright (c) 2003 Michael Niedermayer <michaelni@gmx.at>
5 * This file is part of FFmpeg.
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.
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.
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
24 * Context Adaptive Binary Arithmetic Coder.
29 #include "libavutil/common.h"
30 #include "libavutil/timer.h"
33 #include "cabac_functions.h"
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,
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},
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,
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,
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
108 * @param buf_size size of buf in bits
110 void ff_init_cabac_encoder(CABACContext *c, uint8_t *buf, int buf_size){
111 init_put_bits(&c->pb, buf, buf_size);
115 c->outstanding_count= 0;
116 c->pb.bit_left++; //avoids firstBitFlag
121 * @param buf_size size of buf in bits
123 void ff_init_cabac_decoder(CABACContext *c, const uint8_t *buf, int buf_size){
126 c->bytestream_end= buf + buf_size;
129 c->low = (*c->bytestream++)<<18;
130 c->low+= (*c->bytestream++)<<10;
132 c->low = (*c->bytestream++)<<10;
134 c->low+= ((*c->bytestream++)<<2) + 2;
138 void ff_init_cabac_states(void)
141 static int initialized = 0;
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];
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;
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;
158 ff_h264_mlps_state[128-2*i-1]= 1;
159 ff_h264_mlps_state[128-2*i-2]= 0;
162 for(i=0; i< 63; i++){
163 ff_h264_last_coeff_flag_offset_8x8[i] = last_coeff_flag_offset_8x8[i];
172 #include "libavutil/lfg.h"
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);
182 static inline void renorm_cabac_encoder(CABACContext *c){
183 while(c->range < 0x100){
187 }else if(c->low<0x200){
188 c->outstanding_count++;
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];
203 if(bit == ((*state)&1)){
204 c->range -= RangeLPS;
205 *state = ff_h264_mlps_state[128 + *state];
207 c->low += c->range - RangeLPS;
209 *state= ff_h264_mlps_state[127 - *state];
212 renorm_cabac_encoder(c);
216 * @param bit 0 -> write zero bit, !=0 write one bit
218 static void put_cabac_bypass(CABACContext *c, int bit){
227 }else if(c->low<0x400){
228 c->outstanding_count++;
238 * @return the number of bytes written
240 static int put_cabac_terminate(CABACContext *c, int bit){
244 renorm_cabac_encoder(c);
249 renorm_cabac_encoder(c);
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);
255 flush_put_bits(&c->pb); //FIXME FIXME FIXME XXX wrong
258 return (put_bits_count(&c->pb)+7)>>3;
266 uint8_t state[10]= {0};
269 av_lfg_init(&prng, 1);
270 ff_init_cabac_encoder(&c, b, SIZE);
271 ff_init_cabac_states();
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;
278 for(i=0; i<SIZE; i++){
280 put_cabac_bypass(&c, r[i]&1);
281 STOP_TIMER("put_cabac_bypass")
284 for(i=0; i<SIZE; i++){
286 put_cabac(&c, state, r[i]&1);
287 STOP_TIMER("put_cabac")
290 put_cabac_terminate(&c, 1);
292 ff_init_cabac_decoder(&c, b, SIZE);
294 memset(state, 0, sizeof(state));
296 for(i=0; i<SIZE; i++){
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")
303 for(i=0; i<SIZE; i++){
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")
309 if(!get_cabac_terminate(&c))
310 av_log(NULL, AV_LOG_ERROR, "where's the Terminator?\n");