Supporting rfft~ and rifft~

[jameysharp]

I heard from https://hackers.town/@JoshuaACNewman that there are open questions about how to implement FFT support in hvcc. I don't know anything about PD or Heavy, but I do know a thing or two about FFTs, dataflow languages, and compilers, and wanted to offer some help. I don't want to hang out in a Discord though so I thought I'd see if folks would be interested in having a conversation here.

I'm having trouble making sense of Heavy's ir2c generator, but if I'm reading it correctly, it looks like the main difficulty is that every signal block takes one sample at a time, or at most, one SIMD vector of samples at a time. That would be troublesome since an FFT necessarily has to wait for N samples to arrive before it can produce any output, where N is the length of the FFT.

I see from the example of SignalConvolution that a signal block can keep a ring-buffer of past inputs in local state. I think that pattern should work for FFTs as well: every time an input sample arrives, save it in the ring buffer, and when the ring buffer wraps, compute the FFT or inverse FFT of the whole buffer.

The other difficulty is it looks like signal blocks are synchronous: they must produce an output sample for every input sample. A length-N FFT introduces N samples worth of latency, so there's no meaningful value to output for the first N samples. That's okay as long as PD's semantics allow emitting N samples of zeroes at the beginning. Does it?

If there aren't any other challenges I've missed, then I think this is… relatively straightforward, and I'd be happy to chat further about how to make it work.

[dromer]

Thank you a lot for the input @jameysharp !
Do note that Heavy does not contain a line of PD code. Essentially it emulates a PD DSP graph using its own internal library.

Very cool to hear that this has some possibility to be implemented, however even though I took over maintenance of the project I know very little about the internal workings of Heavy, or about programming DSP code in general. So any help with this is certainly appreciated.

[dromer]

I did a little test by adding a

sendFloatToReceiver(0xB5B01859, static_cast<float>(n4)); // send to __hv_blocksize

to the main process() function and this will send the current actual block size to a special receiver object that we can query to at least set normalization. Possibly we can query this receiver from the rfft~ functions as well.

[dromer]

@jameysharp I'm staring a bit more at this now (and putting some first tries in generating code for it) but I'm a bit confused to how we can get separate real and imaginary parts out of (and into) pffft_transform_ordered.

[dromer]

Ah, from these notes it appears that the imaginary part is interleaved and there are two possible layouts for this (for which you suggested the ordered one): https://chromium.googlesource.com/chromium/src/+/master/third_party/pffft/README.md

So I suppose that will need some manual (un)tangling to set up the buffer correctly (I have no experience with this).

[dromer]

@jameysharp when you have time please take a look at #110 which should hopefully have most parts needed. Still very much WIP (and pseudo) on the HvSignalRFFT code.

[dromer]

Reading back to what you said before @jameysharp "I'm guessing it's one sample in, one sample out." I believe this depends on the SIMD implementation. The buffers that are used can be either 1, 4 or 8 value structures.

I indeed noticed that pffft_transform_ordered() requires single float values, so I assume that we have to iterate over this array and run it through the fft function?

[dromer]

I took a bit of a dive into the internals and SignalConvolution is actually related to an implementation of a conv~ object which does not exist in Pure Data, but (together with lorenz~) has some heavy-specific code. It's unknown to me where it originates from.

It will take some piecing together from various other objects to better understand how to implement rfft~/rifft~ further "up" the chain.

[dromer]

Potential implementation from Emilie Gillet that at least works on embedded/STM32 target (MIT): https://github.com/electro-smith/DaisyExamples/blob/master/field/Nimbus/shy_fft.h

[falkTX]

that doesnt look suitable for dpf/plugins, as it relies on input vs output buffers being different.
on quite a few hosts they are the same, reused for saving on cpu, often called "inplace processing".

I have used pffft before, can recommend it. supports both neon and sse, plus has a license compatible with DPF and commercial plugins

[dromer]

Do you think pffft is also suitable for STM32?

[falkTX]

that I have no idea, was mostly thinking about audio plugins here
since pffft is just common C code, I dont see why not

[dromer]

Some more docs on rfft~ usage in pd: http://www.pd-tutorial.com/english/ch03s08.html