mborgerding / kissfft

a Fast Fourier Transform (FFT) library that tries to Keep it Simple, Stupid

KISS FFT

KISS FFT - A mixed-radix Fast Fourier Transform based up on the principle, "Keep It Simple, Stupid."

There are many great fft libraries already around. Kiss FFT is not trying to be better than any of them. It only attempts to be a reasonably efficient, moderately useful FFT that can use fixed or floating data types and can be incorporated into someone's C program in a few minutes with trivial licensing.

USAGE:

The basic usage for 1-d complex FFT is:

    #include "kiss_fft.h"
    kiss_fft_cfg cfg = kiss_fft_alloc( nfft ,is_inverse_fft ,0,0 );
    while ...
    
        ... // put kth sample in cx_in[k].r and cx_in[k].i
        
        kiss_fft( cfg , cx_in , cx_out );
        
        ... // transformed. DC is in cx_out[0].r and cx_out[0].i 
        
    kiss_fft_free(cfg);

• Note: frequency-domain data is stored from dc up to 2pi. so cx_out[0] is the dc bin of the FFT and cx_out[nfft/2] is the Nyquist bin (if exists)

Declarations are in "kiss_fft.h", along with a brief description of the functions you'll need to use.

Code definitions for 1d complex FFTs are in kiss_fft.c.

You can do other cool stuff with the extras you'll find in tools/

• multi-dimensional FFTs
• real-optimized FFTs (returns the positive half-spectrum: (nfft/2+1) complex frequency bins)
• fast convolution FIR filtering (not available for fixed point)
• spectrum image creation

The core fft and most tools/ code can be compiled to use float, double, Q15 short or Q31 samples. The default is float.

BUILDING:

There are two functionally-equivalent build systems supported by kissfft:

• Make (traditional Makefiles for Unix / Linux systems)
• CMake (more modern and feature-rich build system developed by Kitware)

To build kissfft, the following build environment can be used:

• GNU build environment with GCC, Clang and GNU Make or CMake (>= 3.6)
• Microsoft Visual C++ (MSVC) with CMake (>= 3.6)

Additional libraries required to build and test kissfft include:

• libpng for psdpng tool,
• libfftw3 to validate kissfft results against it,
• python 2/3 with Numpy to validate kissfft results against it.
• OpenMP supported by GCC, Clang or MSVC for multi-core FFT transformations

Environments like Cygwin and MinGW can be highly likely used to build kissfft targeting Windows platform, but no tests were performed to the date.

Both Make and CMake builds are easily configurable:

• KISSFFT_DATATYPE=<datatype> (for Make) or -DKISSFFT_DATATYPE=<datatype> (for CMake) denote the principal datatype used by kissfft. It can be one of the following:

  • float (default)
  • double
  • int16_t
  • int32_t
  • SIMD (requires SSE instruction set support on target CPU)

• KISSFFT_OPENMP=1 (for Make) or -DKISSFFT_OPENMP=ON (for CMake) builds kissfft with OpenMP support. Please note that a supported compiler is required and this option is turned off by default.

• KISSFFT_STATIC=1 (for Make) or -DKISSFFT_STATIC=ON (for CMake) instructs the builder to create static library ('.lib' for Windows / '.a' for Unix or Linux). By default, this option is turned off and the shared library is created ('.dll' for Windows, '.so' for Linux or Unix, '.dylib' for Mac OSX)

• -DKISSFFT_TEST=OFF (for CMake) disables building tests for kissfft. On Make, building tests is done separately by 'make testall' or 'make testsingle', so no specific setting is required.

• KISSFFT_TOOLS=0 (for Make) or -DKISSFFT_TOOLS=OFF (for CMake) builds kissfft without command-line tools like 'fastconv'. By default the tools are built.

  • KISSFFT_USE_ALLOCA=1 (for Make) or -DKISSFFT_USE_ALLOCA=ON (for CMake) build kissfft with 'alloca' usage instead of 'malloc' / 'free'.

  • PREFIX=/full/path/to/installation/prefix/directory (for Make) or -DCMAKE_INSTALL_PREFIX=/full/path/to/installation/prefix/directory (for CMake) specifies the prefix directory to install kissfft into.

For example, to build kissfft as a static library with 'int16_t' datatype and OpenMP support using Make, run the command from kissfft source tree:

make KISSFFT_DATATYPE=int16_t KISSFFT_STATIC=1 KISSFFT_OPENMP=1 all

The same configuration for CMake is:

mkdir build && cd build
cmake -DKISSFFT_DATATYPE=int16_t -DKISSFFT_STATIC=ON -DKISSFFT_OPENMP=ON ..
make all

To specify '/tmp/1234' as installation prefix directory, run:

make PREFIX=/tmp/1234 KISSFFT_DATATYPE=int16_t KISSFFT_STATIC=1 KISSFFT_OPENMP=1 install

or

mkdir build && cd build
cmake -DCMAKE_INSTALL_PREFIX=/tmp/1234 -DKISSFFT_DATATYPE=int16_t -DKISSFFT_STATIC=ON -DKISSFFT_OPENMP=ON ..
make all
make install

TESTING:

To validate the build configured as an example above, run the following command from kissfft source tree:

make KISSFFT_DATATYPE=int16_t KISSFFT_STATIC=1 KISSFFT_OPENMP=1 testsingle

if using Make, or:

make test

if using CMake.

