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  table_size = 1 << table_nb_bits;
166  if (table_nb_bits > 30)
167  return AVERROR(EINVAL);
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  ff_dlog(NULL, "%4x: code=%d n=%d\n", j, i, n);
192  if (bits != 0 && bits != n) {
193  av_log(NULL, AV_LOG_ERROR, "incorrect codes\n");
194  return AVERROR_INVALIDDATA;
195  }
196  table[j][1] = n; //bits
197  table[j][0] = symbol;
198  j += inc;
199  }
200  } else {
201  /* fill auxiliary table recursively */
202  n -= table_nb_bits;
203  code_prefix = code >> (32 - table_nb_bits);
204  subtable_bits = n;
205  codes[i].bits = n;
206  codes[i].code = code << table_nb_bits;
207  for (k = i+1; k < nb_codes; k++) {
208  n = codes[k].bits - table_nb_bits;
209  if (n <= 0)
210  break;
211  code = codes[k].code;
212  if (code >> (32 - table_nb_bits) != code_prefix)
213  break;
214  codes[k].bits = n;
215  codes[k].code = code << table_nb_bits;
216  subtable_bits = FFMAX(subtable_bits, n);
217  }
218  subtable_bits = FFMIN(subtable_bits, table_nb_bits);
219  j = (flags & INIT_VLC_LE) ? bitswap_32(code_prefix) >> (32 - table_nb_bits) : code_prefix;
220  table[j][1] = -subtable_bits;
221  ff_dlog(NULL, "%4x: n=%d (subtable)\n",
222  j, codes[i].bits + table_nb_bits);
223  index = build_table(vlc, subtable_bits, k-i, codes+i, flags);
224  if (index < 0)
225  return index;
226  /* note: realloc has been done, so reload tables */
227  table = (volatile VLC_TYPE (*)[2])&vlc->table[table_index];
228  table[j][0] = index; //code
229  i = k-1;
230  }
231  }
232 
233  for (i = 0; i < table_size; i++) {
234  if (table[i][1] == 0) //bits
235  table[i][0] = -1; //codes
236  }
237 
238  return table_index;
239 }
240 
241 
242 /* Build VLC decoding tables suitable for use with get_vlc().
243 
244  'nb_bits' sets the decoding table size (2^nb_bits) entries. The
245  bigger it is, the faster is the decoding. But it should not be too
246  big to save memory and L1 cache. '9' is a good compromise.
247 
248  'nb_codes' : number of vlcs codes
249 
250  'bits' : table which gives the size (in bits) of each vlc code.
251 
252  'codes' : table which gives the bit pattern of of each vlc code.
253 
254  'symbols' : table which gives the values to be returned from get_vlc().
255 
256  'xxx_wrap' : give the number of bytes between each entry of the
257  'bits' or 'codes' tables.
258 
259  'xxx_size' : gives the number of bytes of each entry of the 'bits'
260  or 'codes' tables. Currently 1,2 and 4 are supported.
261 
262  'wrap' and 'size' make it possible to use any memory configuration and types
263  (byte/word/long) to store the 'bits', 'codes', and 'symbols' tables.
264 
265  'use_static' should be set to 1 for tables, which should be freed
266  with av_free_static(), 0 if ff_free_vlc() will be used.
267 */
268 int ff_init_vlc_sparse(VLC *vlc_arg, int nb_bits, int nb_codes,
269  const void *bits, int bits_wrap, int bits_size,
270  const void *codes, int codes_wrap, int codes_size,
271  const void *symbols, int symbols_wrap, int symbols_size,
272  int flags)
273 {
274  VLCcode *buf;
275  int i, j, ret;
276  VLCcode localbuf[1500]; // the maximum currently needed is 1296 by rv34
277  VLC localvlc, *vlc;
278 
279  vlc = vlc_arg;
280  vlc->bits = nb_bits;
281  if (flags & INIT_VLC_USE_NEW_STATIC) {
282  av_assert0(nb_codes + 1 <= FF_ARRAY_ELEMS(localbuf));
283  buf = localbuf;
284  localvlc = *vlc_arg;
285  vlc = &localvlc;
286  vlc->table_size = 0;
287  } else {
288  vlc->table = NULL;
289  vlc->table_allocated = 0;
290  vlc->table_size = 0;
291 
292  buf = av_malloc_array((nb_codes + 1), sizeof(VLCcode));
293  if (!buf)
294  return AVERROR(ENOMEM);
295  }
296 
297 
298  av_assert0(symbols_size <= 2 || !symbols);
299  j = 0;
300 #define COPY(condition)\
301  for (i = 0; i < nb_codes; i++) { \
302  GET_DATA(buf[j].bits, bits, i, bits_wrap, bits_size); \
303  if (!(condition)) \
304  continue; \
305  if (buf[j].bits > 3*nb_bits || buf[j].bits>32) { \
306  av_log(NULL, AV_LOG_ERROR, "Too long VLC (%d) in init_vlc\n", buf[j].bits);\
307  if (!(flags & INIT_VLC_USE_NEW_STATIC)) \
308  av_free(buf); \
309  return AVERROR(EINVAL); \
310  } \
311  GET_DATA(buf[j].code, codes, i, codes_wrap, codes_size); \
312  if (buf[j].code >= (1LL<<buf[j].bits)) { \
313  av_log(NULL, AV_LOG_ERROR, "Invalid code %"PRIx32" for %d in " \
314  "init_vlc\n", buf[j].code, i); \
315  if (!(flags & INIT_VLC_USE_NEW_STATIC)) \
316  av_free(buf); \
317  return AVERROR(EINVAL); \
318  } \
319  if (flags & INIT_VLC_LE) \
320  buf[j].code = bitswap_32(buf[j].code); \
321  else \
322  buf[j].code <<= 32 - buf[j].bits; \
323  if (symbols) \
324  GET_DATA(buf[j].symbol, symbols, i, symbols_wrap, symbols_size) \
325  else \
326  buf[j].symbol = i; \
327  j++; \
328  }
329  COPY(buf[j].bits > nb_bits);
330  // qsort is the slowest part of init_vlc, and could probably be improved or avoided
331  AV_QSORT(buf, j, struct VLCcode, compare_vlcspec);
332  COPY(buf[j].bits && buf[j].bits <= nb_bits);
333  nb_codes = j;
334 
335  ret = build_table(vlc, nb_bits, nb_codes, buf, flags);
336 
337  if (flags & INIT_VLC_USE_NEW_STATIC) {
338  if(vlc->table_size != vlc->table_allocated)
339  av_log(NULL, AV_LOG_ERROR, "needed %d had %d\n", vlc->table_size, vlc->table_allocated);
340 
341  av_assert0(ret >= 0);
342  *vlc_arg = *vlc;
343  } else {
344  av_free(buf);
345  if (ret < 0) {
346  av_freep(&vlc->table);
347  return ret;
348  }
349  }
350  return 0;
351 }
352 
353 
354 void ff_free_vlc(VLC *vlc)
355 {
356  av_freep(&vlc->table);
357 }
#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:208
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:268
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 src
Definition: vp8dsp.c:254
#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:101
#define av_log(a,...)
static const uint16_t table[]
Definition: prosumer.c:201
#define AV_LOG_ERROR
Something went wrong and cannot losslessly be recovered.
Definition: log.h:176
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
static int put_bits_left(PutBitContext *s)
Definition: put_bits.h:93
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:115
#define FFMAX(a, b)
Definition: common.h:94
Definition: vlc.h:26
static int put_bits_count(PutBitContext *s)
Definition: put_bits.h:85
#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:333
#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
int n
Definition: avisynth_c.h:684
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
int table_allocated
Definition: vlc.h:29
Libavcodec external API header.
int bit_left
Definition: put_bits.h:37
void * buf
Definition: avisynth_c.h:690
int index
Definition: gxfenc.c:89
#define flags(name, subs,...)
Definition: cbs_av1.c:606
common internal api header.
static void flush_put_bits(PutBitContext *s)
Pad the end of the output stream with zeros.
Definition: put_bits.h:101
#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:354
#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)
static int alloc_table(VLC *vlc, int size, int use_static)
Definition: bitstream.c:110
bitstream writer API