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