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
48static 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
81static 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
112static 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
159static 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
206static 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
258static 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
308static 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
377static 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
450static
451void 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                  */
487static
488int 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
518static 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 * */
541kiss_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;
586fail:
587    opus_fft_free(st);
588    return NULL;
589}
590
591kiss_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
596void 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
609void 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
668void 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
720