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