1 /* Copyright (c) 2007-2008 CSIRO
2 Copyright (c) 2007-2008 Xiph.Org Foundation
3 Written by Jean-Marc Valin */
4 /*
5 Redistribution and use in source and binary forms, with or without
6 modification, are permitted provided that the following conditions
7 are met:
8
9 - Redistributions of source code must retain the above copyright
10 notice, this list of conditions and the following disclaimer.
11
12 - Redistributions in binary form must reproduce the above copyright
13 notice, this list of conditions and the following disclaimer in the
14 documentation and/or other materials provided with the distribution.
15
16 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
20 OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
21 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
22 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
23 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
24 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
25 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
26 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29 /* This is a simple MDCT implementation that uses a N/4 complex FFT
30 to do most of the work. It should be relatively straightforward to
31 plug in pretty much and FFT here.
32
33 This replaces the Vorbis FFT (and uses the exact same API), which
34 was a bit too messy and that was ending up duplicating code
35 (might as well use the same FFT everywhere).
36
37 The algorithm is similar to (and inspired from) Fabrice Bellard's
38 MDCT implementation in FFMPEG, but has differences in signs, ordering
39 and scaling in many places.
40 */
41
42 #ifndef SKIP_CONFIG_H
43 #ifdef HAVE_CONFIG_H
44 #include "config.h"
45 #endif
46 #endif
47
48 #include "mdct.h"
49 #include "kiss_fft.h"
50 #include "_kiss_fft_guts.h"
51 #include <math.h>
52 #include "os_support.h"
53 #include "mathops.h"
54 #include "stack_alloc.h"
55
56 #if defined(MIPSr1_ASM)
57 #include "mips/mdct_mipsr1.h"
58 #endif
59
60
61 #ifdef CUSTOM_MODES
62
clt_mdct_init(mdct_lookup * l,int N,int maxshift,int arch)63 int clt_mdct_init(mdct_lookup *l,int N, int maxshift, int arch)
64 {
65 int i;
66 kiss_twiddle_scalar *trig;
67 int shift;
68 int N2=N>>1;
69 l->n = N;
70 l->maxshift = maxshift;
71 for (i=0;i<=maxshift;i++)
72 {
73 if (i==0)
74 l->kfft[i] = opus_fft_alloc(N>>2>>i, 0, 0, arch);
75 else
76 l->kfft[i] = opus_fft_alloc_twiddles(N>>2>>i, 0, 0, l->kfft[0], arch);
77 #ifndef ENABLE_TI_DSPLIB55
78 if (l->kfft[i]==NULL)
79 return 0;
80 #endif
81 }
82 l->trig = trig = (kiss_twiddle_scalar*)opus_alloc((N-(N2>>maxshift))*sizeof(kiss_twiddle_scalar));
83 if (l->trig==NULL)
84 return 0;
85 for (shift=0;shift<=maxshift;shift++)
86 {
87 /* We have enough points that sine isn't necessary */
88 #if defined(FIXED_POINT)
89 #if 1
90 for (i=0;i<N2;i++)
91 trig[i] = TRIG_UPSCALE*celt_cos_norm(DIV32(ADD32(SHL32(EXTEND32(i),17),N2+16384),N));
92 #else
93 for (i=0;i<N2;i++)
94 trig[i] = (kiss_twiddle_scalar)MAX32(-32767,MIN32(32767,floor(.5+32768*cos(2*M_PI*(i+.125)/N))));
95 #endif
96 #else
97 for (i=0;i<N2;i++)
98 trig[i] = (kiss_twiddle_scalar)cos(2*PI*(i+.125)/N);
99 #endif
100 trig += N2;
101 N2 >>= 1;
102 N >>= 1;
103 }
104 return 1;
105 }
106
clt_mdct_clear(mdct_lookup * l,int arch)107 void clt_mdct_clear(mdct_lookup *l, int arch)
108 {
109 int i;
110 for (i=0;i<=l->maxshift;i++)
111 opus_fft_free(l->kfft[i], arch);
112 opus_free((kiss_twiddle_scalar*)l->trig);
113 }
114
115 #endif /* CUSTOM_MODES */
116
117 /* Forward MDCT trashes the input array */
118 #ifndef OVERRIDE_clt_mdct_forward
clt_mdct_forward_c(const mdct_lookup * l,kiss_fft_scalar * in,kiss_fft_scalar * OPUS_RESTRICT out,const opus_val16 * window,int overlap,int shift,int stride,int arch)119 void clt_mdct_forward_c(const mdct_lookup *l, kiss_fft_scalar *in, kiss_fft_scalar * OPUS_RESTRICT out,
120 const opus_val16 *window, int overlap, int shift, int stride, int arch)
121 {
122 int i;
123 int N, N2, N4;
124 VARDECL(kiss_fft_scalar, f);
125 VARDECL(kiss_fft_cpx, f2);
126 const kiss_fft_state *st = l->kfft[shift];
127 const kiss_twiddle_scalar *trig;
128 opus_val16 scale;
129 #ifdef FIXED_POINT
130 /* Allows us to scale with MULT16_32_Q16(), which is faster than
131 MULT16_32_Q15() on ARM. */
132 int scale_shift = st->scale_shift-1;
133 #endif
134 SAVE_STACK;
135 (void)arch;
136 scale = st->scale;
137
138 N = l->n;
139 trig = l->trig;
140 for (i=0;i<shift;i++)
141 {
142 N >>= 1;
143 trig += N;
144 }
145 N2 = N>>1;
146 N4 = N>>2;
147
148 ALLOC(f, N2, kiss_fft_scalar);
149 ALLOC(f2, N4, kiss_fft_cpx);
150
151 /* Consider the input to be composed of four blocks: [a, b, c, d] */
152 /* Window, shuffle, fold */
153 {
154 /* Temp pointers to make it really clear to the compiler what we're doing */
155 const kiss_fft_scalar * OPUS_RESTRICT xp1 = in+(overlap>>1);
156 const kiss_fft_scalar * OPUS_RESTRICT xp2 = in+N2-1+(overlap>>1);
157 kiss_fft_scalar * OPUS_RESTRICT yp = f;
158 const opus_val16 * OPUS_RESTRICT wp1 = window+(overlap>>1);
159 const opus_val16 * OPUS_RESTRICT wp2 = window+(overlap>>1)-1;
160 for(i=0;i<((overlap+3)>>2);i++)
161 {
162 /* Real part arranged as -d-cR, Imag part arranged as -b+aR*/
163 *yp++ = MULT16_32_Q15(*wp2, xp1[N2]) + MULT16_32_Q15(*wp1,*xp2);
164 *yp++ = MULT16_32_Q15(*wp1, *xp1) - MULT16_32_Q15(*wp2, xp2[-N2]);
165 xp1+=2;
166 xp2-=2;
167 wp1+=2;
168 wp2-=2;
169 }
170 wp1 = window;
171 wp2 = window+overlap-1;
172 for(;i<N4-((overlap+3)>>2);i++)
173 {
174 /* Real part arranged as a-bR, Imag part arranged as -c-dR */
175 *yp++ = *xp2;
176 *yp++ = *xp1;
177 xp1+=2;
178 xp2-=2;
179 }
180 for(;i<N4;i++)
181 {
182 /* Real part arranged as a-bR, Imag part arranged as -c-dR */
183 *yp++ = -MULT16_32_Q15(*wp1, xp1[-N2]) + MULT16_32_Q15(*wp2, *xp2);
184 *yp++ = MULT16_32_Q15(*wp2, *xp1) + MULT16_32_Q15(*wp1, xp2[N2]);
185 xp1+=2;
186 xp2-=2;
187 wp1+=2;
188 wp2-=2;
189 }
190 }
191 /* Pre-rotation */
192 {
193 kiss_fft_scalar * OPUS_RESTRICT yp = f;
194 const kiss_twiddle_scalar *t = &trig[0];
195 for(i=0;i<N4;i++)
196 {
197 kiss_fft_cpx yc;
198 kiss_twiddle_scalar t0, t1;
199 kiss_fft_scalar re, im, yr, yi;
200 t0 = t[i];
201 t1 = t[N4+i];
202 re = *yp++;
203 im = *yp++;
204 yr = S_MUL(re,t0) - S_MUL(im,t1);
205 yi = S_MUL(im,t0) + S_MUL(re,t1);
206 yc.r = yr;
207 yc.i = yi;
208 yc.r = PSHR32(MULT16_32_Q16(scale, yc.r), scale_shift);
209 yc.i = PSHR32(MULT16_32_Q16(scale, yc.i), scale_shift);
210 f2[st->bitrev[i]] = yc;
211 }
212 }
213
214 /* N/4 complex FFT, does not downscale anymore */
215 opus_fft_impl(st, f2);
216
217 /* Post-rotate */
218 {
219 /* Temp pointers to make it really clear to the compiler what we're doing */
220 const kiss_fft_cpx * OPUS_RESTRICT fp = f2;
221 kiss_fft_scalar * OPUS_RESTRICT yp1 = out;
222 kiss_fft_scalar * OPUS_RESTRICT yp2 = out+stride*(N2-1);
223 const kiss_twiddle_scalar *t = &trig[0];
224 /* Temp pointers to make it really clear to the compiler what we're doing */
225 for(i=0;i<N4;i++)
226 {
227 kiss_fft_scalar yr, yi;
228 yr = S_MUL(fp->i,t[N4+i]) - S_MUL(fp->r,t[i]);
229 yi = S_MUL(fp->r,t[N4+i]) + S_MUL(fp->i,t[i]);
230 *yp1 = yr;
231 *yp2 = yi;
232 fp++;
233 yp1 += 2*stride;
234 yp2 -= 2*stride;
235 }
236 }
237 RESTORE_STACK;
238 }
239 #endif /* OVERRIDE_clt_mdct_forward */
240
241 #ifndef OVERRIDE_clt_mdct_backward
clt_mdct_backward_c(const mdct_lookup * l,kiss_fft_scalar * in,kiss_fft_scalar * OPUS_RESTRICT out,const opus_val16 * OPUS_RESTRICT window,int overlap,int shift,int stride,int arch)242 void clt_mdct_backward_c(const mdct_lookup *l, kiss_fft_scalar *in, kiss_fft_scalar * OPUS_RESTRICT out,
243 const opus_val16 * OPUS_RESTRICT window, int overlap, int shift, int stride, int arch)
244 {
245 int i;
246 int N, N2, N4;
247 const kiss_twiddle_scalar *trig;
248 (void) arch;
249
250 N = l->n;
251 trig = l->trig;
252 for (i=0;i<shift;i++)
253 {
254 N >>= 1;
255 trig += N;
256 }
257 N2 = N>>1;
258 N4 = N>>2;
259
260 /* Pre-rotate */
261 {
262 /* Temp pointers to make it really clear to the compiler what we're doing */
263 const kiss_fft_scalar * OPUS_RESTRICT xp1 = in;
264 const kiss_fft_scalar * OPUS_RESTRICT xp2 = in+stride*(N2-1);
265 kiss_fft_scalar * OPUS_RESTRICT yp = out+(overlap>>1);
266 const kiss_twiddle_scalar * OPUS_RESTRICT t = &trig[0];
267 const opus_int16 * OPUS_RESTRICT bitrev = l->kfft[shift]->bitrev;
268 for(i=0;i<N4;i++)
269 {
270 int rev;
271 kiss_fft_scalar yr, yi;
272 rev = *bitrev++;
273 yr = S_MUL(*xp2, t[i]) + S_MUL(*xp1, t[N4+i]);
274 yi = S_MUL(*xp1, t[i]) - S_MUL(*xp2, t[N4+i]);
275 /* We swap real and imag because we use an FFT instead of an IFFT. */
276 yp[2*rev+1] = yr;
277 yp[2*rev] = yi;
278 /* Storing the pre-rotation directly in the bitrev order. */
279 xp1+=2*stride;
280 xp2-=2*stride;
281 }
282 }
283
284 opus_fft_impl(l->kfft[shift], (kiss_fft_cpx*)(out+(overlap>>1)));
285
286 /* Post-rotate and de-shuffle from both ends of the buffer at once to make
287 it in-place. */
288 {
289 kiss_fft_scalar * yp0 = out+(overlap>>1);
290 kiss_fft_scalar * yp1 = out+(overlap>>1)+N2-2;
291 const kiss_twiddle_scalar *t = &trig[0];
292 /* Loop to (N4+1)>>1 to handle odd N4. When N4 is odd, the
293 middle pair will be computed twice. */
294 for(i=0;i<(N4+1)>>1;i++)
295 {
296 kiss_fft_scalar re, im, yr, yi;
297 kiss_twiddle_scalar t0, t1;
298 /* We swap real and imag because we're using an FFT instead of an IFFT. */
299 re = yp0[1];
300 im = yp0[0];
301 t0 = t[i];
302 t1 = t[N4+i];
303 /* We'd scale up by 2 here, but instead it's done when mixing the windows */
304 yr = S_MUL(re,t0) + S_MUL(im,t1);
305 yi = S_MUL(re,t1) - S_MUL(im,t0);
306 /* We swap real and imag because we're using an FFT instead of an IFFT. */
307 re = yp1[1];
308 im = yp1[0];
309 yp0[0] = yr;
310 yp1[1] = yi;
311
312 t0 = t[(N4-i-1)];
313 t1 = t[(N2-i-1)];
314 /* We'd scale up by 2 here, but instead it's done when mixing the windows */
315 yr = S_MUL(re,t0) + S_MUL(im,t1);
316 yi = S_MUL(re,t1) - S_MUL(im,t0);
317 yp1[0] = yr;
318 yp0[1] = yi;
319 yp0 += 2;
320 yp1 -= 2;
321 }
322 }
323
324 /* Mirror on both sides for TDAC */
325 {
326 kiss_fft_scalar * OPUS_RESTRICT xp1 = out+overlap-1;
327 kiss_fft_scalar * OPUS_RESTRICT yp1 = out;
328 const opus_val16 * OPUS_RESTRICT wp1 = window;
329 const opus_val16 * OPUS_RESTRICT wp2 = window+overlap-1;
330
331 for(i = 0; i < overlap/2; i++)
332 {
333 kiss_fft_scalar x1, x2;
334 x1 = *xp1;
335 x2 = *yp1;
336 *yp1++ = MULT16_32_Q15(*wp2, x2) - MULT16_32_Q15(*wp1, x1);
337 *xp1-- = MULT16_32_Q15(*wp1, x2) + MULT16_32_Q15(*wp2, x1);
338 wp1++;
339 wp2--;
340 }
341 }
342 }
343 #endif /* OVERRIDE_clt_mdct_backward */
344