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
31 //#include "avcodec.h"
32 #include "ffmpeg_get_bits.h"
33 #include "ffmpeg_put_bits.h"
34 #include "ffmpeg_intreadwrite.h"
43 const uint8_t ff_log2_run
[32]={
44 0, 0, 0, 0, 1, 1, 1, 1,
45 2, 2, 2, 2, 3, 3, 3, 3,
46 4, 4, 5, 5, 6, 6, 7, 7,
47 8, 9,10,11,12,13,14,15
50 #if 0 // unused in rockbox
51 void align_put_bits(PutBitContext
*s
)
53 #ifdef ALT_BITSTREAM_WRITER
54 put_bits(s
,( - s
->index
) & 7,0);
56 put_bits(s
,s
->bit_left
& 7,0);
60 void ff_put_string(PutBitContext
*pb
, const char *string
, int terminate_string
)
63 put_bits(pb
, 8, *string
);
71 void ff_copy_bits(PutBitContext
*pb
, const uint8_t *src
, int length
)
79 if(words
< 16 || put_bits_count(pb
)&7){
80 for(i
=0; i
<words
; i
++) put_bits(pb
, 16, AV_RB16(src
+ 2*i
));
82 for(i
=0; put_bits_count(pb
)&31; i
++)
83 put_bits(pb
, 8, src
[i
]);
85 memcpy(put_bits_ptr(pb
), src
+i
, 2*words
-i
);
86 skip_put_bytes(pb
, 2*words
-i
);
89 put_bits(pb
, bits
, AV_RB16(src
+ 2*words
)>>(16-bits
));
96 #define GET_DATA(v, table, i, wrap, size) \
98 const uint8_t *ptr = (const uint8_t *)table + i * wrap;\
101 v = *(const uint8_t *)ptr;\
104 v = *(const uint16_t *)ptr;\
107 v = *(const uint32_t *)ptr;\
113 static int alloc_table(VLC
*vlc
, int size
, int use_static
)
116 index
= vlc
->table_size
;
117 vlc
->table_size
+= size
;
118 if (vlc
->table_size
> vlc
->table_allocated
) {
121 DEBUGF("init_vlc() used with too little memory : table_size > allocated_memory\n");
124 // abort(); //cant do anything, init_vlc() is used with too little memory
125 // vlc->table_allocated += (1 << vlc->bits);
126 // vlc->table = av_realloc(vlc->table,
127 // sizeof(VLC_TYPE) * 2 * vlc->table_allocated);
135 static av_always_inline uint32_t bitswap_32(uint32_t x) {
136 return av_reverse[x&0xFF]<<24
137 | av_reverse[(x>>8)&0xFF]<<16
138 | av_reverse[(x>>16)&0xFF]<<8
146 /** codeword, with the first bit-to-be-read in the msb
147 * (even if intended for a little-endian bitstream reader) */
149 } __attribute__((__packed__
)) VLCcode
; /* packed to save space */
151 static int compare_vlcspec(const void *a
, const void *b
)
153 const VLCcode
*sa
=a
, *sb
=b
;
154 return (sa
->code
>> 1) - (sb
->code
>> 1);
158 * Build VLC decoding tables suitable for use with get_vlc().
160 * @param vlc the context to be initted
162 * @param table_nb_bits max length of vlc codes to store directly in this table
163 * (Longer codes are delegated to subtables.)
165 * @param nb_codes number of elements in codes[]
167 * @param codes descriptions of the vlc codes
168 * These must be ordered such that codes going into the same subtable are contiguous.
169 * Sorting by VLCcode.code is sufficient, though not necessary.
171 static int build_table(VLC
*vlc
, int table_nb_bits
, int nb_codes
,
172 VLCcode
*codes
, int flags
)
174 int table_size
, table_index
, index
, symbol
, subtable_bits
;
175 int i
, j
, k
, n
, nb
, inc
;
176 uint32_t code
, code_prefix
;
177 VLC_TYPE (*table
)[2];
179 table_size
= 1 << table_nb_bits
;
180 table_index
= alloc_table(vlc
, table_size
, flags
& INIT_VLC_USE_NEW_STATIC
);
182 av_log(NULL
,AV_LOG_DEBUG
,"new table index=%d size=%d\n",
183 table_index
, table_size
);
187 table
= &vlc
->table
[table_index
];
189 for (i
= 0; i
< table_size
; i
++) {
190 table
[i
][1] = 0; //bits
191 table
[i
][0] = -1; //codes
194 /* first pass: map codes and compute auxillary table sizes */
195 for (i
= 0; i
< nb_codes
; i
++) {
197 code
= codes
[i
].code
;
198 symbol
= codes
[i
].symbol
;
199 #if defined(DEBUG_VLC) && 0
200 av_log(NULL
,AV_LOG_DEBUG
,"i=%d n=%d code=0x%x\n", i
, n
, code
);
202 if (n
<= table_nb_bits
) {
203 /* no need to add another table */
204 j
= code
>> (32 - table_nb_bits
);
205 nb
= 1 << (table_nb_bits
- n
);
207 /* if (flags & INIT_VLC_LE) {
208 j = bitswap_32(code);
211 for (k
= 0; k
< nb
; k
++) {
213 av_log(NULL
, AV_LOG_DEBUG
, "%4x: code=%d n=%d\n",
216 if (table
[j
][1] /*bits*/ != 0) {
217 av_log(NULL
, AV_LOG_ERROR
, "incorrect codes\n");
220 table
[j
][1] = n
; //bits
221 table
[j
][0] = symbol
;
225 /* fill auxiliary table recursively */
227 code_prefix
= code
>> (32 - table_nb_bits
);
230 codes
[i
].code
= code
<< table_nb_bits
;
231 for (k
= i
+1; k
< nb_codes
; k
++) {
232 n
= codes
[k
].bits
- table_nb_bits
;
235 code
= codes
[k
].code
;
236 if (code
>> (32 - table_nb_bits
) != code_prefix
)
239 codes
[k
].code
= code
<< table_nb_bits
;
240 subtable_bits
= FFMAX(subtable_bits
, n
);
242 subtable_bits
= FFMIN(subtable_bits
, table_nb_bits
);
243 j
= /*(flags & INIT_VLC_LE) ? bitswap_32(code_prefix) >> (32 - table_nb_bits) :*/ code_prefix
;
244 table
[j
][1] = -subtable_bits
;
246 av_log(NULL
,AV_LOG_DEBUG
,"%4x: n=%d (subtable)\n",
247 j
, codes
[i
].bits
+ table_nb_bits
);
249 index
= build_table(vlc
, subtable_bits
, k
-i
, codes
+i
, flags
);
252 /* note: realloc has been done, so reload tables */
253 table
= &vlc
->table
[table_index
];
254 table
[j
][0] = index
; //code
262 /* Build VLC decoding tables suitable for use with get_vlc().
264 'nb_bits' set thee decoding table size (2^nb_bits) entries. The
265 bigger it is, the faster is the decoding. But it should not be too
266 big to save memory and L1 cache. '9' is a good compromise.
268 'nb_codes' : number of vlcs codes
270 'bits' : table which gives the size (in bits) of each vlc code.
272 'codes' : table which gives the bit pattern of of each vlc code.
274 'symbols' : table which gives the values to be returned from get_vlc().
276 'xxx_wrap' : give the number of bytes between each entry of the
277 'bits' or 'codes' tables.
279 'xxx_size' : gives the number of bytes of each entry of the 'bits'
282 'wrap' and 'size' allows to use any memory configuration and types
283 (byte/word/long) to store the 'bits', 'codes', and 'symbols' tables.
285 'use_static' should be set to 1 for tables, which should be freed
286 with av_free_static(), 0 if free_vlc() will be used.
289 /* Rockbox: support for INIT_VLC_LE is currently disabled since none of our
290 codecs use it, there's a LUT based bit reverse function for this commented
291 out above (bitswap_32) and an inline asm version in libtremor/codebook.c
292 if we ever want this */
294 static VLCcode buf
[1336+1]; /* worst case is wma, which has one table with 1336 entries */
296 int init_vlc_sparse(VLC
*vlc
, int nb_bits
, int nb_codes
,
297 const void *bits
, int bits_wrap
, int bits_size
,
298 const void *codes
, int codes_wrap
, int codes_size
,
299 const void *symbols
, int symbols_wrap
, int symbols_size
,
302 if (nb_codes
+1 > (int)(sizeof (buf
)/ sizeof (VLCcode
)))
304 DEBUGF("Table is larger than temp buffer!\n");
311 if(flags
& INIT_VLC_USE_NEW_STATIC
){
312 if(vlc
->table_size
&& vlc
->table_size
== vlc
->table_allocated
){
314 }else if(vlc
->table_size
){
315 DEBUGF("fatal error, we are called on a partially initialized table\n");
317 // abort(); // fatal error, we are called on a partially initialized table
321 vlc
->table_allocated
= 0;
326 av_log(NULL
,AV_LOG_DEBUG
,"build table nb_codes=%d\n", nb_codes
);
329 // buf = av_malloc((nb_codes+1)*sizeof(VLCcode));
331 // assert(symbols_size <= 2 || !symbols);
333 #define COPY(condition)\
334 for (i = 0; i < nb_codes; i++) {\
335 GET_DATA(buf[j].bits, bits, i, bits_wrap, bits_size);\
338 GET_DATA(buf[j].code, codes, i, codes_wrap, codes_size);\
339 /* if (flags & INIT_VLC_LE)*/\
340 /* buf[j].code = bitswap_32(buf[j].code);*/\
342 buf[j].code <<= 32 - buf[j].bits;\
344 GET_DATA(buf[j].symbol, symbols, i, symbols_wrap, symbols_size)\
349 COPY(buf
[j
].bits
> nb_bits
);
350 // qsort is the slowest part of init_vlc, and could probably be improved or avoided
351 qsort(buf
, j
, sizeof(VLCcode
), compare_vlcspec
);
352 COPY(buf
[j
].bits
&& buf
[j
].bits
<= nb_bits
);
355 ret
= build_table(vlc
, nb_bits
, nb_codes
, buf
, flags
);
359 // av_freep(&vlc->table);
362 if((flags
& INIT_VLC_USE_NEW_STATIC
) && vlc
->table_size
!= vlc
->table_allocated
) {
363 av_log(NULL
, AV_LOG_ERROR
, "needed %d had %d\n", vlc
->table_size
, vlc
->table_allocated
);
368 /* not used in rockbox
369 void free_vlc(VLC *vlc)
371 av_freep(&vlc->table);