[libav.git] / libavcodec / common.c

/*
 * Common bit i/o utils
 * Copyright (c) 2000, 2001 Gerard Lantau.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#ifdef __FreeBSD__
#include <sys/param.h>
#endif
#include <netinet/in.h>
#include <math.h>
#include "common.h"

#define NDEBUG
#include <assert.h>

void init_put_bits(PutBitContext *s, 
                   UINT8 *buffer, int buffer_size,
                   void *opaque,
                   void (*write_data)(void *, UINT8 *, int))
{
    s->buf = buffer;
    s->buf_ptr = s->buf;
    s->buf_end = s->buf + buffer_size;
    s->bit_cnt=0;
    s->bit_buf=0;
    s->data_out_size = 0;
    s->write_data = write_data;
    s->opaque = opaque;
}

static void flush_buffer(PutBitContext *s)
{
    int size;
    if (s->write_data) {
        size = s->buf_ptr - s->buf;
        if (size > 0)
            s->write_data(s->opaque, s->buf, size);
        s->buf_ptr = s->buf;
        s->data_out_size += size;
    }
}

void put_bits(PutBitContext *s, int n, unsigned int value)
{
    unsigned int bit_buf;
    int bit_cnt;

#ifdef STATS
    st_out_bit_counts[st_current_index] += n;
#endif
    //    printf("put_bits=%d %x\n", n, value);
    assert(n == 32 || value < (1U << n));

    bit_buf = s->bit_buf;
    bit_cnt = s->bit_cnt;

    //    printf("n=%d value=%x cnt=%d buf=%x\n", n, value, bit_cnt, bit_buf);
    /* XXX: optimize */
    if (n < (32-bit_cnt)) {
        bit_buf |= value << (32 - n - bit_cnt);
        bit_cnt+=n;
    } else {
        bit_buf |= value >> (n + bit_cnt - 32);
        *(UINT32 *)s->buf_ptr = htonl(bit_buf);
        //printf("bitbuf = %08x\n", bit_buf);
        s->buf_ptr+=4;
        if (s->buf_ptr >= s->buf_end)
            flush_buffer(s);
        bit_cnt=bit_cnt + n - 32;
        if (bit_cnt == 0) {
            bit_buf = 0;
        } else {
            bit_buf = value << (32 - bit_cnt);
        }
    }
    
    s->bit_buf = bit_buf;
    s->bit_cnt = bit_cnt;
}

/* return the number of bits output */
long long get_bit_count(PutBitContext *s)
{
    return (s->buf_ptr - s->buf + s->data_out_size) * 8 + (long long)s->bit_cnt;
}

void align_put_bits(PutBitContext *s)
{
    put_bits(s,(8 - s->bit_cnt) & 7,0);
}

/* pad the end of the output stream with zeros */
void flush_put_bits(PutBitContext *s)
{
    while (s->bit_cnt > 0) {
        /* XXX: should test end of buffer */
        *s->buf_ptr++=s->bit_buf >> 24;
        s->bit_buf<<=8;
        s->bit_cnt-=8;
    }
    flush_buffer(s);
    s->bit_cnt=0;
    s->bit_buf=0;
}

/* for jpeg : espace 0xff with 0x00 after it */
void jput_bits(PutBitContext *s, int n, unsigned int value)
{
    unsigned int bit_buf, b;
    int bit_cnt, i;
    
    assert(n == 32 || value < (1U << n));

    bit_buf = s->bit_buf;
    bit_cnt = s->bit_cnt;

    //printf("n=%d value=%x cnt=%d buf=%x\n", n, value, bit_cnt, bit_buf);
    /* XXX: optimize */
    if (n < (32-bit_cnt)) {
        bit_buf |= value << (32 - n - bit_cnt);
        bit_cnt+=n;
    } else {
        bit_buf |= value >> (n + bit_cnt - 32);
        /* handle escape */
        for(i=0;i<4;i++) {
            b = (bit_buf >> 24);
            *(s->buf_ptr++) = b;
            if (b == 0xff)
                *(s->buf_ptr++) = 0;
            bit_buf <<= 8;
        }
        /* we flush the buffer sooner to handle worst case */
        if (s->buf_ptr >= (s->buf_end - 8))
            flush_buffer(s);

        bit_cnt=bit_cnt + n - 32;
        if (bit_cnt == 0) {
            bit_buf = 0;
        } else {
            bit_buf = value << (32 - bit_cnt);
        }
    }
    
    s->bit_buf = bit_buf;
    s->bit_cnt = bit_cnt;
}

