routes.lib

//################################ routes.lib ##########################################
// Routing library. Its official prefix is `ro`.
//
// This library provides tools for managing and organizing audio and control signal
// routing in Faust. It includes functions for channel mapping, splitting, merging, and
// dynamic routing, as well as utilities for building multichannel processing structures.
//
// The Routes library is organized into 1 section:
//
// * [Functions Reference](#functions-reference)
// 
// #### References
//
// * <https://github.com/grame-cncm/faustlibraries/blob/master/routes.lib>
//########################################################################################

/************************************************************************
************************************************************************
FAUST library file
Copyright (C) 2003-2019 GRAME, Centre National de Creation Musicale
----------------------------------------------------------------------
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as
published by the Free Software Foundation; either version 2.1 of the
License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public
License along with the GNU C Library; if not, write to the Free
Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
02111-1307 USA.

EXCEPTION TO THE LGPL LICENSE : As a special exception, you may create a
larger FAUST program which directly or indirectly imports this library
file and still distribute the compiled code generated by the FAUST
compiler, or a modified version of this compiled code, under your own
copyright and license. This EXCEPTION TO THE LGPL LICENSE explicitly
grants you the right to freely choose the license for the resulting
compiled code. In particular the resulting compiled code has no obligation
to be LGPL or GPL. For example you are free to choose a commercial or
closed source license or any other license if you decide so.
************************************************************************
************************************************************************/

ba = library("basics.lib");
si = library("signals.lib");
sp = library("spats.lib");

declare name "Faust Signal Routing Library";
declare version "1.3.0";

//=============================Functions Reference========================================
//========================================================================================

//--------------------------------`(ro.)cross`-----------------------------------
// Cross N signals: `(x1,x2,..,xn) -> (xn,..,x2,x1)`.
// `cross` is a standard Faust function.
//
// #### Usage
//
// ```
// cross(N)
// _,_,_ : cross(3) : _,_,_
// ```
//
// Where:
//
// * `N`: number of signals (int, as a constant numerical expression)
//
// #### Test
// ```
// ro = library("routes.lib");
// os = library("oscillators.lib");
// cross_test = (os.osc(200), os.osc(300), os.osc(400)) : ro.cross(3);
// ```
//
// #### Note
//
// Special case: `cross2`:
//
// ```
// cross2 = _,cross(2),_;
// ```
//-----------------------------------------------------------------------------
// cross n cables : (x1,x2,..,xn) -> (xn,..,x2,x1)
cross(N) = route(N, N, par(i, N, (i+1, N-i)));
cross2 = _,cross(2),_; // for compatibility with some old misceffects.lib functions


//--------------`(ro.)crossnn`--------------
// Cross two `bus(N)`s.
//
// #### Usage
//
// ```
// (si.bus(2*N)) : crossnn(N) : (si.bus(2*N))
// ```
//
// Where:
//
// * `N`: the number of signals in the `bus` (int, as a constant numerical expression)
//
// #### Test
// ```
// ro = library("routes.lib");
// os = library("oscillators.lib");
// crossnn_test = (os.osc(110), os.osc(220), os.osc(330), os.osc(440)) : ro.crossnn(2);
// ```
//--------------------------------------
crossnn(N) = crossNM(N,N);


//--------------`(ro.)crossn1`--------------
// Cross `bus(N)` and `bus(1)`.
//
// #### Usage
//
// ```
// (si.bus(N),_) : crossn1(N) : (_,si.bus(N))
// ```
//
// Where:
//
// * `N`: the number of signals in the first `bus` (int, as a constant numerical expression)
//
// #### Test
// ```
// ro = library("routes.lib");
// os = library("oscillators.lib");
// crossn1_test = (os.osc(100), os.osc(200), os.osc(300), os.osc(400)) : ro.crossn1(3);
// ```
//--------------------------------------
crossn1(N) = crossNM(N,1);


//--------------`(ro.)cross1n`--------------
// Cross `bus(1)` and `bus(N)`.
//
// #### Usage
//
// ```
// (_,si.bus(N)) : crossn1(N) : (si.bus(N),_)
// ```
//
// Where:
//
// * `N`: the number of signals in the second `bus` (int, as a constant numerical expression)
//
// #### Test
// ```
// ro = library("routes.lib");
// os = library("oscillators.lib");
// cross1n_test = (os.osc(150), os.osc(250), os.osc(350), os.osc(450)) : ro.cross1n(3);
// ```
//--------------------------------------
cross1n(N) = crossNM(1,N);


