media/ffvpx/libavcodec/vlc.h

   1 /*
   2  * This file is part of FFmpeg.
   3  *
   4  * FFmpeg is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Lesser General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2.1 of the License, or (at your option) any later version.
   8  *
   9  * FFmpeg is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Lesser General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser General Public
  15  * License along with FFmpeg; if not, write to the Free Software
  16  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  17  */
  18
  19 #ifndef AVCODEC_VLC_H
  20 #define AVCODEC_VLC_H
  21
  22 #include <stddef.h>
  23 #include <stdint.h>
  24
  25 #include "libavutil/macros.h"
  26
  27 #define VLC_MULTI_MAX_SYMBOLS 6
  28
  29 // When changing this, be sure to also update tableprint_vlc.h accordingly.
  30 typedef int16_t VLCBaseType;
  31
  32 typedef struct VLCElem {
  33     VLCBaseType sym, len;
  34 } VLCElem;
  35
  36 typedef struct VLC {
  37     int bits;
  38     VLCElem *table;
  39     int table_size, table_allocated;
  40 } VLC;
  41
  42 typedef struct VLC_MULTI_ELEM {
  43     union {
  44         uint8_t   val8[VLC_MULTI_MAX_SYMBOLS];
  45         uint16_t val16[VLC_MULTI_MAX_SYMBOLS / 2];
  46     };
  47     int8_t len; // -31,32
  48     uint8_t num;
  49 } VLC_MULTI_ELEM;
  50
  51 typedef struct VLC_MULTI {
  52     VLC_MULTI_ELEM *table;
  53     int table_size, table_allocated;
  54 } VLC_MULTI;
  55
  56 typedef struct RL_VLC_ELEM {
  57     int16_t level;
  58     int8_t len;
  59     uint8_t run;
  60 } RL_VLC_ELEM;
  61
  62 #define vlc_init(vlc, nb_bits, nb_codes,                \
  63                  bits, bits_wrap, bits_size,            \
  64                  codes, codes_wrap, codes_size,         \
  65                  flags)                                 \
  66     ff_vlc_init_sparse(vlc, nb_bits, nb_codes,          \
  67                        bits, bits_wrap, bits_size,      \
  68                        codes, codes_wrap, codes_size,   \
  69                        NULL, 0, 0, flags)
  70
  71 /**
  72  * Build VLC decoding tables suitable for use with get_vlc2().
  73  *
  74  * @param[in,out] vlc      The VLC to be initialized; table and table_allocated
  75  *                         must have been set when initializing a static VLC,
  76  *                         otherwise this will be treated as uninitialized.
  77  * @param[in] nb_bits      The number of bits to use for the VLC table;
  78  *                         higher values take up more memory and cache, but
  79  *                         allow to read codes with fewer reads.
  80  *                         Corresponds to the `bits` parameter of get_vlc2().
  81  * @param[in] nb_codes     The number of provided bits, codes and (if supplied)
  82  *                         symbol entries.
  83  * @param[in] bits         The lengths (in bits) of the codes. Entries > 0
  84  *                         correspond to valid codes; entries == 0 will be skipped.
  85  * @param[in] bits_wrap    Stride (in bytes) of the bits table.
  86  * @param[in] codes_size   Size of the bits. 1, 2 and 4 are supported.
  87  * @param[in] codes        Table which gives the bit pattern of of each vlc code.
  88  * @param[in] codes_wrap   Stride (in bytes) of the codes table.
  89  * @param[in] codes_size   Size of the codes. 1, 2 and 4 are supported.
  90  * @param[in] symbols      The symbols, i.e. what is returned from get_vlc2()
  91  *                         when the corresponding code is encountered.
  92  *                         May be NULL, then 0, 1, 2, 3, 4,... will be used.
  93  * @param[in] symbols_wrap Stride (in bytes) of the symbols table.
  94  * @param[in] symbols_size Size of the symbols. 1 and 2 are supported.
  95  * @param[in] flags        A combination of the VLC_INIT_* flags.
  96  *
  97  * 'wrap' and 'size' make it possible to use any memory configuration and types
  98  * (byte/word/int) to store the 'bits', 'codes', and 'symbols' tables.
  99  */
 100 int ff_vlc_init_sparse(VLC *vlc, int nb_bits, int nb_codes,
 101                        const void *bits, int bits_wrap, int bits_size,
 102                        const void *codes, int codes_wrap, int codes_size,
 103                        const void *symbols, int symbols_wrap, int symbols_size,
 104                        int flags);
 105
 106 /**
 107  * Build VLC decoding tables suitable for use with get_vlc2()
 108  *
 109  * This function takes lengths and symbols and calculates the codes from them.
 110  * For this the input lengths and symbols have to be sorted according to "left
 111  * nodes in the corresponding tree first".
 112  *
 113  * @param[in,out] vlc      The VLC to be initialized; table and table_allocated
 114  *                         must have been set when initializing a static VLC,
 115  *                         otherwise this will be treated as uninitialized.
 116  * @param[in] nb_bits      The number of bits to use for the VLC table;
 117  *                         higher values take up more memory and cache, but
 118  *                         allow to read codes with fewer reads.
 119  * @param[in] nb_codes     The number of provided length and (if supplied) symbol
 120  *                         entries.
 121  * @param[in] lens         The lengths of the codes. Entries > 0 correspond to
 122  *                         valid codes; entries == 0 will be skipped and entries
 123  *                         with len < 0 indicate that the tree is incomplete and
 124  *                         has an open end of length -len at this position.
 125  * @param[in] lens_wrap    Stride (in bytes) of the lengths.
 126  * @param[in] symbols      The symbols, i.e. what is returned from get_vlc2()
 127  *                         when the corresponding code is encountered.
 128  *                         May be NULL, then 0, 1, 2, 3, 4,... will be used.
 129  * @param[in] symbols_wrap Stride (in bytes) of the symbols.
 130  * @param[in] symbols_size Size of the symbols. 1 and 2 are supported.
 131  * @param[in] offset       An offset to apply to all the valid symbols.
 132  * @param[in] flags        A combination of the VLC_INIT_* flags; notice that
 133  *                         VLC_INIT_INPUT_LE is pointless and ignored.
 134  */
 135 int ff_vlc_init_from_lengths(VLC *vlc, int nb_bits, int nb_codes,
 136                              const int8_t *lens, int lens_wrap,
 137                              const void *symbols, int symbols_wrap, int symbols_size,
 138                              int offset, int flags, void *logctx);
 139
 140 /**
 141  * Build VLC decoding tables suitable for use with get_vlc_multi()
 142  *
 143  * This function takes lengths and symbols and calculates the codes from them.
 144  * For this the input lengths and symbols have to be sorted according to "left
 145  * nodes in the corresponding tree first".
 146  *
 147  * @param[in,out] vlc      The VLC to be initialized; table and table_allocated
 148  *                         must have been set when initializing a static VLC,
 149  *                         otherwise this will be treated as uninitialized.
 150  * @param[in,out] multi    The VLC_MULTI to be initialized; table and table_allocated
 151  *                         must have been set when initializing a static VLC,
 152  *                         otherwise this will be treated as uninitialized.
 153  * @param[in] nb_bits      The number of bits to use for the VLC table;
 154  *                         higher values take up more memory and cache, but
 155  *                         allow to read codes with fewer reads.
 156  * @param[in] nb_elems     The max possible number of elements.
 157  * @param[in] nb_codes     The number of provided length and (if supplied) symbol
 158  *                         entries.
 159  * @param[in] lens         The lengths of the codes. Entries > 0 correspond to
 160  *                         valid codes; entries == 0 will be skipped and entries
 161  *                         with len < 0 indicate that the tree is incomplete and
 162  *                         has an open end of length -len at this position.
 163  * @param[in] lens_wrap    Stride (in bytes) of the lengths.
 164  * @param[in] symbols      The symbols, i.e. what is returned from get_vlc2()
 165  *                         when the corresponding code is encountered.
 166  *                         May be NULL, then 0, 1, 2, 3, 4,... will be used.
 167  * @param[in] symbols_wrap Stride (in bytes) of the symbols.
 168  * @param[in] symbols_size Size of the symbols. 1 and 2 are supported.
 169  * @param[in] offset       An offset to apply to all the valid symbols.
 170  * @param[in] flags        A combination of the VLC_INIT_* flags; notice that
 171  *                         VLC_INIT_INPUT_LE is pointless and ignored.
 172  */
 173 int ff_vlc_init_multi_from_lengths(VLC *vlc, VLC_MULTI *multi, int nb_bits, int nb_elems,
 174                                    int nb_codes, const int8_t *lens, int lens_wrap,
 175                                    const void *symbols, int symbols_wrap, int symbols_size,
 176                                    int offset, int flags, void *logctx);
 177
 178
 179 void ff_vlc_free_multi(VLC_MULTI *vlc);
 180 void ff_vlc_free(VLC *vlc);
 181
 182 #define VLC_INIT_USE_STATIC     1
 183 #define VLC_INIT_STATIC_OVERLONG (2 | VLC_INIT_USE_STATIC)
 184 /* If VLC_INIT_INPUT_LE is set, the LSB bit of the codes used to
 185  * initialize the VLC table is the first bit to be read. */
 186 #define VLC_INIT_INPUT_LE       4
 187 /* If set the VLC is intended for a little endian bitstream reader. */
 188 #define VLC_INIT_OUTPUT_LE      8
 189 #define VLC_INIT_LE             (VLC_INIT_INPUT_LE | VLC_INIT_OUTPUT_LE)
 190
 191 /**
 192  * For static VLCs, the number of bits can often be hardcoded
 193  * at each get_vlc2() callsite. Then using a full VLC would be uneconomical,
 194  * because only VLC.table would ever be accessed after initialization.
 195  * The following functions provide wrappers around the relevant ff_vlc_init_*
 196  * functions suitable for said task.
 197  *
 198  * The ff_vlc_init_tables_* functions are intended to be used for initializing
 199  * a series of VLCs. The user initializes a VLCInitState with the details
 200  * about the underlying array of VLCElem; it is automatically updated by
 201  * the ff_vlc_init_tables_* functions (i.e. table is incremented and size
 202  * decremented by the number of elements of the current table).
 203  * The VLC_INIT_STATIC_OVERLONG flag is also automatically added.
 204  * These functions return a pointer to the table just initialized,
 205  * potentially to be used in arrays of pointer to VLC tables.
 206  *
 207  * The ff_vlc_init_table_* functions are intended to be used for initializing
 208  * a single VLC table, given by table and table_size. The VLC_INIT_USE_STATIC
 209  * flag is automatically added.
 210  */
 211
 212 typedef struct VLCInitState {
 213     VLCElem *table;  ///< points to where the next VLC table will be placed
 214     unsigned size;   ///< remaining number of elements in table
 215 } VLCInitState;
 216
 217 #define VLC_INIT_STATE(_table) { .table = (_table), .size = FF_ARRAY_ELEMS(_table) }
 218
 219 void ff_vlc_init_table_from_lengths(VLCElem table[], int table_size,
 220                                     int nb_bits, int nb_codes,
 221                                     const int8_t *lens, int lens_wrap,
 222                                     const void *symbols, int symbols_wrap, int symbols_size,
 223                                     int offset, int flags);
 224
 225 const VLCElem *ff_vlc_init_tables_from_lengths(VLCInitState *state,
 226                                                int nb_bits, int nb_codes,
 227                                                const int8_t *lens, int lens_wrap,
 228                                                const void *symbols, int symbols_wrap, int symbols_size,
 229                                                int offset, int flags);
 230
 231 void ff_vlc_init_table_sparse(VLCElem table[], int table_size,
 232                               int nb_bits, int nb_codes,
 233                               const void *bits, int bits_wrap, int bits_size,
 234                               const void *codes, int codes_wrap, int codes_size,
 235                               const void *symbols, int symbols_wrap, int symbols_size,
 236                               int flags);
 237
 238 const VLCElem *ff_vlc_init_tables_sparse(VLCInitState *state,
 239                                          int nb_bits, int nb_codes,
 240                                          const void *bits, int bits_wrap, int bits_size,
 241                                          const void *codes, int codes_wrap, int codes_size,
 242                                          const void *symbols, int symbols_wrap, int symbols_size,
 243                                          int flags);
 244
 245 static inline
 246 const VLCElem *ff_vlc_init_tables(VLCInitState *state,
 247                                   int nb_bits, int nb_codes,
 248                                   const void *bits, int bits_wrap, int bits_size,
 249                                   const void *codes, int codes_wrap, int codes_size,
 250                                   int flags)
 251 {
 252     return ff_vlc_init_tables_sparse(state, nb_bits, nb_codes,
 253                                      bits, bits_wrap, bits_size,
 254                                      codes, codes_wrap, codes_size,
 255                                      NULL, 0, 0, flags);
 256 }
 257
 258 #define VLC_INIT_STATIC_SPARSE_TABLE(vlc_table, nb_bits, nb_codes,         \
 259                                      bits, bits_wrap, bits_size,           \
 260                                      codes, codes_wrap, codes_size,        \
 261                                      symbols, symbols_wrap, symbols_size,  \
 262                                      flags)                                \
 263     ff_vlc_init_table_sparse(vlc_table, FF_ARRAY_ELEMS(vlc_table),         \
 264                              (nb_bits), (nb_codes),                        \
 265                              (bits), (bits_wrap), (bits_size),             \
 266                              (codes), (codes_wrap), (codes_size),          \
 267                              (symbols), (symbols_wrap), (symbols_size),    \
 268                              (flags))
 269
 270 #define VLC_INIT_STATIC_TABLE(vlc_table, nb_bits, nb_codes,                \
 271                               bits, bits_wrap, bits_size,                  \
 272                               codes, codes_wrap, codes_size,               \
 273                               flags)                                       \
 274     ff_vlc_init_table_sparse(vlc_table, FF_ARRAY_ELEMS(vlc_table),         \
 275                              (nb_bits), (nb_codes),                        \
 276                              (bits), (bits_wrap), (bits_size),             \
 277                              (codes), (codes_wrap), (codes_size),          \
 278                              NULL, 0, 0, (flags))
 279
 280 #define VLC_INIT_STATIC_TABLE_FROM_LENGTHS(vlc_table, nb_bits, nb_codes,   \
 281                                            lens, lens_wrap,                \
 282                                            syms, syms_wrap, syms_size,     \
 283                                            offset, flags)                  \
 284     ff_vlc_init_table_from_lengths(vlc_table, FF_ARRAY_ELEMS(vlc_table),   \
 285                                    (nb_bits), (nb_codes),                  \
 286                                    (lens), (lens_wrap),                    \
 287                                    (syms), (syms_wrap), (syms_size),       \
 288                                    (offset), (flags))
 289
 290 #endif /* AVCODEC_VLC_H */