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 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(void)
 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++){
 168       ff_h264_last_coeff_flag_offset_8x8[i] = last_coeff_flag_offset_8x8[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);
 275     ff_init_cabac_states();
 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++){
 283 START_TIMER
 284         put_cabac_bypass(&c, r[i]&1);
 285 STOP_TIMER("put_cabac_bypass")
 286     }
 287
 288     for(i=0; i<SIZE; i++){
 289 START_TIMER
 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++){
 301 START_TIMER
 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++){
 308 START_TIMER
 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 */