//--------------`(ro.)crossNM`--------------
// Cross `bus(N)` and `bus(M)`.
//
// #### Usage
//
// ```
// (si.bus(N),si.bus(M)) : crossNM(N,M) : (si.bus(M),si.bus(N))
// ```
//
// Where:
//
// * `N`: the number of signals in the first `bus` (int, as a constant numerical expression)
// * `M`: the number of signals in the second `bus` (int, as a constant numerical expression)
//
// #### Test
// ```
// ro = library("routes.lib");
// os = library("oscillators.lib");
// crossNM_test = (os.osc(180), os.osc(280), os.osc(380), os.osc(480), os.osc(580)) : ro.crossNM(2,3);
// ```
//--------------------------------------
crossNM(N,M) = route(N+M, N+M, par(i, N+M, i+1, ((i+M)%(N+M))+1));


//--------------------------`(ro.)interleave`------------------------------
// Interleave R x C cables from column order to row order. That is, transpose the input CxR matrix, 
// the first R inputs is the first row.
//
// input : `x(0), x(1), x(2) ..., x(row*col-1)`
//
// output: `x(0+0*row), x(0+1*row), x(0+2*row), ..., x(1+0*row), x(1+1*row), x(1+2*row), ...`
// 
// 
//
// #### Usage
//
// ```
// si.bus(R*C) : interleave(R,C) : si.bus(R*C)
// ```
//
// Where:
//
// * `R`: row length (int, as a constant numerical expression)
// * `C`: column length (int, as a constant numerical expression)
//
// #### Test
// ```
// ro = library("routes.lib");
// os = library("oscillators.lib");
// interleave_test = (os.osc(200), os.osc(300), os.osc(400), os.osc(500)) : ro.interleave(2,2);
// ```
//-----------------------------------------------------------------------------
interleave(1,2) = _,_;
interleave(R,C) = route(R*C, R*C, par(i, R*C, (i+1, (i%R)*C + int(i/R) + 1)));

//-------------------------------`(ro.)butterfly`--------------------------------
// Addition (first half) then substraction (second half) of interleaved signals.
//
// #### Usage
//
// ```
// si.bus(N) : butterfly(N) : si.bus(N)
// ```
//
// Where:
//
// * `N`: size of the butterfly (N is int, even and as a constant numerical expression)
//
// #### Test
// ```
// ro = library("routes.lib");
// os = library("oscillators.lib");
// butterfly_test = (os.osc(250), os.osc(350), os.osc(450), os.osc(550)) : ro.butterfly(4);
// ```
//-----------------------------------------------------------------------------
butterfly(2) = si.bus(2) <: +,-;
butterfly(N) = si.bus(N) <: interleave(N/2,2), interleave(N/2,2) : par(i, N/2, +), par(i, N/2, -);


//------------------------------`(ro.)hadamard`----------------------------------
// Hadamard matrix function of size `N = 2^k`.
//
// #### Usage
//
// ```
// si.bus(N) : hadamard(N) : si.bus(N)
// ```
//
// Where:
//
// * `N`: `2^k`, size of the matrix (int, as a constant numerical expression)
//
// #### Test
// ```
// ro = library("routes.lib");
// os = library("oscillators.lib");
// hadamard_test = (os.osc(220), os.osc(330), os.osc(440), os.osc(550)) : ro.hadamard(4);
// ```
//-----------------------------------------------------------------------------
declare hadamard author "Remy Muller, revised by Romain Michon";
hadamard(2) = butterfly(2);
hadamard(N) = butterfly(N) : (hadamard(N/2), hadamard(N/2));


