FFmpeg  2.8.17
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Modules 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 "avcodec.h"
34 #include "internal.h"
35 #include "mathops.h"
36 #include "get_bits.h"
37 #include "put_bits.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  default: \
102  v = *(const uint32_t *)ptr; \
103  break; \
104  } \
105 }
106 
107 
108 static int alloc_table(VLC *vlc, int size, int use_static)
109 {
110  int index = vlc->table_size;
111 
112  vlc->table_size += size;
113  if (vlc->table_size > vlc->table_allocated) {
114  if (use_static)
115  abort(); // cannot do anything, init_vlc() is used with too little memory
116  vlc->table_allocated += (1 << vlc->bits);
117  vlc->table = av_realloc_f(vlc->table, vlc->table_allocated, sizeof(VLC_TYPE) * 2);
118  if (!vlc->table) {
119  vlc->table_allocated = 0;
120  vlc->table_size = 0;
121  return AVERROR(ENOMEM);
122  }
123  memset(vlc->table + vlc->table_allocated - (1 << vlc->bits), 0, sizeof(VLC_TYPE) * 2 << vlc->bits);
124  }
125  return index;
126 }
127 
128 static av_always_inline uint32_t bitswap_32(uint32_t x)
129 {
130  return (uint32_t)ff_reverse[ x & 0xFF] << 24 |
131  (uint32_t)ff_reverse[(x >> 8) & 0xFF] << 16 |
132  (uint32_t)ff_reverse[(x >> 16) & 0xFF] << 8 |
133  (uint32_t)ff_reverse[ x >> 24];
134 }
135 
136 typedef struct VLCcode {
138  uint16_t symbol;
139  /** codeword, with the first bit-to-be-read in the msb
140  * (even if intended for a little-endian bitstream reader) */
141  uint32_t code;
142 } VLCcode;
143 
144 static int compare_vlcspec(const void *a, const void *b)
145 {
146  const VLCcode *sa = a, *sb = b;
147  return (sa->code >> 1) - (sb->code >> 1);
148 }
149 /**
150  * Build VLC decoding tables suitable for use with get_vlc().
151  *
152  * @param vlc the context to be initted
153  *
154  * @param table_nb_bits max length of vlc codes to store directly in this table
155  * (Longer codes are delegated to subtables.)
156  *
157  * @param nb_codes number of elements in codes[]
158  *
159  * @param codes descriptions of the vlc codes
160  * These must be ordered such that codes going into the same subtable are contiguous.
161  * Sorting by VLCcode.code is sufficient, though not necessary.
162  */
163 static int build_table(VLC *vlc, int table_nb_bits, int nb_codes,
164  VLCcode *codes, int flags)
165 {
166  int table_size, table_index, index, code_prefix, symbol, subtable_bits;
167  int i, j, k, n, nb, inc;
168  uint32_t code;
169  volatile VLC_TYPE (* volatile table)[2]; // the double volatile is needed to prevent a internal compiler error in gcc 4.2
170 
171  table_size = 1 << table_nb_bits;
172  if (table_nb_bits > 30)
173  return -1;
174  table_index = alloc_table(vlc, table_size, flags & INIT_VLC_USE_NEW_STATIC);
175  ff_dlog(NULL, "new table index=%d size=%d\n", table_index, table_size);
176  if (table_index < 0)
177  return table_index;
178  table = (volatile VLC_TYPE (*)[2])&vlc->table[table_index];
179 
180  /* first pass: map codes and compute auxiliary table sizes */
181  for (i = 0; i < nb_codes; i++) {
182  n = codes[i].bits;
183  code = codes[i].code;
184  symbol = codes[i].symbol;
185  ff_dlog(NULL, "i=%d n=%d code=0x%x\n", i, n, code);
186  if (n <= table_nb_bits) {
187  /* no need to add another table */
188  j = code >> (32 - table_nb_bits);
189  nb = 1 << (table_nb_bits - n);
190  inc = 1;
191  if (flags & INIT_VLC_LE) {
192  j = bitswap_32(code);
193  inc = 1 << n;
194  }
195  for (k = 0; k < nb; k++) {
196  int bits = table[j][1];
197  int oldsym = table[j][0];
198  ff_dlog(NULL, "%4x: code=%d n=%d\n", j, i, n);
199  if ((bits || oldsym) && (bits != n || oldsym != symbol)) {
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  if (table[j][0] != index) {
237  avpriv_request_sample(NULL, "strange codes");
238  return AVERROR_PATCHWELCOME;
239  }
240  i = k-1;
241  }
242  }
243 
244  for (i = 0; i < table_size; i++) {
245  if (table[i][1] == 0) //bits
246  table[i][0] = -1; //codes
247  }
248 
249  return table_index;
250 }
251 
252 
253 /* Build VLC decoding tables suitable for use with get_vlc().
254 
255  'nb_bits' set the decoding table size (2^nb_bits) entries. The
256  bigger it is, the faster is the decoding. But it should not be too
257  big to save memory and L1 cache. '9' is a good compromise.
258 
259  'nb_codes' : number of vlcs codes
260 
261  'bits' : table which gives the size (in bits) of each vlc code.
262 
263  'codes' : table which gives the bit pattern of of each vlc code.
264 
265  'symbols' : table which gives the values to be returned from get_vlc().
266 
267  'xxx_wrap' : give the number of bytes between each entry of the
268  'bits' or 'codes' tables.
269 
270  'xxx_size' : gives the number of bytes of each entry of the 'bits'
271  or 'codes' tables.
272 
273  'wrap' and 'size' make it possible to use any memory configuration and types
274  (byte/word/long) to store the 'bits', 'codes', and 'symbols' tables.
275 
276  'use_static' should be set to 1 for tables, which should be freed
277  with av_free_static(), 0 if ff_free_vlc() will be used.
278 */
279 int ff_init_vlc_sparse(VLC *vlc_arg, int nb_bits, int nb_codes,
280  const void *bits, int bits_wrap, int bits_size,
281  const void *codes, int codes_wrap, int codes_size,
282  const void *symbols, int symbols_wrap, int symbols_size,
283  int flags)
284 {
285  VLCcode *buf;
286  int i, j, ret;
287  VLCcode localbuf[1500]; // the maximum currently needed is 1296 by rv34
288  VLC localvlc, *vlc;
289 
290  vlc = vlc_arg;
291  vlc->bits = nb_bits;
292  if (flags & INIT_VLC_USE_NEW_STATIC) {
293  av_assert0(nb_codes + 1 <= FF_ARRAY_ELEMS(localbuf));
294  buf = localbuf;
295  localvlc = *vlc_arg;
296  vlc = &localvlc;
297  vlc->table_size = 0;
298  } else {
299  vlc->table = NULL;
300  vlc->table_allocated = 0;
301  vlc->table_size = 0;
302 
303  buf = av_malloc_array((nb_codes + 1), sizeof(VLCcode));
304  if (!buf)
305  return AVERROR(ENOMEM);
306  }
307 
308 
309  av_assert0(symbols_size <= 2 || !symbols);
310  j = 0;
311 #define COPY(condition)\
312  for (i = 0; i < nb_codes; i++) { \
313  GET_DATA(buf[j].bits, bits, i, bits_wrap, bits_size); \
314  if (!(condition)) \
315  continue; \
316  if (buf[j].bits > 3*nb_bits || buf[j].bits>32) { \
317  av_log(NULL, AV_LOG_ERROR, "Too long VLC (%d) in init_vlc\n", buf[j].bits);\
318  if (!(flags & INIT_VLC_USE_NEW_STATIC)) \
319  av_free(buf); \
320  return -1; \
321  } \
322  GET_DATA(buf[j].code, codes, i, codes_wrap, codes_size); \
323  if (buf[j].code >= (1LL<<buf[j].bits)) { \
324  av_log(NULL, AV_LOG_ERROR, "Invalid code in init_vlc\n"); \
325  if (!(flags & INIT_VLC_USE_NEW_STATIC)) \
326  av_free(buf); \
327  return -1; \
328  } \
329  if (flags & INIT_VLC_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(buf[j].bits > nb_bits);
340  // qsort is the slowest part of init_vlc, and could probably be improved or avoided
341  qsort(buf, j, sizeof(VLCcode), compare_vlcspec);
342  COPY(buf[j].bits && buf[j].bits <= 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  av_free(buf);
355  if (ret < 0) {
356  av_freep(&vlc->table);
357  return ret;
358  }
359  }
360  return 0;
361 }
362 
363 
364 void ff_free_vlc(VLC *vlc)
365 {
366  av_freep(&vlc->table);
367 }
#define NULL
Definition: coverity.c:32
const uint8_t ff_log2_run[41]
Definition: bitstream.c:39
int table_size
Definition: get_bits.h:67
const char * s
Definition: avisynth_c.h:631
#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:205
#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:279
const char * b
Definition: vf_curves.c:109
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
#define CONFIG_SMALL
Definition: config.h:490
#define VLC_TYPE
Definition: get_bits.h:62
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:163
#define av_assert0(cond)
assert() equivalent, that is always enabled.
Definition: avassert.h:37
uint8_t bits
Definition: crc.c:295
uint8_t
static av_always_inline uint32_t bitswap_32(uint32_t x)
Definition: bitstream.c:128
#define COPY(condition)
#define ff_dlog(a,...)
bitstream reader API header.
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 AV_RB16
Definition: intreadwrite.h:53
#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:141
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:90
Libavcodec external API header.
Definition: get_bits.h:64
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:92
uint8_t bits
Definition: bitstream.c:137
uint16_t symbol
Definition: bitstream.c:138
int n
Definition: avisynth_c.h:547
static int compare_vlcspec(const void *a, const void *b)
Definition: bitstream.c:144
#define INIT_VLC_USE_NEW_STATIC
Definition: get_bits.h:479
#define FF_ARRAY_ELEMS(a)
int bits
Definition: get_bits.h:65
#define AVERROR_PATCHWELCOME
Not yet implemented in FFmpeg, patches welcome.
Definition: error.h:62
int table_allocated
Definition: get_bits.h:67
AVS_Value src
Definition: avisynth_c.h:482
int bit_left
Definition: put_bits.h:37
void * buf
Definition: avisynth_c.h:553
#define INIT_VLC_LE
Definition: get_bits.h:478
int index
Definition: gxfenc.c:89
static int flags
Definition: cpu.c:47
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
if(ret< 0)
Definition: vf_mcdeint.c:280
#define av_free(p)
VLC_TYPE(* table)[2]
code, bits
Definition: get_bits.h:66
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 av_always_inline
Definition: attributes.h:37
#define av_malloc_array(a, b)
void ff_free_vlc(VLC *vlc)
Definition: bitstream.c:364
for(j=16;j >0;--j)
static int alloc_table(VLC *vlc, int size, int use_static)
Definition: bitstream.c:108
bitstream writer API