git.sesse.net Git - ffmpeg/blob - libavcodec/cabac.h

   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 /**
  24  * @file cabac.h
  25  * Context Adaptive Binary Arithmetic Coder.
  26  */
  27
  28
  29 //#undef NDEBUG
  30 #include <assert.h>
  31
  32 #define CABAC_BITS 16
  33 #define CABAC_MASK ((1<<CABAC_BITS)-1)
  34
  35 typedef struct CABACContext{
  36     int low;
  37     int range;
  38     int outstanding_count;
  39 #ifdef STRICT_LIMITS
  40     int symCount;
  41 #endif
  42     uint8_t lps_range[2*65][4];   ///< rangeTabLPS
  43     uint8_t lps_state[2*64];      ///< transIdxLPS
  44     uint8_t mps_state[2*64];      ///< transIdxMPS
  45     const uint8_t *bytestream_start;
  46     const uint8_t *bytestream;
  47     const uint8_t *bytestream_end;
  48     PutBitContext pb;
  49 }CABACContext;
  50
  51 extern const uint8_t ff_h264_lps_range[64][4];
  52 extern const uint8_t ff_h264_mps_state[64];
  53 extern const uint8_t ff_h264_lps_state[64];
  54 extern const uint8_t ff_h264_norm_shift[256];
  55
  56
  57 void ff_init_cabac_encoder(CABACContext *c, uint8_t *buf, int buf_size);
  58 void ff_init_cabac_decoder(CABACContext *c, const uint8_t *buf, int buf_size);
  59 void ff_init_cabac_states(CABACContext *c, uint8_t const (*lps_range)[4],
  60                           uint8_t const *mps_state, uint8_t const *lps_state, int state_count);
  61
  62
  63 static inline void put_cabac_bit(CABACContext *c, int b){
  64     put_bits(&c->pb, 1, b);
  65     for(;c->outstanding_count; c->outstanding_count--){
  66         put_bits(&c->pb, 1, 1-b);
  67     }
  68 }
  69
  70 static inline void renorm_cabac_encoder(CABACContext *c){
  71     while(c->range < 0x100){
  72         //FIXME optimize
  73         if(c->low<0x100){
  74             put_cabac_bit(c, 0);
  75         }else if(c->low<0x200){
  76             c->outstanding_count++;
  77             c->low -= 0x100;
  78         }else{
  79             put_cabac_bit(c, 1);
  80             c->low -= 0x200;
  81         }
  82
  83         c->range+= c->range;
  84         c->low += c->low;
  85     }
  86 }
  87
  88 static void put_cabac(CABACContext *c, uint8_t * const state, int bit){
  89     int RangeLPS= c->lps_range[*state][c->range>>6];
  90
  91     if(bit == ((*state)&1)){
  92         c->range -= RangeLPS;
  93         *state= c->mps_state[*state];
  94     }else{
  95         c->low += c->range - RangeLPS;
  96         c->range = RangeLPS;
  97         *state= c->lps_state[*state];
  98     }
  99
 100     renorm_cabac_encoder(c);
 101
 102 #ifdef STRICT_LIMITS
 103     c->symCount++;
 104 #endif
 105 }
 106
 107 static void put_cabac_static(CABACContext *c, int RangeLPS, int bit){
 108     assert(c->range > RangeLPS);
 109
 110     if(!bit){
 111         c->range -= RangeLPS;
 112     }else{
 113         c->low += c->range - RangeLPS;
 114         c->range = RangeLPS;
 115     }
 116
 117     renorm_cabac_encoder(c);
 118
 119 #ifdef STRICT_LIMITS
 120     c->symCount++;
 121 #endif
 122 }
 123
 124 /**
 125  * @param bit 0 -> write zero bit, !=0 write one bit
 126  */
 127 static void put_cabac_bypass(CABACContext *c, int bit){
 128     c->low += c->low;
 129
 130     if(bit){
 131         c->low += c->range;
 132     }
 133 //FIXME optimize
 134     if(c->low<0x200){
 135         put_cabac_bit(c, 0);
 136     }else if(c->low<0x400){
 137         c->outstanding_count++;
 138         c->low -= 0x200;
 139     }else{
 140         put_cabac_bit(c, 1);
 141         c->low -= 0x400;
 142     }
 143
 144 #ifdef STRICT_LIMITS
 145     c->symCount++;
 146 #endif
 147 }
 148
 149 /**
 150  *
 151  * @return the number of bytes written
 152  */
 153 static int put_cabac_terminate(CABACContext *c, int bit){
 154     c->range -= 2;
 155
 156     if(!bit){
 157         renorm_cabac_encoder(c);
 158     }else{
 159         c->low += c->range;
 160         c->range= 2;
 161
 162         renorm_cabac_encoder(c);
 163
 164         assert(c->low <= 0x1FF);
 165         put_cabac_bit(c, c->low>>9);
 166         put_bits(&c->pb, 2, ((c->low>>7)&3)|1);
 167
 168         flush_put_bits(&c->pb); //FIXME FIXME FIXME XXX wrong
 169     }
 170
 171 #ifdef STRICT_LIMITS
 172     c->symCount++;
 173 #endif
 174
 175     return (put_bits_count(&c->pb)+7)>>3;
 176 }
 177
 178 /**
 179  * put (truncated) unary binarization.
 180  */
 181 static void put_cabac_u(CABACContext *c, uint8_t * state, int v, int max, int max_index, int truncated){
 182     int i;
 183
 184     assert(v <= max);
 185
 186 #if 1
 187     for(i=0; i<v; i++){
 188         put_cabac(c, state, 1);
 189         if(i < max_index) state++;
 190     }
 191     if(truncated==0 || v<max)
 192         put_cabac(c, state, 0);
 193 #else
 194     if(v <= max_index){
 195         for(i=0; i<v; i++){
 196             put_cabac(c, state+i, 1);
 197         }
 198         if(truncated==0 || v<max)
 199             put_cabac(c, state+i, 0);
 200     }else{
 201         for(i=0; i<=max_index; i++){
 202             put_cabac(c, state+i, 1);
 203         }
 204         for(; i<v; i++){
 205             put_cabac(c, state+max_index, 1);
 206         }
 207         if(truncated==0 || v<max)
 208             put_cabac(c, state+max_index, 0);
 209     }
 210 #endif
 211 }
 212
 213 /**
 214  * put unary exp golomb k-th order binarization.
 215  */
 216 static void put_cabac_ueg(CABACContext *c, uint8_t * state, int v, int max, int is_signed, int k, int max_index){
 217     int i;
 218
 219     if(v==0)
 220         put_cabac(c, state, 0);
 221     else{
 222         const int sign= v < 0;
 223
 224         if(is_signed) v= ABS(v);
 225
 226         if(v<max){
 227             for(i=0; i<v; i++){
 228                 put_cabac(c, state, 1);
 229                 if(i < max_index) state++;
 230             }
 231
 232             put_cabac(c, state, 0);
 233         }else{
 234             int m= 1<<k;
 235
 236             for(i=0; i<max; i++){
 237                 put_cabac(c, state, 1);
 238                 if(i < max_index) state++;
 239             }
 240
 241             v -= max;
 242             while(v >= m){ //FIXME optimize
 243                 put_cabac_bypass(c, 1);
 244                 v-= m;
 245                 m+= m;
 246             }
 247             put_cabac_bypass(c, 0);
 248             while(m>>=1){
 249                 put_cabac_bypass(c, v&m);
 250             }
 251         }
 252
 253         if(is_signed)
 254             put_cabac_bypass(c, sign);
 255     }
 256 }
 257
 258 static void refill(CABACContext *c){
 259     if(c->bytestream <= c->bytestream_end)
 260 #if CABAC_BITS == 16
 261         c->low+= (c->bytestream[0]<<9) + (c->bytestream[1]<<1);
 262 #else
 263         c->low+= c->bytestream[0]<<1;
 264 #endif
 265     c->low -= CABAC_MASK;
 266     c->bytestream+= CABAC_BITS/8;
 267 }
 268
 269 #if 0 /* all use commented */
 270 static void refill2(CABACContext *c){
 271     int i, x;
 272
 273     x= c->low ^ (c->low-1);
 274     i= 8 - ff_h264_norm_shift[x>>(CABAC_BITS+1)];
 275
 276     x= -CABAC_MASK;
 277
 278     if(c->bytestream < c->bytestream_end)
 279 #if CABAC_BITS == 16
 280         x+= (c->bytestream[0]<<9) + (c->bytestream[1]<<1);
 281 #else
 282         x+= c->bytestream[0]<<1;
 283 #endif
 284
 285     c->low += x<<i;
 286     c->bytestream+= CABAC_BITS/8;
 287 }
 288 #endif
 289
 290 static inline void renorm_cabac_decoder(CABACContext *c){
 291     while(c->range < (0x200 << CABAC_BITS)){
 292         c->range+= c->range;
 293         c->low+= c->low;
 294         if(!(c->low & CABAC_MASK))
 295             refill(c);
 296     }
 297 }
 298
 299 static inline void renorm_cabac_decoder_once(CABACContext *c){
 300 #ifdef ARCH_X86
 301     int temp;
 302 #if 0
 303     //P3:683
 304     asm(
 305         "lea -0x2000000(%0), %2     \n\t"
 306         "shr $31, %2                \n\t"  //FIXME 31->63 for x86-64
 307         "shl %%cl, %0               \n\t"
 308         "shl %%cl, %1               \n\t"
 309         : "+r"(c->range), "+r"(c->low), "+c"(temp)
 310     );
 311 #elif 0
 312     //P3:680
 313     asm(
 314         "cmp $0x2000000, %0         \n\t"
 315         "setb %%cl                  \n\t"  //FIXME 31->63 for x86-64
 316         "shl %%cl, %0               \n\t"
 317         "shl %%cl, %1               \n\t"
 318         : "+r"(c->range), "+r"(c->low), "+c"(temp)
 319     );
 320 #elif 1
 321     int temp2;
 322     //P3:665
 323     asm(
 324         "lea -0x2000000(%0), %%eax  \n\t"
 325         "cdq                        \n\t"
 326         "mov %0, %%eax              \n\t"
 327         "and %%edx, %0              \n\t"
 328         "and %1, %%edx              \n\t"
 329         "add %%eax, %0              \n\t"
 330         "add %%edx, %1              \n\t"
 331         : "+r"(c->range), "+r"(c->low), "+a"(temp), "+d"(temp2)
 332     );
 333 #elif 0
 334     int temp2;
 335     //P3:673
 336     asm(
 337         "cmp $0x2000000, %0         \n\t"
 338         "sbb %%edx, %%edx           \n\t"
 339         "mov %0, %%eax              \n\t"
 340         "and %%edx, %0              \n\t"
 341         "and %1, %%edx              \n\t"
 342         "add %%eax, %0              \n\t"
 343         "add %%edx, %1              \n\t"
 344         : "+r"(c->range), "+r"(c->low), "+a"(temp), "+d"(temp2)
 345     );
 346 #else
 347     int temp2;
 348     //P3:677
 349     asm(
 350         "cmp $0x2000000, %0         \n\t"
 351         "lea (%0, %0), %%eax        \n\t"
 352         "lea (%1, %1), %%edx        \n\t"
 353         "cmovb %%eax, %0            \n\t"
 354         "cmovb %%edx, %1            \n\t"
 355         : "+r"(c->range), "+r"(c->low), "+a"(temp), "+d"(temp2)
 356     );
 357 #endif
 358 #else
 359     //P3:675
 360     int shift= (uint32_t)(c->range - (0x200 << CABAC_BITS))>>31;
 361     c->range<<= shift;
 362     c->low  <<= shift;
 363 #endif
 364     if(!(c->low & CABAC_MASK))
 365         refill(c);
 366 }
 367
 368 static int get_cabac(CABACContext *c, uint8_t * const state){
 369     //FIXME gcc generates duplicate load/stores for c->low and c->range
 370 START_TIMER
 371     int s = *state;
 372     int RangeLPS= c->lps_range[s][c->range>>(CABAC_BITS+7)]<<(CABAC_BITS+1);
 373     int bit, lps_mask attribute_unused;
 374
 375     c->range -= RangeLPS;
 376 #if 1
 377     if(c->low < c->range){
 378         bit= s&1;
 379         *state= c->mps_state[s];
 380         renorm_cabac_decoder_once(c);
 381     }else{
 382 //        int shift= ff_h264_norm_shift[RangeLPS>>17];
 383         bit= (s&1)^1;
 384         c->low -= c->range;
 385         *state= c->lps_state[s];
 386         c->range = RangeLPS;
 387         renorm_cabac_decoder(c);
 388 /*        c->range = RangeLPS<<shift;
 389         c->low <<= shift;
 390         if(!(c->low & 0xFFFF)){
 391             refill2(c);
 392         }*/
 393     }
 394 #else
 395     lps_mask= (c->range - c->low)>>31;
 396
 397     c->low -= c->range & lps_mask;
 398     c->range += (RangeLPS - c->range) & lps_mask;
 399
 400     bit= (s^lps_mask)&1;
 401     *state= c->mps_state[s - (128&lps_mask)];
 402
 403     lps_mask= ff_h264_norm_shift[c->range>>(CABAC_BITS+2)];
 404     c->range<<= lps_mask;
 405     c->low  <<= lps_mask;
 406     if(!(c->low & CABAC_MASK))
 407         refill2(c);
 408 #endif
 409 STOP_TIMER("get_cabac")
 410     return bit;
 411 }
 412
 413 static int get_cabac_bypass(CABACContext *c){
 414     c->low += c->low;
 415
 416     if(!(c->low & CABAC_MASK))
 417         refill(c);
 418
 419     if(c->low < c->range){
 420         return 0;
 421     }else{
 422         c->low -= c->range;
 423         return 1;
 424     }
 425 }
 426
 427 /**
 428  *
 429  * @return the number of bytes read or 0 if no end
 430  */
 431 static int get_cabac_terminate(CABACContext *c){
 432     c->range -= 4<<CABAC_BITS;
 433     if(c->low < c->range){
 434         renorm_cabac_decoder_once(c);
 435         return 0;
 436     }else{
 437         return c->bytestream - c->bytestream_start;
 438     }
 439 }
 440
 441 /**
 442  * get (truncated) unnary binarization.
 443  */
 444 static int get_cabac_u(CABACContext *c, uint8_t * state, int max, int max_index, int truncated){
 445     int i;
 446
 447     for(i=0; i<max; i++){
 448         if(get_cabac(c, state)==0)
 449             return i;
 450
 451         if(i< max_index) state++;
 452     }
 453
 454     return truncated ? max : -1;
 455 }
 456
 457 /**
 458  * get unary exp golomb k-th order binarization.
 459  */
 460 static int get_cabac_ueg(CABACContext *c, uint8_t * state, int max, int is_signed, int k, int max_index){
 461     int i, v;
 462     int m= 1<<k;
 463
 464     if(get_cabac(c, state)==0)
 465         return 0;
 466
 467     if(0 < max_index) state++;
 468
 469     for(i=1; i<max; i++){
 470         if(get_cabac(c, state)==0){
 471             if(is_signed && get_cabac_bypass(c)){
 472                 return -i;
 473             }else
 474                 return i;
 475         }
 476
 477         if(i < max_index) state++;
 478     }
 479
 480     while(get_cabac_bypass(c)){
 481         i+= m;
 482         m+= m;
 483     }
 484
 485     v=0;
 486     while(m>>=1){
 487         v+= v + get_cabac_bypass(c);
 488     }
 489     i += v;
 490
 491     if(is_signed && get_cabac_bypass(c)){
 492         return -i;
 493     }else
 494         return i;
 495 }