Statistics
| Branch: | Revision:

ffmpeg / libavcodec / bitstream.c @ f49568a4

History | View | Annotate | Download (10.2 KB)

1 de6d9b64 Fabrice Bellard
/*
2
 * Common bit i/o utils
3 406792e7 Diego Biurrun
 * Copyright (c) 2000, 2001 Fabrice Bellard
4 8f2ab833 Michael Niedermayer
 * Copyright (c) 2002-2004 Michael Niedermayer <michaelni@gmx.at>
5 de6d9b64 Fabrice Bellard
 *
6 7b94177e Diego Biurrun
 * alternative bitstream reader & writer by Michael Niedermayer <michaelni@gmx.at>
7
 *
8 b78e7197 Diego Biurrun
 * This file is part of FFmpeg.
9
 *
10
 * FFmpeg is free software; you can redistribute it and/or
11 ff4ec49e Fabrice Bellard
 * modify it under the terms of the GNU Lesser General Public
12
 * License as published by the Free Software Foundation; either
13 b78e7197 Diego Biurrun
 * version 2.1 of the License, or (at your option) any later version.
14 de6d9b64 Fabrice Bellard
 *
15 b78e7197 Diego Biurrun
 * FFmpeg is distributed in the hope that it will be useful,
16 de6d9b64 Fabrice Bellard
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 ff4ec49e Fabrice Bellard
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
18
 * Lesser General Public License for more details.
19 de6d9b64 Fabrice Bellard
 *
20 ff4ec49e Fabrice Bellard
 * You should have received a copy of the GNU Lesser General Public
21 b78e7197 Diego Biurrun
 * License along with FFmpeg; if not, write to the Free Software
22 5509bffa Diego Biurrun
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
23 de6d9b64 Fabrice Bellard
 */
24 983e3246 Michael Niedermayer
25
/**
26 bad5537e Diego Biurrun
 * @file libavcodec/bitstream.c
27 caa336b4 Michael Niedermayer
 * bitstream api.
28 983e3246 Michael Niedermayer
 */
29 115329f1 Diego Biurrun
30 df595131 Zdenek Kabelac
#include "avcodec.h"
31 caa336b4 Michael Niedermayer
#include "bitstream.h"
32 c81f0349 Michael Niedermayer
33 b3bf98aa Stefan Gehrer
const uint8_t ff_log2_run[32]={
34
 0, 0, 0, 0, 1, 1, 1, 1,
35
 2, 2, 2, 2, 3, 3, 3, 3,
36
 4, 4, 5, 5, 6, 6, 7, 7,
37
 8, 9,10,11,12,13,14,15
38
};
39
40 beebfdb1 Panagiotis Issaris
/**
41
 * Same as av_mallocz_static(), but does a realloc.
42
 *
43
 * @param[in] ptr The block of memory to reallocate.
44
 * @param[in] size The requested size.
45
 * @return Block of memory of requested size.
46 19032450 Diego Biurrun
 * @deprecated. Code which uses ff_realloc_static is broken/misdesigned
47 671adb17 Mark Cox
 * and should correctly use static arrays
48 beebfdb1 Panagiotis Issaris
 */
