#include <math.h>
#define PI 3.141592653589793238462643
#define NFFT 256
void fft(short *x)
{
static short once=1, sint[3 * NFFT / 4];
int n1, n2, ie, i, j, k, xt, yt;
short *xi, *xl, *sinus;
if (once)
{
for (i=0; i < 3*NFFT/4; i++) /* sine table */
sint[i] = 0x7FFF * sin(2 * PI * i / NFFT);
once = 0;
}
for (n2=NFFT, ie=1; ie<NFFT; ie=ie<<1)
{
n1 = n2;
n2 = n2 >> 1;
sinus = sint;
for (j=0; j < n2; j++)
{
for (i=j<<1; i < 2*NFFT; i+=n1<<1)
{
xi = x + i;
xl = xi + n1;
xt = (xi[0] - xl[0]) >> 1;
yt = (xi[1] - xl[1]) >> 1;
*(int*)xi = (((xi[0] + xl[0]) << 15) & 0xFFFF0000) | (unsigned short)((xi[1] + xl[1]) >> 1);
*(int*)xl = (((xt * sinus[NFFT/4] + yt * sinus[0]) << 1) & 0xFFFF0000) | (unsigned short)((yt * sinus[NFFT/4] - xt * sinus[0]) >> 15);
}
sinus = sinus + ie;
}
}
for (j=i=0; i < 2*NFFT; i+=2) /* bit reverse */
{
if (i < j)
{
ie = *(int*)(x+i);
*(int*)(x+i) = *(int*)(x+j);
*(int*)(x+j) = ie;
}
k = NFFT;
while (j >= k)
{
j -= k;
k = k >> 1;
}
j += k;
}
}