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
131
132
133
134
135
136
137
138
139

//! GF(2^16) tower kernels for x86 / `x86_64`.
//!
//! Every kernel here is the same identity, spelled three ways. Interleaved
//! bytes `[a, b]` are `a + b*u`; multiplying by `c0 + c1*u` gives
//!
//! ```text
//! even lane = c0*a       ^ (DELTA*c1)*b
//! odd  lane = (c0+c1)*b  ^ c1*a
//! ```
//!
//! Both lanes are therefore one alternating-coefficient byte multiply of the
//! source, `XORed` with one of the source with adjacent bytes exchanged. No
//! planar de-interleave, no 16-bit multiply, no 128 KiB table.
//!
//! - **GFNI** does each byte multiply with `GF2P8MULB` and gets the two
//!   alternating coefficients straight out of
//!   [`TowerCoeff`](crate::kernel::tables::TowerCoeff) — one `vpbroadcastw`
//!   each, no table at all.
//! - **AVX2 / SSSE3** have no field multiply, so each of the four base-field
//!   factors becomes a split-nibble `PSHUFB` pair against
//!   [`TowerTables`](crate::kernel::tables::TowerTables); the even and odd
//!
//! Multi-row wiring differs by backend. SSSE3 blocks gather and matrix;
//! GFNI also blocks both, while AVX2 uses repeated AXPY for those shapes.
//! On `V4x`, matrix tiles widen; scatter and gather retain their GFNI lanes.
//! A coefficient occupies two broadcast words or four nibble tables, so the
//! amount of live coefficient state determines which row shapes benefit from
//! blocking.
//!
//! Submodules split on instruction set: `ssse3`, `avx2`, `gfni` (itself split
//! on fan shape), and `avx512` under `simd512`. The coefficient words, shuffle
//! controls, and blocked-state sizes every instruction set shares live in this
//! file.
//!
//! Every public kernel is a safe [`archmage`] entrypoint taking the exact
//! capability token its instructions require (`X64V4xToken` for AVX-512,
//! `X64V3GfniCryptoToken` for GFNI, `X64V3Token` for AVX2, and `X64V2Token`
//! for SSSE3) and validating its geometry. Inner helpers are `#[rite]`.
//!
//! Owned unsafe is confined to the narrow non-temporal stores and the
//! offset-addressed scatter and matrix groups. Wide matrix groups borrow
//! disjoint row slices without raw pointers.
//!
//! [`archmage`]: https://docs.rs/archmage

mod avx2;
#[cfg(feature = "simd512")]
mod avx512;
mod gfni;
mod ssse3;

pub use avx2::{
    mul_add_avx2, mul_add_scatter_avx2, mul_assign_avx2, mul_elementwise_assign_avx2,
    mul_elementwise_avx2, mul_into_avx2,
};
#[cfg(all(test, feature = "simd512"))]
pub(crate) use avx512::MUL_ADD_PEEL_MIN;
#[cfg(feature = "simd512")]
pub use avx512::{
    mul_add_avx512, mul_add_matrix_avx512, mul_add_matrix_avx512_with, mul_assign_avx512,
    mul_elementwise_assign_avx512, mul_elementwise_avx512, mul_into_avx512,
};
pub use gfni::{
    mul_add_gather_gfni, mul_add_gfni, mul_add_matrix_gfni, mul_add_matrix_gfni_with,
    mul_add_scatter_gfni, mul_assign_gfni, mul_elementwise_assign_gfni, mul_elementwise_gfni,
    mul_into_gfni,
};
pub use ssse3::{
    mul_add_gather_ssse3, mul_add_matrix_ssse3, mul_add_matrix_ssse3_with, mul_add_scatter_ssse3,
    mul_add_ssse3, mul_assign_ssse3, mul_elementwise_assign_ssse3, mul_elementwise_ssse3,
    mul_into_ssse3,
};

// Cores shared with the Fan–Paar tower kernels.
pub(crate) use avx2::{NibbleAvx2, nibble_avx2, scale_avx2};
pub(crate) use ssse3::{nibble_ssse3, scale_ssse3};

use crate::kernel::tables::TowerCoeff;

#[cfg(target_arch = "x86")]
use core::arch::x86::*;
#[cfg(target_arch = "x86_64")]
use core::arch::x86_64::*;

/// Rejects byte lengths that end inside a GF(2^16) element.
#[inline]
fn check_elements(name: &str, bytes: usize) {
    assert!(
        bytes.is_multiple_of(2),
        "{name}: buffer of {bytes} bytes ends with a partial GF(2^16) element",
    );
}

/// `PSHUFB` control that exchanges the two bytes of every element.
///
/// The 16-byte pattern is repeated because `PSHUFB` indexes within each
/// 128-bit lane independently — which costs nothing here, since an element
/// never straddles a lane boundary.
const SWAP_ADJACENT: [u8; 16] = [1, 0, 3, 2, 5, 4, 7, 6, 9, 8, 11, 10, 13, 12, 15, 14];

/// The same control repeated for AVX2's two 128-bit lanes.
const SWAP_ADJACENT_AVX2: [u8; 32] = {
    let mut wide = [0u8; 32];
    let mut i = 0;
    while i < 32 {
        wide[i] = SWAP_ADJACENT[i & 15];
        i += 1;
    }
    wide
};

/// The two broadcast words of a coefficient, as the halfwords `set1_epi16`
/// takes.
///
/// `to_ne_bytes`/`from_ne_bytes` rather than a cast: this is a
/// reinterpretation of the same 16 bits, not a numeric conversion.
#[inline]
fn broadcast_words(coeff: TowerCoeff) -> (i16, i16) {
    (
        i16::from_ne_bytes(coeff.same.to_ne_bytes()),
        i16::from_ne_bytes(coeff.cross.to_ne_bytes()),
    )
}

/// Load the 32-byte adjacent-exchange shuffle control.
#[archmage::rite(v3, import_intrinsics)]
fn swap_mask_avx2() -> __m256i {
    _mm256_loadu_si256(&SWAP_ADJACENT_AVX2)
}

/// Load the 16-byte adjacent-exchange shuffle control.
#[archmage::rite(v2, import_intrinsics)]
fn swap_mask_ssse3() -> __m128i {
    _mm_loadu_si128(&SWAP_ADJACENT)
}

/// Prepared coefficient sets the blocked gather and matrix shapes hold at
/// once.
const TERM_TILE: usize = 8;