p3_mds/
butterflies.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
use p3_field::FieldAlgebra;

/// DIT butterfly.
#[inline]
pub(crate) fn dit_butterfly<FA: FieldAlgebra, const N: usize>(
    values: &mut [FA; N],
    idx_1: usize,
    idx_2: usize,
    twiddle: FA::F,
) {
    let val_1 = values[idx_1].clone();
    let val_2 = values[idx_2].clone() * FA::from_f(twiddle);
    values[idx_1] = val_1.clone() + val_2.clone();
    values[idx_2] = val_1 - val_2;
}

/// DIF butterfly.
#[inline]
pub(crate) fn dif_butterfly<FA: FieldAlgebra, const N: usize>(
    values: &mut [FA; N],
    idx_1: usize,
    idx_2: usize,
    twiddle: FA::F,
) {
    let val_1 = values[idx_1].clone();
    let val_2 = values[idx_2].clone();
    values[idx_1] = val_1.clone() + val_2.clone();
    values[idx_2] = (val_1 - val_2) * FA::from_f(twiddle);
}

/// Butterfly with twiddle factor 1 (works in either DIT or DIF).
#[inline]
pub(crate) fn twiddle_free_butterfly<FA: FieldAlgebra, const N: usize>(
    values: &mut [FA; N],
    idx_1: usize,
    idx_2: usize,
) {
    let val_1 = values[idx_1].clone();
    let val_2 = values[idx_2].clone();
    values[idx_1] = val_1.clone() + val_2.clone();
    values[idx_2] = val_1 - val_2;
}