indent
[libav.git] / libavcodec / bitstream.c
CommitLineData
de6d9b64
FB
1/*
2 * Common bit i/o utils
406792e7 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/**
bad5537e 26 * @file libavcodec/bitstream.c
caa336b4 27 * bitstream api.
983e3246 28 */
115329f1 29
df595131 30#include "avcodec.h"
9106a698 31#include "get_bits.h"
b2755007 32#include "put_bits.h"
c81f0349 33
b3bf98aa
SG
34const uint8_t ff_log2_run[32]={
35 0, 0, 0, 0, 1, 1, 1, 1,
36 2, 2, 2, 2, 3, 3, 3, 3,
37 4, 4, 5, 5, 6, 6, 7, 7,
38 8, 9,10,11,12,13,14,15
39};
40
de6d9b64
FB
41void align_put_bits(PutBitContext *s)
42{
17592475
MN
43#ifdef ALT_BITSTREAM_WRITER
44 put_bits(s,( - s->index) & 7,0);
45#else
d8cf5aea 46 put_bits(s,s->bit_left & 7,0);
17592475 47#endif
de6d9b64
FB
48}
49
587edd6a 50void ff_put_string(PutBitContext *pb, const char *string, int terminate_string)
9717dad8 51{
587edd6a
SS
52 while(*string){
53 put_bits(pb, 8, *string);
54 string++;
9717dad8 55 }
54b02ccd 56 if(terminate_string)
587edd6a 57 put_bits(pb, 8, 0);
9717dad8
MN
58}
59
1701cbfa 60void ff_copy_bits(PutBitContext *pb, const uint8_t *src, int length)
98f7b56b 61{
98f7b56b
AJ
62 int words= length>>4;
63 int bits= length&15;
64 int i;
65
66 if(length==0) return;
67
49fb20cb 68 if(CONFIG_SMALL || words < 16 || put_bits_count(pb)&7){
ec62d942 69 for(i=0; i<words; i++) put_bits(pb, 16, AV_RB16(src + 2*i));
98f7b56b
AJ
70 }else{
71 for(i=0; put_bits_count(pb)&31; i++)
72 put_bits(pb, 8, src[i]);
73 flush_put_bits(pb);
fb53b4a0 74 memcpy(put_bits_ptr(pb), src+i, 2*words-i);
98f7b56b
AJ
75 skip_put_bytes(pb, 2*words-i);
76 }
77
ec62d942 78 put_bits(pb, bits, AV_RB16(src + 2*words)>>(16-bits));
98f7b56b
AJ
79}
80
de6d9b64
FB
81/* VLC decoding */
82
83//#define DEBUG_VLC
84
85#define GET_DATA(v, table, i, wrap, size) \
86{\
0c1a9eda 87 const uint8_t *ptr = (const uint8_t *)table + i * wrap;\
de6d9b64
FB
88 switch(size) {\
89 case 1:\
0c1a9eda 90 v = *(const uint8_t *)ptr;\
de6d9b64
FB
91 break;\
92 case 2:\
0c1a9eda 93 v = *(const uint16_t *)ptr;\
de6d9b64
FB
94 break;\
95 default:\
0c1a9eda 96 v = *(const uint32_t *)ptr;\
de6d9b64
FB
97 break;\
98 }\
99}
100
101
073c2593 102static int alloc_table(VLC *vlc, int size, int use_static)
de6d9b64
FB
103{
104 int index;
105 index = vlc->table_size;
106 vlc->table_size += size;
107 if (vlc->table_size > vlc->table_allocated) {
e518a49f 108 if(use_static)
ccc54864 109 abort(); //cant do anything, init_vlc() is used with too little memory
de6d9b64 110 vlc->table_allocated += (1 << vlc->bits);
1e224c54
RD
111 vlc->table = av_realloc(vlc->table,
112 sizeof(VLC_TYPE) * 2 * vlc->table_allocated);
8db1a1dd 113 if (!vlc->table)
de6d9b64
FB
114 return -1;
115 }
116 return index;
117}
118
8db1a1dd 119static int build_table(VLC *vlc, int table_nb_bits,
de6d9b64
FB
120 int nb_codes,
121 const void *bits, int bits_wrap, int bits_size,
122 const void *codes, int codes_wrap, int codes_size,
b613bacc 123 const void *symbols, int symbols_wrap, int symbols_size,
cea27ac7 124 uint32_t code_prefix, int n_prefix, int flags)
de6d9b64 125{
b613bacc 126 int i, j, k, n, table_size, table_index, nb, n1, index, code_prefix2, symbol;
0c1a9eda 127 uint32_t code;
8db1a1dd 128 VLC_TYPE (*table)[2];
de6d9b64
FB
129
130 table_size = 1 << table_nb_bits;
595324e1 131 table_index = alloc_table(vlc, table_size, flags & INIT_VLC_USE_NEW_STATIC);
de6d9b64 132#ifdef DEBUG_VLC
b8a99745 133 av_log(NULL,AV_LOG_DEBUG,"new table index=%d size=%d code_prefix=%x n=%d\n",
de6d9b64
FB
134 table_index, table_size, code_prefix, n_prefix);
135#endif
136 if (table_index < 0)
137 return -1;
8db1a1dd 138 table = &vlc->table[table_index];
de6d9b64
FB
139
140 for(i=0;i<table_size;i++) {
8db1a1dd
MN
141 table[i][1] = 0; //bits
142 table[i][0] = -1; //codes
de6d9b64
FB
143 }
144
145 /* first pass: map codes and compute auxillary table sizes */
146 for(i=0;i<nb_codes;i++) {
147 GET_DATA(n, bits, i, bits_wrap, bits_size);
148 GET_DATA(code, codes, i, codes_wrap, codes_size);
149 /* we accept tables with holes */
150 if (n <= 0)
151 continue;
b613bacc
LM
152 if (!symbols)
153 symbol = i;
154 else
155 GET_DATA(symbol, symbols, i, symbols_wrap, symbols_size);
de6d9b64 156#if defined(DEBUG_VLC) && 0
b8a99745 157 av_log(NULL,AV_LOG_DEBUG,"i=%d n=%d code=0x%x\n", i, n, code);
de6d9b64
FB
158#endif
159 /* if code matches the prefix, it is in the table */
160 n -= n_prefix;
4c4e7465 161 if (n > 0) {
769c4975
MR
162 if(flags & INIT_VLC_LE)
163 code_prefix2= code & (n_prefix>=32 ? 0xffffffff : (1 << n_prefix)-1);
164 else
165 code_prefix2= code >> n;
166 if (code_prefix2 == code_prefix) {
167 if (n <= table_nb_bits) {
168 /* no need to add another table */
169 j = (code << (table_nb_bits - n)) & (table_size - 1);
170 nb = 1 << (table_nb_bits - n);
171 for(k=0;k<nb;k++) {
172 if(flags & INIT_VLC_LE)
173 j = (code >> n_prefix) + (k<<n);
de6d9b64 174#ifdef DEBUG_VLC
769c4975
MR
175 av_log(NULL, AV_LOG_DEBUG, "%4x: code=%d n=%d\n",
176 j, i, n);
de6d9b64 177#endif
769c4975
MR
178 if (table[j][1] /*bits*/ != 0) {
179 av_log(NULL, AV_LOG_ERROR, "incorrect codes\n");
180 return -1;
181 }
182 table[j][1] = n; //bits
183 table[j][0] = symbol;
184 j++;
de6d9b64 185 }
769c4975
MR
186 } else {
187 n -= table_nb_bits;
188 j = (code >> ((flags & INIT_VLC_LE) ? n_prefix : n)) & ((1 << table_nb_bits) - 1);
de6d9b64 189#ifdef DEBUG_VLC
769c4975
MR
190 av_log(NULL,AV_LOG_DEBUG,"%4x: n=%d (subtable)\n",
191 j, n);
de6d9b64 192#endif
769c4975
MR
193 /* compute table size */
194 n1 = -table[j][1]; //bits
195 if (n > n1)
196 n1 = n;
197 table[j][1] = -n1; //bits
198 }
de6d9b64
FB
199 }
200 }
201 }
202
203 /* second pass : fill auxillary tables recursively */
204 for(i=0;i<table_size;i++) {
8db1a1dd 205 n = table[i][1]; //bits
de6d9b64
FB
206 if (n < 0) {
207 n = -n;
208 if (n > table_nb_bits) {
209 n = table_nb_bits;
8db1a1dd 210 table[i][1] = -n; //bits
de6d9b64
FB
211 }
212 index = build_table(vlc, n, nb_codes,
213 bits, bits_wrap, bits_size,
214 codes, codes_wrap, codes_size,
b613bacc 215 symbols, symbols_wrap, symbols_size,
cea27ac7
MN
216 (flags & INIT_VLC_LE) ? (code_prefix | (i << n_prefix)) : ((code_prefix << table_nb_bits) | i),
217 n_prefix + table_nb_bits, flags);
de6d9b64
FB
218 if (index < 0)
219 return -1;
220 /* note: realloc has been done, so reload tables */
8db1a1dd 221 table = &vlc->table[table_index];
6300c80a 222 table[i][0] = index; //code
de6d9b64
FB
223 }
224 }
225 return table_index;
226}
227
228
4e66ab3b
FB
229/* Build VLC decoding tables suitable for use with get_vlc().
230
231 'nb_bits' set thee decoding table size (2^nb_bits) entries. The
232 bigger it is, the faster is the decoding. But it should not be too
233 big to save memory and L1 cache. '9' is a good compromise.
115329f1 234
4e66ab3b
FB
235 'nb_codes' : number of vlcs codes
236
237 'bits' : table which gives the size (in bits) of each vlc code.
238
239 'codes' : table which gives the bit pattern of of each vlc code.
240
b613bacc
LM
241 'symbols' : table which gives the values to be returned from get_vlc().
242
4e66ab3b
FB
243 'xxx_wrap' : give the number of bytes between each entry of the
244 'bits' or 'codes' tables.
245
246 'xxx_size' : gives the number of bytes of each entry of the 'bits'
247 or 'codes' tables.
248
249 'wrap' and 'size' allows to use any memory configuration and types
b613bacc 250 (byte/word/long) to store the 'bits', 'codes', and 'symbols' tables.
073c2593
BP
251
252 'use_static' should be set to 1 for tables, which should be freed
253 with av_free_static(), 0 if free_vlc() will be used.
4e66ab3b 254*/
b613bacc 255int init_vlc_sparse(VLC *vlc, int nb_bits, int nb_codes,
de6d9b64 256 const void *bits, int bits_wrap, int bits_size,
073c2593 257 const void *codes, int codes_wrap, int codes_size,
b613bacc 258 const void *symbols, int symbols_wrap, int symbols_size,
d7645fb9 259 int flags)
de6d9b64
FB
260{
261 vlc->bits = nb_bits;
ccc54864
MN
262 if(flags & INIT_VLC_USE_NEW_STATIC){
263 if(vlc->table_size && vlc->table_size == vlc->table_allocated){
264 return 0;
265 }else if(vlc->table_size){
266 abort(); // fatal error, we are called on a partially initialized table
267 }
595324e1 268 }else {
073c2593
BP
269 vlc->table = NULL;
270 vlc->table_allocated = 0;
271 vlc->table_size = 0;
073c2593
BP
272 }
273
de6d9b64 274#ifdef DEBUG_VLC
b8a99745 275 av_log(NULL,AV_LOG_DEBUG,"build table nb_codes=%d\n", nb_codes);
de6d9b64
FB
276#endif
277
278 if (build_table(vlc, nb_bits, nb_codes,
279 bits, bits_wrap, bits_size,
280 codes, codes_wrap, codes_size,
b613bacc 281 symbols, symbols_wrap, symbols_size,
d7645fb9 282 0, 0, flags) < 0) {
85d366fd 283 av_freep(&vlc->table);
de6d9b64
FB
284 return -1;
285 }
ccc54864
MN
286 if((flags & INIT_VLC_USE_NEW_STATIC) && vlc->table_size != vlc->table_allocated)
287 av_log(NULL, AV_LOG_ERROR, "needed %d had %d\n", vlc->table_size, vlc->table_allocated);
de6d9b64
FB
288 return 0;
289}
290
291
292void free_vlc(VLC *vlc)
293{
85d366fd 294 av_freep(&vlc->table);
de6d9b64
FB
295}
296