49 9f6152df Zuxy Meng
attribute_deprecated av_alloc_size(2)
50 09dafaeb Michael Niedermayer
static void *ff_realloc_static(void *ptr, unsigned int size);
51
52
static void *ff_realloc_static(void *ptr, unsigned int size)
53
{
54 b9c83887 Michael Niedermayer
    return av_realloc(ptr, size);
55 09dafaeb Michael Niedermayer
}
56
57 de6d9b64 Fabrice Bellard
void align_put_bits(PutBitContext *s)
58
{
59 17592475 Michael Niedermayer
#ifdef ALT_BITSTREAM_WRITER
60
    put_bits(s,(  - s->index) & 7,0);
61
#else
62 d8cf5aea Michael Niedermayer
    put_bits(s,s->bit_left & 7,0);
63 17592475 Michael Niedermayer
#endif
64 de6d9b64 Fabrice Bellard
}
65
66 1701cbfa Michael Niedermayer
void ff_put_string(PutBitContext * pbc, const char *s, int put_zero)
67 9717dad8 Michael Niedermayer
{
68
    while(*s){
69
        put_bits(pbc, 8, *s);
70
        s++;
71
    }
72 99683a30 Michael Niedermayer
    if(put_zero)
73
        put_bits(pbc, 8, 0);
74 9717dad8 Michael Niedermayer
}
75
76 1701cbfa Michael Niedermayer
void ff_copy_bits(PutBitContext *pb, const uint8_t *src, int length)
77 98f7b56b Aurelien Jacobs
{
78 1701cbfa Michael Niedermayer
    const uint16_t *srcw= (const uint16_t*)src;
79 98f7b56b Aurelien Jacobs
    int words= length>>4;
80
    int bits= length&15;
81
    int i;
82
83
    if(length==0) return;
84
85 49fb20cb Aurelien Jacobs
    if(CONFIG_SMALL || words < 16 || put_bits_count(pb)&7){
86 f49568a4 Måns Rullgård
        for(i=0; i<words; i++) put_bits(pb, 16, AV_RB16(&srcw[i]));
87 98f7b56b Aurelien Jacobs
    }else{
88
        for(i=0; put_bits_count(pb)&31; i++)
89
            put_bits(pb, 8, src[i]);
90
        flush_put_bits(pb);
91
        memcpy(pbBufPtr(pb), src+i, 2*words-i);
92
        skip_put_bytes(pb, 2*words-i);
93
    }
94
95 f49568a4 Måns Rullgård
    put_bits(pb, bits, AV_RB16(&srcw[words])>>(16-bits));
96 98f7b56b Aurelien Jacobs
}
97
98 de6d9b64 Fabrice Bellard
/* VLC decoding */
99
100
//#define DEBUG_VLC
101
102
#define GET_DATA(v, table, i, wrap, size) \
103
{\
104 0c1a9eda Zdenek Kabelac
    const uint8_t *ptr = (const uint8_t *)table + i * wrap;\
105 de6d9b64 Fabrice Bellard
    switch(size) {\
106
    case 1:\
107 0c1a9eda Zdenek Kabelac
        v = *(const uint8_t *)ptr;\
108 de6d9b64 Fabrice Bellard
        break;\
109
    case 2:\
110 0c1a9eda Zdenek Kabelac
        v = *(const uint16_t *)ptr;\
111 de6d9b64 Fabrice Bellard
        break;\
112
    default:\
113 0c1a9eda Zdenek Kabelac
        v = *(const uint32_t *)ptr;\
114 de6d9b64 Fabrice Bellard
        break;\
115
    }\
116
}
117
118
119 073c2593 Burkhard Plaum
static int alloc_table(VLC *vlc, int size, int use_static)
120 de6d9b64 Fabrice Bellard
{
121
    int index;
122
    index = vlc->table_size;
123
    vlc->table_size += size;
124
    if (vlc->table_size > vlc->table_allocated) {
125 ccc54864 Michael Niedermayer
        if(use_static>1)
126
            abort(); //cant do anything, init_vlc() is used with too little memory
127 de6d9b64 Fabrice Bellard
        vlc->table_allocated += (1 << vlc->bits);
128 073c2593 Burkhard Plaum
        if(use_static)
129 5dad0282 Panagiotis Issaris
            vlc->table = ff_realloc_static(vlc->table,
130 073c2593 Burkhard Plaum
                                           sizeof(VLC_TYPE) * 2 * vlc->table_allocated);
131
        else
132
            vlc->table = av_realloc(vlc->table,
133
                                    sizeof(VLC_TYPE) * 2 * vlc->table_allocated);
134 8db1a1dd Michael Niedermayer
        if (!vlc->table)
135 de6d9b64 Fabrice Bellard
            return -1;
136
    }
137
    return index;
138
}
139
140 8db1a1dd Michael Niedermayer
static int build_table(VLC *vlc, int table_nb_bits,
141 de6d9b64 Fabrice Bellard
                       int nb_codes,
142
                       const void *bits, int bits_wrap, int bits_size,
143
                       const void *codes, int codes_wrap, int codes_size,
144 b613bacc Loren Merritt
                       const void *symbols, int symbols_wrap, int symbols_size,
145 cea27ac7 Michael Niedermayer
                       uint32_t code_prefix, int n_prefix, int flags)
