198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project/* 298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source ProjectCopyright (c) 2003-2004, Mark Borgerding 398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source ProjectCopyright (c) 2005-2007, Jean-Marc Valin 498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source ProjectAll rights reserved. 698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source ProjectRedistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: 898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project * Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. 1098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project * 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. 1198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project * Neither the author nor the names of any contributors may be used to endorse or promote products derived from this software without specific prior written permission. 1298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 1398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source ProjectTHIS 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. 1498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project*/ 1598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 1698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 1798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#ifdef HAVE_CONFIG_H 1898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#include "config.h" 1998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#endif 2098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 2198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#include "_kiss_fft_guts.h" 2298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#include "arch.h" 2398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#include "os_support.h" 2498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 2598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project/* The guts header contains all the multiplication and addition macros that are defined for 2698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project fixed or floating point complex numbers. It also delares the kf_ internal functions. 2798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project */ 2898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 2998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Projectstatic void kf_bfly2( 3098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kiss_fft_cpx * Fout, 3198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project const size_t fstride, 3298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project const kiss_fft_cfg st, 3398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project int m, 3498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project int N, 3598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project int mm 3698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project ) 3798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project{ 3898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kiss_fft_cpx * Fout2; 3998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kiss_fft_cpx * tw1; 4098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kiss_fft_cpx t; 4198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project if (!st->inverse) { 4298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project int i,j; 4398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kiss_fft_cpx * Fout_beg = Fout; 4498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project for (i=0;i<N;i++) 4598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project { 4698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout = Fout_beg + i*mm; 4798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout2 = Fout + m; 4898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project tw1 = st->twiddles; 4998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project for(j=0;j<m;j++) 5098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project { 5198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project /* Almost the same as the code path below, except that we divide the input by two 5298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project (while keeping the best accuracy possible) */ 5398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project spx_word32_t tr, ti; 5498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project tr = SHR32(SUB32(MULT16_16(Fout2->r , tw1->r),MULT16_16(Fout2->i , tw1->i)), 1); 5598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project ti = SHR32(ADD32(MULT16_16(Fout2->i , tw1->r),MULT16_16(Fout2->r , tw1->i)), 1); 5698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project tw1 += fstride; 5798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout2->r = PSHR32(SUB32(SHL32(EXTEND32(Fout->r), 14), tr), 15); 5898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout2->i = PSHR32(SUB32(SHL32(EXTEND32(Fout->i), 14), ti), 15); 5998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout->r = PSHR32(ADD32(SHL32(EXTEND32(Fout->r), 14), tr), 15); 6098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout->i = PSHR32(ADD32(SHL32(EXTEND32(Fout->i), 14), ti), 15); 6198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project ++Fout2; 6298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project ++Fout; 6398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } 6498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } 6598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } else { 6698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project int i,j; 6798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kiss_fft_cpx * Fout_beg = Fout; 6898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project for (i=0;i<N;i++) 6998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project { 7098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout = Fout_beg + i*mm; 7198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout2 = Fout + m; 7298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project tw1 = st->twiddles; 7398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project for(j=0;j<m;j++) 7498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project { 7598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_MUL (t, *Fout2 , *tw1); 7698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project tw1 += fstride; 7798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_SUB( *Fout2 , *Fout , t ); 7898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_ADDTO( *Fout , t ); 7998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project ++Fout2; 8098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project ++Fout; 8198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } 8298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } 8398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } 8498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project} 8598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 8698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Projectstatic void kf_bfly4( 8798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kiss_fft_cpx * Fout, 8898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project const size_t fstride, 8998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project const kiss_fft_cfg st, 9098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project int m, 9198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project int N, 9298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project int mm 9398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project ) 9498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project{ 9598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kiss_fft_cpx *tw1,*tw2,*tw3; 9698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kiss_fft_cpx scratch[6]; 9798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project const size_t m2=2*m; 9898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project const size_t m3=3*m; 9998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project int i, j; 10098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 10198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project if (st->inverse) 10298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project { 10398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kiss_fft_cpx * Fout_beg = Fout; 10498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project for (i=0;i<N;i++) 10598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project { 10698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout = Fout_beg + i*mm; 10798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project tw3 = tw2 = tw1 = st->twiddles; 10898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project for (j=0;j<m;j++) 10998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project { 11098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_MUL(scratch[0],Fout[m] , *tw1 ); 11198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_MUL(scratch[1],Fout[m2] , *tw2 ); 11298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_MUL(scratch[2],Fout[m3] , *tw3 ); 11398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 11498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_SUB( scratch[5] , *Fout, scratch[1] ); 11598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_ADDTO(*Fout, scratch[1]); 11698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_ADD( scratch[3] , scratch[0] , scratch[2] ); 11798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_SUB( scratch[4] , scratch[0] , scratch[2] ); 11898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_SUB( Fout[m2], *Fout, scratch[3] ); 11998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project tw1 += fstride; 12098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project tw2 += fstride*2; 12198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project tw3 += fstride*3; 12298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_ADDTO( *Fout , scratch[3] ); 12398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 12498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout[m].r = scratch[5].r - scratch[4].i; 12598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout[m].i = scratch[5].i + scratch[4].r; 12698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout[m3].r = scratch[5].r + scratch[4].i; 12798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout[m3].i = scratch[5].i - scratch[4].r; 12898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project ++Fout; 12998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } 13098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } 13198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } else 13298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project { 13398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kiss_fft_cpx * Fout_beg = Fout; 13498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project for (i=0;i<N;i++) 13598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project { 13698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout = Fout_beg + i*mm; 13798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project tw3 = tw2 = tw1 = st->twiddles; 13898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project for (j=0;j<m;j++) 13998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project { 14098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_MUL4(scratch[0],Fout[m] , *tw1 ); 14198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_MUL4(scratch[1],Fout[m2] , *tw2 ); 14298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_MUL4(scratch[2],Fout[m3] , *tw3 ); 14398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 14498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout->r = PSHR16(Fout->r, 2); 14598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout->i = PSHR16(Fout->i, 2); 14698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_SUB( scratch[5] , *Fout, scratch[1] ); 14798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_ADDTO(*Fout, scratch[1]); 14898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_ADD( scratch[3] , scratch[0] , scratch[2] ); 14998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_SUB( scratch[4] , scratch[0] , scratch[2] ); 15098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout[m2].r = PSHR16(Fout[m2].r, 2); 15198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout[m2].i = PSHR16(Fout[m2].i, 2); 15298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_SUB( Fout[m2], *Fout, scratch[3] ); 15398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project tw1 += fstride; 15498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project tw2 += fstride*2; 15598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project tw3 += fstride*3; 15698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_ADDTO( *Fout , scratch[3] ); 15798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 15898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout[m].r = scratch[5].r + scratch[4].i; 15998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout[m].i = scratch[5].i - scratch[4].r; 16098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout[m3].r = scratch[5].r - scratch[4].i; 16198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout[m3].i = scratch[5].i + scratch[4].r; 16298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project ++Fout; 16398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } 16498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } 16598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } 16698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project} 16798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 16898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Projectstatic void kf_bfly3( 16998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kiss_fft_cpx * Fout, 17098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project const size_t fstride, 17198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project const kiss_fft_cfg st, 17298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project size_t m 17398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project ) 17498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project{ 17598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project size_t k=m; 17698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project const size_t m2 = 2*m; 17798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kiss_fft_cpx *tw1,*tw2; 17898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kiss_fft_cpx scratch[5]; 17998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kiss_fft_cpx epi3; 18098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project epi3 = st->twiddles[fstride*m]; 18198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 18298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project tw1=tw2=st->twiddles; 18398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 18498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project do{ 18598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project if (!st->inverse) { 18698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_FIXDIV(*Fout,3); C_FIXDIV(Fout[m],3); C_FIXDIV(Fout[m2],3); 18798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } 18898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 18998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_MUL(scratch[1],Fout[m] , *tw1); 19098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_MUL(scratch[2],Fout[m2] , *tw2); 19198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 19298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_ADD(scratch[3],scratch[1],scratch[2]); 19398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_SUB(scratch[0],scratch[1],scratch[2]); 19498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project tw1 += fstride; 19598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project tw2 += fstride*2; 19698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 19798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout[m].r = Fout->r - HALF_OF(scratch[3].r); 19898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout[m].i = Fout->i - HALF_OF(scratch[3].i); 19998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 20098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_MULBYSCALAR( scratch[0] , epi3.i ); 20198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 20298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_ADDTO(*Fout,scratch[3]); 20398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 20498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout[m2].r = Fout[m].r + scratch[0].i; 20598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout[m2].i = Fout[m].i - scratch[0].r; 20698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 20798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout[m].r -= scratch[0].i; 20898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout[m].i += scratch[0].r; 20998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 21098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project ++Fout; 21198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project }while(--k); 21298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project} 21398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 21498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Projectstatic void kf_bfly5( 21598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kiss_fft_cpx * Fout, 21698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project const size_t fstride, 21798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project const kiss_fft_cfg st, 21898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project int m 21998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project ) 22098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project{ 22198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kiss_fft_cpx *Fout0,*Fout1,*Fout2,*Fout3,*Fout4; 22298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project int u; 22398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kiss_fft_cpx scratch[13]; 22498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kiss_fft_cpx * twiddles = st->twiddles; 22598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kiss_fft_cpx *tw; 22698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kiss_fft_cpx ya,yb; 22798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project ya = twiddles[fstride*m]; 22898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project yb = twiddles[fstride*2*m]; 22998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 23098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout0=Fout; 23198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout1=Fout0+m; 23298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout2=Fout0+2*m; 23398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout3=Fout0+3*m; 23498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout4=Fout0+4*m; 23598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 23698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project tw=st->twiddles; 23798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project for ( u=0; u<m; ++u ) { 23898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project if (!st->inverse) { 23998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_FIXDIV( *Fout0,5); C_FIXDIV( *Fout1,5); C_FIXDIV( *Fout2,5); C_FIXDIV( *Fout3,5); C_FIXDIV( *Fout4,5); 24098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } 24198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project scratch[0] = *Fout0; 24298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 24398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_MUL(scratch[1] ,*Fout1, tw[u*fstride]); 24498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_MUL(scratch[2] ,*Fout2, tw[2*u*fstride]); 24598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_MUL(scratch[3] ,*Fout3, tw[3*u*fstride]); 24698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_MUL(scratch[4] ,*Fout4, tw[4*u*fstride]); 24798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 24898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_ADD( scratch[7],scratch[1],scratch[4]); 24998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_SUB( scratch[10],scratch[1],scratch[4]); 25098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_ADD( scratch[8],scratch[2],scratch[3]); 25198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_SUB( scratch[9],scratch[2],scratch[3]); 25298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 25398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout0->r += scratch[7].r + scratch[8].r; 25498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout0->i += scratch[7].i + scratch[8].i; 25598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 25698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project scratch[5].r = scratch[0].r + S_MUL(scratch[7].r,ya.r) + S_MUL(scratch[8].r,yb.r); 25798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project scratch[5].i = scratch[0].i + S_MUL(scratch[7].i,ya.r) + S_MUL(scratch[8].i,yb.r); 25898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 25998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project scratch[6].r = S_MUL(scratch[10].i,ya.i) + S_MUL(scratch[9].i,yb.i); 26098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project scratch[6].i = -S_MUL(scratch[10].r,ya.i) - S_MUL(scratch[9].r,yb.i); 26198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 26298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_SUB(*Fout1,scratch[5],scratch[6]); 26398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_ADD(*Fout4,scratch[5],scratch[6]); 26498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 26598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project scratch[11].r = scratch[0].r + S_MUL(scratch[7].r,yb.r) + S_MUL(scratch[8].r,ya.r); 26698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project scratch[11].i = scratch[0].i + S_MUL(scratch[7].i,yb.r) + S_MUL(scratch[8].i,ya.r); 26798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project scratch[12].r = - S_MUL(scratch[10].i,yb.i) + S_MUL(scratch[9].i,ya.i); 26898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project scratch[12].i = S_MUL(scratch[10].r,yb.i) - S_MUL(scratch[9].r,ya.i); 26998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 27098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_ADD(*Fout2,scratch[11],scratch[12]); 27198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_SUB(*Fout3,scratch[11],scratch[12]); 27298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 27398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project ++Fout0;++Fout1;++Fout2;++Fout3;++Fout4; 27498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } 27598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project} 27698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 27798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project/* perform the butterfly for one stage of a mixed radix FFT */ 27898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Projectstatic void kf_bfly_generic( 27998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kiss_fft_cpx * Fout, 28098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project const size_t fstride, 28198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project const kiss_fft_cfg st, 28298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project int m, 28398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project int p 28498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project ) 28598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project{ 28698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project int u,k,q1,q; 28798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kiss_fft_cpx * twiddles = st->twiddles; 28898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kiss_fft_cpx t; 28998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kiss_fft_cpx scratchbuf[17]; 29098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project int Norig = st->nfft; 29198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 29298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project /*CHECKBUF(scratchbuf,nscratchbuf,p);*/ 29398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project if (p>17) 29498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project speex_fatal("KissFFT: max radix supported is 17"); 29598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 29698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project for ( u=0; u<m; ++u ) { 29798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project k=u; 29898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project for ( q1=0 ; q1<p ; ++q1 ) { 29998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project scratchbuf[q1] = Fout[ k ]; 30098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project if (!st->inverse) { 30198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_FIXDIV(scratchbuf[q1],p); 30298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } 30398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project k += m; 30498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } 30598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 30698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project k=u; 30798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project for ( q1=0 ; q1<p ; ++q1 ) { 30898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project int twidx=0; 30998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout[ k ] = scratchbuf[0]; 31098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project for (q=1;q<p;++q ) { 31198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project twidx += fstride * k; 31298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project if (twidx>=Norig) twidx-=Norig; 31398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_MUL(t,scratchbuf[q] , twiddles[twidx] ); 31498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_ADDTO( Fout[ k ] ,t); 31598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } 31698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project k += m; 31798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } 31898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } 31998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project} 32098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 32198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Projectstatic 32298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Projectvoid kf_shuffle( 32398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kiss_fft_cpx * Fout, 32498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project const kiss_fft_cpx * f, 32598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project const size_t fstride, 32698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project int in_stride, 32798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project int * factors, 32898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project const kiss_fft_cfg st 32998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project ) 33098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project{ 33198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project const int p=*factors++; /* the radix */ 33298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project const int m=*factors++; /* stage's fft length/p */ 33398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 33498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project /*printf ("fft %d %d %d %d %d %d\n", p*m, m, p, s2, fstride*in_stride, N);*/ 33598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project if (m==1) 33698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project { 33798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project int j; 33898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project for (j=0;j<p;j++) 33998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project { 34098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout[j] = *f; 34198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project f += fstride*in_stride; 34298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } 34398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } else { 34498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project int j; 34598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project for (j=0;j<p;j++) 34698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project { 34798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kf_shuffle( Fout , f, fstride*p, in_stride, factors,st); 34898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project f += fstride*in_stride; 34998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout += m; 35098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } 35198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } 35298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project} 35398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 35498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Projectstatic 35598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Projectvoid kf_work( 35698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kiss_fft_cpx * Fout, 35798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project const kiss_fft_cpx * f, 35898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project const size_t fstride, 35998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project int in_stride, 36098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project int * factors, 36198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project const kiss_fft_cfg st, 36298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project int N, 36398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project int s2, 36498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project int m2 36598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project ) 36698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project{ 36798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project int i; 36898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kiss_fft_cpx * Fout_beg=Fout; 36998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project const int p=*factors++; /* the radix */ 37098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project const int m=*factors++; /* stage's fft length/p */ 37198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#if 0 37298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project /*printf ("fft %d %d %d %d %d %d\n", p*m, m, p, s2, fstride*in_stride, N);*/ 37398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project if (m==1) 37498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project { 37598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project /* int j; 37698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project for (j=0;j<p;j++) 37798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project { 37898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout[j] = *f; 37998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project f += fstride*in_stride; 38098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project }*/ 38198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } else { 38298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project int j; 38398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project for (j=0;j<p;j++) 38498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project { 38598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kf_work( Fout , f, fstride*p, in_stride, factors,st, N*p, fstride*in_stride, m); 38698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project f += fstride*in_stride; 38798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout += m; 38898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } 38998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } 39098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 39198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout=Fout_beg; 39298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 39398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project switch (p) { 39498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project case 2: kf_bfly2(Fout,fstride,st,m); break; 39598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project case 3: kf_bfly3(Fout,fstride,st,m); break; 39698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project case 4: kf_bfly4(Fout,fstride,st,m); break; 39798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project case 5: kf_bfly5(Fout,fstride,st,m); break; 39898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project default: kf_bfly_generic(Fout,fstride,st,m,p); break; 39998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } 40098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#else 40198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project /*printf ("fft %d %d %d %d %d %d %d\n", p*m, m, p, s2, fstride*in_stride, N, m2);*/ 40298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project if (m==1) 40398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project { 40498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project /*for (i=0;i<N;i++) 40598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project { 40698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project int j; 40798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Fout = Fout_beg+i*m2; 40898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project const kiss_fft_cpx * f2 = f+i*s2; 40998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project for (j=0;j<p;j++) 41098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project { 41198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project *Fout++ = *f2; 41298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project f2 += fstride*in_stride; 41398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } 41498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project }*/ 41598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project }else{ 41698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kf_work( Fout , f, fstride*p, in_stride, factors,st, N*p, fstride*in_stride, m); 41798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } 41898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 41998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 42098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 42198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 42298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project switch (p) { 42398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project case 2: kf_bfly2(Fout,fstride,st,m, N, m2); break; 42498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project case 3: for (i=0;i<N;i++){Fout=Fout_beg+i*m2; kf_bfly3(Fout,fstride,st,m);} break; 42598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project case 4: kf_bfly4(Fout,fstride,st,m, N, m2); break; 42698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project case 5: for (i=0;i<N;i++){Fout=Fout_beg+i*m2; kf_bfly5(Fout,fstride,st,m);} break; 42798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project default: for (i=0;i<N;i++){Fout=Fout_beg+i*m2; kf_bfly_generic(Fout,fstride,st,m,p);} break; 42898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } 42998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#endif 43098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project} 43198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 43298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project/* facbuf is populated by p1,m1,p2,m2, ... 43398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project where 43498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project p[i] * m[i] = m[i-1] 43598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project m0 = n */ 43698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Projectstatic 43798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Projectvoid kf_factor(int n,int * facbuf) 43898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project{ 43998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project int p=4; 44098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 44198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project /*factor out powers of 4, powers of 2, then any remaining primes */ 44298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project do { 44398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project while (n % p) { 44498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project switch (p) { 44598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project case 4: p = 2; break; 44698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project case 2: p = 3; break; 44798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project default: p += 2; break; 44898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } 44998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project if (p>32000 || (spx_int32_t)p*(spx_int32_t)p > n) 45098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project p = n; /* no more factors, skip to end */ 45198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } 45298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project n /= p; 45398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project *facbuf++ = p; 45498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project *facbuf++ = n; 45598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } while (n > 1); 45698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project} 45798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project/* 45898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project * 45998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project * User-callable function to allocate all necessary storage space for the fft. 46098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project * 46198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project * The return value is a contiguous block of memory, allocated with malloc. As such, 46298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project * It can be freed with free(), rather than a kiss_fft-specific function. 46398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project * */ 46498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Projectkiss_fft_cfg kiss_fft_alloc(int nfft,int inverse_fft,void * mem,size_t * lenmem ) 46598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project{ 46698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kiss_fft_cfg st=NULL; 46798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project size_t memneeded = sizeof(struct kiss_fft_state) 46898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project + sizeof(kiss_fft_cpx)*(nfft-1); /* twiddle factors*/ 46998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 47098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project if ( lenmem==NULL ) { 47198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project st = ( kiss_fft_cfg)KISS_FFT_MALLOC( memneeded ); 47298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project }else{ 47398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project if (mem != NULL && *lenmem >= memneeded) 47498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project st = (kiss_fft_cfg)mem; 47598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project *lenmem = memneeded; 47698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } 47798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project if (st) { 47898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project int i; 47998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project st->nfft=nfft; 48098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project st->inverse = inverse_fft; 48198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#ifdef FIXED_POINT 48298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project for (i=0;i<nfft;++i) { 48398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project spx_word32_t phase = i; 48498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project if (!st->inverse) 48598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project phase = -phase; 48698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kf_cexp2(st->twiddles+i, DIV32(SHL32(phase,17),nfft)); 48798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } 48898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#else 48998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project for (i=0;i<nfft;++i) { 49098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project const double pi=3.14159265358979323846264338327; 49198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project double phase = ( -2*pi /nfft ) * i; 49298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project if (st->inverse) 49398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project phase *= -1; 49498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kf_cexp(st->twiddles+i, phase ); 49598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } 49698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#endif 49798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kf_factor(nfft,st->factors); 49898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } 49998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project return st; 50098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project} 50198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 50298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 50398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 50498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 50598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Projectvoid kiss_fft_stride(kiss_fft_cfg st,const kiss_fft_cpx *fin,kiss_fft_cpx *fout,int in_stride) 50698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project{ 50798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project if (fin == fout) 50898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project { 50998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project speex_fatal("In-place FFT not supported"); 51098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project /*CHECKBUF(tmpbuf,ntmpbuf,st->nfft); 51198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kf_work(tmpbuf,fin,1,in_stride, st->factors,st); 51298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project SPEEX_MOVE(fout,tmpbuf,st->nfft);*/ 51398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } else { 51498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kf_shuffle( fout, fin, 1,in_stride, st->factors,st); 51598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kf_work( fout, fin, 1,in_stride, st->factors,st, 1, in_stride, 1); 51698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project } 51798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project} 51898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 51998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Projectvoid kiss_fft(kiss_fft_cfg cfg,const kiss_fft_cpx *fin,kiss_fft_cpx *fout) 52098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project{ 52198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kiss_fft_stride(cfg,fin,fout,1); 52298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project} 52398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 524