[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 "common.h"
#include <math.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 = be2me_32(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 */
INT64 get_bit_count(PutBitContext *s)
{
    return (s->buf_ptr - s->buf + s->data_out_size) * 8 + (INT64)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 : escape 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 */
/* also true: n > s->bit_cnt */
unsigned int get_bits_long(GetBitContext *s, int n)
{
    unsigned int val;
    int bit_cnt;
    unsigned int bit_buf;

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

    bit_buf = s->bit_buf;
    bit_cnt = s->bit_cnt - n;
    
//    if (bit_cnt >= 0) {
//        val = bit_buf >> (32 - n);
//        bit_buf <<= n; 
//    } else 
    {
	UINT8 *buf_ptr;
        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) {
#if ARCH_X86
	    bit_buf = bswap_32(*((unsigned long*)(&buf_ptr[-4])));
#else
	    bit_buf = (buf_ptr[-4] << 24) |
		(buf_ptr[-3] << 16) |
                (buf_ptr[-2] << 8) |
                (buf_ptr[-1]);	    
#endif
        } 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;
}


/* Build VLC decoding tables suitable for use with get_vlc().

   'nb_bits' set thee decoding table size (2^nb_bits) entries. The
   bigger it is, the faster is the decoding. But it should not be too
   big to save memory and L1 cache. '9' is a good compromise.
   
   'nb_codes' : number of vlcs codes

   'bits' : table which gives the size (in bits) of each vlc code.

   'codes' : table which gives the bit pattern of of each vlc code.

   'xxx_wrap' : give the number of bytes between each entry of the
   'bits' or 'codes' tables.

   'xxx_size' : gives the number of bytes of each entry of the 'bits'
   or 'codes' tables.

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