146 de6d9b64 Fabrice Bellard
{
147 b613bacc Loren Merritt
    int i, j, k, n, table_size, table_index, nb, n1, index, code_prefix2, symbol;
148 0c1a9eda Zdenek Kabelac
    uint32_t code;
149 8db1a1dd Michael Niedermayer
    VLC_TYPE (*table)[2];
150 de6d9b64 Fabrice Bellard
151
    table_size = 1 << table_nb_bits;
152 ccc54864 Michael Niedermayer
    table_index = alloc_table(vlc, table_size, flags & (INIT_VLC_USE_STATIC|INIT_VLC_USE_NEW_STATIC));
153 de6d9b64 Fabrice Bellard
#ifdef DEBUG_VLC
154 b8a99745 Denis Fortin
    av_log(NULL,AV_LOG_DEBUG,"new table index=%d size=%d code_prefix=%x n=%d\n",
155 de6d9b64 Fabrice Bellard
           table_index, table_size, code_prefix, n_prefix);
156
#endif
157
    if (table_index < 0)
158
        return -1;
159 8db1a1dd Michael Niedermayer
    table = &vlc->table[table_index];
160 de6d9b64 Fabrice Bellard
161
    for(i=0;i<table_size;i++) {
162 8db1a1dd Michael Niedermayer
        table[i][1] = 0; //bits
163
        table[i][0] = -1; //codes
164 de6d9b64 Fabrice Bellard
    }
165
166
    /* first pass: map codes and compute auxillary table sizes */
167
    for(i=0;i<nb_codes;i++) {
168
        GET_DATA(n, bits, i, bits_wrap, bits_size);
169
        GET_DATA(code, codes, i, codes_wrap, codes_size);
170
        /* we accept tables with holes */
171
        if (n <= 0)
172
            continue;
173 b613bacc Loren Merritt
        if (!symbols)
174
            symbol = i;
175
        else
176
            GET_DATA(symbol, symbols, i, symbols_wrap, symbols_size);
177 de6d9b64 Fabrice Bellard
#if defined(DEBUG_VLC) && 0
178 b8a99745 Denis Fortin
        av_log(NULL,AV_LOG_DEBUG,"i=%d n=%d code=0x%x\n", i, n, code);
179 de6d9b64 Fabrice Bellard
#endif
180
        /* if code matches the prefix, it is in the table */
181
        n -= n_prefix;
182 cea27ac7 Michael Niedermayer
        if(flags & INIT_VLC_LE)
183
            code_prefix2= code & (n_prefix>=32 ? 0xffffffff : (1 << n_prefix)-1);
184
        else
185
            code_prefix2= code >> n;
186
        if (n > 0 && code_prefix2 == code_prefix) {
187 de6d9b64 Fabrice Bellard
            if (n <= table_nb_bits) {
188
                /* no need to add another table */
189
                j = (code << (table_nb_bits - n)) & (table_size - 1);
190
                nb = 1 << (table_nb_bits - n);
191
                for(k=0;k<nb;k++) {
192 cea27ac7 Michael Niedermayer
                    if(flags & INIT_VLC_LE)
193
                        j = (code >> n_prefix) + (k<<n);
194 de6d9b64 Fabrice Bellard
#ifdef DEBUG_VLC
195 3d0ef6dd Michael Niedermayer
                    av_log(NULL, AV_LOG_DEBUG, "%4x: code=%d n=%d\n",
196 de6d9b64 Fabrice Bellard
                           j, i, n);
197
#endif
198 8db1a1dd Michael Niedermayer
                    if (table[j][1] /*bits*/ != 0) {
199 9b879566 Michel Bardiaux
                        av_log(NULL, AV_LOG_ERROR, "incorrect codes\n");
200 9fe5a7b8 Michael Niedermayer
                        return -1;
201 de6d9b64 Fabrice Bellard
                    }
202 8db1a1dd Michael Niedermayer
                    table[j][1] = n; //bits
203 b613bacc Loren Merritt
                    table[j][0] = symbol;
204 de6d9b64 Fabrice Bellard
                    j++;
205
                }
206
            } else {
207
                n -= table_nb_bits;
208 cea27ac7 Michael Niedermayer
                j = (code >> ((flags & INIT_VLC_LE) ? n_prefix : n)) & ((1 << table_nb_bits) - 1);
209 de6d9b64 Fabrice Bellard
#ifdef DEBUG_VLC
210 b8a99745 Denis Fortin
                av_log(NULL,AV_LOG_DEBUG,"%4x: n=%d (subtable)\n",
211 de6d9b64 Fabrice Bellard
                       j, n);
212
#endif
213
                /* compute table size */
214 8db1a1dd Michael Niedermayer
                n1 = -table[j][1]; //bits
215 de6d9b64 Fabrice Bellard
                if (n > n1)
216
                    n1 = n;
217 8db1a1dd Michael Niedermayer
                table[j][1] = -n1; //bits
218 de6d9b64 Fabrice Bellard
            }
219
        }
220
    }
221
222
    /* second pass : fill auxillary tables recursively */
223
    for(i=0;i<table_size;i++) {
224 8db1a1dd Michael Niedermayer
        n = table[i][1]; //bits
225 de6d9b64 Fabrice Bellard
        if (n < 0) {
226
            n = -n;
227
            if (n > table_nb_bits) {
228
                n = table_nb_bits;
229 8db1a1dd Michael Niedermayer
                table[i][1] = -n; //bits
230 de6d9b64 Fabrice Bellard
            }
231
            index = build_table(vlc, n, nb_codes,
232
                                bits, bits_wrap, bits_size,
233
                                codes, codes_wrap, codes_size,
234 b613bacc Loren Merritt
                                symbols, symbols_wrap, symbols_size,
235 cea27ac7 Michael Niedermayer
                                (flags & INIT_VLC_LE) ? (code_prefix | (i << n_prefix)) : ((code_prefix << table_nb_bits) | i),
236
                                n_prefix + table_nb_bits, flags);
237 de6d9b64 Fabrice Bellard
            if (index < 0)
238
                return -1;
239
            /* note: realloc has been done, so reload tables */
240 8db1a1dd Michael Niedermayer
            table = &vlc->table[table_index];
241 6300c80a Michael Niedermayer
            table[i][0] = index; //code
242 de6d9b64 Fabrice Bellard
        }
243
    }
244
    return table_index;
245
}
246
247
248 4e66ab3b Fabrice Bellard
/* Build VLC decoding tables suitable for use with get_vlc().
249

250
   'nb_bits' set thee decoding table size (2^nb_bits) entries. The
251
   bigger it is, the faster is the decoding. But it should not be too
252
   big to save memory and L1 cache. '9' is a good compromise.
253 115329f1 Diego Biurrun

254 4e66ab3b Fabrice Bellard
   'nb_codes' : number of vlcs codes
255

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

258
   'codes' : table which gives the bit pattern of of each vlc code.
259

260 b613bacc Loren Merritt
   'symbols' : table which gives the values to be returned from get_vlc().
261

262 4e66ab3b Fabrice Bellard
   'xxx_wrap' : give the number of bytes between each entry of the
263
   'bits' or 'codes' tables.
264

265
   'xxx_size' : gives the number of bytes of each entry of the 'bits'
266
   or 'codes' tables.
267

268
   'wrap' and 'size' allows to use any memory configuration and types
269 b613bacc Loren Merritt
   (byte/word/long) to store the 'bits', 'codes', and 'symbols' tables.
270 073c2593 Burkhard Plaum

271
   'use_static' should be set to 1 for tables, which should be freed
272
   with av_free_static(), 0 if free_vlc() will be used.
273 4e66ab3b Fabrice Bellard
*/
274 b613bacc Loren Merritt
int init_vlc_sparse(VLC *vlc, int nb_bits, int nb_codes,
275 de6d9b64 Fabrice Bellard
             const void *bits, int bits_wrap, int bits_size,
276 073c2593 Burkhard Plaum
             const void *codes, int codes_wrap, int codes_size,
277 b613bacc Loren Merritt
             const void *symbols, int symbols_wrap, int symbols_size,
278 d7645fb9 Måns Rullgård
             int flags)
