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.
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
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....).
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@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@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
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; ========================
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@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.... ).
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@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@lists.iem.at mailing list UNSUBSCRIBE and account-management ->
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@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@gmail.com mailto:katjavetter@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.... 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@urbanstew.org mailto:robert@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@lists.iem.at mailto:Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list http://lists.puredata.info/listinfo/pd-list
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@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@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@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.... ).
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@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@lists.iem.at mailing list UNSUBSCRIBE and account-management ->
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@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@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@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@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....).
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@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@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
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@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@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@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@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....).
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@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@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
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@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@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@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@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@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.... ).
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@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@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management ->
hi, I'd like to pick up this thread after stumbling on it in the archive. For the same reason that Matt explained I'd like to see rfft~ working for small blocks of 4 to 32 samples. best, marius.
2015-10-19 22:08 GMT+02:00 Matt Barber brbrofsvl@gmail.com:
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@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@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@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@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@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.
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@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@lists.iem.at mailing list > UNSUBSCRIBE and account-management -> > http://lists.puredata.info/listinfo/pd-list
Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/
listinfo/pd-list
Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/ listinfo/pd-list
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@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@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@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@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@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....).
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@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@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list