p3_mds/
butterflies.rs

1use p3_field::FieldAlgebra;
2
3/// DIT butterfly.
4#[inline]
5pub(crate) fn dit_butterfly<FA: FieldAlgebra, const N: usize>(
6    values: &mut [FA; N],
7    idx_1: usize,
8    idx_2: usize,
9    twiddle: FA::F,
10) {
11    let val_1 = values[idx_1].clone();
12    let val_2 = values[idx_2].clone() * FA::from_f(twiddle);
13    values[idx_1] = val_1.clone() + val_2.clone();
14    values[idx_2] = val_1 - val_2;
15}
16
17/// DIF butterfly.
18#[inline]
19pub(crate) fn dif_butterfly<FA: FieldAlgebra, const N: usize>(
20    values: &mut [FA; N],
21    idx_1: usize,
22    idx_2: usize,
23    twiddle: FA::F,
24) {
25    let val_1 = values[idx_1].clone();
26    let val_2 = values[idx_2].clone();
27    values[idx_1] = val_1.clone() + val_2.clone();
28    values[idx_2] = (val_1 - val_2) * FA::from_f(twiddle);
29}
30
31/// Butterfly with twiddle factor 1 (works in either DIT or DIF).
32#[inline]
33pub(crate) fn twiddle_free_butterfly<FA: FieldAlgebra, const N: usize>(
34    values: &mut [FA; N],
35    idx_1: usize,
36    idx_2: usize,
37) {
38    let val_1 = values[idx_1].clone();
39    let val_2 = values[idx_2].clone();
40    values[idx_1] = val_1.clone() + val_2.clone();
41    values[idx_2] = val_1 - val_2;
42}