Add the noreturn attribute on the assert functions to aid static analysis, improve...
[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   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 #include "os_support.h"
44
45 /* The guts header contains all the multiplication and addition macros that are defined for
46    complex numbers.  It also delares the kf_ internal functions.
47 */
48
49 static void kf_bfly2(
50                      kiss_fft_cpx * Fout,
51                      const size_t fstride,
52                      const kiss_fft_state *st,
53                      int m,
54                      int N,
55                      int mm
56                     )
57 {
58    kiss_fft_cpx * Fout2;
59    const kiss_twiddle_cpx * tw1;
60    int i,j;
61    kiss_fft_cpx * Fout_beg = Fout;
62    for (i=0;i<N;i++)
63    {
64       Fout = Fout_beg + i*mm;
65       Fout2 = Fout + m;
66       tw1 = st->twiddles;
67       for(j=0;j<m;j++)
68       {
69          kiss_fft_cpx t;
70          Fout->r = SHR(Fout->r, 1);Fout->i = SHR(Fout->i, 1);
71          Fout2->r = SHR(Fout2->r, 1);Fout2->i = SHR(Fout2->i, 1);
72          C_MUL (t,  *Fout2 , *tw1);
73          tw1 += fstride;
74          C_SUB( *Fout2 ,  *Fout , t );
75          C_ADDTO( *Fout ,  t );
76          ++Fout2;
77          ++Fout;
78       }
79    }
80 }
81
82 static void ki_bfly2(
83                      kiss_fft_cpx * Fout,
84                      const size_t fstride,
85                      const kiss_fft_state *st,
86                      int m,
87                      int N,
88                      int mm
89                     )
90 {
91    kiss_fft_cpx * Fout2;
92    const kiss_twiddle_cpx * tw1;
93    kiss_fft_cpx t;
94    int i,j;
95    kiss_fft_cpx * Fout_beg = Fout;
96    for (i=0;i<N;i++)
97    {
98       Fout = Fout_beg + i*mm;
99       Fout2 = Fout + m;
100       tw1 = st->twiddles;
101       for(j=0;j<m;j++)
102       {
103          C_MULC (t,  *Fout2 , *tw1);
104          tw1 += fstride;
105          C_SUB( *Fout2 ,  *Fout , t );
106          C_ADDTO( *Fout ,  t );
107          ++Fout2;
108          ++Fout;
109       }
110    }
111 }
112
113 static void kf_bfly4(
114                      kiss_fft_cpx * Fout,
115                      const size_t fstride,
116                      const kiss_fft_state *st,
117                      int m,
118                      int N,
119                      int mm
120                     )
121 {
122    const kiss_twiddle_cpx *tw1,*tw2,*tw3;
123    kiss_fft_cpx scratch[6];
124    const size_t m2=2*m;
125    const size_t m3=3*m;
126    int i, j;
127
128    kiss_fft_cpx * Fout_beg = Fout;
129    for (i=0;i<N;i++)
130    {
131       Fout = Fout_beg + i*mm;
132       tw3 = tw2 = tw1 = st->twiddles;
133       for (j=0;j<m;j++)
134       {
135          C_MUL4(scratch[0],Fout[m] , *tw1 );
136          C_MUL4(scratch[1],Fout[m2] , *tw2 );
137          C_MUL4(scratch[2],Fout[m3] , *tw3 );
138
139          Fout->r = PSHR(Fout->r, 2);
140          Fout->i = PSHR(Fout->i, 2);
141          C_SUB( scratch[5] , *Fout, scratch[1] );
142          C_ADDTO(*Fout, scratch[1]);
143          C_ADD( scratch[3] , scratch[0] , scratch[2] );
144          C_SUB( scratch[4] , scratch[0] , scratch[2] );
145          Fout[m2].r = PSHR(Fout[m2].r, 2);
146          Fout[m2].i = PSHR(Fout[m2].i, 2);
147          C_SUB( Fout[m2], *Fout, scratch[3] );
148          tw1 += fstride;
149          tw2 += fstride*2;
150          tw3 += fstride*3;
151          C_ADDTO( *Fout , scratch[3] );
152
153          Fout[m].r = scratch[5].r + scratch[4].i;
154          Fout[m].i = scratch[5].i - scratch[4].r;
155          Fout[m3].r = scratch[5].r - scratch[4].i;
156          Fout[m3].i = scratch[5].i + scratch[4].r;
157          ++Fout;
158       }
159    }
160 }
161
162 static void ki_bfly4(
163                      kiss_fft_cpx * Fout,
164                      const size_t fstride,
165                      const kiss_fft_state *st,
166                      int m,
167                      int N,
168                      int mm
169                     )
170 {
171    const kiss_twiddle_cpx *tw1,*tw2,*tw3;
172    kiss_fft_cpx scratch[6];
173    const size_t m2=2*m;
174    const size_t m3=3*m;
175    int i, j;
176
177    kiss_fft_cpx * Fout_beg = Fout;
178    for (i=0;i<N;i++)
179    {
180       Fout = Fout_beg + i*mm;
181       tw3 = tw2 = tw1 = st->twiddles;
182       for (j=0;j<m;j++)
183       {
184          C_MULC(scratch[0],Fout[m] , *tw1 );
185          C_MULC(scratch[1],Fout[m2] , *tw2 );
186          C_MULC(scratch[2],Fout[m3] , *tw3 );
187
188          C_SUB( scratch[5] , *Fout, scratch[1] );
189          C_ADDTO(*Fout, scratch[1]);
190          C_ADD( scratch[3] , scratch[0] , scratch[2] );
191          C_SUB( scratch[4] , scratch[0] , scratch[2] );
192          C_SUB( Fout[m2], *Fout, scratch[3] );
193          tw1 += fstride;
194          tw2 += fstride*2;
195          tw3 += fstride*3;
196          C_ADDTO( *Fout , scratch[3] );
197
198          Fout[m].r = scratch[5].r - scratch[4].i;
199          Fout[m].i = scratch[5].i + scratch[4].r;
200          Fout[m3].r = scratch[5].r + scratch[4].i;
201          Fout[m3].i = scratch[5].i - scratch[4].r;
202          ++Fout;
203       }
204    }
205 }
206
207 #ifndef RADIX_TWO_ONLY
208
209 static void kf_bfly3(
210                      kiss_fft_cpx * Fout,
211                      const size_t fstride,
212                      const kiss_fft_state *st,
213                      int m,
214                      int N,
215                      int mm
216                     )
217 {
218    int i;
219    size_t k;
220    const size_t m2 = 2*m;
221    const kiss_twiddle_cpx *tw1,*tw2;
222    kiss_fft_cpx scratch[5];
223    kiss_twiddle_cpx epi3;
224
225    kiss_fft_cpx * Fout_beg = Fout;
226    epi3 = st->twiddles[fstride*m];
227    for (i=0;i<N;i++)
228    {
229       Fout = Fout_beg + i*mm;
230       tw1=tw2=st->twiddles;
231       k=m;
232       do {
233          C_FIXDIV(*Fout,3); C_FIXDIV(Fout[m],3); C_FIXDIV(Fout[m2],3);
234
235          C_MUL(scratch[1],Fout[m] , *tw1);
236          C_MUL(scratch[2],Fout[m2] , *tw2);
237
238          C_ADD(scratch[3],scratch[1],scratch[2]);
239          C_SUB(scratch[0],scratch[1],scratch[2]);
240          tw1 += fstride;
241          tw2 += fstride*2;
242
243          Fout[m].r = Fout->r - HALF_OF(scratch[3].r);
244          Fout[m].i = Fout->i - HALF_OF(scratch[3].i);
245
246          C_MULBYSCALAR( scratch[0] , epi3.i );
247
248          C_ADDTO(*Fout,scratch[3]);
249
250          Fout[m2].r = Fout[m].r + scratch[0].i;
251          Fout[m2].i = Fout[m].i - scratch[0].r;
252
253          Fout[m].r -= scratch[0].i;
254          Fout[m].i += scratch[0].r;
255
256          ++Fout;
257       } while(--k);
258    }
259 }
260
261 static void ki_bfly3(
262                      kiss_fft_cpx * Fout,
263                      const size_t fstride,
264                      const kiss_fft_state *st,
265                      int m,
266                      int N,
267                      int mm
268                     )
269 {
270    int i, k;
271    const size_t m2 = 2*m;
272    const kiss_twiddle_cpx *tw1,*tw2;
273    kiss_fft_cpx scratch[5];
274    kiss_twiddle_cpx epi3;
275
276    kiss_fft_cpx * Fout_beg = Fout;
277    epi3 = st->twiddles[fstride*m];
278    for (i=0;i<N;i++)
279    {
280       Fout = Fout_beg + i*mm;
281       tw1=tw2=st->twiddles;
282       k=m;
283       do{
284
285          C_MULC(scratch[1],Fout[m] , *tw1);
286          C_MULC(scratch[2],Fout[m2] , *tw2);
287
288          C_ADD(scratch[3],scratch[1],scratch[2]);
289          C_SUB(scratch[0],scratch[1],scratch[2]);
290          tw1 += fstride;
291          tw2 += fstride*2;
292
293          Fout[m].r = Fout->r - HALF_OF(scratch[3].r);
294          Fout[m].i = Fout->i - HALF_OF(scratch[3].i);
295
296          C_MULBYSCALAR( scratch[0] , -epi3.i );
297
298          C_ADDTO(*Fout,scratch[3]);
299
300          Fout[m2].r = Fout[m].r + scratch[0].i;
301          Fout[m2].i = Fout[m].i - scratch[0].r;
302
303          Fout[m].r -= scratch[0].i;
304          Fout[m].i += scratch[0].r;
305
306          ++Fout;
307       }while(--k);
308    }
309 }
310
311 static void kf_bfly5(
312                      kiss_fft_cpx * Fout,
313                      const size_t fstride,
314                      const kiss_fft_state *st,
315                      int m,
316                      int N,
317                      int mm
318                     )
319 {
320    kiss_fft_cpx *Fout0,*Fout1,*Fout2,*Fout3,*Fout4;
321    int i, u;
322    kiss_fft_cpx scratch[13];
323    const kiss_twiddle_cpx * twiddles = st->twiddles;
324    const kiss_twiddle_cpx *tw;
325    kiss_twiddle_cpx ya,yb;
326    kiss_fft_cpx * Fout_beg = Fout;
327
328    ya = twiddles[fstride*m];
329    yb = twiddles[fstride*2*m];
330    tw=st->twiddles;
331
332    for (i=0;i<N;i++)
333    {
334       Fout = Fout_beg + i*mm;
335       Fout0=Fout;
336       Fout1=Fout0+m;
337       Fout2=Fout0+2*m;
338       Fout3=Fout0+3*m;
339       Fout4=Fout0+4*m;
340
341       for ( u=0; u<m; ++u ) {
342          C_FIXDIV( *Fout0,5); C_FIXDIV( *Fout1,5); C_FIXDIV( *Fout2,5); C_FIXDIV( *Fout3,5); C_FIXDIV( *Fout4,5);
343          scratch[0] = *Fout0;
344
345          C_MUL(scratch[1] ,*Fout1, tw[u*fstride]);
346          C_MUL(scratch[2] ,*Fout2, tw[2*u*fstride]);
347          C_MUL(scratch[3] ,*Fout3, tw[3*u*fstride]);
348          C_MUL(scratch[4] ,*Fout4, tw[4*u*fstride]);
349
350          C_ADD( scratch[7],scratch[1],scratch[4]);
351          C_SUB( scratch[10],scratch[1],scratch[4]);
352          C_ADD( scratch[8],scratch[2],scratch[3]);
353          C_SUB( scratch[9],scratch[2],scratch[3]);
354
355          Fout0->r += scratch[7].r + scratch[8].r;
356          Fout0->i += scratch[7].i + scratch[8].i;
357
358          scratch[5].r = scratch[0].r + S_MUL(scratch[7].r,ya.r) + S_MUL(scratch[8].r,yb.r);
359          scratch[5].i = scratch[0].i + S_MUL(scratch[7].i,ya.r) + S_MUL(scratch[8].i,yb.r);
360
361          scratch[6].r =  S_MUL(scratch[10].i,ya.i) + S_MUL(scratch[9].i,yb.i);
362          scratch[6].i = -S_MUL(scratch[10].r,ya.i) - S_MUL(scratch[9].r,yb.i);
363
364          C_SUB(*Fout1,scratch[5],scratch[6]);
365          C_ADD(*Fout4,scratch[5],scratch[6]);
366
367          scratch[11].r = scratch[0].r + S_MUL(scratch[7].r,yb.r) + S_MUL(scratch[8].r,ya.r);
368          scratch[11].i = scratch[0].i + S_MUL(scratch[7].i,yb.r) + S_MUL(scratch[8].i,ya.r);
369          scratch[12].r = - S_MUL(scratch[10].i,yb.i) + S_MUL(scratch[9].i,ya.i);
370          scratch[12].i = S_MUL(scratch[10].r,yb.i) - S_MUL(scratch[9].r,ya.i);
371
372          C_ADD(*Fout2,scratch[11],scratch[12]);
373          C_SUB(*Fout3,scratch[11],scratch[12]);
374
375          ++Fout0;++Fout1;++Fout2;++Fout3;++Fout4;
376       }
377    }
378 }
379
380 static void ki_bfly5(
381                      kiss_fft_cpx * Fout,
382                      const size_t fstride,
383                      const kiss_fft_state *st,
384                      int m,
385                      int N,
386                      int mm
387                     )
388 {
389    kiss_fft_cpx *Fout0,*Fout1,*Fout2,*Fout3,*Fout4;
390    int i, u;
391    kiss_fft_cpx scratch[13];
392    const kiss_twiddle_cpx * twiddles = st->twiddles;
393    const kiss_twiddle_cpx *tw;
394    kiss_twiddle_cpx ya,yb;
395    kiss_fft_cpx * Fout_beg = Fout;
396
397    ya = twiddles[fstride*m];
398    yb = twiddles[fstride*2*m];
399    tw=st->twiddles;
400
401    for (i=0;i<N;i++)
402    {
403       Fout = Fout_beg + i*mm;
404       Fout0=Fout;
405       Fout1=Fout0+m;
406       Fout2=Fout0+2*m;
407       Fout3=Fout0+3*m;
408       Fout4=Fout0+4*m;
409
410       for ( u=0; u<m; ++u ) {
411          scratch[0] = *Fout0;
412
413          C_MULC(scratch[1] ,*Fout1, tw[u*fstride]);
414          C_MULC(scratch[2] ,*Fout2, tw[2*u*fstride]);
415          C_MULC(scratch[3] ,*Fout3, tw[3*u*fstride]);
416          C_MULC(scratch[4] ,*Fout4, tw[4*u*fstride]);
417
418          C_ADD( scratch[7],scratch[1],scratch[4]);
419          C_SUB( scratch[10],scratch[1],scratch[4]);
420          C_ADD( scratch[8],scratch[2],scratch[3]);
421          C_SUB( scratch[9],scratch[2],scratch[3]);
422
423          Fout0->r += scratch[7].r + scratch[8].r;
424          Fout0->i += scratch[7].i + scratch[8].i;
425
426          scratch[5].r = scratch[0].r + S_MUL(scratch[7].r,ya.r) + S_MUL(scratch[8].r,yb.r);
427          scratch[5].i = scratch[0].i + S_MUL(scratch[7].i,ya.r) + S_MUL(scratch[8].i,yb.r);
428
429          scratch[6].r = -S_MUL(scratch[10].i,ya.i) - S_MUL(scratch[9].i,yb.i);
430          scratch[6].i =  S_MUL(scratch[10].r,ya.i) + S_MUL(scratch[9].r,yb.i);
431
432          C_SUB(*Fout1,scratch[5],scratch[6]);
433          C_ADD(*Fout4,scratch[5],scratch[6]);
434
435          scratch[11].r = scratch[0].r + S_MUL(scratch[7].r,yb.r) + S_MUL(scratch[8].r,ya.r);
436          scratch[11].i = scratch[0].i + S_MUL(scratch[7].i,yb.r) + S_MUL(scratch[8].i,ya.r);
437          scratch[12].r =  S_MUL(scratch[10].i,yb.i) - S_MUL(scratch[9].i,ya.i);
438          scratch[12].i = -S_MUL(scratch[10].r,yb.i) + S_MUL(scratch[9].r,ya.i);
439
440          C_ADD(*Fout2,scratch[11],scratch[12]);
441          C_SUB(*Fout3,scratch[11],scratch[12]);
442
443          ++Fout0;++Fout1;++Fout2;++Fout3;++Fout4;
444       }
445    }
446 }
447
448 #endif
449
450
451 #ifdef CUSTOM_MODES
452
453 static
454 void compute_bitrev_table(
455          int Fout,
456          opus_int16 *f,
457          const size_t fstride,
458          int in_stride,
459          opus_int16 * factors,
460          const kiss_fft_state *st
461             )
462 {
463    const int p=*factors++; /* the radix  */
464    const int m=*factors++; /* stage's fft length/p */
465
466     /*printf ("fft %d %d %d %d %d %d\n", p*m, m, p, s2, fstride*in_stride, N);*/
467    if (m==1)
468    {
469       int j;
470       for (j=0;j<p;j++)
471       {
472          *f = Fout+j;
473          f += fstride*in_stride;
474       }
475    } else {
476       int j;
477       for (j=0;j<p;j++)
478       {
479          compute_bitrev_table( Fout , f, fstride*p, in_stride, factors,st);
480          f += fstride*in_stride;
481          Fout += m;
482       }
483    }
484 }
485
486 /*  facbuf is populated by p1,m1,p2,m2, ...
487     where
488     p[i] * m[i] = m[i-1]
489     m0 = n                  */
490 static
491 int kf_factor(int n,opus_int16 * facbuf)
492 {
493     int p=4;
494
495     /*factor out powers of 4, powers of 2, then any remaining primes */
496     do {
497         while (n % p) {
498             switch (p) {
499                 case 4: p = 2; break;
500                 case 2: p = 3; break;
501                 default: p += 2; break;
502             }
503             if (p>32000 || (opus_int32)p*(opus_int32)p > n)
504                 p = n;          /* no more factors, skip to end */
505         }
506         n /= p;
507 #ifdef RADIX_TWO_ONLY
508         if (p!=2 && p != 4)
509 #else
510         if (p>5)
511 #endif
512         {
513            return 0;
514         }
515         *facbuf++ = p;
516         *facbuf++ = n;
517     } while (n > 1);
518     return 1;
519 }
520
521 static void compute_twiddles(kiss_twiddle_cpx *twiddles, int nfft)
522 {
523    int i;
524 #ifdef FIXED_POINT
525    for (i=0;i<nfft;++i) {
526       opus_val32 phase = -i;
527       kf_cexp2(twiddles+i, DIV32(SHL32(phase,17),nfft));
528    }
529 #else
530    for (i=0;i<nfft;++i) {
531       const double pi=3.14159265358979323846264338327;
532       double phase = ( -2*pi /nfft ) * i;
533       kf_cexp(twiddles+i, phase );
534    }
535 #endif
536 }
537
538 /*
539  *
540  * Allocates all necessary storage space for the fft and ifft.
541  * The return value is a contiguous block of memory.  As such,
542  * It can be freed with free().
543  * */
544 kiss_fft_state *opus_fft_alloc_twiddles(int nfft,void * mem,size_t * lenmem,  const kiss_fft_state *base)
545 {
546     kiss_fft_state *st=NULL;
547     size_t memneeded = sizeof(struct kiss_fft_state); /* twiddle factors*/
548
549     if ( lenmem==NULL ) {
550         st = ( kiss_fft_state*)KISS_FFT_MALLOC( memneeded );
551     }else{
552         if (mem != NULL && *lenmem >= memneeded)
553             st = (kiss_fft_state*)mem;
554         *lenmem = memneeded;
555     }
556     if (st) {
557         opus_int16 *bitrev;
558         kiss_twiddle_cpx *twiddles;
559
560         st->nfft=nfft;
561 #ifndef FIXED_POINT
562         st->scale = 1./nfft;
563 #endif
564         if (base != NULL)
565         {
566            st->twiddles = base->twiddles;
567            st->shift = 0;
568            while (nfft<<st->shift != base->nfft && st->shift < 32)
569               st->shift++;
570            if (st->shift>=32)
571               goto fail;
572         } else {
573            st->twiddles = twiddles = (kiss_twiddle_cpx*)KISS_FFT_MALLOC(sizeof(kiss_twiddle_cpx)*nfft);
574            compute_twiddles(twiddles, nfft);
575            st->shift = -1;
576         }
577         if (!kf_factor(nfft,st->factors))
578         {
579            opus_fft_free(st);
580            goto fail;
581         }
582
583         /* bitrev */
584         st->bitrev = bitrev = (opus_int16*)KISS_FFT_MALLOC(sizeof(opus_int16)*nfft);
585         if (st->bitrev==NULL)
586             goto fail;
587         compute_bitrev_table(0, bitrev, 1,1, st->factors,st);
588     }
589     return st;
590 fail:
591     opus_fft_free(st);
592     return NULL;
593 }
594
595 kiss_fft_state *opus_fft_alloc(int nfft,void * mem,size_t * lenmem )
596 {
597    return opus_fft_alloc_twiddles(nfft, mem, lenmem, NULL);
598 }
599
600 void opus_fft_free(const kiss_fft_state *cfg)
601 {
602    if (cfg)
603    {
604       opus_free((opus_int16*)cfg->bitrev);
605       if (cfg->shift < 0)
606          opus_free((kiss_twiddle_cpx*)cfg->twiddles);
607       opus_free((kiss_fft_state*)cfg);
608    }
609 }
610
611 #endif /* CUSTOM_MODES */
612
613 void opus_fft(const kiss_fft_state *st,const kiss_fft_cpx *fin,kiss_fft_cpx *fout)
614 {
615     int m2, m;
616     int p;
617     int L;
618     int fstride[MAXFACTORS];
619     int i;
620     int shift;
621
622     /* st->shift can be -1 */
623     shift = st->shift>0 ? st->shift : 0;
624
625     celt_assert2 (fin != fout, "In-place FFT not supported");
626     /* Bit-reverse the input */
627     for (i=0;i<st->nfft;i++)
628     {
629        fout[st->bitrev[i]] = fin[i];
630 #ifndef FIXED_POINT
631        fout[st->bitrev[i]].r *= st->scale;
632        fout[st->bitrev[i]].i *= st->scale;
633 #endif
634     }
635
636     fstride[0] = 1;
637     L=0;
638     do {
639        p = st->factors[2*L];
640        m = st->factors[2*L+1];
641        fstride[L+1] = fstride[L]*p;
642        L++;
643     } while(m!=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    m = st->factors[2*L-1];
697    for (i=L-1;i>=0;i--)
698    {
699       if (i!=0)
700          m2 = st->factors[2*i-1];
701       else
702          m2 = 1;
703       switch (st->factors[2*i])
704       {
705       case 2:
706          ki_bfly2(fout,fstride[i]<<shift,st,m, fstride[i], m2);
707          break;
708       case 4:
709          ki_bfly4(fout,fstride[i]<<shift,st,m, fstride[i], m2);
710          break;
711 #ifndef RADIX_TWO_ONLY
712       case 3:
713          ki_bfly3(fout,fstride[i]<<shift,st,m, fstride[i], m2);
714          break;
715       case 5:
716          ki_bfly5(fout,fstride[i]<<shift,st,m, fstride[i], m2);
717          break;
718 #endif
719       }
720       m = m2;
721    }
722 }
723