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 library is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU Lesser General Public
   7  * License as published by the Free Software Foundation; either
   8  * version 2 of the License, or (at your option) any later version.
   9  *
  10  * This library is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * Lesser General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU Lesser General Public
  16  * License along with this library; if not, write to the Free Software
  17  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  18  *
  19  */
  20
  21 /**
  22  * @file cabac.h
  23  * Context Adaptive Binary Arithmetic Coder.
  24  */
  25
  26
  27 #undef NDEBUG
  28 #include <assert.h>
  29
  30 typedef struct CABACContext{
  31     int low;
  32     int range;
  33     int outstanding_count;
  34 #ifdef STRICT_LIMITS
  35     int symCount;
  36 #endif
  37     uint8_t lps_range[2*64][4];   ///< rangeTabLPS
  38     uint8_t lps_state[2*64];      ///< transIdxLPS
  39     uint8_t mps_state[2*64];      ///< transIdxMPS
  40     const uint8_t *bytestream_start;
  41     const uint8_t *bytestream;
  42     const uint8_t *bytestream_end;
  43     int bits_left;                ///<
  44     PutBitContext pb;
  45 }CABACContext;
  46
  47 extern const uint8_t ff_h264_lps_range[64][4];
  48 extern const uint8_t ff_h264_mps_state[64];
  49 extern const uint8_t ff_h264_lps_state[64];
  50
  51 void ff_init_cabac_encoder(CABACContext *c, uint8_t *buf, int buf_size);
  52 void ff_init_cabac_decoder(CABACContext *c, const uint8_t *buf, int buf_size);
  53 void ff_init_cabac_states(CABACContext *c, uint8_t const (*lps_range)[4],
  54                           uint8_t const *mps_state, uint8_t const *lps_state, int state_count);
  55
  56
  57 static inline void put_cabac_bit(CABACContext *c, int b){
  58     put_bits(&c->pb, 1, b);
  59     for(;c->outstanding_count; c->outstanding_count--){
  60         put_bits(&c->pb, 1, 1-b);
  61     }
  62 }
  63
  64 static inline void renorm_cabac_encoder(CABACContext *c){
  65     while(c->range < 0x100){
  66         //FIXME optimize
  67         if(c->low<0x100){
  68             put_cabac_bit(c, 0);
  69         }else if(c->low<0x200){
  70             c->outstanding_count++;
  71             c->low -= 0x100;
  72         }else{
  73             put_cabac_bit(c, 1);
  74             c->low -= 0x200;
  75         }
  76
  77         c->range+= c->range;
  78         c->low += c->low;
  79     }
  80 }
  81
  82 static inline void put_cabac(CABACContext *c, uint8_t * const state, int bit){
  83     int RangeLPS= c->lps_range[*state][((c->range)>>6)&3];
  84
  85     if(bit == ((*state)&1)){
  86         c->range -= RangeLPS;
  87         *state= c->mps_state[*state];
  88     }else{
  89         c->low += c->range - RangeLPS;
  90         c->range = RangeLPS;
  91         *state= c->lps_state[*state];
  92     }
  93
  94     renorm_cabac_encoder(c);
  95
  96 #ifdef STRICT_LIMITS
  97     c->symCount++;
  98 #endif
  99 }
 100
 101 static inline void put_cabac_static(CABACContext *c, int RangeLPS, int bit){
 102     assert(c->range > RangeLPS);
 103
 104     if(!bit){
 105         c->range -= RangeLPS;
 106     }else{
 107         c->low += c->range - RangeLPS;
 108         c->range = RangeLPS;
 109     }
 110
 111     renorm_cabac_encoder(c);
 112
 113 #ifdef STRICT_LIMITS
 114     c->symCount++;
 115 #endif
 116 }
 117
 118 /**
 119  * @param bit 0 -> write zero bit, !=0 write one bit
 120  */
 121 static inline void put_cabac_bypass(CABACContext *c, int bit){
 122     c->low += c->low;
 123
 124     if(bit){
 125         c->low += c->range;
 126     }
 127 //FIXME optimize
 128     if(c->low<0x200){
 129         put_cabac_bit(c, 0);
 130     }else if(c->low<0x400){
 131         c->outstanding_count++;
 132         c->low -= 0x200;
 133     }else{
 134         put_cabac_bit(c, 1);
 135         c->low -= 0x400;
 136     }
 137
 138 #ifdef STRICT_LIMITS
 139     c->symCount++;
 140 #endif
 141 }
 142
 143 /**
 144  *
 145  * @return the number of bytes written
 146  */
 147 static inline int put_cabac_terminate(CABACContext *c, int bit){
 148     c->range -= 2;
 149
 150     if(!bit){
 151         renorm_cabac_encoder(c);
 152     }else{
 153         c->low += c->range;
 154         c->range= 2;
 155
 156         renorm_cabac_encoder(c);
 157
 158         assert(c->low <= 0x1FF);
 159         put_cabac_bit(c, c->low>>9);
 160         put_bits(&c->pb, 2, ((c->low>>7)&3)|1);
 161
 162         flush_put_bits(&c->pb); //FIXME FIXME FIXME XXX wrong
 163     }
 164
 165 #ifdef STRICT_LIMITS
 166     c->symCount++;
 167 #endif
 168
 169     return (put_bits_count(&c->pb)+7)>>3;
 170 }
 171
 172 /**
 173  * put (truncated) unary binarization.
 174  */
 175 static inline void put_cabac_u(CABACContext *c, uint8_t * state, int v, int max, int max_index, int truncated){
 176     int i;
 177
 178     assert(v <= max);
 179
 180 #if 1
 181     for(i=0; i<v; i++){
 182         put_cabac(c, state, 1);
 183         if(i < max_index) state++;
 184     }
 185     if(truncated==0 || v<max)
 186         put_cabac(c, state, 0);
 187 #else
 188     if(v <= max_index){
 189         for(i=0; i<v; i++){
 190             put_cabac(c, state+i, 1);
 191         }
 192         if(truncated==0 || v<max)
 193             put_cabac(c, state+i, 0);
 194     }else{
 195         for(i=0; i<=max_index; i++){
 196             put_cabac(c, state+i, 1);
 197         }
 198         for(; i<v; i++){
 199             put_cabac(c, state+max_index, 1);
 200         }
 201         if(truncated==0 || v<max)
 202             put_cabac(c, state+max_index, 0);
 203     }
 204 #endif
 205 }
 206
 207 /**
 208  * put unary exp golomb k-th order binarization.
 209  */
 210 static inline void put_cabac_ueg(CABACContext *c, uint8_t * state, int v, int max, int is_signed, int k, int max_index){
 211     int i;
 212
 213     if(v==0)
 214         put_cabac(c, state, 0);
 215     else{
 216         const int sign= v < 0;
 217
 218         if(is_signed) v= ABS(v);
 219
 220         if(v<max){
 221             for(i=0; i<v; i++){
 222                 put_cabac(c, state, 1);
 223                 if(i < max_index) state++;
 224             }
 225
 226             put_cabac(c, state, 0);
 227         }else{
 228             int m= 1<<k;
 229
 230             for(i=0; i<max; i++){
 231                 put_cabac(c, state, 1);
 232                 if(i < max_index) state++;
 233             }
 234
 235             v -= max;
 236             while(v >= m){ //FIXME optimize
 237                 put_cabac_bypass(c, 1);
 238                 v-= m;
 239                 m+= m;
 240             }
 241             put_cabac_bypass(c, 0);
 242             while(m>>=1){
 243                 put_cabac_bypass(c, v&m);
 244             }
 245         }
 246
 247         if(is_signed)
 248             put_cabac_bypass(c, sign);
 249     }
 250 }
 251
 252 static inline void renorm_cabac_decoder(CABACContext *c){
 253     while(c->range < 0x10000){
 254         c->range+= c->range;
 255         c->low+= c->low;
 256         if(--c->bits_left == 0){
 257             if(c->bytestream < c->bytestream_end)
 258                 c->low+= *c->bytestream;
 259             c->bytestream++;
 260             c->bits_left= 8;
 261         }
 262     }
 263 }
 264
 265 static inline int get_cabac(CABACContext *c, uint8_t * const state){
 266     int RangeLPS= c->lps_range[*state][((c->range)>>14)&3]<<8;
 267     int bit;
 268
 269     c->range -= RangeLPS;
 270     if(c->low < c->range){
 271         bit= (*state)&1;
 272         *state= c->mps_state[*state];
 273     }else{
 274         bit= ((*state)&1)^1;
 275         c->low -= c->range;
 276         c->range = RangeLPS;
 277         *state= c->lps_state[*state];
 278     }
 279     renorm_cabac_decoder(c);
 280
 281     return bit;
 282 }
 283
 284 static inline int get_cabac_static(CABACContext *c, int RangeLPS){
 285     int bit;
 286
 287     c->range -= RangeLPS;
 288     if(c->low < c->range){
 289         bit= 0;
 290     }else{
 291         bit= 1;
 292         c->low -= c->range;
 293         c->range = RangeLPS;
 294     }
 295     renorm_cabac_decoder(c);
 296
 297     return bit;
 298 }
 299
 300 static inline int get_cabac_bypass(CABACContext *c){
 301     c->low += c->low;
 302
 303     if(--c->bits_left == 0){
 304         if(c->bytestream < c->bytestream_end)
 305             c->low+= *c->bytestream;
 306         c->bytestream++;
 307         c->bits_left= 8;
 308     }
 309
 310     if(c->low < c->range){
 311         return 0;
 312     }else{
 313         c->low -= c->range;
 314         return 1;
 315     }
 316 }
 317
 318 /**
 319  *
 320  * @return the number of bytes read or 0 if no end
 321  */
 322 static inline int get_cabac_terminate(CABACContext *c){
 323     c->range -= 2<<8;
 324     if(c->low < c->range){
 325         renorm_cabac_decoder(c);
 326         return 0;
 327     }else{
 328         return c->bytestream - c->bytestream_start;
 329     }
 330 }
 331
 332 /**
 333  * get (truncated) unnary binarization.
 334  */
 335 static inline int get_cabac_u(CABACContext *c, uint8_t * state, int max, int max_index, int truncated){
 336     int i;
 337
 338     for(i=0; i<max; i++){
 339         if(get_cabac(c, state)==0)
 340             return i;
 341
 342         if(i< max_index) state++;
 343     }
 344
 345     return truncated ? max : -1;
 346 }
 347
 348 /**
 349  * get unary exp golomb k-th order binarization.
 350  */
 351 static inline int get_cabac_ueg(CABACContext *c, uint8_t * state, int max, int is_signed, int k, int max_index){
 352     int i, v;
 353     int m= 1<<k;
 354
 355     if(get_cabac(c, state)==0)
 356         return 0;
 357
 358     if(0 < max_index) state++;
 359
 360     for(i=1; i<max; i++){
 361         if(get_cabac(c, state)==0){
 362             if(is_signed && get_cabac_bypass(c)){
 363                 return -i;
 364             }else
 365                 return i;
 366         }
 367
 368         if(i < max_index) state++;
 369     }
 370
 371     while(get_cabac_bypass(c)){
 372         i+= m;
 373         m+= m;
 374     }
 375
 376     v=0;
 377     while(m>>=1){
 378         v+= v + get_cabac_bypass(c);
 379     }
 380     i += v;
 381
 382     if(is_signed && get_cabac_bypass(c)){
 383         return -i;
 384     }else
 385         return i;
 386 }