kube-gustavson-fft.cpp File Reference

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include "kube-gustavson-fft.hpp"

Include dependency graph for kube-gustavson-fft.cpp:

base refererrect $kube-gustavson-fft_8hpp.html 378,150 519,174

Go to the source code of this file.

Defines

#define LoadRow(buffer, row, cols)

#define StoreRow(buffer, row, cols)

#define LoadCol(buffer, col, rows, cols)

#define StoreCol(buffer, col, rows, cols)

#define handle_error(msg) fprintf(stderr,msg)

Functions

int allocateBuffer (int size)

void freeBuffer (void)

int power_of_2 (int n)

int fastlog2 (int n)

void R2TX (int nthpo, DCOMPLEX *c0, DCOMPLEX *c1)

void R4TX (int nthpo, DCOMPLEX *c0, DCOMPLEX *c1, DCOMPLEX *c2, DCOMPLEX *c3)

void R8TX (int nxtlt, int nthpo, int length, DCOMPLEX *cc0, DCOMPLEX *cc1, DCOMPLEX *cc2, DCOMPLEX *cc3, DCOMPLEX *cc4, DCOMPLEX *cc5, DCOMPLEX *cc6, DCOMPLEX *cc7)

void FFT842 (int direction, int n, DCOMPLEX *b)

int fft2f (COMPLEX *array, int rows, int cols, int direction)

int fft2d (DCOMPLEX *array, int rows, int cols, int direction)

int forward_fft2f (COMPLEX *array, int rows, int cols)

int inverse_fft2f (COMPLEX *array, int rows, int cols)

int forward_fft2d (DCOMPLEX *array, int rows, int cols)

int inverse_fft2d (DCOMPLEX *array, int rows, int cols)

Variables

DCOMPLEX * stageBuff

COMPLEX * bigBuff

DCOMPLEX * bigBuffd

Define Documentation

#define handle_error ( msg ) fprintf(stderr,msg)

Definition at line 112 of file kube-gustavson-fft.cpp.

Referenced by allocateBuffer(), fft2d(), and fft2f().

#define LoadCol	(	buffer,
		col,
		rows,
		cols	)

Value:

if (1){\
    register int j,k;\
    for (j = i,k = 0 ; k < rows ; j+=cols, k++){\
        stageBuff[k].re = buffer[j].re;\
        stageBuff[k].im = buffer[j].im;\
        }\
    } else {}

Definition at line 94 of file kube-gustavson-fft.cpp.

Referenced by fft2d(), and fft2f().

#define LoadRow	(	buffer,
		row,
		cols	)

Value:

if (1){\
    register int j,k;\
    for (j = row*cols, k = 0 ; k < cols ; j++, k++){\
        stageBuff[k].re = buffer[j].re;\
          stageBuff[k].im = buffer[j].im;\
        }\
    } else {}

************************************************************* kube-gustavson-fft.c

Forward and inverse discrete 2D Fourier transforms.

Originally a FORTRAN implementation published in: Programming for Digital Signal Processing, IEEE Press 1979, Section 1, by G. D. Bergland and M. T. Dolan. Ported long ago from Fortran to old-fashioned Standard C by someone who failed to put his or her name in the source. Ported from Standard C to ANSI C by Stefan Gustavson (stegu@itn.liu.se) 2003-10-20.

