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