/* pad the end of the output stream with zeros */
void jflush_put_bits(PutBitContext *s)
{
    unsigned int b;

    while (s->bit_cnt > 0) {
        b = s->bit_buf >> 24;
        *s->buf_ptr++ = b;
        if (b == 0xff)
            *s->buf_ptr++ = 0;
        s->bit_buf<<=8;
        s->bit_cnt-=8;
    }
    flush_buffer(s);
    s->bit_cnt=0;
    s->bit_buf=0;
}

/* bit input functions */

void init_get_bits(GetBitContext *s, 
                   UINT8 *buffer, int buffer_size)
{
    s->buf = buffer;
    s->buf_ptr = buffer;
    s->buf_end = buffer + buffer_size;
    s->bit_cnt = 0;
    s->bit_buf = 0;
    while (s->buf_ptr < s->buf_end && 
           s->bit_cnt < 32) {
        s->bit_buf |= (*s->buf_ptr++ << (24 - s->bit_cnt));
        s->bit_cnt += 8;
    }
}

/* n must be >= 1 and <= 32 */
unsigned int get_bits(GetBitContext *s, int n)
{
    unsigned int val;
    int bit_cnt;
    unsigned int bit_buf;
    UINT8 *buf_ptr;

#ifdef STATS
    st_bit_counts[st_current_index] += n;
#endif

    bit_cnt = s->bit_cnt;
    bit_buf = s->bit_buf;
    
    bit_cnt -= n;
    if (bit_cnt >= 0) {
        /* most common case here */
        val = bit_buf >> (32 - n);
        bit_buf <<= n; 
    } else {
        val = bit_buf >> (32 - n);
        buf_ptr = s->buf_ptr;
        buf_ptr += 4;
        /* handle common case: we can read everything */
        if (buf_ptr <= s->buf_end) {
            bit_buf = (buf_ptr[-4] << 24) |
                (buf_ptr[-3] << 16) |
                (buf_ptr[-2] << 8) |
                (buf_ptr[-1]);
        } else {
            buf_ptr -= 4;
            bit_buf = 0;
            if (buf_ptr < s->buf_end)
                bit_buf |= *buf_ptr++ << 24;
            if (buf_ptr < s->buf_end)
                bit_buf |= *buf_ptr++ << 16;
            if (buf_ptr < s->buf_end)
                bit_buf |= *buf_ptr++ << 8;
            if (buf_ptr < s->buf_end)
                bit_buf |= *buf_ptr++;
        }
        s->buf_ptr = buf_ptr;
        val |= bit_buf >> (32 + bit_cnt);
        bit_buf <<= - bit_cnt;
        bit_cnt += 32;
    }
    s->bit_buf = bit_buf;
    s->bit_cnt = bit_cnt;
    return val;
}

void align_get_bits(GetBitContext *s)
{
    int n;
    n = s->bit_cnt & 7;
    if (n > 0) {
        get_bits(s, n);
    }
}

/* VLC decoding */

//#define DEBUG_VLC

#define GET_DATA(v, table, i, wrap, size) \
{\
    UINT8 *ptr = (UINT8 *)table + i * wrap;\
    switch(size) {\
    case 1:\
        v = *(UINT8 *)ptr;\
        break;\
    case 2:\
        v = *(UINT16 *)ptr;\
        break;\
    default:\
        v = *(UINT32 *)ptr;\
        break;\
    }\
}


static int alloc_table(VLC *vlc, int size)
{
    int index;
    index = vlc->table_size;
    vlc->table_size += size;
    if (vlc->table_size > vlc->table_allocated) {
        vlc->table_allocated += (1 << vlc->bits);
        vlc->table_bits = realloc(vlc->table_bits, 
                                  sizeof(INT8) * vlc->table_allocated);
        vlc->table_codes = realloc(vlc->table_codes,
                                   sizeof(INT16) * vlc->table_allocated);
        if (!vlc->table_bits ||
            !vlc->table_codes)
            return -1;
    }
    return index;
}

