git.sesse.net Git - ffmpeg/blob - libavcodec/bitstream.c

   1 /*
   2  * Common bit i/o utils
   3  * Copyright (c) 2000, 2001 Fabrice Bellard
   4  * Copyright (c) 2002-2004 Michael Niedermayer <michaelni@gmx.at>
   5  * Copyright (c) 2010 Loren Merritt
   6  *
   7  * alternative bitstream reader & writer by Michael Niedermayer <michaelni@gmx.at>
   8  *
   9  * This file is part of FFmpeg.
  10  *
  11  * FFmpeg is free software; you can redistribute it and/or
  12  * modify it under the terms of the GNU Lesser General Public
  13  * License as published by the Free Software Foundation; either
  14  * version 2.1 of the License, or (at your option) any later version.
  15  *
  16  * FFmpeg is distributed in the hope that it will be useful,
  17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  19  * Lesser General Public License for more details.
  20  *
  21  * You should have received a copy of the GNU Lesser General Public
  22  * License along with FFmpeg; if not, write to the Free Software
  23  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  24  */
  25
  26 /**
  27  * @file
  28  * bitstream api.
  29  */
  30
  31 #include "libavutil/atomic.h"
  32 #include "libavutil/avassert.h"
  33 #include "avcodec.h"
  34 #include "internal.h"
  35 #include "mathops.h"
  36 #include "get_bits.h"
  37 #include "put_bits.h"
  38
  39 const uint8_t ff_log2_run[41]={
  40  0, 0, 0, 0, 1, 1, 1, 1,
  41  2, 2, 2, 2, 3, 3, 3, 3,
  42  4, 4, 5, 5, 6, 6, 7, 7,
  43  8, 9,10,11,12,13,14,15,
  44 16,17,18,19,20,21,22,23,
  45 24,
  46 };
  47
  48 void avpriv_align_put_bits(PutBitContext *s)
  49 {
  50     put_bits(s, s->bit_left & 7, 0);
  51 }
  52
  53 void avpriv_put_string(PutBitContext *pb, const char *string,
  54                        int terminate_string)
  55 {
  56     while (*string) {
  57         put_bits(pb, 8, *string);
  58         string++;
  59     }
  60     if (terminate_string)
  61         put_bits(pb, 8, 0);
  62 }
  63
  64 void avpriv_copy_bits(PutBitContext *pb, const uint8_t *src, int length)
  65 {
  66     int words = length >> 4;
  67     int bits  = length & 15;
  68     int i;
  69
  70     if (length == 0)
  71         return;
  72
  73     av_assert0(length <= put_bits_left(pb));
  74
  75     if (CONFIG_SMALL || words < 16 || put_bits_count(pb) & 7) {
  76         for (i = 0; i < words; i++)
  77             put_bits(pb, 16, AV_RB16(src + 2 * i));
  78     } else {
  79         for (i = 0; put_bits_count(pb) & 31; i++)
  80             put_bits(pb, 8, src[i]);
  81         flush_put_bits(pb);
  82         memcpy(put_bits_ptr(pb), src + i, 2 * words - i);
  83         skip_put_bytes(pb, 2 * words - i);
  84     }
  85
  86     put_bits(pb, bits, AV_RB16(src + 2 * words) >> (16 - bits));
  87 }
  88
  89 /* VLC decoding */
  90
  91 #define GET_DATA(v, table, i, wrap, size)                   \
  92 {                                                           \
  93     const uint8_t *ptr = (const uint8_t *)table + i * wrap; \
  94     switch(size) {                                          \
  95     case 1:                                                 \
  96         v = *(const uint8_t *)ptr;                          \
  97         break;                                              \
  98     case 2:                                                 \
  99         v = *(const uint16_t *)ptr;                         \
 100         break;                                              \
 101     default:                                                \
 102         v = *(const uint32_t *)ptr;                         \
 103         break;                                              \
 104     }                                                       \
 105 }
 106
 107
 108 static int alloc_table(VLC *vlc, int size, int use_static)
 109 {
 110     int index = vlc->table_size;
 111
 112     vlc->table_size += size;
 113     if (vlc->table_size > vlc->table_allocated) {
 114         if (use_static)
 115             abort(); // cannot do anything, init_vlc() is used with too little memory
 116         vlc->table_allocated += (1 << vlc->bits);
 117         vlc->table = av_realloc_f(vlc->table, vlc->table_allocated, sizeof(VLC_TYPE) * 2);
 118         if (!vlc->table) {
 119             vlc->table_allocated = 0;
 120             vlc->table_size = 0;
 121             return AVERROR(ENOMEM);
 122         }
 123         memset(vlc->table + vlc->table_allocated - (1 << vlc->bits), 0, sizeof(VLC_TYPE) * 2 << vlc->bits);
 124     }
 125     return index;
 126 }
 127
 128 static av_always_inline uint32_t bitswap_32(uint32_t x)
 129 {
 130     return (uint32_t)ff_reverse[ x        & 0xFF] << 24 |
 131            (uint32_t)ff_reverse[(x >> 8)  & 0xFF] << 16 |
 132            (uint32_t)ff_reverse[(x >> 16) & 0xFF] << 8  |
 133            (uint32_t)ff_reverse[ x >> 24];
 134 }
 135
 136 typedef struct VLCcode {
 137     uint8_t bits;
 138     uint16_t symbol;
 139     /** codeword, with the first bit-to-be-read in the msb
 140      * (even if intended for a little-endian bitstream reader) */
 141     uint32_t code;
 142 } VLCcode;
 143
 144 static int compare_vlcspec(const void *a, const void *b)
 145 {
 146     const VLCcode *sa = a, *sb = b;
 147     return (sa->code >> 1) - (sb->code >> 1);
 148 }
 149 /**
 150  * Build VLC decoding tables suitable for use with get_vlc().
 151  *
 152  * @param vlc            the context to be initted
 153  *
 154  * @param table_nb_bits  max length of vlc codes to store directly in this table
 155  *                       (Longer codes are delegated to subtables.)
 156  *
 157  * @param nb_codes       number of elements in codes[]
 158  *
 159  * @param codes          descriptions of the vlc codes
 160  *                       These must be ordered such that codes going into the same subtable are contiguous.
 161  *                       Sorting by VLCcode.code is sufficient, though not necessary.
 162  */
 163 static int build_table(VLC *vlc, int table_nb_bits, int nb_codes,
 164                        VLCcode *codes, int flags)
 165 {
 166     int table_size, table_index, index, code_prefix, symbol, subtable_bits;
 167     int i, j, k, n, nb, inc;
 168     uint32_t code;
 169     volatile VLC_TYPE (* volatile table)[2]; // the double volatile is needed to prevent a internal compiler error in gcc 4.2
 170
 171     table_size = 1 << table_nb_bits;
 172     if (table_nb_bits > 30)
 173        return -1;
 174     table_index = alloc_table(vlc, table_size, flags & INIT_VLC_USE_NEW_STATIC);
 175     ff_dlog(NULL, "new table index=%d size=%d\n", table_index, table_size);
 176     if (table_index < 0)
 177         return table_index;
 178     table = (volatile VLC_TYPE (*)[2])&vlc->table[table_index];
 179
 180     /* first pass: map codes and compute auxiliary table sizes */
 181     for (i = 0; i < nb_codes; i++) {
 182         n      = codes[i].bits;
 183         code   = codes[i].code;
 184         symbol = codes[i].symbol;
 185         ff_dlog(NULL, "i=%d n=%d code=0x%x\n", i, n, code);
 186         if (n <= table_nb_bits) {
 187             /* no need to add another table */
 188             j = code >> (32 - table_nb_bits);
 189             nb = 1 << (table_nb_bits - n);
 190             inc = 1;
 191             if (flags & INIT_VLC_LE) {
 192                 j = bitswap_32(code);
 193                 inc = 1 << n;
 194             }
 195             for (k = 0; k < nb; k++) {
 196                 int bits = table[j][1];
 197                 ff_dlog(NULL, "%4x: code=%d n=%d\n", j, i, n);
 198                 if (bits != 0 && bits != n) {
 199                     av_log(NULL, AV_LOG_ERROR, "incorrect codes\n");
 200                     return AVERROR_INVALIDDATA;
 201                 }
 202                 table[j][1] = n; //bits
 203                 table[j][0] = symbol;
 204                 j += inc;
 205             }
 206         } else {
 207             /* fill auxiliary table recursively */
 208             n -= table_nb_bits;
 209             code_prefix = code >> (32 - table_nb_bits);
 210             subtable_bits = n;
 211             codes[i].bits = n;
 212             codes[i].code = code << table_nb_bits;
 213             for (k = i+1; k < nb_codes; k++) {
 214                 n = codes[k].bits - table_nb_bits;
 215                 if (n <= 0)
 216                     break;
 217                 code = codes[k].code;
 218                 if (code >> (32 - table_nb_bits) != code_prefix)
 219                     break;
 220                 codes[k].bits = n;
 221                 codes[k].code = code << table_nb_bits;
 222                 subtable_bits = FFMAX(subtable_bits, n);
 223             }
 224             subtable_bits = FFMIN(subtable_bits, table_nb_bits);
 225             j = (flags & INIT_VLC_LE) ? bitswap_32(code_prefix) >> (32 - table_nb_bits) : code_prefix;
 226             table[j][1] = -subtable_bits;
 227             ff_dlog(NULL, "%4x: n=%d (subtable)\n",
 228                     j, codes[i].bits + table_nb_bits);
 229             index = build_table(vlc, subtable_bits, k-i, codes+i, flags);
 230             if (index < 0)
 231                 return index;
 232             /* note: realloc has been done, so reload tables */
 233             table = (volatile VLC_TYPE (*)[2])&vlc->table[table_index];
 234             table[j][0] = index; //code
 235             i = k-1;
 236         }
 237     }
 238
 239     for (i = 0; i < table_size; i++) {
 240         if (table[i][1] == 0) //bits
 241             table[i][0] = -1; //codes
 242     }
 243
 244     return table_index;
 245 }
 246
 247
 248 /* Build VLC decoding tables suitable for use with get_vlc().
 249
 250    'nb_bits' set the decoding table size (2^nb_bits) entries. The
 251    bigger it is, the faster is the decoding. But it should not be too
 252    big to save memory and L1 cache. '9' is a good compromise.
 253
 254    'nb_codes' : number of vlcs codes
 255
 256    'bits' : table which gives the size (in bits) of each vlc code.
 257
 258    'codes' : table which gives the bit pattern of of each vlc code.
 259
 260    'symbols' : table which gives the values to be returned from get_vlc().
 261
 262    'xxx_wrap' : give the number of bytes between each entry of the
 263    'bits' or 'codes' tables.
 264
 265    'xxx_size' : gives the number of bytes of each entry of the 'bits'
 266    or 'codes' tables.
 267
 268    'wrap' and 'size' make it possible to use any memory configuration and types
 269    (byte/word/long) to store the 'bits', 'codes', and 'symbols' tables.
 270
 271    'use_static' should be set to 1 for tables, which should be freed
 272    with av_free_static(), 0 if ff_free_vlc() will be used.
 273 */
 274 int ff_init_vlc_sparse(VLC *vlc_arg, int nb_bits, int nb_codes,
 275                        const void *bits, int bits_wrap, int bits_size,
 276                        const void *codes, int codes_wrap, int codes_size,
 277                        const void *symbols, int symbols_wrap, int symbols_size,
 278                        int flags)
 279 {
 280     VLCcode *buf;
 281     int i, j, ret;
 282     VLCcode localbuf[1500]; // the maximum currently needed is 1296 by rv34
 283     VLC localvlc, *vlc;
 284
 285     vlc = vlc_arg;
 286     vlc->bits = nb_bits;
 287     if (flags & INIT_VLC_USE_NEW_STATIC) {
 288         av_assert0(nb_codes + 1 <= FF_ARRAY_ELEMS(localbuf));
 289         buf = localbuf;
 290         localvlc = *vlc_arg;
 291         vlc = &localvlc;
 292         vlc->table_size = 0;
 293     } else {
 294         vlc->table           = NULL;
 295         vlc->table_allocated = 0;
 296         vlc->table_size      = 0;
 297
 298         buf = av_malloc_array((nb_codes + 1), sizeof(VLCcode));
 299         if (!buf)
 300             return AVERROR(ENOMEM);
 301     }
 302
 303
 304     av_assert0(symbols_size <= 2 || !symbols);
 305     j = 0;
 306 #define COPY(condition)\
 307     for (i = 0; i < nb_codes; i++) {                                        \
 308         GET_DATA(buf[j].bits, bits, i, bits_wrap, bits_size);               \
 309         if (!(condition))                                                   \
 310             continue;                                                       \
 311         if (buf[j].bits > 3*nb_bits || buf[j].bits>32) {                    \
 312             av_log(NULL, AV_LOG_ERROR, "Too long VLC (%d) in init_vlc\n", buf[j].bits);\
 313             if (!(flags & INIT_VLC_USE_NEW_STATIC))                         \
 314                 av_free(buf);                                               \
 315             return -1;                                                      \
 316         }                                                                   \
 317         GET_DATA(buf[j].code, codes, i, codes_wrap, codes_size);            \
 318         if (buf[j].code >= (1LL<<buf[j].bits)) {                            \
 319             av_log(NULL, AV_LOG_ERROR, "Invalid code in init_vlc\n");       \
 320             if (!(flags & INIT_VLC_USE_NEW_STATIC))                         \
 321                 av_free(buf);                                               \
 322             return -1;                                                      \
 323         }                                                                   \
 324         if (flags & INIT_VLC_LE)                                            \
 325             buf[j].code = bitswap_32(buf[j].code);                          \
 326         else                                                                \
 327             buf[j].code <<= 32 - buf[j].bits;                               \
 328         if (symbols)                                                        \
 329             GET_DATA(buf[j].symbol, symbols, i, symbols_wrap, symbols_size) \
 330         else                                                                \
 331             buf[j].symbol = i;                                              \
 332         j++;                                                                \
 333     }
 334     COPY(buf[j].bits > nb_bits);
 335     // qsort is the slowest part of init_vlc, and could probably be improved or avoided
 336     qsort(buf, j, sizeof(VLCcode), compare_vlcspec);
 337     COPY(buf[j].bits && buf[j].bits <= nb_bits);
 338     nb_codes = j;
 339
 340     ret = build_table(vlc, nb_bits, nb_codes, buf, flags);
 341
 342     if (flags & INIT_VLC_USE_NEW_STATIC) {
 343         if(vlc->table_size != vlc->table_allocated)
 344             av_log(NULL, AV_LOG_ERROR, "needed %d had %d\n", vlc->table_size, vlc->table_allocated);
 345
 346         av_assert0(ret >= 0);
 347         *vlc_arg = *vlc;
 348     } else {
 349         av_free(buf);
 350         if (ret < 0) {
 351             av_freep(&vlc->table);
 352             return ret;
 353         }
 354     }
 355     return 0;
 356 }
 357
 358
 359 void ff_free_vlc(VLC *vlc)
 360 {
 361     av_freep(&vlc->table);
 362 }