Fast Fourier Transform in C99

fft.c

#include <math.h>
#include "fft.h"

#ifndef M_PI
# define M_PI	3.14159265358979323846264338327950288
#endif

void fft(complex *v, int n, enum fft_direction sgn, complex *tmp)
{
	int k;
	complex z, w, w0, *vo, *ve;

	if (n <= 1)
		return;
	ve = tmp;
	vo = tmp + n / 2;
	for (k = 0; k < n/2; k++) {
		ve[k] = v[2*k];
		vo[k] = v[2*k + 1];
	}
	fft(ve, n/2, sgn, v);
	fft(vo, n/2, sgn, v);
	w0 = cexp(sgn*I * 2*M_PI / n);
	w = 1;
	for (k = 0; k < n/2; k++) {
		z = vo[k] * w;
		w *= w0;
		v[k] = ve[k] + z;
		v[k + n/2] = ve[k] - z;
	}
}

fft.h

#ifndef FFT_H

#include <complex.h>

enum fft_direction { FFT_FORWARD = -1, FFT_BACKWARD = 1 };

extern void fft(complex *, int, enum fft_direction, complex *);

#endif /* FFT_H */