[libav.git] / libavcodec / common.c

/*
 * Common bit i/o utils
 * Copyright (c) 2000, 2001 Fabrice Bellard.
 * Copyright (c) 2002-2004 Michael Niedermayer <michaelni@gmx.at>
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library 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
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 * alternative bitstream reader & writer by Michael Niedermayer <michaelni@gmx.at>
 */

/**
 * @file common.c
 * common internal api.
 */

#include "avcodec.h"

const uint8_t ff_sqrt_tab[128]={
        0, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5,
        5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
        8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
        9, 9, 9, 9,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,11,11,11,11,11,11,11
};

const uint8_t ff_log2_tab[256]={
        0,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
        5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
        6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
        6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
        7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
        7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
        7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
        7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7
};

void align_put_bits(PutBitContext *s)
{
#ifdef ALT_BITSTREAM_WRITER
    put_bits(s,(  - s->index) & 7,0);
#else
    put_bits(s,s->bit_left & 7,0);
#endif
}

void put_string(PutBitContext * pbc, char *s, int put_zero)
{
    while(*s){
        put_bits(pbc, 8, *s);
        s++;
    }
    if(put_zero)
        put_bits(pbc, 8, 0);
}

/* bit input functions */

/** 
 * reads 0-32 bits.
 */
unsigned int get_bits_long(GetBitContext *s, int n){
    if(n<=17) return get_bits(s, n);
    else{
        int ret= get_bits(s, 16) << (n-16);
        return ret | get_bits(s, n-16);
    }
}

/** 
 * shows 0-32 bits.
 */
unsigned int show_bits_long(GetBitContext *s, int n){
    if(n<=17) return show_bits(s, n);
    else{
        GetBitContext gb= *s;
        int ret= get_bits_long(s, n);
        *s= gb;
        return ret;
    }
}

void align_get_bits(GetBitContext *s)
{
    int n= (-get_bits_count(s)) & 7;
    if(n) skip_bits(s, n);
}

int check_marker(GetBitContext *s, const char *msg)
{
    int bit= get_bits1(s);
    if(!bit)
	    av_log(NULL, AV_LOG_INFO, "Marker bit missing %s\n", msg);

    return bit;
}

/* VLC decoding */

//#define DEBUG_VLC

#define GET_DATA(v, table, i, wrap, size) \
{\
    const uint8_t *ptr = (const uint8_t *)table + i * wrap;\
    switch(size) {\
    case 1:\
        v = *(const uint8_t *)ptr;\
        break;\
    case 2:\
        v = *(const uint16_t *)ptr;\
        break;\
    default:\
        v = *(const uint32_t *)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 = av_realloc(vlc->table,
                                sizeof(VLC_TYPE) * 2 * vlc->table_allocated);
        if (!vlc->table)
            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_t code_prefix, int n_prefix)
{
    int i, j, k, n, table_size, table_index, nb, n1, index;
    uint32_t code;
    VLC_TYPE (*table)[2];

    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 = &vlc->table[table_index];

    for(i=0;i<table_size;i++) {
        table[i][1] = 0; //bits
        table[i][0] = -1; //codes
    }

    /* 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
                    av_log(NULL, AV_LOG_DEBUG, "%4x: code=%d n=%d\n",
                           j, i, n);
#endif
                    if (table[j][1] /*bits*/ != 0) {
                        av_log(NULL, AV_LOG_ERROR, "incorrect codes\n");
                        return -1;
                    }
                    table[j][1] = n; //bits
                    table[j][0] = i; //code
                    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[j][1]; //bits
                if (n > n1)
                    n1 = n;
                table[j][1] = -n1; //bits
            }
        }
    }

    /* second pass : fill auxillary tables recursively */
    for(i=0;i<table_size;i++) {
        n = table[i][1]; //bits
        if (n < 0) {
            n = -n;
            if (n > table_nb_bits) {
                n = table_nb_bits;
                table[i][1] = -n; //bits
            }
            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 = &vlc->table[table_index];
            table[i][0] = index; //code
        }
    }
    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 = 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) {
        av_free(vlc->table);
        return -1;
    }
    return 0;
}


