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 
73  av_assert0(length <= put_bits_left(pb));
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 int ff_init_vlc_sparse(VLC *vlc_arg, int nb_bits, int nb_codes,
271  const void *bits, int bits_wrap, int bits_size,
272  const void *codes, int codes_wrap, int codes_size,
273  const void *symbols, int symbols_wrap, int symbols_size,
274  int flags)
275 {
276  VLCcode *buf;
277  int i, j, ret;
278  VLCcode localbuf[1500]; // the maximum currently needed is 1296 by rv34
279  VLC localvlc, *vlc;
280 
281  vlc = vlc_arg;
282  vlc->bits = nb_bits;
283  if (flags & INIT_VLC_USE_NEW_STATIC) {
284  av_assert0(nb_codes + 1 <= FF_ARRAY_ELEMS(localbuf));
285  localvlc = *vlc_arg;
286  vlc = &localvlc;
287  vlc->table_size = 0;
288  } else {
289  vlc->table = NULL;
290  vlc->table_allocated = 0;
291  vlc->table_size = 0;
292  }
293  if (nb_codes + 1 > FF_ARRAY_ELEMS(localbuf)) {
294  buf = av_malloc_array((nb_codes + 1), sizeof(VLCcode));
295  if (!buf)
296  return AVERROR(ENOMEM);
297  } else
298  buf = localbuf;
299 
300 
301  av_assert0(symbols_size <= 2 || !symbols);
302  j = 0;
303 #define COPY(condition)\
304  for (i = 0; i < nb_codes; i++) { \
305  GET_DATA(buf[j].bits, bits, i, bits_wrap, bits_size); \
306  if (!(condition)) \
307  continue; \
308  if (buf[j].bits > 3*nb_bits || buf[j].bits>32) { \
309  av_log(NULL, AV_LOG_ERROR, "Too long VLC (%d) in init_vlc\n", buf[j].bits);\
310  if (buf != localbuf) \
311  av_free(buf); \
312  return AVERROR(EINVAL); \
313  } \
314  GET_DATA(buf[j].code, codes, i, codes_wrap, codes_size); \
315  if (buf[j].code >= (1LL<<buf[j].bits)) { \
316  av_log(NULL, AV_LOG_ERROR, "Invalid code %"PRIx32" for %d in " \
317  "init_vlc\n", buf[j].code, i); \
318  if (buf != localbuf) \
319  av_free(buf); \
320  return AVERROR(EINVAL); \
321  } \
322  if (flags & INIT_VLC_LE) \
323  buf[j].code = bitswap_32(buf[j].code); \
324  else \
325  buf[j].code <<= 32 - buf[j].bits; \
326  if (symbols) \
327  GET_DATA(buf[j].symbol, symbols, i, symbols_wrap, symbols_size) \
328  else \
329  buf[j].symbol = i; \
330  j++; \
331  }
332  COPY(buf[j].bits > nb_bits);
333  // qsort is the slowest part of init_vlc, and could probably be improved or avoided
334  AV_QSORT(buf, j, struct VLCcode, compare_vlcspec);
335  COPY(buf[j].bits && buf[j].bits <= nb_bits);
336  nb_codes = j;
337 
338  ret = build_table(vlc, nb_bits, nb_codes, buf, flags);
339 
340  if (flags & INIT_VLC_USE_NEW_STATIC) {
341  if(vlc->table_size != vlc->table_allocated)
342  av_log(NULL, AV_LOG_ERROR, "needed %d had %d\n", vlc->table_size, vlc->table_allocated);
343 
344  av_assert0(ret >= 0);
345  *vlc_arg = *vlc;
346  } else {
347  if (buf != localbuf)
348  av_free(buf);
349  if (ret < 0) {
350  av_freep(&vlc->table);
351  return ret;
352  }
353  }
354  return 0;
355 }
356 
357 
358 void ff_free_vlc(VLC *vlc)
359 {
360  av_freep(&vlc->table);
361 }
#define NULL
Definition: coverity.c:32
const uint8_t ff_log2_run[41]
Definition: bitstream.c:39
int table_size
Definition: vlc.h:29
#define AVERROR_INVALIDDATA
Invalid data found when processing input.
Definition: error.h:59
#define av_realloc_f(p, o, n)
static void put_bits(Jpeg2000EncoderContext *s, int val, int n)
put n times val bit
Definition: j2kenc.c:218
#define avpriv_request_sample(...)
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:270
static av_always_inline uint32_t bitswap_32(uint32_t x)
Definition: mathops.h:243
void avpriv_copy_bits(PutBitContext *pb, const uint8_t *src, int length)
Copy the content of src to the bitstream.
Definition: bitstream.c:64
void avpriv_align_put_bits(PutBitContext *s)
Pad the bitstream with zeros up to the next byte boundary.
Definition: bitstream.c:48
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:36
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:87
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
#define av_assert0(cond)
assert() equivalent, that is always enabled.
Definition: avassert.h:37
uint8_t
#define COPY(condition)
#define ff_dlog(a,...)
ptrdiff_t size
Definition: opengl_enc.c:100
#define av_log(a,...)
static const uint16_t table[]
Definition: prosumer.c:206
#define src
Definition: vp8dsp.c:254
#define AV_LOG_ERROR
Something went wrong and cannot losslessly be recovered.
Definition: log.h:194
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:347
static int put_bits_left(PutBitContext *s)
Definition: put_bits.h:107
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
simple assert() macros that are a bit more flexible than ISO C assert().
GLsizei GLsizei * length
Definition: opengl_enc.c:114
uint8_t bits
Definition: vp3data.h:202
#define FFMAX(a, b)
Definition: common.h:94
Definition: vlc.h:26
static int put_bits_count(PutBitContext *s)
Definition: put_bits.h:81
#define b
Definition: input.c:41
static void skip_put_bytes(PutBitContext *s, int n)
Skip the given number of bytes.
Definition: put_bits.h:356
#define FFMIN(a, b)
Definition: common.h:96
uint8_t bits
Definition: bitstream.c:131
uint16_t symbol
Definition: bitstream.c:132
#define s(width, name)
Definition: cbs_vp9.c:257
static int compare_vlcspec(const void *a, const void *b)
Definition: bitstream.c:138
#define FF_ARRAY_ELEMS(a)
#define INIT_VLC_LE
Definition: vlc.h:54
int bits
Definition: vlc.h:27
if(ret)
#define AVERROR_PATCHWELCOME
Not yet implemented in FFmpeg, patches welcome.
Definition: error.h:62
int table_allocated
Definition: vlc.h:29
Libavcodec external API header.
int bit_left
Definition: put_bits.h:51
int index
Definition: gxfenc.c:89
#define flags(name, subs,...)
Definition: cbs_av1.c:560
common internal api header.
static void flush_put_bits(PutBitContext *s)
Pad the end of the output stream with zeros.
Definition: put_bits.h:115
#define INIT_VLC_USE_NEW_STATIC
Definition: vlc.h:55
static const unsigned code_prefix[]
Definition: qdmc.c:76
#define av_free(p)
VLC_TYPE(* table)[2]
code, bits
Definition: vlc.h:28
void avpriv_put_string(PutBitContext *pb, const char *string, int terminate_string)
Put the string string in the bitstream.
Definition: bitstream.c:53
#define av_freep(p)
#define VLC_TYPE
Definition: vlc.h:24
#define av_malloc_array(a, b)
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
void ff_free_vlc(VLC *vlc)
Definition: bitstream.c:358
#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
for(j=16;j >0;--j)
int i
Definition: input.c:407
static int alloc_table(VLC *vlc, int size, int use_static)
Definition: bitstream.c:110
bitstream writer API