Minimum FFT size is still not fixed in pd 0.48-1test3. I verified that 4 point works as expected for all FFT objects (fft~, ifft~, rfft~ and rifft~) if this conditional check is changed in function ooura_init():
"if (n < 64)" becomes "if (n < 4)" By the way I used a 16 point FFT to quickly test a wild idea. Without the small FFT it would have taken much more time to reveal that it was indeed a fata morgana. So, yes, very useful (as a time-saver in this case). Katja On Mon, Oct 19, 2015 at 8:26 PM, Miller Puckette <[email protected]> wrote: > I'm not sure, but I think I had limited it to 64 because some older FFT > package I was using had that limit. I'm not sure but I think the rfft > objects require at least 4 points to work properly. So perhaps it would be > OK to impose 4 as a minimum for all the FFT objects. > > In any case, there certainly should have been an error message... it simply > never occurred to me that anyone would want an FFT of fewer than 64 points :) > > M > > > On Sat, Oct 17, 2015 at 10:59:00AM +0200, katja wrote: >> OOURA's cdft and rdft function descriptions clearly state that FFT >> size 2 is the minimum. Maybe the data permutation is trickier for >> block size < 64. The old arrangement was weird, you don't get an array >> with complex numbers, but the imaginary output appearing in reversed >> order after the real output. Because the FFT functions are in Pd's API >> it is still rearranged that way (and the object has to rearrange again >> when copying to the outlet). I don't know if this hampers FFT size < >> 64, this is just a wild guess. >> >> Anyway I don't like this limitation at all. Small FFT sizes can be >> indispensable in rigid tests and experiments. >> >> Katja >> >> Katja >> >> On Sat, Oct 17, 2015 at 4:17 AM, Matt Barber <[email protected]> wrote: >> > Looking closer, it appears the OOURA fft has special routines for n<64... >> > but it uses those routines regularly as subroutines in larger ffts. In any >> > case it looks like the smaller block sizes are intended to be usable in the >> > code itself, but Miller must've had a reason not to trust them. Here's the >> > main OOURA complex fourier transform subroutine, which calls a bunch of >> > others, which all call smaller ones. The Pd prologue code would make sure >> > that none of the smaller cases at the bottom would ever be called. >> > >> > ======================================= >> > void cftfsub(int n, FFTFLT *a, int *ip, int nw, FFTFLT *w) >> > { >> > void bitrv2(int n, int *ip, FFTFLT *a); >> > void bitrv216(FFTFLT *a); >> > void bitrv208(FFTFLT *a); >> > void cftf1st(int n, FFTFLT *a, FFTFLT *w); >> > void cftrec4(int n, FFTFLT *a, int nw, FFTFLT *w); >> > void cftleaf(int n, int isplt, FFTFLT *a, int nw, FFTFLT *w); >> > void cftfx41(int n, FFTFLT *a, int nw, FFTFLT *w); >> > void cftf161(FFTFLT *a, FFTFLT *w); >> > void cftf081(FFTFLT *a, FFTFLT *w); >> > void cftf040(FFTFLT *a); >> > void cftx020(FFTFLT *a); >> > #ifdef USE_CDFT_THREADS >> > void cftrec4_th(int n, FFTFLT *a, int nw, FFTFLT *w); >> > #endif /* USE_CDFT_THREADS */ >> > >> > if (n > 8) { >> > if (n > 32) { >> > cftf1st(n, a, &w[nw - (n >> 2)]); >> > #ifdef USE_CDFT_THREADS >> > if (n > CDFT_THREADS_BEGIN_N) { >> > cftrec4_th(n, a, nw, w); >> > } else >> > #endif /* USE_CDFT_THREADS */ >> > if (n > 512) { >> > cftrec4(n, a, nw, w); >> > } else if (n > 128) { >> > cftleaf(n, 1, a, nw, w); >> > } else { >> > cftfx41(n, a, nw, w); >> > } >> > bitrv2(n, ip, a); >> > } else if (n == 32) { >> > cftf161(a, &w[nw - 8]); >> > bitrv216(a); >> > } else { >> > cftf081(a, w); >> > bitrv208(a); >> > } >> > } else if (n == 8) { >> > cftf040(a); >> > } else if (n == 4) { >> > cftx020(a); >> > } >> > } >> > ======================================= >> > >> > On Fri, Oct 16, 2015 at 7:43 PM, Robert Esler <[email protected]> wrote: >> >> >> >> Sorry I checked your patch again. I get the same behavior. I had an >> >> older version of Pd I was using. >> >> >> >> Yes, I just noticed this too. It appears OOURA limits the calculation to >> >> a block size of 32 or higher. Why? The code is so horribly documented >> >> I’d >> >> rather not even try to figure it out. >> >> >> >> Pd also has the option of using the FFTW3 library by Thomas Grill, which >> >> on a surface reading doesn’t seem to have a block boundary. But I can’t >> >> be >> >> sure w/o trying it. Of course this would require a manual compiling of >> >> Pd. >> >> >> >> Not sure why the mayer fft lib was removed, but this is one of the few >> >> instances of Pd breaking older patches. Maybe this needs to be a dev >> >> request? At the very least print an error to the Pd window. >> >> >> >> -Rob >> >> >> >> P.S - I have a C++ version of the old mayer_fft that I could probably wrap >> >> into a Pd object if it seems like this is a big enough problem. >> >> >> >> >> >> On Oct 16, 2015, at 4:09 PM, Matt Barber <[email protected]> wrote: >> >> >> >> OK, looking at the OOURA code, the init routine has this: >> >> >> >> ======================== >> >> static int ooura_init( int n) >> >> { >> >> n = (1 << ilog2(n)); >> >> if (n < 64) >> >> return (0); >> >> ======================== >> >> >> >> >> >> then later in the fft/ifft routine: >> >> >> >> ======================== >> >> if (!ooura_init(2*n)) >> >> return; >> >> ======================== >> >> >> >> and rfft: >> >> ======================== >> >> if (!ooura_init(n)) >> >> return; >> >> ======================== >> >> >> >> >> >> >> >> since these operate directly on samples in the signal vector, it will pass >> >> signals in small blocks without performing dft. I don't know what this is >> >> supposed to avoid. I've used fft in small block sizes before, and I can't >> >> be >> >> the only one whose patches might be broken by this. >> >> >> >> >> >> >> >> On Fri, Oct 16, 2015 at 5:33 PM, katja <[email protected]> wrote: >> >>> >> >>> If I understand the fft files correctly OOURA is now the default, but >> >>> 'disguised' as mayer fft so the old API should remain valid. >> >>> >> >>> (http://sourceforge.net/p/pure-data/pure-data/ci/master/tree/src/d_fft_fftsg.c). >> >>> >> >>> Indeed I get the same result for Matt's test patch with Pd 0.46-5 >> >>> which is on my system. Sinusoids for block size 8 and 16, instead of >> >>> spectrum points. >> >>> >> >>> A while ago I've been reading in OOURA fft code and what I remember >> >>> is, Pd uses its mixed radix functions. Not sure about it though. >> >>> >> >>> Katja >> >>> >> >>> >> >>> On Fri, Oct 16, 2015 at 10:00 PM, Robert Esler <[email protected]> >> >>> wrote: >> >>> > >> >>> > As far as I know Pd stopped using the mayer fft library in .46, which >> >>> > is probably why this is new behavior. I only get what you’re >> >>> > experiencing >> >>> > with a block size of 8. Otherwise, it seems to perform as expected. >> >>> > To really understand if this is a bug or not is to know which fft >> >>> > library is being used for OS X. My guess is it’s the OOURA but it’s >> >>> > not >> >>> > clear from looking at [fft~] object code that comes with distribution. >> >>> > You could also download the old library and recompile Pd, but I doubt >> >>> > it’s worth it. >> >>> > -Rob >> >>> > ------- >> >>> > Hi list, >> >>> > >> >>> > There's either a major bug in the [fft~] objects in Pd-0.46.7 (64bit >> >>> > OSX) >> >>> > or I'm going crazy. I'd love to see if others can reproduce it. >> >>> > >> >>> > Basically, for [block~] sizes less than 32 bits, [fft~] doesn't perform >> >>> > -- >> >>> > it just passes the signal through unchanged. [ifft~] does the same. The >> >>> > [rfft~]-[rifft~] is a little more complicated -- it passes signal >> >>> > through >> >>> > but zeroes out the last N/2 for [block~] sizes less than 64. >> >>> > >> >>> > >> >>> > See the attached patch, which only shows [fft~]. The saved contents of >> >>> > the >> >>> > tables on opening are the results for [block~ 8] on my machine, for >> >>> > quarter-nyquist at 44100. >> >>> > >> >>> > I've never seen this before in other versions of Pd. Anyone else get >> >>> > this >> >>> > behavior? >> >>> > >> >>> > Matt >> >>> > _______________________________________________ >> >>> > [email protected] mailing list >> >>> > UNSUBSCRIBE and account-management -> >> >>> > http://lists.puredata.info/listinfo/pd-list >> >> >> >> >> >> >> > >> >> _______________________________________________ >> [email protected] mailing list >> UNSUBSCRIBE and account-management -> >> http://lists.puredata.info/listinfo/pd-list _______________________________________________ [email protected] mailing list UNSUBSCRIBE and account-management -> https://lists.puredata.info/listinfo/pd-list