void free_vlc(VLC *vlc)
{
    av_free(vlc->table);
}

int64_t ff_gcd(int64_t a, int64_t b){
    if(b) return ff_gcd(b, a%b);
    else  return a;
}
Commit	Line	Data
de6d9b64 FB	1	/*
de6d9b64 FB	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	*
ff4ec49e FB	6	* This library is free software; you can redistribute it and/or
	7	* modify it under the terms of the GNU Lesser General Public
	8	* License as published by the Free Software Foundation; either
	9	* version 2 of the License, or (at your option) any later version.
de6d9b64	10	*
ff4ec49e	11	* This library is distributed in the hope that it will be useful,
de6d9b64	12	* but WITHOUT ANY WARRANTY; without even the implied warranty of
ff4ec49e FB	13	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
ff4ec49e FB	14	* Lesser General Public License for more details.
de6d9b64	15	*
ff4ec49e FB	16	* You should have received a copy of the GNU Lesser General Public
	17	* License along with this library; if not, write to the Free Software
	18	* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
27a3e2c5	19	*
17592475	20	* alternative bitstream reader & writer by Michael Niedermayer <michaelni@gmx.at>
de6d9b64	21	*/
983e3246 MN	22
	23	/**
	24	* @file common.c
	25	* common internal api.
	26	*/
	27
df595131	28	#include "avcodec.h"
a9b3f630	29
0c1a9eda	30	const uint8_t ff_sqrt_tab[128]={
f36db5df MN	31	0, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5,
	32	5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
	33	8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
	34	9, 9, 9, 9,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,11,11,11,11,11,11,11
	35	};
	36
c81f0349 MN	37	const uint8_t ff_log2_tab[256]={
	38	0,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
	39	5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
	40	6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
	41	6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
	42	7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
	43	7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
	44	7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
	45	7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7
	46	};
	47
de6d9b64 FB	48	void align_put_bits(PutBitContext *s)
de6d9b64 FB	49	{
17592475 MN	50	#ifdef ALT_BITSTREAM_WRITER
	51	put_bits(s,( - s->index) & 7,0);
	52	#else
d8cf5aea	53	put_bits(s,s->bit_left & 7,0);
17592475	54	#endif
de6d9b64 FB	55	}
de6d9b64 FB	56
99683a30	57	void put_string(PutBitContext * pbc, char *s, int put_zero)
9717dad8 MN	58	{
	59	while(*s){
	60	put_bits(pbc, 8, *s);
	61	s++;
	62	}
99683a30 MN	63	if(put_zero)
99683a30 MN	64	put_bits(pbc, 8, 0);
9717dad8 MN	65	}
9717dad8 MN	66
de6d9b64 FB	67	/* bit input functions */
de6d9b64 FB	68
17fb5fd3 MN	69	/**
	70	* reads 0-32 bits.
	71	*/
	72	unsigned int get_bits_long(GetBitContext *s, int n){
	73	if(n<=17) return get_bits(s, n);
	74	else{
	75	int ret= get_bits(s, 16) << (n-16);
	76	return ret \| get_bits(s, n-16);
	77	}
	78	}
	79
	80	/**
	81	* shows 0-32 bits.
	82	*/
	83	unsigned int show_bits_long(GetBitContext *s, int n){
	84	if(n<=17) return show_bits(s, n);
	85	else{
	86	GetBitContext gb= *s;
	87	int ret= get_bits_long(s, n);
	88	*s= gb;
	89	return ret;
	90	}
	91	}
	92
de6d9b64 FB	93	void align_get_bits(GetBitContext *s)
de6d9b64 FB	94	{
8db1a1dd MN	95	int n= (-get_bits_count(s)) & 7;
8db1a1dd MN	96	if(n) skip_bits(s, n);
de6d9b64	97	}
27a3e2c5	98
18f77016	99	int check_marker(GetBitContext s, const char msg)
49c9325f MN	100	{
49c9325f MN	101	int bit= get_bits1(s);
9b879566 MB	102	if(!bit)
9b879566 MB	103	av_log(NULL, AV_LOG_INFO, "Marker bit missing %s\n", msg);
49c9325f MN	104
	105	return bit;
	106	}
	107
