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(){
 141     int i, j;
 142
 143     for(i=0; i<64; i++){
 144         for(j=0; j<4; j++){ //FIXME check if this is worth the 1 shift we save
 145             ff_h264_lps_range[j*2*64+2*i+0]=
 146             ff_h264_lps_range[j*2*64+2*i+1]= lps_range[i][j];
 147         }
 148
 149         ff_h264_mlps_state[128+2*i+0]=
 150         h264_mps_state[2 * i + 0] = 2 * mps_state[i] + 0;
 151         ff_h264_mlps_state[128+2*i+1]=
 152         h264_mps_state[2 * i + 1] = 2 * mps_state[i] + 1;
 153
 154         if( i ){
 155             h264_lps_state[2*i+0]=
 156             ff_h264_mlps_state[128-2*i-1]= 2*lps_state[i]+0;
 157             h264_lps_state[2*i+1]=
 158             ff_h264_mlps_state[128-2*i-2]= 2*lps_state[i]+1;
 159         }else{
 160             h264_lps_state[2*i+0]=
 161             ff_h264_mlps_state[128-2*i-1]= 1;
 162             h264_lps_state[2*i+1]=
 163             ff_h264_mlps_state[128-2*i-2]= 0;
 164         }
 165     }
 166     for(i=0; i< 63; i++){
 167       ff_h264_last_coeff_flag_offset_8x8[i] = last_coeff_flag_offset_8x8[i];
 168     }
 169 }
 170
 171 #ifdef TEST
 172 #define SIZE 10240
 173
 174 #include "libavutil/lfg.h"
 175 #include "avcodec.h"
 176 #include "cabac.h"
 177
 178 static inline void put_cabac_bit(CABACContext *c, int b){
 179     put_bits(&c->pb, 1, b);
 180     for(;c->outstanding_count; c->outstanding_count--){
 181         put_bits(&c->pb, 1, 1-b);
 182     }
 183 }
 184
 185 static inline void renorm_cabac_encoder(CABACContext *c){
 186     while(c->range < 0x100){
 187         //FIXME optimize
 188         if(c->low<0x100){
 189             put_cabac_bit(c, 0);
 190         }else if(c->low<0x200){
 191             c->outstanding_count++;
 192             c->low -= 0x100;
 193         }else{
 194             put_cabac_bit(c, 1);
 195             c->low -= 0x200;
 196         }
 197
 198         c->range+= c->range;
 199         c->low += c->low;
 200     }
 201 }
 202
 203 static void put_cabac(CABACContext *c, uint8_t * const state, int bit){
 204     int RangeLPS= ff_h264_lps_range[2*(c->range&0xC0) + *state];
 205
 206     if(bit == ((*state)&1)){
 207         c->range -= RangeLPS;
 208         *state    = h264_mps_state[*state];
 209     }else{
 210         c->low += c->range - RangeLPS;
 211         c->range = RangeLPS;
 212         *state= h264_lps_state[*state];
 213     }
 214
 215     renorm_cabac_encoder(c);
 216 }
 217
 218 /**
 219  * @param bit 0 -> write zero bit, !=0 write one bit
 220  */
 221 static void put_cabac_bypass(CABACContext *c, int bit){
 222     c->low += c->low;
 223
 224     if(bit){
 225         c->low += c->range;
 226     }
 227 //FIXME optimize
 228     if(c->low<0x200){
 229         put_cabac_bit(c, 0);
 230     }else if(c->low<0x400){
 231         c->outstanding_count++;
 232         c->low -= 0x200;
 233     }else{
 234         put_cabac_bit(c, 1);
 235         c->low -= 0x400;
 236     }
 237 }
 238
 239 /**
 240  *
 241  * @return the number of bytes written
 242  */
 243 static int put_cabac_terminate(CABACContext *c, int bit){
 244     c->range -= 2;
 245
 246     if(!bit){
 247         renorm_cabac_encoder(c);
 248     }else{
 249         c->low += c->range;
 250         c->range= 2;
 251
 252         renorm_cabac_encoder(c);
 253
 254         av_assert0(c->low <= 0x1FF);
 255         put_cabac_bit(c, c->low>>9);
 256         put_bits(&c->pb, 2, ((c->low>>7)&3)|1);
 257
 258         flush_put_bits(&c->pb); //FIXME FIXME FIXME XXX wrong
 259     }
 260
 261     return (put_bits_count(&c->pb)+7)>>3;
 262 }
 263
 264 int main(void){
 265     CABACContext c;
 266     uint8_t b[9*SIZE];
 267     uint8_t r[9*SIZE];
 268     int i;
 269     uint8_t state[10]= {0};
 270     AVLFG prng;
 271
 272     av_lfg_init(&prng, 1);
 273     ff_init_cabac_encoder(&c, b, SIZE);
 274     ff_init_cabac_states();
 275
 276     for(i=0; i<SIZE; i++){
 277         if(2*i<SIZE) r[i] = av_lfg_get(&prng) % 7;
 278         else         r[i] = (i>>8)&1;
 279     }
 280
 281     for(i=0; i<SIZE; i++){
 282 START_TIMER
 283         put_cabac_bypass(&c, r[i]&1);
 284 STOP_TIMER("put_cabac_bypass")
 285     }
 286
 287     for(i=0; i<SIZE; i++){
 288 START_TIMER
 289         put_cabac(&c, state, r[i]&1);
 290 STOP_TIMER("put_cabac")
 291     }
 292
 293     put_cabac_terminate(&c, 1);
 294
 295     ff_init_cabac_decoder(&c, b, SIZE);
 296
 297     memset(state, 0, sizeof(state));
 298
 299     for(i=0; i<SIZE; i++){
 300 START_TIMER
 301         if( (r[i]&1) != get_cabac_bypass(&c) )
 302             av_log(NULL, AV_LOG_ERROR, "CABAC bypass failure at %d\n", i);
 303 STOP_TIMER("get_cabac_bypass")
 304     }
 305
 306     for(i=0; i<SIZE; i++){
 307 START_TIMER
 308         if( (r[i]&1) != get_cabac(&c, state) )
 309             av_log(NULL, AV_LOG_ERROR, "CABAC failure at %d\n", i);
 310 STOP_TIMER("get_cabac")
 311     }
 312     if(!get_cabac_terminate(&c))
 313         av_log(NULL, AV_LOG_ERROR, "where's the Terminator?\n");
 314
 315     return 0;
 316 }
 317
 318 #endif /* TEST */