path: root/libavcodec/vorbis.c (plain)
blob: 399020eec55178628754f4f25917622183edd03e

1	/**
2	* @file
3	* Common code for Vorbis I encoder and decoder
4	* @author Denes Balatoni ( dbalatoni programozo hu )
5	*
6	* This file is part of FFmpeg.
7	*
8	* FFmpeg is free software; you can redistribute it and/or
9	* modify it under the terms of the GNU Lesser General Public
10	* License as published by the Free Software Foundation; either
11	* version 2.1 of the License, or (at your option) any later version.
12	*
13	* FFmpeg is distributed in the hope that it will be useful,
14	* but WITHOUT ANY WARRANTY; without even the implied warranty of
15	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16	* Lesser General Public License for more details.
17	*
18	* You should have received a copy of the GNU Lesser General Public
19	* License along with FFmpeg; if not, write to the Free Software
20	* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
21	*/
22
23	/**
24	* @file
25	* Common code for Vorbis I encoder and decoder
26	* @author Denes Balatoni ( dbalatoni programozo hu )
27	*/
28
29	#include "libavutil/common.h"
30
31	#include "avcodec.h"
32	#include "vorbis.h"
33
34
35	/* Helper functions */
36
37	// x^(1/n)
38	unsigned int ff_vorbis_nth_root(unsigned int x, unsigned int n)
39	{
40	unsigned int ret = 0, i, j;
41
42	do {
43	++ret;
44	for (i = 0, j = ret; i < n - 1; i++)
45	j *= ret;
46	} while (j <= x);
47
48	return ret - 1;
49	}
50
51	// Generate vlc codes from vorbis huffman code lengths
52
53	// the two bits[p] > 32 checks should be redundant, all calling code should
54	// already ensure that, but since it allows overwriting the stack it seems
55	// reasonable to check redundantly.
56	int ff_vorbis_len2vlc(uint8_t *bits, uint32_t *codes, unsigned num)
57	{
58	uint32_t exit_at_level[33] = { 404 };
59	unsigned i, j, p, code;
60
61	for (p = 0; (bits[p] == 0) && (p < num); ++p)
62	;
63	if (p == num)
64	return 0;
65
66	codes[p] = 0;
67	if (bits[p] > 32)
68	return AVERROR_INVALIDDATA;
69	for (i = 0; i < bits[p]; ++i)
70	exit_at_level[i+1] = 1 << i;
71
72	++p;
73
74	for (i = p; (bits[i] == 0) && (i < num); ++i)
75	;
76	if (i == num)
77	return 0;
78
79	for (; p < num; ++p) {
80	if (bits[p] > 32)
81	return AVERROR_INVALIDDATA;
82	if (bits[p] == 0)
83	continue;
84	// find corresponding exit(node which the tree can grow further from)
85	for (i = bits[p]; i > 0; --i)
86	if (exit_at_level[i])
87	break;
88	if (!i) // overspecified tree
89	return AVERROR_INVALIDDATA;
90	code = exit_at_level[i];
91	exit_at_level[i] = 0;
92	// construct code (append 0s to end) and introduce new exits
93	for (j = i + 1 ;j <= bits[p]; ++j)
94	exit_at_level[j] = code + (1 << (j - 1));
95	codes[p] = code;
96	}
97
98	//no exits should be left (underspecified tree - ie. unused valid vlcs - not allowed by SPEC)
99	for (p = 1; p < 33; p++)
100	if (exit_at_level[p])
101	return AVERROR_INVALIDDATA;
102
103	return 0;
104	}
105
106	int ff_vorbis_ready_floor1_list(AVCodecContext *avctx,
107	vorbis_floor1_entry *list, int values)
108	{
109	int i;
110	list[0].sort = 0;
111	list[1].sort = 1;
112	for (i = 2; i < values; i++) {
113	int j;
114	list[i].low = 0;
115	list[i].high = 1;
116	list[i].sort = i;
117	for (j = 2; j < i; j++) {
118	int tmp = list[j].x;
119	if (tmp < list[i].x) {
120	if (tmp > list[list[i].low].x)
121	list[i].low = j;
122	} else {
123	if (tmp < list[list[i].high].x)
124	list[i].high = j;
125	}
126	}
127	}
128	for (i = 0; i < values - 1; i++) {
129	int j;
130	for (j = i + 1; j < values; j++) {
131	if (list[i].x == list[j].x) {
132	av_log(avctx, AV_LOG_ERROR,
133	"Duplicate value found in floor 1 X coordinates\n");
134	return AVERROR_INVALIDDATA;
135	}
136	if (list[list[i].sort].x > list[list[j].sort].x) {
137	int tmp = list[i].sort;
138	list[i].sort = list[j].sort;
139	list[j].sort = tmp;
140	}
141	}
142	}
143	return 0;
144	}
145
146	static inline void render_line_unrolled(intptr_t x, int y, int x1,
147	intptr_t sy, int ady, int adx,
148	float *buf)
149	{
150	int err = -adx;
151	x -= x1 - 1;
152	buf += x1 - 1;
153	while (++x < 0) {
154	err += ady;
155	if (err >= 0) {
156	err += ady - adx;
157	y += sy;
158	buf[x++] = ff_vorbis_floor1_inverse_db_table[av_clip_uint8(y)];
159	}
160	buf[x] = ff_vorbis_floor1_inverse_db_table[av_clip_uint8(y)];
161	}
162	if (x <= 0) {
163	if (err + ady >= 0)
164	y += sy;
165	buf[x] = ff_vorbis_floor1_inverse_db_table[av_clip_uint8(y)];
166	}
167	}
168
169	static void render_line(int x0, int y0, int x1, int y1, float *buf)
170	{
171	int dy = y1 - y0;
172	int adx = x1 - x0;
173	int ady = FFABS(dy);
174	int sy = dy < 0 ? -1 : 1;
175	buf[x0] = ff_vorbis_floor1_inverse_db_table[av_clip_uint8(y0)];
176	if (ady*2 <= adx) { // optimized common case
177	render_line_unrolled(x0, y0, x1, sy, ady, adx, buf);
178	} else {
179	int base = dy / adx;
180	int x = x0;
181	int y = y0;
182	int err = -adx;
183	ady -= FFABS(base) * adx;
184	while (++x < x1) {
185	y += base;
186	err += ady;
187	if (err >= 0) {
188	err -= adx;
189	y += sy;
190	}
191	buf[x] = ff_vorbis_floor1_inverse_db_table[av_clip_uint8(y)];
192	}
193	}
194	}
195
196	void ff_vorbis_floor1_render_list(vorbis_floor1_entry * list, int values,
197	uint16_t *y_list, int *flag,
198	int multiplier, float *out, int samples)
199	{
200	int lx, ly, i;
201	lx = 0;
202	ly = y_list[0] * multiplier;
203	for (i = 1; i < values; i++) {
204	int pos = list[i].sort;
205	if (flag[pos]) {
206	int x1 = list[pos].x;
207	int y1 = y_list[pos] * multiplier;
208	if (lx < samples)
209	render_line(lx, ly, FFMIN(x1,samples), y1, out);
210	lx = x1;
211	ly = y1;
212	}
213	if (lx >= samples)
214	break;
215	}
216	if (lx < samples)
217	render_line(lx, ly, samples, ly, out);
218	}
219