de6d9b64 FB	108	/* VLC decoding */
	109
	110	//#define DEBUG_VLC
	111
	112	#define GET_DATA(v, table, i, wrap, size) \
	113	{\
0c1a9eda	114	const uint8_t ptr = (const uint8_t )table + i * wrap;\
de6d9b64 FB	115	switch(size) {\
de6d9b64 FB	116	case 1:\
0c1a9eda	117	v = (const uint8_t )ptr;\
de6d9b64 FB	118	break;\
de6d9b64 FB	119	case 2:\
0c1a9eda	120	v = (const uint16_t )ptr;\
de6d9b64 FB	121	break;\
de6d9b64 FB	122	default:\
0c1a9eda	123	v = (const uint32_t )ptr;\
de6d9b64 FB	124	break;\
	125	}\
	126	}
	127
	128
	129	static int alloc_table(VLC *vlc, int size)
	130	{
	131	int index;
	132	index = vlc->table_size;
	133	vlc->table_size += size;
	134	if (vlc->table_size > vlc->table_allocated) {
	135	vlc->table_allocated += (1 << vlc->bits);
8e1e6f31 FB	136	vlc->table = av_realloc(vlc->table,
8e1e6f31 FB	137	sizeof(VLC_TYPE) * 2 * vlc->table_allocated);
8db1a1dd	138	if (!vlc->table)
de6d9b64 FB	139	return -1;
	140	}
	141	return index;
	142	}
	143
8db1a1dd	144	static int build_table(VLC *vlc, int table_nb_bits,
de6d9b64 FB	145	int nb_codes,
	146	const void *bits, int bits_wrap, int bits_size,
	147	const void *codes, int codes_wrap, int codes_size,
0c1a9eda	148	uint32_t code_prefix, int n_prefix)
de6d9b64 FB	149	{
de6d9b64 FB	150	int i, j, k, n, table_size, table_index, nb, n1, index;
0c1a9eda	151	uint32_t code;
8db1a1dd	152	VLC_TYPE (*table)[2];
de6d9b64 FB	153
	154	table_size = 1 << table_nb_bits;
	155	table_index = alloc_table(vlc, table_size);
	156	#ifdef DEBUG_VLC
8db1a1dd	157	printf("new table index=%d size=%d code_prefix=%x n=%d\n",
de6d9b64 FB	158	table_index, table_size, code_prefix, n_prefix);
	159	#endif
	160	if (table_index < 0)
	161	return -1;
8db1a1dd	162	table = &vlc->table[table_index];
de6d9b64 FB	163
de6d9b64 FB	164	for(i=0;i<table_size;i++) {
8db1a1dd MN	165	table[i][1] = 0; //bits
8db1a1dd MN	166	table[i][0] = -1; //codes
de6d9b64 FB	167	}
	168
	169	/* first pass: map codes and compute auxillary table sizes */
	170	for(i=0;i<nb_codes;i++) {
	171	GET_DATA(n, bits, i, bits_wrap, bits_size);
	172	GET_DATA(code, codes, i, codes_wrap, codes_size);
	173	/* we accept tables with holes */
	174	if (n <= 0)
	175	continue;
	176	#if defined(DEBUG_VLC) && 0
	177	printf("i=%d n=%d code=0x%x\n", i, n, code);
	178	#endif
	179	/* if code matches the prefix, it is in the table */
	180	n -= n_prefix;
	181	if (n > 0 && (code >> n) == code_prefix) {
	182	if (n <= table_nb_bits) {
	183	/* no need to add another table */
	184	j = (code << (table_nb_bits - n)) & (table_size - 1);
	185	nb = 1 << (table_nb_bits - n);
	186	for(k=0;k<nb;k++) {
	187	#ifdef DEBUG_VLC
3d0ef6dd	188	av_log(NULL, AV_LOG_DEBUG, "%4x: code=%d n=%d\n",
de6d9b64 FB	189	j, i, n);
de6d9b64 FB	190	#endif
8db1a1dd	191	if (table[j][1] /bits/ != 0) {
9b879566	192	av_log(NULL, AV_LOG_ERROR, "incorrect codes\n");
9fe5a7b8	193	return -1;
de6d9b64	194	}
8db1a1dd MN	195	table[j][1] = n; //bits
8db1a1dd MN	196	table[j][0] = i; //code
de6d9b64 FB	197	j++;
	198	}
	199	} else {
	200	n -= table_nb_bits;
	201	j = (code >> n) & ((1 << table_nb_bits) - 1);
	202	#ifdef DEBUG_VLC
	203	printf("%4x: n=%d (subtable)\n",
	204	j, n);
	205	#endif
	206	/* compute table size */
8db1a1dd	207	n1 = -table[j][1]; //bits
de6d9b64 FB	208	if (n > n1)
de6d9b64 FB	209	n1 = n;
8db1a1dd	210	table[j][1] = -n1; //bits
de6d9b64 FB	211	}
	212	}
	213	}
	214
	215	/* second pass : fill auxillary tables recursively */
	216	for(i=0;i<table_size;i++) {
8db1a1dd	217	n = table[i][1]; //bits
de6d9b64 FB	218	if (n < 0) {
	219	n = -n;
	220	if (n > table_nb_bits) {
	221	n = table_nb_bits;
8db1a1dd	222	table[i][1] = -n; //bits
de6d9b64 FB	223	}
	224	index = build_table(vlc, n, nb_codes,
	225	bits, bits_wrap, bits_size,
	226	codes, codes_wrap, codes_size,
	227	(code_prefix << table_nb_bits) \| i,
	228	n_prefix + table_nb_bits);
	229	if (index < 0)
	230	return -1;
	231	/* note: realloc has been done, so reload tables */
8db1a1dd	232	table = &vlc->table[table_index];
6300c80a	233	table[i][0] = index; //code
de6d9b64 FB	234	}
	235	}
	236	return table_index;
	237	}
	238
	239
