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 "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 
49 {
50  put_bits(s, s->bit_left & 7, 0);
51 }
52 
53 void avpriv_put_string(PutBitContext *pb, const char *string,
54  int terminate_string)
55 {
56  while (*string) {
57  put_bits(pb, 8, *string);
58  string++;
59  }
60  if (terminate_string)
61  put_bits(pb, 8, 0);
62 }
63 
65 {
66  int words = length >> 4;
67  int bits = length & 15;
68  int i;
69 
70  if (length == 0)
71  return;
72 
74 
75  if (CONFIG_SMALL || words < 16 || put_bits_count(pb) & 7) {
76  for (i = 0; i < words; i++)
77  put_bits(pb, 16, AV_RB16(src + 2 * i));
78  } else {
79  for (i = 0; put_bits_count(pb) & 31; i++)
80  put_bits(pb, 8, src[i]);
81  flush_put_bits(pb);
82  memcpy(put_bits_ptr(pb), src + i, 2 * words - i);
83  skip_put_bytes(pb, 2 * words - i);
84  }
85 
86  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 static int alloc_table(VLC *vlc, int size, int use_static)
111 {
112  int index = vlc->table_size;
113 
114  vlc->table_size += size;
115  if (vlc->table_size > vlc->table_allocated) {
116  if (use_static)
117  abort(); // cannot do anything, init_vlc() is used with too little memory
118  vlc->table_allocated += (1 << vlc->bits);
119  vlc->table = av_realloc_f(vlc->table, vlc->table_allocated, sizeof(VLC_TYPE) * 2);
120  if (!vlc->table) {
121  vlc->table_allocated = 0;
122  vlc->table_size = 0;
123  return AVERROR(ENOMEM);
124  }
125  memset(vlc->table + vlc->table_allocated - (1 << vlc->bits), 0, sizeof(VLC_TYPE) * 2 << vlc->bits);
126  }
127  return index;
128 }
129 
130 typedef struct VLCcode {
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 static int compare_vlcspec(const void *a, const void *b)
139 {
140  const VLCcode *sa = a, *sb = b;
141  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 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  if (table_nb_bits > 30)
166  return AVERROR(EINVAL);
167  table_size = 1 << table_nb_bits;
168  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  if (table_index < 0)
171  return table_index;
172  table = (volatile VLC_TYPE (*)[2])&vlc->table[table_index];
173 
174  /* first pass: map codes and compute auxiliary table sizes */
175  for (i = 0; i < nb_codes; i++) {
176  n = codes[i].bits;
177  code = codes[i].code;
178  symbol = codes[i].symbol;
179  ff_dlog(NULL, "i=%d n=%d code=0x%"PRIx32"\n", i, n, code);
180  if (n <= table_nb_bits) {
181  /* no need to add another table */
182  j = code >> (32 - table_nb_bits);
183  nb = 1 << (table_nb_bits - n);
184  inc = 1;
185  if (flags & INIT_VLC_LE) {
186  j = bitswap_32(code);
187  inc = 1 << n;
188  }
189  for (k = 0; k < nb; k++) {
190  int bits = table[j][1];
191  int oldsym = table[j][0];
192  ff_dlog(NULL, "%4x: code=%d n=%d\n", j, i, n);
193  if ((bits || oldsym) && (bits != n || oldsym != symbol)) {
194  av_log(NULL, AV_LOG_ERROR, "incorrect codes\n");
195  return AVERROR_INVALIDDATA;
196  }
197  table[j][1] = n; //bits
198  table[j][0] = symbol;
199  j += inc;
200  }
201  } else {
202  /* fill auxiliary table recursively */
203  n -= table_nb_bits;
204  code_prefix = code >> (32 - table_nb_bits);
205  subtable_bits = n;
206  codes[i].bits = n;
207  codes[i].code = code << table_nb_bits;
208  for (k = i+1; k < nb_codes; k++) {
209  n = codes[k].bits - table_nb_bits;
210  if (n <= 0)
211  break;
212  code = codes[k].code;
213  if (code >> (32 - table_nb_bits) != code_prefix)
214  break;
215  codes[k].bits = n;
216  codes[k].code = code << table_nb_bits;
217  subtable_bits = FFMAX(subtable_bits, n);
218  }
219  subtable_bits = FFMIN(subtable_bits, table_nb_bits);
220  j = (flags & INIT_VLC_LE) ? bitswap_32(code_prefix) >> (32 - table_nb_bits) : code_prefix;
221  table[j][1] = -subtable_bits;
222  ff_dlog(NULL, "%4x: n=%d (subtable)\n",
223  j, codes[i].bits + table_nb_bits);
224  index = build_table(vlc, subtable_bits, k-i, codes+i, flags);
225  if (index < 0)
226  return index;
227  /* note: realloc has been done, so reload tables */
228  table = (volatile VLC_TYPE (*)[2])&vlc->table[table_index];
229  table[j][0] = index; //code
230  if (table[j][0] != index) {
231  avpriv_request_sample(NULL, "strange codes");
232  return AVERROR_PATCHWELCOME;
233  }
234  i = k-1;
235  }
236  }
237 
238  for (i = 0; i < table_size; i++) {
239  if (table[i][1] == 0) //bits
240  table[i][0] = -1; //codes
241  }
242 
243  return table_index;
244 }
245 
246 
247 /* Build VLC decoding tables suitable for use with get_vlc().
248 
249  'nb_bits' sets the decoding table size (2^nb_bits) entries. The
250  bigger it is, the faster is the decoding. But it should not be too
251  big to save memory and L1 cache. '9' is a good compromise.
252 
253  'nb_codes' : number of vlcs codes
254 
255  'bits' : table which gives the size (in bits) of each vlc code.
256 
257  'codes' : table which gives the bit pattern of of each vlc code.
258 
259  'symbols' : table which gives the values to be returned from get_vlc().
260 
261  'xxx_wrap' : give the number of bytes between each entry of the
262  'bits' or 'codes' tables.
263 
264  'xxx_size' : gives the number of bytes of each entry of the 'bits'
265  or 'codes' tables. Currently 1,2 and 4 are supported.
266 
267  'wrap' and 'size' make it possible to use any memory configuration and types
268  (byte/word/long) to store the 'bits', 'codes', and 'symbols' tables.
269 
270  'use_static' should be set to 1 for tables, which should be freed
271  with av_free_static(), 0 if ff_free_vlc() will be used.
272 */
273 int ff_init_vlc_sparse(VLC *vlc_arg, int nb_bits, int nb_codes,
274  const void *bits, int bits_wrap, int bits_size,
275  const void *codes, int codes_wrap, int codes_size,
276  const void *symbols, int symbols_wrap, int symbols_size,
277  int flags)
278 {
279  VLCcode *buf;
280  int i, j, ret;
281  VLCcode localbuf[1500]; // the maximum currently needed is 1296 by rv34
282  VLC localvlc, *vlc;
283 
284  vlc = vlc_arg;
285  vlc->bits = nb_bits;
287  av_assert0(nb_codes + 1 <= FF_ARRAY_ELEMS(localbuf));
288  buf = localbuf;
289  localvlc = *vlc_arg;
290  vlc = &localvlc;
291  vlc->table_size = 0;
292  } else {
293  vlc->table = NULL;
294  vlc->table_allocated = 0;
295  vlc->table_size = 0;
296 
297  buf = av_malloc_array((nb_codes + 1), sizeof(VLCcode));
298  if (!buf)
299  return AVERROR(ENOMEM);
300  }
301 
302 
303  av_assert0(symbols_size <= 2 || !symbols);
304  j = 0;
305 #define COPY(condition)\
306  for (i = 0; i < nb_codes; i++) { \
307  GET_DATA(buf[j].bits, bits, i, bits_wrap, bits_size); \
308  if (!(condition)) \
309  continue; \
310  if (buf[j].bits > 3*nb_bits || buf[j].bits>32) { \
311  av_log(NULL, AV_LOG_ERROR, "Too long VLC (%d) in init_vlc\n", buf[j].bits);\
312  if (!(flags & INIT_VLC_USE_NEW_STATIC)) \
313  av_free(buf); \
314  return AVERROR(EINVAL); \
315  } \
316  GET_DATA(buf[j].code, codes, i, codes_wrap, codes_size); \
317  if (buf[j].code >= (1LL<<buf[j].bits)) { \
318  av_log(NULL, AV_LOG_ERROR, "Invalid code %"PRIx32" for %d in " \
319  "init_vlc\n", buf[j].code, i); \
320  if (!(flags & INIT_VLC_USE_NEW_STATIC)) \
321  av_free(buf); \
322  return AVERROR(EINVAL); \
323  } \
324  if (flags & INIT_VLC_LE) \
325  buf[j].code = bitswap_32(buf[j].code); \
326  else \
327  buf[j].code <<= 32 - buf[j].bits; \
328  if (symbols) \
329  GET_DATA(buf[j].symbol, symbols, i, symbols_wrap, symbols_size) \
330  else \
331  buf[j].symbol = i; \
332  j++; \
333  }
334  COPY(buf[j].bits > nb_bits);
335  // qsort is the slowest part of init_vlc, and could probably be improved or avoided
336  AV_QSORT(buf, j, struct VLCcode, compare_vlcspec);
337  COPY(buf[j].bits && buf[j].bits <= nb_bits);
338  nb_codes = j;
339 
340  ret = build_table(vlc, nb_bits, nb_codes, buf, flags);
341 
343  if(vlc->table_size != vlc->table_allocated)
344  av_log(NULL, AV_LOG_ERROR, "needed %d had %d\n", vlc->table_size, vlc->table_allocated);
345 
346  av_assert0(ret >= 0);
347  *vlc_arg = *vlc;
348  } else {
349  av_free(buf);
350  if (ret < 0) {
351  av_freep(&vlc->table);
352  return ret;
353  }
354  }
355  return 0;
356 }
357 
358 
359 void ff_free_vlc(VLC *vlc)
360 {
361  av_freep(&vlc->table);
362 }
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:157
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
n
int n
Definition: avisynth_c.h:760
put_bits
static void put_bits(Jpeg2000EncoderContext *s, int val, int n)
put n times val bit
Definition: j2kenc.c:208
avpriv_put_string
void avpriv_put_string(PutBitContext *pb, const char *string, int terminate_string)
Put the string string in the bitstream.
Definition: bitstream.c:53
internal.h
b
#define b
Definition: input.c:41
table
static const uint16_t table[]
Definition: prosumer.c:206
INIT_VLC_LE
#define INIT_VLC_LE
Definition: vlc.h:54
COPY
#define COPY(condition)
VLC_TYPE
#define VLC_TYPE
Definition: vlc.h:24
VLCcode::symbol
uint16_t symbol
Definition: bitstream.c:132
put_bits_left
static int put_bits_left(PutBitContext *s)
Definition: put_bits.h:93
src
#define src
Definition: vp8dsp.c:254
avassert.h
AV_LOG_ERROR
#define AV_LOG_ERROR
Something went wrong and cannot losslessly be recovered.
Definition: log.h:176
buf
void * buf
Definition: avisynth_c.h:766
s
#define s(width, name)
Definition: cbs_vp9.c:257
bits
uint8_t bits
Definition: vp3data.h:202
av_assert0
#define av_assert0(cond)
assert() equivalent, that is always enabled.
Definition: avassert.h:37
ff_free_vlc
void ff_free_vlc(VLC *vlc)
Definition: bitstream.c:359
PutBitContext
Definition: put_bits.h:35
if
if(ret)
Definition: filter_design.txt:179
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:62
ff_log2_run
const uint8_t ff_log2_run[41]
Definition: bitstream.c:39
mathops.h
INIT_VLC_USE_NEW_STATIC
#define INIT_VLC_USE_NEW_STATIC
Definition: vlc.h:55
ff_init_vlc_sparse
int ff_init_vlc_sparse(VLC *vlc_arg, 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:273
index
int index
Definition: gxfenc.c:89
for
for(j=16;j >0;--j)
Definition: h264pred_template.c:469
avpriv_copy_bits
void avpriv_copy_bits(PutBitContext *pb, const uint8_t *src, int length)
Copy the content of src to the bitstream.
Definition: bitstream.c:64
VLCcode
Definition: bitstream.c:130
ff_dlog
#define ff_dlog(a,...)
Definition: tableprint_vlc.h:29
avpriv_align_put_bits
void avpriv_align_put_bits(PutBitContext *s)
Pad the bitstream with zeros up to the next byte boundary.
Definition: bitstream.c:48
VLC::table_allocated
int table_allocated
Definition: vlc.h:29
qsort.h
FFMAX
#define FFMAX(a, b)
Definition: common.h:94
size
int size
Definition: twinvq_data.h:11134
FFMIN
#define FFMIN(a, b)
Definition: common.h:96
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
i
#define i(width, name, range_min, range_max)
Definition: cbs_h2645.c:259
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:85
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
av_malloc_array
#define av_malloc_array(a, b)
Definition: tableprint_vlc.h:32
VLCcode::bits
uint8_t bits
Definition: bitstream.c:131
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:135
uint8_t
uint8_t
Definition: audio_convert.c:194
avcodec.h
VLC::bits
int bits
Definition: vlc.h:27
alloc_table
static int alloc_table(VLC *vlc, int size, int use_static)
Definition: bitstream.c:110
ret
ret
Definition: filter_design.txt:187
FF_ARRAY_ELEMS
#define FF_ARRAY_ELEMS(a)
Definition: sinewin_tablegen_template.c:38
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:324
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:333
VLC::table_size
int table_size
Definition: vlc.h:29
avpriv_request_sample
#define avpriv_request_sample(...)
Definition: tableprint_vlc.h:39
flush_put_bits
static void flush_put_bits(PutBitContext *s)
Pad the end of the output stream with zeros.
Definition: put_bits.h:101
av_free
#define av_free(p)
Definition: tableprint_vlc.h:34
av_freep
#define av_freep(p)
Definition: tableprint_vlc.h:35
compare_vlcspec
static int compare_vlcspec(const void *a, const void *b)
Definition: bitstream.c:138
vlc.h
flags
#define flags(name, subs,...)
Definition: cbs_av1.c:565
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:59
length
const char int length
Definition: avisynth_c.h:860
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:94