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 "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  ff_dlog(NULL, "%4x: code=%d n=%d\n", j, i, n);
198  if (bits != 0 && bits != n) {
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_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  i = k-1;
236  }
237  }
238 
239  for (i = 0; i < table_size; i++) {
240  if (table[i][1] == 0) //bits
241  table[i][0] = -1; //codes
242  }
243 
244  return table_index;
245 }
246 
247 
248 /* Build VLC decoding tables suitable for use with get_vlc().
249 
250  'nb_bits' set the decoding table size (2^nb_bits) entries. The
251  bigger it is, the faster is the decoding. But it should not be too
252  big to save memory and L1 cache. '9' is a good compromise.
253 
254  'nb_codes' : number of vlcs codes
255 
256  'bits' : table which gives the size (in bits) of each vlc code.
257 
258  'codes' : table which gives the bit pattern of of each vlc code.
259 
260  'symbols' : table which gives the values to be returned from get_vlc().
261 
262  'xxx_wrap' : give the number of bytes between each entry of the
263  'bits' or 'codes' tables.
264 
265  'xxx_size' : gives the number of bytes of each entry of the 'bits'
266  or 'codes' tables.
267 
268  'wrap' and 'size' make it possible to use any memory configuration and types
269  (byte/word/long) to store the 'bits', 'codes', and 'symbols' tables.
270 
271  'use_static' should be set to 1 for tables, which should be freed
272  with av_free_static(), 0 if ff_free_vlc() will be used.
273 */
274 int ff_init_vlc_sparse(VLC *vlc_arg, int nb_bits, int nb_codes,
275  const void *bits, int bits_wrap, int bits_size,
276  const void *codes, int codes_wrap, int codes_size,
277  const void *symbols, int symbols_wrap, int symbols_size,
278  int flags)
279 {
280  VLCcode *buf;
281  int i, j, ret;
282  VLCcode localbuf[1500]; // the maximum currently needed is 1296 by rv34
283  VLC localvlc, *vlc;
284 
285  vlc = vlc_arg;
286  vlc->bits = nb_bits;
287  if (flags & INIT_VLC_USE_NEW_STATIC) {
288  av_assert0(nb_codes + 1 <= FF_ARRAY_ELEMS(localbuf));
289  buf = 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  buf = av_malloc_array((nb_codes + 1), sizeof(VLCcode));
299  if (!buf)
300  return AVERROR(ENOMEM);
301  }
302 
303 
304  av_assert0(symbols_size <= 2 || !symbols);
305  j = 0;
306 #define COPY(condition)\
307  for (i = 0; i < nb_codes; i++) { \
308  GET_DATA(buf[j].bits, bits, i, bits_wrap, bits_size); \
309  if (!(condition)) \
310  continue; \
311  if (buf[j].bits > 3*nb_bits || buf[j].bits>32) { \
312  av_log(NULL, AV_LOG_ERROR, "Too long VLC (%d) in init_vlc\n", buf[j].bits);\
313  if (!(flags & INIT_VLC_USE_NEW_STATIC)) \
314  av_free(buf); \
315  return -1; \
316  } \
317  GET_DATA(buf[j].code, codes, i, codes_wrap, codes_size); \
318  if (buf[j].code >= (1LL<<buf[j].bits)) { \
319  av_log(NULL, AV_LOG_ERROR, "Invalid code in init_vlc\n"); \
320  if (!(flags & INIT_VLC_USE_NEW_STATIC)) \
321  av_free(buf); \
322  return -1; \
323  } \
324  if (flags & INIT_VLC_LE) \
325  buf[j].code = bitswap_32(buf[j].code); \
326  else \
327  buf[j].code <<= 32 - buf[j].bits; \
328  if (symbols) \
329  GET_DATA(buf[j].symbol, symbols, i, symbols_wrap, symbols_size) \
330  else \
331  buf[j].symbol = i; \
332  j++; \
333  }
334  COPY(buf[j].bits > nb_bits);
335  // qsort is the slowest part of init_vlc, and could probably be improved or avoided
336  qsort(buf, j, sizeof(VLCcode), compare_vlcspec);
337  COPY(buf[j].bits && buf[j].bits <= nb_bits);
338  nb_codes = j;
339 
340  ret = build_table(vlc, nb_bits, nb_codes, buf, flags);
341 
342  if (flags & INIT_VLC_USE_NEW_STATIC) {
343  if(vlc->table_size != vlc->table_allocated)
344  av_log(NULL, AV_LOG_ERROR, "needed %d had %d\n", vlc->table_size, vlc->table_allocated);
345 
346  av_assert0(ret >= 0);
347  *vlc_arg = *vlc;
348  } else {
349  av_free(buf);
350  if (ret < 0) {
351  av_freep(&vlc->table);
352  return ret;
353  }
354  }
355  return 0;
356 }
357 
358 
359 void ff_free_vlc(VLC *vlc)
360 {
361  av_freep(&vlc->table);
362 }
#define NULL
Definition: coverity.c:32
const uint8_t ff_log2_run[41]
Definition: bitstream.c:39
int table_size
Definition: get_bits.h:66
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:167
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:274
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 VLC_TYPE
Definition: get_bits.h:61
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: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:219
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: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:79
Libavcodec external API header.
Definition: get_bits.h:63
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:228
#define FFMIN(a, b)
Definition: common.h:81
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:474
#define FF_ARRAY_ELEMS(a)
int bits
Definition: get_bits.h:64
int table_allocated
Definition: get_bits.h:66
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:473
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
#define av_free(p)
VLC_TYPE(* table)[2]
code, bits
Definition: get_bits.h:65
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:359
for(j=16;j >0;--j)
static int alloc_table(VLC *vlc, int size, int use_static)
Definition: bitstream.c:108
bitstream writer API