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