Statistics
| Branch: | Revision:

ffmpeg / libavcodec / common.c @ 8a01fc47

History | View | Annotate | Download (8.62 KB)

1 de6d9b64 Fabrice Bellard
/*
2
 * Common bit i/o utils
3 ff4ec49e Fabrice Bellard
 * Copyright (c) 2000, 2001 Fabrice Bellard.
4 8f2ab833 Michael Niedermayer
 * Copyright (c) 2002-2004 Michael Niedermayer <michaelni@gmx.at>
5 de6d9b64 Fabrice Bellard
 *
6 ff4ec49e Fabrice Bellard
 * 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.
10 de6d9b64 Fabrice Bellard
 *
11 ff4ec49e Fabrice Bellard
 * This library is distributed in the hope that it will be useful,
12 de6d9b64 Fabrice Bellard
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 ff4ec49e Fabrice Bellard
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14
 * Lesser General Public License for more details.
15 de6d9b64 Fabrice Bellard
 *
16 ff4ec49e Fabrice Bellard
 * 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
19 27a3e2c5 Michael Niedermayer
 *
20 17592475 Michael Niedermayer
 * alternative bitstream reader & writer by Michael Niedermayer <michaelni@gmx.at>
21 de6d9b64 Fabrice Bellard
 */
22 983e3246 Michael Niedermayer
23
/**
24
 * @file common.c
25
 * common internal api.
26
 */
