Statistics
| Branch: | Revision:

ffmpeg / libavcodec / common.c @ 8a01fc47

History | View | Annotate | Download (8.62 KB)

1
/*
2
 * Common bit i/o utils
3
 * Copyright (c) 2000, 2001 Fabrice Bellard.
4
 * Copyright (c) 2002-2004 Michael Niedermayer <michaelni@gmx.at>
5
 *
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.
10
 *
11
 * This library is distributed in the hope that it will be useful,
12
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14
 * Lesser General Public License for more details.
15
 *
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
19
 *
20
 * alternative bitstream reader & writer by Michael Niedermayer <michaelni@gmx.at>
21
 */
22

    
23
/**
24
 * @file common.c
25
 * common internal api.
26
 */
27

    
28
#include "avcodec.h"
29

    
30
const uint8_t ff_sqrt_tab[128]={
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

    
37
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
void align_put_bits(PutBitContext *s)
49
{
50
#ifdef ALT_BITSTREAM_WRITER
51
    put_bits(s,(  - s->index) & 7,0);
52
#else
53
    put_bits(s,s->bit_left & 7,0);
54
#endif
55
}
56

    
57
void put_string(PutBitContext * pbc, char *s, int put_zero)
58
{
59
    while(*s){
60
        put_bits(pbc, 8, *s);
61
        s++;
62
    }
63
    if(put_zero)
64
        put_bits(pbc, 8, 0);
65
}
66

    
67
/* bit input functions */
68

    
69
/** 
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
void align_get_bits(GetBitContext *s)
94
{
95
    int n= (-get_bits_count(s)) & 7;
96
    if(n) skip_bits(s, n);
97
}
98

    
99
int check_marker(GetBitContext *s, const char *msg)
100
{
101
    int bit= get_bits1(s);
102
    if(!bit)
103
            av_log(NULL, AV_LOG_INFO, "Marker bit missing %s\n", msg);
104

    
105
    return bit;
106
}
107

    
108
/* VLC decoding */
109

    
110
//#define DEBUG_VLC
111

    
112
#define GET_DATA(v, table, i, wrap, size) \
113
{\
114
    const uint8_t *ptr = (const uint8_t *)table + i * wrap;\
115
    switch(size) {\
116
    case 1:\
117
        v = *(const uint8_t *)ptr;\
118
        break;\
119
    case 2:\
120
        v = *(const uint16_t *)ptr;\
121
        break;\
122
    default:\
123
        v = *(const uint32_t *)ptr;\
124
        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
        vlc->table = av_realloc(vlc->table,
137
                                sizeof(VLC_TYPE) * 2 * vlc->table_allocated);
138
        if (!vlc->table)
139
            return -1;
140
    }
141
    return index;
142
}
143

    
144
static int build_table(VLC *vlc, int table_nb_bits,
145
                       int nb_codes,
146
                       const void *bits, int bits_wrap, int bits_size,
147
                       const void *codes, int codes_wrap, int codes_size,
148
                       uint32_t code_prefix, int n_prefix)
149
{
150
    int i, j, k, n, table_size, table_index, nb, n1, index;
151
    uint32_t code;
152
    VLC_TYPE (*table)[2];
153

    
154
    table_size = 1 << table_nb_bits;
155
    table_index = alloc_table(vlc, table_size);
156
#ifdef DEBUG_VLC
157
    printf("new table index=%d size=%d code_prefix=%x n=%d\n",
158
           table_index, table_size, code_prefix, n_prefix);
159
#endif
160
    if (table_index < 0)
161
        return -1;
162
    table = &vlc->table[table_index];
163

    
164
    for(i=0;i<table_size;i++) {
165
        table[i][1] = 0; //bits
166
        table[i][0] = -1; //codes
167
    }
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
                    av_log(NULL, AV_LOG_DEBUG, "%4x: code=%d n=%d\n",
189
                           j, i, n);
190
#endif
191
                    if (table[j][1] /*bits*/ != 0) {
192
                        av_log(NULL, AV_LOG_ERROR, "incorrect codes\n");
193
                        return -1;
194
                    }
195
                    table[j][1] = n; //bits
196
                    table[j][0] = i; //code
197
                    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
                n1 = -table[j][1]; //bits
208
                if (n > n1)
209
                    n1 = n;
210
                table[j][1] = -n1; //bits
211
            }
212
        }
213
    }
214

    
215
    /* second pass : fill auxillary tables recursively */
216
    for(i=0;i<table_size;i++) {
217
        n = table[i][1]; //bits
218
        if (n < 0) {
219
            n = -n;
220
            if (n > table_nb_bits) {
221
                n = table_nb_bits;
222
                table[i][1] = -n; //bits
223
            }
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
            table = &vlc->table[table_index];
233
            table[i][0] = index; //code
234
        }
235
    }
236
    return table_index;
237
}
238

    
239

    
240
/* 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
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
    vlc->table = NULL;
267
    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
        av_free(vlc->table);
278
        return -1;
279
    }
280
    return 0;
281
}
282

    
283

    
284
void free_vlc(VLC *vlc)
285
{
286
    av_free(vlc->table);
287
}
288

    
289
int64_t ff_gcd(int64_t a, int64_t b){
290
    if(b) return ff_gcd(b, a%b);
291
    else  return a;
292
}