🚀 go-pugleaf

In article <9520007@hpsad.HP.COM> toma@hpsad.HP.COM (Tom Anderson) writes:
>> ...does anyone have some C code laying around to do the 2D FFT that I
>> may obtain a copy of?
>
>    Please send it to me, too, or better yet, post!
>
>Tom Anderson    toma@hpsad.hp.com        "It's only hardware"
>Opinions expressed here are not HP's

Come on, guys. This is pretty trivial stuff. 

I don't have a proper shar utility, so here goes:

/* Simple 2D fft program.
 * This program assumes the existence of an in-place 1D FFT routine,
 * with the prototype
 * 	1D_fft(complex *data, int size)
 * 
 * size should be an integer power of 2.
 */
#include <stdio.h>
typedef struct {float re, im} complex;

main() {
	int i, j;
	complex image[y][x];
	complex temp[x]; /* Larger of x or y */

	read(fileno(stdin),image, sizeof(image));
	for (i = 0; i < y; i++)
		1D_fft(image[i], x);

	for (j = 0; j < x; j++) {
		for(i = 0; i < y; i++) temp[i] = image[i][j];
		1D_fft(temp, y);
		for(i = 0; i < y; i++) image[i][j] = temp[i];
	}
	write(fileno(stdout), image, sizeof(image));
}

And that's it. Since the 2D DFT is separable, it can be computed by taking
the 1D DFT of all of the rows, followed by a DFT of all of the columns.

Note: I wrote this program as an example. I haven't tested it for syntactic
correctness (I'm not sure if 1D_fft(image[i], x) will pass in the correct
pointer). For generality I'd declare image to be a pointer to pointer of
complex, and allocate a 2D array using malloc(). This gives you flexibility
on image size.

If you were looking for a true 2D FFT, I can't help you there.

Theo Smit (smit@enel.UCalgary.CA)