Make celt_pitch_xcorr_edsp() work on ARMv5TE.
[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
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 = 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
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 = 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
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
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
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
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
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
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
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
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  * */
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
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
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
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
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