Butterfly

p3_dft

Trait Butterfly 

Source 
pub trait Butterfly<F: Field>:
    Copy
    + Send
    + Sync {
    // Required method
    fn apply<PF: PackedField<Scalar = F>>(&self, x_1: PF, x_2: PF) -> (PF, PF);

    // Provided methods
    fn apply_in_place<PF: PackedField<Scalar = F>>(
        &self,
        x_1: &mut PF,
        x_2: &mut PF,
    ) { ... }
    fn apply_to_rows(&self, row_1: &mut [F], row_2: &mut [F]) { ... }
    fn apply_to_rows_oop(
        &self,
        src_1: &[F],
        dst_1: &mut [MaybeUninit<F>],
        src_2: &[F],
        dst_2: &mut [MaybeUninit<F>],
    ) { ... }
}
Expand description

A butterfly operation used in NTT to combine two values into a new pair.

This trait defines how to transform two elements (or vectors of elements) according to the structure of a butterfly gate.

In an NTT, butterflies are the core units that recursively combine values across layers. Each butterfly computes:

  (a + b * twiddle, a - b * twiddle)   // DIT
or
  (a + b, (a - b) * twiddle)           // DIF

The transformation can be applied:

  • in-place (mutating input values)
  • to full rows of values (arrays of field elements)
  • out-of-place (writing results to separate destination buffers)

Different butterfly variants (DIT, DIF, or twiddle-free) define the exact formula.

Required Methods§

Source

fn apply<PF: PackedField<Scalar = F>>(&self, x_1: PF, x_2: PF) -> (PF, PF)

Applies the butterfly transformation to two packed field values.

This method takes two inputs x_1 and x_2 and returns two outputs (y_1, y_2) depending on the butterfly type.

Example (DIF):
  Input:  x_1 = a, x_2 = b
  Output: (a + b, (a - b) * twiddle)

Provided Methods§

Source

fn apply_in_place<PF: PackedField<Scalar = F>>( &self, x_1: &mut PF, x_2: &mut PF, )

Applies the butterfly in-place to two packed values.

Mutates both x_1 and x_2 directly, storing the result of apply.

Source

fn apply_to_rows(&self, row_1: &mut [F], row_2: &mut [F])

Applies the butterfly transformation to two rows of scalar field values.

Each row is a slice of F. This function processes the rows in packed chunks using SIMD where possible, and falls back to scalar operations for the suffix (remaining elements).

The transformation is done in-place.

Source

fn apply_to_rows_oop( &self, src_1: &[F], dst_1: &mut [MaybeUninit<F>], src_2: &[F], dst_2: &mut [MaybeUninit<F>], )

Applies the butterfly out-of-place to two source rows.

This version does not overwrite the source. Instead, it writes the result of each butterfly to separate destination slices (which may be uninitialized memory).

This is useful when performing LDE’s where the size of the output is larger than the size of the input.

  • src_1, src_2: input slices
  • dst_1, dst_2: output slices to write to (must be MaybeUninit)

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§