Initial revision
[libav.git] / libavcodec / common.c
CommitLineData
de6d9b64
FB
1/*
2 * Common bit i/o utils
3 * Copyright (c) 2000, 2001 Gerard Lantau.
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
18 */
19#include <stdlib.h>
20#include <stdio.h>
21#include <string.h>
22#ifdef __FreeBSD__
23#include <sys/param.h>
24#endif
25#include <netinet/in.h>
26#include <math.h>
27#include "common.h"
28
29#define NDEBUG
30#include <assert.h>
31
32void init_put_bits(PutBitContext *s,
33 UINT8 *buffer, int buffer_size,
34 void *opaque,
35 void (*write_data)(void *, UINT8 *, int))
36{
37 s->buf = buffer;
38 s->buf_ptr = s->buf;
39 s->buf_end = s->buf + buffer_size;
40 s->bit_cnt=0;
41 s->bit_buf=0;
42 s->data_out_size = 0;
43 s->write_data = write_data;
44 s->opaque = opaque;
45}
46
47static void flush_buffer(PutBitContext *s)
48{
49 int size;
50 if (s->write_data) {
51 size = s->buf_ptr - s->buf;
52 if (size > 0)
53 s->write_data(s->opaque, s->buf, size);
54 s->buf_ptr = s->buf;
55 s->data_out_size += size;
56 }
57}
58
59void put_bits(PutBitContext *s, int n, unsigned int value)
60{
61 unsigned int bit_buf;
62 int bit_cnt;
63
64#ifdef STATS
65 st_out_bit_counts[st_current_index] += n;
66#endif
67 // printf("put_bits=%d %x\n", n, value);
68 assert(n == 32 || value < (1U << n));
69
70 bit_buf = s->bit_buf;
71 bit_cnt = s->bit_cnt;
72
73 // printf("n=%d value=%x cnt=%d buf=%x\n", n, value, bit_cnt, bit_buf);
74 /* XXX: optimize */
75 if (n < (32-bit_cnt)) {
76 bit_buf |= value << (32 - n - bit_cnt);
77 bit_cnt+=n;
78 } else {
79 bit_buf |= value >> (n + bit_cnt - 32);
80 *(UINT32 *)s->buf_ptr = htonl(bit_buf);
81 //printf("bitbuf = %08x\n", bit_buf);
82 s->buf_ptr+=4;
83 if (s->buf_ptr >= s->buf_end)
84 flush_buffer(s);
85 bit_cnt=bit_cnt + n - 32;
86 if (bit_cnt == 0) {
87 bit_buf = 0;
88 } else {
89 bit_buf = value << (32 - bit_cnt);
90 }
91 }
92
93 s->bit_buf = bit_buf;
94 s->bit_cnt = bit_cnt;
95}
96
97/* return the number of bits output */
98long long get_bit_count(PutBitContext *s)
99{
100 return (s->buf_ptr - s->buf + s->data_out_size) * 8 + (long long)s->bit_cnt;
101}
102
103void align_put_bits(PutBitContext *s)
104{
105 put_bits(s,(8 - s->bit_cnt) & 7,0);
106}
107
108/* pad the end of the output stream with zeros */
109void flush_put_bits(PutBitContext *s)
110{
111 while (s->bit_cnt > 0) {
112 /* XXX: should test end of buffer */
113 *s->buf_ptr++=s->bit_buf >> 24;
114 s->bit_buf<<=8;
115 s->bit_cnt-=8;
116 }
117 flush_buffer(s);
118 s->bit_cnt=0;
119 s->bit_buf=0;
120}
121
122/* for jpeg : espace 0xff with 0x00 after it */
123void jput_bits(PutBitContext *s, int n, unsigned int value)
124{
125 unsigned int bit_buf, b;
126 int bit_cnt, i;
127
128 assert(n == 32 || value < (1U << n));
129
130 bit_buf = s->bit_buf;
131 bit_cnt = s->bit_cnt;
132
133 //printf("n=%d value=%x cnt=%d buf=%x\n", n, value, bit_cnt, bit_buf);
134 /* XXX: optimize */
135 if (n < (32-bit_cnt)) {
136 bit_buf |= value << (32 - n - bit_cnt);
137 bit_cnt+=n;
138 } else {
139 bit_buf |= value >> (n + bit_cnt - 32);
140 /* handle escape */
141 for(i=0;i<4;i++) {
142 b = (bit_buf >> 24);
143 *(s->buf_ptr++) = b;
144 if (b == 0xff)
145 *(s->buf_ptr++) = 0;
146 bit_buf <<= 8;
147 }
148 /* we flush the buffer sooner to handle worst case */
149 if (s->buf_ptr >= (s->buf_end - 8))
150 flush_buffer(s);
151
152 bit_cnt=bit_cnt + n - 32;
153 if (bit_cnt == 0) {
154 bit_buf = 0;
155 } else {
156 bit_buf = value << (32 - bit_cnt);
157 }
158 }
159
160 s->bit_buf = bit_buf;
161 s->bit_cnt = bit_cnt;
162}
163
164/* pad the end of the output stream with zeros */
165void jflush_put_bits(PutBitContext *s)
166{
167 unsigned int b;
168
169 while (s->bit_cnt > 0) {
170 b = s->bit_buf >> 24;
171 *s->buf_ptr++ = b;
172 if (b == 0xff)
173 *s->buf_ptr++ = 0;
174 s->bit_buf<<=8;
175 s->bit_cnt-=8;
176 }
177 flush_buffer(s);
178 s->bit_cnt=0;
179 s->bit_buf=0;
180}
181
182/* bit input functions */
183
184void init_get_bits(GetBitContext *s,
185 UINT8 *buffer, int buffer_size)
186{
187 s->buf = buffer;
188 s->buf_ptr = buffer;
189 s->buf_end = buffer + buffer_size;
190 s->bit_cnt = 0;
191 s->bit_buf = 0;
192 while (s->buf_ptr < s->buf_end &&
193 s->bit_cnt < 32) {
194 s->bit_buf |= (*s->buf_ptr++ << (24 - s->bit_cnt));
195 s->bit_cnt += 8;
196 }
197}
198
199/* n must be >= 1 and <= 32 */
200unsigned int get_bits(GetBitContext *s, int n)
201{
202 unsigned int val;
203 int bit_cnt;
204 unsigned int bit_buf;
205 UINT8 *buf_ptr;
206
207#ifdef STATS
208 st_bit_counts[st_current_index] += n;
209#endif
210
211 bit_cnt = s->bit_cnt;
212 bit_buf = s->bit_buf;
213
214 bit_cnt -= n;
215 if (bit_cnt >= 0) {
216 /* most common case here */
217 val = bit_buf >> (32 - n);
218 bit_buf <<= n;
219 } else {
220 val = bit_buf >> (32 - n);
221 buf_ptr = s->buf_ptr;
222 buf_ptr += 4;
223 /* handle common case: we can read everything */
224 if (buf_ptr <= s->buf_end) {
225 bit_buf = (buf_ptr[-4] << 24) |
226 (buf_ptr[-3] << 16) |
227 (buf_ptr[-2] << 8) |
228 (buf_ptr[-1]);
229 } else {
230 buf_ptr -= 4;
231 bit_buf = 0;
232 if (buf_ptr < s->buf_end)
233 bit_buf |= *buf_ptr++ << 24;
234 if (buf_ptr < s->buf_end)
235 bit_buf |= *buf_ptr++ << 16;
236 if (buf_ptr < s->buf_end)
237 bit_buf |= *buf_ptr++ << 8;
238 if (buf_ptr < s->buf_end)
239 bit_buf |= *buf_ptr++;
240 }
241 s->buf_ptr = buf_ptr;
242 val |= bit_buf >> (32 + bit_cnt);
243 bit_buf <<= - bit_cnt;
244 bit_cnt += 32;
245 }
246 s->bit_buf = bit_buf;
247 s->bit_cnt = bit_cnt;
248 return val;
249}
250
251void align_get_bits(GetBitContext *s)
252{
253 int n;
254 n = s->bit_cnt & 7;
255 if (n > 0) {
256 get_bits(s, n);
257 }
258}
259
260/* VLC decoding */
261
262//#define DEBUG_VLC
263
264#define GET_DATA(v, table, i, wrap, size) \
265{\
266 UINT8 *ptr = (UINT8 *)table + i * wrap;\
267 switch(size) {\
268 case 1:\
269 v = *(UINT8 *)ptr;\
270 break;\
271 case 2:\
272 v = *(UINT16 *)ptr;\
273 break;\
274 default:\
275 v = *(UINT32 *)ptr;\
276 break;\
277 }\
278}
279
280
281static int alloc_table(VLC *vlc, int size)
282{
283 int index;
284 index = vlc->table_size;
285 vlc->table_size += size;
286 if (vlc->table_size > vlc->table_allocated) {
287 vlc->table_allocated += (1 << vlc->bits);
288 vlc->table_bits = realloc(vlc->table_bits,
289 sizeof(INT8) * vlc->table_allocated);
290 vlc->table_codes = realloc(vlc->table_codes,
291 sizeof(INT16) * vlc->table_allocated);
292 if (!vlc->table_bits ||
293 !vlc->table_codes)
294 return -1;
295 }
296 return index;
297}
298
299static int build_table(VLC *vlc, int table_nb_bits,
300 int nb_codes,
301 const void *bits, int bits_wrap, int bits_size,
302 const void *codes, int codes_wrap, int codes_size,
303 UINT32 code_prefix, int n_prefix)
304{
305 int i, j, k, n, table_size, table_index, nb, n1, index;
306 UINT32 code;
307 INT8 *table_bits;
308 INT16 *table_codes;
309
310 table_size = 1 << table_nb_bits;
311 table_index = alloc_table(vlc, table_size);
312#ifdef DEBUG_VLC
313 printf("new table index=%d size=%d code_prefix=%x n=%d\n",
314 table_index, table_size, code_prefix, n_prefix);
315#endif
316 if (table_index < 0)
317 return -1;
318 table_bits = &vlc->table_bits[table_index];
319 table_codes = &vlc->table_codes[table_index];
320
321 for(i=0;i<table_size;i++) {
322 table_bits[i] = 0;
323 table_codes[i] = -1;
324 }
325
326 /* first pass: map codes and compute auxillary table sizes */
327 for(i=0;i<nb_codes;i++) {
328 GET_DATA(n, bits, i, bits_wrap, bits_size);
329 GET_DATA(code, codes, i, codes_wrap, codes_size);
330 /* we accept tables with holes */
331 if (n <= 0)
332 continue;
333#if defined(DEBUG_VLC) && 0
334 printf("i=%d n=%d code=0x%x\n", i, n, code);
335#endif
336 /* if code matches the prefix, it is in the table */
337 n -= n_prefix;
338 if (n > 0 && (code >> n) == code_prefix) {
339 if (n <= table_nb_bits) {
340 /* no need to add another table */
341 j = (code << (table_nb_bits - n)) & (table_size - 1);
342 nb = 1 << (table_nb_bits - n);
343 for(k=0;k<nb;k++) {
344#ifdef DEBUG_VLC
345 printf("%4x: code=%d n=%d\n",
346 j, i, n);
347#endif
348 if (table_bits[j] != 0) {
349 fprintf(stderr, "incorrect codes\n");
350 exit(1);
351 }
352 table_bits[j] = n;
353 table_codes[j] = i;
354 j++;
355 }
356 } else {
357 n -= table_nb_bits;
358 j = (code >> n) & ((1 << table_nb_bits) - 1);
359#ifdef DEBUG_VLC
360 printf("%4x: n=%d (subtable)\n",
361 j, n);
362#endif
363 /* compute table size */
364 n1 = -table_bits[j];
365 if (n > n1)
366 n1 = n;
367 table_bits[j] = -n1;
368 }
369 }
370 }
371
372 /* second pass : fill auxillary tables recursively */
373 for(i=0;i<table_size;i++) {
374 n = table_bits[i];
375 if (n < 0) {
376 n = -n;
377 if (n > table_nb_bits) {
378 n = table_nb_bits;
379 table_bits[i] = -n;
380 }
381 index = build_table(vlc, n, nb_codes,
382 bits, bits_wrap, bits_size,
383 codes, codes_wrap, codes_size,
384 (code_prefix << table_nb_bits) | i,
385 n_prefix + table_nb_bits);
386 if (index < 0)
387 return -1;
388 /* note: realloc has been done, so reload tables */
389 table_bits = &vlc->table_bits[table_index];
390 table_codes = &vlc->table_codes[table_index];
391 table_codes[i] = index;
392 }
393 }
394 return table_index;
395}
396
397
398/* wrap and size allow to handle most types of storage. */
399int init_vlc(VLC *vlc, int nb_bits, int nb_codes,
400 const void *bits, int bits_wrap, int bits_size,
401 const void *codes, int codes_wrap, int codes_size)
402{
403 vlc->bits = nb_bits;
404 vlc->table_bits = NULL;
405 vlc->table_codes = NULL;
406 vlc->table_allocated = 0;
407 vlc->table_size = 0;
408#ifdef DEBUG_VLC
409 printf("build table nb_codes=%d\n", nb_codes);
410#endif
411
412 if (build_table(vlc, nb_bits, nb_codes,
413 bits, bits_wrap, bits_size,
414 codes, codes_wrap, codes_size,
415 0, 0) < 0) {
416 if (vlc->table_bits)
417 free(vlc->table_bits);
418 if (vlc->table_codes)
419 free(vlc->table_codes);
420 return -1;
421 }
422 return 0;
423}
424
425
426void free_vlc(VLC *vlc)
427{
428 free(vlc->table_bits);
429 free(vlc->table_codes);
430}
431
432int get_vlc(GetBitContext *s, VLC *vlc)
433{
434 int bit_cnt, code, n, nb_bits, index;
435 UINT32 bit_buf;
436 INT16 *table_codes;
437 INT8 *table_bits;
438 UINT8 *buf_ptr;
439
440 SAVE_BITS(s);
441 nb_bits = vlc->bits;
442 table_codes = vlc->table_codes;
443 table_bits = vlc->table_bits;
444 for(;;) {
445 SHOW_BITS(s, index, nb_bits);
446 code = table_codes[index];
447 n = table_bits[index];
448 if (n > 0) {
449 /* most common case */
450 FLUSH_BITS(n);
451#ifdef STATS
452 st_bit_counts[st_current_index] += n;
453#endif
454 break;
455 } else if (n == 0) {
456 return -1;
457 } else {
458 FLUSH_BITS(nb_bits);
459#ifdef STATS
460 st_bit_counts[st_current_index] += nb_bits;
461#endif
462 nb_bits = -n;
463 table_codes = vlc->table_codes + code;
464 table_bits = vlc->table_bits + code;
465 }
466 }
467 RESTORE_BITS(s);
468 return code;
469}