Libav
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 Libav.
10  *
11  * Libav 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  * Libav 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 Libav; if not, write to the Free Software
23  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
24  */
25 
31 #include "avcodec.h"
32 #include "mathops.h"
33 #include "get_bits.h"
34 #include "put_bits.h"
35 
36 const uint8_t ff_log2_run[41]={
37  0, 0, 0, 0, 1, 1, 1, 1,
38  2, 2, 2, 2, 3, 3, 3, 3,
39  4, 4, 5, 5, 6, 6, 7, 7,
40  8, 9,10,11,12,13,14,15,
41 16,17,18,19,20,21,22,23,
42 24,
43 };
44 
46 {
47  put_bits(s, s->bit_left & 7, 0);
48 }
49 
50 void avpriv_put_string(PutBitContext *pb, const char *string,
51  int terminate_string)
52 {
53  while (*string) {
54  put_bits(pb, 8, *string);
55  string++;
56  }
57  if (terminate_string)
58  put_bits(pb, 8, 0);
59 }
60 
61 void avpriv_copy_bits(PutBitContext *pb, const uint8_t *src, int length)
62 {
63  int words = length >> 4;
64  int bits = length & 15;
65  int i;
66 
67  if (length == 0)
68  return;
69 
70  if (CONFIG_SMALL || words < 16 || put_bits_count(pb) & 7) {
71  for (i = 0; i < words; i++)
72  put_bits(pb, 16, AV_RB16(src + 2 * i));
73  } else {
74  for (i = 0; put_bits_count(pb) & 31; i++)
75  put_bits(pb, 8, src[i]);
76  flush_put_bits(pb);
77  memcpy(put_bits_ptr(pb), src + i, 2 * words - i);
78  skip_put_bytes(pb, 2 * words - i);
79  }
80 
81  put_bits(pb, bits, AV_RB16(src + 2 * words) >> (16 - bits));
82 }
83 
84 /* VLC decoding */
85 
86 #define GET_DATA(v, table, i, wrap, size) \
87 { \
88  const uint8_t *ptr = (const uint8_t *)table + i * wrap; \
89  switch(size) { \
90  case 1: \
91  v = *(const uint8_t *)ptr; \
92  break; \
93  case 2: \
94  v = *(const uint16_t *)ptr; \
95  break; \
96  default: \
97  v = *(const uint32_t *)ptr; \
98  break; \
99  } \
100 }
101 
102 
103 static int alloc_table(VLC *vlc, int size, int use_static)
104 {
105  int index = vlc->table_size;
106 
107  vlc->table_size += size;
108  if (vlc->table_size > vlc->table_allocated) {
109  int err;
110  if (use_static)
111  return AVERROR_BUG;
112  vlc->table_allocated += (1 << vlc->bits);
113  if ((err = av_reallocp(&vlc->table,
114  sizeof(VLC_TYPE) * 2 *
115  vlc->table_allocated)) < 0) {
116  vlc->table_allocated = 0;
117  vlc->table_size = 0;
118  return err;
119  }
120  }
121  return index;
122 }
123 
124 static av_always_inline uint32_t bitswap_32(uint32_t x)
125 {
126  return (uint32_t)ff_reverse[ x & 0xFF] << 24 |
127  (uint32_t)ff_reverse[(x >> 8) & 0xFF] << 16 |
128  (uint32_t)ff_reverse[(x >> 16) & 0xFF] << 8 |
129  (uint32_t)ff_reverse[ x >> 24];
130 }
131 
132 typedef struct {
134  uint16_t symbol;
137  uint32_t code;
138 } VLCcode;
139 
140 static int compare_vlcspec(const void *a, const void *b)
141 {
142  const VLCcode *sa = a, *sb = b;
143  return (sa->code >> 1) - (sb->code >> 1);
144 }
159 static int build_table(VLC *vlc, int table_nb_bits, int nb_codes,
160  VLCcode *codes, int flags)
161 {
162  int table_size, table_index, index, code_prefix, symbol, subtable_bits;
163  int i, j, k, n, nb, inc;
164  uint32_t code;
165  VLC_TYPE (*table)[2];
166 
167  table_size = 1 << table_nb_bits;
168  table_index = alloc_table(vlc, table_size, flags & INIT_VLC_USE_NEW_STATIC);
169  av_dlog(NULL, "new table index=%d size=%d\n", table_index, table_size);
170  if (table_index < 0)
171  return table_index;
172  table = &vlc->table[table_index];
173 
174  for (i = 0; i < table_size; i++) {
175  table[i][1] = 0; //bits
176  table[i][0] = -1; //codes
177  }
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  av_dlog(NULL, "i=%d n=%d code=0x%x\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_LE) {
191  j = bitswap_32(code);
192  inc = 1 << n;
193  }
194  for (k = 0; k < nb; k++) {
195  av_dlog(NULL, "%4x: code=%d n=%d\n", j, i, n);
196  if (table[j][1] /*bits*/ != 0) {
197  av_log(NULL, AV_LOG_ERROR, "incorrect codes\n");
198  return AVERROR_INVALIDDATA;
199  }
200  table[j][1] = n; //bits
201  table[j][0] = symbol;
202  j += inc;
203  }
204  } else {
205  /* fill auxiliary table recursively */
206  n -= table_nb_bits;
207  code_prefix = code >> (32 - table_nb_bits);
208  subtable_bits = n;
209  codes[i].bits = n;
210  codes[i].code = code << table_nb_bits;
211  for (k = i+1; k < nb_codes; k++) {
212  n = codes[k].bits - table_nb_bits;
213  if (n <= 0)
214  break;
215  code = codes[k].code;
216  if (code >> (32 - table_nb_bits) != code_prefix)
217  break;
218  codes[k].bits = n;
219  codes[k].code = code << table_nb_bits;
220  subtable_bits = FFMAX(subtable_bits, n);
221  }
222  subtable_bits = FFMIN(subtable_bits, table_nb_bits);
223  j = (flags & INIT_VLC_LE) ? bitswap_32(code_prefix) >> (32 - table_nb_bits) : code_prefix;
224  table[j][1] = -subtable_bits;
225  av_dlog(NULL, "%4x: n=%d (subtable)\n",
226  j, codes[i].bits + table_nb_bits);
227  index = build_table(vlc, subtable_bits, k-i, codes+i, flags);
228  if (index < 0)
229  return index;
230  /* note: realloc has been done, so reload tables */
231  table = &vlc->table[table_index];
232  table[j][0] = index; //code
233  i = k-1;
234  }
235  }
236  return table_index;
237 }
238 
239 
240 /* Build VLC decoding tables suitable for use with get_vlc().
241 
242  'nb_bits' set thee decoding table size (2^nb_bits) entries. The
243  bigger it is, the faster is the decoding. But it should not be too
244  big to save memory and L1 cache. '9' is a good compromise.
245 
246  'nb_codes' : number of vlcs codes
247 
248  'bits' : table which gives the size (in bits) of each vlc code.
249 
250  'codes' : table which gives the bit pattern of of each vlc code.
251 
252  'symbols' : table which gives the values to be returned from get_vlc().
253 
254  'xxx_wrap' : give the number of bytes between each entry of the
255  'bits' or 'codes' tables.
256 
257  'xxx_size' : gives the number of bytes of each entry of the 'bits'
258  or 'codes' tables.
259 
260  'wrap' and 'size' allows to use any memory configuration and types
261  (byte/word/long) to store the 'bits', 'codes', and 'symbols' tables.
262 
263  'use_static' should be set to 1 for tables, which should be freed
264  with av_free_static(), 0 if ff_free_vlc() will be used.
265 */
266 int ff_init_vlc_sparse(VLC *vlc, int nb_bits, int nb_codes,
267  const void *bits, int bits_wrap, int bits_size,
268  const void *codes, int codes_wrap, int codes_size,
269  const void *symbols, int symbols_wrap, int symbols_size,
270  int flags)
271 {
272  VLCcode *buf;
273  int i, j, ret;
274 
275  vlc->bits = nb_bits;
276  if (flags & INIT_VLC_USE_NEW_STATIC) {
277  if (vlc->table_size && vlc->table_size == vlc->table_allocated) {
278  return 0;
279  } else if (vlc->table_size) {
280  return AVERROR_BUG;
281  }
282  } else {
283  vlc->table = NULL;
284  vlc->table_allocated = 0;
285  vlc->table_size = 0;
286  }
287 
288  av_dlog(NULL, "build table nb_codes=%d\n", nb_codes);
289 
290  buf = av_malloc((nb_codes + 1) * sizeof(VLCcode));
291  if (!buf)
292  return AVERROR(ENOMEM);
293 
294  assert(symbols_size <= 2 || !symbols);
295  j = 0;
296 #define COPY(condition) \
297  for (i = 0; i < nb_codes; i++) { \
298  GET_DATA(buf[j].bits, bits, i, bits_wrap, bits_size); \
299  if (!(condition)) \
300  continue; \
301  GET_DATA(buf[j].code, codes, i, codes_wrap, codes_size); \
302  if (flags & INIT_VLC_LE) \
303  buf[j].code = bitswap_32(buf[j].code); \
304  else \
305  buf[j].code <<= 32 - buf[j].bits; \
306  if (symbols) \
307  GET_DATA(buf[j].symbol, symbols, i, symbols_wrap, symbols_size) \
308  else \
309  buf[j].symbol = i; \
310  j++; \
311  }
312  COPY(buf[j].bits > nb_bits);
313  // qsort is the slowest part of init_vlc, and could probably be improved or avoided
314  qsort(buf, j, sizeof(VLCcode), compare_vlcspec);
315  COPY(buf[j].bits && buf[j].bits <= nb_bits);
316  nb_codes = j;
317 
318  ret = build_table(vlc, nb_bits, nb_codes, buf, flags);
319 
320  av_free(buf);
321  if (ret < 0) {
322  av_freep(&vlc->table);
323  return ret;
324  }
325  if ((flags & INIT_VLC_USE_NEW_STATIC) &&
326  vlc->table_size != vlc->table_allocated)
327  av_log(NULL, AV_LOG_ERROR, "needed %d had %d\n",
328  vlc->table_size, vlc->table_allocated);
329  return 0;
330 }
331 
332 
333 void ff_free_vlc(VLC *vlc)
334 {
335  av_freep(&vlc->table);
336 }
const uint8_t ff_log2_run[41]
Definition: bitstream.c:36
void * av_malloc(size_t size)
Allocate a block of size bytes with alignment suitable for all memory accesses (including vectors if ...
Definition: mem.c:62
int table_size
Definition: get_bits.h:67
#define AVERROR_INVALIDDATA
Invalid data found when processing input.
Definition: error.h:54
int size
void avpriv_copy_bits(PutBitContext *pb, const uint8_t *src, int length)
Copy the content of src to the bitstream.
Definition: bitstream.c:61
void avpriv_align_put_bits(PutBitContext *s)
Pad the bitstream with zeros up to the next byte boundary.
Definition: bitstream.c:45
#define VLC_TYPE
Definition: get_bits.h:62
av_dlog(ac->avr,"%d samples - audio_convert: %s to %s (%s)\n", len, av_get_sample_fmt_name(ac->in_fmt), av_get_sample_fmt_name(ac->out_fmt), use_generic?ac->func_descr_generic:ac->func_descr)
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:159
void av_freep(void *arg)
Free a memory block which has been allocated with av_malloc(z)() or av_realloc() and set the pointer ...
Definition: mem.c:198
int ff_init_vlc_sparse(VLC *vlc, 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:266
uint8_t bits
Definition: crc.c:251
uint8_t
static av_always_inline uint32_t bitswap_32(uint32_t x)
Definition: bitstream.c:124
#define b
Definition: input.c:52
#define COPY(condition)
int av_reallocp(void *ptr, size_t size)
Allocate or reallocate a block of memory.
Definition: mem.c:140
static int flags
Definition: log.c:44
bitstream reader API header.
#define AV_LOG_ERROR
Something went wrong and cannot losslessly be recovered.
Definition: log.h:123
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:199
void av_free(void *ptr)
Free a memory block which has been allocated with av_malloc(z)() or av_realloc(). ...
Definition: mem.c:186
#define AV_RB16
Definition: intreadwrite.h:53
#define AVERROR(e)
Definition: error.h:43
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:137
void av_log(void *avcl, int level, const char *fmt,...)
Definition: log.c:169
static void put_bits(PutBitContext *s, int n, unsigned int value)
Write up to 31 bits into a bitstream.
Definition: put_bits.h:134
#define FFMAX(a, b)
Definition: common.h:55
Definition: get_bits.h:64
static int put_bits_count(PutBitContext *s)
Definition: put_bits.h:67
#define CONFIG_SMALL
Definition: config.h:364
static void skip_put_bytes(PutBitContext *s, int n)
Skip the given number of bytes.
Definition: put_bits.h:208
#define FFMIN(a, b)
Definition: common.h:57
uint8_t bits
Definition: bitstream.c:133
uint16_t symbol
Definition: bitstream.c:134
static int compare_vlcspec(const void *a, const void *b)
Definition: bitstream.c:140
#define INIT_VLC_USE_NEW_STATIC
Definition: get_bits.h:441
int bits
Definition: get_bits.h:65
int table_allocated
Definition: get_bits.h:67
NULL
Definition: eval.c:55
Libavcodec external API header.
int bit_left
Definition: put_bits.h:37
#define AVERROR_BUG
Bug detected, please report the issue.
Definition: error.h:60
#define INIT_VLC_LE
Definition: get_bits.h:440
int index
Definition: gxfenc.c:72
static void flush_put_bits(PutBitContext *s)
Pad the end of the output stream with zeros.
Definition: put_bits.h:83
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:50
#define av_always_inline
Definition: attributes.h:40
const uint8_t ff_reverse[256]
Definition: mathtables.c:72
void ff_free_vlc(VLC *vlc)
Definition: bitstream.c:333
static int alloc_table(VLC *vlc, int size, int use_static)
Definition: bitstream.c:103
bitstream writer API