libavcodec/get_bits.h

   1 /*
   2  * copyright (c) 2004 Michael Niedermayer <michaelni@gmx.at>
   3  *
   4  * This file is part of FFmpeg.
   5  *
   6  * FFmpeg is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * FFmpeg is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with FFmpeg; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  19  */
  20
  21 /**
  22  * @file
  23  * bitstream reader API header.
  24  */
  25
  26 #ifndef AVCODEC_GET_BITS_H
  27 #define AVCODEC_GET_BITS_H
  28
  29 #include <stdint.h>
  30 #include <stdlib.h>
  31 #include <assert.h>
  32 #include "libavutil/bswap.h"
  33 #include "libavutil/common.h"
  34 #include "libavutil/intreadwrite.h"
  35 #include "libavutil/log.h"
  36 #include "mathops.h"
  37
  38 #if defined(ALT_BITSTREAM_READER_LE) && !defined(ALT_BITSTREAM_READER)
  39 #   define ALT_BITSTREAM_READER
  40 #endif
  41
  42 #if !defined(A32_BITSTREAM_READER) && !defined(ALT_BITSTREAM_READER)
  43 #   if ARCH_ARM && !HAVE_FAST_UNALIGNED
  44 #       define A32_BITSTREAM_READER
  45 #   else
  46 #       define ALT_BITSTREAM_READER
  47 //#define A32_BITSTREAM_READER
  48 #   endif
  49 #endif
  50
  51 /* bit input */
  52 /* buffer, buffer_end and size_in_bits must be present and used by every reader */
  53 typedef struct GetBitContext {
  54     const uint8_t *buffer, *buffer_end;
  55 #ifdef ALT_BITSTREAM_READER
  56     int index;
  57 #elif defined A32_BITSTREAM_READER
  58     uint32_t *buffer_ptr;
  59     uint32_t cache0;
  60     uint32_t cache1;
  61     int bit_count;
  62 #endif
  63     int size_in_bits;
  64 } GetBitContext;
  65
  66 #define VLC_TYPE int16_t
  67
  68 typedef struct VLC {
  69     int bits;
  70     VLC_TYPE (*table)[2]; ///< code, bits
  71     int table_size, table_allocated;
  72 } VLC;
  73
  74 typedef struct RL_VLC_ELEM {
  75     int16_t level;
  76     int8_t len;
  77     uint8_t run;
  78 } RL_VLC_ELEM;
  79
  80 /* Bitstream reader API docs:
  81 name
  82     arbitrary name which is used as prefix for the internal variables
  83
  84 gb
  85     getbitcontext
  86
  87 OPEN_READER(name, gb)
  88     loads gb into local variables
  89
  90 CLOSE_READER(name, gb)
  91     stores local vars in gb
  92
  93 UPDATE_CACHE(name, gb)
  94     refills the internal cache from the bitstream
  95     after this call at least MIN_CACHE_BITS will be available,
  96
  97 GET_CACHE(name, gb)
  98     will output the contents of the internal cache, next bit is MSB of 32 or 64 bit (FIXME 64bit)
  99
 100 SHOW_UBITS(name, gb, num)
 101     will return the next num bits
 102
 103 SHOW_SBITS(name, gb, num)
 104     will return the next num bits and do sign extension
 105
 106 SKIP_BITS(name, gb, num)
 107     will skip over the next num bits
 108     note, this is equivalent to SKIP_CACHE; SKIP_COUNTER
 109
 110 SKIP_CACHE(name, gb, num)
 111     will remove the next num bits from the cache (note SKIP_COUNTER MUST be called before UPDATE_CACHE / CLOSE_READER)
 112
 113 SKIP_COUNTER(name, gb, num)
 114     will increment the internal bit counter (see SKIP_CACHE & SKIP_BITS)
 115
 116 LAST_SKIP_CACHE(name, gb, num)
 117     will remove the next num bits from the cache if it is needed for UPDATE_CACHE otherwise it will do nothing
 118
 119 LAST_SKIP_BITS(name, gb, num)
 120     is equivalent to LAST_SKIP_CACHE; SKIP_COUNTER
 121
 122 for examples see get_bits, show_bits, skip_bits, get_vlc
 123 */
 124
 125 #ifdef ALT_BITSTREAM_READER
 126 #   define MIN_CACHE_BITS 25
 127
 128 #   define OPEN_READER(name, gb)                \
 129     unsigned int name##_index = (gb)->index;    \
 130     av_unused unsigned int name##_cache
 131
 132 #   define CLOSE_READER(name, gb) (gb)->index = name##_index
 133
 134 # ifdef ALT_BITSTREAM_READER_LE
 135 #   define UPDATE_CACHE(name, gb) \
 136     name##_cache = AV_RL32(((const uint8_t *)(gb)->buffer)+(name##_index>>3)) >> (name##_index&0x07)
 137
 138 #   define SKIP_CACHE(name, gb, num) name##_cache >>= (num)
 139 # else
 140 #   define UPDATE_CACHE(name, gb) \
 141     name##_cache = AV_RB32(((const uint8_t *)(gb)->buffer)+(name##_index>>3)) << (name##_index&0x07)
 142
 143 #   define SKIP_CACHE(name, gb, num) name##_cache <<= (num)
 144 # endif
 145
 146 // FIXME name?
 147 #   define SKIP_COUNTER(name, gb, num) name##_index += (num)
 148
 149 #   define SKIP_BITS(name, gb, num) do {        \
 150         SKIP_CACHE(name, gb, num);              \
 151         SKIP_COUNTER(name, gb, num);            \
 152     } while (0)
 153
 154 #   define LAST_SKIP_BITS(name, gb, num) SKIP_COUNTER(name, gb, num)
 155 #   define LAST_SKIP_CACHE(name, gb, num)
 156
 157 # ifdef ALT_BITSTREAM_READER_LE
 158 #   define SHOW_UBITS(name, gb, num) zero_extend(name##_cache, num)
 159
 160 #   define SHOW_SBITS(name, gb, num) sign_extend(name##_cache, num)
 161 # else
 162 #   define SHOW_UBITS(name, gb, num) NEG_USR32(name##_cache, num)
 163
 164 #   define SHOW_SBITS(name, gb, num) NEG_SSR32(name##_cache, num)
 165 # endif
 166
 167 #   define GET_CACHE(name, gb) ((uint32_t)name##_cache)
 168
 169 static inline int get_bits_count(const GetBitContext *s){
 170     return s->index;
 171 }
 172
 173 static inline void skip_bits_long(GetBitContext *s, int n){
 174     s->index += n;
 175 }
 176
 177 #elif defined A32_BITSTREAM_READER
 178
 179 #   define MIN_CACHE_BITS 32
 180
 181 #   define OPEN_READER(name, gb)                        \
 182     int name##_bit_count        = (gb)->bit_count;      \
 183     uint32_t name##_cache0      = (gb)->cache0;         \
 184     uint32_t name##_cache1      = (gb)->cache1;         \
 185     uint32_t *name##_buffer_ptr = (gb)->buffer_ptr
 186
 187 #   define CLOSE_READER(name, gb) do {          \
 188         (gb)->bit_count  = name##_bit_count;    \
 189         (gb)->cache0     = name##_cache0;       \
 190         (gb)->cache1     = name##_cache1;       \
 191         (gb)->buffer_ptr = name##_buffer_ptr;   \
 192     } while (0)
 193
 194 #   define UPDATE_CACHE(name, gb) do {                                  \
 195         if(name##_bit_count > 0){                                       \
 196             const uint32_t next = av_be2ne32(*name##_buffer_ptr);       \
 197             name##_cache0 |= NEG_USR32(next, name##_bit_count);         \
 198             name##_cache1 |= next << name##_bit_count;                  \
 199             name##_buffer_ptr++;                                        \
 200             name##_bit_count -= 32;                                     \
 201         }                                                               \
 202     } while (0)
 203
 204 #   define SKIP_CACHE(name, gb, num) do {               \
 205         name##_cache0 <<= (num);                        \
 206         name##_cache0 |= NEG_USR32(name##_cache1,num);  \
 207         name##_cache1 <<= (num);                        \
 208     } while (0)
 209
 210 #   define SKIP_COUNTER(name, gb, num) name##_bit_count += (num)
 211
 212 #   define SKIP_BITS(name, gb, num) do {        \
 213         SKIP_CACHE(name, gb, num);              \
 214         SKIP_COUNTER(name, gb, num);            \
 215     } while (0)
 216
 217 #   define LAST_SKIP_BITS(name, gb, num)  SKIP_BITS(name, gb, num)
 218 #   define LAST_SKIP_CACHE(name, gb, num) SKIP_CACHE(name, gb, num)
 219
 220 #   define SHOW_UBITS(name, gb, num) NEG_USR32(name##_cache0, num)
 221
 222 #   define SHOW_SBITS(name, gb, num) NEG_SSR32(name##_cache0, num)
 223
 224 #   define GET_CACHE(name, gb) name##_cache0
 225
 226 static inline int get_bits_count(const GetBitContext *s) {
 227     return ((uint8_t*)s->buffer_ptr - s->buffer)*8 - 32 + s->bit_count;
 228 }
 229
 230 static inline void skip_bits_long(GetBitContext *s, int n){
 231     OPEN_READER(re, s);
 232     re_bit_count += n;
 233     re_buffer_ptr += re_bit_count>>5;
 234     re_bit_count &= 31;
 235     re_cache0 = av_be2ne32(re_buffer_ptr[-1]) << re_bit_count;
 236     re_cache1 = 0;
 237     UPDATE_CACHE(re, s);
 238     CLOSE_READER(re, s);
 239 }
 240
 241 #endif
 242
 243 /**
 244  * read mpeg1 dc style vlc (sign bit + mantisse with no MSB).
 245  * if MSB not set it is negative
 246  * @param n length in bits
 247  * @author BERO
 248  */
 249 static inline int get_xbits(GetBitContext *s, int n){
 250     register int sign;
 251     register int32_t cache;
 252     OPEN_READER(re, s);
 253     UPDATE_CACHE(re, s);
 254     cache = GET_CACHE(re, s);
 255     sign = ~cache >> 31;
 256     LAST_SKIP_BITS(re, s, n);
 257     CLOSE_READER(re, s);
 258     return (NEG_USR32(sign ^ cache, n) ^ sign) - sign;
 259 }
 260
 261 static inline int get_sbits(GetBitContext *s, int n){
 262     register int tmp;
 263     OPEN_READER(re, s);
 264     UPDATE_CACHE(re, s);
 265     tmp = SHOW_SBITS(re, s, n);
 266     LAST_SKIP_BITS(re, s, n);
 267     CLOSE_READER(re, s);
 268     return tmp;
 269 }
 270
 271 /**
 272  * Read 1-25 bits.
 273  */
 274 static inline unsigned int get_bits(GetBitContext *s, int n){
 275     register int tmp;
 276     OPEN_READER(re, s);
 277     UPDATE_CACHE(re, s);
 278     tmp = SHOW_UBITS(re, s, n);
 279     LAST_SKIP_BITS(re, s, n);
 280     CLOSE_READER(re, s);
 281     return tmp;
 282 }
 283
 284 /**
 285  * Shows 1-25 bits.
 286  */
 287 static inline unsigned int show_bits(GetBitContext *s, int n){
 288     register int tmp;
 289     OPEN_READER(re, s);
 290     UPDATE_CACHE(re, s);
 291     tmp = SHOW_UBITS(re, s, n);
 292     return tmp;
 293 }
 294
 295 static inline void skip_bits(GetBitContext *s, int n){
 296  //Note gcc seems to optimize this to s->index+=n for the ALT_READER :))
 297     OPEN_READER(re, s);
 298     UPDATE_CACHE(re, s);
 299     LAST_SKIP_BITS(re, s, n);
 300     CLOSE_READER(re, s);
 301 }
 302
 303 static inline unsigned int get_bits1(GetBitContext *s){
 304 #ifdef ALT_BITSTREAM_READER
 305     unsigned int index = s->index;
 306     uint8_t result = s->buffer[index>>3];
 307 #ifdef ALT_BITSTREAM_READER_LE
 308     result >>= index & 7;
 309     result &= 1;
 310 #else
 311     result <<= index & 7;
 312     result >>= 8 - 1;
 313 #endif
 314     index++;
 315     s->index = index;
 316
 317     return result;
 318 #else
 319     return get_bits(s, 1);
 320 #endif
 321 }
 322
 323 static inline unsigned int show_bits1(GetBitContext *s){
 324     return show_bits(s, 1);
 325 }
 326
 327 static inline void skip_bits1(GetBitContext *s){
 328     skip_bits(s, 1);
 329 }
 330
 331 /**
 332  * reads 0-32 bits.
 333  */
 334 static inline unsigned int get_bits_long(GetBitContext *s, int n){
 335     if (n <= MIN_CACHE_BITS) return get_bits(s, n);
 336     else {
 337 #ifdef ALT_BITSTREAM_READER_LE
 338         int ret = get_bits(s, 16);
 339         return ret | (get_bits(s, n-16) << 16);
 340 #else
 341         int ret = get_bits(s, 16) << (n-16);
 342         return ret | get_bits(s, n-16);
 343 #endif
 344     }
 345 }
 346
 347 /**
 348  * reads 0-32 bits as a signed integer.
 349  */
 350 static inline int get_sbits_long(GetBitContext *s, int n) {
 351     return sign_extend(get_bits_long(s, n), n);
 352 }
 353
 354 /**
 355  * shows 0-32 bits.
 356  */
 357 static inline unsigned int show_bits_long(GetBitContext *s, int n){
 358     if (n <= MIN_CACHE_BITS) return show_bits(s, n);
 359     else {
 360         GetBitContext gb = *s;
 361         return get_bits_long(&gb, n);
 362     }
 363 }
 364
 365 static inline int check_marker(GetBitContext *s, const char *msg)
 366 {
 367     int bit = get_bits1(s);
 368     if (!bit)
 369         av_log(NULL, AV_LOG_INFO, "Marker bit missing %s\n", msg);
 370
 371     return bit;
 372 }
 373
 374 /**
 375  * init GetBitContext.
 376  * @param buffer bitstream buffer, must be FF_INPUT_BUFFER_PADDING_SIZE bytes larger than the actual read bits
 377  * because some optimized bitstream readers read 32 or 64 bit at once and could read over the end
 378  * @param bit_size the size of the buffer in bits
 379  *
 380  * While GetBitContext stores the buffer size, for performance reasons you are
 381  * responsible for checking for the buffer end yourself (take advantage of the padding)!
 382  */
 383 static inline void init_get_bits(GetBitContext *s,
 384                    const uint8_t *buffer, int bit_size)
 385 {
 386     int buffer_size = (bit_size+7)>>3;
 387     if (buffer_size < 0 || bit_size < 0) {
 388         buffer_size = bit_size = 0;
 389         buffer = NULL;
 390     }
 391
 392     s->buffer       = buffer;
 393     s->size_in_bits = bit_size;
 394     s->buffer_end   = buffer + buffer_size;
 395 #ifdef ALT_BITSTREAM_READER
 396     s->index        = 0;
 397 #elif defined A32_BITSTREAM_READER
 398     s->buffer_ptr   = (uint32_t*)((intptr_t)buffer & ~3);
 399     s->bit_count    = 32 +     8*((intptr_t)buffer &  3);
 400     skip_bits_long(s, 0);
 401 #endif
 402 }
 403
 404 static inline void align_get_bits(GetBitContext *s)
 405 {
 406     int n = -get_bits_count(s) & 7;
 407     if (n) skip_bits(s, n);
 408 }
 409
 410 #define init_vlc(vlc, nb_bits, nb_codes,                \
 411                  bits, bits_wrap, bits_size,            \
 412                  codes, codes_wrap, codes_size,         \
 413                  flags)                                 \
 414         init_vlc_sparse(vlc, nb_bits, nb_codes,         \
 415                         bits, bits_wrap, bits_size,     \
 416                         codes, codes_wrap, codes_size,  \
 417                         NULL, 0, 0, flags)
 418
 419 int init_vlc_sparse(VLC *vlc, int nb_bits, int nb_codes,
 420              const void *bits, int bits_wrap, int bits_size,
 421              const void *codes, int codes_wrap, int codes_size,
 422              const void *symbols, int symbols_wrap, int symbols_size,
 423              int flags);
 424 #define INIT_VLC_LE         2
 425 #define INIT_VLC_USE_NEW_STATIC 4
 426 void free_vlc(VLC *vlc);
 427
 428 #define INIT_VLC_STATIC(vlc, bits, a,b,c,d,e,f,g, static_size) do {     \
 429         static VLC_TYPE table[static_size][2];                          \
 430         (vlc)->table = table;                                           \
 431         (vlc)->table_allocated = static_size;                           \
 432         init_vlc(vlc, bits, a,b,c,d,e,f,g, INIT_VLC_USE_NEW_STATIC);    \
 433     } while (0)
 434
 435
 436 /**
 437  *
 438  * If the vlc code is invalid and max_depth=1, then no bits will be removed.
 439  * If the vlc code is invalid and max_depth>1, then the number of bits removed
 440  * is undefined.
 441  */
 442 #define GET_VLC(code, name, gb, table, bits, max_depth) do {    \
 443         int n, nb_bits;                                         \
 444         unsigned int index;                                     \
 445                                                                 \
 446         index = SHOW_UBITS(name, gb, bits);                     \
 447         code  = table[index][0];                                \
 448         n     = table[index][1];                                \
 449                                                                 \
 450         if (max_depth > 1 && n < 0) {                           \
 451             LAST_SKIP_BITS(name, gb, bits);                     \
 452             UPDATE_CACHE(name, gb);                             \
 453                                                                 \
 454             nb_bits = -n;                                       \
 455                                                                 \
 456             index = SHOW_UBITS(name, gb, nb_bits) + code;       \
 457             code  = table[index][0];                            \
 458             n     = table[index][1];                            \
 459             if (max_depth > 2 && n < 0) {                       \
 460                 LAST_SKIP_BITS(name, gb, nb_bits);              \
 461                 UPDATE_CACHE(name, gb);                         \
 462                                                                 \
 463                 nb_bits = -n;                                   \
 464                                                                 \
 465                 index = SHOW_UBITS(name, gb, nb_bits) + code;   \
 466                 code  = table[index][0];                        \
 467                 n     = table[index][1];                        \
 468             }                                                   \
 469         }                                                       \
 470         SKIP_BITS(name, gb, n);                                 \
 471     } while (0)
 472
 473 #define GET_RL_VLC(level, run, name, gb, table, bits, max_depth, need_update) do { \
 474         int n, nb_bits;                                                 \
 475         unsigned int index;                                             \
 476                                                                         \
 477         index = SHOW_UBITS(name, gb, bits);                             \
 478         level = table[index].level;                                     \
 479         n     = table[index].len;                                       \
 480                                                                         \
 481         if (max_depth > 1 && n < 0) {                                   \
 482             SKIP_BITS(name, gb, bits);                                  \
 483             if (need_update) {                                          \
 484                 UPDATE_CACHE(name, gb);                                 \
 485             }                                                           \
 486                                                                         \
 487             nb_bits = -n;                                               \
 488                                                                         \
 489             index = SHOW_UBITS(name, gb, nb_bits) + level;              \
 490             level = table[index].level;                                 \
 491             n     = table[index].len;                                   \
 492         }                                                               \
 493         run = table[index].run;                                         \
 494         SKIP_BITS(name, gb, n);                                         \
 495     } while (0)
 496
 497
 498 /**
 499  * parses a vlc code, faster than get_vlc()
 500  * @param bits is the number of bits which will be read at once, must be
 501  *             identical to nb_bits in init_vlc()
 502  * @param max_depth is the number of times bits bits must be read to completely
 503  *                  read the longest vlc code
 504  *                  = (max_vlc_length + bits - 1) / bits
 505  */
 506 static av_always_inline int get_vlc2(GetBitContext *s, VLC_TYPE (*table)[2],
 507                                   int bits, int max_depth)
 508 {
 509     int code;
 510
 511     OPEN_READER(re, s);
 512     UPDATE_CACHE(re, s);
 513
 514     GET_VLC(code, re, s, table, bits, max_depth);
 515
 516     CLOSE_READER(re, s);
 517     return code;
 518 }
 519
 520 static inline int decode012(GetBitContext *gb){
 521     int n;
 522     n = get_bits1(gb);
 523     if (n == 0)
 524         return 0;
 525     else
 526         return get_bits1(gb) + 1;
 527 }
 528
 529 static inline int decode210(GetBitContext *gb){
 530     if (get_bits1(gb))
 531         return 0;
 532     else
 533         return 2 - get_bits1(gb);
 534 }
 535
 536 static inline int get_bits_left(GetBitContext *gb)
 537 {
 538     return gb->size_in_bits - get_bits_count(gb);
 539 }
 540
 541 //#define TRACE
 542
 543 #ifdef TRACE
 544 static inline void print_bin(int bits, int n){
 545     int i;
 546
 547     for (i = n-1; i >= 0; i--) {
 548         av_log(NULL, AV_LOG_DEBUG, "%d", (bits>>i)&1);
 549     }
 550     for (i = n; i < 24; i++)
 551         av_log(NULL, AV_LOG_DEBUG, " ");
 552 }
 553
 554 static inline int get_bits_trace(GetBitContext *s, int n, char *file,
 555                                  const char *func, int line){
 556     int r = get_bits(s, n);
 557
 558     print_bin(r, n);
 559     av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d bit @%5d in %s %s:%d\n",
 560            r, n, r, get_bits_count(s)-n, file, func, line);
 561     return r;
 562 }
 563 static inline int get_vlc_trace(GetBitContext *s, VLC_TYPE (*table)[2],
 564                                 int bits, int max_depth, char *file,
 565                                 const char *func, int line){
 566     int show  = show_bits(s, 24);
 567     int pos   = get_bits_count(s);
 568     int r     = get_vlc2(s, table, bits, max_depth);
 569     int len   = get_bits_count(s) - pos;
 570     int bits2 = show >> (24-len);
 571
 572     print_bin(bits2, len);
 573
 574     av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d vlc @%5d in %s %s:%d\n",
 575            bits2, len, r, pos, file, func, line);
 576     return r;
 577 }
 578 static inline int get_xbits_trace(GetBitContext *s, int n, char *file,
 579                                   const char *func, int line){
 580     int show = show_bits(s, n);
 581     int r    = get_xbits(s, n);
 582
 583     print_bin(show, n);
 584     av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d xbt @%5d in %s %s:%d\n",
 585            show, n, r, get_bits_count(s)-n, file, func, line);
 586     return r;
 587 }
 588
 589 #define get_bits(s, n)  get_bits_trace(s, n, __FILE__, __PRETTY_FUNCTION__, __LINE__)
 590 #define get_bits1(s)    get_bits_trace(s, 1, __FILE__, __PRETTY_FUNCTION__, __LINE__)
 591 #define get_xbits(s, n) get_xbits_trace(s, n, __FILE__, __PRETTY_FUNCTION__, __LINE__)
 592 #define get_vlc(s, vlc)            get_vlc_trace(s, (vlc)->table, (vlc)->bits, 3, __FILE__, __PRETTY_FUNCTION__, __LINE__)
 593 #define get_vlc2(s, tab, bits, max) get_vlc_trace(s, tab, bits, max, __FILE__, __PRETTY_FUNCTION__, __LINE__)
 594
 595 #define tprintf(p, ...) av_log(p, AV_LOG_DEBUG, __VA_ARGS__)
 596
 597 #else //TRACE
 598 #define tprintf(p, ...) {}
 599 #endif
 600
 601 #endif /* AVCODEC_GET_BITS_H */