mborgerding / kissfft Goto Github PK
View Code? Open in Web Editor NEWa Fast Fourier Transform (FFT) library that tries to Keep it Simple, Stupid
License: Other
a Fast Fourier Transform (FFT) library that tries to Keep it Simple, Stupid
License: Other
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
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);
}
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.
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:
Lines 104 to 110 in 8f47a67
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:
Lines 112 to 117 in 8f47a67
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).
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.
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.
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.
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?
I was wondering if you would accept a pull request to add Arduino Support which contains the following changes
#if defined(ARDUINO) && !defined(IGNORE_ARDUINO_CONFIG)
#include "kiss_arduino_config.h"
#endif
With these changes the project can be used as Arduino library...
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);
}
I have no idea where is wrong, can you give me some advice?
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
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!
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.
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.
Is there anything we could do to make it work ?
Thanks
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
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.
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;
}
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.
Line 129 in 1efe720
Shouldn't this be (note the zero) ?
/// stored in @c dst[0].real() and @c dst[0].imag() respectively.
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
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 :) ).
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.
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).
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
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.
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>
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.
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 ?
kissfft on ARMv7 with fixed point is slow. A neon version would improve performance quite a bit.
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.
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
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
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.
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.
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.
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.
They created a repo from 1.3.0 source archive and made some changes on kissfft.hh
https://github.com/bazaar-projects/kissfft
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.
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.
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?
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:
Lines 104 to 110 in 8f47a67
GNUInstallDirs should be included unconditionally. That is what most projects do. See glfw, portaudio, SQLiteCPP.
Otherwise one cannot use the install step on windows.
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?
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.
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)...
Should the BSD license instead of and show the actual year and owner of the license?
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
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?
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
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).
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.