4e66ab3b FB	240	/* Build VLC decoding tables suitable for use with get_vlc().
	241
	242	'nb_bits' set thee decoding table size (2^nb_bits) entries. The
	243	bigger it is, the faster is the decoding. But it should not be too
	244	big to save memory and L1 cache. '9' is a good compromise.
	245
	246	'nb_codes' : number of vlcs codes
	247
	248	'bits' : table which gives the size (in bits) of each vlc code.
	249
	250	'codes' : table which gives the bit pattern of of each vlc code.
	251
	252	'xxx_wrap' : give the number of bytes between each entry of the
	253	'bits' or 'codes' tables.
	254
	255	'xxx_size' : gives the number of bytes of each entry of the 'bits'
	256	or 'codes' tables.
	257
	258	'wrap' and 'size' allows to use any memory configuration and types
	259	(byte/word/long) to store the 'bits' and 'codes' tables.
	260	*/
de6d9b64 FB	261	int init_vlc(VLC *vlc, int nb_bits, int nb_codes,
	262	const void *bits, int bits_wrap, int bits_size,
	263	const void *codes, int codes_wrap, int codes_size)
	264	{
	265	vlc->bits = nb_bits;
8db1a1dd	266	vlc->table = NULL;
de6d9b64 FB	267	vlc->table_allocated = 0;
	268	vlc->table_size = 0;
	269	#ifdef DEBUG_VLC
	270	printf("build table nb_codes=%d\n", nb_codes);
	271	#endif
	272
	273	if (build_table(vlc, nb_bits, nb_codes,
	274	bits, bits_wrap, bits_size,
	275	codes, codes_wrap, codes_size,
	276	0, 0) < 0) {
8db1a1dd	277	av_free(vlc->table);
de6d9b64 FB	278	return -1;
	279	}
	280	return 0;
	281	}
	282
	283
	284	void free_vlc(VLC *vlc)
	285	{
8db1a1dd	286	av_free(vlc->table);
de6d9b64 FB	287	}
de6d9b64 FB	288
14bea432	289	int64_t ff_gcd(int64_t a, int64_t b){
9dbcbd92 MN	290	if(b) return ff_gcd(b, a%b);
	291	else return a;
	292	}