[PD] fft~ bug in Pd-0.46-7-64bit.app on OSX
katja
katjavetter at gmail.com
Sun Dec 31 13:02:53 CET 2017
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 <msp at ucsd.edu> 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 <brbrofsvl at gmail.com> 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 <robert at urbanstew.org> 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 <brbrofsvl at gmail.com> 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 <katjavetter at gmail.com> 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 <robert at urbanstew.org>
>> >>> 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
>> >>> > _______________________________________________
>> >>> > Pd-list at lists.iem.at mailing list
>> >>> > UNSUBSCRIBE and account-management ->
>> >>> > http://lists.puredata.info/listinfo/pd-list
>> >>
>> >>
>> >>
>> >
>>
>> _______________________________________________
>> Pd-list at lists.iem.at mailing list
>> UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
More information about the Pd-list
mailing list