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