zero_latency_convolver.hpp File Reference

Runtime zero-latency convolver; scheduling support and design constants are provided by zero_latency_convolver_support.hpp. More...

#include <pulp/signal/zero_latency_convolver_support.hpp>
#include <pulp/simd/simd.hpp>

Go to the source code of this file.

Classes
class	pulp::signal::ZeroLatencyConvolverT< SampleType >
	See the file doc block for the schedule and its lineage. More...

Namespaces
namespace	pulp
namespace	pulp::signal

Typedefs
using	pulp::signal::ZeroLatencyConvolver = ZeroLatencyConvolverT<float>
using	pulp::signal::ZeroLatencyConvolver64 = ZeroLatencyConvolverT<double>

Detailed Description

Runtime zero-latency convolver; scheduling support and design constants are provided by zero_latency_convolver_support.hpp.

Zero-latency non-uniform partitioned convolution (direct FIR head + doubling FFT tail), with the IR ingest policy — resample, DC-block, Schroeder tail trim, normalization — that makes an arbitrary measured impulse response usable at any session rate.

RT contract: prepare(sample_rate, max_block, channels) and load_impulse_response(...) MAY allocate (FFT scratch, partition spectra, input-history rings, predelay ring). process(...), reset(), and every set_* allocate NOTHING and take no locks on the audio thread. All FFT work for a block is bounded by the distributed schedule described below — there is no "if behind, catch up" branch, so a late host block cannot cascade. latency_samples() is the literal constant 0.

Why this ships alongside NonUniformPartitionedConvolverT, not inside it

convolver_non_uniform.hpp already implements a two-stage Gardner convolver: an overlap-save head at the host block size B plus one larger-block tail at K*B (K = 4 by default). It is correct and it is also zero-latency. It is deliberately left alone, because the two blocks answer different questions and merging them would make one of them worse:

• NonUniformPartitionedConvolverT is a two-stage engine. Its tail is a single uniform partition size, so a 1.4 s IR at B = 128, K = 4 becomes 127 partitions of 512 taps — the per-sample cost grows LINEARLY with IR length past the head. It also runs its whole tail transform inside the one block where its frame closes. For the short IRs it is used with (a few thousand taps) that is the right, simple engine and it should keep its ~280-line shape.
• ZeroLatencyConvolverT is the geometric engine: partition sizes double, so per-sample cost grows as O(log M) in IR length, and every transform larger than the host block is sliced across the samples of its own scheduling margin so the worst block costs about what the mean block costs. It also owns the IR-ingest policy (resampling, normalization, tail trim), true-stereo 2x2 routing, and the send/mix section.

Folding the geometric schedule into the two-stage class would replace its entire body, and every existing caller would pay the ingest and scheduling machinery it does not use. They share the same published lineage (Gardner 1995) at different altitudes, which is why this header names the other one here rather than duplicating its rationale.

M22 (speaker/cabinet emulation) is this module's sibling: the sampled-IR path is this class, the physics path is M22's. M22 should cite ZeroLatencyConvolverT + IrNormalizeMode::peak for its cabinet-IR loader (see the cookbook at the bottom of this file) and must not restate the partitioning, ingest, or latency argument.

The schedule, and why it is not the pure-doubling one

Split the convolution by delay: y[n] = sum_k h[k] x[n-k] becomes a direct time-domain FIR over h[0, N0) plus a set of frequency-domain partitions over disjoint ranges of h. A partition of block length L covering IR delays [d, d+L) runs overlap-save at FFT size K = 2L; the frame that closes at input time T produces the output samples [T+d-L+1, T+d], so its scheduling margin — the time between the frame closing and the first output it owns falling due — is

margin = d - L + 1                                                  (*)

Gardner's zero-latency result is that a partition may take up to its margin to compute and still be on time (Gardner 1995). Load balancing needs margin >= L, i.e. d >= 2L - 1: only then can a length-L transform be spread over the L samples before it is due.

The pure-doubling schedule (head [0, N0), then one partition of length L_i covering [L_i, 2 L_i)) sets d = L, which by (*) gives a margin of one sample at every level — not L_i. It is arithmetically correct as a partition of the convolution, but it cannot be sliced: every level must run its whole transform in the block where its frame closes, and the largest level's transform then lands entirely in one audio block. That is exactly the peak this design is supposed to remove.

The shipped schedule is Gardner's canonical two-partitions-per-size form, stated here in the one shape that makes it uniform:

a GROUP of block length L holds two partitions of length L and covers
the IR range [2L, 4L)

with L_g = L_min * 2^g, L_min = N0/2, so group g covers [N0 * 2^g, N0 * 2^(g+1)) and the groups tile [N0, N0 * 2^P) exactly. The binding margin is the first partition's, 2L - L + 1 = L + 1 — one full period, which is what makes slicing legal. Both partitions in a group have delays differing by L, so they share one forward and one inverse transform through a frequency-domain delay line (the uniform sub-convolver / FDL of Garcia 2002 and Wefers 2015), and the group's per-sample cost is

10 * log2(2L) + 16   real flops        (2 transforms + 2 spectral MACs)

against 10 * log2(2L) + 8 for a pure-doubling level of the same size, on the standard cost model where a length-K REAL transform costs 2.5 * K * log2 K. The shipped schedule needs one more level for the same IR length but each level is half the size, and the two totals land within 2 %: for 48 kHz, B = 128, N0 = 128, M = 65536 taps the shipped schedule costs 1390 flops/sample against 1408 for the unschedulable one. The bounded-peak property is therefore algorithmically free.

What this implementation actually costs, and why it is higher. The resumable transform below is a COMPLEX radix-2 FFT run on real input with a zero imaginary part, which is 5 * K * log2 K — exactly twice the real-FFT model. The measured cost for the case above is 2512 flops/sample rather than

1. That 1.8x is a deliberate, documented gap: a packed real transform (half-length complex FFT plus an untangle stage) would recover it, but the untangle has to become two more resumable phases in the cursor, and the property this module is accountable for is the bounded peak, not the constant factor. Per-block compute bound asserts peak/mean; the absolute figure is read from last_block_cost() and stated, not asserted. Schedule margin asserts the other half — that every level has room to be sliced at all.

References

• W. G. Gardner, "Efficient Convolution without Input-Output Delay", J. Audio Eng. Soc. 43(3):127-136, March 1995 — the zero-latency non-uniform partition scheme and the deadline argument.
• T. G. Stockham Jr., "High-Speed Convolution and Correlation", Proc. AFIPS Spring Joint Computer Conf. 28:229-233, 1966 — FFT block convolution.
• A. V. Oppenheim & R. W. Schafer, Discrete-Time Signal Processing, 3rd ed., Prentice Hall, 2009, section 8.7 — overlap-save mechanics.
• G. Garcia, "Optimal Filter Partition for Efficient Convolution with Short Input/Output Delay", Proc. 113th AES Convention, 2002 — the multi-partition-per-size family and the shared forward transform.
• F. Wefers, Partitioned Convolution Algorithms for Real-Time Auralization, PhD dissertation, RWTH Aachen, Logos Verlag, 2015, Ch. 3-5 — FDL and load balancing.
• E. Battenberg & R. Avizienis, "Implementing Real-Time Partitioned Convolution Algorithms on Conventional Operating Systems", Proc. DAFx-11, 2011 — single-thread scheduling of partition transforms.
• J. W. Cooley & J. W. Tukey, "An Algorithm for the Machine Calculation of Complex Fourier Series", Math. Comp. 19(90):297-301, 1965 — the radix-2 transform and its O(K log K) cost model.