This is a pretty fast FFT algorithm. Not super-optimized lightning-fast, but very good considering its age and relative simplicity. There are several places in the code where clock cycles could be saved, for example by getting rid of some copying of data back and forth, but the savings would not be that great. If you want optimally fast FFTs, consider the excellent FFTW package. (http://www.fftw.org)

This software is in the public domain.

int forward_fft2f(COMPLEX *array, int rows, int cols) int inverse_fft2f(COMPLEX *array, int rows, int cols) int forward_fft2d(DCOMPLEX *array, int rows, int cols) int inverse_fft2d(DCOMPLEX *array, int rows, int cols)

These functions compute the forward and inverse DFT's, respectively, of a single-precision COMPLEX or DCOMPLEX array by means of an FFT algorithm.

The result is a COMPLEX/DCOMPLEX array of the same size, returned in the same space as the input array. That is, the original array is overwritten and destroyed.

Rows and columns must each be an integral power of 2.

These routines return integer value ERROR if an error was detected, NO_ERROR otherwise.

This particular implementation of the DFT uses the transform pair defined as follows: Let there be two complex arrays each with n rows and m columns. Index them as

$f(x,y): 0 <= x <= m - 1, 0 <= y <= n - 1$

$F(u,v): -m/2 <= u <= m/2 - 1, -n/2 <= v <= n/2 - 1$

Then the forward and inverse transforms are related as follows. Forward:

$F(u,v) = \sum_{x=0}^{m-1} \sum_{y=0}^{n-1} f(x,y) \exp{-2\pi i (ux/m + vy/n)}$

Inverse:

$f(x,y) = 1/(mn) \sum_{u=-m/2}^{m/2-1} \sum_{v=-n/2}^{n/2-1} F(u,v) \exp{2\pi i (ux/m + vy/n)}$

Therefore, the transforms have these properties: 1. $\sum_x \sum_y f(x,y) = F(0,0)$ 2. $m n \sum_x \sum_y |f(x,y)|^2 = \sum_u \sum_v |F(u,v)|^2$

These somewhat awkward macros move data between the input/output array and stageBuff, while also performing any conversions float<->double.

Definition at line 78 of file kube-gustavson-fft.cpp.

Referenced by fft2d(), and fft2f().

#define StoreCol	(	buffer,
		col,
		rows,
		cols	)

Value:

if (1){\
    register int j,k;\
    for (j = i,k = 0 ; k < rows ; j+=cols, k++){\
        buffer[j].re = stageBuff[k].re;\
        buffer[j].im = stageBuff[k].im;\
        }\
    } else {}

Definition at line 102 of file kube-gustavson-fft.cpp.

Referenced by fft2d(), and fft2f().

#define StoreRow	(	buffer,
		row,
		cols	)

Value:

if (1){\
    register int j,k;\
    for (j = row*cols, k = 0 ; k < cols ; j++, k++){\
        buffer[j].re = stageBuff[k].re;\
        buffer[j].im = stageBuff[k].im;\
        }\
    } else {}

Definition at line 86 of file kube-gustavson-fft.cpp.

Referenced by fft2d(), and fft2f().

Function Documentation

int allocateBuffer ( int size )

Allocate space for stageBuff

Definition at line 120 of file kube-gustavson-fft.cpp.

References ERROR, handle_error, and NO_ERROR.

Referenced by fft2d(), and fft2f().

int fastlog2 ( int n )

Get binary log of integer argument - exact if n is a power of 2

Definition at line 152 of file kube-gustavson-fft.cpp.

Referenced by FFT842().

int fft2d	(	DCOMPLEX *	array,
		int	rows,
		int	cols,
		int	direction
	)

Definition at line 545 of file kube-gustavson-fft.cpp.

References allocateBuffer(), ERROR, FFT842(), freeBuffer(), handle_error, LoadCol, LoadRow, NO_ERROR, power_of_2(), StoreCol, and StoreRow.

Referenced by forward_fft2d(), and inverse_fft2d().

int fft2f	(	COMPLEX *	array,
		int	rows,
		int	cols,
		int	direction
	)

Definition at line 503 of file kube-gustavson-fft.cpp.

References allocateBuffer(), ERROR, FFT842(), freeBuffer(), handle_error, LoadCol, LoadRow, NO_ERROR, power_of_2(), StoreCol, and StoreRow.

Referenced by forward_fft2f(), and inverse_fft2f().

void FFT842	(	int	direction,
		int	n,
		DCOMPLEX *	b
	)

FFT842 (Name kept from the original Fortran version) This routine replaces the input DCOMPLEX vector by its finite discrete complex fourier transform if in==FFT_FORWARD. It replaces the input DCOMPLEX vector by its finite discrete complex inverse fourier transform if in==FFT_INVERSE.

The implementation is a radix-2 FFT, but with faster shortcuts for radix-4 and radix-8. It performs as many radix-8 iterations as possible, and then finishes with a radix-2 or -4 iteration if needed.

Definition at line 380 of file kube-gustavson-fft.cpp.

References fastlog2(), FFT_FORWARD, FFT_INVERSE, DCOMPLEX::im, R2TX(), R4TX(), R8TX(), and DCOMPLEX::re.

Referenced by fft2d(), and fft2f().

int forward_fft2d	(	DCOMPLEX *	array,
		int	rows,
		int	cols
	)

Perform forward 2D transform on a DCOMPLEX array.

Definition at line 597 of file kube-gustavson-fft.cpp.

References fft2d(), and FFT_FORWARD.

int forward_fft2f	(	COMPLEX *	array,
		int	rows,
		int	cols
	)