//---------------`(ro.)recursivize`-------------
// Create a recursion from two arbitrary processors `p` and `q`.
//
// #### Usage
//
// ```
// _,_ : recursivize(p,q) : _,_
//
// ```
//
// Where:
//
// * `p`: the forward arbitrary processor
// * `q`: the feedback arbitrary processor
//
// #### Test
// ```
// ro = library("routes.lib");
// os = library("oscillators.lib");
// recursivize_test = (os.osc(220), os.osc(330)) : ro.recursivize(*(0.5), *(0.3));
// ```
//----------------------------------------
recursivize(p,q) = (_,_,_,_ :> sp.stereoize(p)) ~ sp.stereoize(q);


//--------------------`(ro.)bubbleSort`-----------------------------------------
//
// Sort a set of N parallel signals in ascending order on-the-fly through
// the Bubble Sort algorithm.
//
// Mechanism: having a set of N parallel signals indexed from 0 to N - 1,
// compare the first pair of signals and swap them if sig[0] > sig[1];
// repeat the pair comparison for the signals sig[1] and sig[2], then again
// recursively until reaching the signals sig[N - 2] and sig[N - 1]; by the end,
// the largest element in the set will be placed last; repeat the process for
// the remaining N - 1 signals until there is a single pair left.
//
// Note that this implementation will always perform the worst-case
// computation, O(n^2).
//
// Even though the Bubble Sort algorithm is one of the least efficient ones,
// it is a useful example of how automatic sorting can be implemented at the
// signal level.
//
// #### Usage
//
// ```
// si.bus(N) : bubbleSort(N) : si.bus(N)
//
// ```
//
// Where:
//
// * `N`: the number of signals to be sorted (must be an int >= 0, as a constant numerical expression)
//
// #### Test
// ```
// ro = library("routes.lib");
// bubbleSort_test = (
//     hslider("bubbleSort:x0", 0.3, -1, 1, 0.01),
//     hslider("bubbleSort:x1", -0.2, -1, 1, 0.01),
//     hslider("bubbleSort:x2", 0.8, -1, 1, 0.01),
//     hslider("bubbleSort:x3", -0.5, -1, 1, 0.01)
// ) : ro.bubbleSort(4);
// ```
//
// #### References
//
// * <https://en.wikipedia.org/wiki/Bubble_sort>
//------------------------------------------------------------------------------
declare bubbleSort author "Dario Sanfilippo";
declare bubbleSort copyright "Copyright (C) 2021 Dario Sanfilippo
    <sanfilippo.dario@gmail.com>";
declare bubbleSort license "MIT License";
bubbleSort(0) = 0 : !;
bubbleSort(1) = _;
bubbleSort(N) = seq(i, N - 1, pairSortN(N - i), bus(i))
    with {
        bus(0) = 0 : !;
        bus(N) = si.bus(N);
        pairSort = bus(2) <: select2(>), select2(<);
        pairSortN(N) = seq(i, N - 1, bus(i), pairSort, bus(N - i - 2));
    };


//--------------------(ro.)bitonicSort------------------------------------------
//
// A bitonic sorter is a parallel sorting network that performs comparisons
// and swaps on signal pairs iteratively. The pairs are selected according
// to different index gaps determined by the current state and pass indices, 
// while the sorting direction of each pair depends on the current stage index.
//
// The algorithm first builds a bitonic sequence with the input values, 
// that is, a sequence that is ascending for the first half, and descending 
// for the second half. Then, it applies a bitonic merger to sort the bitonic
// list in ascending or descending order.
//
// The algorithm has O(log2(N) ^ 2) depth complexity, and O(N * log2(N) ^ 2)
// work complexity. Specifically, the bitonic sorter algorithm requires N 
// inputs to be a power-of-two. The algorithm has a total of 
// log2(N) * ((log2(N) + 1) / 2) stages, and each stage requires N / 2 
// comparators. Each comparator has one min() and one max() function.
//
// For comparison, the Bubble Sort algorithm has N - 1 stages, and
// N * (N - 1) / 2 comparators. For N = 32, Bitonic Sort has 15 stages
// and 240 comparators, Bubble Sort has 31 stages and 496 comparators.
//
// The sorting process is zero-latency.
//
// #### Usage
//
// ```
// si.bus(N) : bitonicSort(N) : si.bus(N)
//
// ```
//
// Where:
//
// * `N`: the number of signals to be sorted (it must be a power-of-two 
// compile-time numerical expression)
//
// #### Test
// ```
// ro = library("routes.lib");
// bitonicSort_test = (
//     hslider("bubbleSort:x0", 0.3, -1, 1, 0.01),
//     hslider("bubbleSort:x1", -0.2, -1, 1, 0.01),
//     hslider("bubbleSort:x2", 0.8, -1, 1, 0.01),
//     hslider("bubbleSort:x3", -0.5, -1, 1, 0.01)
// ) : ro.bitonicSort(4);
// ```
//
// #### References
//
// * <https://en.wikipedia.org/wiki/Bitonic_sorter>
declare bitonicSort author "Dario Sanfilippo";
declare bitonicSort copyright "Copyright (C) 2026 Dario Sanfilippo
    <sanfilippo.dario@gmail.com>";
