[PD] fft~ bug in Pd-0.46-7-64bit.app on OSX
Matt Barber
brbrofsvl at gmail.com
Mon Oct 19 22:08:10 CEST 2015
Seems fine, since the 2-pt FFTs are trivial to compute if needed. And the
rfft/rifft objects already throw an error for block < 4.
One use case for the smaller FFTs is that since they can be computed on
paper as a direct DFT pretty easily (4 and 8 points especially), the Pd
objects make great illustration for teaching purposes. "We did the
calculation. Here's what we expect; let's see if Pd agrees."
On Mon, Oct 19, 2015 at 2: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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puredata.info/pipermail/pd-list/attachments/20151019/1ee10347/attachment-0001.html>
More information about the Pd-list
mailing list