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