Perform forward 2D transform on a COMPLEX array.

Definition at line 585 of file kube-gustavson-fft.cpp.

References fft2f(), and FFT_FORWARD.

Referenced by bildcomplex::FFT_forward().

void freeBuffer ( void )

Free space for stageBuff

Definition at line 133 of file kube-gustavson-fft.cpp.

Referenced by fft2d(), and fft2f().

int inverse_fft2d	(	DCOMPLEX *	array,
		int	rows,
		int	cols
	)

Perform inverse 2D transform on a DCOMPLEX array.

Definition at line 603 of file kube-gustavson-fft.cpp.

References fft2d(), and FFT_INVERSE.

int inverse_fft2f	(	COMPLEX *	array,
		int	rows,
		int	cols
	)

Perform inverse 2D transform on a COMPLEX array.

Definition at line 591 of file kube-gustavson-fft.cpp.

References fft2f(), and FFT_INVERSE.

Referenced by bildcomplex::FFT_backward().

int power_of_2 ( int n )

See if exactly one bit is set in integer argument

Definition at line 140 of file kube-gustavson-fft.cpp.

Referenced by fft2d(), and fft2f().

void R2TX	(	int	nthpo,
		DCOMPLEX *	c0,
		DCOMPLEX *	c1
	)

Radix-2 iteration subroutine

Definition at line 164 of file kube-gustavson-fft.cpp.

References DCOMPLEX::im, and DCOMPLEX::re.

Referenced by FFT842().

void R4TX	(	int	nthpo,
		DCOMPLEX *	c0,
		DCOMPLEX *	c1,
		DCOMPLEX *	c2,
		DCOMPLEX *	c3
	)

Radix-4 iteration subroutine

Definition at line 189 of file kube-gustavson-fft.cpp.

References DCOMPLEX::im, and DCOMPLEX::re.

Referenced by FFT842().

void R8TX	(	int	nxtlt,
		int	nthpo,
		int	length,
		DCOMPLEX *	cc0,
		DCOMPLEX *	cc1,
		DCOMPLEX *	cc2,
		DCOMPLEX *	cc3,
		DCOMPLEX *	cc4,
		DCOMPLEX *	cc5,
		DCOMPLEX *	cc6,
		DCOMPLEX *	cc7
	)

Radix-8 iteration subroutine

Definition at line 230 of file kube-gustavson-fft.cpp.

References DCOMPLEX::im, IRT2, DCOMPLEX::re, and TWOPI.

Referenced by FFT842().

Variable Documentation

COMPLEX* bigBuff

Definition at line 115 of file kube-gustavson-fft.cpp.

DCOMPLEX* bigBuffd

Definition at line 116 of file kube-gustavson-fft.cpp.

DCOMPLEX* stageBuff

Definition at line 114 of file kube-gustavson-fft.cpp.


Defines
#define	LoadRow(buffer, row, cols)
#define	StoreRow(buffer, row, cols)
#define	LoadCol(buffer, col, rows, cols)
#define	StoreCol(buffer, col, rows, cols)
#define	handle_error(msg) fprintf(stderr,msg)
Functions
int	allocateBuffer (int size)
void	freeBuffer (void)
int	power_of_2 (int n)
int	fastlog2 (int n)
void	R2TX (int nthpo, DCOMPLEX c0, DCOMPLEX c1)
void	R4TX (int nthpo, DCOMPLEX c0, DCOMPLEX c1, DCOMPLEX c2, DCOMPLEX c3)
void	R8TX (int nxtlt, int nthpo, int length, DCOMPLEX cc0, DCOMPLEX cc1, DCOMPLEX cc2, DCOMPLEX cc3, DCOMPLEX cc4, DCOMPLEX cc5, DCOMPLEX cc6, DCOMPLEX cc7)
void	FFT842 (int direction, int n, DCOMPLEX *b)
int	fft2f (COMPLEX *array, int rows, int cols, int direction)
int	fft2d (DCOMPLEX *array, int rows, int cols, int direction)
int	forward_fft2f (COMPLEX *array, int rows, int cols)
int	inverse_fft2f (COMPLEX *array, int rows, int cols)
int	forward_fft2d (DCOMPLEX *array, int rows, int cols)
int	inverse_fft2d (DCOMPLEX *array, int rows, int cols)
Variables
DCOMPLEX *	stageBuff
COMPLEX *	bigBuff
DCOMPLEX *	bigBuffd