Trait Convolve

Source

pub trait Convolve<F, T: ConvolutionElt, U: ConvolutionRhs> {
    const T_ZERO: T;
    const U_ZERO: U;
Show 23 methods
    // Required methods
    fn halve(val: T) -> T;
    fn read(input: F) -> T;
    fn parity_dot<const N: usize>(lhs: [T; N], rhs: [U; N]) -> T;
    fn reduce(z: T) -> F;

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

Expand description

Trait for computing cyclic and negacyclic convolutions.

Implementors choose how to lift field elements into a wider type, compute dot products, and reduce back. This allows integer-lifted arithmetic (e.g. i64) to avoid modular reductions inside the inner loops.

§Overflow contract

For a convolution of size N, it must be possible to add N elements of type T without overflow, and similarly for U. The product of one T and one U element must not overflow T after about N further additions.

§Performance notes

In practice one operand is a compile-time constant (the MDS matrix). The compiler folds the constant arithmetic at compile time. For large matrices (N >= 24), the compile-time-generated constants are about N times bigger than strictly necessary.

Required Associated Constants§

Source

const T_ZERO: T

Additive identity for the wide operand type T.

Used to initialize output and scratch arrays before the convolution fills them with computed values.

Source

const U_ZERO: U

Additive identity for the narrow operand type U.

Used to initialize temporary arrays for the RHS decomposition in the recursive CRT / Karatsuba steps.

Required Methods§

Source

fn halve(val: T) -> T

Divide an element of T by 2.

For integers (i64, i128): arithmetic right shift by 1.
For field elements: multiplication by the multiplicative inverse of 2.

Source

fn read(input: F) -> T

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

Source

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

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.

Source