some libmpeg2 style bitstream reader fixes (no dv doesnt yet work with it)
[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
de6d9b64 47void init_put_bits(PutBitContext *s,
0c1a9eda 48 uint8_t *buffer, int buffer_size,
de6d9b64 49 void *opaque,
0c1a9eda 50 void (*write_data)(void *, uint8_t *, int))
de6d9b64
FB
51{
52 s->buf = buffer;
de6d9b64 53 s->buf_end = s->buf + buffer_size;
de6d9b64 54 s->data_out_size = 0;
17592475
MN
55 if(write_data!=NULL)
56 {
57 fprintf(stderr, "write Data callback is not supported\n");
58 }
d8cf5aea
MN
59#ifdef ALT_BITSTREAM_WRITER
60 s->index=0;
61 ((uint32_t*)(s->buf))[0]=0;
62// memset(buffer, 0, buffer_size);
17592475 63#else
17592475 64 s->buf_ptr = s->buf;
d8cf5aea 65 s->bit_left=32;
17592475
MN
66 s->bit_buf=0;
67#endif
de6d9b64
FB
68}
69
5fd74135
MN
70#ifdef CONFIG_ENCODERS
71
de6d9b64 72/* return the number of bits output */
0c1a9eda 73int64_t get_bit_count(PutBitContext *s)
de6d9b64 74{
17592475
MN
75#ifdef ALT_BITSTREAM_WRITER
76 return s->data_out_size * 8 + s->index;
77#else
0c1a9eda 78 return (s->buf_ptr - s->buf + s->data_out_size) * 8 + 32 - (int64_t)s->bit_left;
17592475 79#endif
de6d9b64
FB
80}
81
82void align_put_bits(PutBitContext *s)
83{
17592475
MN
84#ifdef ALT_BITSTREAM_WRITER
85 put_bits(s,( - s->index) & 7,0);
86#else
d8cf5aea 87 put_bits(s,s->bit_left & 7,0);
17592475 88#endif
de6d9b64
FB
89}
90
5fd74135
MN
91#endif //CONFIG_ENCODERS
92
de6d9b64
FB
93/* pad the end of the output stream with zeros */
94void flush_put_bits(PutBitContext *s)
95{
17592475
MN
96#ifdef ALT_BITSTREAM_WRITER
97 align_put_bits(s);
98#else
d8cf5aea
MN
99 s->bit_buf<<= s->bit_left;
100 while (s->bit_left < 32) {
de6d9b64
FB
101 /* XXX: should test end of buffer */
102 *s->buf_ptr++=s->bit_buf >> 24;
103 s->bit_buf<<=8;
d8cf5aea 104 s->bit_left+=8;
de6d9b64 105 }
d8cf5aea 106 s->bit_left=32;
de6d9b64 107 s->bit_buf=0;
17592475 108#endif
de6d9b64
FB
109}
110
5fd74135
MN
111#ifdef CONFIG_ENCODERS
112
9717dad8
MN
113void put_string(PutBitContext * pbc, char *s)
114{
115 while(*s){
116 put_bits(pbc, 8, *s);
117 s++;
118 }
119 put_bits(pbc, 8, 0);
120}
121
de6d9b64
FB
122/* bit input functions */
123
5fd74135
MN
124#endif //CONFIG_ENCODERS
125
f138f883
MN
126/**
127 * init GetBitContext.
128 * @param buffer bitstream buffer, must be FF_INPUT_BUFFER_PADDING_SIZE bytes larger then the actual read bits
129 * because some optimized bitstream readers read 32 or 64 bit at once and could read over the end
130 * @param bit_size the size of the buffer in bits
131 */
8db1a1dd 132void init_get_bits(GetBitContext *s,
ae39132d 133 const uint8_t *buffer, int bit_size)
de6d9b64 134{
68f593b4
MN
135 const int buffer_size= (bit_size+7)>>3;
136
27a3e2c5 137 s->buffer= buffer;
68f593b4 138 s->size_in_bits= bit_size;
8db1a1dd
MN
139 s->buffer_end= buffer + buffer_size;
140#ifdef ALT_BITSTREAM_READER
141 s->index=0;
142#elif defined LIBMPEG2_BITSTREAM_READER
d8e00c09
B
143#ifdef LIBMPEG2_BITSTREAM_HACK
144 if ((int)buffer&1) {
145 /* word alignment */
146 s->cache = (*buffer++)<<24;
147 s->buffer_ptr = buffer;
148 s->bit_count = 16-8;
149 } else
150#endif
151 {
8db1a1dd
MN
152 s->buffer_ptr = buffer;
153 s->bit_count = 16;
154 s->cache = 0;
d8e00c09 155 }
8db1a1dd
MN
156#elif defined A32_BITSTREAM_READER
157 s->buffer_ptr = (uint32_t*)buffer;
158 s->bit_count = 32;
159 s->cache0 = 0;
160 s->cache1 = 0;
de6d9b64 161#endif
2931ecb9 162 {
8db1a1dd
MN
163 OPEN_READER(re, s)
164 UPDATE_CACHE(re, s)
165// UPDATE_CACHE(re, s)
166 CLOSE_READER(re, s)
de6d9b64 167 }
8db1a1dd
MN
168#ifdef A32_BITSTREAM_READER
169 s->cache1 = 0;
27a3e2c5 170#endif
8db1a1dd 171}
de6d9b64
FB
172
173void align_get_bits(GetBitContext *s)
174{
8db1a1dd
MN
175 int n= (-get_bits_count(s)) & 7;
176 if(n) skip_bits(s, n);
de6d9b64 177}
27a3e2c5 178
18f77016 179int check_marker(GetBitContext *s, const char *msg)
49c9325f
MN
180{
181 int bit= get_bits1(s);
182 if(!bit) printf("Marker bit missing %s\n", msg);
183
184 return bit;
185}
186
de6d9b64
FB
187/* VLC decoding */
188
189//#define DEBUG_VLC
190
191#define GET_DATA(v, table, i, wrap, size) \
192{\
0c1a9eda 193 const uint8_t *ptr = (const uint8_t *)table + i * wrap;\
de6d9b64
FB
194 switch(size) {\
195 case 1:\
0c1a9eda 196 v = *(const uint8_t *)ptr;\
de6d9b64
FB
197 break;\
198 case 2:\
0c1a9eda 199 v = *(const uint16_t *)ptr;\
de6d9b64
FB
200 break;\
201 default:\
0c1a9eda 202 v = *(const uint32_t *)ptr;\
de6d9b64
FB
203 break;\
204 }\
205}
206
207
208static int alloc_table(VLC *vlc, int size)
209{
210 int index;
211 index = vlc->table_size;
212 vlc->table_size += size;
213 if (vlc->table_size > vlc->table_allocated) {
214 vlc->table_allocated += (1 << vlc->bits);
8e1e6f31
FB
215 vlc->table = av_realloc(vlc->table,
216 sizeof(VLC_TYPE) * 2 * vlc->table_allocated);
8db1a1dd 217 if (!vlc->table)
de6d9b64
FB
218 return -1;
219 }
220 return index;
221}
222
8db1a1dd 223static int build_table(VLC *vlc, int table_nb_bits,
de6d9b64
FB
224 int nb_codes,
225 const void *bits, int bits_wrap, int bits_size,
226 const void *codes, int codes_wrap, int codes_size,
0c1a9eda 227 uint32_t code_prefix, int n_prefix)
de6d9b64
FB
228{
229 int i, j, k, n, table_size, table_index, nb, n1, index;
0c1a9eda 230 uint32_t code;
8db1a1dd 231 VLC_TYPE (*table)[2];
de6d9b64
FB
232
233 table_size = 1 << table_nb_bits;
234 table_index = alloc_table(vlc, table_size);
235#ifdef DEBUG_VLC
8db1a1dd 236 printf("new table index=%d size=%d code_prefix=%x n=%d\n",
de6d9b64
FB
237 table_index, table_size, code_prefix, n_prefix);
238#endif
239 if (table_index < 0)
240 return -1;
8db1a1dd 241 table = &vlc->table[table_index];
de6d9b64
FB
242
243 for(i=0;i<table_size;i++) {
8db1a1dd
MN
244 table[i][1] = 0; //bits
245 table[i][0] = -1; //codes
de6d9b64
FB
246 }
247
248 /* first pass: map codes and compute auxillary table sizes */
249 for(i=0;i<nb_codes;i++) {
250 GET_DATA(n, bits, i, bits_wrap, bits_size);
251 GET_DATA(code, codes, i, codes_wrap, codes_size);
252 /* we accept tables with holes */
253 if (n <= 0)
254 continue;
255#if defined(DEBUG_VLC) && 0
256 printf("i=%d n=%d code=0x%x\n", i, n, code);
257#endif
258 /* if code matches the prefix, it is in the table */
259 n -= n_prefix;
260 if (n > 0 && (code >> n) == code_prefix) {
261 if (n <= table_nb_bits) {
262 /* no need to add another table */
263 j = (code << (table_nb_bits - n)) & (table_size - 1);
264 nb = 1 << (table_nb_bits - n);
265 for(k=0;k<nb;k++) {
266#ifdef DEBUG_VLC
267 printf("%4x: code=%d n=%d\n",
268 j, i, n);
269#endif
8db1a1dd 270 if (table[j][1] /*bits*/ != 0) {
de6d9b64
FB
271 fprintf(stderr, "incorrect codes\n");
272 exit(1);
273 }
8db1a1dd
MN
274 table[j][1] = n; //bits
275 table[j][0] = i; //code
de6d9b64
FB
276 j++;
277 }
278 } else {
279 n -= table_nb_bits;
280 j = (code >> n) & ((1 << table_nb_bits) - 1);
281#ifdef DEBUG_VLC
282 printf("%4x: n=%d (subtable)\n",
283 j, n);
284#endif
285 /* compute table size */
8db1a1dd 286 n1 = -table[j][1]; //bits
de6d9b64
FB
287 if (n > n1)
288 n1 = n;
8db1a1dd 289 table[j][1] = -n1; //bits
de6d9b64
FB
290 }
291 }
292 }
293
294 /* second pass : fill auxillary tables recursively */
295 for(i=0;i<table_size;i++) {
8db1a1dd 296 n = table[i][1]; //bits
de6d9b64
FB
297 if (n < 0) {
298 n = -n;
299 if (n > table_nb_bits) {
300 n = table_nb_bits;
8db1a1dd 301 table[i][1] = -n; //bits
de6d9b64
FB
302 }
303 index = build_table(vlc, n, nb_codes,
304 bits, bits_wrap, bits_size,
305 codes, codes_wrap, codes_size,
306 (code_prefix << table_nb_bits) | i,
307 n_prefix + table_nb_bits);
308 if (index < 0)
309 return -1;
310 /* note: realloc has been done, so reload tables */
8db1a1dd 311 table = &vlc->table[table_index];
6300c80a 312 table[i][0] = index; //code
de6d9b64
FB
313 }
314 }
315 return table_index;
316}
317
318
4e66ab3b
FB
319/* Build VLC decoding tables suitable for use with get_vlc().
320
321 'nb_bits' set thee decoding table size (2^nb_bits) entries. The
322 bigger it is, the faster is the decoding. But it should not be too
323 big to save memory and L1 cache. '9' is a good compromise.
324
325 'nb_codes' : number of vlcs codes
326
327 'bits' : table which gives the size (in bits) of each vlc code.
328
329 'codes' : table which gives the bit pattern of of each vlc code.
330
331 'xxx_wrap' : give the number of bytes between each entry of the
332 'bits' or 'codes' tables.
333
334 'xxx_size' : gives the number of bytes of each entry of the 'bits'
335 or 'codes' tables.
336
337 'wrap' and 'size' allows to use any memory configuration and types
338 (byte/word/long) to store the 'bits' and 'codes' tables.
339*/
de6d9b64
FB
340int init_vlc(VLC *vlc, int nb_bits, int nb_codes,
341 const void *bits, int bits_wrap, int bits_size,
342 const void *codes, int codes_wrap, int codes_size)
343{
344 vlc->bits = nb_bits;
8db1a1dd 345 vlc->table = NULL;
de6d9b64
FB
346 vlc->table_allocated = 0;
347 vlc->table_size = 0;
348#ifdef DEBUG_VLC
349 printf("build table nb_codes=%d\n", nb_codes);
350#endif
351
352 if (build_table(vlc, nb_bits, nb_codes,
353 bits, bits_wrap, bits_size,
354 codes, codes_wrap, codes_size,
355 0, 0) < 0) {
8db1a1dd 356 av_free(vlc->table);
de6d9b64
FB
357 return -1;
358 }
359 return 0;
360}
361
362
363void free_vlc(VLC *vlc)
364{
8db1a1dd 365 av_free(vlc->table);
de6d9b64
FB
366}
367
14bea432 368int64_t ff_gcd(int64_t a, int64_t b){
9dbcbd92
MN
369 if(b) return ff_gcd(b, a%b);
370 else return a;
371}
5d3cea3a
MN
372
373void ff_float2fraction(int *nom_arg, int *denom_arg, double f, int max){
374 double best_diff=1E10, diff;
375 int best_denom=1, best_nom=1;
376 int nom, denom, gcd;
377
378 //brute force here, perhaps we should try continued fractions if we need large max ...
379 for(denom=1; denom<=max; denom++){
380 nom= (int)(f*denom + 0.5);
381 if(nom<=0 || nom>max) continue;
382
383 diff= ABS( f - (double)nom / (double)denom );
384 if(diff < best_diff){
385 best_diff= diff;
386 best_nom= nom;
387 best_denom= denom;
388 }
389 }
390
391 gcd= ff_gcd(best_nom, best_denom);
392 best_nom /= gcd;
393 best_denom /= gcd;
394
395 *nom_arg= best_nom;
396 *denom_arg= best_denom;
397}