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