1 /* -------------------------------------------------------------- */
2 /* (C)Copyright 2008 Free Software Foundation, Inc. */
3 /* (C)Copyright 2001,2007, */
4 /* International Business Machines Corporation, */
5 /* Sony Computer Entertainment, Incorporated, */
6 /* Toshiba Corporation, */
8 /* All Rights Reserved. */
10 /* Redistribution and use in source and binary forms, with or */
11 /* without modification, are permitted provided that the */
12 /* following conditions are met: */
14 /* - Redistributions of source code must retain the above copyright*/
15 /* notice, this list of conditions and the following disclaimer. */
17 /* - Redistributions in binary form must reproduce the above */
18 /* copyright notice, this list of conditions and the following */
19 /* disclaimer in the documentation and/or other materials */
20 /* provided with the distribution. */
22 /* - Neither the name of IBM Corporation nor the names of its */
23 /* contributors may be used to endorse or promote products */
24 /* derived from this software without specific prior written */
27 /* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND */
28 /* CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, */
29 /* INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF */
30 /* MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE */
31 /* DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR */
32 /* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, */
33 /* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT */
34 /* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; */
35 /* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) */
36 /* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN */
37 /* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR */
38 /* OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, */
39 /* EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */
40 /* -------------------------------------------------------------- */
41 /* PROLOG END TAG zYx */
43 #ifndef INCLUDED_LIBFFT_H
44 #define INCLUDED_LIBFFT_H
46 // must be defined before inclusion of fft_1d_r2.h
47 #define MAX_FFT_1D_SIZE 4096
51 * Performs a single precision, complex Fast Fourier Transform using
52 * the DFT (Discrete Fourier Transform) with radix-2 decimation in time.
53 * The input <in> is an array of complex numbers of length (1<<log2_size)
54 * entries. The result is returned in the array of complex numbers specified
55 * by <out>. Note: This routine can support an in-place transformation
56 * by specifying <in> and <out> to be the same array.
58 * This implementation utilizes the Cooley-Tukey algorithm consisting
59 * of <log2_size> stages. The basic operation is the butterfly.
61 * p --------------------------> P = p + q*Wi
70 * q --| Wi |-----------------> Q = p - q*Wi
73 * This routine also requires pre-computed twiddle values, W. W is an
74 * array of single precision complex numbers of length 1<<(log2_size-2)
75 * and is computed as follows:
77 * for (i=0; i<n/4; i++)
78 * W[i].real = cos(i * 2*PI/n);
79 * W[i].imag = -sin(i * 2*PI/n);
82 * This array actually only contains the first half of the twiddle
83 * factors. Due for symmetry, the second half of the twiddle factors
84 * are implied and equal:
86 * for (i=0; i<n/4; i++)
87 * W[i+n/4].real = W[i].imag = sin(i * 2*PI/n);
88 * W[i+n/4].imag = -W[i].real = -cos(i * 2*PI/n);
91 * Further symmetry allows one to generate the twiddle factor table
92 * using half the number of trig computations as follows:
96 * for (i=1; i<n/4; i++)
97 * W[i].real = cos(i * 2*PI/n);
98 * W[n/4 - i].imag = -W[i].real;
101 * The complex numbers are packed into quadwords as follows:
104 * array element array elements
105 * -----------------------------------------------------
106 * i | real 2*i | imag 2*i | real 2*i+1 | imag 2*i+1 |
107 * -----------------------------------------------------
111 void fft_1d_r2(vector float *out, vector float *in, vector float *W, int log2_size);
113 #endif /* INCLUDED_LIBFFT_H */