LCOV - code coverage report
Current view: top level - libavcodec - bitstream.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 119 132 90.2 %
Date: 2017-12-15 11:05:35 Functions: 8 8 100.0 %

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

Generated by: LCOV version 1.13