fgf 3.0.0

Faster Galois Fields: SIMD and portable finite-field arithmetic (binary towers and prime fields) and vector kernels
Documentation 
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

//! Portable prime-field kernels.
//!
//! The reference and fallback path for the prime fields, and the differential
//! oracle for their SIMD backends. These are field-generic and elementwise:
//! correct on any [`Field`] whose [`Elem`] implements modular arithmetic.
//!
//! Unlike [`crate::kernel::scalar`], addition here is the field's modular
//! `add`, never XOR — these are wrong for the binary fields and right for the
//! prime fields. As with the scalar module, keeping this obviously correct is
//! worth more than making it fast: the vector backends carry the speed.

use crate::field::{Elem, FieldBuffer, FieldElem};

/// `dst[i] += src[i]`, modular field addition.
pub fn add_assign<F: FieldBuffer>(dst: &mut [u8], src: &[u8]) {
    debug_assert_eq!(dst.len(), src.len());
    for (d, s) in dst
        .chunks_exact_mut(F::BYTES)
        .zip(src.chunks_exact(F::BYTES))
    {
        let value = F::decode(d).add(F::decode(s));
        F::encode(d, value);
    }
}

/// `dst[i] -= src[i]`, modular field subtraction.
pub fn sub_assign<F: FieldBuffer>(dst: &mut [u8], src: &[u8]) {
    debug_assert_eq!(dst.len(), src.len());
    for (d, s) in dst
        .chunks_exact_mut(F::BYTES)
        .zip(src.chunks_exact(F::BYTES))
    {
        let value = F::decode(d).sub(F::decode(s));
        F::encode(d, value);
    }
}

/// `dst[i] += coeff * src[i]`, elementwise.
pub fn mul_add<F: FieldBuffer>(dst: &mut [u8], coeff: Elem<F>, src: &[u8]) {
    debug_assert_eq!(dst.len(), src.len());
    if coeff.is_zero() {
        return;
    }
    if coeff.is_one() {
        add_assign::<F>(dst, src);
        return;
    }
    for (d, s) in dst
        .chunks_exact_mut(F::BYTES)
        .zip(src.chunks_exact(F::BYTES))
    {
        let value = F::decode(d).add(F::decode(s).mul(coeff));
        F::encode(d, value);
    }
}

/// `dst[i] = coeff * dst[i]`, in place.
pub fn mul_assign<F: FieldBuffer>(dst: &mut [u8], coeff: Elem<F>) {
    if coeff.is_one() {
        return;
    }
    if coeff.is_zero() {
        dst.fill(0);
        return;
    }
    for d in dst.chunks_exact_mut(F::BYTES) {
        let value = F::decode(d).mul(coeff);
        F::encode(d, value);
    }
}

/// `rows[j] += coeffs[j] * src` for every row `j`.
pub fn mul_add_scatter<F: FieldBuffer>(
    rows: &mut [u8],
    row_len: usize,
    coeffs: &[Elem<F>],
    src: &[u8],
) {
    for (row, &coeff) in rows.chunks_exact_mut(row_len).zip(coeffs) {
        mul_add::<F>(row, coeff, src);
    }
}

/// `dst += sum(coeffs[i] * srcs[i])`.
pub fn mul_add_gather<F: FieldBuffer>(dst: &mut [u8], coeffs: &[Elem<F>], srcs: &[&[u8]]) {
    for (&coeff, &src) in coeffs.iter().zip(srcs) {
        mul_add::<F>(dst, coeff, src);
    }
}

/// Apply every `(coeffs, src)` term to all `nrows` rows.
pub fn mul_add_matrix<F: FieldBuffer>(
    rows: &mut [u8],
    row_len: usize,
    nrows: usize,
    terms: &[(&[Elem<F>], &[u8])],
) {
    for &(coeffs, src) in terms {
        for (row, &coeff) in rows.chunks_exact_mut(row_len).take(nrows).zip(coeffs) {
            mul_add::<F>(row, coeff, src);
        }
    }
}

/// `dst[i] = a[i] * b[i]`, elementwise.
pub fn mul_elementwise<F: FieldBuffer>(dst: &mut [u8], a: &[u8], b: &[u8]) {
    debug_assert_eq!(dst.len(), a.len());
    debug_assert_eq!(dst.len(), b.len());
    for ((d, x), y) in dst
        .chunks_exact_mut(F::BYTES)
        .zip(a.chunks_exact(F::BYTES))
        .zip(b.chunks_exact(F::BYTES))
    {
        F::encode(d, F::decode(x).mul(F::decode(y)));
    }
}

/// `dst[i] += value`, modular field addition of one broadcast element.
pub fn add_assign_scalar<F: FieldBuffer>(dst: &mut [u8], value: Elem<F>) {
    for d in dst.chunks_exact_mut(F::BYTES) {
        F::encode(d, F::decode(d).add(value));
    }
}

/// `dst[i] -= value`, modular field subtraction of one broadcast element.
pub fn sub_assign_scalar<F: FieldBuffer>(dst: &mut [u8], value: Elem<F>) {
    for d in dst.chunks_exact_mut(F::BYTES) {
        F::encode(d, F::decode(d).sub(value));
    }
}