git.sesse.net Git - ffmpeg/blob - libavcodec/cabac.c

   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(&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 */