FFmpeg
bitstream.c
Go to the documentation of this file.
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 <inttypes.h>
32 #include <stdint.h>
33 #include <stdlib.h>
34 #include <string.h>
35 
36 #include "config.h"
37 #include "libavutil/avassert.h"
38 #include "libavutil/bswap.h"
39 #include "libavutil/common.h"
40 #include "libavutil/error.h"
41 #include "libavutil/internal.h"
42 #include "libavutil/intreadwrite.h"
43 #include "libavutil/log.h"
44 #include "libavutil/mem.h"
45 #include "libavutil/qsort.h"
46 #include "mathops.h"
47 #include "put_bits.h"
48 #include "vlc.h"
49 
50 const uint8_t ff_log2_run[41]={
51  0, 0, 0, 0, 1, 1, 1, 1,
52  2, 2, 2, 2, 3, 3, 3, 3,
53  4, 4, 5, 5, 6, 6, 7, 7,
54  8, 9,10,11,12,13,14,15,
55 16,17,18,19,20,21,22,23,
56 24,
57 };
58 
59 void ff_put_string(PutBitContext *pb, const char *string, int terminate_string)
60 {
61  while (*string) {
62  put_bits(pb, 8, *string);
63  string++;
64  }
65  if (terminate_string)
66  put_bits(pb, 8, 0);
67 }
68 
69 void ff_copy_bits(PutBitContext *pb, const uint8_t *src, int length)
70 {
71  int words = length >> 4;
72  int bits = length & 15;
73  int i;
74 
75  if (length == 0)
76  return;
77 
78  av_assert0(length <= put_bits_left(pb));
79 
80  if (CONFIG_SMALL || words < 16 || put_bits_count(pb) & 7) {
81  for (i = 0; i < words; i++)
82  put_bits(pb, 16, AV_RB16(src + 2 * i));
83  } else {
84  for (i = 0; put_bits_count(pb) & 31; i++)
85  put_bits(pb, 8, src[i]);
86  flush_put_bits(pb);
87  memcpy(put_bits_ptr(pb), src + i, 2 * words - i);
88  skip_put_bytes(pb, 2 * words - i);
89  }
90 
91  put_bits(pb, bits, AV_RB16(src + 2 * words) >> (16 - bits));
92 }
93 
94 /* VLC decoding */
95 
96 #define GET_DATA(v, table, i, wrap, size) \
97 { \
98  const uint8_t *ptr = (const uint8_t *)table + i * wrap; \
99  switch(size) { \
100  case 1: \
101  v = *(const uint8_t *)ptr; \
102  break; \
103  case 2: \
104  v = *(const uint16_t *)ptr; \
105  break; \
106  case 4: \
107  default: \
108  av_assert1(size == 4); \
109  v = *(const uint32_t *)ptr; \
110  break; \
111  } \
112 }
113 
114 
115 static int alloc_table(VLC *vlc, int size, int use_static)
116 {
117  int index = vlc->table_size;
118 
119  vlc->table_size += size;
120  if (vlc->table_size > vlc->table_allocated) {
121  if (use_static)
122  abort(); // cannot do anything, init_vlc() is used with too little memory
123  vlc->table_allocated += (1 << vlc->bits);
124  vlc->table = av_realloc_f(vlc->table, vlc->table_allocated, sizeof(VLC_TYPE) * 2);
125  if (!vlc->table) {
126  vlc->table_allocated = 0;
127  vlc->table_size = 0;
128  return AVERROR(ENOMEM);
129  }
130  memset(vlc->table + vlc->table_allocated - (1 << vlc->bits), 0, sizeof(VLC_TYPE) * 2 << vlc->bits);
131  }
132  return index;
133 }
134 
135 #define LOCALBUF_ELEMS 1500 // the maximum currently needed is 1296 by rv34
136 
137 typedef struct VLCcode {
138  uint8_t bits;
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 vlc_common_init(VLC *vlc, int nb_bits, int nb_codes,
146  VLCcode **buf, int flags)
147 {
148  vlc->bits = nb_bits;
149  vlc->table_size = 0;
151  av_assert0(nb_codes <= LOCALBUF_ELEMS);
152  } else {
153  vlc->table = NULL;
154  vlc->table_allocated = 0;
155  }
156  if (nb_codes > LOCALBUF_ELEMS) {
157  *buf = av_malloc_array(nb_codes, sizeof(VLCcode));
158  if (!*buf)
159  return AVERROR(ENOMEM);
160  }
161 
162  return 0;
163 }
164 
165 static int compare_vlcspec(const void *a, const void *b)
166 {
167  const VLCcode *sa = a, *sb = b;
168  return (sa->code >> 1) - (sb->code >> 1);
169 }
170 /**
171  * Build VLC decoding tables suitable for use with get_vlc().
172  *
173  * @param vlc the context to be initialized
174  *
175  * @param table_nb_bits max length of vlc codes to store directly in this table
176  * (Longer codes are delegated to subtables.)
177  *
178  * @param nb_codes number of elements in codes[]
179  *
180  * @param codes descriptions of the vlc codes
181  * These must be ordered such that codes going into the same subtable are contiguous.
182  * Sorting by VLCcode.code is sufficient, though not necessary.
183  */
184 static int build_table(VLC *vlc, int table_nb_bits, int nb_codes,
185  VLCcode *codes, int flags)
186 {
187  int table_size, table_index, index, code_prefix, symbol, subtable_bits;
188  int i, j, k, n, nb, inc;
189  VLC_TYPE (*table)[2];
190  uint32_t code;
191 
192  if (table_nb_bits > 30)
193  return AVERROR(EINVAL);
194  table_size = 1 << table_nb_bits;
195  table_index = alloc_table(vlc, table_size, flags & INIT_VLC_USE_NEW_STATIC);
196  ff_dlog(NULL, "new table index=%d size=%d\n", table_index, table_size);
197  if (table_index < 0)
198  return table_index;
199  table = &vlc->table[table_index];
200 
201  /* first pass: map codes and compute auxiliary table sizes */
202  for (i = 0; i < nb_codes; i++) {
203  n = codes[i].bits;
204  code = codes[i].code;
205  symbol = codes[i].symbol;
206  ff_dlog(NULL, "i=%d n=%d code=0x%"PRIx32"\n", i, n, code);
207  if (n <= table_nb_bits) {
208  /* no need to add another table */
209  j = code >> (32 - table_nb_bits);
210  nb = 1 << (table_nb_bits - n);
211  inc = 1;
212  if (flags & INIT_VLC_OUTPUT_LE) {
213  j = bitswap_32(code);
214  inc = 1 << n;
215  }
216  for (k = 0; k < nb; k++) {
217  int bits = table[j][1];
218  int oldsym = table[j][0];
219  ff_dlog(NULL, "%4x: code=%d n=%d\n", j, i, n);
220  if ((bits || oldsym) && (bits != n || oldsym != symbol)) {
221  av_log(NULL, AV_LOG_ERROR, "incorrect codes\n");
222  return AVERROR_INVALIDDATA;
223  }
224  table[j][1] = n; //bits
225  table[j][0] = symbol;
226  j += inc;
227  }
228  } else {
229  /* fill auxiliary table recursively */
230  n -= table_nb_bits;
231  code_prefix = code >> (32 - table_nb_bits);
232  subtable_bits = n;
233  codes[i].bits = n;
234  codes[i].code = code << table_nb_bits;
235  for (k = i+1; k < nb_codes; k++) {
236  n = codes[k].bits - table_nb_bits;
237  if (n <= 0)
238  break;
239  code = codes[k].code;
240  if (code >> (32 - table_nb_bits) != code_prefix)
241  break;
242  codes[k].bits = n;
243  codes[k].code = code << table_nb_bits;
244  subtable_bits = FFMAX(subtable_bits, n);
245  }
246  subtable_bits = FFMIN(subtable_bits, table_nb_bits);
247  j = (flags & INIT_VLC_OUTPUT_LE) ? bitswap_32(code_prefix) >> (32 - table_nb_bits) : code_prefix;
248  table[j][1] = -subtable_bits;
249  ff_dlog(NULL, "%4x: n=%d (subtable)\n",
250  j, codes[i].bits + table_nb_bits);
251  index = build_table(vlc, subtable_bits, k-i, codes+i, flags);
252  if (index < 0)
253  return index;
254  /* note: realloc has been done, so reload tables */
255  table = &vlc->table[table_index];
256  table[j][0] = index; //code
257  if (table[j][0] != index) {
258  avpriv_request_sample(NULL, "strange codes");
259  return AVERROR_PATCHWELCOME;
260  }
261  i = k-1;
262  }
263  }
264 
265  for (i = 0; i < table_size; i++) {
266  if (table[i][1] == 0) //bits
267  table[i][0] = -1; //codes
268  }
269 
270  return table_index;
271 }
272 
273 static int vlc_common_end(VLC *vlc, int nb_bits, int nb_codes, VLCcode *codes,
274  int flags, VLCcode localbuf[LOCALBUF_ELEMS])
275 {
276  int ret = build_table(vlc, nb_bits, nb_codes, codes, flags);
277 
279  if (vlc->table_size != vlc->table_allocated &&
281  av_log(NULL, AV_LOG_ERROR, "needed %d had %d\n", vlc->table_size, vlc->table_allocated);
282  av_assert0(ret >= 0);
283  } else {
284  if (codes != localbuf)
285  av_free(codes);
286  if (ret < 0) {
287  av_freep(&vlc->table);
288  return ret;
289  }
290  }
291  return 0;
292 }
293 
294 /* Build VLC decoding tables suitable for use with get_vlc().
295 
296  'nb_bits' sets the decoding table size (2^nb_bits) entries. The
297  bigger it is, the faster is the decoding. But it should not be too
298  big to save memory and L1 cache. '9' is a good compromise.
299 
300  'nb_codes' : number of vlcs codes
301 
302  'bits' : table which gives the size (in bits) of each vlc code.
303 
304  'codes' : table which gives the bit pattern of of each vlc code.
305 
306  'symbols' : table which gives the values to be returned from get_vlc().
307 
308  'xxx_wrap' : give the number of bytes between each entry of the
309  'bits' or 'codes' tables.
310 
311  'xxx_size' : gives the number of bytes of each entry of the 'bits'
312  or 'codes' tables. Currently 1,2 and 4 are supported.
313 
314  'wrap' and 'size' make it possible to use any memory configuration and types
315  (byte/word/long) to store the 'bits', 'codes', and 'symbols' tables.
316 */
317 int ff_init_vlc_sparse(VLC *vlc, int nb_bits, int nb_codes,
318  const void *bits, int bits_wrap, int bits_size,
319  const void *codes, int codes_wrap, int codes_size,
320  const void *symbols, int symbols_wrap, int symbols_size,
321  int flags)
322 {
323  VLCcode localbuf[LOCALBUF_ELEMS], *buf = localbuf;
324  int i, j, ret;
325 
326  ret = vlc_common_init(vlc, nb_bits, nb_codes, &buf, flags);
327  if (ret < 0)
328  return ret;
329 
330  av_assert0(symbols_size <= 2 || !symbols);
331  j = 0;
332 #define COPY(condition)\
333  for (i = 0; i < nb_codes; i++) { \
334  unsigned len; \
335  GET_DATA(len, bits, i, bits_wrap, bits_size); \
336  if (!(condition)) \
337  continue; \
338  if (len > 3*nb_bits || len > 32) { \
339  av_log(NULL, AV_LOG_ERROR, "Too long VLC (%u) in init_vlc\n", len);\
340  if (buf != localbuf) \
341  av_free(buf); \
342  return AVERROR(EINVAL); \
343  } \
344  buf[j].bits = len; \
345  GET_DATA(buf[j].code, codes, i, codes_wrap, codes_size); \
346  if (buf[j].code >= (1LL<<buf[j].bits)) { \
347  av_log(NULL, AV_LOG_ERROR, "Invalid code %"PRIx32" for %d in " \
348  "init_vlc\n", buf[j].code, i); \
349  if (buf != localbuf) \
350  av_free(buf); \
351  return AVERROR(EINVAL); \
352  } \
353  if (flags & INIT_VLC_INPUT_LE) \
354  buf[j].code = bitswap_32(buf[j].code); \
355  else \
356  buf[j].code <<= 32 - buf[j].bits; \
357  if (symbols) \
358  GET_DATA(buf[j].symbol, symbols, i, symbols_wrap, symbols_size) \
359  else \
360  buf[j].symbol = i; \
361  j++; \
362  }
363  COPY(len > nb_bits);
364  // qsort is the slowest part of init_vlc, and could probably be improved or avoided
365  AV_QSORT(buf, j, struct VLCcode, compare_vlcspec);
366  COPY(len && len <= nb_bits);
367  nb_codes = j;
368 
369  return vlc_common_end(vlc, nb_bits, nb_codes, buf,
370  flags, localbuf);
371 }
372 
373 int ff_init_vlc_from_lengths(VLC *vlc, int nb_bits, int nb_codes,
374  const int8_t *lens, int lens_wrap,
375  const void *symbols, int symbols_wrap, int symbols_size,
376  int offset, int flags, void *logctx)
377 {
378  VLCcode localbuf[LOCALBUF_ELEMS], *buf = localbuf;
379  uint64_t code;
380  int ret, j, len_max = FFMIN(32, 3 * nb_bits);
381 
382  ret = vlc_common_init(vlc, nb_bits, nb_codes, &buf, flags);
383  if (ret < 0)
384  return ret;
385 
386  j = code = 0;
387  for (int i = 0; i < nb_codes; i++, lens += lens_wrap) {
388  int len = *lens;
389  if (len > 0) {
390  unsigned sym;
391 
392  buf[j].bits = len;
393  if (symbols)
394  GET_DATA(sym, symbols, i, symbols_wrap, symbols_size)
395  else
396  sym = i;
397  buf[j].symbol = sym + offset;
398  buf[j++].code = code;
399  } else if (len < 0) {
400  len = -len;
401  } else
402  continue;
403  if (len > len_max || code & ((1U << (32 - len)) - 1)) {
404  av_log(logctx, AV_LOG_ERROR, "Invalid VLC (length %u)\n", len);
405  goto fail;
406  }
407  code += 1U << (32 - len);
408  if (code > UINT32_MAX + 1ULL) {
409  av_log(logctx, AV_LOG_ERROR, "Overdetermined VLC tree\n");
410  goto fail;
411  }
412  }
413  return vlc_common_end(vlc, nb_bits, j, buf, flags, localbuf);
414 fail:
415  if (buf != localbuf)
416  av_free(buf);
417  return AVERROR_INVALIDDATA;
418 }
419 
420 void ff_free_vlc(VLC *vlc)
421 {
422  av_freep(&vlc->table);
423 }
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: bitstream.c:184
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
bitswap_32
static av_always_inline uint32_t bitswap_32(uint32_t x)
Definition: mathops.h:243
INIT_VLC_OUTPUT_LE
#define INIT_VLC_OUTPUT_LE
Definition: vlc.h:93
put_bits
static void put_bits(Jpeg2000EncoderContext *s, int val, int n)
put n times val bit
Definition: j2kenc.c:220
index
fg index
Definition: ffmpeg_filter.c:167
b
#define b
Definition: input.c:40
table
static const uint16_t table[]
Definition: prosumer.c:206
FFMAX
#define FFMAX(a, b)
Definition: macros.h:47
COPY
#define COPY(condition)
ff_copy_bits
void ff_copy_bits(PutBitContext *pb, const uint8_t *src, int length)
Copy the content of src to the bitstream.
Definition: bitstream.c:69
VLC_TYPE
#define VLC_TYPE
Definition: vlc.h:24
U
#define U(x)
Definition: vp56_arith.h:37
fail
#define fail()
Definition: checkasm.h:128
put_bits_left
static int put_bits_left(PutBitContext *s)
Definition: put_bits.h:124
avassert.h
AV_LOG_ERROR
#define AV_LOG_ERROR
Something went wrong and cannot losslessly be recovered.
Definition: log.h:180
intreadwrite.h
bits
uint8_t bits
Definition: vp3data.h:141
av_assert0
#define av_assert0(cond)
assert() equivalent, that is always enabled.
Definition: avassert.h:37
vlc_common_init
static int vlc_common_init(VLC *vlc, int nb_bits, int nb_codes, VLCcode **buf, int flags)
Definition: bitstream.c:145
ff_put_string
void ff_put_string(PutBitContext *pb, const char *string, int terminate_string)
Put the string string in the bitstream.
Definition: bitstream.c:59
ff_free_vlc
void ff_free_vlc(VLC *vlc)
Definition: bitstream.c:420
LOCALBUF_ELEMS
#define LOCALBUF_ELEMS
Definition: bitstream.c:135
PutBitContext
Definition: put_bits.h:49
av_realloc_f
#define av_realloc_f(p, o, n)
Definition: tableprint_vlc.h:33
NULL
#define NULL
Definition: coverity.c:32
AVERROR_PATCHWELCOME
#define AVERROR_PATCHWELCOME
Not yet implemented in FFmpeg, patches welcome.
Definition: error.h:64
ff_log2_run
const uint8_t ff_log2_run[41]
Definition: bitstream.c:50
mathops.h
INIT_VLC_USE_NEW_STATIC
#define INIT_VLC_USE_NEW_STATIC
Definition: vlc.h:95
error.h
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: bitstream.c:317
VLCcode
Definition: bitstream.c:137
ff_dlog
#define ff_dlog(a,...)
Definition: tableprint_vlc.h:29
VLC::table_allocated
int table_allocated
Definition: vlc.h:29
qsort.h
GET_DATA
#define GET_DATA(v, table, i, wrap, size)
Definition: bitstream.c:96
size
int size
Definition: twinvq_data.h:10344
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:76
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
log.h
i
#define i(width, name, range_min, range_max)
Definition: cbs_h2645.c:271
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
put_bits_count
static int put_bits_count(PutBitContext *s)
Definition: put_bits.h:79
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
internal.h
av_malloc_array
#define av_malloc_array(a, b)
Definition: tableprint_vlc.h:32
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: bitstream.c:373
common.h
VLCcode::bits
uint8_t bits
Definition: bitstream.c:138
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: bitstream.c:142
len
int len
Definition: vorbis_enc_data.h:426
VLC::bits
int bits
Definition: vlc.h:27
alloc_table
static int alloc_table(VLC *vlc, int size, int use_static)
Definition: bitstream.c:115
ret
ret
Definition: filter_design.txt:187
INIT_VLC_STATIC_OVERLONG
#define INIT_VLC_STATIC_OVERLONG
Definition: vlc.h:96
bswap.h
put_bits_ptr
static uint8_t * put_bits_ptr(PutBitContext *s)
Return the pointer to the byte where the bitstream writer will put the next bit.
Definition: put_bits.h:369
VLC
Definition: vlc.h:26
skip_put_bytes
static void skip_put_bytes(PutBitContext *s, int n)
Skip the given number of bytes.
Definition: put_bits.h:378
VLC::table_size
int table_size
Definition: vlc.h:29
mem.h
avpriv_request_sample
#define avpriv_request_sample(...)
Definition: tableprint_vlc.h:37
flush_put_bits
static void flush_put_bits(PutBitContext *s)
Pad the end of the output stream with zeros.
Definition: put_bits.h:142
av_free
#define av_free(p)
Definition: tableprint_vlc.h:34
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: bitstream.c:273
av_freep
#define av_freep(p)
Definition: tableprint_vlc.h:35
src
INIT_CLIP pixel * src
Definition: h264pred_template.c:418
compare_vlcspec
static int compare_vlcspec(const void *a, const void *b)
Definition: bitstream.c:165
vlc.h
flags
#define flags(name, subs,...)
Definition: cbs_av1.c:561
av_log
#define av_log(a,...)
Definition: tableprint_vlc.h:28
AVERROR_INVALIDDATA
#define AVERROR_INVALIDDATA
Invalid data found when processing input.
Definition: error.h:61
VLCcode::symbol
VLC_TYPE symbol
Definition: bitstream.c:139
put_bits.h
VLC::table
VLC_TYPE(* table)[2]
code, bits
Definition: vlc.h:28
AV_RB16
uint64_t_TMPL AV_WL64 unsigned int_TMPL AV_WL32 unsigned int_TMPL AV_WL24 unsigned int_TMPL AV_WL16 uint64_t_TMPL AV_WB64 unsigned int_TMPL AV_WB32 unsigned int_TMPL AV_WB24 unsigned int_TMPL AV_RB16
Definition: bytestream.h:98