declare bitonicSort license "MIT License";

/// Helper 0-indexed route wrapper
route0idx(N, M, connectionList) = 
    route(N, M, si.vecOp((connectionList, par(i, outputs(connectionList), 1)), +));
/// Ascending and descending comparators
comparatorDes(x0, x1) = max(x0, x1) , min(x0, x1);
comparatorAsc(x0, x1) = min(x0, x1) , max(x0, x1);
comparator(0, x0, x1) = comparatorDes(x0, x1);
comparator(1, x0, x1) = comparatorAsc(x0, x1);
/// Direction selector, according to the stage index
comparatorDirections(N, s) = par(i, N / 2, (i % (2 ^ (s + 1)) < (2 ^ s)));
/// Comparison input routing pairs
bitonicRouteCompareInputList(N, G) = inlets , outlets : interleave(N, 2) with {
    inlets = par(j, N / (2 * G) , par(i, G, i + j * (2 * G) , i + G + j * (2 * G)));
    outlets = par(i, N, i);
};
/// Comparison output unrouting pairs
bitonicRouteCompareOutputList(N, G) = inlets , outlets : interleave(N, 2) with {
    inlets = par(i, N, i);
    outlets = par(j, N / (2 * G) , par(i, G, i + j * (2 * G) , i + G + j * (2 * G)));
};
/// Apply routing
bitonicRouteInput(N, G) = route0idx(N, N, (bitonicRouteCompareInputList(N, G)));
bitonicRouteOutput(N, G) = route0idx(N, N, (bitonicRouteCompareOutputList(N, G)));
/// Bitonic sequence builder layer
bitonicBuilderLayer(N, s, p) = Y with {
    G = 2 ^ (s - p);
    D(i) = ba.pick(comparatorDirections(N, s), i);
    Y = bitonicRouteInput(N, G) : par(i, N / 2, comparator(D(i))) : bitonicRouteOutput(N, G);
};
/// Bitonic sequence builder network
bitonicBuilderNetwork(N) = Y with {
    S = rint(log2(N) - 1);
    Y = seq(s, S, seq(p, s + 1, bitonicBuilderLayer(N, s, p)));
    log2(x) = log(x)/log(2.0);
};
/// Bitonic sorter layer
bitonicSorterLayer(N, s, p) = Y with {
    G = 2 ^ (s - p);
    Y = bitonicRouteInput(N, G) : par(i, N / 2, comparator(1)) : bitonicRouteOutput(N, G);
};
/// Bitonic sorter network
bitonicSorterNetwork(N) = Y with {
    S = rint(log2(N) - 1);
    Y = seq(p, S + 1, bitonicSorterLayer(N, S, p));
    log2(x) = log(x)/log(2.0);
};
/// Bitonic sorter
bitonicSort(N) = bitonicBuilderNetwork(N) : bitonicSorterNetwork(N);