static int build_table(VLC *vlc, int table_nb_bits, 
                       int nb_codes,
                       const void *bits, int bits_wrap, int bits_size,
                       const void *codes, int codes_wrap, int codes_size,
                       UINT32 code_prefix, int n_prefix)
{
    int i, j, k, n, table_size, table_index, nb, n1, index;
    UINT32 code;
    INT8 *table_bits;
    INT16 *table_codes;

    table_size = 1 << table_nb_bits;
    table_index = alloc_table(vlc, table_size);
#ifdef DEBUG_VLC
    printf("new table index=%d size=%d code_prefix=%x n=%d\n", 
           table_index, table_size, code_prefix, n_prefix);
#endif
    if (table_index < 0)
        return -1;
    table_bits = &vlc->table_bits[table_index];
    table_codes = &vlc->table_codes[table_index];

    for(i=0;i<table_size;i++) {
        table_bits[i] = 0;
        table_codes[i] = -1;
    }

    /* first pass: map codes and compute auxillary table sizes */
    for(i=0;i<nb_codes;i++) {
        GET_DATA(n, bits, i, bits_wrap, bits_size);
        GET_DATA(code, codes, i, codes_wrap, codes_size);
        /* we accept tables with holes */
        if (n <= 0)
            continue;
#if defined(DEBUG_VLC) && 0
        printf("i=%d n=%d code=0x%x\n", i, n, code);
#endif
        /* if code matches the prefix, it is in the table */
        n -= n_prefix;
        if (n > 0 && (code >> n) == code_prefix) {
            if (n <= table_nb_bits) {
                /* no need to add another table */
                j = (code << (table_nb_bits - n)) & (table_size - 1);
                nb = 1 << (table_nb_bits - n);
                for(k=0;k<nb;k++) {
#ifdef DEBUG_VLC
                    printf("%4x: code=%d n=%d\n",
                           j, i, n);
#endif
                    if (table_bits[j] != 0) {
                        fprintf(stderr, "incorrect codes\n");
                        exit(1);
                    }
                    table_bits[j] = n;
                    table_codes[j] = i;
                    j++;
                }
            } else {
                n -= table_nb_bits;
                j = (code >> n) & ((1 << table_nb_bits) - 1);
#ifdef DEBUG_VLC
                printf("%4x: n=%d (subtable)\n",
                       j, n);
#endif
                /* compute table size */
                n1 = -table_bits[j];
                if (n > n1)
                    n1 = n;
                table_bits[j] = -n1;
            }
        }
    }

    /* second pass : fill auxillary tables recursively */
    for(i=0;i<table_size;i++) {
        n = table_bits[i];
        if (n < 0) {
            n = -n;
            if (n > table_nb_bits) {
                n = table_nb_bits;
                table_bits[i] = -n;
            }
            index = build_table(vlc, n, nb_codes,
                                bits, bits_wrap, bits_size,
                                codes, codes_wrap, codes_size,
                                (code_prefix << table_nb_bits) | i,
                                n_prefix + table_nb_bits);
            if (index < 0)
                return -1;
            /* note: realloc has been done, so reload tables */
            table_bits = &vlc->table_bits[table_index];
            table_codes = &vlc->table_codes[table_index];
            table_codes[i] = index;
        }
    }
    return table_index;
}


/* wrap and size allow to handle most types of storage.  */
int init_vlc(VLC *vlc, int nb_bits, int nb_codes,
             const void *bits, int bits_wrap, int bits_size,
             const void *codes, int codes_wrap, int codes_size)
{
    vlc->bits = nb_bits;
    vlc->table_bits = NULL;
    vlc->table_codes = NULL;
    vlc->table_allocated = 0;
    vlc->table_size = 0;
#ifdef DEBUG_VLC
    printf("build table nb_codes=%d\n", nb_codes);
#endif

    if (build_table(vlc, nb_bits, nb_codes,
                    bits, bits_wrap, bits_size,
                    codes, codes_wrap, codes_size,
                    0, 0) < 0) {
        if (vlc->table_bits)
            free(vlc->table_bits);
        if (vlc->table_codes)
            free(vlc->table_codes);
        return -1;
    }
    return 0;
}


void free_vlc(VLC *vlc)
{
    free(vlc->table_bits);
    free(vlc->table_codes);
}

int get_vlc(GetBitContext *s, VLC *vlc)
{
    int bit_cnt, code, n, nb_bits, index;
    UINT32 bit_buf;
    INT16 *table_codes;
    INT8 *table_bits;
    UINT8 *buf_ptr;

    SAVE_BITS(s);
    nb_bits = vlc->bits;
    table_codes = vlc->table_codes;
    table_bits = vlc->table_bits;
    for(;;) {
        SHOW_BITS(s, index, nb_bits);
        code = table_codes[index];
        n = table_bits[index];
        if (n > 0) {
            /* most common case */
            FLUSH_BITS(n);
#ifdef STATS
            st_bit_counts[st_current_index] += n;
#endif
            break;
        } else if (n == 0) {
            return -1;
        } else {
            FLUSH_BITS(nb_bits);
#ifdef STATS
            st_bit_counts[st_current_index] += nb_bits;
#endif
            nb_bits = -n;
            table_codes = vlc->table_codes + code;
            table_bits = vlc->table_bits + code;
        }
    }
    RESTORE_BITS(s);
    return code;
}
Commit	Line	Data
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
	32	void 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
	47	static 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
	59	void 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 */
98	long 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
103	void 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 */
109	void 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 */
123	void 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 */
165	void 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
184	void 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 */
200	unsigned 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
251	void 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
281	static 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
299	static 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. */
399	int 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
426	void free_vlc(VLC *vlc)
427	{
428	free(vlc->table_bits);
429	free(vlc->table_codes);
430	}
431
432	int 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	}