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 "libavutil/timer.h"
  31 #include "get_bits.h"
  32 #include "cabac.h"
  33 #include "cabac_functions.h"
  34
  35 const 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     // LPS range
  57     -128,    -128,    -128,    -128,    -128,    -128,    123,     123,
  58     116,     116,     111,     111,     105,     105,     100,     100,
  59     95,      95,      90,      90,      85,      85,      81,      81,
  60     77,      77,      73,      73,      69,      69,      66,      66,
  61     62,      62,      59,      59,      56,      56,      53,      53,
  62     51,      51,      48,      48,      46,      46,      43,      43,
  63     41,      41,      39,      39,      37,      37,      35,      35,
  64     33,      33,      32,      32,      30,      30,      29,      29,
  65     27,      27,      26,      26,      24,      24,      23,      23,
  66     22,      22,      21,      21,      20,      20,      19,      19,
  67     18,      18,      17,      17,      16,      16,      15,      15,
  68     14,      14,      14,      14,      13,      13,      12,      12,
  69     12,      12,      11,      11,      11,      11,      10,      10,
  70     10,      10,      9,       9,       9,       9,       8,       8,
  71     8,       8,       7,       7,       7,       7,       7,       7,
  72     6,       6,       6,       6,       6,       6,       2,       2,
  73     -80,     -80,     -89,     -89,     -98,     -98,     -106,    -106,
  74     -114,    -114,    -121,    -121,    -128,    -128,    122,     122,
  75     116,     116,     110,     110,     104,     104,     99,      99,
  76     94,      94,      89,      89,      85,      85,      80,      80,
  77     76,      76,      72,      72,      69,      69,      65,      65,
  78     62,      62,      59,      59,      56,      56,      53,      53,
  79     50,      50,      48,      48,      45,      45,      43,      43,
  80     41,      41,      39,      39,      37,      37,      35,      35,
  81     33,      33,      31,      31,      30,      30,      28,      28,
  82     27,      27,      26,      26,      24,      24,      23,      23,
  83     22,      22,      21,      21,      20,      20,      19,      19,
  84     18,      18,      17,      17,      16,      16,      15,      15,
  85     14,      14,      14,      14,      13,      13,      12,      12,
  86     12,      12,      11,      11,      11,      11,      10,      10,
  87     9,       9,       9,       9,       9,       9,       8,       8,
  88     8,       8,       7,       7,       7,       7,       2,       2,
  89     -48,     -48,     -59,     -59,     -69,     -69,     -78,     -78,
  90     -87,     -87,     -96,     -96,     -104,    -104,    -112,    -112,
  91     -119,    -119,    -126,    -126,    123,     123,     117,     117,
  92     111,     111,     105,     105,     100,     100,     95,      95,
  93     90,      90,      86,      86,      81,      81,      77,      77,
  94     73,      73,      69,      69,      66,      66,      63,      63,
  95     59,      59,      56,      56,      54,      54,      51,      51,
  96     48,      48,      46,      46,      43,      43,      41,      41,
  97     39,      39,      37,      37,      35,      35,      33,      33,
  98     32,      32,      30,      30,      29,      29,      27,      27,
  99     26,      26,      25,      25,      23,      23,      22,      22,
 100     21,      21,      20,      20,      19,      19,      18,      18,
 101     17,      17,      16,      16,      15,      15,      15,      15,
 102     14,      14,      13,      13,      12,      12,      12,      12,
 103     11,      11,      11,      11,      10,      10,      10,      10,
 104     9,       9,       9,       9,       8,       8,       2,       2,
 105     -16,     -16,     -29,     -29,     -40,     -40,     -51,     -51,
 106     -61,     -61,     -71,     -71,     -81,     -81,     -90,     -90,
 107     -98,     -98,     -106,    -106,    -114,    -114,    -121,    -121,
 108     -128,    -128,    122,     122,     116,     116,     110,     110,
 109     104,     104,     99,      99,      94,      94,      89,      89,
 110     85,      85,      80,      80,      76,      76,      72,      72,
 111     69,      69,      65,      65,      62,      62,      59,      59,
 112     56,      56,      53,      53,      50,      50,      48,      48,
 113     45,      45,      43,      43,      41,      41,      39,      39,
 114     37,      37,      35,      35,      33,      33,      31,      31,
 115     30,      30,      28,      28,      27,      27,      25,      25,
 116     24,      24,      23,      23,      22,      22,      21,      21,
 117     20,      20,      19,      19,      18,      18,      17,      17,
 118     16,      16,      15,      15,      14,      14,      14,      14,
 119     13,      13,      12,      12,      12,      12,      11,      11,
 120     11,      11,      10,      10,      9,       9,       2,       2,
 121     // mlps state
 122     127,     126,     77,      76,      77,      76,      75,      74,
 123     75,      74,      75,      74,      73,      72,      73,      72,
 124     73,      72,      71,      70,      71,      70,      71,      70,
 125     69,      68,      69,      68,      67,      66,      67,      66,
 126     67,      66,      65,      64,      65,      64,      63,      62,
 127     61,      60,      61,      60,      61,      60,      59,      58,
 128     59,      58,      57,      56,      55,      54,      55,      54,
 129     53,      52,      53,      52,      51,      50,      49,      48,
 130     49,      48,      47,      46,      45,      44,      45,      44,
 131     43,      42,      43,      42,      39,      38,      39,      38,
 132     37,      36,      37,      36,      33,      32,      33,      32,
 133     31,      30,      31,      30,      27,      26,      27,      26,
 134     25,      24,      23,      22,      23,      22,      19,      18,
 135     19,      18,      17,      16,      15,      14,      13,      12,
 136     11,      10,      9,       8,       9,       8,       5,       4,
 137     5,       4,       3,       2,       1,       0,       0,       1,
 138     2,       3,       4,       5,       6,       7,       8,       9,
 139     10,      11,      12,      13,      14,      15,      16,      17,
 140     18,      19,      20,      21,      22,      23,      24,      25,
 141     26,      27,      28,      29,      30,      31,      32,      33,
 142     34,      35,      36,      37,      38,      39,      40,      41,
 143     42,      43,      44,      45,      46,      47,      48,      49,
 144     50,      51,      52,      53,      54,      55,      56,      57,
 145     58,      59,      60,      61,      62,      63,      64,      65,
 146     66,      67,      68,      69,      70,      71,      72,      73,
 147     74,      75,      76,      77,      78,      79,      80,      81,
 148     82,      83,      84,      85,      86,      87,      88,      89,
 149     90,      91,      92,      93,      94,      95,      96,      97,
 150     98,      99,      100,     101,     102,     103,     104,     105,
 151     106,     107,     108,     109,     110,     111,     112,     113,
 152     114,     115,     116,     117,     118,     119,     120,     121,
 153     122,     123,     124,     125,     124,     125,     126,     127,
 154     // last_coeff_flag_offset_8x8
 155     0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 156     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
 157     3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
 158     5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8
 159 };
 160
 161 /**
 162  * @param buf_size size of buf in bits
 163  */
 164 void ff_init_cabac_encoder(CABACContext *c, uint8_t *buf, int buf_size){
 165     init_put_bits(&c->pb, buf, buf_size);
 166
 167     c->low= 0;
 168     c->range= 0x1FE;
 169     c->outstanding_count= 0;
 170     c->pb.bit_left++; //avoids firstBitFlag
 171 }
 172
 173 /**
 174  *
 175  * @param buf_size size of buf in bits
 176  */
 177 int ff_init_cabac_decoder(CABACContext *c, const uint8_t *buf, int buf_size){
 178     c->bytestream_start=
 179     c->bytestream= buf;
 180     c->bytestream_end= buf + buf_size;
 181
 182 #if CABAC_BITS == 16
 183     c->low =  (*c->bytestream++)<<18;
 184     c->low+=  (*c->bytestream++)<<10;
 185     // Keep our fetches on a 2-byte boundry as this should avoid ever having to
 186     // do unaligned loads if the compiler (or asm) optimises the double byte
 187     // load into a single instruction
 188     if(((uintptr_t)c->bytestream & 1) == 0) {
 189         c->low += (1 << 9);
 190     }
 191     else {
 192         c->low += ((*c->bytestream++) << 2) + 2;
 193     }
 194 #else
 195     c->low =  (*c->bytestream++)<<10;
 196     c->low+= ((*c->bytestream++)<<2) + 2;
 197 #endif
 198     c->range= 0x1FE;
 199     if ((c->range<<(CABAC_BITS+1)) < c->low)
 200         return AVERROR_INVALIDDATA;
 201     return 0;
 202 }
 203
 204 #ifdef TEST
 205 #define SIZE 10240
 206
 207 #include "libavutil/lfg.h"
 208 #include "avcodec.h"
 209
 210 static inline void put_cabac_bit(CABACContext *c, int b){
 211     put_bits(&c->pb, 1, b);
 212     for(;c->outstanding_count; c->outstanding_count--){
 213         put_bits(&c->pb, 1, 1-b);
 214     }
 215 }
 216
 217 static inline void renorm_cabac_encoder(CABACContext *c){
 218     while(c->range < 0x100){
 219         //FIXME optimize
 220         if(c->low<0x100){
 221             put_cabac_bit(c, 0);
 222         }else if(c->low<0x200){
 223             c->outstanding_count++;
 224             c->low -= 0x100;
 225         }else{
 226             put_cabac_bit(c, 1);
 227             c->low -= 0x200;
 228         }
 229
 230         c->range+= c->range;
 231         c->low += c->low;
 232     }
 233 }
 234
 235 static void put_cabac(CABACContext *c, uint8_t * const state, int bit){
 236     int RangeLPS= ff_h264_lps_range[2*(c->range&0xC0) + *state];
 237
 238     if(bit == ((*state)&1)){
 239         c->range -= RangeLPS;
 240         *state    = ff_h264_mlps_state[128 + *state];
 241     }else{
 242         c->low += c->range - RangeLPS;
 243         c->range = RangeLPS;
 244         *state= ff_h264_mlps_state[127 - *state];
 245     }
 246
 247     renorm_cabac_encoder(c);
 248 }
 249
 250 /**
 251  * @param bit 0 -> write zero bit, !=0 write one bit
 252  */
 253 static void put_cabac_bypass(CABACContext *c, int bit){
 254     c->low += c->low;
 255
 256     if(bit){
 257         c->low += c->range;
 258     }
 259 //FIXME optimize
 260     if(c->low<0x200){
 261         put_cabac_bit(c, 0);
 262     }else if(c->low<0x400){
 263         c->outstanding_count++;
 264         c->low -= 0x200;
 265     }else{
 266         put_cabac_bit(c, 1);
 267         c->low -= 0x400;
 268     }
 269 }
 270
 271 /**
 272  *
 273  * @return the number of bytes written
 274  */
 275 static int put_cabac_terminate(CABACContext *c, int bit){
 276     c->range -= 2;
 277
 278     if(!bit){
 279         renorm_cabac_encoder(c);
 280     }else{
 281         c->low += c->range;
 282         c->range= 2;
 283
 284         renorm_cabac_encoder(c);
 285
 286         av_assert0(c->low <= 0x1FF);
 287         put_cabac_bit(c, c->low>>9);
 288         put_bits(&c->pb, 2, ((c->low>>7)&3)|1);
 289
 290         flush_put_bits(&c->pb); //FIXME FIXME FIXME XXX wrong
 291     }
 292
 293     return (put_bits_count(&c->pb)+7)>>3;
 294 }
 295
 296 int main(void){
 297     CABACContext c;
 298     uint8_t b[9*SIZE];
 299     uint8_t r[9*SIZE];
 300     int i, ret = 0;
 301     uint8_t state[10]= {0};
 302     AVLFG prng;
 303
 304     av_lfg_init(&prng, 1);
 305     ff_init_cabac_encoder(&c, b, SIZE);
 306
 307     for(i=0; i<SIZE; i++){
 308         if(2*i<SIZE) r[i] = av_lfg_get(&prng) % 7;
 309         else         r[i] = (i>>8)&1;
 310     }
 311
 312     for(i=0; i<SIZE; i++){
 313         put_cabac_bypass(&c, r[i]&1);
 314     }
 315
 316     for(i=0; i<SIZE; i++){
 317         put_cabac(&c, state, r[i]&1);
 318     }
 319
 320     i= put_cabac_terminate(&c, 1);
 321     b[i++] = av_lfg_get(&prng);
 322     b[i  ] = av_lfg_get(&prng);
 323
 324     ff_init_cabac_decoder(&c, b, SIZE);
 325
 326     memset(state, 0, sizeof(state));
 327
 328     for(i=0; i<SIZE; i++){
 329         if( (r[i]&1) != get_cabac_bypass(&c) ) {
 330             av_log(NULL, AV_LOG_ERROR, "CABAC bypass failure at %d\n", i);
 331             ret = 1;
 332         }
 333     }
 334
 335     for(i=0; i<SIZE; i++){
 336         if( (r[i]&1) != get_cabac_noinline(&c, state) ) {
 337             av_log(NULL, AV_LOG_ERROR, "CABAC failure at %d\n", i);
 338             ret = 1;
 339         }
 340     }
 341     if(!get_cabac_terminate(&c)) {
 342         av_log(NULL, AV_LOG_ERROR, "where's the Terminator?\n");
 343         ret = 1;
 344     }
 345
 346     return ret;
 347 }
 348
 349 #endif /* TEST */