//--------------------(ro.)bitonicSortIdx---------------------------------------
//
// This function is based on the `bitonicSort` function, except it returns the 
// set of indices for the ordered input values. This is useful if you want
// to sort one set based on another one.
//
// #### Usage
//
// ```
// si.bus(N) : bitonicSortIdx(N) : si.bus(N)
//
// ```
//
// Where:
//
// * `N`: the number of signals to be sorted (it must be a power-of-two
// compile-time numerical expression)
//
// #### Test
// ```
// ro = library("routes.lib");
// bitonicSortIdx_test = (
//     hslider("bubbleSort:x0", 0.3, -1, 1, 0.01),
//     hslider("bubbleSort:x1", -0.2, -1, 1, 0.01),
//     hslider("bubbleSort:x2", 0.8, -1, 1, 0.01),
//     hslider("bubbleSort:x3", -0.5, -1, 1, 0.01)
// ) : ro.bitonicSortIdx(4);
// ```
//
// #### References
//
// * <https://en.wikipedia.org/wiki/Bitonic_sorter>
declare bitonicSortIdx author "Dario Sanfilippo";
declare bitonicSortIdx copyright "Copyright (C) 2026 Dario Sanfilippo
    <sanfilippo.dario@gmail.com>";
declare bitonicSortIdx license "MIT License";

comparatorDesIdx(x0, i0, x1, i1) = ba.if(cond, x1, x0) , ba.if(cond, i1, i0) , ba.if(cond, x0, x1) , ba.if(cond, i0, i1) with {
    cond = x1 > x0;
};
comparatorAscIdx(x0, i0, x1, i1) = ba.if(cond, x1, x0) , ba.if(cond, i1, i0) , ba.if(cond, x0, x1) , ba.if(cond, i0, i1) with {
    cond = x0 > x1;
};
comparatorIdx(0, x0, i0, x1, i1) = comparatorDesIdx(x0, i0, x1, i1);
comparatorIdx(1, x0, i0, x1, i1) = comparatorAscIdx(x0, i0, x1, i1);
comparatorDirectionsIdx(N, s) = par(i, N / 2, (i % (2 ^ (s + 1)) < (2 ^ s)));

bitonicRouteCompareInputListIdx(N, G) = inlets , outlets : interleave(2 * N, 2) with {
    inlets = par(j, N / (2 * G) , par(i, G,
        2 * (i + j * (2 * G)) ,
        2 * (i + j * (2 * G)) + 1 ,
        2 * (i + G + j * (2 * G)) ,
        2 * (i + G + j * (2 * G)) + 1
    ));
    outlets = par(i, N, 2 * i , 2 * i + 1);
};
bitonicRouteCompareOutputListIdx(N, G) = inlets , outlets : interleave(2 * N, 2) with {
    inlets = par(i, N, 2 * i , 2 * i + 1);
    outlets = par(j, N / (2 * G) , par(i, G,
        2 * (i + j * (2 * G)) ,
        2 * (i + j * (2 * G)) + 1 ,
        2 * (i + G + j * (2 * G)) ,
        2 * (i + G + j * (2 * G)) + 1
    ));
};
bitonicRouteInputIdx(N, G) = route0idx(2 * N, 2 * N, (bitonicRouteCompareInputListIdx(N, G)));
bitonicRouteOutputIdx(N, G) = route0idx(2 * N, 2 * N, (bitonicRouteCompareOutputListIdx(N, G)));

bitonicBuilderLayerIdx(N, s, p) = Y with {
    G = 2 ^ (s - p);
    D(i) = ba.pick(comparatorDirectionsIdx(N, s), i);
    Y = bitonicRouteInputIdx(N, G) : par(i, N / 2, comparatorIdx(D(i))) : bitonicRouteOutputIdx(N, G);
};
bitonicBuilderNetworkIdx(N) = Y with {
    S = rint(log2(N) - 1);
    Y = seq(s, S, seq(p, s + 1, bitonicBuilderLayerIdx(N, s, p)));
    log2(x) = log(x)/log(2.0);
};
bitonicSorterLayerIdx(N, s, p) = Y with {
    G = 2 ^ (s - p);
    Y = bitonicRouteInputIdx(N, G) : par(i, N / 2, comparatorIdx(1)) : bitonicRouteOutputIdx(N, G);
};
bitonicSorterNetworkIdx(N) = Y with {
    S = rint(log2(N) - 1);
    Y = seq(p, S + 1, bitonicSorterLayerIdx(N, S, p));
    log2(x) = log(x)/log(2.0);
};
bitonicSortIdx(N) = si.bus(N) , par(i, N, i) : interleave(N, 2) : bitonicBuilderNetworkIdx(N) : bitonicSorterNetworkIdx(N) : par(i, N, ! , _);