extern C declarations were removed.
[libav.git] / libavcodec / bitstream.c
CommitLineData
de6d9b64
FB
1/*
2 * Common bit i/o utils
ff4ec49e 3 * Copyright (c) 2000, 2001 Fabrice Bellard.
8f2ab833 4 * Copyright (c) 2002-2004 Michael Niedermayer <michaelni@gmx.at>
de6d9b64 5 *
b78e7197
DB
6 * This file is part of FFmpeg.
7 *
8 * FFmpeg is free software; you can redistribute it and/or
ff4ec49e
FB
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
b78e7197 11 * version 2.1 of the License, or (at your option) any later version.
de6d9b64 12 *
b78e7197 13 * FFmpeg is distributed in the hope that it will be useful,
de6d9b64 14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
ff4ec49e
FB
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
de6d9b64 17 *
ff4ec49e 18 * You should have received a copy of the GNU Lesser General Public
b78e7197 19 * License along with FFmpeg; if not, write to the Free Software
5509bffa 20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
27a3e2c5 21 *
17592475 22 * alternative bitstream reader & writer by Michael Niedermayer <michaelni@gmx.at>
de6d9b64 23 */
983e3246
MN
24
25/**
caa336b4
MN
26 * @file bitstream.c
27 * bitstream api.
983e3246 28 */
115329f1 29
df595131 30#include "avcodec.h"
caa336b4 31#include "bitstream.h"
c81f0349 32
beebfdb1
PI
33/**
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.
671adb17
MC
39 * @deprecated. Code which uses ff_realloc_static is broken/missdesigned
40 * and should correctly use static arrays
beebfdb1 41 */
0769498a 42attribute_deprecated void *ff_realloc_static(void *ptr, unsigned int size);
beebfdb1 43
de6d9b64
FB
44void align_put_bits(PutBitContext *s)
45{
17592475
MN
46#ifdef ALT_BITSTREAM_WRITER
47 put_bits(s,( - s->index) & 7,0);
48#else
d8cf5aea 49 put_bits(s,s->bit_left & 7,0);
17592475 50#endif
de6d9b64
FB
51}
52
344b825c 53void ff_put_string(PutBitContext * pbc, char *s, int put_zero)
9717dad8
MN
54{
55 while(*s){
56 put_bits(pbc, 8, *s);
57 s++;
58 }
99683a30
MN
59 if(put_zero)
60 put_bits(pbc, 8, 0);
9717dad8
MN
61}
62
de6d9b64
FB
63/* VLC decoding */
64
65//#define DEBUG_VLC
66
67#define GET_DATA(v, table, i, wrap, size) \
68{\
0c1a9eda 69 const uint8_t *ptr = (const uint8_t *)table + i * wrap;\
de6d9b64
FB
70 switch(size) {\
71 case 1:\
0c1a9eda 72 v = *(const uint8_t *)ptr;\
de6d9b64
FB
73 break;\
74 case 2:\
0c1a9eda 75 v = *(const uint16_t *)ptr;\
de6d9b64
FB
76 break;\
77 default:\
0c1a9eda 78 v = *(const uint32_t *)ptr;\
de6d9b64
FB
79 break;\
80 }\
81}
82
83
073c2593 84static int alloc_table(VLC *vlc, int size, int use_static)
de6d9b64
FB
85{
86 int index;
87 index = vlc->table_size;
88 vlc->table_size += size;
89 if (vlc->table_size > vlc->table_allocated) {
90 vlc->table_allocated += (1 << vlc->bits);
073c2593 91 if(use_static)
5dad0282 92 vlc->table = ff_realloc_static(vlc->table,
073c2593
BP
93 sizeof(VLC_TYPE) * 2 * vlc->table_allocated);
94 else
95 vlc->table = av_realloc(vlc->table,
96 sizeof(VLC_TYPE) * 2 * vlc->table_allocated);
8db1a1dd 97 if (!vlc->table)
de6d9b64
FB
98 return -1;
99 }
100 return index;
101}
102
8db1a1dd 103static int build_table(VLC *vlc, int table_nb_bits,
de6d9b64
FB
104 int nb_codes,
105 const void *bits, int bits_wrap, int bits_size,
106 const void *codes, int codes_wrap, int codes_size,
cea27ac7 107 uint32_t code_prefix, int n_prefix, int flags)
de6d9b64 108{
cea27ac7 109 int i, j, k, n, table_size, table_index, nb, n1, index, code_prefix2;
0c1a9eda 110 uint32_t code;
8db1a1dd 111 VLC_TYPE (*table)[2];
de6d9b64
FB
112
113 table_size = 1 << table_nb_bits;
cea27ac7 114 table_index = alloc_table(vlc, table_size, flags & INIT_VLC_USE_STATIC);
de6d9b64 115#ifdef DEBUG_VLC
b8a99745 116 av_log(NULL,AV_LOG_DEBUG,"new table index=%d size=%d code_prefix=%x n=%d\n",
de6d9b64
FB
117 table_index, table_size, code_prefix, n_prefix);
118#endif
119 if (table_index < 0)
120 return -1;
8db1a1dd 121 table = &vlc->table[table_index];
de6d9b64
FB
122
123 for(i=0;i<table_size;i++) {
8db1a1dd
MN
124 table[i][1] = 0; //bits
125 table[i][0] = -1; //codes
de6d9b64
FB
126 }
127
128 /* first pass: map codes and compute auxillary table sizes */
129 for(i=0;i<nb_codes;i++) {
130 GET_DATA(n, bits, i, bits_wrap, bits_size);
131 GET_DATA(code, codes, i, codes_wrap, codes_size);
132 /* we accept tables with holes */
133 if (n <= 0)
134 continue;
135#if defined(DEBUG_VLC) && 0
b8a99745 136 av_log(NULL,AV_LOG_DEBUG,"i=%d n=%d code=0x%x\n", i, n, code);
de6d9b64
FB
137#endif
138 /* if code matches the prefix, it is in the table */
139 n -= n_prefix;
cea27ac7
MN
140 if(flags & INIT_VLC_LE)
141 code_prefix2= code & (n_prefix>=32 ? 0xffffffff : (1 << n_prefix)-1);
142 else
143 code_prefix2= code >> n;
144 if (n > 0 && code_prefix2 == code_prefix) {
de6d9b64
FB
145 if (n <= table_nb_bits) {
146 /* no need to add another table */
147 j = (code << (table_nb_bits - n)) & (table_size - 1);
148 nb = 1 << (table_nb_bits - n);
149 for(k=0;k<nb;k++) {
cea27ac7
MN
150 if(flags & INIT_VLC_LE)
151 j = (code >> n_prefix) + (k<<n);
de6d9b64 152#ifdef DEBUG_VLC
3d0ef6dd 153 av_log(NULL, AV_LOG_DEBUG, "%4x: code=%d n=%d\n",
de6d9b64
FB
154 j, i, n);
155#endif
8db1a1dd 156 if (table[j][1] /*bits*/ != 0) {
9b879566 157 av_log(NULL, AV_LOG_ERROR, "incorrect codes\n");
9fe5a7b8 158 return -1;
de6d9b64 159 }
8db1a1dd
MN
160 table[j][1] = n; //bits
161 table[j][0] = i; //code
de6d9b64
FB
162 j++;
163 }
164 } else {
165 n -= table_nb_bits;
cea27ac7 166 j = (code >> ((flags & INIT_VLC_LE) ? n_prefix : n)) & ((1 << table_nb_bits) - 1);
de6d9b64 167#ifdef DEBUG_VLC
b8a99745 168 av_log(NULL,AV_LOG_DEBUG,"%4x: n=%d (subtable)\n",
de6d9b64
FB
169 j, n);
170#endif
171 /* compute table size */
8db1a1dd 172 n1 = -table[j][1]; //bits
de6d9b64
FB
173 if (n > n1)
174 n1 = n;
8db1a1dd 175 table[j][1] = -n1; //bits
de6d9b64
FB
176 }
177 }
178 }
179
180 /* second pass : fill auxillary tables recursively */
181 for(i=0;i<table_size;i++) {
8db1a1dd 182 n = table[i][1]; //bits
de6d9b64
FB
183 if (n < 0) {
184 n = -n;
185 if (n > table_nb_bits) {
186 n = table_nb_bits;
8db1a1dd 187 table[i][1] = -n; //bits
de6d9b64
FB
188 }
189 index = build_table(vlc, n, nb_codes,
190 bits, bits_wrap, bits_size,
191 codes, codes_wrap, codes_size,
cea27ac7
MN
192 (flags & INIT_VLC_LE) ? (code_prefix | (i << n_prefix)) : ((code_prefix << table_nb_bits) | i),
193 n_prefix + table_nb_bits, flags);
de6d9b64
FB
194 if (index < 0)
195 return -1;
196 /* note: realloc has been done, so reload tables */
8db1a1dd 197 table = &vlc->table[table_index];
6300c80a 198 table[i][0] = index; //code
de6d9b64
FB
199 }
200 }
201 return table_index;
202}
203
204
4e66ab3b
FB
205/* Build VLC decoding tables suitable for use with get_vlc().
206
207 'nb_bits' set thee decoding table size (2^nb_bits) entries. The
208 bigger it is, the faster is the decoding. But it should not be too
209 big to save memory and L1 cache. '9' is a good compromise.
115329f1 210
4e66ab3b
FB
211 'nb_codes' : number of vlcs codes
212
213 'bits' : table which gives the size (in bits) of each vlc code.
214
215 'codes' : table which gives the bit pattern of of each vlc code.
216
217 'xxx_wrap' : give the number of bytes between each entry of the
218 'bits' or 'codes' tables.
219
220 'xxx_size' : gives the number of bytes of each entry of the 'bits'
221 or 'codes' tables.
222
223 'wrap' and 'size' allows to use any memory configuration and types
115329f1 224 (byte/word/long) to store the 'bits' and 'codes' tables.
073c2593
BP
225
226 'use_static' should be set to 1 for tables, which should be freed
227 with av_free_static(), 0 if free_vlc() will be used.
4e66ab3b 228*/
de6d9b64
FB
229int init_vlc(VLC *vlc, int nb_bits, int nb_codes,
230 const void *bits, int bits_wrap, int bits_size,
073c2593 231 const void *codes, int codes_wrap, int codes_size,
d7645fb9 232 int flags)
de6d9b64
FB
233{
234 vlc->bits = nb_bits;
d7645fb9 235 if(!(flags & INIT_VLC_USE_STATIC)) {
073c2593
BP
236 vlc->table = NULL;
237 vlc->table_allocated = 0;
238 vlc->table_size = 0;
239 } else {
240 /* Static tables are initially always NULL, return
241 if vlc->table != NULL to avoid double allocation */
242 if(vlc->table)
243 return 0;
244 }
245
de6d9b64 246#ifdef DEBUG_VLC
b8a99745 247 av_log(NULL,AV_LOG_DEBUG,"build table nb_codes=%d\n", nb_codes);
de6d9b64
FB
248#endif
249
250 if (build_table(vlc, nb_bits, nb_codes,
251 bits, bits_wrap, bits_size,
252 codes, codes_wrap, codes_size,
d7645fb9 253 0, 0, flags) < 0) {
8db1a1dd 254 av_free(vlc->table);
de6d9b64
FB
255 return -1;
256 }
257 return 0;
258}
259
260
261void free_vlc(VLC *vlc)
262{
8db1a1dd 263 av_free(vlc->table);
de6d9b64
FB
264}
265