Statistics
| Branch: | Revision:

ffmpeg / libavcodec / bitstream.c @ 19032450

History | View | Annotate | Download (9.3 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 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 caa336b4 Michael Niedermayer
 * @file bitstream.c
27
 * 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 beebfdb1 Panagiotis Issaris
/**
34
 * Same as av_mallocz_static(), but does a realloc.
35
 *
36
 * @param[in] ptr The block of memory to reallocate.
37
 * @param[in] size The requested size.
38
 * @return Block of memory of requested size.
39 19032450 Diego Biurrun
 * @deprecated. Code which uses ff_realloc_static is broken/misdesigned
40 671adb17 Mark Cox
 * and should correctly use static arrays
41 beebfdb1 Panagiotis Issaris
 */
42 0769498a Michael Niedermayer
attribute_deprecated void *ff_realloc_static(void *ptr, unsigned int size);
43 beebfdb1 Panagiotis Issaris
44 de6d9b64 Fabrice Bellard
void align_put_bits(PutBitContext *s)
45
{
46 17592475 Michael Niedermayer
#ifdef ALT_BITSTREAM_WRITER
47
    put_bits(s,(  - s->index) & 7,0);
48
#else
49 d8cf5aea Michael Niedermayer
    put_bits(s,s->bit_left & 7,0);
50 17592475 Michael Niedermayer
#endif
51 de6d9b64 Fabrice Bellard
}
52
53 344b825c Diego Biurrun
void ff_put_string(PutBitContext * pbc, char *s, int put_zero)
54 9717dad8 Michael Niedermayer
{
55
    while(*s){
56
        put_bits(pbc, 8, *s);
57
        s++;
58
    }
59 99683a30 Michael Niedermayer
    if(put_zero)
60
        put_bits(pbc, 8, 0);
61 9717dad8 Michael Niedermayer
}
62
63 98f7b56b Aurelien Jacobs
void ff_copy_bits(PutBitContext *pb, uint8_t *src, int length)
64
{
65
    const uint16_t *srcw= (uint16_t*)src;
66
    int words= length>>4;
67
    int bits= length&15;
68
    int i;
69
70
    if(length==0) return;
71
72 58e28fd5 Aurelien Jacobs
    if(ENABLE_SMALL || words < 16 || put_bits_count(pb)&7){
73 98f7b56b Aurelien Jacobs
        for(i=0; i<words; i++) put_bits(pb, 16, be2me_16(srcw[i]));
74
    }else{
75
        for(i=0; put_bits_count(pb)&31; i++)
76
            put_bits(pb, 8, src[i]);
77
        flush_put_bits(pb);
78
        memcpy(pbBufPtr(pb), src+i, 2*words-i);
79
        skip_put_bytes(pb, 2*words-i);
80
    }
81
82
    put_bits(pb, bits, be2me_16(srcw[words])>>(16-bits));
83
}
84
85 de6d9b64 Fabrice Bellard
/* VLC decoding */
86
87
//#define DEBUG_VLC
88
89
#define GET_DATA(v, table, i, wrap, size) \
90
{\
91 0c1a9eda Zdenek Kabelac
    const uint8_t *ptr = (const uint8_t *)table + i * wrap;\
92 de6d9b64 Fabrice Bellard
    switch(size) {\
93
    case 1:\
94 0c1a9eda Zdenek Kabelac
        v = *(const uint8_t *)ptr;\
95 de6d9b64 Fabrice Bellard
        break;\
96
    case 2:\
97 0c1a9eda Zdenek Kabelac
        v = *(const uint16_t *)ptr;\
98 de6d9b64 Fabrice Bellard
        break;\
99
    default:\
100 0c1a9eda Zdenek Kabelac
        v = *(const uint32_t *)ptr;\
101 de6d9b64 Fabrice Bellard
        break;\
102
    }\
103
}
104
105
106 073c2593 Burkhard Plaum
static int alloc_table(VLC *vlc, int size, int use_static)
107 de6d9b64 Fabrice Bellard
{
108
    int index;
109
    index = vlc->table_size;
110
    vlc->table_size += size;
111
    if (vlc->table_size > vlc->table_allocated) {
112
        vlc->table_allocated += (1 << vlc->bits);
113 073c2593 Burkhard Plaum
        if(use_static)
114 5dad0282 Panagiotis Issaris
            vlc->table = ff_realloc_static(vlc->table,
115 073c2593 Burkhard Plaum
                                           sizeof(VLC_TYPE) * 2 * vlc->table_allocated);
116
        else
117
            vlc->table = av_realloc(vlc->table,
118
                                    sizeof(VLC_TYPE) * 2 * vlc->table_allocated);
119 8db1a1dd Michael Niedermayer
        if (!vlc->table)
120 de6d9b64 Fabrice Bellard
            return -1;
121
    }
122
    return index;
123
}
124
125 8db1a1dd Michael Niedermayer
static int build_table(VLC *vlc, int table_nb_bits,
126 de6d9b64 Fabrice Bellard
                       int nb_codes,
127
                       const void *bits, int bits_wrap, int bits_size,
128
                       const void *codes, int codes_wrap, int codes_size,
129 b613bacc Loren Merritt
                       const void *symbols, int symbols_wrap, int symbols_size,
130 cea27ac7 Michael Niedermayer
                       uint32_t code_prefix, int n_prefix, int flags)
131 de6d9b64 Fabrice Bellard
{
132 b613bacc Loren Merritt
    int i, j, k, n, table_size, table_index, nb, n1, index, code_prefix2, symbol;
133 0c1a9eda Zdenek Kabelac
    uint32_t code;
134 8db1a1dd Michael Niedermayer
    VLC_TYPE (*table)[2];
135 de6d9b64 Fabrice Bellard
136
    table_size = 1 << table_nb_bits;
137 cea27ac7 Michael Niedermayer
    table_index = alloc_table(vlc, table_size, flags & INIT_VLC_USE_STATIC);
138 de6d9b64 Fabrice Bellard
#ifdef DEBUG_VLC
139 b8a99745 Denis Fortin
    av_log(NULL,AV_LOG_DEBUG,"new table index=%d size=%d code_prefix=%x n=%d\n",
140 de6d9b64 Fabrice Bellard
           table_index, table_size, code_prefix, n_prefix);
141
#endif
142
    if (table_index < 0)
143
        return -1;
144 8db1a1dd Michael Niedermayer
    table = &vlc->table[table_index];
145 de6d9b64 Fabrice Bellard
146
    for(i=0;i<table_size;i++) {
147 8db1a1dd Michael Niedermayer
        table[i][1] = 0; //bits
148
        table[i][0] = -1; //codes
149 de6d9b64 Fabrice Bellard
    }
150
151
    /* first pass: map codes and compute auxillary table sizes */
152
    for(i=0;i<nb_codes;i++) {
153
        GET_DATA(n, bits, i, bits_wrap, bits_size);
154
        GET_DATA(code, codes, i, codes_wrap, codes_size);
155
        /* we accept tables with holes */
156
        if (n <= 0)
157
            continue;
158 b613bacc Loren Merritt
        if (!symbols)
159
            symbol = i;
160
        else
161
            GET_DATA(symbol, symbols, i, symbols_wrap, symbols_size);
162 de6d9b64 Fabrice Bellard
#if defined(DEBUG_VLC) && 0
163 b8a99745 Denis Fortin
        av_log(NULL,AV_LOG_DEBUG,"i=%d n=%d code=0x%x\n", i, n, code);
164 de6d9b64 Fabrice Bellard
#endif
165
        /* if code matches the prefix, it is in the table */
166
        n -= n_prefix;
167 cea27ac7 Michael Niedermayer
        if(flags & INIT_VLC_LE)
168
            code_prefix2= code & (n_prefix>=32 ? 0xffffffff : (1 << n_prefix)-1);
169
        else
170
            code_prefix2= code >> n;
171
        if (n > 0 && code_prefix2 == code_prefix) {
172 de6d9b64 Fabrice Bellard
            if (n <= table_nb_bits) {
173
                /* no need to add another table */
174
                j = (code << (table_nb_bits - n)) & (table_size - 1);
175
                nb = 1 << (table_nb_bits - n);
176
                for(k=0;k<nb;k++) {
177 cea27ac7 Michael Niedermayer
                    if(flags & INIT_VLC_LE)
178
                        j = (code >> n_prefix) + (k<<n);
179 de6d9b64 Fabrice Bellard
#ifdef DEBUG_VLC
180 3d0ef6dd Michael Niedermayer
                    av_log(NULL, AV_LOG_DEBUG, "%4x: code=%d n=%d\n",
181 de6d9b64 Fabrice Bellard
                           j, i, n);
182
#endif
183 8db1a1dd Michael Niedermayer
                    if (table[j][1] /*bits*/ != 0) {
184 9b879566 Michel Bardiaux
                        av_log(NULL, AV_LOG_ERROR, "incorrect codes\n");
185 9fe5a7b8 Michael Niedermayer
                        return -1;
186 de6d9b64 Fabrice Bellard
                    }
187 8db1a1dd Michael Niedermayer
                    table[j][1] = n; //bits
188 b613bacc Loren Merritt
                    table[j][0] = symbol;
189 de6d9b64 Fabrice Bellard
                    j++;
190
                }
191
            } else {
192
                n -= table_nb_bits;
193 cea27ac7 Michael Niedermayer
                j = (code >> ((flags & INIT_VLC_LE) ? n_prefix : n)) & ((1 << table_nb_bits) - 1);
194 de6d9b64 Fabrice Bellard
#ifdef DEBUG_VLC
195 b8a99745 Denis Fortin
                av_log(NULL,AV_LOG_DEBUG,"%4x: n=%d (subtable)\n",
196 de6d9b64 Fabrice Bellard
                       j, n);
197
#endif
198
                /* compute table size */
199 8db1a1dd Michael Niedermayer
                n1 = -table[j][1]; //bits
200 de6d9b64 Fabrice Bellard
                if (n > n1)
201
                    n1 = n;
202 8db1a1dd Michael Niedermayer
                table[j][1] = -n1; //bits
203 de6d9b64 Fabrice Bellard
            }
204
        }
205
    }
206
207
    /* second pass : fill auxillary tables recursively */
208
    for(i=0;i<table_size;i++) {
209 8db1a1dd Michael Niedermayer
        n = table[i][1]; //bits
210 de6d9b64 Fabrice Bellard
        if (n < 0) {
211
            n = -n;
212
            if (n > table_nb_bits) {
213
                n = table_nb_bits;
214 8db1a1dd Michael Niedermayer
                table[i][1] = -n; //bits
215 de6d9b64 Fabrice Bellard
            }
216
            index = build_table(vlc, n, nb_codes,
217
                                bits, bits_wrap, bits_size,
218
                                codes, codes_wrap, codes_size,
219 b613bacc Loren Merritt
                                symbols, symbols_wrap, symbols_size,
220 cea27ac7 Michael Niedermayer
                                (flags & INIT_VLC_LE) ? (code_prefix | (i << n_prefix)) : ((code_prefix << table_nb_bits) | i),
221
                                n_prefix + table_nb_bits, flags);
222 de6d9b64 Fabrice Bellard
            if (index < 0)
223
                return -1;
224
            /* note: realloc has been done, so reload tables */
225 8db1a1dd Michael Niedermayer
            table = &vlc->table[table_index];
226 6300c80a Michael Niedermayer
            table[i][0] = index; //code
227 de6d9b64 Fabrice Bellard
        }
228
    }
229
    return table_index;
230
}
231
232
233 4e66ab3b Fabrice Bellard
/* Build VLC decoding tables suitable for use with get_vlc().
234

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

239 4e66ab3b Fabrice Bellard
   'nb_codes' : number of vlcs codes
240

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

243
   'codes' : table which gives the bit pattern of of each vlc code.
244

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

247 4e66ab3b Fabrice Bellard
   'xxx_wrap' : give the number of bytes between each entry of the
248
   'bits' or 'codes' tables.
249

250
   'xxx_size' : gives the number of bytes of each entry of the 'bits'
251
   or 'codes' tables.
252

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

256
   'use_static' should be set to 1 for tables, which should be freed
257
   with av_free_static(), 0 if free_vlc() will be used.
258 4e66ab3b Fabrice Bellard
*/
259 b613bacc Loren Merritt
int init_vlc_sparse(VLC *vlc, int nb_bits, int nb_codes,
260 de6d9b64 Fabrice Bellard
             const void *bits, int bits_wrap, int bits_size,
261 073c2593 Burkhard Plaum
             const void *codes, int codes_wrap, int codes_size,
262 b613bacc Loren Merritt
             const void *symbols, int symbols_wrap, int symbols_size,
263 d7645fb9 Måns Rullgård
             int flags)
264 de6d9b64 Fabrice Bellard
{
265
    vlc->bits = nb_bits;
266 d7645fb9 Måns Rullgård
    if(!(flags & INIT_VLC_USE_STATIC)) {
267 073c2593 Burkhard Plaum
        vlc->table = NULL;
268
        vlc->table_allocated = 0;
269
        vlc->table_size = 0;
270
    } else {
271
        /* Static tables are initially always NULL, return
272
           if vlc->table != NULL to avoid double allocation */
273
        if(vlc->table)
274
            return 0;
275
    }
276
277 de6d9b64 Fabrice Bellard
#ifdef DEBUG_VLC
278 b8a99745 Denis Fortin
    av_log(NULL,AV_LOG_DEBUG,"build table nb_codes=%d\n", nb_codes);
279 de6d9b64 Fabrice Bellard
#endif
280
281
    if (build_table(vlc, nb_bits, nb_codes,
282
                    bits, bits_wrap, bits_size,
283
                    codes, codes_wrap, codes_size,
284 b613bacc Loren Merritt
                    symbols, symbols_wrap, symbols_size,
285 d7645fb9 Måns Rullgård
                    0, 0, flags) < 0) {
286 85d366fd Måns Rullgård
        av_freep(&vlc->table);
287 de6d9b64 Fabrice Bellard
        return -1;
288
    }
289
    return 0;
290
}
291
292
293
void free_vlc(VLC *vlc)
294
{
295 85d366fd Måns Rullgård
    av_freep(&vlc->table);
296 de6d9b64 Fabrice Bellard
}