KVR Audio

k-acid · Post by **k-acid** » Tue Dec 04, 2012 7:20 pm

Hello

I need a good fft library that provides source code and does not have a GPL.

I've been recommended KISS fft but wondered if anyone has any other recommendations.

I need source code as I want to be able to use it on multiple platforms like ios and android so something written in C would be perfect!

liquidsonics · Post by **liquidsonics** » Tue Dec 04, 2012 8:05 pm

Consider this perhaps: http://www.kurims.kyoto-u.ac.jp/~ooura/fft.html

I learnt about this from the FFTW benchmark page a while ago and was moderately happy with the performance but don't use it any longer. Have you not considered using FFTW (which I gather from a very Google search can be used on Android) and Accelerate on iOS? I'd be tempted to use the best available on each platform and put a wrapper around it to simplify your coding.

Music Engineer · Post by **Music Engineer** » Tue Dec 04, 2012 8:06 pm

k-acid wrote:Hello

I need a good fft library that provides source code and does not have a GPL.

I've been recommended KISS fft but wondered if anyone has any other recommendations.

I need source code as I want to be able to use it on multiple platforms like ios and android so something written in C would be perfect!

i like:

http://www.kurims.kyoto-u.ac.jp/~ooura/fft.html

i once benchmarked it against kiss-fft, stefan bernsee's routine and a self-written one and this one was the winner. needless to say, that my own was slowest. i didn't measure against fftw and ipp though - i guess, they are still faster. last time i checked, kiss-fft appeared to support arbitrary length fft, so i suppose (but didn't check), it implements also the bluestein algorithm which could be a big plus, if you need that.

lkjb · Post by **lkjb** » Tue Dec 04, 2012 8:07 pm

Another possibility might be FFTReal (link). As the name suggests it only works for real signals in the time domain.

liquidsonics · Post by **liquidsonics** » Tue Dec 04, 2012 8:07 pm

Robin from www.rs-met.com wrote:i didn't measure against fftw and ipp though - i guess, they are still faster.

I checked against them both, and it was beaten fairly convincingly, motivating my move to use Intel IPP.

k-acid · Post by **k-acid** » Tue Dec 04, 2012 8:36 pm

wow! Thanks for quick responses

I looked at FFTW but was put off by the GPL. As I understand the GPL you have to provide a source code to anything that links to code covered by it.

Yes, I will probably use the vDSP api for ios but was hoping to get something simple for android, possibly using JNI and a C lib.

Like liquidsonics says I can use an interface to abstract the fft code and hide the implementation details below this. After it only needs an array of complex. Maybe using one lib will be too much of a ease of use / performance trade off esp as its the part of the code what will be 'always on' or used most.

BTW im writing some Real-Time audio analysis tools mainly for fun tbh but I do have a few pro musicians interested so want to do a good job. Though I suspect the real pain for me will be the UI

jpommier · Post by **jpommier** » Sat Dec 08, 2012 10:26 am

You may want to try this one also: https://bitbucket.org/jpommier/pffft (bsd licensed)

Music Engineer · Post by **Music Engineer** » Sat Dec 08, 2012 11:20 am

jpommier wrote:You may want to try this one also: https://bitbucket.org/jpommier/pffft (bsd licensed)

hi Julien,

and thanks for making this library available. but i have no idea how to read the benchmark results. what exactly do these numbers show?

edit: "pffft" is a nice name, by the way

jpommier · Post by **jpommier** » Sat Dec 08, 2012 7:31 pm

It is the number of mflops achieved by each lib, with the number of floating point operations being defined as 5Nlog2(N) for a length N complex fft, and 2.5*Nlog2(N) for a real fft (so it is not an actual flop count, but it is just a good mean to compare various fft implementations). So the higher it is the better it is.

DaveHoskins · Post by **DaveHoskins** » Sat Dec 08, 2012 7:54 pm

jpommier wrote:It is the number of mflops achieved by each lib, with the number of floating point operations being defined as 5Nlog2(N) for a length N complex fft, and 2.5*Nlog2(N) for a real fft (so it is not an actual flop count, but it is just a good mean to compare various fft implementations). So the higher it is the better it is.

Hey, I might have a look at your lib, what's the data format for the real FFT?
It looks like it uses exact FFT length for the results, is that correct?

jpommier · Post by **jpommier** » Sun Dec 09, 2012 3:59 pm

DaveHoskins wrote:Hey, I might have a look at your lib, what's the data format for the real FFT?
It looks like it uses exact FFT length for the results, is that correct?

Yes, if F(i) is the FFT of an array of length N, the "ordered" fft functions store it as:

real(F(0)) imag(F(N/2)) real(F(1)) imag(F(1)) real(F(2)) imag(F(2)) ... imag(F(N/2-1))

DaveHoskins · Post by **DaveHoskins** » Sun Dec 09, 2012 4:42 pm

"real(F(0)) imag(F(N/2)) real(F(1)) imag(F(1)) real(F(2)) imag(F(2)) ... imag(F(N/2-1))"

Sorry, I'm being a bit woolly-Sunday today, there's only one output buffer, so I'm guessing F(2) cannot be both real and imaginary at the same time?
Is it either interleaved RE(0), IM(1), RE(2)...IM(N-1)
Or it's REAL(0 to (N/2)-1) and IMAG(N/2 to N-1) inclusive?
The latter is what I was looking for with SSE convolution.

Also, can the output buffer be the same location as the input buffer?

Thanks again.

Dave.

jpommier · Post by **jpommier** » Sun Dec 09, 2012 5:54 pm

Yes the output of pffft_transform_ordered() is interleaved -- but for real tranforms, the first complex number is a special case, it is RE(0)+i*IM(N/2) (since IM(0) = 0 and RE(N/2) = 0 and there is no room to store them in a length N array)

If you want to perform convolution , it is more efficient to use pffft_transform() instead of pffft_transform_ordered() , and do the multiplication of complex coefficients with pffft_zconvolve_accumulate function, as the fft output will be stored in a more sse-friendly ordering.

The input and output can be the same.

table · Post by **table** » Mon Apr 29, 2013 10:56 pm

Hi,

thanks for pffft jp!
btw, have you ever benchmarked pffft against kissfft ?

the output of pffft_transform_ordered() is interleaved

And how is the array stored when it is not ordered (when it's created by pffft_transform) ?

is it something like that ? :
real(F(0)) real(F(1)) ...real(F(N/2-1) imag(F(N/2)) imag(F(1)) ... imag(F(N/2-1))

thanks!

xoxos · Post by **xoxos** » Tue Apr 30, 2013 6:35 pm

i'm using the fft code from dspguide.com, which i cannot place on the fftw comparison charts... i removed the zr[]/zi[] transcendentals as they only need to be generated for the window length), usually runs about 2% of a 1.6g cpu.

looking at the ~ooura package, there's a 75kb zip. attempting to use a library or sdk generally leaves me with lasting psychological scars, and while 75kb is relatively non-intimidating,

can anyone estimate the threat to my continued sense of well-being should i attempt to open that zip and find the bits to replace the dspguide.com code i use?