279 de6d9b64 Fabrice Bellard
{
280
    vlc->bits = nb_bits;
281 ccc54864 Michael Niedermayer
    if(flags & INIT_VLC_USE_NEW_STATIC){
282
        if(vlc->table_size && vlc->table_size == vlc->table_allocated){
283
            return 0;
284
        }else if(vlc->table_size){
285
            abort(); // fatal error, we are called on a partially initialized table
286
        }
287
    }else if(!(flags & INIT_VLC_USE_STATIC)) {
288 073c2593 Burkhard Plaum
        vlc->table = NULL;
289
        vlc->table_allocated = 0;
290
        vlc->table_size = 0;
291
    } else {
292
        /* Static tables are initially always NULL, return
293
           if vlc->table != NULL to avoid double allocation */
294
        if(vlc->table)
295
            return 0;
296
    }
297
298 de6d9b64 Fabrice Bellard
#ifdef DEBUG_VLC
299 b8a99745 Denis Fortin
    av_log(NULL,AV_LOG_DEBUG,"build table nb_codes=%d\n", nb_codes);
300 de6d9b64 Fabrice Bellard
#endif
301
302
    if (build_table(vlc, nb_bits, nb_codes,
303
                    bits, bits_wrap, bits_size,
304
                    codes, codes_wrap, codes_size,
305 b613bacc Loren Merritt
                    symbols, symbols_wrap, symbols_size,
306 d7645fb9 Måns Rullgård
                    0, 0, flags) < 0) {
307 85d366fd Måns Rullgård
        av_freep(&vlc->table);
308 de6d9b64 Fabrice Bellard
        return -1;
309
    }
310 ccc54864 Michael Niedermayer
    if((flags & INIT_VLC_USE_NEW_STATIC) && vlc->table_size != vlc->table_allocated)
311
        av_log(NULL, AV_LOG_ERROR, "needed %d had %d\n", vlc->table_size, vlc->table_allocated);
312 de6d9b64 Fabrice Bellard
    return 0;
313
}
314
315
316
void free_vlc(VLC *vlc)
317
{
318 85d366fd Måns Rullgård
    av_freep(&vlc->table);
319 de6d9b64 Fabrice Bellard
}