Add FFT-based reverb

2 files changed, 40 insertions, 0 deletions

diff --git a/fft.bqn b/fft.bqn
new file mode 100644
index 0000000..2d10ccf
--- /dev/null
+++ b/fft.bqn
@@ -0,0 +1,20 @@
+# Fast Fourier transform
+# Argument has shape ⟨l⟩ for real values or ⟨2,l⟩ for complex, l←2⋆n
+# Result is complex encoded as shape ⟨2,l⟩.
+
+Sin‿Cos ← •math
+
+{
+  𝕨𝕊⁼𝕩: (-𝕨1⊘≢¯1)𝕊𝕩 ;
+
+  inv ← 𝕨≡¯1
+  "FFT argument must be a list or have two list cells" ! (3⌊=)◶⟨0,1,2=≠,0⟩𝕩
+  n ← 2 ⋆⁼ l ← ¯1⊑≢𝕩
+  "FFT length must be a power of two" ! ⌊⊸=n
+  s ← 2 ⥊˜ n
+
+  r ← (Cos≍Sin) π × (1↓s) ⥊ -⍟inv ↕⊸÷ l÷2   # Roots of unity
+  M ← -˝∘× ≍ +˝∘×⟜⌽                         # Complex multiplication
+  F ← { 𝕨 ⊏⎉1⊸𝕊⍟(1<=𝕨) (+˝˘≍⎉(-=𝕨)𝕨M-˝˘)𝕩 } # FFT loop
+  ÷⟜l⍟inv ⥊˘ r F s⊸⥊˘ ≍⟜(0¨)⍟(1==) 𝕩
+}
diff --git a/mix.bqn b/mix.bqn
index 21172c0..e8ad794 100644
--- a/mix.bqn
+++ b/mix.bqn
@@ -1,5 +1,6 @@
 "mix.bqn takes a single option namespace, or no arguments" ! 1≥≠•args
 o ← ≠◶⟨•Import∘"options.bqn", ⊑⟩ •args
+fft ← •Import "fft.bqn"
 
 # List of length |𝕩 that starts at 0 and stops just before 1,
 # reversed if 𝕩<0.
@@ -40,3 +41,22 @@ _crossfade ⇐ {
   G←↑≍○<↓
   (-𝕗)⊸G⊸(∾ 1⌽∾˜○(1⊸↓) ∾⟜< (¬⊸≍I𝕗)+˝∘×≍○⊑)⟜(𝕗⊸G)⎉1
 }
+
+# Apply reverb impulse response (IR) 𝕨 to 𝕩.
+# Argument rows are extended, giving result length (𝕩+○≠𝕨)-1 (for lists).
+# Equivalent to (+´¨+⌜○↕○≠⊔×⌜)⎉1 except for numeric precision.
+Reverb ⇐ {
+  M ← -˝∘× ≍ +˝∘×⟜⌽ # Complex multiplication
+  lw‿lx ← (¯1⊑≢)¨ 𝕨‿𝕩
+  ! 0<lw
+  # Use the overlap-add method.
+  o ← lw-1          # Overlap length
+  n ← ⌈⌾(2⋆⁼⊢) 3×o  # Window length, including overlap
+  l ← n-o           # Without overlap
+  k ← lx+o          # Result length
+  k0← ⌈⌾(÷⟜l) k     # Rounded up
+  𝕨 {
+    CW ← ⊏ · (FFT n↑𝕨)⊸M⌾FFT n⊸↑
+    {t←0 ⋄ k↑⥊ {r‿s←(-o)(t⊸+⌾(o⊸↑)∘↓≍○<↑)CW𝕩⋄t↩s⋄r}˘ ∘‿l⥊k0↑𝕩}⎉1 𝕩
+  }⎉(1≍1+0⌈-˜○=) 𝕩
+}