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