ae738bcee9e47720a3b162252e433a9fa17745c9
[opus.git] / libcelt / 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   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
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 = SHR(Fout->r, 1);Fout->i = SHR(Fout->i, 1);
70          Fout2->r = SHR(Fout2->r, 1);Fout2->i = SHR(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
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
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 = PSHR(Fout->r, 2);
139          Fout->i = PSHR(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          Fout[m2].r = PSHR(Fout[m2].r, 2);
145          Fout[m2].i = PSHR(Fout[m2].i, 2);
146          C_SUB( Fout[m2], *Fout, scratch[3] );
147          tw1 += fstride;
148          tw2 += fstride*2;
149          tw3 += fstride*3;
150          C_ADDTO( *Fout , scratch[3] );
151
152          Fout[m].r = scratch[5].r + scratch[4].i;
153          Fout[m].i = scratch[5].i - scratch[4].r;
154          Fout[m3].r = scratch[5].r - scratch[4].i;
155          Fout[m3].i = scratch[5].i + scratch[4].r;
156          ++Fout;
157       }
158    }
159 }
160
161 static void ki_bfly4(
162                      kiss_fft_cpx * Fout,
163                      const size_t fstride,
164                      const kiss_fft_state *st,
165                      int m,
166                      int N,
167                      int mm
168                     )
169 {
170    const kiss_twiddle_cpx *tw1,*tw2,*tw3;
171    kiss_fft_cpx scratch[6];
172    const size_t m2=2*m;
173    const size_t m3=3*m;
174    int i, j;
175
176    kiss_fft_cpx * Fout_beg = Fout;
177    for (i=0;i<N;i++)
178    {
179       Fout = Fout_beg + i*mm;
180       tw3 = tw2 = tw1 = st->twiddles;
181       for (j=0;j<m;j++)
182       {
183          C_MULC(scratch[0],Fout[m] , *tw1 );
184          C_MULC(scratch[1],Fout[m2] , *tw2 );
185          C_MULC(scratch[2],Fout[m3] , *tw3 );
186
187          C_SUB( scratch[5] , *Fout, scratch[1] );
188          C_ADDTO(*Fout, scratch[1]);
189          C_ADD( scratch[3] , scratch[0] , scratch[2] );
190          C_SUB( scratch[4] , scratch[0] , scratch[2] );
191          C_SUB( Fout[m2], *Fout, scratch[3] );
192          tw1 += fstride;
193          tw2 += fstride*2;
194          tw3 += fstride*3;
195          C_ADDTO( *Fout , scratch[3] );
196
197          Fout[m].r = scratch[5].r - scratch[4].i;
198          Fout[m].i = scratch[5].i + scratch[4].r;
199          Fout[m3].r = scratch[5].r + scratch[4].i;
200          Fout[m3].i = scratch[5].i - scratch[4].r;
201          ++Fout;
202       }
203    }
204 }
205
206 #ifndef RADIX_TWO_ONLY
207
208 static void kf_bfly3(
209                      kiss_fft_cpx * Fout,
210                      const size_t fstride,
211                      const kiss_fft_state *st,
212                      int m,
213                      int N,
214                      int mm
215                     )
216 {
217    int i;
218    size_t k;
219    const size_t m2 = 2*m;
220    const kiss_twiddle_cpx *tw1,*tw2;
221    kiss_fft_cpx scratch[5];
222    kiss_twiddle_cpx epi3;
223
224    kiss_fft_cpx * Fout_beg = Fout;
225    epi3 = st->twiddles[fstride*m];
226    for (i=0;i<N;i++)
227    {
228       Fout = Fout_beg + i*mm;
229       tw1=tw2=st->twiddles;
230       k=m;
231       do {
232          C_FIXDIV(*Fout,3); C_FIXDIV(Fout[m],3); C_FIXDIV(Fout[m2],3);
233
234          C_MUL(scratch[1],Fout[m] , *tw1);
235          C_MUL(scratch[2],Fout[m2] , *tw2);
236
237          C_ADD(scratch[3],scratch[1],scratch[2]);
238          C_SUB(scratch[0],scratch[1],scratch[2]);
239          tw1 += fstride;
240          tw2 += fstride*2;
241
242          Fout[m].r = Fout->r - HALF_OF(scratch[3].r);
243          Fout[m].i = Fout->i - HALF_OF(scratch[3].i);
244
245          C_MULBYSCALAR( scratch[0] , epi3.i );
246
247          C_ADDTO(*Fout,scratch[3]);
248
249          Fout[m2].r = Fout[m].r + scratch[0].i;
250          Fout[m2].i = Fout[m].i - scratch[0].r;
251
252          Fout[m].r -= scratch[0].i;
253          Fout[m].i += scratch[0].r;
254
255          ++Fout;
256       } while(--k);
257    }
258 }
259
260 static void ki_bfly3(
261                      kiss_fft_cpx * Fout,
262                      const size_t fstride,
263                      const kiss_fft_state *st,
264                      size_t m,
265                      int N,
266                      int mm
267                     )
268 {
269    size_t i, k;
270    const size_t m2 = 2*m;
271    const kiss_twiddle_cpx *tw1,*tw2;
272    kiss_fft_cpx scratch[5];
273    kiss_twiddle_cpx epi3;
274
275    kiss_fft_cpx * Fout_beg = Fout;
276    epi3 = st->twiddles[fstride*m];
277    for (i=0;i<N;i++)
278    {
279       Fout = Fout_beg + i*mm;
280       tw1=tw2=st->twiddles;
281       k=m;
282       do{
283
284          C_MULC(scratch[1],Fout[m] , *tw1);
285          C_MULC(scratch[2],Fout[m2] , *tw2);
286
287          C_ADD(scratch[3],scratch[1],scratch[2]);
288          C_SUB(scratch[0],scratch[1],scratch[2]);
289          tw1 += fstride;
290          tw2 += fstride*2;
291
292          Fout[m].r = Fout->r - HALF_OF(scratch[3].r);
293          Fout[m].i = Fout->i - HALF_OF(scratch[3].i);
294
295          C_MULBYSCALAR( scratch[0] , -epi3.i );
296
297          C_ADDTO(*Fout,scratch[3]);
298
299          Fout[m2].r = Fout[m].r + scratch[0].i;
300          Fout[m2].i = Fout[m].i - scratch[0].r;
301
302          Fout[m].r -= scratch[0].i;
303          Fout[m].i += scratch[0].r;
304
305          ++Fout;
306       }while(--k);
307    }
308 }
309
310 static void kf_bfly5(
311                      kiss_fft_cpx * Fout,
312                      const size_t fstride,
313                      const kiss_fft_state *st,
314                      int m,
315                      int N,
316                      int mm
317                     )
318 {
319    kiss_fft_cpx *Fout0,*Fout1,*Fout2,*Fout3,*Fout4;
320    int i, u;
321    kiss_fft_cpx scratch[13];
322    const kiss_twiddle_cpx * twiddles = st->twiddles;
323    const kiss_twiddle_cpx *tw;
324    kiss_twiddle_cpx ya,yb;
325    kiss_fft_cpx * Fout_beg = Fout;
326
327    ya = twiddles[fstride*m];
328    yb = twiddles[fstride*2*m];
329    tw=st->twiddles;
330
331    for (i=0;i<N;i++)
332    {
333       Fout = Fout_beg + i*mm;
334       Fout0=Fout;
335       Fout1=Fout0+m;
336       Fout2=Fout0+2*m;
337       Fout3=Fout0+3*m;
338       Fout4=Fout0+4*m;
339
340       for ( u=0; u<m; ++u ) {
341          C_FIXDIV( *Fout0,5); C_FIXDIV( *Fout1,5); C_FIXDIV( *Fout2,5); C_FIXDIV( *Fout3,5); C_FIXDIV( *Fout4,5);
342          scratch[0] = *Fout0;
343
344          C_MUL(scratch[1] ,*Fout1, tw[u*fstride]);
345          C_MUL(scratch[2] ,*Fout2, tw[2*u*fstride]);
346          C_MUL(scratch[3] ,*Fout3, tw[3*u*fstride]);
347          C_MUL(scratch[4] ,*Fout4, tw[4*u*fstride]);
348
349          C_ADD( scratch[7],scratch[1],scratch[4]);
350          C_SUB( scratch[10],scratch[1],scratch[4]);
351          C_ADD( scratch[8],scratch[2],scratch[3]);
352          C_SUB( scratch[9],scratch[2],scratch[3]);
353
354          Fout0->r += scratch[7].r + scratch[8].r;
355          Fout0->i += scratch[7].i + scratch[8].i;
356
357          scratch[5].r = scratch[0].r + S_MUL(scratch[7].r,ya.r) + S_MUL(scratch[8].r,yb.r);
358          scratch[5].i = scratch[0].i + S_MUL(scratch[7].i,ya.r) + S_MUL(scratch[8].i,yb.r);
359
360          scratch[6].r =  S_MUL(scratch[10].i,ya.i) + S_MUL(scratch[9].i,yb.i);
361          scratch[6].i = -S_MUL(scratch[10].r,ya.i) - S_MUL(scratch[9].r,yb.i);
362
363          C_SUB(*Fout1,scratch[5],scratch[6]);
364          C_ADD(*Fout4,scratch[5],scratch[6]);
365
366          scratch[11].r = scratch[0].r + S_MUL(scratch[7].r,yb.r) + S_MUL(scratch[8].r,ya.r);
367          scratch[11].i = scratch[0].i + S_MUL(scratch[7].i,yb.r) + S_MUL(scratch[8].i,ya.r);
368          scratch[12].r = - S_MUL(scratch[10].i,yb.i) + S_MUL(scratch[9].i,ya.i);
369          scratch[12].i = S_MUL(scratch[10].r,yb.i) - S_MUL(scratch[9].r,ya.i);
370
371          C_ADD(*Fout2,scratch[11],scratch[12]);
372          C_SUB(*Fout3,scratch[11],scratch[12]);
373
374          ++Fout0;++Fout1;++Fout2;++Fout3;++Fout4;
375       }
376    }
377 }
378
379 static void ki_bfly5(
380                      kiss_fft_cpx * Fout,
381                      const size_t fstride,
382                      const kiss_fft_state *st,
383                      int m,
384                      int N,
385                      int mm
386                     )
387 {
388    kiss_fft_cpx *Fout0,*Fout1,*Fout2,*Fout3,*Fout4;
389    int i, u;
390    kiss_fft_cpx scratch[13];
391    const kiss_twiddle_cpx * twiddles = st->twiddles;
392    const kiss_twiddle_cpx *tw;
393    kiss_twiddle_cpx ya,yb;
394    kiss_fft_cpx * Fout_beg = Fout;
395
396    ya = twiddles[fstride*m];
397    yb = twiddles[fstride*2*m];
398    tw=st->twiddles;
399
400    for (i=0;i<N;i++)
401    {
402       Fout = Fout_beg + i*mm;
403       Fout0=Fout;
404       Fout1=Fout0+m;
405       Fout2=Fout0+2*m;
406       Fout3=Fout0+3*m;
407       Fout4=Fout0+4*m;
408
409       for ( u=0; u<m; ++u ) {
410          scratch[0] = *Fout0;
411
412          C_MULC(scratch[1] ,*Fout1, tw[u*fstride]);
413          C_MULC(scratch[2] ,*Fout2, tw[2*u*fstride]);
414          C_MULC(scratch[3] ,*Fout3, tw[3*u*fstride]);
415          C_MULC(scratch[4] ,*Fout4, tw[4*u*fstride]);
416
417          C_ADD( scratch[7],scratch[1],scratch[4]);
418          C_SUB( scratch[10],scratch[1],scratch[4]);
419          C_ADD( scratch[8],scratch[2],scratch[3]);
420          C_SUB( scratch[9],scratch[2],scratch[3]);
421
422          Fout0->r += scratch[7].r + scratch[8].r;
423          Fout0->i += scratch[7].i + scratch[8].i;
424
425          scratch[5].r = scratch[0].r + S_MUL(scratch[7].r,ya.r) + S_MUL(scratch[8].r,yb.r);
426          scratch[5].i = scratch[0].i + S_MUL(scratch[7].i,ya.r) + S_MUL(scratch[8].i,yb.r);
427
428          scratch[6].r = -S_MUL(scratch[10].i,ya.i) - S_MUL(scratch[9].i,yb.i);
429          scratch[6].i =  S_MUL(scratch[10].r,ya.i) + S_MUL(scratch[9].r,yb.i);
430
431          C_SUB(*Fout1,scratch[5],scratch[6]);
432          C_ADD(*Fout4,scratch[5],scratch[6]);
433
434          scratch[11].r = scratch[0].r + S_MUL(scratch[7].r,yb.r) + S_MUL(scratch[8].r,ya.r);
435          scratch[11].i = scratch[0].i + S_MUL(scratch[7].i,yb.r) + S_MUL(scratch[8].i,ya.r);
436          scratch[12].r =  S_MUL(scratch[10].i,yb.i) - S_MUL(scratch[9].i,ya.i);
437          scratch[12].i = -S_MUL(scratch[10].r,yb.i) + S_MUL(scratch[9].r,ya.i);
438
439          C_ADD(*Fout2,scratch[11],scratch[12]);
440          C_SUB(*Fout3,scratch[11],scratch[12]);
441
442          ++Fout0;++Fout1;++Fout2;++Fout3;++Fout4;
443       }
444    }
445 }
446
447 #endif
448
449
450 #ifdef CUSTOM_MODES
451
452 static
453 void compute_bitrev_table(
454          int Fout,
455          opus_int16 *f,
456          const size_t fstride,
457          int in_stride,
458          opus_int16 * factors,
459          const kiss_fft_state *st
460             )
461 {
462    const int p=*factors++; /* the radix  */
463    const int m=*factors++; /* stage's fft length/p */
464
465     /*printf ("fft %d %d %d %d %d %d\n", p*m, m, p, s2, fstride*in_stride, N);*/
466    if (m==1)
467    {
468       int j;
469       for (j=0;j<p;j++)
470       {
471          *f = Fout+j;
472          f += fstride*in_stride;
473       }
474    } else {
475       int j;
476       for (j=0;j<p;j++)
477       {
478          compute_bitrev_table( Fout , f, fstride*p, in_stride, factors,st);
479          f += fstride*in_stride;
480          Fout += m;
481       }
482    }
483 }
484
485 /*  facbuf is populated by p1,m1,p2,m2, ...
486     where
487     p[i] * m[i] = m[i-1]
488     m0 = n                  */
489 static
490 int kf_factor(int n,opus_int16 * facbuf)
491 {
492     int p=4;
493
494     /*factor out powers of 4, powers of 2, then any remaining primes */
495     do {
496         while (n % p) {
497             switch (p) {
498                 case 4: p = 2; break;
499                 case 2: p = 3; break;
500                 default: p += 2; break;
501             }
502             if (p>32000 || (opus_int32)p*(opus_int32)p > n)
503                 p = n;          /* no more factors, skip to end */
504         }
505         n /= p;
506 #ifdef RADIX_TWO_ONLY
507         if (p!=2 && p != 4)
508 #else
509         if (p>5)
510 #endif
511         {
512            return 0;
513         }
514         *facbuf++ = p;
515         *facbuf++ = n;
516     } while (n > 1);
517     return 1;
518 }
519
520 static void compute_twiddles(kiss_twiddle_cpx *twiddles, int nfft)
521 {
522    int i;
523 #ifdef FIXED_POINT
524    for (i=0;i<nfft;++i) {
525       opus_val32 phase = -i;
526       kf_cexp2(twiddles+i, DIV32(SHL32(phase,17),nfft));
527    }
528 #else
529    for (i=0;i<nfft;++i) {
530       const double pi=3.14159265358979323846264338327;
531       double phase = ( -2*pi /nfft ) * i;
532       kf_cexp(twiddles+i, phase );
533    }
534 #endif
535 }
536
537 /*
538  *
539  * Allocates all necessary storage space for the fft and ifft.
540  * The return value is a contiguous block of memory.  As such,
541  * It can be freed with free().
542  * */
543 kiss_fft_state *opus_fft_alloc_twiddles(int nfft,void * mem,size_t * lenmem,  const kiss_fft_state *base)
544 {
545     kiss_fft_state *st=NULL;
546     size_t memneeded = sizeof(struct kiss_fft_state); /* twiddle factors*/
547
548     if ( lenmem==NULL ) {
549         st = ( kiss_fft_state*)KISS_FFT_MALLOC( memneeded );
550     }else{
551         if (mem != NULL && *lenmem >= memneeded)
552             st = (kiss_fft_state*)mem;
553         *lenmem = memneeded;
554     }
555     if (st) {
556         opus_int16 *bitrev;
557         kiss_twiddle_cpx *twiddles;
558
559         st->nfft=nfft;
560 #ifndef FIXED_POINT
561         st->scale = 1./nfft;
562 #endif
563         if (base != NULL)
564         {
565            st->twiddles = base->twiddles;
566            st->shift = 0;
567            while (nfft<<st->shift != base->nfft && st->shift < 32)
568               st->shift++;
569            if (st->shift>=32)
570               goto fail;
571         } else {
572            st->twiddles = twiddles = (kiss_twiddle_cpx*)KISS_FFT_MALLOC(sizeof(kiss_twiddle_cpx)*nfft);
573            compute_twiddles(twiddles, nfft);
574            st->shift = -1;
575         }
576         if (!kf_factor(nfft,st->factors))
577         {
578            opus_fft_free(st);
579            goto fail;
580         }
581
582         /* bitrev */
583         st->bitrev = bitrev = (opus_int16*)KISS_FFT_MALLOC(sizeof(opus_int16)*nfft);
584         if (st->bitrev==NULL)
585             goto fail;
586         compute_bitrev_table(0, bitrev, 1,1, st->factors,st);
587     }
588     return st;
589 fail:
590     opus_fft_free(st);
591     return NULL;
592 }
593
594 kiss_fft_state *opus_fft_alloc(int nfft,void * mem,size_t * lenmem )
595 {
596    return opus_fft_alloc_twiddles(nfft, mem, lenmem, NULL);
597 }
598
599 void opus_fft_free(const kiss_fft_state *cfg)
600 {
601    if (cfg)
602    {
603       celt_free((opus_int16*)cfg->bitrev);
604       if (cfg->shift < 0)
605          celt_free((kiss_twiddle_cpx*)cfg->twiddles);
606       celt_free((kiss_fft_state*)cfg);
607    }
608 }
609
610 #endif /* CUSTOM_MODES */
611
612 void opus_fft(const kiss_fft_state *st,const kiss_fft_cpx *fin,kiss_fft_cpx *fout)
613 {
614     int m2, m;
615     int p;
616     int L;
617     int fstride[MAXFACTORS];
618     int i;
619     int shift;
620
621     /* st->shift can be -1 */
622     shift = st->shift>0 ? st->shift : 0;
623
624     celt_assert2 (fin != fout, "In-place FFT not supported");
625     /* Bit-reverse the input */
626     for (i=0;i<st->nfft;i++)
627     {
628        fout[st->bitrev[i]] = fin[i];
629 #ifndef FIXED_POINT
630        fout[st->bitrev[i]].r *= st->scale;
631        fout[st->bitrev[i]].i *= st->scale;
632 #endif
633     }
634
635     fstride[0] = 1;
636     L=0;
637     do {
638        p = st->factors[2*L];
639        m = st->factors[2*L+1];
640        fstride[L+1] = fstride[L]*p;
641        L++;
642     } while(m!=1);
643     m2 = 1;
644     m = st->factors[2*L-1];
645     for (i=L-1;i>=0;i--)
646     {
647        if (i!=0)
648           m2 = st->factors[2*i-1];
649        else
650           m2 = 1;
651        switch (st->factors[2*i])
652        {
653        case 2:
654           kf_bfly2(fout,fstride[i]<<shift,st,m, fstride[i], m2);
655           break;
656        case 4:
657           kf_bfly4(fout,fstride[i]<<shift,st,m, fstride[i], m2);
658           break;
659  #ifndef RADIX_TWO_ONLY
660        case 3:
661           kf_bfly3(fout,fstride[i]<<shift,st,m, fstride[i], m2);
662           break;
663        case 5:
664           kf_bfly5(fout,fstride[i]<<shift,st,m, fstride[i], m2);
665           break;
666  #endif
667        }
668        m = m2;
669     }
670 }
671
672 void opus_ifft(const kiss_fft_state *st,const kiss_fft_cpx *fin,kiss_fft_cpx *fout)
673 {
674    int m2, m;
675    int p;
676    int L;
677    int fstride[MAXFACTORS];
678    int i;
679    int shift;
680
681    /* st->shift can be -1 */
682    shift = st->shift>0 ? st->shift : 0;
683    celt_assert2 (fin != fout, "In-place FFT not supported");
684    /* Bit-reverse the input */
685    for (i=0;i<st->nfft;i++)
686       fout[st->bitrev[i]] = fin[i];
687
688    fstride[0] = 1;
689    L=0;
690    do {
691       p = st->factors[2*L];
692       m = st->factors[2*L+1];
693       fstride[L+1] = fstride[L]*p;
694       L++;
695    } while(m!=1);
696    m2 = 1;
697    m = st->factors[2*L-1];
698    for (i=L-1;i>=0;i--)
699    {
700       if (i!=0)
701          m2 = st->factors[2*i-1];
702       else
703          m2 = 1;
704       switch (st->factors[2*i])
705       {
706       case 2:
707          ki_bfly2(fout,fstride[i]<<shift,st,m, fstride[i], m2);
708          break;
709       case 4:
710          ki_bfly4(fout,fstride[i]<<shift,st,m, fstride[i], m2);
711          break;
712 #ifndef RADIX_TWO_ONLY
713       case 3:
714          ki_bfly3(fout,fstride[i]<<shift,st,m, fstride[i], m2);
715          break;
716       case 5:
717          ki_bfly5(fout,fstride[i]<<shift,st,m, fstride[i], m2);
718          break;
719 #endif
720       }
721       m = m2;
722    }
723 }
724