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 Libav.
   6  *
   7  * Libav 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  * Libav 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 Libav; 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 #ifndef AVCODEC_CABAC_H
  28 #define AVCODEC_CABAC_H
  29
  30 #include "put_bits.h"
  31
  32 //#undef NDEBUG
  33 #include <assert.h>
  34 #include "libavutil/x86_cpu.h"
  35
  36 #define CABAC_BITS 16
  37 #define CABAC_MASK ((1<<CABAC_BITS)-1)
  38
  39 typedef struct CABACContext{
  40     int low;
  41     int range;
  42     int outstanding_count;
  43 #ifdef STRICT_LIMITS
  44     int symCount;
  45 #endif
  46     const uint8_t *bytestream_start;
  47     const uint8_t *bytestream;
  48     const uint8_t *bytestream_end;
  49     PutBitContext pb;
  50 }CABACContext;
  51
  52 extern uint8_t ff_h264_mlps_state[4*64];
  53 extern uint8_t ff_h264_lps_range[4*2*64];  ///< rangeTabLPS
  54 extern uint8_t ff_h264_mps_state[2*64];     ///< transIdxMPS
  55 extern uint8_t ff_h264_lps_state[2*64];     ///< transIdxLPS
  56 extern const uint8_t ff_h264_norm_shift[512];
  57
  58
  59 void ff_init_cabac_encoder(CABACContext *c, uint8_t *buf, int buf_size);
  60 void ff_init_cabac_decoder(CABACContext *c, const uint8_t *buf, int buf_size);
  61 void ff_init_cabac_states(CABACContext *c);
  62
  63
  64 static inline void put_cabac_bit(CABACContext *c, int b){
  65     put_bits(&c->pb, 1, b);
  66     for(;c->outstanding_count; c->outstanding_count--){
  67         put_bits(&c->pb, 1, 1-b);
  68     }
  69 }
  70
  71 static inline void renorm_cabac_encoder(CABACContext *c){
  72     while(c->range < 0x100){
  73         //FIXME optimize
  74         if(c->low<0x100){
  75             put_cabac_bit(c, 0);
  76         }else if(c->low<0x200){
  77             c->outstanding_count++;
  78             c->low -= 0x100;
  79         }else{
  80             put_cabac_bit(c, 1);
  81             c->low -= 0x200;
  82         }
  83
  84         c->range+= c->range;
  85         c->low += c->low;
  86     }
  87 }
  88
  89 #ifdef TEST
  90 static void put_cabac(CABACContext *c, uint8_t * const state, int bit){
  91     int RangeLPS= ff_h264_lps_range[2*(c->range&0xC0) + *state];
  92
  93     if(bit == ((*state)&1)){
  94         c->range -= RangeLPS;
  95         *state= ff_h264_mps_state[*state];
  96     }else{
  97         c->low += c->range - RangeLPS;
  98         c->range = RangeLPS;
  99         *state= ff_h264_lps_state[*state];
 100     }
 101
 102     renorm_cabac_encoder(c);
 103
 104 #ifdef STRICT_LIMITS
 105     c->symCount++;
 106 #endif
 107 }
 108
 109 static void put_cabac_static(CABACContext *c, int RangeLPS, int bit){
 110     assert(c->range > RangeLPS);
 111
 112     if(!bit){
 113         c->range -= RangeLPS;
 114     }else{
 115         c->low += c->range - RangeLPS;
 116         c->range = RangeLPS;
 117     }
 118
 119     renorm_cabac_encoder(c);
 120
 121 #ifdef STRICT_LIMITS
 122     c->symCount++;
 123 #endif
 124 }
 125
 126 /**
 127  * @param bit 0 -> write zero bit, !=0 write one bit
 128  */
 129 static void put_cabac_bypass(CABACContext *c, int bit){
 130     c->low += c->low;
 131
 132     if(bit){
 133         c->low += c->range;
 134     }
 135 //FIXME optimize
 136     if(c->low<0x200){
 137         put_cabac_bit(c, 0);
 138     }else if(c->low<0x400){
 139         c->outstanding_count++;
 140         c->low -= 0x200;
 141     }else{
 142         put_cabac_bit(c, 1);
 143         c->low -= 0x400;
 144     }
 145
 146 #ifdef STRICT_LIMITS
 147     c->symCount++;
 148 #endif
 149 }
 150
 151 /**
 152  *
 153  * @return the number of bytes written
 154  */
 155 static int put_cabac_terminate(CABACContext *c, int bit){
 156     c->range -= 2;
 157
 158     if(!bit){
 159         renorm_cabac_encoder(c);
 160     }else{
 161         c->low += c->range;
 162         c->range= 2;
 163
 164         renorm_cabac_encoder(c);
 165
 166         assert(c->low <= 0x1FF);
 167         put_cabac_bit(c, c->low>>9);
 168         put_bits(&c->pb, 2, ((c->low>>7)&3)|1);
 169
 170         flush_put_bits(&c->pb); //FIXME FIXME FIXME XXX wrong
 171     }
 172
 173 #ifdef STRICT_LIMITS
 174     c->symCount++;
 175 #endif
 176
 177     return (put_bits_count(&c->pb)+7)>>3;
 178 }
 179
 180 /**
 181  * put (truncated) unary binarization.
 182  */
 183 static void put_cabac_u(CABACContext *c, uint8_t * state, int v, int max, int max_index, int truncated){
 184     int i;
 185
 186     assert(v <= max);
 187
 188 #if 1
 189     for(i=0; i<v; i++){
 190         put_cabac(c, state, 1);
 191         if(i < max_index) state++;
 192     }
 193     if(truncated==0 || v<max)
 194         put_cabac(c, state, 0);
 195 #else
 196     if(v <= max_index){
 197         for(i=0; i<v; i++){
 198             put_cabac(c, state+i, 1);
 199         }
 200         if(truncated==0 || v<max)
 201             put_cabac(c, state+i, 0);
 202     }else{
 203         for(i=0; i<=max_index; i++){
 204             put_cabac(c, state+i, 1);
 205         }
 206         for(; i<v; i++){
 207             put_cabac(c, state+max_index, 1);
 208         }
 209         if(truncated==0 || v<max)
 210             put_cabac(c, state+max_index, 0);
 211     }
 212 #endif
 213 }
 214
 215 /**
 216  * put unary exp golomb k-th order binarization.
 217  */
 218 static void put_cabac_ueg(CABACContext *c, uint8_t * state, int v, int max, int is_signed, int k, int max_index){
 219     int i;
 220
 221     if(v==0)
 222         put_cabac(c, state, 0);
 223     else{
 224         const int sign= v < 0;
 225
 226         if(is_signed) v= FFABS(v);
 227
 228         if(v<max){
 229             for(i=0; i<v; i++){
 230                 put_cabac(c, state, 1);
 231                 if(i < max_index) state++;
 232             }
 233
 234             put_cabac(c, state, 0);
 235         }else{
 236             int m= 1<<k;
 237
 238             for(i=0; i<max; i++){
 239                 put_cabac(c, state, 1);
 240                 if(i < max_index) state++;
 241             }
 242
 243             v -= max;
 244             while(v >= m){ //FIXME optimize
 245                 put_cabac_bypass(c, 1);
 246                 v-= m;
 247                 m+= m;
 248             }
 249             put_cabac_bypass(c, 0);
 250             while(m>>=1){
 251                 put_cabac_bypass(c, v&m);
 252             }
 253         }
 254
 255         if(is_signed)
 256             put_cabac_bypass(c, sign);
 257     }
 258 }
 259 #endif /* TEST */
 260
 261 static void refill(CABACContext *c){
 262 #if CABAC_BITS == 16
 263         c->low+= (c->bytestream[0]<<9) + (c->bytestream[1]<<1);
 264 #else
 265         c->low+= c->bytestream[0]<<1;
 266 #endif
 267     c->low -= CABAC_MASK;
 268     c->bytestream+= CABAC_BITS/8;
 269 }
 270
 271 #if ! ( ARCH_X86 && HAVE_7REGS && HAVE_EBX_AVAILABLE && !defined(BROKEN_RELOCATIONS) )
 272 static void refill2(CABACContext *c){
 273     int i, x;
 274
 275     x= c->low ^ (c->low-1);
 276     i= 7 - ff_h264_norm_shift[x>>(CABAC_BITS-1)];
 277
 278     x= -CABAC_MASK;
 279
 280 #if CABAC_BITS == 16
 281         x+= (c->bytestream[0]<<9) + (c->bytestream[1]<<1);
 282 #else
 283         x+= c->bytestream[0]<<1;
 284 #endif
 285
 286     c->low += x<<i;
 287     c->bytestream+= CABAC_BITS/8;
 288 }
 289 #endif
 290
 291 static inline void renorm_cabac_decoder(CABACContext *c){
 292     while(c->range < 0x100){
 293         c->range+= c->range;
 294         c->low+= c->low;
 295         if(!(c->low & CABAC_MASK))
 296             refill(c);
 297     }
 298 }
 299
 300 static inline void renorm_cabac_decoder_once(CABACContext *c){
 301     int shift= (uint32_t)(c->range - 0x100)>>31;
 302     c->range<<= shift;
 303     c->low  <<= shift;
 304     if(!(c->low & CABAC_MASK))
 305         refill(c);
 306 }
 307
 308 static av_always_inline int get_cabac_inline(CABACContext *c, uint8_t * const state){
 309     //FIXME gcc generates duplicate load/stores for c->low and c->range
 310 #define LOW          "0"
 311 #define RANGE        "4"
 312 #if ARCH_X86_64
 313 #define BYTESTART   "16"
 314 #define BYTE        "24"
 315 #define BYTEEND     "32"
 316 #else
 317 #define BYTESTART   "12"
 318 #define BYTE        "16"
 319 #define BYTEEND     "20"
 320 #endif
 321 #if ARCH_X86 && HAVE_7REGS && HAVE_EBX_AVAILABLE && !defined(BROKEN_RELOCATIONS)
 322     int bit;
 323
 324 #if HAVE_FAST_CMOV
 325 #define BRANCHLESS_GET_CABAC_UPDATE(ret, cabac, statep, low, lowword, range, tmp, tmpbyte)\
 326         "mov    "tmp"       , %%ecx                                     \n\t"\
 327         "shl    $17         , "tmp"                                     \n\t"\
 328         "cmp    "low"       , "tmp"                                     \n\t"\
 329         "cmova  %%ecx       , "range"                                   \n\t"\
 330         "sbb    %%ecx       , %%ecx                                     \n\t"\
 331         "and    %%ecx       , "tmp"                                     \n\t"\
 332         "sub    "tmp"       , "low"                                     \n\t"\
 333         "xor    %%ecx       , "ret"                                     \n\t"
 334 #else /* HAVE_FAST_CMOV */
 335 #define BRANCHLESS_GET_CABAC_UPDATE(ret, cabac, statep, low, lowword, range, tmp, tmpbyte)\
 336         "mov    "tmp"       , %%ecx                                     \n\t"\
 337         "shl    $17         , "tmp"                                     \n\t"\
 338         "sub    "low"       , "tmp"                                     \n\t"\
 339         "sar    $31         , "tmp"                                     \n\t" /*lps_mask*/\
 340         "sub    %%ecx       , "range"                                   \n\t" /*RangeLPS - range*/\
 341         "and    "tmp"       , "range"                                   \n\t" /*(RangeLPS - range)&lps_mask*/\
 342         "add    %%ecx       , "range"                                   \n\t" /*new range*/\
 343         "shl    $17         , %%ecx                                     \n\t"\
 344         "and    "tmp"       , %%ecx                                     \n\t"\
 345         "sub    %%ecx       , "low"                                     \n\t"\
 346         "xor    "tmp"       , "ret"                                     \n\t"
 347 #endif /* HAVE_FAST_CMOV */
 348
 349
 350 #define BRANCHLESS_GET_CABAC(ret, cabac, statep, low, lowword, range, tmp, tmpbyte)\
 351         "movzbl "statep"    , "ret"                                     \n\t"\
 352         "mov    "range"     , "tmp"                                     \n\t"\
 353         "and    $0xC0       , "range"                                   \n\t"\
 354         "movzbl "MANGLE(ff_h264_lps_range)"("ret", "range", 2), "range" \n\t"\
 355         "sub    "range"     , "tmp"                                     \n\t"\
 356         BRANCHLESS_GET_CABAC_UPDATE(ret, cabac, statep, low, lowword, range, tmp, tmpbyte)\
 357         "movzbl " MANGLE(ff_h264_norm_shift) "("range"), %%ecx          \n\t"\
 358         "shl    %%cl        , "range"                                   \n\t"\
 359         "movzbl "MANGLE(ff_h264_mlps_state)"+128("ret"), "tmp"          \n\t"\
 360         "mov    "tmpbyte"   , "statep"                                  \n\t"\
 361         "shl    %%cl        , "low"                                     \n\t"\
 362         "test   "lowword"   , "lowword"                                 \n\t"\
 363         " jnz   1f                                                      \n\t"\
 364         "mov "BYTE"("cabac"), %%"REG_c"                                 \n\t"\
 365         "movzwl (%%"REG_c")     , "tmp"                                 \n\t"\
 366         "bswap  "tmp"                                                   \n\t"\
 367         "shr    $15         , "tmp"                                     \n\t"\
 368         "sub    $0xFFFF     , "tmp"                                     \n\t"\
 369         "add    $2          , %%"REG_c"                                 \n\t"\
 370         "mov    %%"REG_c"   , "BYTE    "("cabac")                       \n\t"\
 371         "lea    -1("low")   , %%ecx                                     \n\t"\
 372         "xor    "low"       , %%ecx                                     \n\t"\
 373         "shr    $15         , %%ecx                                     \n\t"\
 374         "movzbl " MANGLE(ff_h264_norm_shift) "(%%ecx), %%ecx            \n\t"\
 375         "neg    %%ecx                                                   \n\t"\
 376         "add    $7          , %%ecx                                     \n\t"\
 377         "shl    %%cl        , "tmp"                                     \n\t"\
 378         "add    "tmp"       , "low"                                     \n\t"\
 379         "1:                                                             \n\t"
 380
 381     __asm__ volatile(
 382         "movl "RANGE    "(%2), %%esi            \n\t"
 383         "movl "LOW      "(%2), %%ebx            \n\t"
 384         BRANCHLESS_GET_CABAC("%0", "%2", "(%1)", "%%ebx", "%%bx", "%%esi", "%%edx", "%%dl")
 385         "movl %%esi, "RANGE    "(%2)            \n\t"
 386         "movl %%ebx, "LOW      "(%2)            \n\t"
 387
 388         :"=&a"(bit)
 389         :"r"(state), "r"(c)
 390         : "%"REG_c, "%ebx", "%edx", "%esi", "memory"
 391     );
 392     bit&=1;
 393 #else /* ARCH_X86 && HAVE_7REGS && HAVE_EBX_AVAILABLE && !defined(BROKEN_RELOCATIONS) */
 394     int s = *state;
 395     int RangeLPS= ff_h264_lps_range[2*(c->range&0xC0) + s];
 396     int bit, lps_mask;
 397
 398     c->range -= RangeLPS;
 399     lps_mask= ((c->range<<(CABAC_BITS+1)) - c->low)>>31;
 400
 401     c->low -= (c->range<<(CABAC_BITS+1)) & lps_mask;
 402     c->range += (RangeLPS - c->range) & lps_mask;
 403
 404     s^=lps_mask;
 405     *state= (ff_h264_mlps_state+128)[s];
 406     bit= s&1;
 407
 408     lps_mask= ff_h264_norm_shift[c->range];
 409     c->range<<= lps_mask;
 410     c->low  <<= lps_mask;
 411     if(!(c->low & CABAC_MASK))
 412         refill2(c);
 413 #endif /* ARCH_X86 && HAVE_7REGS && HAVE_EBX_AVAILABLE && !defined(BROKEN_RELOCATIONS) */
 414     return bit;
 415 }
 416
 417 static int av_noinline av_unused get_cabac_noinline(CABACContext *c, uint8_t * const state){
 418     return get_cabac_inline(c,state);
 419 }
 420
 421 static int av_unused get_cabac(CABACContext *c, uint8_t * const state){
 422     return get_cabac_inline(c,state);
 423 }
 424
 425 static int av_unused get_cabac_bypass(CABACContext *c){
 426 #if 0 //not faster
 427     int bit;
 428     __asm__ volatile(
 429         "movl "RANGE    "(%1), %%ebx            \n\t"
 430         "movl "LOW      "(%1), %%eax            \n\t"
 431         "shl $17, %%ebx                         \n\t"
 432         "add %%eax, %%eax                       \n\t"
 433         "sub %%ebx, %%eax                       \n\t"
 434         "cltd                                   \n\t"
 435         "and %%edx, %%ebx                       \n\t"
 436         "add %%ebx, %%eax                       \n\t"
 437         "test %%ax, %%ax                        \n\t"
 438         " jnz 1f                                \n\t"
 439         "movl "BYTE     "(%1), %%"REG_b"        \n\t"
 440         "subl $0xFFFF, %%eax                    \n\t"
 441         "movzwl (%%"REG_b"), %%ecx              \n\t"
 442         "bswap %%ecx                            \n\t"
 443         "shrl $15, %%ecx                        \n\t"
 444         "addl $2, %%"REG_b"                     \n\t"
 445         "addl %%ecx, %%eax                      \n\t"
 446         "movl %%"REG_b", "BYTE     "(%1)        \n\t"
 447         "1:                                     \n\t"
 448         "movl %%eax, "LOW      "(%1)            \n\t"
 449
 450         :"=&d"(bit)
 451         :"r"(c)
 452         : "%eax", "%"REG_b, "%ecx", "memory"
 453     );
 454     return bit+1;
 455 #else
 456     int range;
 457     c->low += c->low;
 458
 459     if(!(c->low & CABAC_MASK))
 460         refill(c);
 461
 462     range= c->range<<(CABAC_BITS+1);
 463     if(c->low < range){
 464         return 0;
 465     }else{
 466         c->low -= range;
 467         return 1;
 468     }
 469 #endif
 470 }
 471
 472
 473 static av_always_inline int get_cabac_bypass_sign(CABACContext *c, int val){
 474 #if ARCH_X86 && HAVE_EBX_AVAILABLE
 475     __asm__ volatile(
 476         "movl "RANGE    "(%1), %%ebx            \n\t"
 477         "movl "LOW      "(%1), %%eax            \n\t"
 478         "shl $17, %%ebx                         \n\t"
 479         "add %%eax, %%eax                       \n\t"
 480         "sub %%ebx, %%eax                       \n\t"
 481         "cltd                                   \n\t"
 482         "and %%edx, %%ebx                       \n\t"
 483         "add %%ebx, %%eax                       \n\t"
 484         "xor %%edx, %%ecx                       \n\t"
 485         "sub %%edx, %%ecx                       \n\t"
 486         "test %%ax, %%ax                        \n\t"
 487         " jnz 1f                                \n\t"
 488         "mov  "BYTE     "(%1), %%"REG_b"        \n\t"
 489         "subl $0xFFFF, %%eax                    \n\t"
 490         "movzwl (%%"REG_b"), %%edx              \n\t"
 491         "bswap %%edx                            \n\t"
 492         "shrl $15, %%edx                        \n\t"
 493         "add  $2, %%"REG_b"                     \n\t"
 494         "addl %%edx, %%eax                      \n\t"
 495         "mov  %%"REG_b", "BYTE     "(%1)        \n\t"
 496         "1:                                     \n\t"
 497         "movl %%eax, "LOW      "(%1)            \n\t"
 498
 499         :"+c"(val)
 500         :"r"(c)
 501         : "%eax", "%"REG_b, "%edx", "memory"
 502     );
 503     return val;
 504 #else
 505     int range, mask;
 506     c->low += c->low;
 507
 508     if(!(c->low & CABAC_MASK))
 509         refill(c);
 510
 511     range= c->range<<(CABAC_BITS+1);
 512     c->low -= range;
 513     mask= c->low >> 31;
 514     range &= mask;
 515     c->low += range;
 516     return (val^mask)-mask;
 517 #endif
 518 }
 519
 520 /**
 521  *
 522  * @return the number of bytes read or 0 if no end
 523  */
 524 static int av_unused get_cabac_terminate(CABACContext *c){
 525     c->range -= 2;
 526     if(c->low < c->range<<(CABAC_BITS+1)){
 527         renorm_cabac_decoder_once(c);
 528         return 0;
 529     }else{
 530         return c->bytestream - c->bytestream_start;
 531     }
 532 }
 533
 534 #if 0
 535 /**
 536  * Get (truncated) unary binarization.
 537  */
 538 static int get_cabac_u(CABACContext *c, uint8_t * state, int max, int max_index, int truncated){
 539     int i;
 540
 541     for(i=0; i<max; i++){
 542         if(get_cabac(c, state)==0)
 543             return i;
 544
 545         if(i< max_index) state++;
 546     }
 547
 548     return truncated ? max : -1;
 549 }
 550
 551 /**
 552  * get unary exp golomb k-th order binarization.
 553  */
 554 static int get_cabac_ueg(CABACContext *c, uint8_t * state, int max, int is_signed, int k, int max_index){
 555     int i, v;
 556     int m= 1<<k;
 557
 558     if(get_cabac(c, state)==0)
 559         return 0;
 560
 561     if(0 < max_index) state++;
 562
 563     for(i=1; i<max; i++){
 564         if(get_cabac(c, state)==0){
 565             if(is_signed && get_cabac_bypass(c)){
 566                 return -i;
 567             }else
 568                 return i;
 569         }
 570
 571         if(i < max_index) state++;
 572     }
 573
 574     while(get_cabac_bypass(c)){
 575         i+= m;
 576         m+= m;
 577     }
 578
 579     v=0;
 580     while(m>>=1){
 581         v+= v + get_cabac_bypass(c);
 582     }
 583     i += v;
 584
 585     if(is_signed && get_cabac_bypass(c)){
 586         return -i;
 587     }else
 588         return i;
 589 }
 590 #endif /* 0 */
 591
 592 #endif /* AVCODEC_CABAC_H */