Trait Convolve

pub trait Convolve<F, T: RngElt, U: RngElt, V: RngElt> {
    // Required methods
    fn read(input: F) -> T;
    fn parity_dot<const N: usize>(lhs: [T; N], rhs: [U; N]) -> V;
    fn reduce(z: V) -> F;

    // Provided methods
    fn apply<const N: usize, C: Fn([T; N], [U; N], &mut [V])>(
        lhs: [F; N],
        rhs: [U; N],
        conv: C,
    ) -> [F; N] { ... }
    fn conv3(lhs: [T; 3], rhs: [U; 3], output: &mut [V]) { ... }
    fn negacyclic_conv3(lhs: [T; 3], rhs: [U; 3], output: &mut [V]) { ... }
    fn conv4(lhs: [T; 4], rhs: [U; 4], output: &mut [V]) { ... }
    fn negacyclic_conv4(lhs: [T; 4], rhs: [U; 4], output: &mut [V]) { ... }
    fn conv6(lhs: [T; 6], rhs: [U; 6], output: &mut [V]) { ... }
    fn negacyclic_conv6(lhs: [T; 6], rhs: [U; 6], output: &mut [V]) { ... }
    fn conv8(lhs: [T; 8], rhs: [U; 8], output: &mut [V]) { ... }
    fn negacyclic_conv8(lhs: [T; 8], rhs: [U; 8], output: &mut [V]) { ... }
    fn conv12(lhs: [T; 12], rhs: [U; 12], output: &mut [V]) { ... }
    fn negacyclic_conv12(lhs: [T; 12], rhs: [U; 12], output: &mut [V]) { ... }
    fn conv16(lhs: [T; 16], rhs: [U; 16], output: &mut [V]) { ... }
    fn negacyclic_conv16(lhs: [T; 16], rhs: [U; 16], output: &mut [V]) { ... }
    fn conv24(lhs: [T; 24], rhs: [U; 24], output: &mut [V]) { ... }
    fn conv32(lhs: [T; 32], rhs: [U; 32], output: &mut [V]) { ... }
    fn negacyclic_conv32(lhs: [T; 32], rhs: [U; 32], output: &mut [V]) { ... }
    fn conv64(lhs: [T; 64], rhs: [U; 64], output: &mut [V]) { ... }
}

Template function to perform convolution of vectors.

Roughly speaking, for a convolution of size N, it should be possible to add N elements of type T without overflowing, and similarly for U. Then multiplication via Self::mul should produce an element of type V which will not overflow after about N additions (this is an over-estimate).

For example usage, see {mersenne-31,baby-bear,goldilocks}/src/mds.rs.

NB: In practice, one of the parameters to the convolution will be constant (the MDS matrix). After inspecting Godbolt output, it seems that the compiler does indeed generate single constants as inputs to the multiplication, rather than doing all that arithmetic on the constant values every time. Note however that, for MDS matrices with large entries (N >= 24), these compile-time generated constants will be about N times bigger than they need to be in principle, which could be a potential avenue for some minor improvements.

NB: If primitive multiplications are still the bottleneck, a further possibility would be to find an MDS matrix some of whose entries are powers of 2. Then the multiplication can be replaced with a shift, which on most architectures has better throughput and latency, and is issued on different ports (1p06) to multiplication (1p1).

Required Methods

fn read(input: F) -> T

Given an input element, retrieve the corresponding internal element that will be used in calculations.

fn parity_dot<const N: usize>(lhs: [T; N], rhs: [U; N]) -> V

Given input vectors lhs and rhs, calculate their dot product. The result can be reduced with respect to the modulus (of F), but it must have the same lower 10 bits as the dot product if all inputs are considered integers. See monty-31/src/mds.rs::barrett_red_monty31() for an example of how this can be implemented in practice.

fn reduce(z: V) -> F

Convert an internal element of type V back into an external element.

Provided Methods

fn apply<const N: usize, C: Fn([T; N], [U; N], &mut [V])>( lhs: [F; N], rhs: [U; N], conv: C, ) -> [F; N]

Convolve lhs and rhs.

The parameter conv should be the function in this trait that corresponds to length N.

fn conv3(lhs: [T; 3], rhs: [U; 3], output: &mut [V])

fn negacyclic_conv3(lhs: [T; 3], rhs: [U; 3], output: &mut [V])

fn conv4(lhs: [T; 4], rhs: [U; 4], output: &mut [V])

fn negacyclic_conv4(lhs: [T; 4], rhs: [U; 4], output: &mut [V])

fn conv6(lhs: [T; 6], rhs: [U; 6], output: &mut [V])

fn negacyclic_conv6(lhs: [T; 6], rhs: [U; 6], output: &mut [V])

fn conv8(lhs: [T; 8], rhs: [U; 8], output: &mut [V])

fn negacyclic_conv8(lhs: [T; 8], rhs: [U; 8], output: &mut [V])

fn conv12(lhs: [T; 12], rhs: [U; 12], output: &mut [V])

fn negacyclic_conv12(lhs: [T; 12], rhs: [U; 12], output: &mut [V])

fn conv16(lhs: [T; 16], rhs: [U; 16], output: &mut [V])

fn negacyclic_conv16(lhs: [T; 16], rhs: [U; 16], output: &mut [V])

fn conv24(lhs: [T; 24], rhs: [U; 24], output: &mut [V])

fn conv32(lhs: [T; 32], rhs: [U; 32], output: &mut [V])

fn negacyclic_conv32(lhs: [T; 32], rhs: [U; 32], output: &mut [V])

fn conv64(lhs: [T; 64], rhs: [U; 64], output: &mut [V])

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors