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 
48 #if FF_API_AVPRIV_PUT_BITS
50 {
51  align_put_bits(s);
52 }
54 {
55  ff_copy_bits(pb, src, length);
56 }
57 #endif
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 
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  v = *(const uint32_t *)ptr; \
108  break; \
109  default: \
110  av_assert1(0); \
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 typedef struct VLCcode {
138  /** codeword, with the first bit-to-be-read in the msb
139  * (even if intended for a little-endian bitstream reader) */
140  uint32_t code;
141 } VLCcode;
142 
143 static int compare_vlcspec(const void *a, const void *b)
144 {
145  const VLCcode *sa = a, *sb = b;
146  return (sa->code >> 1) - (sb->code >> 1);
147 }
148 /**
149  * Build VLC decoding tables suitable for use with get_vlc().
150  *
151  * @param vlc the context to be initialized
152  *
153  * @param table_nb_bits max length of vlc codes to store directly in this table
154  * (Longer codes are delegated to subtables.)
155  *
156  * @param nb_codes number of elements in codes[]
157  *
158  * @param codes descriptions of the vlc codes
159  * These must be ordered such that codes going into the same subtable are contiguous.
160  * Sorting by VLCcode.code is sufficient, though not necessary.
161  */
162 static int build_table(VLC *vlc, int table_nb_bits, int nb_codes,
163  VLCcode *codes, int flags)
164 {
165  int table_size, table_index, index, code_prefix, symbol, subtable_bits;
166  int i, j, k, n, nb, inc;
167  uint32_t code;
168  volatile VLC_TYPE (* volatile table)[2]; // the double volatile is needed to prevent an internal compiler error in gcc 4.2
169 
170  if (table_nb_bits > 30)
171  return AVERROR(EINVAL);
172  table_size = 1 << table_nb_bits;
173  table_index = alloc_table(vlc, table_size, flags & INIT_VLC_USE_NEW_STATIC);
174  ff_dlog(NULL, "new table index=%d size=%d\n", table_index, table_size);
175  if (table_index < 0)
176  return table_index;
177  table = (volatile VLC_TYPE (*)[2])&vlc->table[table_index];
178 
179  /* first pass: map codes and compute auxiliary table sizes */
180  for (i = 0; i < nb_codes; i++) {
181  n = codes[i].bits;
182  code = codes[i].code;
183  symbol = codes[i].symbol;
184  ff_dlog(NULL, "i=%d n=%d code=0x%"PRIx32"\n", i, n, code);
185  if (n <= table_nb_bits) {
186  /* no need to add another table */
187  j = code >> (32 - table_nb_bits);
188  nb = 1 << (table_nb_bits - n);
189  inc = 1;
190  if (flags & INIT_VLC_OUTPUT_LE) {
191  j = bitswap_32(code);
192  inc = 1 << n;
193  }
194  for (k = 0; k < nb; k++) {
195  int bits = table[j][1];
196  int oldsym = table[j][0];
197  ff_dlog(NULL, "%4x: code=%d n=%d\n", j, i, n);
198  if ((bits || oldsym) && (bits != n || oldsym != symbol)) {
199  av_log(NULL, AV_LOG_ERROR, "incorrect codes\n");
200  return AVERROR_INVALIDDATA;
201  }
202  table[j][1] = n; //bits
203  table[j][0] = symbol;
204  j += inc;
205  }
206  } else {
207  /* fill auxiliary table recursively */
208  n -= table_nb_bits;
209  code_prefix = code >> (32 - table_nb_bits);
210  subtable_bits = n;
211  codes[i].bits = n;
212  codes[i].code = code << table_nb_bits;
213  for (k = i+1; k < nb_codes; k++) {
214  n = codes[k].bits - table_nb_bits;
215  if (n <= 0)
216  break;
217  code = codes[k].code;
218  if (code >> (32 - table_nb_bits) != code_prefix)
219  break;
220  codes[k].bits = n;
221  codes[k].code = code << table_nb_bits;
222  subtable_bits = FFMAX(subtable_bits, n);
223  }
224  subtable_bits = FFMIN(subtable_bits, table_nb_bits);
225  j = (flags & INIT_VLC_OUTPUT_LE) ? bitswap_32(code_prefix) >> (32 - table_nb_bits) : code_prefix;
226  table[j][1] = -subtable_bits;
227  ff_dlog(NULL, "%4x: n=%d (subtable)\n",
228  j, codes[i].bits + table_nb_bits);
229  index = build_table(vlc, subtable_bits, k-i, codes+i, flags);
230  if (index < 0)
231  return index;
232  /* note: realloc has been done, so reload tables */
233  table = (volatile VLC_TYPE (*)[2])&vlc->table[table_index];
234  table[j][0] = index; //code
235  if (table[j][0] != index) {
236  avpriv_request_sample(NULL, "strange codes");
237  return AVERROR_PATCHWELCOME;
238  }
239  i = k-1;
240  }
241  }
242 
243  for (i = 0; i < table_size; i++) {
244  if (table[i][1] == 0) //bits
245  table[i][0] = -1; //codes
246  }
247 
248  return table_index;
249 }
250 
251 
252 /* Build VLC decoding tables suitable for use with get_vlc().
253 
254  'nb_bits' sets the decoding table size (2^nb_bits) entries. The
255  bigger it is, the faster is the decoding. But it should not be too
256  big to save memory and L1 cache. '9' is a good compromise.
257 
258  'nb_codes' : number of vlcs codes
259 
260  'bits' : table which gives the size (in bits) of each vlc code.
261 
262  'codes' : table which gives the bit pattern of of each vlc code.
263 
264  'symbols' : table which gives the values to be returned from get_vlc().
265 
266  'xxx_wrap' : give the number of bytes between each entry of the
267  'bits' or 'codes' tables.
268 
269  'xxx_size' : gives the number of bytes of each entry of the 'bits'
270  or 'codes' tables. Currently 1,2 and 4 are supported.
271 
272  'wrap' and 'size' make it possible to use any memory configuration and types
273  (byte/word/long) to store the 'bits', 'codes', and 'symbols' tables.
274 */
275 int ff_init_vlc_sparse(VLC *vlc_arg, int nb_bits, int nb_codes,
276  const void *bits, int bits_wrap, int bits_size,
277  const void *codes, int codes_wrap, int codes_size,
278  const void *symbols, int symbols_wrap, int symbols_size,
279  int flags)
280 {
281  VLCcode *buf;
282  int i, j, ret;
283  VLCcode localbuf[1500]; // the maximum currently needed is 1296 by rv34
284  VLC localvlc, *vlc;
285 
286  vlc = vlc_arg;
287  vlc->bits = nb_bits;
288  if (flags & INIT_VLC_USE_NEW_STATIC) {
289  av_assert0(nb_codes <= FF_ARRAY_ELEMS(localbuf));
290  localvlc = *vlc_arg;
291  vlc = &localvlc;
292  vlc->table_size = 0;
293  } else {
294  vlc->table = NULL;
295  vlc->table_allocated = 0;
296  vlc->table_size = 0;
297  }
298  if (nb_codes > FF_ARRAY_ELEMS(localbuf)) {
299  buf = av_malloc_array(nb_codes, sizeof(VLCcode));
300  if (!buf)
301  return AVERROR(ENOMEM);
302  } else
303  buf = localbuf;
304 
305 
306  av_assert0(symbols_size <= 2 || !symbols);
307  j = 0;
308 #define COPY(condition)\
309  for (i = 0; i < nb_codes; i++) { \
310  unsigned len; \
311  GET_DATA(len, bits, i, bits_wrap, bits_size); \
312  if (!(condition)) \
313  continue; \
314  if (len > 3*nb_bits || len > 32) { \
315  av_log(NULL, AV_LOG_ERROR, "Too long VLC (%u) in init_vlc\n", len);\
316  if (buf != localbuf) \
317  av_free(buf); \
318  return AVERROR(EINVAL); \
319  } \
320  buf[j].bits = len; \
321  GET_DATA(buf[j].code, codes, i, codes_wrap, codes_size); \
322  if (buf[j].code >= (1LL<<buf[j].bits)) { \
323  av_log(NULL, AV_LOG_ERROR, "Invalid code %"PRIx32" for %d in " \
324  "init_vlc\n", buf[j].code, i); \
325  if (buf != localbuf) \
326  av_free(buf); \
327  return AVERROR(EINVAL); \
328  } \
329  if (flags & INIT_VLC_INPUT_LE) \
330  buf[j].code = bitswap_32(buf[j].code); \
331  else \
332  buf[j].code <<= 32 - buf[j].bits; \
333  if (symbols) \
334  GET_DATA(buf[j].symbol, symbols, i, symbols_wrap, symbols_size) \
335  else \
336  buf[j].symbol = i; \
337  j++; \
338  }
339  COPY(len > nb_bits);
340  // qsort is the slowest part of init_vlc, and could probably be improved or avoided
341  AV_QSORT(buf, j, struct VLCcode, compare_vlcspec);
342  COPY(len && len <= nb_bits);
343  nb_codes = j;
344 
345  ret = build_table(vlc, nb_bits, nb_codes, buf, flags);
346 
347  if (flags & INIT_VLC_USE_NEW_STATIC) {
348  if(vlc->table_size != vlc->table_allocated)
349  av_log(NULL, AV_LOG_ERROR, "needed %d had %d\n", vlc->table_size, vlc->table_allocated);
350 
351  av_assert0(ret >= 0);
352  *vlc_arg = *vlc;
353  } else {
354  if (buf != localbuf)
355  av_free(buf);
356  if (ret < 0) {
357  av_freep(&vlc->table);
358  return ret;
359  }
360  }
361  return 0;
362 }
363 
364 
365 void ff_free_vlc(VLC *vlc)
366 {
367  av_freep(&vlc->table);
368 }
#define NULL
Definition: coverity.c:32
const uint8_t ff_log2_run[41]
Definition: bitstream.c:39
int table_size
Definition: vlc.h:29
static void align_put_bits(PutBitContext *s)
Pad the bitstream with zeros up to the next byte boundary.
Definition: put_bits.h:393
#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:275
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)
Definition: bitstream.c:53
void avpriv_align_put_bits(PutBitContext *s)
Definition: bitstream.c:49
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:91
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:162
#define av_assert0(cond)
assert() equivalent, that is always enabled.
Definition: avassert.h:37
uint8_t
void ff_copy_bits(PutBitContext *pb, const uint8_t *src, int length)
Copy the content of src to the bitstream.
Definition: bitstream.c:69
#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:349
static int put_bits_left(PutBitContext *s)
Definition: put_bits.h:109
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:140
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:83
#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:358
VLC_TYPE symbol
Definition: bitstream.c:137
#define FFMIN(a, b)
Definition: common.h:96
uint8_t bits
Definition: bitstream.c:136
#define s(width, name)
Definition: cbs_vp9.c:257
static int compare_vlcspec(const void *a, const void *b)
Definition: bitstream.c:143
#define FF_ARRAY_ELEMS(a)
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 index
Definition: gxfenc.c:89
#define flags(name, subs,...)
Definition: cbs_av1.c:560
void ff_put_string(PutBitContext *pb, const char *string, int terminate_string)
Put the string string in the bitstream.
Definition: bitstream.c:59
common internal api header.
static void flush_put_bits(PutBitContext *s)
Pad the end of the output stream with zeros.
Definition: put_bits.h:117
#define INIT_VLC_USE_NEW_STATIC
Definition: vlc.h:60
static const unsigned code_prefix[]
Definition: qdmc.c:76
#define av_free(p)
int len
VLC_TYPE(* table)[2]
code, bits
Definition: vlc.h:28
#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:365
#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:115
#define INIT_VLC_OUTPUT_LE
Definition: vlc.h:58
bitstream writer API