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