DOCSEARCHbyAlgolia
Submit Docs

KISS FFT

repository·master·Indexed 24 days ago

https://github.com/mborgerding/kissfft

A simple and efficient mixed-radix Fast Fourier Transform library for C programs. It supports both fixed-point and floating-point data types (float, double, int16_t, int32_t) and provides 1-D complex FFTs. Additional features include multi-dimensional FFTs, real-optimized FFTs, fast convolution FIR filtering, and SIMD extensions for batch processing on Intel x86 machines with SSE.

Tokens
1.7K
Snippets
4
Records
8
Agent score
34%

What's inside kissfft

  1. Build KISS FFT with Make or CMake

    master

    KISS FFT supports both Make and CMake build systems. You can configure the principal datatype, enable OpenMP, and choose between static or shared libraries.

    Configuration Options

    Option (Make)Option (CMake)Description
    KISSFFT_DATATYPE-DKISSFFT_DATATYPEData type: float (default), double, int16_t, int32_t, or simd (requires SSE)
    KISSFFT_OPENMP-DKISSFFT_OPENMPEnable OpenMP support (set to 1 or ON)
    KISSFFT_STATIC-DKISSFFT_STATICBuild a static library (1/ON) instead of a shared library
    KISSFFT_TOOLS-DKISSFFT_TOOLSBuild command-line tools (default is enabled; set to 0 or OFF to disable)
    KISSFFT_USE_ALLOCA-DKISSFFT_USE_ALLOCAUse alloca instead of malloc/free
    PREFIX-DCMAKE_INSTALL_PREFIXInstallation prefix directory

    Build Examples

    Using Make (Static library, int16_t, OpenMP):

    make KISSFFT_DATATYPE=int16_t KISSFFT_STATIC=1 KISSFFT_OPENMP=1 all

    Using CMake (Static library, int16_t, OpenMP):

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

  2. Run KISS FFT tests

    master

    To validate your build, you can run specific tests or the full suite.

    Single test (Make):

    make KISSFFT_DATATYPE=int16_t KISSFFT_STATIC=1 KISSFFT_OPENMP=1 testsingle

    All tests (CMake):

    make test

    Extended Testsuite (All configurations): Run this from the source tree to test all possible build configurations. Note that this takes approximately 20-40 minutes.

    sh test/kissfft-testsuite.sh

  3. Use SIMD extensions for batch FFT processing

    master

    The SIMD extensions in kissfft allow you to perform 4 separate FFTs simultaneously, potentially providing a 2-3x speedup on Intel x86 machines with SSE.

    Instead of processing one signal, a single FFT call processes four signals (A, B, C, and D) at once. This requires a specific data layout where elements from the four signals are interleaved into __m128 packed float types.

    Data Layout

    For Complex Data: The real and imaginary parts are interleaved as follows: rA0, rB0, rC0, rD0, iA0, iB0, iC0, iD0, rA1, rB1, rC1, rD1, iA1, iB1, iC1, iD1 ... (where rA0 is the real part of the 0th sample for signal A).

    For Real-only Data: The data is laid out as: rA0, rB0, rC0, rD0, rA1, rB1, rC1, rD1, ...

  4. Enable SIMD extensions via compiler flags

    master

    To use the SIMD features, you must define USE_SIMD=1 and enable the appropriate instruction set (e.g., -msse) during compilation. It is recommended to use high optimization levels like -O3.

    Example GCC flags:

    -O3 -mpreferred-stack-boundary=4 -DUSE_SIMD=1 -msse

  5. Troubleshoot KISS FFT output issues

    master

    If the FFT output is not what you expect, check the following:

    1. Scaling: Check if there is a constant multiplier required between your output and the expected result. Note that the floating-point version performs no scaling for speed, while the fixed-point version scales both ways to prevent overflow.
    2. Mixed Build Environment: Ensure all code is compiled with the same preprocessor definitions for FIXED_POINT and kiss_fft_scalar.

  6. Perform a 1-D complex FFT

    master

    To perform a 1-D complex Fast Fourier Transform, you need to allocate a configuration object using kiss_fft_alloc, pass your input data to kiss_fft, and then free the configuration.

    Data Layout:

    • Frequency-domain data is stored from DC up to $2\pi$.
    • cx_out[0] is the DC bin.
    • cx_out[nfft/2] is the Nyquist bin (if it exists).

    Available Extras: Beyond basic 1-D FFTs, the tools/ directory provides:

    • Multi-dimensional FFTs
    • Real-optimized FFTs (returns $nfft/2 + 1$ complex frequency bins)
    • Fast convolution FIR filtering (not available for fixed point)
    • Spectrum image creation
        #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);

  7. Avoid segfaults by ensuring SIMD alignment

    master
    When using SIMD, memory alignment is critical. The kissfft implementation uses scratch variables on the stack, and with SIMD enabled, these must have addresses on 16-byte boundaries. Failure to ensure this alignment is the most likely cause of segmentation faults.

  8. Pack and unpack data for SIMD FFTs

    master

    Because the SIMD API requires a specific interleaved format, you must transpose your data from standard arrays to the SIMD-ready format (and back).

    Below are example utility functions (SSETools::pack128 and SSETools::unpack128) provided by the community to perform these 4xN and Nx4 transpositions. Use these at your own risk.

    void SSETools::pack128(float* target, float* source, unsigned long size128)
{
   __m128* pDest = (__m128*)target;
   __m128* pDestEnd = pDest+size128;
   float* source0=source;
   float* source1=source0+size128;
   float* source2=source1+size128;
   float* source3=source2+size128;

while(pDest<pDestEnd)
   {
       *pDest=_mm_set_ps(*source3,*source2,*source1,*source0);
       source0++;
       source1++;
       source2++;
       source3++;
       pDest++;
   }
}

void SSETools::unpack128(float* target, float* source, unsigned long size128)
{

float* pSrc = source;
   float* pSrcEnd = pSrc+size128*4;
   float* target0=target;
   float* target1=target0+size128;
   float* target2=target1+size128;
   float* target3=target2+size128;

while(pSrc<pSrcEnd)
   {
       *target0=pSrc[0];
       *target1=pSrc[1];
       *target2=pSrc[2];
       *target3=pSrc[3];
       target0++;
       target1++;
       target2++;
       target3++;
       pSrc+=4;
   }
}