1 /*Copyright (c) 2003-2004, Mark Borgerding
2 Lots of modifications by Jean-Marc Valin
3 Copyright (c) 2005-2007, Xiph.Org Foundation
4 Copyright (c) 2008, Xiph.Org Foundation, CSIRO
5
6 All rights reserved.
7
8 Redistribution and use in source and binary forms, with or without
9 modification, are permitted provided that the following conditions are met:
10
11 * Redistributions of source code must retain the above copyright notice,
12 this list of conditions and the following disclaimer.
13 * Redistributions in binary form must reproduce the above copyright notice,
14 this list of conditions and the following disclaimer in the
15 documentation and/or other materials provided with the distribution.
16
17 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
21 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27 POSSIBILITY OF SUCH DAMAGE.*/
28
29 /* This code is originally from Mark Borgerding's KISS-FFT but has been
30 heavily modified to better suit Opus */
31
32 #ifndef SKIP_CONFIG_H
33 # ifdef HAVE_CONFIG_H
34 # include "config.h"
35 # endif
36 #endif
37
38 #include "_kiss_fft_guts.h"
39 #include "arch.h"
40 #include "os_support.h"
41 #include "mathops.h"
42 #include "stack_alloc.h"
43
44 /* The guts header contains all the multiplication and addition macros that are defined for
45 complex numbers. It also delares the kf_ internal functions.
46 */
47
kf_bfly2(kiss_fft_cpx * Fout,const size_t fstride,const kiss_fft_state * st,int m,int N,int mm)48 static void kf_bfly2(
49 kiss_fft_cpx * Fout,
50 const size_t fstride,
51 const kiss_fft_state *st,
52 int m,
53 int N,
54 int mm
55 )
56 {
57 kiss_fft_cpx * Fout2;
58 const kiss_twiddle_cpx * tw1;
59 int i,j;
60 kiss_fft_cpx * Fout_beg = Fout;
61 for (i=0;i<N;i++)
62 {
63 Fout = Fout_beg + i*mm;
64 Fout2 = Fout + m;
65 tw1 = st->twiddles;
66 for(j=0;j<m;j++)
67 {
68 kiss_fft_cpx t;
69 Fout->r = SHR32(Fout->r, 1);Fout->i = SHR32(Fout->i, 1);
70 Fout2->r = SHR32(Fout2->r, 1);Fout2->i = SHR32(Fout2->i, 1);
71 C_MUL (t, *Fout2 , *tw1);
72 tw1 += fstride;
73 C_SUB( *Fout2 , *Fout , t );
74 C_ADDTO( *Fout , t );
75 ++Fout2;
76 ++Fout;
77 }
78 }
79 }
80
ki_bfly2(kiss_fft_cpx * Fout,const size_t fstride,const kiss_fft_state * st,int m,int N,int mm)81 static void ki_bfly2(
82 kiss_fft_cpx * Fout,
83 const size_t fstride,
84 const kiss_fft_state *st,
85 int m,
86 int N,
87 int mm
88 )
89 {
90 kiss_fft_cpx * Fout2;
91 const kiss_twiddle_cpx * tw1;
92 kiss_fft_cpx t;
93 int i,j;
94 kiss_fft_cpx * Fout_beg = Fout;
95 for (i=0;i<N;i++)
96 {
97 Fout = Fout_beg + i*mm;
98 Fout2 = Fout + m;
99 tw1 = st->twiddles;
100 for(j=0;j<m;j++)
101 {
102 C_MULC (t, *Fout2 , *tw1);
103 tw1 += fstride;
104 C_SUB( *Fout2 , *Fout , t );
105 C_ADDTO( *Fout , t );
106 ++Fout2;
107 ++Fout;
108 }
109 }
110 }
111
kf_bfly4(kiss_fft_cpx * Fout,const size_t fstride,const kiss_fft_state * st,int m,int N,int mm)112 static void kf_bfly4(
113 kiss_fft_cpx * Fout,
114 const size_t fstride,
115 const kiss_fft_state *st,
116 int m,
117 int N,
118 int mm
119 )
120 {
121 const kiss_twiddle_cpx *tw1,*tw2,*tw3;
122 kiss_fft_cpx scratch[6];
123 const size_t m2=2*m;
124 const size_t m3=3*m;
125 int i, j;
126
127 kiss_fft_cpx * Fout_beg = Fout;
128 for (i=0;i<N;i++)
129 {
130 Fout = Fout_beg + i*mm;
131 tw3 = tw2 = tw1 = st->twiddles;
132 for (j=0;j<m;j++)
133 {
134 C_MUL4(scratch[0],Fout[m] , *tw1 );
135 C_MUL4(scratch[1],Fout[m2] , *tw2 );
136 C_MUL4(scratch[2],Fout[m3] , *tw3 );
137
138 Fout->r = PSHR32(Fout->r, 2);
139 Fout->i = PSHR32(Fout->i, 2);
140 C_SUB( scratch[5] , *Fout, scratch[1] );
141 C_ADDTO(*Fout, scratch[1]);
142 C_ADD( scratch[3] , scratch[0] , scratch[2] );
143 C_SUB( scratch[4] , scratch[0] , scratch[2] );
144 C_SUB( Fout[m2], *Fout, scratch[3] );
145 tw1 += fstride;
146 tw2 += fstride*2;
147 tw3 += fstride*3;
148 C_ADDTO( *Fout , scratch[3] );
149
150 Fout[m].r = scratch[5].r + scratch[4].i;
151 Fout[m].i = scratch[5].i - scratch[4].r;
152 Fout[m3].r = scratch[5].r - scratch[4].i;
153 Fout[m3].i = scratch[5].i + scratch[4].r;
154 ++Fout;
155 }
156 }
157 }
158
ki_bfly4(kiss_fft_cpx * Fout,const size_t fstride,const kiss_fft_state * st,int m,int N,int mm)159 static void ki_bfly4(
160 kiss_fft_cpx * Fout,
161 const size_t fstride,
162 const kiss_fft_state *st,
163 int m,
164 int N,
165 int mm
166 )
167 {
168 const kiss_twiddle_cpx *tw1,*tw2,*tw3;
169 kiss_fft_cpx scratch[6];
170 const size_t m2=2*m;
171 const size_t m3=3*m;
172 int i, j;
173
174 kiss_fft_cpx * Fout_beg = Fout;
175 for (i=0;i<N;i++)
176 {
177 Fout = Fout_beg + i*mm;
178 tw3 = tw2 = tw1 = st->twiddles;
179 for (j=0;j<m;j++)
180 {
181 C_MULC(scratch[0],Fout[m] , *tw1 );
182 C_MULC(scratch[1],Fout[m2] , *tw2 );
183 C_MULC(scratch[2],Fout[m3] , *tw3 );
184
185 C_SUB( scratch[5] , *Fout, scratch[1] );
186 C_ADDTO(*Fout, scratch[1]);
187 C_ADD( scratch[3] , scratch[0] , scratch[2] );
188 C_SUB( scratch[4] , scratch[0] , scratch[2] );
189 C_SUB( Fout[m2], *Fout, scratch[3] );
190 tw1 += fstride;
191 tw2 += fstride*2;
192 tw3 += fstride*3;
193 C_ADDTO( *Fout , scratch[3] );
194
195 Fout[m].r = scratch[5].r - scratch[4].i;
196 Fout[m].i = scratch[5].i + scratch[4].r;
197 Fout[m3].r = scratch[5].r + scratch[4].i;
198 Fout[m3].i = scratch[5].i - scratch[4].r;
199 ++Fout;
200 }
201 }
202 }
203
204 #ifndef RADIX_TWO_ONLY
205
kf_bfly3(kiss_fft_cpx * Fout,const size_t fstride,const kiss_fft_state * st,int m,int N,int mm)206 static void kf_bfly3(
207 kiss_fft_cpx * Fout,
208 const size_t fstride,
209 const kiss_fft_state *st,
210 int m,
211 int N,
212 int mm
213 )
214 {
215 int i;
216 size_t k;
217 const size_t m2 = 2*m;
218 const kiss_twiddle_cpx *tw1,*tw2;
219 kiss_fft_cpx scratch[5];
220 kiss_twiddle_cpx epi3;
221
222 kiss_fft_cpx * Fout_beg = Fout;
223 epi3 = st->twiddles[fstride*m];
224 for (i=0;i<N;i++)
225 {
226 Fout = Fout_beg + i*mm;
227 tw1=tw2=st->twiddles;
228 k=m;
229 do {
230 C_FIXDIV(*Fout,3); C_FIXDIV(Fout[m],3); C_FIXDIV(Fout[m2],3);
231
232 C_MUL(scratch[1],Fout[m] , *tw1);
233 C_MUL(scratch[2],Fout[m2] , *tw2);
234
235 C_ADD(scratch[3],scratch[1],scratch[2]);
236 C_SUB(scratch[0],scratch[1],scratch[2]);
237 tw1 += fstride;
238 tw2 += fstride*2;
239
240 Fout[m].r = Fout->r - HALF_OF(scratch[3].r);
241 Fout[m].i = Fout->i - HALF_OF(scratch[3].i);
242
243 C_MULBYSCALAR( scratch[0] , epi3.i );
244
245 C_ADDTO(*Fout,scratch[3]);
246
247 Fout[m2].r = Fout[m].r + scratch[0].i;
248 Fout[m2].i = Fout[m].i - scratch[0].r;
249
250 Fout[m].r -= scratch[0].i;
251 Fout[m].i += scratch[0].r;
252
253 ++Fout;
254 } while(--k);
255 }
256 }
257
ki_bfly3(kiss_fft_cpx * Fout,const size_t fstride,const kiss_fft_state * st,int m,int N,int mm)258 static void ki_bfly3(
259 kiss_fft_cpx * Fout,
260 const size_t fstride,
261 const kiss_fft_state *st,
262 int m,
263 int N,
264 int mm
265 )
266 {
267 int i, k;
268 const size_t m2 = 2*m;
269 const kiss_twiddle_cpx *tw1,*tw2;
270 kiss_fft_cpx scratch[5];
271 kiss_twiddle_cpx epi3;
272
273 kiss_fft_cpx * Fout_beg = Fout;
274 epi3 = st->twiddles[fstride*m];
275 for (i=0;i<N;i++)
276 {
277 Fout = Fout_beg + i*mm;
278 tw1=tw2=st->twiddles;
279 k=m;
280 do{
281
282 C_MULC(scratch[1],Fout[m] , *tw1);
283 C_MULC(scratch[2],Fout[m2] , *tw2);
284
285 C_ADD(scratch[3],scratch[1],scratch[2]);
286 C_SUB(scratch[0],scratch[1],scratch[2]);
287 tw1 += fstride;
288 tw2 += fstride*2;
289
290 Fout[m].r = Fout->r - HALF_OF(scratch[3].r);
291 Fout[m].i = Fout->i - HALF_OF(scratch[3].i);
292
293 C_MULBYSCALAR( scratch[0] , -epi3.i );
294
295 C_ADDTO(*Fout,scratch[3]);
296
297 Fout[m2].r = Fout[m].r + scratch[0].i;
298 Fout[m2].i = Fout[m].i - scratch[0].r;
299
300 Fout[m].r -= scratch[0].i;
301 Fout[m].i += scratch[0].r;
302
303 ++Fout;
304 }while(--k);
305 }
306 }
307
kf_bfly5(kiss_fft_cpx * Fout,const size_t fstride,const kiss_fft_state * st,int m,int N,int mm)308 static void kf_bfly5(
309 kiss_fft_cpx * Fout,
310 const size_t fstride,
311 const kiss_fft_state *st,
312 int m,
313 int N,
314 int mm
315 )
316 {
317 kiss_fft_cpx *Fout0,*Fout1,*Fout2,*Fout3,*Fout4;
318 int i, u;
319 kiss_fft_cpx scratch[13];
320 const kiss_twiddle_cpx * twiddles = st->twiddles;
321 const kiss_twiddle_cpx *tw;
322 kiss_twiddle_cpx ya,yb;
323 kiss_fft_cpx * Fout_beg = Fout;
324
325 ya = twiddles[fstride*m];
326 yb = twiddles[fstride*2*m];
327 tw=st->twiddles;
328
329 for (i=0;i<N;i++)
330 {
331 Fout = Fout_beg + i*mm;
332 Fout0=Fout;
333 Fout1=Fout0+m;
334 Fout2=Fout0+2*m;
335 Fout3=Fout0+3*m;
336 Fout4=Fout0+4*m;
337
338 for ( u=0; u<m; ++u ) {
339 C_FIXDIV( *Fout0,5); C_FIXDIV( *Fout1,5); C_FIXDIV( *Fout2,5); C_FIXDIV( *Fout3,5); C_FIXDIV( *Fout4,5);
340 scratch[0] = *Fout0;
341
342 C_MUL(scratch[1] ,*Fout1, tw[u*fstride]);
343 C_MUL(scratch[2] ,*Fout2, tw[2*u*fstride]);
344 C_MUL(scratch[3] ,*Fout3, tw[3*u*fstride]);
345 C_MUL(scratch[4] ,*Fout4, tw[4*u*fstride]);
346
347 C_ADD( scratch[7],scratch[1],scratch[4]);
348 C_SUB( scratch[10],scratch[1],scratch[4]);
349 C_ADD( scratch[8],scratch[2],scratch[3]);
350 C_SUB( scratch[9],scratch[2],scratch[3]);
351
352 Fout0->r += scratch[7].r + scratch[8].r;
353 Fout0->i += scratch[7].i + scratch[8].i;
354
355 scratch[5].r = scratch[0].r + S_MUL(scratch[7].r,ya.r) + S_MUL(scratch[8].r,yb.r);
356 scratch[5].i = scratch[0].i + S_MUL(scratch[7].i,ya.r) + S_MUL(scratch[8].i,yb.r);
357
358 scratch[6].r = S_MUL(scratch[10].i,ya.i) + S_MUL(scratch[9].i,yb.i);
359 scratch[6].i = -S_MUL(scratch[10].r,ya.i) - S_MUL(scratch[9].r,yb.i);
360
361 C_SUB(*Fout1,scratch[5],scratch[6]);
362 C_ADD(*Fout4,scratch[5],scratch[6]);
363
364 scratch[11].r = scratch[0].r + S_MUL(scratch[7].r,yb.r) + S_MUL(scratch[8].r,ya.r);
365 scratch[11].i = scratch[0].i + S_MUL(scratch[7].i,yb.r) + S_MUL(scratch[8].i,ya.r);
366 scratch[12].r = - S_MUL(scratch[10].i,yb.i) + S_MUL(scratch[9].i,ya.i);
367 scratch[12].i = S_MUL(scratch[10].r,yb.i) - S_MUL(scratch[9].r,ya.i);
368
369 C_ADD(*Fout2,scratch[11],scratch[12]);
370 C_SUB(*Fout3,scratch[11],scratch[12]);
371
372 ++Fout0;++Fout1;++Fout2;++Fout3;++Fout4;
373 }
374 }
375 }
376
ki_bfly5(kiss_fft_cpx * Fout,const size_t fstride,const kiss_fft_state * st,int m,int N,int mm)377 static void ki_bfly5(
378 kiss_fft_cpx * Fout,
379 const size_t fstride,
380 const kiss_fft_state *st,
381 int m,
382 int N,
383 int mm
384 )
385 {
386 kiss_fft_cpx *Fout0,*Fout1,*Fout2,*Fout3,*Fout4;
387 int i, u;
388 kiss_fft_cpx scratch[13];
389 const kiss_twiddle_cpx * twiddles = st->twiddles;
390 const kiss_twiddle_cpx *tw;
391 kiss_twiddle_cpx ya,yb;
392 kiss_fft_cpx * Fout_beg = Fout;
393
394 ya = twiddles[fstride*m];
395 yb = twiddles[fstride*2*m];
396 tw=st->twiddles;
397
398 for (i=0;i<N;i++)
399 {
400 Fout = Fout_beg + i*mm;
401 Fout0=Fout;
402 Fout1=Fout0+m;
403 Fout2=Fout0+2*m;
404 Fout3=Fout0+3*m;
405 Fout4=Fout0+4*m;
406
407 for ( u=0; u<m; ++u ) {
408 scratch[0] = *Fout0;
409
410 C_MULC(scratch[1] ,*Fout1, tw[u*fstride]);
411 C_MULC(scratch[2] ,*Fout2, tw[2*u*fstride]);
412 C_MULC(scratch[3] ,*Fout3, tw[3*u*fstride]);
413 C_MULC(scratch[4] ,*Fout4, tw[4*u*fstride]);
414
415 C_ADD( scratch[7],scratch[1],scratch[4]);
416 C_SUB( scratch[10],scratch[1],scratch[4]);
417 C_ADD( scratch[8],scratch[2],scratch[3]);
418 C_SUB( scratch[9],scratch[2],scratch[3]);
419
420 Fout0->r += scratch[7].r + scratch[8].r;
421 Fout0->i += scratch[7].i + scratch[8].i;
422
423 scratch[5].r = scratch[0].r + S_MUL(scratch[7].r,ya.r) + S_MUL(scratch[8].r,yb.r);
424 scratch[5].i = scratch[0].i + S_MUL(scratch[7].i,ya.r) + S_MUL(scratch[8].i,yb.r);
425
426 scratch[6].r = -S_MUL(scratch[10].i,ya.i) - S_MUL(scratch[9].i,yb.i);
427 scratch[6].i = S_MUL(scratch[10].r,ya.i) + S_MUL(scratch[9].r,yb.i);
428
429 C_SUB(*Fout1,scratch[5],scratch[6]);
430 C_ADD(*Fout4,scratch[5],scratch[6]);
431
432 scratch[11].r = scratch[0].r + S_MUL(scratch[7].r,yb.r) + S_MUL(scratch[8].r,ya.r);
433 scratch[11].i = scratch[0].i + S_MUL(scratch[7].i,yb.r) + S_MUL(scratch[8].i,ya.r);
434 scratch[12].r = S_MUL(scratch[10].i,yb.i) - S_MUL(scratch[9].i,ya.i);
435 scratch[12].i = -S_MUL(scratch[10].r,yb.i) + S_MUL(scratch[9].r,ya.i);
436
437 C_ADD(*Fout2,scratch[11],scratch[12]);
438 C_SUB(*Fout3,scratch[11],scratch[12]);
439
440 ++Fout0;++Fout1;++Fout2;++Fout3;++Fout4;
441 }
442 }
443 }
444
445 #endif
446
447
448 #ifdef CUSTOM_MODES
449
450 static
compute_bitrev_table(int Fout,opus_int16 * f,const size_t fstride,int in_stride,opus_int16 * factors,const kiss_fft_state * st)451 void compute_bitrev_table(
452 int Fout,
453 opus_int16 *f,
454 const size_t fstride,
455 int in_stride,
456 opus_int16 * factors,
457 const kiss_fft_state *st
458 )
459 {
460 const int p=*factors++; /* the radix */
461 const int m=*factors++; /* stage's fft length/p */
462
463 /*printf ("fft %d %d %d %d %d %d\n", p*m, m, p, s2, fstride*in_stride, N);*/
464 if (m==1)
465 {
466 int j;
467 for (j=0;j<p;j++)
468 {
469 *f = Fout+j;
470 f += fstride*in_stride;
471 }
472 } else {
473 int j;
474 for (j=0;j<p;j++)
475 {
476 compute_bitrev_table( Fout , f, fstride*p, in_stride, factors,st);
477 f += fstride*in_stride;
478 Fout += m;
479 }
480 }
481 }
482
483 /* facbuf is populated by p1,m1,p2,m2, ...
484 where
485 p[i] * m[i] = m[i-1]
486 m0 = n */
487 static
kf_factor(int n,opus_int16 * facbuf)488 int kf_factor(int n,opus_int16 * facbuf)
489 {
490 int p=4;
491
492 /*factor out powers of 4, powers of 2, then any remaining primes */
493 do {
494 while (n % p) {
495 switch (p) {
496 case 4: p = 2; break;
497 case 2: p = 3; break;
498 default: p += 2; break;
499 }
500 if (p>32000 || (opus_int32)p*(opus_int32)p > n)
501 p = n; /* no more factors, skip to end */
502 }
503 n /= p;
504 #ifdef RADIX_TWO_ONLY
505 if (p!=2 && p != 4)
506 #else
507 if (p>5)
508 #endif
509 {
510 return 0;
511 }
512 *facbuf++ = p;
513 *facbuf++ = n;
514 } while (n > 1);
515 return 1;
516 }
517
compute_twiddles(kiss_twiddle_cpx * twiddles,int nfft)518 static void compute_twiddles(kiss_twiddle_cpx *twiddles, int nfft)
519 {
520 int i;
521 #ifdef FIXED_POINT
522 for (i=0;i<nfft;++i) {
523 opus_val32 phase = -i;
524 kf_cexp2(twiddles+i, DIV32(SHL32(phase,17),nfft));
525 }
526 #else
527 for (i=0;i<nfft;++i) {
528 const double pi=3.14159265358979323846264338327;
529 double phase = ( -2*pi /nfft ) * i;
530 kf_cexp(twiddles+i, phase );
531 }
532 #endif
533 }
534
535 /*
536 *
537 * Allocates all necessary storage space for the fft and ifft.
538 * The return value is a contiguous block of memory. As such,
539 * It can be freed with free().
540 * */
opus_fft_alloc_twiddles(int nfft,void * mem,size_t * lenmem,const kiss_fft_state * base)541 kiss_fft_state *opus_fft_alloc_twiddles(int nfft,void * mem,size_t * lenmem, const kiss_fft_state *base)
542 {
543 kiss_fft_state *st=NULL;
544 size_t memneeded = sizeof(struct kiss_fft_state); /* twiddle factors*/
545
546 if ( lenmem==NULL ) {
547 st = ( kiss_fft_state*)KISS_FFT_MALLOC( memneeded );
548 }else{
549 if (mem != NULL && *lenmem >= memneeded)
550 st = (kiss_fft_state*)mem;
551 *lenmem = memneeded;
552 }
553 if (st) {
554 opus_int16 *bitrev;
555 kiss_twiddle_cpx *twiddles;
556
557 st->nfft=nfft;
558 #ifndef FIXED_POINT
559 st->scale = 1.f/nfft;
560 #endif
561 if (base != NULL)
562 {
563 st->twiddles = base->twiddles;
564 st->shift = 0;
565 while (nfft<<st->shift != base->nfft && st->shift < 32)
566 st->shift++;
567 if (st->shift>=32)
568 goto fail;
569 } else {
570 st->twiddles = twiddles = (kiss_twiddle_cpx*)KISS_FFT_MALLOC(sizeof(kiss_twiddle_cpx)*nfft);
571 compute_twiddles(twiddles, nfft);
572 st->shift = -1;
573 }
574 if (!kf_factor(nfft,st->factors))
575 {
576 goto fail;
577 }
578
579 /* bitrev */
580 st->bitrev = bitrev = (opus_int16*)KISS_FFT_MALLOC(sizeof(opus_int16)*nfft);
581 if (st->bitrev==NULL)
582 goto fail;
583 compute_bitrev_table(0, bitrev, 1,1, st->factors,st);
584 }
585 return st;
586 fail:
587 opus_fft_free(st);
588 return NULL;
589 }
590
opus_fft_alloc(int nfft,void * mem,size_t * lenmem)591 kiss_fft_state *opus_fft_alloc(int nfft,void * mem,size_t * lenmem )
592 {
593 return opus_fft_alloc_twiddles(nfft, mem, lenmem, NULL);
594 }
595
opus_fft_free(const kiss_fft_state * cfg)596 void opus_fft_free(const kiss_fft_state *cfg)
597 {
598 if (cfg)
599 {
600 opus_free((opus_int16*)cfg->bitrev);
601 if (cfg->shift < 0)
602 opus_free((kiss_twiddle_cpx*)cfg->twiddles);
603 opus_free((kiss_fft_state*)cfg);
604 }
605 }
606
607 #endif /* CUSTOM_MODES */
608
opus_fft(const kiss_fft_state * st,const kiss_fft_cpx * fin,kiss_fft_cpx * fout)609 void opus_fft(const kiss_fft_state *st,const kiss_fft_cpx *fin,kiss_fft_cpx *fout)
610 {
611 int m2, m;
612 int p;
613 int L;
614 int fstride[MAXFACTORS];
615 int i;
616 int shift;
617
618 /* st->shift can be -1 */
619 shift = st->shift>0 ? st->shift : 0;
620
621 celt_assert2 (fin != fout, "In-place FFT not supported");
622 /* Bit-reverse the input */
623 for (i=0;i<st->nfft;i++)
624 {
625 fout[st->bitrev[i]] = fin[i];
626 #ifndef FIXED_POINT
627 fout[st->bitrev[i]].r *= st->scale;
628 fout[st->bitrev[i]].i *= st->scale;
629 #endif
630 }
631
632 fstride[0] = 1;
633 L=0;
634 do {
635 p = st->factors[2*L];
636 m = st->factors[2*L+1];
637 fstride[L+1] = fstride[L]*p;
638 L++;
639 } while(m!=1);
640 m = st->factors[2*L-1];
641 for (i=L-1;i>=0;i--)
642 {
643 if (i!=0)
644 m2 = st->factors[2*i-1];
645 else
646 m2 = 1;
647 switch (st->factors[2*i])
648 {
649 case 2:
650 kf_bfly2(fout,fstride[i]<<shift,st,m, fstride[i], m2);
651 break;
652 case 4:
653 kf_bfly4(fout,fstride[i]<<shift,st,m, fstride[i], m2);
654 break;
655 #ifndef RADIX_TWO_ONLY
656 case 3:
657 kf_bfly3(fout,fstride[i]<<shift,st,m, fstride[i], m2);
658 break;
659 case 5:
660 kf_bfly5(fout,fstride[i]<<shift,st,m, fstride[i], m2);
661 break;
662 #endif
663 }
664 m = m2;
665 }
666 }
667
opus_ifft(const kiss_fft_state * st,const kiss_fft_cpx * fin,kiss_fft_cpx * fout)668 void opus_ifft(const kiss_fft_state *st,const kiss_fft_cpx *fin,kiss_fft_cpx *fout)
669 {
670 int m2, m;
671 int p;
672 int L;
673 int fstride[MAXFACTORS];
674 int i;
675 int shift;
676
677 /* st->shift can be -1 */
678 shift = st->shift>0 ? st->shift : 0;
679 celt_assert2 (fin != fout, "In-place FFT not supported");
680 /* Bit-reverse the input */
681 for (i=0;i<st->nfft;i++)
682 fout[st->bitrev[i]] = fin[i];
683
684 fstride[0] = 1;
685 L=0;
686 do {
687 p = st->factors[2*L];
688 m = st->factors[2*L+1];
689 fstride[L+1] = fstride[L]*p;
690 L++;
691 } while(m!=1);
692 m = st->factors[2*L-1];
693 for (i=L-1;i>=0;i--)
694 {
695 if (i!=0)
696 m2 = st->factors[2*i-1];
697 else
698 m2 = 1;
699 switch (st->factors[2*i])
700 {
701 case 2:
702 ki_bfly2(fout,fstride[i]<<shift,st,m, fstride[i], m2);
703 break;
704 case 4:
705 ki_bfly4(fout,fstride[i]<<shift,st,m, fstride[i], m2);
706 break;
707 #ifndef RADIX_TWO_ONLY
708 case 3:
709 ki_bfly3(fout,fstride[i]<<shift,st,m, fstride[i], m2);
710 break;
711 case 5:
712 ki_bfly5(fout,fstride[i]<<shift,st,m, fstride[i], m2);
713 break;
714 #endif
715 }
716 m = m2;
717 }
718 }
719
720