Removing (already broken) support for strides in kiss-fft
[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         const opus_int16 * factors,
439         const kiss_fft_state *st,
440         int N,
441         int m2
442         )
443 {
444     const int p=*factors++; /* the radix  */
445     const int m=*factors++; /* stage's fft length/p */
446     /*printf ("fft %d %d %d %d %d %d %d\n", p*m, m, p, s2, fstride*in_stride, N, m2);*/
447     if (m!=1)
448         kf_work( Fout , f, fstride*p, factors,st, N*p, m);
449
450     /* Compensate for longer twiddles table (when sharing) */
451     if (st->shift>0)
452        fstride <<= st->shift;
453     switch (p) {
454         case 2: kf_bfly2(Fout,fstride,st,m, N, m2); break;
455         case 4: kf_bfly4(Fout,fstride,st,m, N, m2); break;
456 #ifndef RADIX_TWO_ONLY
457         case 3: kf_bfly3(Fout,fstride,st,m, N, m2); break;
458         case 5: kf_bfly5(Fout,fstride,st,m, N, m2); break;
459 #endif
460     }
461 }
462
463 static void ki_work(
464              kiss_fft_cpx * Fout,
465              const kiss_fft_cpx * f,
466              size_t fstride,
467              const opus_int16 * factors,
468              const kiss_fft_state *st,
469              int N,
470              int m2
471             )
472 {
473    const int p=*factors++; /* the radix  */
474    const int m=*factors++; /* stage's fft length/p */
475    /*printf ("fft %d %d %d %d %d %d %d\n", p*m, m, p, s2, fstride*in_stride, N, m2);*/
476    if (m!=1)
477       ki_work( Fout , f, fstride*p, factors,st, N*p, m);
478
479    /* Compensate for longer twiddles table (when sharing) */
480    if (st->shift>0)
481       fstride <<= st->shift;
482    switch (p) {
483       case 2: ki_bfly2(Fout,fstride,st,m, N, m2); break;
484       case 4: ki_bfly4(Fout,fstride,st,m, N, m2); break;
485 #ifndef RADIX_TWO_ONLY
486       case 3: ki_bfly3(Fout,fstride,st,m, N, m2); break;
487       case 5: ki_bfly5(Fout,fstride,st,m, N, m2); break;
488 #endif
489    }
490 }
491
492 #ifdef CUSTOM_MODES
493
494 static
495 void compute_bitrev_table(
496          int Fout,
497          opus_int16 *f,
498          const size_t fstride,
499          int in_stride,
500          opus_int16 * factors,
501          const kiss_fft_state *st
502             )
503 {
504    const int p=*factors++; /* the radix  */
505    const int m=*factors++; /* stage's fft length/p */
506
507     /*printf ("fft %d %d %d %d %d %d\n", p*m, m, p, s2, fstride*in_stride, N);*/
508    if (m==1)
509    {
510       int j;
511       for (j=0;j<p;j++)
512       {
513          *f = Fout+j;
514          f += fstride*in_stride;
515       }
516    } else {
517       int j;
518       for (j=0;j<p;j++)
519       {
520          compute_bitrev_table( Fout , f, fstride*p, in_stride, factors,st);
521          f += fstride*in_stride;
522          Fout += m;
523       }
524    }
525 }
526
527 /*  facbuf is populated by p1,m1,p2,m2, ...
528     where
529     p[i] * m[i] = m[i-1]
530     m0 = n                  */
531 static
532 int kf_factor(int n,opus_int16 * facbuf)
533 {
534     int p=4;
535
536     /*factor out powers of 4, powers of 2, then any remaining primes */
537     do {
538         while (n % p) {
539             switch (p) {
540                 case 4: p = 2; break;
541                 case 2: p = 3; break;
542                 default: p += 2; break;
543             }
544             if (p>32000 || (opus_int32)p*(opus_int32)p > n)
545                 p = n;          /* no more factors, skip to end */
546         }
547         n /= p;
548 #ifdef RADIX_TWO_ONLY
549         if (p!=2 && p != 4)
550 #else
551         if (p>5)
552 #endif
553         {
554            return 0;
555         }
556         *facbuf++ = p;
557         *facbuf++ = n;
558     } while (n > 1);
559     return 1;
560 }
561
562 static void compute_twiddles(kiss_twiddle_cpx *twiddles, int nfft)
563 {
564    int i;
565 #ifdef FIXED_POINT
566    for (i=0;i<nfft;++i) {
567       opus_val32 phase = -i;
568       kf_cexp2(twiddles+i, DIV32(SHL32(phase,17),nfft));
569    }
570 #else
571    for (i=0;i<nfft;++i) {
572       const double pi=3.14159265358979323846264338327;
573       double phase = ( -2*pi /nfft ) * i;
574       kf_cexp(twiddles+i, phase );
575    }
576 #endif
577 }
578
579 /*
580  *
581  * User-callable function to allocate all necessary storage space for the fft.
582  *
583  * The return value is a contiguous block of memory, allocated with malloc.  As such,
584  * It can be freed with free(), rather than a kiss_fft-specific function.
585  * */
586 kiss_fft_state *kiss_fft_alloc_twiddles(int nfft,void * mem,size_t * lenmem,  const kiss_fft_state *base)
587 {
588     kiss_fft_state *st=NULL;
589     size_t memneeded = sizeof(struct kiss_fft_state); /* twiddle factors*/
590
591     if ( lenmem==NULL ) {
592         st = ( kiss_fft_state*)KISS_FFT_MALLOC( memneeded );
593     }else{
594         if (mem != NULL && *lenmem >= memneeded)
595             st = (kiss_fft_state*)mem;
596         *lenmem = memneeded;
597     }
598     if (st) {
599         opus_int16 *bitrev;
600         kiss_twiddle_cpx *twiddles;
601
602         st->nfft=nfft;
603 #ifndef FIXED_POINT
604         st->scale = 1./nfft;
605 #endif
606         if (base != NULL)
607         {
608            st->twiddles = base->twiddles;
609            st->shift = 0;
610            while (nfft<<st->shift != base->nfft && st->shift < 32)
611               st->shift++;
612            if (st->shift>=32)
613               goto fail;
614         } else {
615            st->twiddles = twiddles = (kiss_twiddle_cpx*)KISS_FFT_MALLOC(sizeof(kiss_twiddle_cpx)*nfft);
616            compute_twiddles(twiddles, nfft);
617            st->shift = -1;
618         }
619         if (!kf_factor(nfft,st->factors))
620         {
621            kiss_fft_free(st);
622            goto fail;
623         }
624
625         /* bitrev */
626         st->bitrev = bitrev = (opus_int16*)KISS_FFT_MALLOC(sizeof(opus_int16)*nfft);
627         if (st->bitrev==NULL)
628             goto fail;
629         compute_bitrev_table(0, bitrev, 1,1, st->factors,st);
630     }
631     return st;
632 fail:
633     kiss_fft_free(st);
634     return NULL;
635 }
636
637 kiss_fft_state *kiss_fft_alloc(int nfft,void * mem,size_t * lenmem )
638 {
639    return kiss_fft_alloc_twiddles(nfft, mem, lenmem, NULL);
640 }
641
642 void kiss_fft_free(const kiss_fft_state *cfg)
643 {
644    if (cfg)
645    {
646       celt_free((opus_int16*)cfg->bitrev);
647       if (cfg->shift < 0)
648          celt_free((kiss_twiddle_cpx*)cfg->twiddles);
649       celt_free((kiss_fft_state*)cfg);
650    }
651 }
652
653 #endif /* CUSTOM_MODES */
654
655 void kiss_fft(const kiss_fft_state *st,const kiss_fft_cpx *fin,kiss_fft_cpx *fout)
656 {
657     int i;
658     celt_assert2 (fin != fout, "In-place FFT not supported");
659     /* Bit-reverse the input */
660     for (i=0;i<st->nfft;i++)
661     {
662        fout[st->bitrev[i]] = fin[i];
663 #ifndef FIXED_POINT
664        fout[st->bitrev[i]].r *= st->scale;
665        fout[st->bitrev[i]].i *= st->scale;
666 #endif
667     }
668     kf_work( fout, fin, 1, st->factors,st, 1, 1);
669 }
670
671 void kiss_ifft(const kiss_fft_state *st,const kiss_fft_cpx *fin,kiss_fft_cpx *fout)
672 {
673    int i;
674    celt_assert2 (fin != fout, "In-place FFT not supported");
675    /* Bit-reverse the input */
676    for (i=0;i<st->nfft;i++)
677       fout[st->bitrev[i]] = fin[i];
678    ki_work( fout, fin, 1, st->factors,st, 1, 1);
679 }
680