27
28 df595131 Zdenek Kabelac
#include "avcodec.h"
29 a9b3f630 Nick Kurshev
30 0c1a9eda Zdenek Kabelac
const uint8_t ff_sqrt_tab[128]={
31 f36db5df Michael Niedermayer
        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
37 c81f0349 Michael Niedermayer
const 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
48 de6d9b64 Fabrice Bellard
void align_put_bits(PutBitContext *s)
49
{
50 17592475 Michael Niedermayer
#ifdef ALT_BITSTREAM_WRITER
51
    put_bits(s,(  - s->index) & 7,0);
52
#else
53 d8cf5aea Michael Niedermayer
    put_bits(s,s->bit_left & 7,0);
54 17592475 Michael Niedermayer
#endif
55 de6d9b64 Fabrice Bellard
}
56
57 99683a30 Michael Niedermayer
void put_string(PutBitContext * pbc, char *s, int put_zero)
58 9717dad8 Michael Niedermayer
{
59
    while(*s){
60
        put_bits(pbc, 8, *s);
61
        s++;
62
    }
63 99683a30 Michael Niedermayer
    if(put_zero)
64
        put_bits(pbc, 8, 0);
65 9717dad8 Michael Niedermayer
}
66
67 de6d9b64 Fabrice Bellard
/* bit input functions */
68
69 17fb5fd3 Michael Niedermayer
/** 
70
 * reads 0-32 bits.
71
 */
72
unsigned int get_bits_long(GetBitContext *s, int n){
73
    if(n<=17) return get_bits(s, n);
74
    else{
75
        int ret= get_bits(s, 16) << (n-16);
76
        return ret | get_bits(s, n-16);
77
    }
78
}
79
80
/** 
81
 * shows 0-32 bits.
82
 */
83
unsigned int show_bits_long(GetBitContext *s, int n){
84
    if(n<=17) return show_bits(s, n);
85
    else{
86
        GetBitContext gb= *s;
87
        int ret= get_bits_long(s, n);
88
        *s= gb;
89
        return ret;
90
    }
91
}
92
93 de6d9b64 Fabrice Bellard
void align_get_bits(GetBitContext *s)
94
{
95 8db1a1dd Michael Niedermayer
    int n= (-get_bits_count(s)) & 7;
96
    if(n) skip_bits(s, n);
97 de6d9b64 Fabrice Bellard
}
98 27a3e2c5 Michael Niedermayer
99 18f77016 Zdenek Kabelac
int check_marker(GetBitContext *s, const char *msg)
100 49c9325f Michael Niedermayer
{
101
    int bit= get_bits1(s);
102 9b879566 Michel Bardiaux
    if(!bit)
103
            av_log(NULL, AV_LOG_INFO, "Marker bit missing %s\n", msg);
104 49c9325f Michael Niedermayer
105
    return bit;
106
}
107
108 de6d9b64 Fabrice Bellard
/* VLC decoding */
109
110
//#define DEBUG_VLC
111
112
#define GET_DATA(v, table, i, wrap, size) \
113
{\
114 0c1a9eda Zdenek Kabelac
    const uint8_t *ptr = (const uint8_t *)table + i * wrap;\
115 de6d9b64 Fabrice Bellard
    switch(size) {\
116
    case 1:\
117 0c1a9eda Zdenek Kabelac
        v = *(const uint8_t *)ptr;\
118 de6d9b64 Fabrice Bellard
        break;\
119
    case 2:\
120 0c1a9eda Zdenek Kabelac
        v = *(const uint16_t *)ptr;\
121 de6d9b64 Fabrice Bellard
        break;\
122
    default:\
123 0c1a9eda Zdenek Kabelac
        v = *(const uint32_t *)ptr;\
124 de6d9b64 Fabrice Bellard
        break;\
125
    }\
126
}
127
128
129
static int alloc_table(VLC *vlc, int size)
130
{
131
    int index;
132
    index = vlc->table_size;
133
    vlc->table_size += size;
134
    if (vlc->table_size > vlc->table_allocated) {
135
        vlc->table_allocated += (1 << vlc->bits);
136 8e1e6f31 Fabrice Bellard
        vlc->table = av_realloc(vlc->table,
137
                                sizeof(VLC_TYPE) * 2 * vlc->table_allocated);
138 8db1a1dd Michael Niedermayer
        if (!vlc->table)
139 de6d9b64 Fabrice Bellard
            return -1;
140
    }
141
    return index;
142
}
143
144 8db1a1dd Michael Niedermayer
static int build_table(VLC *vlc, int table_nb_bits,
145 de6d9b64 Fabrice Bellard
                       int nb_codes,
146
                       const void *bits, int bits_wrap, int bits_size,
147
                       const void *codes, int codes_wrap, int codes_size,
148 0c1a9eda Zdenek Kabelac
                       uint32_t code_prefix, int n_prefix)
149 de6d9b64 Fabrice Bellard
{
150
    int i, j, k, n, table_size, table_index, nb, n1, index;
151 0c1a9eda Zdenek Kabelac
    uint32_t code;
152 8db1a1dd Michael Niedermayer
    VLC_TYPE (*table)[2];
153 de6d9b64 Fabrice Bellard
154
    table_size = 1 << table_nb_bits;
155
    table_index = alloc_table(vlc, table_size);
156
#ifdef DEBUG_VLC
157 8db1a1dd Michael Niedermayer
    printf("new table index=%d size=%d code_prefix=%x n=%d\n",
158 de6d9b64 Fabrice Bellard
           table_index, table_size, code_prefix, n_prefix);
159
#endif
160
    if (table_index < 0)
161
        return -1;
162 8db1a1dd Michael Niedermayer
    table = &vlc->table[table_index];
163 de6d9b64 Fabrice Bellard
164
    for(i=0;i<table_size;i++) {
165 8db1a1dd Michael Niedermayer
        table[i][1] = 0; //bits
166
        table[i][0] = -1; //codes
167 de6d9b64 Fabrice Bellard
    }
168
169
    /* first pass: map codes and compute auxillary table sizes */
170
    for(i=0;i<nb_codes;i++) {
171
        GET_DATA(n, bits, i, bits_wrap, bits_size);
172
        GET_DATA(code, codes, i, codes_wrap, codes_size);
173
        /* we accept tables with holes */
174
        if (n <= 0)
175
            continue;
176
#if defined(DEBUG_VLC) && 0
177
        printf("i=%d n=%d code=0x%x\n", i, n, code);
178
#endif
179
        /* if code matches the prefix, it is in the table */
180
        n -= n_prefix;
181
        if (n > 0 && (code >> n) == code_prefix) {
182
            if (n <= table_nb_bits) {
183
                /* no need to add another table */
184
                j = (code << (table_nb_bits - n)) & (table_size - 1);
185
                nb = 1 << (table_nb_bits - n);
186
                for(k=0;k<nb;k++) {
187
#ifdef DEBUG_VLC
188 3d0ef6dd Michael Niedermayer
                    av_log(NULL, AV_LOG_DEBUG, "%4x: code=%d n=%d\n",
189 de6d9b64 Fabrice Bellard
                           j, i, n);
190
#endif
191 8db1a1dd Michael Niedermayer
                    if (table[j][1] /*bits*/ != 0) {
192 9b879566 Michel Bardiaux
                        av_log(NULL, AV_LOG_ERROR, "incorrect codes\n");
193 9fe5a7b8 Michael Niedermayer
                        return -1;
194 de6d9b64 Fabrice Bellard
                    }
195 8db1a1dd Michael Niedermayer
                    table[j][1] = n; //bits
196
                    table[j][0] = i; //code
197 de6d9b64 Fabrice Bellard
                    j++;
198
                }
199
            } else {
200
                n -= table_nb_bits;
201
                j = (code >> n) & ((1 << table_nb_bits) - 1);
202
#ifdef DEBUG_VLC
203
                printf("%4x: n=%d (subtable)\n",
204
                       j, n);
205
#endif
206
                /* compute table size */
207 8db1a1dd Michael Niedermayer
                n1 = -table[j][1]; //bits
208 de6d9b64 Fabrice Bellard
                if (n > n1)
209
                    n1 = n;
210 8db1a1dd Michael Niedermayer
                table[j][1] = -n1; //bits
211 de6d9b64 Fabrice Bellard
            }
212
        }
213
    }
214
215
    /* second pass : fill auxillary tables recursively */
216
    for(i=0;i<table_size;i++) {
217 8db1a1dd Michael Niedermayer
        n = table[i][1]; //bits
218 de6d9b64 Fabrice Bellard
        if (n < 0) {
219
            n = -n;
220
            if (n > table_nb_bits) {
221
                n = table_nb_bits;
222 8db1a1dd Michael Niedermayer
                table[i][1] = -n; //bits
223 de6d9b64 Fabrice Bellard
            }
224
            index = build_table(vlc, n, nb_codes,
225
                                bits, bits_wrap, bits_size,
226
                                codes, codes_wrap, codes_size,
227
                                (code_prefix << table_nb_bits) | i,
228
                                n_prefix + table_nb_bits);
229
            if (index < 0)
230
                return -1;
231
            /* note: realloc has been done, so reload tables */
232 8db1a1dd Michael Niedermayer
            table = &vlc->table[table_index];
233 6300c80a Michael Niedermayer
            table[i][0] = index; //code
234 de6d9b64 Fabrice Bellard
        }
235
    }
236
    return table_index;
237
}
238
239
240 4e66ab3b Fabrice Bellard
/* Build VLC decoding tables suitable for use with get_vlc().
241

242
   'nb_bits' set thee decoding table size (2^nb_bits) entries. The
243
   bigger it is, the faster is the decoding. But it should not be too
244
   big to save memory and L1 cache. '9' is a good compromise.
245
   
246
   'nb_codes' : number of vlcs codes
247

248
   'bits' : table which gives the size (in bits) of each vlc code.
249

250
   'codes' : table which gives the bit pattern of of each vlc code.
251

252
   'xxx_wrap' : give the number of bytes between each entry of the
253
   'bits' or 'codes' tables.
254

255
   'xxx_size' : gives the number of bytes of each entry of the 'bits'
256
   or 'codes' tables.
257

258
   'wrap' and 'size' allows to use any memory configuration and types
259
   (byte/word/long) to store the 'bits' and 'codes' tables.  
260
*/
261 de6d9b64 Fabrice Bellard
int init_vlc(VLC *vlc, int nb_bits, int nb_codes,
262
             const void *bits, int bits_wrap, int bits_size,
263
             const void *codes, int codes_wrap, int codes_size)
264
{
265
    vlc->bits = nb_bits;
266 8db1a1dd Michael Niedermayer
    vlc->table = NULL;
267 de6d9b64 Fabrice Bellard
    vlc->table_allocated = 0;
268
    vlc->table_size = 0;
269
#ifdef DEBUG_VLC
270
    printf("build table nb_codes=%d\n", nb_codes);
271
#endif
272
273
    if (build_table(vlc, nb_bits, nb_codes,
274
                    bits, bits_wrap, bits_size,
275
                    codes, codes_wrap, codes_size,
276
                    0, 0) < 0) {
277 8db1a1dd Michael Niedermayer
        av_free(vlc->table);
278 de6d9b64 Fabrice Bellard
        return -1;
279
    }
280
    return 0;
281
}
282
283
284
void free_vlc(VLC *vlc)
285
{
286 8db1a1dd Michael Niedermayer
    av_free(vlc->table);
287 de6d9b64 Fabrice Bellard
}
288
289 14bea432 Michael Niedermayer
int64_t ff_gcd(int64_t a, int64_t b){
290 9dbcbd92 Michael Niedermayer
    if(b) return ff_gcd(b, a%b);
291
    else  return a;
292
}