these functions (get_bit_count and align_put_bits) are referenced even
[libav.git] / libavcodec / common.c
CommitLineData
de6d9b64
FB
1/*
2 * Common bit i/o utils
ff4ec49e 3 * Copyright (c) 2000, 2001 Fabrice Bellard.
8f2ab833 4 * Copyright (c) 2002-2004 Michael Niedermayer <michaelni@gmx.at>
de6d9b64 5 *
ff4ec49e
FB
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public
8 * License as published by the Free Software Foundation; either
9 * version 2 of the License, or (at your option) any later version.
de6d9b64 10 *
ff4ec49e 11 * This library is distributed in the hope that it will be useful,
de6d9b64 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
ff4ec49e
FB
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Lesser General Public License for more details.
de6d9b64 15 *
ff4ec49e
FB
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library; if not, write to the Free Software
18 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
27a3e2c5 19 *
17592475 20 * alternative bitstream reader & writer by Michael Niedermayer <michaelni@gmx.at>
de6d9b64 21 */
983e3246
MN
22
23/**
24 * @file common.c
25 * common internal api.
26 */
27
df595131 28#include "avcodec.h"
a9b3f630 29
0c1a9eda 30const uint8_t ff_sqrt_tab[128]={
f36db5df
MN
31 0, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5,
32 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
33 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
34 9, 9, 9, 9,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,11,11,11,11,11,11,11
35};
36
c81f0349
MN
37const uint8_t ff_log2_tab[256]={
38 0,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
39 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
40 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
41 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
42 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
43 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
44 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
45 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7
46};
47
ed7debda 48void init_put_bits(PutBitContext *s, uint8_t *buffer, int buffer_size)
de6d9b64
FB
49{
50 s->buf = buffer;
de6d9b64 51 s->buf_end = s->buf + buffer_size;
d8cf5aea
MN
52#ifdef ALT_BITSTREAM_WRITER
53 s->index=0;
54 ((uint32_t*)(s->buf))[0]=0;
55// memset(buffer, 0, buffer_size);
17592475 56#else
17592475 57 s->buf_ptr = s->buf;
d8cf5aea 58 s->bit_left=32;
17592475
MN
59 s->bit_buf=0;
60#endif
de6d9b64
FB
61}
62
7bf32612
MM
63//#ifdef CONFIG_ENCODERS
64#if 1
5fd74135 65
de6d9b64 66/* return the number of bits output */
a8380f44 67int get_bit_count(PutBitContext *s)
de6d9b64 68{
17592475 69#ifdef ALT_BITSTREAM_WRITER
a8380f44 70 return s->index;
17592475 71#else
a8380f44 72 return (s->buf_ptr - s->buf) * 8 + 32 - s->bit_left;
17592475 73#endif
de6d9b64
FB
74}
75
76void align_put_bits(PutBitContext *s)
77{
17592475
MN
78#ifdef ALT_BITSTREAM_WRITER
79 put_bits(s,( - s->index) & 7,0);
80#else
d8cf5aea 81 put_bits(s,s->bit_left & 7,0);
17592475 82#endif
de6d9b64
FB
83}
84
5fd74135
MN
85#endif //CONFIG_ENCODERS
86
de6d9b64
FB
87/* pad the end of the output stream with zeros */
88void flush_put_bits(PutBitContext *s)
89{
17592475
MN
90#ifdef ALT_BITSTREAM_WRITER
91 align_put_bits(s);
92#else
d8cf5aea
MN
93 s->bit_buf<<= s->bit_left;
94 while (s->bit_left < 32) {
de6d9b64
FB
95 /* XXX: should test end of buffer */
96 *s->buf_ptr++=s->bit_buf >> 24;
97 s->bit_buf<<=8;
d8cf5aea 98 s->bit_left+=8;
de6d9b64 99 }
d8cf5aea 100 s->bit_left=32;
de6d9b64 101 s->bit_buf=0;
17592475 102#endif
de6d9b64
FB
103}
104
5fd74135
MN
105#ifdef CONFIG_ENCODERS
106
9717dad8
MN
107void put_string(PutBitContext * pbc, char *s)
108{
109 while(*s){
110 put_bits(pbc, 8, *s);
111 s++;
112 }
113 put_bits(pbc, 8, 0);
114}
115
de6d9b64
FB
116/* bit input functions */
117
5fd74135
MN
118#endif //CONFIG_ENCODERS
119
f138f883
MN
120/**
121 * init GetBitContext.
122 * @param buffer bitstream buffer, must be FF_INPUT_BUFFER_PADDING_SIZE bytes larger then the actual read bits
123 * because some optimized bitstream readers read 32 or 64 bit at once and could read over the end
124 * @param bit_size the size of the buffer in bits
125 */
8db1a1dd 126void init_get_bits(GetBitContext *s,
ae39132d 127 const uint8_t *buffer, int bit_size)
de6d9b64 128{
68f593b4
MN
129 const int buffer_size= (bit_size+7)>>3;
130
27a3e2c5 131 s->buffer= buffer;
68f593b4 132 s->size_in_bits= bit_size;
8db1a1dd
MN
133 s->buffer_end= buffer + buffer_size;
134#ifdef ALT_BITSTREAM_READER
135 s->index=0;
136#elif defined LIBMPEG2_BITSTREAM_READER
17fb5fd3 137#ifdef LIBMPEG2_BITSTREAM_READER_HACK
d8e00c09
B
138 if ((int)buffer&1) {
139 /* word alignment */
140 s->cache = (*buffer++)<<24;
141 s->buffer_ptr = buffer;
142 s->bit_count = 16-8;
143 } else
144#endif
145 {
8db1a1dd
MN
146 s->buffer_ptr = buffer;
147 s->bit_count = 16;
148 s->cache = 0;
d8e00c09 149 }
8db1a1dd
MN
150#elif defined A32_BITSTREAM_READER
151 s->buffer_ptr = (uint32_t*)buffer;
152 s->bit_count = 32;
153 s->cache0 = 0;
154 s->cache1 = 0;
de6d9b64 155#endif
2931ecb9 156 {
8db1a1dd
MN
157 OPEN_READER(re, s)
158 UPDATE_CACHE(re, s)
3bb10888 159 UPDATE_CACHE(re, s)
8db1a1dd 160 CLOSE_READER(re, s)
de6d9b64 161 }
8db1a1dd
MN
162#ifdef A32_BITSTREAM_READER
163 s->cache1 = 0;
27a3e2c5 164#endif
8db1a1dd 165}
de6d9b64 166
17fb5fd3
MN
167/**
168 * reads 0-32 bits.
169 */
170unsigned int get_bits_long(GetBitContext *s, int n){
171 if(n<=17) return get_bits(s, n);
172 else{
173 int ret= get_bits(s, 16) << (n-16);
174 return ret | get_bits(s, n-16);
175 }
176}
177
178/**
179 * shows 0-32 bits.
180 */
181unsigned int show_bits_long(GetBitContext *s, int n){
182 if(n<=17) return show_bits(s, n);
183 else{
184 GetBitContext gb= *s;
185 int ret= get_bits_long(s, n);
186 *s= gb;
187 return ret;
188 }
189}
190
de6d9b64
FB
191void align_get_bits(GetBitContext *s)
192{
8db1a1dd
MN
193 int n= (-get_bits_count(s)) & 7;
194 if(n) skip_bits(s, n);
de6d9b64 195}
27a3e2c5 196
18f77016 197int check_marker(GetBitContext *s, const char *msg)
49c9325f
MN
198{
199 int bit= get_bits1(s);
9b879566
MB
200 if(!bit)
201 av_log(NULL, AV_LOG_INFO, "Marker bit missing %s\n", msg);
49c9325f
MN
202
203 return bit;
204}
205
de6d9b64
FB
206/* VLC decoding */
207
208//#define DEBUG_VLC
209
210#define GET_DATA(v, table, i, wrap, size) \
211{\
0c1a9eda 212 const uint8_t *ptr = (const uint8_t *)table + i * wrap;\
de6d9b64
FB
213 switch(size) {\
214 case 1:\
0c1a9eda 215 v = *(const uint8_t *)ptr;\
de6d9b64
FB
216 break;\
217 case 2:\
0c1a9eda 218 v = *(const uint16_t *)ptr;\
de6d9b64
FB
219 break;\
220 default:\
0c1a9eda 221 v = *(const uint32_t *)ptr;\
de6d9b64
FB
222 break;\
223 }\
224}
225
226
227static int alloc_table(VLC *vlc, int size)
228{
229 int index;
230 index = vlc->table_size;
231 vlc->table_size += size;
232 if (vlc->table_size > vlc->table_allocated) {
233 vlc->table_allocated += (1 << vlc->bits);
8e1e6f31
FB
234 vlc->table = av_realloc(vlc->table,
235 sizeof(VLC_TYPE) * 2 * vlc->table_allocated);
8db1a1dd 236 if (!vlc->table)
de6d9b64
FB
237 return -1;
238 }
239 return index;
240}
241
8db1a1dd 242static int build_table(VLC *vlc, int table_nb_bits,
de6d9b64
FB
243 int nb_codes,
244 const void *bits, int bits_wrap, int bits_size,
245 const void *codes, int codes_wrap, int codes_size,
0c1a9eda 246 uint32_t code_prefix, int n_prefix)
de6d9b64
FB
247{
248 int i, j, k, n, table_size, table_index, nb, n1, index;
0c1a9eda 249 uint32_t code;
8db1a1dd 250 VLC_TYPE (*table)[2];
de6d9b64
FB
251
252 table_size = 1 << table_nb_bits;
253 table_index = alloc_table(vlc, table_size);
254#ifdef DEBUG_VLC
8db1a1dd 255 printf("new table index=%d size=%d code_prefix=%x n=%d\n",
de6d9b64
FB
256 table_index, table_size, code_prefix, n_prefix);
257#endif
258 if (table_index < 0)
259 return -1;
8db1a1dd 260 table = &vlc->table[table_index];
de6d9b64
FB
261
262 for(i=0;i<table_size;i++) {
8db1a1dd
MN
263 table[i][1] = 0; //bits
264 table[i][0] = -1; //codes
de6d9b64
FB
265 }
266
267 /* first pass: map codes and compute auxillary table sizes */
268 for(i=0;i<nb_codes;i++) {
269 GET_DATA(n, bits, i, bits_wrap, bits_size);
270 GET_DATA(code, codes, i, codes_wrap, codes_size);
271 /* we accept tables with holes */
272 if (n <= 0)
273 continue;
274#if defined(DEBUG_VLC) && 0
275 printf("i=%d n=%d code=0x%x\n", i, n, code);
276#endif
277 /* if code matches the prefix, it is in the table */
278 n -= n_prefix;
279 if (n > 0 && (code >> n) == code_prefix) {
280 if (n <= table_nb_bits) {
281 /* no need to add another table */
282 j = (code << (table_nb_bits - n)) & (table_size - 1);
283 nb = 1 << (table_nb_bits - n);
284 for(k=0;k<nb;k++) {
285#ifdef DEBUG_VLC
3d0ef6dd 286 av_log(NULL, AV_LOG_DEBUG, "%4x: code=%d n=%d\n",
de6d9b64
FB
287 j, i, n);
288#endif
8db1a1dd 289 if (table[j][1] /*bits*/ != 0) {
9b879566 290 av_log(NULL, AV_LOG_ERROR, "incorrect codes\n");
e7124ffc 291 av_abort();
de6d9b64 292 }
8db1a1dd
MN
293 table[j][1] = n; //bits
294 table[j][0] = i; //code
de6d9b64
FB
295 j++;
296 }
297 } else {
298 n -= table_nb_bits;
299 j = (code >> n) & ((1 << table_nb_bits) - 1);
300#ifdef DEBUG_VLC
301 printf("%4x: n=%d (subtable)\n",
302 j, n);
303#endif
304 /* compute table size */
8db1a1dd 305 n1 = -table[j][1]; //bits
de6d9b64
FB
306 if (n > n1)
307 n1 = n;
8db1a1dd 308 table[j][1] = -n1; //bits
de6d9b64
FB
309 }
310 }
311 }
312
313 /* second pass : fill auxillary tables recursively */
314 for(i=0;i<table_size;i++) {
8db1a1dd 315 n = table[i][1]; //bits
de6d9b64
FB
316 if (n < 0) {
317 n = -n;
318 if (n > table_nb_bits) {
319 n = table_nb_bits;
8db1a1dd 320 table[i][1] = -n; //bits
de6d9b64
FB
321 }
322 index = build_table(vlc, n, nb_codes,
323 bits, bits_wrap, bits_size,
324 codes, codes_wrap, codes_size,
325 (code_prefix << table_nb_bits) | i,
326 n_prefix + table_nb_bits);
327 if (index < 0)
328 return -1;
329 /* note: realloc has been done, so reload tables */
8db1a1dd 330 table = &vlc->table[table_index];
6300c80a 331 table[i][0] = index; //code
de6d9b64
FB
332 }
333 }
334 return table_index;
335}
336
337
4e66ab3b
FB
338/* Build VLC decoding tables suitable for use with get_vlc().
339
340 'nb_bits' set thee decoding table size (2^nb_bits) entries. The
341 bigger it is, the faster is the decoding. But it should not be too
342 big to save memory and L1 cache. '9' is a good compromise.
343
344 'nb_codes' : number of vlcs codes
345
346 'bits' : table which gives the size (in bits) of each vlc code.
347
348 'codes' : table which gives the bit pattern of of each vlc code.
349
350 'xxx_wrap' : give the number of bytes between each entry of the
351 'bits' or 'codes' tables.
352
353 'xxx_size' : gives the number of bytes of each entry of the 'bits'
354 or 'codes' tables.
355
356 'wrap' and 'size' allows to use any memory configuration and types
357 (byte/word/long) to store the 'bits' and 'codes' tables.
358*/
de6d9b64
FB
359int init_vlc(VLC *vlc, int nb_bits, int nb_codes,
360 const void *bits, int bits_wrap, int bits_size,
361 const void *codes, int codes_wrap, int codes_size)
362{
363 vlc->bits = nb_bits;
8db1a1dd 364 vlc->table = NULL;
de6d9b64
FB
365 vlc->table_allocated = 0;
366 vlc->table_size = 0;
367#ifdef DEBUG_VLC
368 printf("build table nb_codes=%d\n", nb_codes);
369#endif
370
371 if (build_table(vlc, nb_bits, nb_codes,
372 bits, bits_wrap, bits_size,
373 codes, codes_wrap, codes_size,
374 0, 0) < 0) {
8db1a1dd 375 av_free(vlc->table);
de6d9b64
FB
376 return -1;
377 }
378 return 0;
379}
380
381
382void free_vlc(VLC *vlc)
383{
8db1a1dd 384 av_free(vlc->table);
de6d9b64
FB
385}
386
14bea432 387int64_t ff_gcd(int64_t a, int64_t b){
9dbcbd92
MN
388 if(b) return ff_gcd(b, a%b);
389 else return a;
390}