#define FFT_N 128
#define PI 3.14159
struct compx {
float real,imag;
};
struct compx s[FFT_N];
float SIN_TAB[FFT_N/4+1];
struct compx EE(struct compx a,struct compx b)
{
struct compx c;
c.real=a.real*b.real-a.imag*b.imag;
c.imag=a.real*b.imag+a.imag*b.real;
return(c);
}
void create_sin_tab(float *sin_t)
{
int i;
for(i=0;i<=FFT_N/4;i++)
sin_t[i]=sin(2*PI*i/FFT_N);
}
float sin_tab(float pi)
{
int n;
float a;
n=(int)(pi*FFT_N/2/PI);
if(n>=0&&n<=FFT_N/4)
a=SIN_TAB[n];
else if(n>FFT_N/4&&n<FFT_N/2)
{
n-=FFT_N/4;
a=SIN_TAB[FFT_N/4-n];
}
else if(n>=FFT_N/2&&n<3*FFT_N/4)
{
n-=FFT_N/2;
a=-SIN_TAB[n];
}
else if(n>=3*FFT_N/4&&n<3*FFT_N)
{
n=FFT_N-n;
a=-SIN_TAB[n];
}
return a;
}
float cos_tab(float pi)
{
float a,pi2;
pi2=pi+PI/2;
if(pi2>2*PI)
pi2-=2*PI;
a=sin_tab(pi2);
return a;
}
void FFT(struct compx *xin){
int f,m,nv2,nm1,i,k,l,j=0;
struct compx u,w,t;
nv2=FFT_N/2;
nm1=FFT_N-1;
for(i=0;i<nm1;i++)
{
if(i<j)
{
t=xin[j];
xin[j]=xin[i];
xin[i]=t;
}
k=nv2;
while(k<=j)
{
j=j-k;
k=k/2;
}
j=j+k;
}
{
int le,lei,ip;
f=FFT_N;
for(l=1;(f=f/2)!=1;l++)
;
for(m=1;m<=l;m++)
{
le=2<<(m-1);
lei=le/2;
u.real=1.0;
u.imag=0.0;
w.real=cos_tab(PI/lei); // n / PI
w.imag=-sin_tab(PI/lei);
for(j=0;j<=lei-1;j++)
{
for(i=j;i<=FFT_N-1;i=i+le)
{
ip=i+lei;
t=EE(xin[ip],u);
xin[ip].real=xin[i].real-t.real;
xin[ip].imag=xin[i].imag-t.imag;
xin[i].real=xin[i].real+t.real;
xin[i].imag=xin[i].imag+t.imag;
}
u=EE(u,w);
}
}
}
}
void main()
{
int i;
create_sin_tab(SIN_TAB);
for(i=0;i<FFT_N;i++)
{
s[i].real=sin(2*3.141592653589793*i/FFT_N);
s[i].imag=0;
}
FFT(s);
for(i=0;i<FFT_N;i++)
s[i].real=sqrt(s[i].real*s[i].real+s[i].imag*s[i].imag);
while(1);
}