To test all possible build configurations, please run an extended testsuite from kissfft source tree:

sh test/kissfft-testsuite.sh

Please note that the extended testsuite takes around 20-40 minutes depending on device it runs on. This testsuite is useful for reporting bugs or testing the pull requests.

BACKGROUND

I started coding this because I couldn't find a fixed point FFT that didn't use assembly code. I started with floating point numbers so I could get the theory straight before working on fixed point issues. In the end, I had a little bit of code that could be recompiled easily to do ffts with short, float or double (other types should be easy too).

Once I got my FFT working, I was curious about the speed compared to a well respected and highly optimized fft library. I don't want to criticize this great library, so let's call it FFT_BRANDX. During this process, I learned:

1. FFT_BRANDX has more than 100K lines of code. The core of kiss_fft is about 500 lines (cpx 1-d).
2. It took me an embarrassingly long time to get FFT_BRANDX working.
3. A simple program using FFT_BRANDX is 522KB. A similar program using kiss_fft is 18KB (without optimizing for size).
4. FFT_BRANDX is roughly twice as fast as KISS FFT in default mode.

It is wonderful that free, highly optimized libraries like FFT_BRANDX exist. But such libraries carry a huge burden of complexity necessary to extract every last bit of performance.

Sometimes simpler is better, even if it's not better.

FREQUENTLY ASKED QUESTIONS:

Q: Can I use kissfft in a project with a ___ license?
A: Yes. See LICENSE below.

Q: Why don't I get the output I expect?
A: The two most common causes of this are

1. scaling : is there a constant multiplier between what you got and what you want?
2. mixed build environment -- all code must be compiled with same preprocessor definitions for FIXED_POINT and kiss_fft_scalar

Q: Will you write/debug my code for me?
A: Probably not unless you pay me. I am happy to answer pointed and topical questions, but I may refer you to a book, a forum, or some other resource.

PERFORMANCE

(on Athlon XP 2100+, with gcc 2.96, float data type)

Kiss performed 10000 1024-pt cpx ffts in .63 s of cpu time. For comparison, it took md5sum twice as long to process the same amount of data. Transforming 5 minutes of CD quality audio takes less than a second (nfft=1024).

DO NOT:

• use Kiss if you need the Fastest Fourier Transform in the World
• ask me to add features that will bloat the code

UNDER THE HOOD

Kiss FFT uses a time decimation, mixed-radix, out-of-place FFT. If you give it an input buffer
and output buffer that are the same, a temporary buffer will be created to hold the data.

