FFmpeg
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
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/atomic.h"
32 #include "libavutil/avassert.h"
33 #include "libavutil/qsort.h"
34 #include "avcodec.h"
35 #include "internal.h"
36 #include "mathops.h"
37 #include "put_bits.h"
38 #include "vlc.h"
39 
40 const uint8_t ff_log2_run[41]={
41  0, 0, 0, 0, 1, 1, 1, 1,
42  2, 2, 2, 2, 3, 3, 3, 3,
43  4, 4, 5, 5, 6, 6, 7, 7,
44  8, 9,10,11,12,13,14,15,
45 16,17,18,19,20,21,22,23,
46 24,
47 };
48 
50 {
51  put_bits(s, s->bit_left & 7, 0);
52 }
53 
54 void avpriv_put_string(PutBitContext *pb, const char *string,
55  int terminate_string)
56 {
57  while (*string) {
58  put_bits(pb, 8, *string);
59  string++;
60  }
61  if (terminate_string)
62  put_bits(pb, 8, 0);
63 }
64 
66 {
67  int words = length >> 4;
68  int bits = length & 15;
69  int i;
70 
71  if (length == 0)
72  return;
73 
74  av_assert0(length <= put_bits_left(pb));
75 
76  if (CONFIG_SMALL || words < 16 || put_bits_count(pb) & 7) {
77  for (i = 0; i < words; i++)
78  put_bits(pb, 16, AV_RB16(src + 2 * i));
79  } else {
80  for (i = 0; put_bits_count(pb) & 31; i++)
81  put_bits(pb, 8, src[i]);
82  flush_put_bits(pb);
83  memcpy(put_bits_ptr(pb), src + i, 2 * words - i);
84  skip_put_bytes(pb, 2 * words - i);
85  }
86 
87  put_bits(pb, bits, AV_RB16(src + 2 * words) >> (16 - bits));
88 }
89 
90 /* VLC decoding */
91 
92 #define GET_DATA(v, table, i, wrap, size) \
93 { \
94  const uint8_t *ptr = (const uint8_t *)table + i * wrap; \
95  switch(size) { \
96  case 1: \
97  v = *(const uint8_t *)ptr; \
98  break; \
99  case 2: \
100  v = *(const uint16_t *)ptr; \
101  break; \
102  default: \
103  v = *(const uint32_t *)ptr; \
104  break; \
105  } \
106 }
107 
108 
109 static int alloc_table(VLC *vlc, int size, int use_static)
110 {
111  int index = vlc->table_size;
112 
113  vlc->table_size += size;
114  if (vlc->table_size > vlc->table_allocated) {
115  if (use_static)
116  abort(); // cannot do anything, init_vlc() is used with too little memory
117  vlc->table_allocated += (1 << vlc->bits);
118  vlc->table = av_realloc_f(vlc->table, vlc->table_allocated, sizeof(VLC_TYPE) * 2);
119  if (!vlc->table) {
120  vlc->table_allocated = 0;
121  vlc->table_size = 0;
122  return AVERROR(ENOMEM);
123  }
124  memset(vlc->table + vlc->table_allocated - (1 << vlc->bits), 0, sizeof(VLC_TYPE) * 2 << vlc->bits);
125  }
126  return index;
127 }
128 
129 static av_always_inline uint32_t bitswap_32(uint32_t x)
130 {
131  return (uint32_t)ff_reverse[ x & 0xFF] << 24 |
132  (uint32_t)ff_reverse[(x >> 8) & 0xFF] << 16 |
133  (uint32_t)ff_reverse[(x >> 16) & 0xFF] << 8 |
134  (uint32_t)ff_reverse[ x >> 24];
135 }
136 
137 typedef struct VLCcode {
139  uint16_t symbol;
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 compare_vlcspec(const void *a, const void *b)
146 {
147  const VLCcode *sa = a, *sb = b;
148  return (sa->code >> 1) - (sb->code >> 1);
149 }
150 /**
151  * Build VLC decoding tables suitable for use with get_vlc().
152  *
153  * @param vlc the context to be initialized
154  *
155  * @param table_nb_bits max length of vlc codes to store directly in this table
156  * (Longer codes are delegated to subtables.)
157  *
158  * @param nb_codes number of elements in codes[]
159  *
160  * @param codes descriptions of the vlc codes
161  * These must be ordered such that codes going into the same subtable are contiguous.
162  * Sorting by VLCcode.code is sufficient, though not necessary.
163  */
164 static int build_table(VLC *vlc, int table_nb_bits, int nb_codes,
165  VLCcode *codes, int flags)
166 {
167  int table_size, table_index, index, code_prefix, symbol, subtable_bits;
168  int i, j, k, n, nb, inc;
169  uint32_t code;
170  volatile VLC_TYPE (* volatile table)[2]; // the double volatile is needed to prevent an internal compiler error in gcc 4.2
171 
172  table_size = 1 << table_nb_bits;
173  if (table_nb_bits > 30)
174  return -1;
175  table_index = alloc_table(vlc, table_size, flags & INIT_VLC_USE_NEW_STATIC);
176  ff_dlog(NULL, "new table index=%d size=%d\n", table_index, table_size);
177  if (table_index < 0)
178  return table_index;
179  table = (volatile VLC_TYPE (*)[2])&vlc->table[table_index];
180 
181  /* first pass: map codes and compute auxiliary table sizes */
182  for (i = 0; i < nb_codes; i++) {
183  n = codes[i].bits;
184  code = codes[i].code;
185  symbol = codes[i].symbol;
186  ff_dlog(NULL, "i=%d n=%d code=0x%x\n", i, n, code);
187  if (n <= table_nb_bits) {
188  /* no need to add another table */
189  j = code >> (32 - table_nb_bits);
190  nb = 1 << (table_nb_bits - n);
191  inc = 1;
192  if (flags & INIT_VLC_LE) {
193  j = bitswap_32(code);
194  inc = 1 << n;
195  }
196  for (k = 0; k < nb; k++) {
197  int bits = table[j][1];
198  ff_dlog(NULL, "%4x: code=%d n=%d\n", j, i, n);
199  if (bits != 0 && bits != n) {
200  av_log(NULL, AV_LOG_ERROR, "incorrect codes\n");
201  return AVERROR_INVALIDDATA;
202  }
203  table[j][1] = n; //bits
204  table[j][0] = symbol;
205  j += inc;
206  }
207  } else {
208  /* fill auxiliary table recursively */
209  n -= table_nb_bits;
210  code_prefix = code >> (32 - table_nb_bits);
211  subtable_bits = n;
212  codes[i].bits = n;
213  codes[i].code = code << table_nb_bits;
214  for (k = i+1; k < nb_codes; k++) {
215  n = codes[k].bits - table_nb_bits;
216  if (n <= 0)
217  break;
218  code = codes[k].code;
219  if (code >> (32 - table_nb_bits) != code_prefix)
220  break;
221  codes[k].bits = n;
222  codes[k].code = code << table_nb_bits;
223  subtable_bits = FFMAX(subtable_bits, n);
224  }
225  subtable_bits = FFMIN(subtable_bits, table_nb_bits);
226  j = (flags & INIT_VLC_LE) ? bitswap_32(code_prefix) >> (32 - table_nb_bits) : code_prefix;
227  table[j][1] = -subtable_bits;
228  ff_dlog(NULL, "%4x: n=%d (subtable)\n",
229  j, codes[i].bits + table_nb_bits);
230  index = build_table(vlc, subtable_bits, k-i, codes+i, flags);
231  if (index < 0)
232  return index;
233  /* note: realloc has been done, so reload tables */
234  table = (volatile VLC_TYPE (*)[2])&vlc->table[table_index];
235  table[j][0] = index; //code
236  i = k-1;
237  }
238  }
239 
240  for (i = 0; i < table_size; i++) {
241  if (table[i][1] == 0) //bits
242  table[i][0] = -1; //codes
243  }
244 
245  return table_index;
246 }
247 
248 
249 /* Build VLC decoding tables suitable for use with get_vlc().
250 
251  'nb_bits' sets the decoding table size (2^nb_bits) entries. The
252  bigger it is, the faster is the decoding. But it should not be too
253  big to save memory and L1 cache. '9' is a good compromise.
254 
255  'nb_codes' : number of vlcs codes
256 
257  'bits' : table which gives the size (in bits) of each vlc code.
258 
259  'codes' : table which gives the bit pattern of of each vlc code.
260 
261  'symbols' : table which gives the values to be returned from get_vlc().
262 
263  'xxx_wrap' : give the number of bytes between each entry of the
264  'bits' or 'codes' tables.
265 
266  'xxx_size' : gives the number of bytes of each entry of the 'bits'
267  or 'codes' tables.
268 
269  'wrap' and 'size' make it possible to use any memory configuration and types
270  (byte/word/long) to store the 'bits', 'codes', and 'symbols' tables.
271 
272  'use_static' should be set to 1 for tables, which should be freed
273  with av_free_static(), 0 if ff_free_vlc() will be used.
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 + 1 <= FF_ARRAY_ELEMS(localbuf));
290  buf = localbuf;
291  localvlc = *vlc_arg;
292  vlc = &localvlc;
293  vlc->table_size = 0;
294  } else {
295  vlc->table = NULL;
296  vlc->table_allocated = 0;
297  vlc->table_size = 0;
298 
299  buf = av_malloc_array((nb_codes + 1), sizeof(VLCcode));
300  if (!buf)
301  return AVERROR(ENOMEM);
302  }
303 
304 
305  av_assert0(symbols_size <= 2 || !symbols);
306  j = 0;
307 #define COPY(condition)\
308  for (i = 0; i < nb_codes; i++) { \
309  GET_DATA(buf[j].bits, bits, i, bits_wrap, bits_size); \
310  if (!(condition)) \
311  continue; \
312  if (buf[j].bits > 3*nb_bits || buf[j].bits>32) { \
313  av_log(NULL, AV_LOG_ERROR, "Too long VLC (%d) in init_vlc\n", buf[j].bits);\
314  if (!(flags & INIT_VLC_USE_NEW_STATIC)) \
315  av_free(buf); \
316  return -1; \
317  } \
318  GET_DATA(buf[j].code, codes, i, codes_wrap, codes_size); \
319  if (buf[j].code >= (1LL<<buf[j].bits)) { \
320  av_log(NULL, AV_LOG_ERROR, "Invalid code %x for %d in init_vlc\n", buf[j].code, i);\
321  if (!(flags & INIT_VLC_USE_NEW_STATIC)) \
322  av_free(buf); \
323  return -1; \
324  } \
325  if (flags & INIT_VLC_LE) \
326  buf[j].code = bitswap_32(buf[j].code); \
327  else \
328  buf[j].code <<= 32 - buf[j].bits; \
329  if (symbols) \
330  GET_DATA(buf[j].symbol, symbols, i, symbols_wrap, symbols_size) \
331  else \
332  buf[j].symbol = i; \
333  j++; \
334  }
335  COPY(buf[j].bits > nb_bits);
336  // qsort is the slowest part of init_vlc, and could probably be improved or avoided
337  AV_QSORT(buf, j, struct VLCcode, compare_vlcspec);
338  COPY(buf[j].bits && buf[j].bits <= nb_bits);
339  nb_codes = j;
340 
341  ret = build_table(vlc, nb_bits, nb_codes, buf, flags);
342 
343  if (flags & INIT_VLC_USE_NEW_STATIC) {
344  if(vlc->table_size != vlc->table_allocated)
345  av_log(NULL, AV_LOG_ERROR, "needed %d had %d\n", vlc->table_size, vlc->table_allocated);
346 
347  av_assert0(ret >= 0);
348  *vlc_arg = *vlc;
349  } else {
350  av_free(buf);
351  if (ret < 0) {
352  av_freep(&vlc->table);
353  return ret;
354  }
355  }
356  return 0;
357 }
358 
359 
360 void ff_free_vlc(VLC *vlc)
361 {
362  av_freep(&vlc->table);
363 }
#define NULL
Definition: coverity.c:32
const uint8_t ff_log2_run[41]
Definition: bitstream.c:40
int table_size
Definition: vlc.h:29
const char * s
Definition: avisynth_c.h:768
#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:206
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
const char * b
Definition: vf_curves.c:113
void avpriv_copy_bits(PutBitContext *pb, const uint8_t *src, int length)
Copy the content of src to the bitstream.
Definition: bitstream.c:65
void avpriv_align_put_bits(PutBitContext *s)
Pad the bitstream with zeros up to the next byte boundary.
Definition: bitstream.c:49
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:164
#define src
Definition: vp8dsp.c:254
#define av_assert0(cond)
assert() equivalent, that is always enabled.
Definition: avassert.h:37
uint8_t bits
Definition: crc.c:296
uint8_t
static av_always_inline uint32_t bitswap_32(uint32_t x)
Definition: bitstream.c:129
#define COPY(condition)
static int flags
Definition: log.c:57
#define ff_dlog(a,...)
ptrdiff_t size
Definition: opengl_enc.c:101
#define av_log(a,...)
#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:227
static int put_bits_left(PutBitContext *s)
Definition: put_bits.h:93
#define AVERROR(e)
Definition: error.h:43
static const struct endianess table[]
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
const uint8_t ff_reverse[256]
Definition: reverse.c:23
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
static void skip_put_bytes(PutBitContext *s, int n)
Skip the given number of bytes.
Definition: put_bits.h:236
#define FFMIN(a, b)
Definition: common.h:96
uint8_t bits
Definition: bitstream.c:138
uint16_t symbol
Definition: bitstream.c:139
int n
Definition: avisynth_c.h:684
static int compare_vlcspec(const void *a, const void *b)
Definition: bitstream.c:145
#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
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
#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:54
#define av_freep(p)
#define av_always_inline
Definition: attributes.h:39
#define VLC_TYPE
Definition: vlc.h:24
#define av_malloc_array(a, b)
void ff_free_vlc(VLC *vlc)
Definition: bitstream.c:360
#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:109
bitstream writer API