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