3 * Copyright (c) 2000, 2001 Fabrice Bellard
4 * Copyright (c) 2002-2004 Michael Niedermayer <michaelni@gmx.at>
5 * Copyright (c) 2010 Loren Merritt
7 * alternative bitstream reader & writer by Michael Niedermayer <michaelni@gmx.at>
9 * This file is part of FFmpeg.
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.
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.
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
27 * @file libavcodec/bitstream.c
37 const uint8_t ff_log2_run
[32]={
38 0, 0, 0, 0, 1, 1, 1, 1,
39 2, 2, 2, 2, 3, 3, 3, 3,
40 4, 4, 5, 5, 6, 6, 7, 7,
41 8, 9,10,11,12,13,14,15
44 void align_put_bits(PutBitContext
*s
)
46 #ifdef ALT_BITSTREAM_WRITER
47 put_bits(s
,( - s
->index
) & 7,0);
49 put_bits(s
,s
->bit_left
& 7,0);
53 void ff_put_string(PutBitContext
*pb
, const char *string
, int terminate_string
)
56 put_bits(pb
, 8, *string
);
63 void ff_copy_bits(PutBitContext
*pb
, const uint8_t *src
, int length
)
70 /* The following define was just added to make the codec (wma pro) compile */
71 #define CONFIG_SMALL 0
72 if(CONFIG_SMALL
|| words
< 16 || put_bits_count(pb
)&7){
73 for(i
=0; i
<words
; i
++) put_bits(pb
, 16, AV_RB16(src
+ 2*i
));
75 for(i
=0; put_bits_count(pb
)&31; i
++)
76 put_bits(pb
, 8, src
[i
]);
78 memcpy(put_bits_ptr(pb
), src
+i
, 2*words
-i
);
79 skip_put_bytes(pb
, 2*words
-i
);
82 put_bits(pb
, bits
, AV_RB16(src
+ 2*words
)>>(16-bits
));
89 #define GET_DATA(v, table, i, wrap, size) \
91 const uint8_t *ptr = (const uint8_t *)table + i * wrap;\
94 v = *(const uint8_t *)ptr;\
97 v = *(const uint16_t *)ptr;\
100 v = *(const uint32_t *)ptr;\
106 static int alloc_table(VLC
*vlc
, int size
, int use_static
)
109 index
= vlc
->table_size
;
110 vlc
->table_size
+= size
;
111 if (vlc
->table_size
> vlc
->table_allocated
) {
113 return -1; //cant do anything, init_vlc() is used with too little memory
114 vlc
->table_allocated
+= (1 << vlc
->bits
);
115 //vlc->table = av_realloc(vlc->table,
116 // sizeof(VLC_TYPE) * 2 * vlc->table_allocated);
123 static av_always_inline
uint32_t bitswap_32(uint32_t x
) {
124 return av_reverse
[x
&0xFF]<<24
125 | av_reverse
[(x
>>8)&0xFF]<<16
126 | av_reverse
[(x
>>16)&0xFF]<<8
133 /** codeword, with the first bit-to-be-read in the msb
134 * (even if intended for a little-endian bitstream reader) */
138 static int compare_vlcspec(const void *a
, const void *b
)
140 const VLCcode
*sa
=a
, *sb
=b
;
141 return (sa
->code
>> 1) - (sb
->code
>> 1);
145 * Build VLC decoding tables suitable for use with get_vlc().
147 * @param vlc the context to be initted
149 * @param table_nb_bits max length of vlc codes to store directly in this table
150 * (Longer codes are delegated to subtables.)
152 * @param nb_codes number of elements in codes[]
154 * @param codes descriptions of the vlc codes
155 * These must be ordered such that codes going into the same subtable are contiguous.
156 * Sorting by VLCcode.code is sufficient, though not necessary.
158 static int build_table(VLC
*vlc
, int table_nb_bits
, int nb_codes
,
159 VLCcode
*codes
, int flags
)
161 int table_size
, table_index
, index
, code_prefix
, symbol
, subtable_bits
;
162 int i
, j
, k
, n
, nb
, inc
;
164 VLC_TYPE (*table
)[2];
166 table_size
= 1 << table_nb_bits
;
167 table_index
= alloc_table(vlc
, table_size
, flags
& INIT_VLC_USE_NEW_STATIC
);
169 av_log(NULL
,AV_LOG_DEBUG
,"new table index=%d size=%d\n",
170 table_index
, table_size
);
174 table
= &vlc
->table
[table_index
];
176 for (i
= 0; i
< table_size
; i
++) {
177 table
[i
][1] = 0; //bits
178 table
[i
][0] = -1; //codes
181 /* first pass: map codes and compute auxillary table sizes */
182 for (i
= 0; i
< nb_codes
; i
++) {
184 code
= codes
[i
].code
;
185 symbol
= codes
[i
].symbol
;
186 #if defined(DEBUG_VLC) && 0
187 av_log(NULL
,AV_LOG_DEBUG
,"i=%d n=%d code=0x%x\n", i
, n
, code
);
189 if (n
<= table_nb_bits
) {
190 /* no need to add another table */
191 j
= code
>> (32 - table_nb_bits
);
192 nb
= 1 << (table_nb_bits
- n
);
194 if (flags
& INIT_VLC_LE
) {
195 j
= bitswap_32(code
);
198 for (k
= 0; k
< nb
; k
++) {
200 av_log(NULL
, AV_LOG_DEBUG
, "%4x: code=%d n=%d\n",
203 if (table
[j
][1] /*bits*/ != 0) {
204 av_log(NULL
, AV_LOG_ERROR
, "incorrect codes\n");
207 table
[j
][1] = n
; //bits
208 table
[j
][0] = symbol
;
212 /* fill auxiliary table recursively */
214 code_prefix
= code
>> (32 - table_nb_bits
);
217 codes
[i
].code
= code
<< table_nb_bits
;
218 for (k
= i
+1; k
< nb_codes
; k
++) {
219 n
= codes
[k
].bits
- table_nb_bits
;
222 code
= codes
[k
].code
;
223 if (code
>> (32 - table_nb_bits
) != (unsigned)code_prefix
)
226 codes
[k
].code
= code
<< table_nb_bits
;
227 subtable_bits
= FFMAX(subtable_bits
, n
);
229 subtable_bits
= FFMIN(subtable_bits
, table_nb_bits
);
230 j
= (flags
& INIT_VLC_LE
) ? bitswap_32(code_prefix
) >> (32 - table_nb_bits
) : (unsigned)code_prefix
;
231 table
[j
][1] = -subtable_bits
;
233 av_log(NULL
,AV_LOG_DEBUG
,"%4x: n=%d (subtable)\n",
234 j
, codes
[i
].bits
+ table_nb_bits
);
236 index
= build_table(vlc
, subtable_bits
, k
-i
, codes
+i
, flags
);
239 /* note: realloc has been done, so reload tables */
240 table
= &vlc
->table
[table_index
];
241 table
[j
][0] = index
; //code
249 /* Build VLC decoding tables suitable for use with get_vlc().
251 'nb_bits' set thee decoding table size (2^nb_bits) entries. The
252 bigger it is, the faster is the decoding. But it should not be too
253 big to save memory and L1 cache. '9' is a good compromise.
255 'nb_codes' : number of vlcs codes
257 'bits' : table which gives the size (in bits) of each vlc code.
259 'codes' : table which gives the bit pattern of of each vlc code.
261 'symbols' : table which gives the values to be returned from get_vlc().
263 'xxx_wrap' : give the number of bytes between each entry of the
264 'bits' or 'codes' tables.
266 'xxx_size' : gives the number of bytes of each entry of the 'bits'
269 'wrap' and 'size' allows to use any memory configuration and types
270 (byte/word/long) to store the 'bits', 'codes', and 'symbols' tables.
272 'use_static' should be set to 1 for tables, which should be freed
273 with av_free_static(), 0 if free_vlc() will be used.
275 int init_vlc_sparse(VLC
*vlc
, int nb_bits
, int nb_codes
,
276 const void *bits
, int bits_wrap
, int bits_size
,
277 const void *codes
, int codes_wrap
, int codes_size
,
278 const void *symbols
, int symbols_wrap
, int symbols_size
,
281 VLCcode buf
[nb_codes
];
285 if(flags
& INIT_VLC_USE_NEW_STATIC
){
286 if(vlc
->table_size
&& vlc
->table_size
== vlc
->table_allocated
){
288 }else if(vlc
->table_size
){
289 return -1; // fatal error, we are called on a partially initialized table
293 vlc
->table_allocated
= 0;
298 av_log(NULL
,AV_LOG_DEBUG
,"build table nb_codes=%d\n", nb_codes
);
301 //assert(symbols_size <= 2 || !symbols);
303 #define COPY(condition)\
304 for (i = 0; i < nb_codes; i++) {\
305 GET_DATA(buf[j].bits, bits, i, bits_wrap, bits_size);\
308 GET_DATA(buf[j].code, codes, i, codes_wrap, codes_size);\
309 if (flags & INIT_VLC_LE)\
310 buf[j].code = bitswap_32(buf[j].code);\
312 buf[j].code <<= 32 - buf[j].bits;\
314 GET_DATA(buf[j].symbol, symbols, i, symbols_wrap, symbols_size)\
319 COPY(buf
[j
].bits
> nb_bits
);
320 // qsort is the slowest part of init_vlc, and could probably be improved or avoided
321 qsort(buf
, j
, sizeof(VLCcode
), compare_vlcspec
);
322 COPY(buf
[j
].bits
&& buf
[j
].bits
<= nb_bits
);
325 if (build_table(vlc
, nb_bits
, nb_codes
, buf
, flags
) < 0) {
326 //av_freep(&vlc->table);
329 //if((flags & INIT_VLC_USE_NEW_STATIC) && vlc->table_size != vlc->table_allocated)
330 // av_log(NULL, AV_LOG_ERROR, "needed %d had %d\n", vlc->table_size, vlc->table_allocated);