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