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