No static data is used. The core routines of kiss_fft are thread-safe (but not all of the tools directory).[

No scaling is done for the floating point version (for speed).
Scaling is done both ways for the fixed-point version (for overflow prevention).

Optimized butterflies are used for factors 2,3,4, and 5.

The real (i.e. not complex) optimization code only works for even length ffts. It does two half-length FFTs in parallel (packed into real&imag), and then combines them via twiddling. The result is nfft/2+1 complex frequency bins from DC to Nyquist. If you don't know what this means, search the web.

The fast convolution filtering uses the overlap-scrap method, slightly modified to put the scrap at the tail.

LICENSE

Revised BSD License, see COPYING for verbiage. 
Basically, "free to use&change, give credit where due, no guarantees"
Note this license is compatible with GPL at one end of the spectrum and closed, commercial software at 
the other end.  See http://www.fsf.org/licensing/licenses

TODO

• Add real optimization for odd length FFTs
• Document/revisit the input/output fft scaling
• Make doc describing the overlap (tail) scrap fast convolution filtering in kiss_fastfir.c
• Test all the ./tools/ code with fixed point (kiss_fastfir.c doesn't work, maybe others)

AUTHOR

Mark Borgerding
[email protected]

kissfft's Issues

zero padding

Hi there. I need an fft that produces many more frequencies than data points. This can be done with padding the data with zeros. It would be nice if I did not have to actually pad the data with zeros, the fft code would just sum up to ndata, but still calculate frequencies up to nfft, where nfft > ndata. This should be a rather simple change and would make the library vastly more useful. Thanks.

Inverse FFT Broken

The following code does not produce the expected answer:
// -------------------
kiss_fft_cpx data[3];
data[0].r = 1;
data[0].i = 2;
data[1].r = 3;
data[1].i = 4;
data[2].r = 5;
data[2].i = 6;

kiss_fft_cfg fft = kiss_fft_alloc (3, 0, nullptr, nullptr);
kiss_fft_cfg ifft = kiss_fft_alloc (3, 1, nullptr, nullptr);

kiss_fft (fft, data, data);  // correct result
kiss_fft (ifft, data, data); // incorrect result

// -------------------
The intermediate result for the forward FFT matches the output Matlab gives, but the inverse FFT on that forward FFT data does not get back to the original data. This is using the code downloaded from GIT without any modifications.

AVX ?

Hi,

considering the great improvement of the SIMD variant, what about an AVX version that would process the lines 8 by 8 ? Do you see that as doable ?

Actually, I've just compared KissFFT/SIMD against the AVX version of MuFFT on a 1024x1024 2D grid, both take more or less the same amount of time at the moment. Hence my feelding that an AVX version of KissFFT would outperform MuFFT AVX implementation (or even AVX-512)...

Restructure project layout for better subproject integration.

To use kissfft as cmake subproject, all headers should be moved into either

<base>/include/kissfft or
<base>/kissfft

This has the benefit, that all headers has to be included in the namespace of kissfft, eg:

#include <kissfft/kissfft.hh>

stdint.h missing from kiss_fft.c

kiss_fft.c uses the types from stdint.h but doesn't include it, making it sensitive to how it's used in a project and the order in which things are built. #include <stdint.h> should appear in either kiss_fft.c itself or _kiss_fft_guts.h (possibly both, but if not, the latter).

logging with kissfft

Hi Mark

I have fiddling with many DSP platforms where KISSFFT does a good job - THANX A MIL.
But I have now seen some platforms with a quite string handling.

Can I with charm, sneaky tactics, and flatter ask you to change
https://github.com/mborgerding/kissfft/blob/master/kiss_fft_log.h#L20
from
#if defined(NDEBUG)
to
#if defined(NDEBUG) || defined(KIFFFFT_NO_LOG)

or similar - the naming etc I leave up to you.

The problem is that Debug builds will fail if not prohibited with a KISSFFT-specific compile flag.

Again thank you - U rock.

/pto

iFFT waveform type

I noticed that by default the program rebuilds real signal using square waves, is there an easy way to change this to use sine waves instead? It doesn't affect simple fft operations too much but the square waves do create some issues when doing any form of manipulative analysis.

About implementation in swift

Hi there, I need to calculate fft in my iOS project using byte array which from sound record. I can able to integrate kissfft in my project. As per documentation to calculate fft, I have used like this.

for init 
let kissFT = kiss_fft_alloc(Int32(sampleRate), 0, nil,nil)
for calculating cpx_in and cpx_out I have tried like this, but I could not ale to find the method
 let cpx_in = kiss_fft_cpx(r: <#T##Float#>, i: <#T##Float#>)

Here I have to pass ‘r’ and ‘i’ values. But I am not understanding what values I have to pass. Can you please help me.

Where in android I am using like this using DoubleFFt_1D java class.

DoubleFFT_1D fft_1d = new DoubleFFT_1D(windowSize);
double[] rowFFT = new double[2 * windowSize];
 
for (int win = 0; win < windowSize; win++)
{
rowFFT[win * 2] = sample[win + time * (windowSize - overlap)] * windowing[win];
rowFFT[win * 2 + 1] = 0;
}

Could you tell me the theory of the detail implement about kissfft ?

Could you tell me the theory of the detail implement about kissfft, maybe a book or web.

I am confused about the code like in kiss_fftr():

    for ( k=1;k <= ncfft/2 ; ++k ) {
        fpk    = st->tmpbuf[k]; 
        fpnk.r =   st->tmpbuf[ncfft-k].r;
        fpnk.i = - st->tmpbuf[ncfft-k].i;
        C_FIXDIV(fpk,2);
        C_FIXDIV(fpnk,2);

        C_ADD( f1k, fpk , fpnk );
        C_SUB( f2k, fpk , fpnk );
        C_MUL( tw , f2k , st->super_twiddles[k-1]);

        freqdata[k].r = HALF_OF(f1k.r + tw.r);
        freqdata[k].i = HALF_OF(f1k.i + tw.i);
        freqdata[ncfft-k].r = HALF_OF(f1k.r - tw.r);
        freqdata[ncfft-k].i = HALF_OF(tw.i - f1k.i);
    }

Thanks.

Pull Request for Arduino Support

I was wondering if you would accept a pull request to add Arduino Support which contains the following changes

• new file library.properties in the root directory.
• new file kiss_arduino_config.h in the root directory where we can define FIXED_POINT.
• the following change in kiss_fft.h to use the configuration

#if defined(ARDUINO) && !defined(IGNORE_ARDUINO_CONFIG)
#include "kiss_arduino_config.h"
#endif

With these changes the project can be used as Arduino library...

Do not hardcode gcc and ar

When trying to do a cross-build I don't want to use the host tools, but cross aware ones. Please use the default variables $(CC) and $(AR) which make will set with sane default values anyway, but which can easily be overridden.

can u give some material compared with other FFT algorithms? such as speed or accuracy?

Typo in docs

kissfft/kissfft.hh

Line 129 in 1efe720

/// stored in @c dst[0].real() and @c dst[1].imag() respectively.

Shouldn't this be (note the zero) ?

        /// stored in @c dst[0].real() and @c dst[0].imag() respectively.

Odd bug with VS2017 and latest from master ...

Hello. Thanks for kissfft.

I'm building with code cloned from the repo today with VS2017. Here's a snippet that demonstrates the problem. Any thoughts welcomed.

[edit]

See https://github.com/mborgerding/kissfft/blob/master/kissfft.hh#L268 for the problem.

A fix can be hacked in by declaring scatchbuf thusly: std::vector<cpx_type> scratchbuf(p);

        #include <complex>
        #include <kissfft.h>
	static void test()
	{
		typedef kissfft<float> fft_t;
		typedef std::complex<float> fft_type;

		const int nfft = 256;

		fft_t fwd(nfft, false);
		fft_t inv(nfft, true);

		std::vector<fft_type> x(nfft, fft_type());
		std::vector<fft_type> fx(nfft, fft_type());

		x[0] = 2;

		fwd.transform(&x[0], &fx[0]);
	}

This gives the resulting error(s):

1>r:\src\xmos\lib_mp3_test_tools\xcorr\kissfft\kissfft.hh(268): error C2131: expression did not evaluate to a constant
1>r:\src\xmos\lib_mp3_test_tools\xcorr\kissfft\kissfft.hh(268): note: failure was caused by a read of a variable outside its lifetime
1>r:\src\xmos\lib_mp3_test_tools\xcorr\kissfft\kissfft.hh(268): note: see usage of 'p'
1>r:\src\xmos\lib_mp3_test_tools\xcorr\kissfft\kissfft.hh(263): note: while compiling class template member function 'void kissfft<float,kissfft_utils::traits<T_Scalar>>::kf_bfly_generic(std::complex<float> *,const size_t,int,int)'
1>        with
1>        [
1>            T_Scalar=float
1>        ]
1>r:\src\xmos\lib_mp3_test_tools\xcorr\kissfft\kissfft.hh(110): note: see reference to function template instantiation 'void kissfft<float,kissfft_utils::traits<T_Scalar>>::kf_bfly_generic(std::complex<float> *,const size_t,int,int)' being compiled
1>        with
1>        [
1>            T_Scalar=float
1>        ]
1>r:\src\xmos\lib_mp3_test_tools\xcorr\fftxcorr2.h(16): note: see reference to class template instantiation 'kissfft<float,kissfft_utils::traits<T_Scalar>>' being compiled
1>        with
1>        [
1>            T_Scalar=float
1>        ]
1>r:\src\xmos\lib_mp3_test_tools\xcorr\kissfft\kissfft.hh(273): error C3863: array type 'std::complex<float> [p]' is not assignable
1>Done building project "xcorr.vcxproj" -- FAILED.

Testing kiss_fftr

Hi,

I am trying to test this library and there might be something I am missing. This is my example code, in which I create a signal with two superposed waves at 40 and 90 Hz.

int main()
{
  const int N = 512;
  kiss_fft_scalar in[N];
  kiss_fft_cpx out[N/2+1];

  auto config = kiss_fftr_alloc(N, false, nullptr, nullptr);

  const float max_time = 0.5;
  const float dT = max_time / float(N);

  for ( int i=0; i<N; i++) {
    float t = float(i) * dT;
    in[i] = sin( 40 * (2*M_PI) * t ) + 0.5* sin( 90 * (2*M_PI) * t );
  }

  kiss_fftr( config, in, out );

  for ( int i=0; i<N/2; i++)
  {
    kiss_fft_scalar Hz = i * ( 1.0 / dT) / float(N);
    kiss_fft_scalar amplitude = abs( out[i].r ) ;
    printf("%.2f   %.3f\n", Hz, amplitude );
  }
  return 0;
}

Am I doing something extremely stupid here? Am I missing something?

Is it possible to change fft data type during run time?

Hello,

my project requires multiple FFTs with different data types (int32, int16). It seems that the kiss_fft_scalar is fixed after compiling. I tried to define FIXED_POINT with different values in the code, but the result is incorrect. Could anyone tell me if my requirement is possible to be met?

Best

"kiss_fft_scalar" definition not been replaced if build with double type

I use cmake to build kissfft as staticlib on macOS 11 with property -DKISSFFT_DATATYPE=double, every thing works fine until i try to use it my project.

I got nan values from kiss_fft(), and my input array also been changed!!!

After i done some debugging and search on Web, i found that the definition of kiss_fft_scalar in file kiss_fft.h:

# ifndef kiss_fft_scalar
/*  default is float */
#   define kiss_fft_scalar float
# endif

It still set to float, which cause the kissfft fail to calculate the pos of data, lead to access someone else's memory. After i change the float to double, everything works like charm!

I dont' know if i made some mistake during the build process, or there is something you guys missed here.

My build step:

mkdir build
cd build
cmake -DCMAKE_BUILD_TYPE=Debug -DKISSFFT_DATATYPE=double -DKISSFFT_STATIC=ON -DKISSFFT_TEST=OFF -DKISSFFT_TOOLS=OFF ..
make

Suggestion for the #defines

Hi there,

I tweaked the conan recipe for kissfft, it had been missing the extra #defines that the library users needed to include in the compile stage.

I was wondering why library users need to define these themselves?
Instead, could I suggest you auto-generate a header file that has the required defines in there, and #include that in the kiss_fft.h (or other "common" header) ?

You already generate files, such as kissfft-config.cmake.in and kissfft.pc.in
Your generated header could do extra things like double-check any already-defined constants match this library's compiled-in options - to flag potential link errors for library users.

This would help packagers like me, who (for technical reasons) have to duplicate and maintain kissfft's cmake logic into the recipe, like this:

        # got to duplicate the logic from kissfft/CMakeLists.txt
        if self.options.datatype in ["float", "double"]:
            self.cpp_info.components["libkissfft"].defines.append("kiss_fft_scalar={}".format(self.options.datatype))
        elif self.options.datatype == "int16_t":
            self.cpp_info.components["libkissfft"].defines.append("FIXED_POINT=16")
        elif self.options.datatype == "int32_t":
            self.cpp_info.components["libkissfft"].defines.append("FIXED_POINT=32")
        elif self.options.datatype == "simd":
            self.cpp_info.components["libkissfft"].defines.append("USE_SIMD")

        if self.options.use_alloca:
            self.cpp_info.components["libkissfft"].defines.append("KISS_FFT_USE_ALLOCA")

        if self.options.shared:
            self.cpp_info.components["libkissfft"].defines.append("KISS_FFT_SHARED")

This is because in the conan world, only your header and library files get used by the downstream consumer, none of your generated pkgconfig or cmake files are reused... this is so kissfft can be consumed by libraries that use bazel, meson, pkg, automake or cmake... or whatever else in the future.

If you can encode those defines in a header file, then linking to kissfft becomes much simpler and easier to maintain... include files are here, library files are there, no other knowledge is required...

It would also be good if the library was just called "kissfft.a" and not "kissfft-double.a" (would remove some extra logic required in the recipe) ... unless you are building multiple variants that could all be linked at the same time.
In the conan world, you ask for kissfft with a particular option, and you'll get it, no need to name the libraries differently. I'm sure in other worlds it is very handy, so perhaps it could be a cmake option to use the same name, or just leave it as it is now and let the recipe continue to handle the variations.

Best regards,
Paul

Lisnr company use KissFFT library without attribution

The SDK of https://lisnr.com include the compiled functions of KissFFT (You can download Android Apk of Lisnr demo app and decompile it).

But I'm unable to find any attribution to KissFFT.

Do you have provided a commercial license to Lisnr ?

Neon

kissfft on ARMv7 with fixed point is slow. A neon version would improve performance quite a bit.

1. there arent enough registers, so the stack is used
2. shifts and rounding add a lot of overhead

The float version has neither of those issues. The main loop of bfly4 is 68 instructions for float vs 150 for 16 bit fixed point.

3. Neon could also process more than 1 value at a time.
   kiss_fft_cpx has 2 values, and bfly loops process more than 1 in places.
   C_MUL(scratch[0],Fout1 , *tw1 );
   C_MUL(scratch[1],Fout2 , *tw2 );

Windows: install step installs in C:\

Right now the install step on windows copies files to the root of your file system.

CMAKE_INSTALL_PREFIX is ignored for all files but the lib.
That is because CMAKE_INSTALL_* variables are empty.

This has to do with:

kissfft/CMakeLists.txt

Lines 104 to 110 in 8f47a67

	#
	# Add GNUInstallDirs for GNU infrastructure before target)include_directories
	#
	if(CMAKE_SYSTEM_NAME MATCHES "^(Linux|kFreeBSD|GNU)$" AND NOT CMAKE_CROSSCOMPILING)
	include(GNUInstallDirs)
	endif()

GNUInstallDirs should be included unconditionally. That is what most projects do. See glfw, portaudio, SQLiteCPP.

Otherwise one cannot use the install step on windows.

No optimized inverse FFT implementation for real time-domain data

In the C++ implementation, we now have optimized FFT implementation for real input. However the ifft counterpart of the optimized implementation cannot be found. Given that the implementation I mentioned can be found in the C part (namely, the kiss_fftri() function), can I consider it a TODO for this library?

Document what each element of input and output arrays means

There's no one-and-only convention for how input and output arrays in FFT libraries are organized, so it would nice to explicitly document this. It's obvious for complex FFT/IFFT, but it gets more ambiguous for real FFT and especially multidimensional FFT. (It's better to overdocument than underdocument.) For example, kiss_fftndri says

output freqdata has dims[0] X dims[1] X ... X dims[ndims-1]/2+1 complex points

but it's unclear of the order of the points. Is F(k1, k2) found in freqdata[k1 + dims[0] * k2]? I'm suggesting this because I think a lot of people have to spend several minutes making sure their assumptions about how their arrays are organized are correct with their FFT library.

Test code running issue

I'm trying to learn the code and I found there are some python test code, but I failed to run "compfft.py" with "ModuleNotFoundError: No module named 'FFT'", and I noticed that there are both "FFT" and "fft" module import in this source file. Thanks for any help.

kiss_fftr(cfg, kiss_fft_scalar* timedata, kiss_fft_cpx* freqdata) overflows freqdata?

The header file has the following:
void kiss_fftr(kiss_fftr_cfg cfg,const kiss_fft_scalar *timedata,kiss_fft_cpx freqdata);
/
input timedata has nfft scalar points
output freqdata has nfft/2+1 complex points
*/

However, it seems that kiss_fftr fills freqdata with data up to nfft complex points, causing an overflow when using a freqdata buffer with only nfft/2 + 1 complex points allocated. Is this the expected behavior? Am I missing something in the documentation?

I can post some example code if that helps.

BSD-3 Clause year and owner

Should the BSD license instead of and show the actual year and owner of the license?

how to use in swift 5

Hi, my app requires to calculate FF, so can I use in my swift project, if so can you tell the implementation.Thanks in advance.

Incorrect result when using int16 fixed point FFT

I met a problem when using int16 fixed point FFT, here is my mainly code

    kiss_fft_cpx cin[NFFT];
    kiss_fft_cpx cout[NFFT];
    kiss_fft_cfg  kiss_fft_state;
    memset(cin, 0, sizeof(short) * NFFT);
    memset(cout, 0, sizeof(short) * NFFT);
	while(fread(input, sizeof(short), NFFT, in))
	{
		for(int i=0; i<NFFT;i++)
		{
			cin[i].r = input[i];
			cin[i].i = 0;
		}
		kiss_fft_state = kiss_fft_alloc(NFFT, 0, 0, 0);
		kiss_fft(kiss_fft_state, cin, cout);
		kiss_fft_state = kiss_fft_alloc(NFFT, 1, 0, 0);
		kiss_fft(kiss_fft_state, cout, cin);

		for(int i=0; i<NFFT;i++)
		{
			output[i] = cin[i].r;
		}
		ret = fwrite(output, sizeof(short), NFFT, out);
	}

The input audio spectrum is

The output audio spectrum is

I have no idea where is wrong, can you give me some advice?

Question: Is it possible to build kissfft for both float and double in the same app?

I've tried creating a separate .cpp file for both float and double. The contents are:

#undef kiss_fft_scalar
#define kiss_fft_scalar float
#include "kiss_fft.c"

void kiss_fft_1d(const std::complex<float>* in,  std::complex<float>* out,  int n, int sign)
{
    kiss_fft_cfg cfg = kiss_fft_alloc(n, sign == +1 ? 1 : 0, 0, 0);
    kiss_fft(cfg, (const kiss_fft_cpx*)in, (kiss_fft_cpx*)out);
    kiss_fft_free(cfg);
}

and

#undef kiss_fft_scalar
#define kiss_fft_scalar double
#include "kiss_fft.c"

void kiss_fft_1d(const std::complex<double>* in, std::complex<double>* out, int n, int sign)
{
    kiss_fft_cfg cfg = kiss_fft_alloc(n, sign == +1 ? 1 : 0, 0, 0);
    kiss_fft(cfg, (const kiss_fft_cpx*)in, (kiss_fft_cpx*)out);
    kiss_fft_free(cfg);
}

but this doesn't work since function overloading doesn't work in a lot of places and you get multiple definitions of the same functions.

bfly load/stores

The bfly functions do multiple loads and stores of Fout
e.g.
C_ADDTO(*Fout,scratch[3]);

Code size and performance is improved by loading Fout at the top of the loop and storing it at the bottom, using registers for the operations.
On ARMv7 the bfly4 function main loop

Was
170 instructions
46 loads
36 stores

Now
140 instructions
35 loads
19 stores

This is bfly4 with the change:

static void kf_bfly4(
        kiss_fft_cpx * Fout,
        const size_t fstride,
        const kiss_fft_cfg st,
        const size_t m
        )
{
    kiss_fft_cpx *tw1,*tw2,*tw3;
    kiss_fft_cpx scratch[6];
    kiss_fft_cpx Fout0, Fout1, Fout2, Fout3;
    size_t k=m;
    const size_t m2=2*m;
    const size_t m3=3*m;


    tw3 = tw2 = tw1 = st->twiddles;

    do {
        Fout0 = Fout[0];
        Fout1 = Fout[m];
        Fout2 = Fout[m2];
        Fout3 = Fout[m3];
        C_FIXDIV(Fout0,4); C_FIXDIV(Fout1,4); C_FIXDIV(Fout2,4); C_FIXDIV(Fout3,4);

        C_MUL(scratch[0],Fout1 , *tw1 );
        C_MUL(scratch[1],Fout2 , *tw2 );
        C_MUL(scratch[2],Fout3 , *tw3 );

        C_SUB( scratch[5] , Fout0, scratch[1] );
        C_ADDTO(Fout0, scratch[1]);
        C_ADD( scratch[3] , scratch[0] , scratch[2] );
        C_SUB( scratch[4] , scratch[0] , scratch[2] );
        C_SUB( Fout2, Fout0, scratch[3] );
        tw1 += fstride;
        tw2 += fstride*2;
        tw3 += fstride*3;
        C_ADDTO( Fout0 , scratch[3] );

        if(st->inverse) {
            Fout1.r = scratch[5].r - scratch[4].i;
            Fout1.i = scratch[5].i + scratch[4].r;
            Fout3.r = scratch[5].r + scratch[4].i;
            Fout3.i = scratch[5].i - scratch[4].r;
        }else{
            Fout1.r = scratch[5].r + scratch[4].i;
            Fout1.i = scratch[5].i - scratch[4].r;
            Fout3.r = scratch[5].r - scratch[4].i;
            Fout3.i = scratch[5].i + scratch[4].r;
        }
        Fout[0]  = Fout0;
        Fout[m]  = Fout1;
        Fout[m2] = Fout2;
        Fout[m3] = Fout3;
        ++Fout;
    }while(--k);
}

HALF_OF multiplies by a double 0.5

When compiling with msvc 2013 I get this warning:

warning C4244: '=' : conversion from 'double' to 'float', possible loss of data

It looks like a bright mind figured this out before I did. credits to him!
steffen-kiess@a10e9c4

DIVSCALAR off by 1

The current fixed point DIVSCALAR multiplies by SAMP_MAX which is off by 1

#   define DIVSCALAR(x,k) \
    (x) = sround( smul(  x, SAMP_MAX/k ) )

which produces 0.999938965 / k instead of 1 / k. The value is rounded down, so the larger the k value, the higher the error

it should be

#   define DIVSCALAR(x,k) \
    (x) = sround( smul(  x, (1<<(FRACBITS))/k ) )

It is used in bfly functions like this:

C_FIXDIV(*Fout,2); C_FIXDIV(*Fout2,2);

These are all the instances

FIXDIV(c,div) \
FIXDIV( fk , 2 );
FIXDIV( fnkc , 2 );
FIXDIV( *Fout0,5); C_FIXDIV( *Fout1,5); C_FIXDIV( *Fout2,5); C_FIXDIV( *Fout3,5); C_FIXDIV( *Fout4,5);
FIXDIV(*Fout,2); C_FIXDIV(*Fout2,2);
FIXDIV(*Fout,3); C_FIXDIV(Fout[m],3); C_FIXDIV(Fout[m2],3);
FIXDIV(*Fout,4); C_FIXDIV(Fout[m],4); C_FIXDIV(Fout[m2],4); C_FIXDIV(Fout[m3],4);
FIXDIV(fpk,2);
FIXDIV(fpnk,2);
FIXDIV(scratchbuf[q1],p);
FIXDIV(scratch[q1],p);
FIXDIV(st->tmpbuf[0],2);
FIXDIV(tdc,2);

So 4 constants - 2,3,4,5 and p which is a factor, typically a prime number larger than 5.
FIXDIV(*Fout,2); in bfly2 becomes (v * 16387 + 16384) / 32768
which is accurate for values up to 16384, but off by 1 on larger values
e.g. FIXDIV(20000,2) = (20000 × 16383 + 16384) ÷ 32768 = 9999.889648438 which truncates to 9999.
With k = 4
32767/4 = 8191.
e.g. FIXDIV(20000,4) = (20000 × 8191 + 16384) ÷ 32768 = 4999.889648437 which truncates to 4999.
it should be
(20000 × 8192 + 16384) ÷ 32768 = 5000.5 which truncates to 5000.

mis-aligned sub-allocation in kiss_fftnd_alloc

I'm not sure if this is a known issue, but if I call kiss_fftnd_alloc with a 256x256 iFFT and USE_SIMD set to 1, I end up with misaligned memory.

I've traced the bug to kiss_fftnd_alloc packing several things into a single buffer and losing the 16-byte alignment of the parent block.

If this is not a known issue, I can attempt to fix this and submit a pull request. My plan was to add padding to the hand-built sub-allocation layout to put the actual numeric data back into the alignment of the parent block.

Any chance of a recent labelled release?

The last proper release was in 2012, and changes since then haven't been entered in the changelog.

I can just clone the current HEAD, but it'd be nice to have a proper release with a actual version number. Thanks!

---

Also, we've been using KissFFT for in-house and some specialty applications, and it's been extremely easy to use and trouble free. Thanks for releasing it!

`make install` attempts to install to system-root (`/kissfft`)

I'm cross-compiling and getting the following:

$ make install
[...]
[100%] Linking C static library libkissfft-float.a
[100%] Built target kissfft
Install the project...
-- Install configuration: ""
-- Installing: /my-custom-toolchain-path/usr/local/lib/libkissfft-float.a
CMake Error at cmake_install.cmake:53 (file):
  file cannot create directory: /kissfft.  Maybe need administrative
  privileges.

This has to do with:

kissfft/CMakeLists.txt

Lines 104 to 110 in 8f47a67

	#
	# Add GNUInstallDirs for GNU infrastructure before target)include_directories
	#
	if(CMAKE_SYSTEM_NAME MATCHES "^(Linux|kFreeBSD|GNU)$" AND NOT CMAKE_CROSSCOMPILING)
	include(GNUInstallDirs)
	endif()

I'm compiling for a "Generic" system (which will probably change as the CMake support in our toolchain improves), and I'm cross-compiling. So GNUInstallDirs is not included.

This breaks the next few lines break, because CMAKE_INSTALL_INCLUDEDIR was never set:

kissfft/CMakeLists.txt

Lines 112 to 117 in 8f47a67

	#
	# Declare PKGINCLUDEDIR for kissfft include path
	#
	set(PKGINCLUDEDIR "${CMAKE_INSTALL_INCLUDEDIR}/kissfft")
	message(STATUS "PKGINCLUDEDIR is ${PKGINCLUDEDIR}")

I think it's best to include GNUInstallDirs unconditionally. Although I'm not sure how deployment on Windows works.

It's worth noting that our toolchain is using a GNU toolchain layout with /usr/local/include (but it's also using clang in MSVC compatibility mode to compile for Windows - similar to cygwin/mingw, except it's neither of those).

MSVC static code analysis

MSVC 2019 warning about line 210.

kiss_fft.c(210): warning C6011: Dereferencing NULL pointer 'scratch'.
kiss_fft.c(222): warning C6385: Reading invalid data from 'scratch': the readable size is 'sizeof(kiss_fft_cpx)*p' bytes, but '16' bytes may be read.

Are these false positives?

how to use the kiss_fft?

Dear,
thanks to the great project,
but for a new one, It's a little difficult to test the kiss_fft,

so could you please give the main function ?
I just want to use a forward transform,
thx

Data stride in N-D FFTs

Your library works very nicely for a spatial distribution of 1D (i.e. scalar) data!
However, the transformation of 3D (i.e. vector) data can be more tricky, if the data is arranged as (x0,y0,z0, x1,y1,z1, ...).

Maybe I am misunderstanding how the APIs are supposed to be used, but it looks to me like one has to (for N vectors) create 3 arrays (x, y and z) of size N and subsequently do 3 FFTs. This would, in my use case, mean copying data back and forth.

This would be solved by adding a stride to the config or to the APIs. The corresponding initial offset is trivial, as one can simply pass the corresponding data pointer.
We tried adding a stride to the APIs, but got stuck in errors in the recursive function calls, which we do not sufficiently understand. It would be great if you could help out with this!

Might also be related to this feature request on source forge, but I don't want to create an account there just for this.

C++ header (and example applications) don't compile under MSVC++

Basically, there's a number of contexts that use C variable length arrays (it's apparently a C99 feature, and MSVC is a C90 only compiler).

Unfortunately, MSVC(++) doesn't support variable length arrays, and apparently probably never will. Apparently they suggest just using std::vector instead (though the page that was documented on has subsequently been removed. sigh. See here).

The demo programs not supporting MSVC isn't a big deal, but I would like to be able to use the C++ header wrapper. Additionally, variable length arrays in C++ (as opposed to C) are not technically part of the standard, so I suspect the fact that this works in GCC/Clang is a implementation oddment, and is arguably technically undefined to use them.

Anyways, compiler output:

2>c:\code\scfft\deps\kiss_fft\kissfft.hh(329): error C2131: expression did not evaluate to a constant
2>         c:\code\scfft\deps\kiss_fft\kissfft.hh(329): note: failure was caused by non-constant arguments or reference to a non-constant symbol
2>         c:\code\scfft\deps\kiss_fft\kissfft.hh(329): note: see usage of 'p'
2>         c:\code\scfft\deps\kiss_fft\kissfft.hh(327): note: while compiling class template member function 'void kissfft<float>::kf_bfly_generic(std::complex<float> *const ,const std::size_t,const std::size_t,const std::size_t) const'
2>         c:\code\scfft\deps\kiss_fft\kissfft.hh(121): note: see reference to function template instantiation 'void kissfft<float>::kf_bfly_generic(std::complex<float> *const ,const std::size_t,const std::size_t,const std::size_t) const' being compiled
2>         c:\code\scfft\cppsndlib\processsteps\intermediate\fft\fftstep.cpp(31): note: see reference to class template instantiation 'kissfft<float>' being compiled

In this case, it's pointing to the line cpx_t scratchbuf[p]; Replacing it with std::vector<cpx_t> scratchbuf( p ); solves the issue.

Merge changes of kissfft.hh from bazaar-projects/kissfft?

They created a repo from 1.3.0 source archive and made some changes on kissfft.hh
https://github.com/bazaar-projects/kissfft

Small FFT sizes fail with OPENMP

I while ago I had some weird issue when using kissfft in combination with OpenMP.
At that time I found a few threads mentioning the same issue
https://sourceforge.net/p/kissfft/discussion/278332/thread/b2809c8b/

and ended up with that fix:
if (fstride==1 && p<=5 && m!=1) //Fix from http://sourceforge.net/p/kissfft/bugs/10/

Now that the link above is dead, I'm not sure if that patch is still needed.

Make a radix 2 twiddle table once one and reuse?

Is there a way to create the twiddle table just once at program start, and reuse it for different fft sizes ( only for power of 2 fft sizes)? Other libraries typically do this, you just have to create a twiddle table once for the max size, then you use a stride to reuse the twiddle table for different size ffts

kiss_fastfir.c not working for fixed point numbers

Is there anything we could do to make it work ?

Thanks

Use versioned soname in shared library

Usually shared libraries have versioned soname which is incremented when a incompatible change is made.
The new kissfft shared lib doen't have this, it's soname is simply libkissfft.so.
When packaging for Fedora a versioned soname is mandatory, so I'm asking to add the version, like this in your Makefile::
SHARED := -Wl,-soname,libkissfft.so.0 -o libkissfft.so.0.1
The last number in the file name can be incremented independently when a new compatible version of the library is shipped.

Add some windowing algorithms?

I see that only the "pure" FFT is available, no windowing algorithm. Do you think it would be ok to add a small kiss_windowing.h/cpp to provide a bit of windowing ability (maybe a few of the more common, hann, hamming, would be great :) ).

How to calculate FFT

Hi, I need to calculate FFT, which class I need to import and what method I need to call. Please let me know. If any Documentation is there will help us great. Thanks.

Optimised build for sizes that are powers of 2

Currently the code allows for arbitrary numbers of samples in the input. This is great when you need it, but it requires a lot of code that remains unused when the input length is a power of 2.

It would be very helpful for users embedding this library into memory-constrained applications if there was a build option to disable support with sizes that are not powers of 2. In this configuration the kf_bfly3, kf_bfly5 and kf_bfly_generic functions could be left out altogether, which would save quite a bit of space in the binary.

Making it available to Arduino through a package

Thanks so much for an amazing package, this is super useful :)

Have you considered making this available to the Arduino ecosystem as a dedicated package? Currently there is only 1 FFT package available there out of the box, and I find it both undocumented, and low quality code when looking a bit into the source. Your code is much better on all aspects in my opinion.

I just tested your package on a Cortex-M4 based board, and your code is working brilliantly. All I had to do was to substitute your kiss_fft_scalar with the type I wanted to use (float in my case), though I think I could just have added a compilation flag, and everything worked perfectly.

I could look into making this into an Arduino package if you do not want to do it yourself, but are fine with the idea (will have to happen in a few weeks though, very busy now).

Usage of exit

Hi all

For embedded usage - NXP i.MX8 - I have problems with usage of exit(). We do not have it :-(
Would you be fine by having a pull request where exit() is wrapped into a macro - where every exit() becomes KISSFFT_EXIT()

#ifdef KISSFFTT_NO_EXIT 
#define KISSFFT_EXIT {}
#else 
#define KISSFFT_EXIT exit
#endif 

Question on fixed point scaling

Acc. to the docs, fixed point FFT performs scaling (both ways) because of overflow issues. Is it possible to inhibit the scaling so it works the same as for floating point?