FFmpeg
vlc.c
Go to the documentation of this file.
1 /*
2  * API for creating VLC trees
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  * This file is part of FFmpeg.
8  *
9  * FFmpeg is free software; you can redistribute it and/or
10  * modify it under the terms of the GNU Lesser General Public
11  * License as published by the Free Software Foundation; either
12  * version 2.1 of the License, or (at your option) any later version.
13  *
14  * FFmpeg is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17  * Lesser General Public License for more details.
18  *
19  * You should have received a copy of the GNU Lesser General Public
20  * License along with FFmpeg; if not, write to the Free Software
21  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
22  */
23 
24 #include <inttypes.h>
25 #include <stdint.h>
26 #include <stdlib.h>
27 #include <string.h>
28 
29 #include "libavutil/attributes.h"
30 #include "libavutil/avassert.h"
31 #include "libavutil/error.h"
32 #include "libavutil/internal.h"
33 #include "libavutil/log.h"
34 #include "libavutil/macros.h"
35 #include "libavutil/mem.h"
36 #include "libavutil/qsort.h"
37 #include "libavutil/reverse.h"
38 #include "vlc.h"
39 
40 #define GET_DATA(v, table, i, wrap, size) \
41 { \
42  const uint8_t *ptr = (const uint8_t *)table + i * wrap; \
43  switch(size) { \
44  case 1: \
45  v = *(const uint8_t *)ptr; \
46  break; \
47  case 2: \
48  v = *(const uint16_t *)ptr; \
49  break; \
50  case 4: \
51  default: \
52  av_assert1(size == 4); \
53  v = *(const uint32_t *)ptr; \
54  break; \
55  } \
56 }
57 
58 
59 static int alloc_table(VLC *vlc, int size, int use_static)
60 {
61  int index = vlc->table_size;
62 
63  vlc->table_size += size;
64  if (vlc->table_size > vlc->table_allocated) {
65  if (use_static)
66  abort(); // cannot do anything, init_vlc() is used with too little memory
67  vlc->table_allocated += (1 << vlc->bits);
68  vlc->table = av_realloc_f(vlc->table, vlc->table_allocated, sizeof(*vlc->table));
69  if (!vlc->table) {
70  vlc->table_allocated = 0;
71  vlc->table_size = 0;
72  return AVERROR(ENOMEM);
73  }
74  memset(vlc->table + vlc->table_allocated - (1 << vlc->bits), 0, sizeof(*vlc->table) << vlc->bits);
75  }
76  return index;
77 }
78 
79 #define LOCALBUF_ELEMS 1500 // the maximum currently needed is 1296 by rv34
80 
81 static av_always_inline uint32_t bitswap_32(uint32_t x)
82 {
83  return (uint32_t)ff_reverse[ x & 0xFF] << 24 |
84  (uint32_t)ff_reverse[(x >> 8) & 0xFF] << 16 |
85  (uint32_t)ff_reverse[(x >> 16) & 0xFF] << 8 |
86  (uint32_t)ff_reverse[ x >> 24];
87 }
88 
89 typedef struct VLCcode {
90  uint8_t bits;
92  /** codeword, with the first bit-to-be-read in the msb
93  * (even if intended for a little-endian bitstream reader) */
94  uint32_t code;
95 } VLCcode;
96 
97 static int vlc_common_init(VLC *vlc, int nb_bits, int nb_codes,
98  VLCcode **buf, int flags)
99 {
100  vlc->bits = nb_bits;
101  vlc->table_size = 0;
103  av_assert0(nb_codes <= LOCALBUF_ELEMS);
104  } else {
105  vlc->table = NULL;
106  vlc->table_allocated = 0;
107  }
108  if (nb_codes > LOCALBUF_ELEMS) {
109  *buf = av_malloc_array(nb_codes, sizeof(VLCcode));
110  if (!*buf)
111  return AVERROR(ENOMEM);
112  }
113 
114  return 0;
115 }
116 
117 static int compare_vlcspec(const void *a, const void *b)
118 {
119  const VLCcode *sa = a, *sb = b;
120  return (sa->code >> 1) - (sb->code >> 1);
121 }
122 
123 /**
124  * Build VLC decoding tables suitable for use with get_vlc().
125  *
126  * @param vlc the context to be initialized
127  *
128  * @param table_nb_bits max length of vlc codes to store directly in this table
129  * (Longer codes are delegated to subtables.)
130  *
131  * @param nb_codes number of elements in codes[]
132  *
133  * @param codes descriptions of the vlc codes
134  * These must be ordered such that codes going into the same subtable are contiguous.
135  * Sorting by VLCcode.code is sufficient, though not necessary.
136  */
137 static int build_table(VLC *vlc, int table_nb_bits, int nb_codes,
138  VLCcode *codes, int flags)
139 {
140  int table_size, table_index;
141  VLCElem *table;
142 
143  if (table_nb_bits > 30)
144  return AVERROR(EINVAL);
145  table_size = 1 << table_nb_bits;
146  table_index = alloc_table(vlc, table_size, flags & INIT_VLC_USE_NEW_STATIC);
147  ff_dlog(NULL, "new table index=%d size=%d\n", table_index, table_size);
148  if (table_index < 0)
149  return table_index;
150  table = &vlc->table[table_index];
151 
152  /* first pass: map codes and compute auxiliary table sizes */
153  for (int i = 0; i < nb_codes; i++) {
154  int n = codes[i].bits;
155  uint32_t code = codes[i].code;
156  int symbol = codes[i].symbol;
157  ff_dlog(NULL, "i=%d n=%d code=0x%"PRIx32"\n", i, n, code);
158  if (n <= table_nb_bits) {
159  /* no need to add another table */
160  int j = code >> (32 - table_nb_bits);
161  int nb = 1 << (table_nb_bits - n);
162  int inc = 1;
163 
164  if (flags & INIT_VLC_OUTPUT_LE) {
165  j = bitswap_32(code);
166  inc = 1 << n;
167  }
168  for (int k = 0; k < nb; k++) {
169  int bits = table[j].len;
170  int oldsym = table[j].sym;
171  ff_dlog(NULL, "%4x: code=%d n=%d\n", j, i, n);
172  if ((bits || oldsym) && (bits != n || oldsym != symbol)) {
173  av_log(NULL, AV_LOG_ERROR, "incorrect codes\n");
174  return AVERROR_INVALIDDATA;
175  }
176  table[j].len = n;
177  table[j].sym = symbol;
178  j += inc;
179  }
180  } else {
181  /* fill auxiliary table recursively */
182  uint32_t code_prefix;
183  int index, subtable_bits, j, k;
184 
185  n -= table_nb_bits;
186  code_prefix = code >> (32 - table_nb_bits);
187  subtable_bits = n;
188  codes[i].bits = n;
189  codes[i].code = code << table_nb_bits;
190  for (k = i + 1; k < nb_codes; k++) {
191  n = codes[k].bits - table_nb_bits;
192  if (n <= 0)
193  break;
194  code = codes[k].code;
195  if (code >> (32 - table_nb_bits) != code_prefix)
196  break;
197  codes[k].bits = n;
198  codes[k].code = code << table_nb_bits;
199  subtable_bits = FFMAX(subtable_bits, n);
200  }
201  subtable_bits = FFMIN(subtable_bits, table_nb_bits);
202  j = (flags & INIT_VLC_OUTPUT_LE) ? bitswap_32(code_prefix) >> (32 - table_nb_bits) : code_prefix;
203  table[j].len = -subtable_bits;
204  ff_dlog(NULL, "%4x: n=%d (subtable)\n",
205  j, codes[i].bits + table_nb_bits);
206  index = build_table(vlc, subtable_bits, k-i, codes+i, flags);
207  if (index < 0)
208  return index;
209  /* note: realloc has been done, so reload tables */
210  table = &vlc->table[table_index];
211  table[j].sym = index;
212  if (table[j].sym != index) {
213  avpriv_request_sample(NULL, "strange codes");
214  return AVERROR_PATCHWELCOME;
215  }
216  i = k-1;
217  }
218  }
219 
220  for (int i = 0; i < table_size; i++) {
221  if (table[i].len == 0)
222  table[i].sym = -1;
223  }
224 
225  return table_index;
226 }
227 
228 static int vlc_common_end(VLC *vlc, int nb_bits, int nb_codes, VLCcode *codes,
229  int flags, VLCcode localbuf[LOCALBUF_ELEMS])
230 {
231  int ret = build_table(vlc, nb_bits, nb_codes, codes, flags);
232 
234  if (vlc->table_size != vlc->table_allocated &&
236  av_log(NULL, AV_LOG_ERROR, "needed %d had %d\n", vlc->table_size, vlc->table_allocated);
237  av_assert0(ret >= 0);
238  } else {
239  if (codes != localbuf)
240  av_free(codes);
241  if (ret < 0) {
242  av_freep(&vlc->table);
243  return ret;
244  }
245  }
246  return 0;
247 }
248 
249 /* Build VLC decoding tables suitable for use with get_vlc().
250 
251  'nb_bits' sets 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. Currently 1,2 and 4 are supported.
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 int ff_init_vlc_sparse(VLC *vlc, int nb_bits, int nb_codes,
273  const void *bits, int bits_wrap, int bits_size,
274  const void *codes, int codes_wrap, int codes_size,
275  const void *symbols, int symbols_wrap, int symbols_size,
276  int flags)
277 {
278  VLCcode localbuf[LOCALBUF_ELEMS], *buf = localbuf;
279  int j, ret;
280 
281  ret = vlc_common_init(vlc, nb_bits, nb_codes, &buf, flags);
282  if (ret < 0)
283  return ret;
284 
285  av_assert0(symbols_size <= 2 || !symbols);
286  j = 0;
287 #define COPY(condition)\
288  for (int i = 0; i < nb_codes; i++) { \
289  unsigned len; \
290  GET_DATA(len, bits, i, bits_wrap, bits_size); \
291  if (!(condition)) \
292  continue; \
293  if (len > 3*nb_bits || len > 32) { \
294  av_log(NULL, AV_LOG_ERROR, "Too long VLC (%u) in init_vlc\n", len);\
295  if (buf != localbuf) \
296  av_free(buf); \
297  return AVERROR(EINVAL); \
298  } \
299  buf[j].bits = len; \
300  GET_DATA(buf[j].code, codes, i, codes_wrap, codes_size); \
301  if (buf[j].code >= (1LL<<buf[j].bits)) { \
302  av_log(NULL, AV_LOG_ERROR, "Invalid code %"PRIx32" for %d in " \
303  "init_vlc\n", buf[j].code, i); \
304  if (buf != localbuf) \
305  av_free(buf); \
306  return AVERROR(EINVAL); \
307  } \
308  if (flags & INIT_VLC_INPUT_LE) \
309  buf[j].code = bitswap_32(buf[j].code); \
310  else \
311  buf[j].code <<= 32 - buf[j].bits; \
312  if (symbols) \
313  GET_DATA(buf[j].symbol, symbols, i, symbols_wrap, symbols_size) \
314  else \
315  buf[j].symbol = i; \
316  j++; \
317  }
318  COPY(len > nb_bits);
319  // qsort is the slowest part of init_vlc, and could probably be improved or avoided
320  AV_QSORT(buf, j, struct VLCcode, compare_vlcspec);
321  COPY(len && len <= nb_bits);
322  nb_codes = j;
323 
324  return vlc_common_end(vlc, nb_bits, nb_codes, buf,
325  flags, localbuf);
326 }
327 
328 int ff_init_vlc_from_lengths(VLC *vlc, int nb_bits, int nb_codes,
329  const int8_t *lens, int lens_wrap,
330  const void *symbols, int symbols_wrap, int symbols_size,
331  int offset, int flags, void *logctx)
332 {
333  VLCcode localbuf[LOCALBUF_ELEMS], *buf = localbuf;
334  uint64_t code;
335  int ret, j, len_max = FFMIN(32, 3 * nb_bits);
336 
337  ret = vlc_common_init(vlc, nb_bits, nb_codes, &buf, flags);
338  if (ret < 0)
339  return ret;
340 
341  j = code = 0;
342  for (int i = 0; i < nb_codes; i++, lens += lens_wrap) {
343  int len = *lens;
344  if (len > 0) {
345  unsigned sym;
346 
347  buf[j].bits = len;
348  if (symbols)
349  GET_DATA(sym, symbols, i, symbols_wrap, symbols_size)
350  else
351  sym = i;
352  buf[j].symbol = sym + offset;
353  buf[j++].code = code;
354  } else if (len < 0) {
355  len = -len;
356  } else
357  continue;
358  if (len > len_max || code & ((1U << (32 - len)) - 1)) {
359  av_log(logctx, AV_LOG_ERROR, "Invalid VLC (length %u)\n", len);
360  goto fail;
361  }
362  code += 1U << (32 - len);
363  if (code > UINT32_MAX + 1ULL) {
364  av_log(logctx, AV_LOG_ERROR, "Overdetermined VLC tree\n");
365  goto fail;
366  }
367  }
368  return vlc_common_end(vlc, nb_bits, j, buf, flags, localbuf);
369 fail:
370  if (buf != localbuf)
371  av_free(buf);
372  return AVERROR_INVALIDDATA;
373 }
374 
375 void ff_free_vlc(VLC *vlc)
376 {
377  av_freep(&vlc->table);
378 }
VLCcode::symbol
VLCBaseType symbol
Definition: vlc.c:91
AVERROR
Filter the word “frame” indicates either a video frame or a group of audio as stored in an AVFrame structure Format for each input and each output the list of supported formats For video that means pixel format For audio that means channel sample they are references to shared objects When the negotiation mechanism computes the intersection of the formats supported at each end of a all references to both lists are replaced with a reference to the intersection And when a single format is eventually chosen for a link amongst the remaining all references to the list are updated That means that if a filter requires that its input and output have the same format amongst a supported all it has to do is use a reference to the same list of formats query_formats can leave some formats unset and return AVERROR(EAGAIN) to cause the negotiation mechanism toagain later. That can be used by filters with complex requirements to use the format negotiated on one link to set the formats supported on another. Frame references ownership and permissions
INIT_VLC_OUTPUT_LE
#define INIT_VLC_OUTPUT_LE
Definition: vlc.h:98
vlc_common_init
static int vlc_common_init(VLC *vlc, int nb_bits, int nb_codes, VLCcode **buf, int flags)
Definition: vlc.c:97
b
#define b
Definition: input.c:41
ff_reverse
const uint8_t ff_reverse[256]
Definition: reverse.c:23
table
static const uint16_t table[]
Definition: prosumer.c:205
reverse.h
FFMAX
#define FFMAX(a, b)
Definition: macros.h:47
vlc_common_end
static int vlc_common_end(VLC *vlc, int nb_bits, int nb_codes, VLCcode *codes, int flags, VLCcode localbuf[LOCALBUF_ELEMS])
Definition: vlc.c:228
macros.h
fail
#define fail()
Definition: checkasm.h:133
avassert.h
AV_LOG_ERROR
#define AV_LOG_ERROR
Something went wrong and cannot losslessly be recovered.
Definition: log.h:180
bitswap_32
static av_always_inline uint32_t bitswap_32(uint32_t x)
Definition: vlc.c:81
bits
uint8_t bits
Definition: vp3data.h:141
LOCALBUF_ELEMS
#define LOCALBUF_ELEMS
Definition: vlc.c:79
av_assert0
#define av_assert0(cond)
assert() equivalent, that is always enabled.
Definition: avassert.h:37
build_table
static int build_table(VLC *vlc, int table_nb_bits, int nb_codes, VLCcode *codes, int flags)
Build VLC decoding tables suitable for use with get_vlc().
Definition: vlc.c:137
COPY
#define COPY(condition)
av_realloc_f
#define av_realloc_f(p, o, n)
Definition: tableprint_vlc.h:32
GET_DATA
#define GET_DATA(v, table, i, wrap, size)
Definition: vlc.c:40
NULL
#define NULL
Definition: coverity.c:32
AVERROR_PATCHWELCOME
#define AVERROR_PATCHWELCOME
Not yet implemented in FFmpeg, patches welcome.
Definition: error.h:64
ff_init_vlc_from_lengths
int ff_init_vlc_from_lengths(VLC *vlc, int nb_bits, int nb_codes, const int8_t *lens, int lens_wrap, const void *symbols, int symbols_wrap, int symbols_size, int offset, int flags, void *logctx)
Build VLC decoding tables suitable for use with get_vlc2()
Definition: vlc.c:328
INIT_VLC_USE_NEW_STATIC
#define INIT_VLC_USE_NEW_STATIC
Definition: vlc.h:100
index
int index
Definition: gxfenc.c:89
error.h
VLCcode
Definition: vlc.c:89
ff_dlog
#define ff_dlog(a,...)
Definition: tableprint_vlc.h:28
VLC::table_allocated
int table_allocated
Definition: vlc.h:34
qsort.h
compare_vlcspec
static int compare_vlcspec(const void *a, const void *b)
Definition: vlc.c:117
size
int size
Definition: twinvq_data.h:10344
VLCElem
Definition: vlc.h:27
a
The reader does not expect b to be semantically here and if the code is changed by maybe adding a a division or other the signedness will almost certainly be mistaken To avoid this confusion a new type was SUINT is the C unsigned type but it holds a signed int to use the same example SUINT a
Definition: undefined.txt:41
code_prefix
static const unsigned code_prefix[]
Definition: qdmc.c:78
offset
it s the only field you need to keep assuming you have a context There is some magic you don t need to care about around this just let it vf offset
Definition: writing_filters.txt:86
attributes.h
log.h
i
#define i(width, name, range_min, range_max)
Definition: cbs_h2645.c:269
code
and forward the test the status of outputs and forward it to the corresponding return FFERROR_NOT_READY If the filters stores internally one or a few frame for some it can consider them to be part of the FIFO and delay acknowledging a status change accordingly Example code
Definition: filter_design.txt:178
AV_QSORT
#define AV_QSORT(p, num, type, cmp)
Quicksort This sort is fast, and fully inplace but not stable and it is possible to construct input t...
Definition: qsort.h:33
ff_init_vlc_sparse
int ff_init_vlc_sparse(VLC *vlc, int nb_bits, int nb_codes, const void *bits, int bits_wrap, int bits_size, const void *codes, int codes_wrap, int codes_size, const void *symbols, int symbols_wrap, int symbols_size, int flags)
Definition: vlc.c:272
internal.h
av_malloc_array
#define av_malloc_array(a, b)
Definition: tableprint_vlc.h:31
VLCcode::bits
uint8_t bits
Definition: vlc.c:90
av_always_inline
#define av_always_inline
Definition: attributes.h:49
FFMIN
#define FFMIN(a, b)
Definition: macros.h:49
VLCcode::code
uint32_t code
codeword, with the first bit-to-be-read in the msb (even if intended for a little-endian bitstream re...
Definition: vlc.c:94
len
int len
Definition: vorbis_enc_data.h:426
ff_free_vlc
void ff_free_vlc(VLC *vlc)
Definition: vlc.c:375
VLC::bits
int bits
Definition: vlc.h:32
ret
ret
Definition: filter_design.txt:187
INIT_VLC_STATIC_OVERLONG
#define INIT_VLC_STATIC_OVERLONG
Definition: vlc.h:101
U
#define U(x)
Definition: vpx_arith.h:37
VLC
Definition: vlc.h:31
alloc_table
static int alloc_table(VLC *vlc, int size, int use_static)
Definition: vlc.c:59
VLC::table
VLCElem * table
Definition: vlc.h:33
VLC::table_size
int table_size
Definition: vlc.h:34
mem.h
avpriv_request_sample
#define avpriv_request_sample(...)
Definition: tableprint_vlc.h:36
av_free
#define av_free(p)
Definition: tableprint_vlc.h:33
av_freep
#define av_freep(p)
Definition: tableprint_vlc.h:34
vlc.h
flags
#define flags(name, subs,...)
Definition: cbs_av1.c:561
av_log
#define av_log(a,...)
Definition: tableprint_vlc.h:27
AVERROR_INVALIDDATA
#define AVERROR_INVALIDDATA
Invalid data found when processing input.
Definition: error.h:61
VLCBaseType
int16_t VLCBaseType
Definition: vlc.h:25