/*---------------------------------------------------------------------------- 
 * 
 * NAME 
 *      fft2  - A two dimensional FFT subroutine. 
 * 
 * USAGE 
 *      fft2 (n, array, dir) 
 *          int n, dir; 
 *          COMPLEX *array[]; 
 * 
 * EXPLICIT INPUTS 
 *      n:              the square dimension of the array 
 *      array:          a table of pointers to the array rows 
 *      dir:            1 for forward transform 
 *                      -1 for inverse transform 
 * 
 * IMPLICIT INPUTS 
 *      None. 
 * 
 * EXPLICIT OUTPUTS 
 *      None. 
 * 
 * IMPLICIT OUTPUTS 
 *         The contents of the array are changed from the input data to the 
 *      FFT coefficients. 
 * 
 * PROCEDURE 
 *         Performs row transforms and then column transforms. 
 * 
 * HISTORY 
 * 16-Nov-82  John Schlag (jfs) at Carnegie-Mellon University 
 *      Hacked O'Gorman's code to make it independent of Unix. 
 * 
 *---------------------------------------------------------------------------- 
 */ 
 
#include "window.h" 
#include "bblib.h" 
 
int 
fft2 (int n, COMPLEX *array[], int dir) 
/*  n      : image sidelength    */ 
/*  array  : pointers to rows of complex array  */ 
/*  dir    : transform direction   */ 
{ 
    register int      i, j;   /* temporary variables */ 
    double    *rvec,  /* scratch real vector */ 
              *ivec;  /* scratch imaginary vector */ 
 
    rvec = malloc(sizeof(double) * n); 
    if (rvec == NULL) return ERR_ALLOC; 
    ivec = malloc(sizeof(double) * n); 
    if (ivec == NULL) 
    { 
 free(rvec); 
 return ERR_ALLOC; 
    } 
 
    /* Perform the row FFTs. */ 
 
    for (i = 0; i < n; i++) 
    { 
        /* Stuff the temporary row vectors. */ 
 
        for (j = 0; j < n; j++) 
        { 
            rvec[j] = array[i][j].real; 
            ivec[j] = array[i][j].imag; 
        } 
 
        /* Run a single row FFT. */ 
 
        fft1 (n, rvec, ivec, dir); 
 
        /* Unpack the results. */ 
 
        for (j = 0; j < n; j++) 
        { 
            array[i][j].real = rvec[j]; 
            array[i][j].imag = ivec[j]; 
        } 
 update_meter(); 
    } 
    /* Perform the column FFTs. */ 
 
    for (i = 0; i < n; i++) 
    { 
    /* Stuff the temporary column vectors. */ 
 
        for (j = 0; j < n; j++) 
        { 
            rvec[j] = array[j][i].real;         /* Transpose. */ 
            ivec[j] = array[j][i].imag; 
        } 
 
        /* Run a single column FFT. */ 
 
        fft1 (n, rvec, ivec, dir); 
 
        /* Unpack the results. */ 
 
        for (j = 0; j < n; j++) 
        { 
            array[j][i].real = rvec[j]; 
            array[j][i].imag = ivec[j]; 
        } 
 update_meter(); 
    } 
 
    free(rvec); 
    free(ivec); 
 
    return NO_ERROR; 
} 
