// -*- C++ -*- // automatically generated by autodoc // ========== HEADER FILE src/fft/fft-default.h: ========== // Default FFT implementations inline void fft(double *fr, double *fi, ulong ldn, int is); inline void fft(Complex *f, ulong ldn, int is); // ========== HEADER FILE src/fft/fft.h: ========== // FAST FOURIER TRANSFORM (FFT) // typical format of arguments: (double *fr, double *fi, ulong ldn, int is) // fr := pointer to data array (real part), // fi := pointer to data array (imag part), // ldn := base 2 log of array length // is := sign of exponent in fourier kernel // naming conventions: // name_fft() := FFT implementation using algorithm "name" // name_fft0() := same for zero padded data // (i.e. second half of the input data is expected to be zero) // ----- SRCFILE=src/fft/fhtfft.cc: ----- void fht_fft(double *fr, double *fi, ulong ldn, int is); // FFT based on FHT // ldn := base-2 logarithm of the array length // is := sign of the transform (+1 or -1) void fht_fft0(double *fr, double *fi, ulong ldn, int is); // FFT based on FHT // version for zero padded data: // fr[k], fi[k] == 0 for k=n/2 ... n-1 // ldn := base-2 logarithm of the array length // is := sign of the transform (+1 or -1) void fht_fft_conversion(double *fr, double *fi, ulong ldn, int is); // aux // preprocessing to use two length-n FHTs // to compute a length-n complex FFT // or // postprocessing to use two length-n FHTs // to compute a length-n complex FFT // Self-inverse. // is := sign of the transform (+1 or -1) // ldn := base-2 logarithm of the array length // ----- SRCFILE=src/fft/fhtcfft.cc: ----- void fht_fft(Complex *f, ulong ldn, int is); // compute FFT using the Fast Hartley Transform // ldn := base-2 logarithm of the array length // is := sign of the transform (+1 or -1) void fht_fft0(Complex *f, ulong ldn, int is); // compute FFT using the Fast Hartley Transform // ldn := base-2 logarithm of the array length // is := sign of the transform (+1 or -1) // version for zero padded data: // f[k] == 0 for k=n/2 ... n-1 void fht_fft_conversion(Complex *f, ulong ldn, int is); // aux // preprocessing to use one length-n complex FHT // to compute a length-n complex FFT // or // postprocessing to use one length-n complex FHT // to compute a length-n complex FFT // Self-inverse. // is := sign of the transform (+1 or -1) // ldn := base-2 logarithm of the array length // ----- SRCFILE=src/fft/fftdif2.cc: ----- void fft_depth_first_dif2(Complex *f, ulong ldn, int is); // Decimation in frequency (DIF) radix-2 FFT, depth-first version. // Compared to usual fft this one // - does more trig computations // - is (far) better memory local void fft_dif2(Complex *f, ulong ldn, int is); // Decimation in frequency (DIT) radix-2 FFT. // ----- SRCFILE=src/fft/fftdit2.cc: ----- void fft_depth_first_dit2(Complex *f, ulong ldn, int is); // Decimation in time (DIT) radix-2 FFT, depth-first version. // Compared to usual FFT this one // - does more trig computations // - is (far) better memory local void fft_dit2(Complex *f, ulong ldn, int is); // Decimation in time (DIT) radix-2 FFT. // ----- SRCFILE=src/fft/fftdif4l.cc: ----- void fft_dif4l(Complex *f, ulong ldn, int is); // Decimation in frequency (DIF) radix-4 FFT // Non-optimized learners version // ----- SRCFILE=src/fft/fftdit4l.cc: ----- void fft_dit4l(Complex *f, ulong ldn, int is); // Decimation in time (DIT) radix-4 FFT. // Non-optimized learners version. // ----- SRCFILE=src/fft/fftdif4.cc: ----- void fft_dif4_core_p1(double *fr, double *fi, ulong ldn); // aux // Auxiliary routine for fft_dif4(). // Decimation in frequency (DIF) radix-4 FFT. // Output data is in revbin_permuted order. // ldn := base-2 logarithm of the array length. // Fixed isign = +1 void fft_dif4(double *fr, double *fi, ulong ldn, int is); // Decimation in frequency (DIF) radix-4 FFT. // ldn := base-2 logarithm of the array length // is := sign of the transform (+1 or -1) // ----- SRCFILE=src/fft/cfftdif4.cc: ----- void fft_dif4_core_p1(Complex *f, ulong ldn); // aux // Auxiliary routine for fft_dif4(). // Radix-4 decimation in frequency (DIF) FFT, fixed isign = +1 // Output data is in revbin_permuted order. // ldn := base-2 logarithm of the array length. void fft_dif4_core_m1(Complex *f, ulong ldn); // aux // Auxiliary routine for fft_dif4(). // Radix-4 decimation in frequency (DIF) FFT, fixed isign = -1 // Output data is in revbin_permuted order. // ldn := base-2 logarithm of the array length void fft_dif4(Complex *f, ulong ldn, int is); // Fast Fourier Transform // ldn := base-2 logarithm of the array length // is := sign of the transform (+1 or -1) // radix-4 decimation in frequency algorithm // ----- SRCFILE=src/fft/fftdit4.cc: ----- void fft_dit4_core_p1(double *fr, double *fi, ulong ldn); // aux // Auxiliary routine for fft_dit4() // Decimation in time (DIT) radix-4 FFT // Input data must be in revbin_permuted order // ldn := base-2 logarithm of the array length // Fixed isign = +1 void fft_dit4(double *fr, double *fi, ulong ldn, int is); // Decimation in time (DIT) radix-4 FFT // ldn := base-2 logarithm of the array length // is := sign of the transform (+1 or -1) // ----- SRCFILE=src/fft/cfftdit4.cc: ----- void fft_dit4_core_m1(Complex *f, ulong ldn); // aux // Auxiliary routine for fft_dit4(). // Radix-4 decimation in time (DIT) FFT, fixed isign = -1 // ldn := base-2 logarithm of the array length. // Input data must be in revbin_permuted order. void fft_dit4_core_p1(Complex *f, ulong ldn); // aux // Auxiliary routine for fft_dit4() // Radix-4 decimation in time (DIT) FFT, fixed isign = +1 // ldn := base-2 logarithm of the array length // Input data must be in revbin_permuted order void fft_dit4(Complex *f, ulong ldn, int is); // Fast Fourier Transform // ldn := base-2 logarithm of the array length // is := sign of the transform (+1 or -1) // Radix-4 decimation in time algorithm // ----- SRCFILE=src/fft/cfftsplitradix.cc: ----- // tuning parameter: //#define USE_SINCOS3 // default = off // whether sincos is used for 3*angle // else: use algebraic relation // // sin & cos of triple angle by algebra: #define SINCOS3ALG(c, s, c3, s3) { c3 = 4.0*c*(c*c-0.75); s3=4.0*s*(0.75-s*s); } void split_radix_dif_fft_core(Complex *f, ulong ldn); // aux // Split-radix decimation in frequency (DIF) FFT. // ldn := base-2 logarithm of the array length. // Fixed isign = +1 // Output data is in revbin_permuted order. void split_radix_dit_fft_core(Complex *f, ulong ldn); // aux // Split-radix decimation in time (DIT) FFT. // ldn := base-2 logarithm of the array length. // Fixed isign = -1 // Input data must be in revbin_permuted order. void split_radix_fft(Complex *f, ulong ldn, int is); // Fast Fourier Transform. // ldn := base-2 logarithm of the array length. // is := sign of the transform (+1 or -1) // Uses (DIF and DIT) split-radix algorithms. // ----- SRCFILE=src/fft/fftsplitradix.cc: ----- // tuning parameter: //#define USE_SINCOS3 // default = off // whether sincos is used for 3*angle // else: use algebraic relation // // sin & cos of triple angle by algebra: #define SINCOS3ALG(c, s, c3, s3) { c3 = 4.0*c*(c*c-0.75); s3=4.0*s*(0.75-s*s); } void split_radix_fft_dif_core(double *fr, double *fi, ulong ldn); // aux // Auxiliary routine for split_radix_fft_dif(). // Split-radix decimation in frequency (DIF) FFT. // Output data is in revbin_permuted order. // ldn := base-2 logarithm of the array length. // fixed isign == -1 void split_radix_fft(double *fr, double *fi, ulong ldn, int is); // Fast Fourier Transform // Split-radix decimation in frequency (DIF) algorithm. // ldn := base-2 logarithm of the array length. // is := sign of the transform (+1 or -1). // ----- SRCFILE=src/fft/cfftwrap.cc: ----- void complex_to_real_imag(Complex *c, ulong n); // aux // Transform complex data into two seperate fields // with real and imag data (in-place) // n := array length void real_imag_to_complex(double *fr/*, double *fi*/, ulong n); // aux // Transform two seperate fields with real and imag // data into complex data (in-place) // n := array length(s) // Must have: imaginary parts must start at (fr + n). // That is, the data must lie in contiguous memory. void complex_fft(Complex *c, ulong ldn, int is); // FFT wrapper to use the routines that use the data // in the real/imag form for type complex data // ldn := base-2 logarithm of the array length // is := sign of the transform (+1 or -1) // NOTE: dprecated, prefer routine that uses type Complex. void real_imag_fft(double *fr/*, double *fi*/, ulong ldn, int is); // FFT wrapper to use the routines that use the data // in the complex form for data in real/imag form // ldn := base-2 logarithm of the array length // is := sign of the transform (+1 or -1) // Must have: imaginary parts must start at (fr + n). // That is, the data must lie in contiguous memory. // ----- SRCFILE=src/fft/fouriershift.cc: ----- void fourier_shift(Complex *a, ulong n, double v); // aux // auxiliary routine for FFTs: // used for recursive FFTs and matrix FFTs (MFA) // n := length of array // a[k] *= exp(k*v*sqrt(-1)*2*pi/n) for k = 0...n-1 void fourier_shift(double *fr, double *fi, ulong n, double v); // aux // auxiliary routine for FFTs: // used for recursive FFTs and matrix FFTs (MFA) // n := length of array // a[k] *= exp(k*v*sqrt(-1)*2*pi/n) for k = 0...n-1 void fourier_shift_imag0(double *fr, double *fi, ulong n, double v); // aux // auxiliary routine for FFTs: // used for matrix FFTs (MFA) // n := length of array // (fr[k], fi[k]) *= exp(k*v*sqrt(-1)*2*pi/n) for k = 0...n-1 // assume fi[] is zero void fourier_shift(double *fr, double *fi, ulong n, double v, ulong k0, ulong kn); // aux // auxiliary routine for FFTs // (fr[k], fi[k]) *= exp((k0+k)*v*sqrt(-1)*2*pi/n) for k = 0...kn-1 // n := length of array void fourier_shift_imag0(double *fr, double *fi, ulong n, double v, ulong k0, ulong kn); // aux // auxiliary routine for FFTs // (fr[k], fi[k]) *= exp((k0+k)*v*sqrt(-1)*2*pi/n) for k = 0...kn-1 // assume fi[] is zero // ----- SRCFILE=src/fft/skipfft.cc: ----- void skip_fft(double *fr, double *fi, ulong n, ulong d, double *wr, double *wi, int is); // aux // Compute FFT of the n elements // fr, fi [0], [d], [2d], [3d], ..., [(n-1)*d] void skip_fft0(double *fr, double *fi, ulong n, ulong d, double *wr, double *wi, int is); // aux // Compute FFT of the n elements // fr, fi [0], [d], [2d], [3d], ..., [(n-1)*d] // version for zero padded data: // fr[k], fi[k] == 0 for k=d*n/2 ... d*(n-1) // ----- SRCFILE=src/fft/weightedfft.cc: ----- void weighted_fft(double *fr, double *fi, ulong ldn, int is, double w); // Weighted FFT void weighted_inverse_fft(double *fr, double *fi, ulong ldn, int is, double w); // Inverse of weighted_fft() iff signs of both w and is are changed // -------- 2-dim FFT: // ----- SRCFILE=src/fft/twodimfft.cc: ----- void twodim_fft(double *fr, double *fi, ulong nr, ulong nc, int is); // -------- Spectrum: // ----- SRCFILE=src/fft/fftspect.cc: ----- void fft_spectrum(double *f, ulong ldn, int phasesq/*=0*/); // Compute power spectrum using FFT // ldn := base-2 logarithm of the array length // phasesq != 0 requests computation of phases // phase[i] is in f[n-i] (i=1...n/2-1) // phase[0] == 0, phase[n/2] == 0 // output is not normalized // ========== HEADER FILE src/fft/matrixfft.h: ========== // ----- SRCFILE=src/fft/matrixfft.cc: ----- void matrix_fft(double *fr, double *fi, ulong ldn, int is); // Matrix (aka four-step) FFT. // Useful for arrays larger than 2nd-level cache. void matrix_fft0(double *fr, double *fi, ulong ldn, int is); // Matrix (aka four-step) FFT. // Useful for arrays larger than 2nd-level cache. // Version for zero padded data. void matrix_fft(Complex *f, ulong ldn, int is); // Matrix (aka four-step) FFT. // Useful for arrays larger than 2nd-level cache. void matrix_fft0(Complex *f, ulong ldn, int is); // Matrix (aka four-step) FFT. // Useful for arrays larger than 2nd-level cache. // Version for zero padded data. // ----- SRCFILE=src/fft/rowffts.cc: ----- void row_ffts(double *fr, double *fi, ulong nr, ulong nc, int is); // aux // nr x nc matrix (nr rows of length nc) void row_weighted_ffts(double *fr, double *fi, ulong nr, ulong nc, int is); // aux // nr x nc matrix (nr rows of length nc) void row_ffts(Complex *f, ulong nr, ulong nc, int is); // aux // nr x nc matrix (nr rows of length nc) void row_weighted_ffts(Complex *f, ulong nr, ulong nc, int is); // aux // nr x nc matrix (nr rows of length nc) // ----- SRCFILE=src/fft/rowcnvls.cc: ----- void row_weighted_auto_convolutions(double *fr, double *fi, ulong nr, ulong nc, double v); // aux // (complex, weighted) convolution of the rows of the // nr x nc matrix (nr rows, nc columns) // v!=0.0 chooses alternative normalization void row_weighted_auto_convolutions(Complex *f, ulong nr, ulong nc, double v); // aux // (complex, weighted) convolution of the rows of the // nr x nc matrix (nr rows, nc columns) // v!=0.0 chooses alternative normalization // ----- SRCFILE=src/fft/columnffts.cc: ----- void column_ffts(double *fr, double *fi, ulong nr, ulong nc, int is, int zp, double *tmpr, double *tmpi); // aux // nr x nc matrix (nr rows, nc columns) // length of each col is nr // length of each row is nc void column_ffts(Complex *f, ulong nr, ulong nc, int is, int zp, Complex *tmp); // aux // nr x nc matrix (nr rows, nc columns) // length of each col is nr // length of each row is nc void column_real_complex_ffts(double *f, ulong nr, ulong nc, int zp, double *tmp); // aux // nr x nc matrix (nr rows, nc columns) // length of each col is nr // length of each row is nc void column_complex_real_ffts(double *f, ulong nr, ulong nc, double *tmp); // aux // nr x nc matrix (nr rows, nc columns) // length of each col is nr // length of each row is nc void column_complex_imag_ffts(const double *fr, double *fi, ulong nr, ulong nc, double *tmp); // aux // nr x nc matrix (nr rows, nc columns) // length of each col is nr // length of each row is nc // only the imag part of the result is computed // ========== HEADER FILE src/fft/shortfft.h: ========== // ----- SRCFILE=src/fft/fft8ditcore.cc: ----- void fft8_dit_core_p1(Complex *f); // 8-point decimation in time FFT // fixed isign = -1 // input data must be in revbin_permuted order void fft8_dit_core_m1(Complex *f); // 8-point decimation in time FFT // fixed isign = -1 // input data must be in revbin_permuted order void fft8_dit_core_p1(double *fr, double *fi); // 8-point decimation in time FFT // isign = +1 // input data must be in revbin_permuted order inline void fft8_dit_core_m1(double *fr, double *fi); // ----- SRCFILE=src/fft/fft8difcore.cc: ----- void fft8_dif_core_p1(Complex *f); // 8-point decimation in frequency FFT, fixed isign = +1 // Output data is in revbin_permuted order. void fft8_dif_core_m1(Complex *f); // 8-point decimation in frequency FFT, fixed isign = -1 // Output data is in revbin_permuted order. void fft8_dif_core_p1(double *fr, double *fi); // 8-point decimation in frequency FFT, fixed isign = +1 // Output data is in revbin_permuted order. inline void fft8_dif_core_m1(double *fr, double *fi); // ----- SRCFILE=src/fft/fft9.cc: ----- void fft9_m1(Complex *x); // 9-point FFT, fixed isign = -1 void fft9_p1(Complex *x); // 9-point FFT, fixed isign = +1 void fft9_m1(double *xr, double *xi); // 9-point FFT, fixed isign = -1 void fft9_p1(double *xr, double *xi); // 9-point FFT, fixed isign = +1 // ========== HEADER FILE src/fft/slowft.h: ========== // -------- Slow algorithms: // ----- SRCFILE=src/fft/slowft.cc: ----- void slow_ft(Complex *f, ulong n, int is); // Fourier transform by definition (slow!) void slow_ft(double *fr, double *fi, ulong n, int is); // Fourier transform by definition (slow!) void slow_twodim_ft(Complex *f, ulong nr, ulong nc, int is); void slow_twodim_ft(double *fr, double *fi, ulong nr, ulong nc, int is); // ----- SRCFILE=src/fft/recfft2.cc: ----- static void recursive_fft_dit2_core(const Complex *a, ulong n, Complex *x, int is); void recursive_fft_dit2(Complex *a, ulong ldn, int is); // very inefficient, just to demonstrate the // recursive fast fourier transform static void recursive_fft_dif2_core(const Complex *a, ulong n, Complex *x, int is); void recursive_fft_dif2(Complex *a, ulong ldn, int is); // very inefficient, just to demonstrate the // recursive fast fourier transform