src/third_party/ffmpeg/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 "libavutil/timer.h"
  31 #include "get_bits.h"
  32 #include "cabac.h"
  33 #include "cabac_functions.h"
  34
  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,
  56 };
  57
  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},
  75 };
  76
  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,
  86 };
  87
  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,
  97 };
  98
  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
 104 };
 105
 106 /**
 107  *
 108  * @param buf_size size of buf in bits
 109  */
 110 void ff_init_cabac_encoder(CABACContext *c, uint8_t *buf, int buf_size){
 111     init_put_bits(&c->pb, buf, buf_size);
 112
 113     c->low= 0;
 114     c->range= 0x1FE;
 115     c->outstanding_count= 0;
 116     c->pb.bit_left++; //avoids firstBitFlag
 117 }
 118
 119 /**
 120  *
 121  * @param buf_size size of buf in bits
 122  */
 123 void ff_init_cabac_decoder(CABACContext *c, const uint8_t *buf, int buf_size){
 124     c->bytestream_start=
 125     c->bytestream= buf;
 126     c->bytestream_end= buf + buf_size;
 127
 128 #if CABAC_BITS == 16
 129     c->low =  (*c->bytestream++)<<18;
 130     c->low+=  (*c->bytestream++)<<10;
 131 #else
 132     c->low =  (*c->bytestream++)<<10;
 133 #endif
 134     c->low+= ((*c->bytestream++)<<2) + 2;
 135     c->range= 0x1FE;
 136 }
 137
 138 void ff_init_cabac_states(void)
 139 {
 140     int i, j;
 141     static int initialized = 0;
 142
 143     if (initialized)
 144         return;
 145
 146     for(i=0; i<64; i++){
 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];
 150         }
 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;
 153
 154         if( i ){
 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;
 157         }else{
 158             ff_h264_mlps_state[128-2*i-1]= 1;
 159             ff_h264_mlps_state[128-2*i-2]= 0;
 160         }
 161     }
 162     for(i=0; i< 63; i++){
 163       ff_h264_last_coeff_flag_offset_8x8[i] = last_coeff_flag_offset_8x8[i];
 164     }
 165
 166     initialized = 1;
 167 }
 168
 169 #ifdef TEST
 170 #define SIZE 10240
 171
 172 #include "libavutil/lfg.h"
 173 #include "avcodec.h"
 174
 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);
 179     }
 180 }
 181
 182 static inline void renorm_cabac_encoder(CABACContext *c){
 183     while(c->range < 0x100){
 184         //FIXME optimize
 185         if(c->low<0x100){
 186             put_cabac_bit(c, 0);
 187         }else if(c->low<0x200){
 188             c->outstanding_count++;
 189             c->low -= 0x100;
 190         }else{
 191             put_cabac_bit(c, 1);
 192             c->low -= 0x200;
 193         }
 194
 195         c->range+= c->range;
 196         c->low += c->low;
 197     }
 198 }
 199
 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];
 202
 203     if(bit == ((*state)&1)){
 204         c->range -= RangeLPS;
 205         *state    = ff_h264_mlps_state[128 + *state];
 206     }else{
 207         c->low += c->range - RangeLPS;
 208         c->range = RangeLPS;
 209         *state= ff_h264_mlps_state[127 - *state];
 210     }
 211
 212     renorm_cabac_encoder(c);
 213 }
 214
 215 /**
 216  * @param bit 0 -> write zero bit, !=0 write one bit
 217  */
 218 static void put_cabac_bypass(CABACContext *c, int bit){
 219     c->low += c->low;
 220
 221     if(bit){
 222         c->low += c->range;
 223     }
 224 //FIXME optimize
 225     if(c->low<0x200){
 226         put_cabac_bit(c, 0);
 227     }else if(c->low<0x400){
 228         c->outstanding_count++;
 229         c->low -= 0x200;
 230     }else{
 231         put_cabac_bit(c, 1);
 232         c->low -= 0x400;
 233     }
 234 }
 235
 236 /**
 237  *
 238  * @return the number of bytes written
 239  */
 240 static int put_cabac_terminate(CABACContext *c, int bit){
 241     c->range -= 2;
 242
 243     if(!bit){
 244         renorm_cabac_encoder(c);
 245     }else{
 246         c->low += c->range;
 247         c->range= 2;
 248
 249         renorm_cabac_encoder(c);
 250
 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);
 254
 255         flush_put_bits(&c->pb); //FIXME FIXME FIXME XXX wrong
 256     }
 257
 258     return (put_bits_count(&c->pb)+7)>>3;
 259 }
 260
 261 int main(void){
 262     CABACContext c;
 263     uint8_t b[9*SIZE];
 264     uint8_t r[9*SIZE];
 265     int i;
 266     uint8_t state[10]= {0};
 267     AVLFG prng;
 268
 269     av_lfg_init(&prng, 1);
 270     ff_init_cabac_encoder(&c, b, SIZE);
 271     ff_init_cabac_states();
 272
 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;
 276     }
 277
 278     for(i=0; i<SIZE; i++){
 279 START_TIMER
 280         put_cabac_bypass(&c, r[i]&1);
 281 STOP_TIMER("put_cabac_bypass")
 282     }
 283
 284     for(i=0; i<SIZE; i++){
 285 START_TIMER
 286         put_cabac(&c, state, r[i]&1);
 287 STOP_TIMER("put_cabac")
 288     }
 289
 290     put_cabac_terminate(&c, 1);
 291
 292     ff_init_cabac_decoder(&c, b, SIZE);
 293
 294     memset(state, 0, sizeof(state));
 295
 296     for(i=0; i<SIZE; i++){
 297 START_TIMER
 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")
 301     }
 302
 303     for(i=0; i<SIZE; i++){
 304 START_TIMER
 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")
 308     }
 309     if(!get_cabac_terminate(&c))
 310         av_log(NULL, AV_LOG_ERROR, "where's the Terminator?\n");
 311
 312     return 0;
 313 }
 314
 315 #endif /* TEST */