use core::arch::x86_64::{
__m256i, _mm256_add_epi32, _mm256_and_si256, _mm256_extract_epi32, _mm256_i32gather_epi32,
_mm256_insert_epi32, _mm256_loadu_si256, _mm256_set1_epi32, _mm256_setr_epi32,
_mm256_setzero_si256, _mm256_slli_epi32, _mm256_srli_epi32, _mm256_store_si256,
_mm256_storeu_si256, _mm256_xor_si256,
};
use core::sync::atomic::{AtomicU8, Ordering};
use crate::consts::{P_INIT, S_INIT};
const LANES: usize = 8;
#[repr(C, align(64))]
struct SBoxes8([[u32; 8]; 1024]);
impl SBoxes8 {
#[inline(always)]
fn box_base(&self, b: usize) -> *const u32 {
debug_assert!(b < 4);
unsafe { self.0.as_ptr().cast::<u32>().add(b * 256 * 8) }
}
}
struct State8 {
p: [__m256i; 18],
s: SBoxes8,
}
macro_rules! lane_load {
($base:expr, $byte_off:expr) => {{
let mut a = $base as usize + $byte_off;
core::arch::asm!(
"/* {0} */",
inout(reg) a,
options(pure, nomem, nostack, preserves_flags),
);
*(a as *const u32)
}};
}
#[target_feature(enable = "avx2")]
#[inline]
unsafe fn lookup8_gather(box_base: *const i32, idx: __m256i, lane_off: __m256i) -> __m256i {
let vindex = _mm256_add_epi32(_mm256_slli_epi32::<3>(idx), lane_off);
unsafe { _mm256_i32gather_epi32::<4>(box_base, vindex) }
}
macro_rules! lookup8_insert {
($box_base:expr, $off:expr) => {{
let base = ($box_base).cast::<u8>();
let mut offs = [0u32; 8];
unsafe { _mm256_storeu_si256(offs.as_mut_ptr().cast::<__m256i>(), $off) };
let gathered = [
unsafe { lane_load!(base, offs[0] as usize) },
unsafe { lane_load!(base, offs[1] as usize + 4) },
unsafe { lane_load!(base, offs[2] as usize + 8) },
unsafe { lane_load!(base, offs[3] as usize + 12) },
unsafe { lane_load!(base, offs[4] as usize + 16) },
unsafe { lane_load!(base, offs[5] as usize + 20) },
unsafe { lane_load!(base, offs[6] as usize + 24) },
unsafe { lane_load!(base, offs[7] as usize + 28) },
];
unsafe { _mm256_loadu_si256(gathered.as_ptr().cast::<__m256i>()) }
}};
}
macro_rules! lookup8_extract {
($box_base:expr, $off:expr) => {{
let base = ($box_base).cast::<u8>();
let off = $off;
let g0 = unsafe { lane_load!(base, _mm256_extract_epi32::<0>(off) as usize) };
let g1 = unsafe { lane_load!(base, _mm256_extract_epi32::<1>(off) as usize + 4) };
let g2 = unsafe { lane_load!(base, _mm256_extract_epi32::<2>(off) as usize + 8) };
let g3 = unsafe { lane_load!(base, _mm256_extract_epi32::<3>(off) as usize + 12) };
let g4 = unsafe { lane_load!(base, _mm256_extract_epi32::<4>(off) as usize + 16) };
let g5 = unsafe { lane_load!(base, _mm256_extract_epi32::<5>(off) as usize + 20) };
let g6 = unsafe { lane_load!(base, _mm256_extract_epi32::<6>(off) as usize + 24) };
let g7 = unsafe { lane_load!(base, _mm256_extract_epi32::<7>(off) as usize + 28) };
let mut v = _mm256_setzero_si256();
v = _mm256_insert_epi32::<0>(v, g0 as i32);
v = _mm256_insert_epi32::<1>(v, g1 as i32);
v = _mm256_insert_epi32::<2>(v, g2 as i32);
v = _mm256_insert_epi32::<3>(v, g3 as i32);
v = _mm256_insert_epi32::<4>(v, g4 as i32);
v = _mm256_insert_epi32::<5>(v, g5 as i32);
v = _mm256_insert_epi32::<6>(v, g6 as i32);
_mm256_insert_epi32::<7>(v, g7 as i32)
}};
}
#[target_feature(enable = "avx2")]
#[inline]
fn f8_gather(s: &SBoxes8, x: __m256i) -> __m256i {
let byte_mask = _mm256_set1_epi32(0xff);
let a = _mm256_srli_epi32::<24>(x);
let b = _mm256_and_si256(_mm256_srli_epi32::<16>(x), byte_mask);
let c = _mm256_and_si256(_mm256_srli_epi32::<8>(x), byte_mask);
let d = _mm256_and_si256(x, byte_mask);
let lane_off = _mm256_setr_epi32(0, 1, 2, 3, 4, 5, 6, 7);
let (va, vb, vc, vd) = unsafe {
(
lookup8_gather(s.box_base(0).cast::<i32>(), a, lane_off),
lookup8_gather(s.box_base(1).cast::<i32>(), b, lane_off),
lookup8_gather(s.box_base(2).cast::<i32>(), c, lane_off),
lookup8_gather(s.box_base(3).cast::<i32>(), d, lane_off),
)
};
_mm256_add_epi32(_mm256_xor_si256(_mm256_add_epi32(va, vb), vc), vd)
}
macro_rules! f8_insert {
($s:expr, $x:expr) => {{
let s = $s;
let x = $x;
let stride_mask = _mm256_set1_epi32(0x1fe0);
let a = _mm256_and_si256(_mm256_srli_epi32::<19>(x), stride_mask);
let b = _mm256_and_si256(_mm256_srli_epi32::<11>(x), stride_mask);
let c = _mm256_and_si256(_mm256_srli_epi32::<3>(x), stride_mask);
let d = _mm256_and_si256(_mm256_slli_epi32::<5>(x), stride_mask);
let (va, vb, vc, vd) = (
lookup8_insert!(s.box_base(0), a),
lookup8_insert!(s.box_base(1), b),
lookup8_insert!(s.box_base(2), c),
lookup8_insert!(s.box_base(3), d),
);
_mm256_add_epi32(_mm256_xor_si256(_mm256_add_epi32(va, vb), vc), vd)
}};
}
macro_rules! f8_extract {
($s:expr, $x:expr) => {{
let s = $s;
let x = $x;
let stride_mask = _mm256_set1_epi32(0x1fe0);
let a = _mm256_and_si256(_mm256_srli_epi32::<19>(x), stride_mask);
let b = _mm256_and_si256(_mm256_srli_epi32::<11>(x), stride_mask);
let c = _mm256_and_si256(_mm256_srli_epi32::<3>(x), stride_mask);
let d = _mm256_and_si256(_mm256_slli_epi32::<5>(x), stride_mask);
let (va, vb, vc, vd) = (
lookup8_extract!(s.box_base(0), a),
lookup8_extract!(s.box_base(1), b),
lookup8_extract!(s.box_base(2), c),
lookup8_extract!(s.box_base(3), d),
);
_mm256_add_epi32(_mm256_xor_si256(_mm256_add_epi32(va, vb), vc), vd)
}};
}
macro_rules! f8 {
($flavor:ident, $s:expr, $x:expr) => {{
if $flavor == FLAVOR_GATHER {
f8_gather($s, $x)
} else if $flavor == FLAVOR_EXTRACT {
f8_extract!($s, $x)
} else {
f8_insert!($s, $x)
}
}};
}
macro_rules! rounds16 {
($state:expr, $flavor:ident, $l:ident, $r:ident) => {{
macro_rules! pair {
($i:expr) => {{
$l = _mm256_xor_si256($l, $state.p[$i]);
$r = _mm256_xor_si256($r, f8!($flavor, &$state.s, $l));
$r = _mm256_xor_si256($r, $state.p[$i + 1]);
$l = _mm256_xor_si256($l, f8!($flavor, &$state.s, $r));
}};
}
pair!(0);
pair!(2);
pair!(4);
pair!(6);
pair!(8);
pair!(10);
pair!(12);
pair!(14);
$l = _mm256_xor_si256($l, $state.p[16]);
$r = _mm256_xor_si256($r, $state.p[17]);
core::mem::swap(&mut $l, &mut $r);
}};
}
#[target_feature(enable = "avx2")]
#[inline]
fn encipher8<const FLAVOR: u8>(
state: &State8,
mut l: __m256i,
mut r: __m256i,
) -> (__m256i, __m256i) {
rounds16!(state, FLAVOR, l, r);
(l, r)
}
#[target_feature(enable = "avx2")]
#[inline]
fn expand_state_v8<const FLAVOR: u8>(
state: &mut State8,
swv: &[__m256i; 4],
kwv: &[__m256i; 18],
) {
for ((p, &init), &k) in state.p.iter_mut().zip(P_INIT.iter()).zip(kwv.iter()) {
*p = _mm256_xor_si256(_mm256_set1_epi32(init as i32), k);
}
for (entry, &init) in state.s.0.iter_mut().zip(S_INIT.as_flattened().iter()) {
*entry = [init; 8];
}
let (mut l, mut r) = (_mm256_setzero_si256(), _mm256_setzero_si256());
let mut j = 0usize;
for pair in 0..9 {
l = _mm256_xor_si256(l, swv[j % 4]);
j += 1;
r = _mm256_xor_si256(r, swv[j % 4]);
j += 1;
rounds16!(state, FLAVOR, l, r);
state.p[2 * pair] = l;
state.p[2 * pair + 1] = r;
}
for b in 0..4 {
for pair in 0..128 {
l = _mm256_xor_si256(l, swv[j % 4]);
j += 1;
r = _mm256_xor_si256(r, swv[j % 4]);
j += 1;
rounds16!(state, FLAVOR, l, r);
let e = b * 256 + 2 * pair;
unsafe {
_mm256_store_si256(state.s.0[e].as_mut_ptr().cast::<__m256i>(), l);
_mm256_store_si256(state.s.0[e + 1].as_mut_ptr().cast::<__m256i>(), r);
}
}
}
}
#[target_feature(enable = "avx2")]
#[inline]
fn encrypt_zero_chain_v8<const FLAVOR: u8>(state: &mut State8) {
let (mut l, mut r) = (_mm256_setzero_si256(), _mm256_setzero_si256());
for pair in 0..9 {
rounds16!(state, FLAVOR, l, r);
state.p[2 * pair] = l;
state.p[2 * pair + 1] = r;
}
for b in 0..4 {
for pair in 0..128 {
rounds16!(state, FLAVOR, l, r);
let e = b * 256 + 2 * pair;
unsafe {
_mm256_store_si256(state.s.0[e].as_mut_ptr().cast::<__m256i>(), l);
_mm256_store_si256(state.s.0[e + 1].as_mut_ptr().cast::<__m256i>(), r);
}
}
}
}
#[target_feature(enable = "avx2")]
#[inline]
fn expand0state_v8<const FLAVOR: u8>(state: &mut State8, wv: &[__m256i; 18]) {
for (p, &w) in state.p.iter_mut().zip(wv.iter()) {
*p = _mm256_xor_si256(*p, w);
}
encrypt_zero_chain_v8::<FLAVOR>(state);
}
#[target_feature(enable = "avx2")]
#[inline]
fn expand0state_salt_v8<const FLAVOR: u8>(state: &mut State8, swv: &[__m256i; 4]) {
for (i, p) in state.p.iter_mut().enumerate() {
*p = _mm256_xor_si256(*p, swv[i & 3]);
}
encrypt_zero_chain_v8::<FLAVOR>(state);
}
#[target_feature(enable = "avx2")]
#[inline]
fn transpose_keys(key_words: &[[u32; 18]]) -> [__m256i; 18] {
debug_assert_eq!(key_words.len(), LANES);
let mut out = [_mm256_setzero_si256(); 18];
for (i, v) in out.iter_mut().enumerate() {
*v = _mm256_setr_epi32(
key_words[0][i] as i32,
key_words[1][i] as i32,
key_words[2][i] as i32,
key_words[3][i] as i32,
key_words[4][i] as i32,
key_words[5][i] as i32,
key_words[6][i] as i32,
key_words[7][i] as i32,
);
}
out
}
#[target_feature(enable = "avx2")]
#[inline]
fn transpose_salts(salt_words: &[[u32; 4]]) -> [__m256i; 4] {
debug_assert_eq!(salt_words.len(), LANES);
let mut out = [_mm256_setzero_si256(); 4];
for (i, v) in out.iter_mut().enumerate() {
*v = _mm256_setr_epi32(
salt_words[0][i] as i32,
salt_words[1][i] as i32,
salt_words[2][i] as i32,
salt_words[3][i] as i32,
salt_words[4][i] as i32,
salt_words[5][i] as i32,
salt_words[6][i] as i32,
salt_words[7][i] as i32,
);
}
out
}
#[target_feature(enable = "avx2")]
#[inline]
unsafe fn bcrypt8<const FLAVOR: u8>(
cost: u32,
key_words: &[[u32; 18]],
salt_words: &[[u32; 4]],
outs: &mut [[u8; 24]],
) {
debug_assert!((4..=31).contains(&cost));
debug_assert_eq!(key_words.len(), LANES);
debug_assert_eq!(salt_words.len(), LANES);
debug_assert_eq!(outs.len(), LANES);
#[cfg_attr(not(feature = "zeroize"), allow(unused_mut))]
let mut kwv = transpose_keys(key_words);
let swv = transpose_salts(salt_words);
let mut state = State8 {
p: [_mm256_setzero_si256(); 18],
s: SBoxes8([[0; 8]; 1024]),
};
expand_state_v8::<FLAVOR>(&mut state, &swv, &kwv);
for _ in 0..(1u64 << cost) {
expand0state_v8::<FLAVOR>(&mut state, &kwv);
expand0state_salt_v8::<FLAVOR>(&mut state, &swv);
}
let mut cdata = [
_mm256_set1_epi32(0x4f72_7068),
_mm256_set1_epi32(0x6561_6e42),
_mm256_set1_epi32(0x6568_6f6c),
_mm256_set1_epi32(0x6465_7253),
_mm256_set1_epi32(0x6372_7944),
_mm256_set1_epi32(0x6f75_6274),
];
for _ in 0..64 {
for pair in 0..3 {
let (l, r) = encipher8::<FLAVOR>(&state, cdata[2 * pair], cdata[2 * pair + 1]);
cdata[2 * pair] = l;
cdata[2 * pair + 1] = r;
}
}
for (w, &cv) in cdata.iter().enumerate() {
let mut words = [0u32; 8];
unsafe { _mm256_storeu_si256(words.as_mut_ptr().cast::<__m256i>(), cv) };
for (lane, out) in outs.iter_mut().enumerate() {
out[4 * w..4 * w + 4].copy_from_slice(&words[lane].to_be_bytes());
}
}
#[cfg(feature = "zeroize")]
{
crate::wipe::secure_wipe_u32(unsafe {
core::slice::from_raw_parts_mut(state.p.as_mut_ptr().cast::<u32>(), 18 * 8)
});
crate::wipe::secure_wipe_u32(state.s.0.as_flattened_mut());
crate::wipe::secure_wipe_u32(unsafe {
core::slice::from_raw_parts_mut(cdata.as_mut_ptr().cast::<u32>(), 6 * 8)
});
crate::wipe::secure_wipe_u32(unsafe {
core::slice::from_raw_parts_mut(kwv.as_mut_ptr().cast::<u32>(), 18 * 8)
});
}
}
#[derive(Copy, Clone)]
enum Flavor {
Gather,
Insert,
Extract,
}
const FLAVOR_UNINIT: u8 = 0;
const FLAVOR_GATHER: u8 = 1;
const FLAVOR_INSERT: u8 = 2;
const FLAVOR_EXTRACT: u8 = 3;
static CACHED_FLAVOR: AtomicU8 = AtomicU8::new(FLAVOR_UNINIT);
const fn flavor_to_u8(flavor: Flavor) -> u8 {
match flavor {
Flavor::Gather => FLAVOR_GATHER,
Flavor::Insert => FLAVOR_INSERT,
Flavor::Extract => FLAVOR_EXTRACT,
}
}
const fn flavor_from_u8(value: u8) -> Flavor {
match value {
FLAVOR_GATHER => Flavor::Gather,
FLAVOR_EXTRACT => Flavor::Extract,
_ => Flavor::Insert,
}
}
#[inline]
fn flavor() -> Flavor {
let cached = CACHED_FLAVOR.load(Ordering::Relaxed);
if cached == FLAVOR_UNINIT {
pick_and_cache()
} else {
flavor_from_u8(cached)
}
}
#[cold]
#[inline(never)]
fn pick_and_cache() -> Flavor {
let picked = pick_flavor();
CACHED_FLAVOR.store(flavor_to_u8(picked), Ordering::Relaxed);
picked
}
#[cfg(all(feature = "std", not(debug_assertions), not(miri)))]
fn pick_flavor() -> Flavor {
shootout()
}
#[cfg(not(all(feature = "std", not(debug_assertions), not(miri))))]
fn pick_flavor() -> Flavor {
Flavor::Insert
}
#[cfg(all(feature = "std", not(debug_assertions), not(miri)))]
fn shootout() -> Flavor {
use std::time::Instant;
let mut rng = 0xBC79_7A5A_F1A0_0001u64;
let mut next_u32 = move || {
rng = rng.wrapping_add(0x9E37_79B9_7F4A_7C15);
let mut z = rng;
z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
(z ^ (z >> 31)) as u32
};
let mut kws = [[0u32; 18]; LANES];
let mut sws = [[0u32; 4]; LANES];
for w in kws.as_flattened_mut().iter_mut().chain(sws.as_flattened_mut()) {
*w = next_u32();
}
let mut outs = [[0u8; 24]; LANES];
unsafe { bcrypt8::<FLAVOR_GATHER>(4, &kws, &sws, &mut outs) };
let reference = outs;
unsafe { bcrypt8::<FLAVOR_INSERT>(4, &kws, &sws, &mut outs) };
assert_eq!(
outs, reference,
"avx2 flavor shootout: gather and insert kernels diverged — a kernel bug, not timing"
);
unsafe { bcrypt8::<FLAVOR_EXTRACT>(4, &kws, &sws, &mut outs) };
assert_eq!(
outs, reference,
"avx2 flavor shootout: gather and extract kernels diverged — a kernel bug, not timing"
);
let (mut best_gather, mut best_insert, mut best_extract) = (f64::MAX, f64::MAX, f64::MAX);
for _ in 0..3 {
let start = Instant::now();
unsafe { bcrypt8::<FLAVOR_GATHER>(4, &kws, &sws, &mut outs) };
best_gather = best_gather.min(start.elapsed().as_secs_f64());
let start = Instant::now();
unsafe { bcrypt8::<FLAVOR_INSERT>(4, &kws, &sws, &mut outs) };
best_insert = best_insert.min(start.elapsed().as_secs_f64());
let start = Instant::now();
unsafe { bcrypt8::<FLAVOR_EXTRACT>(4, &kws, &sws, &mut outs) };
best_extract = best_extract.min(start.elapsed().as_secs_f64());
core::hint::black_box(&mut outs);
}
if best_gather <= best_insert && best_gather <= best_extract {
Flavor::Gather
} else if best_insert <= best_extract {
Flavor::Insert
} else {
Flavor::Extract
}
}
#[target_feature(enable = "avx2")]
#[inline]
unsafe fn bcrypt_lanes_impl(
cost: u32,
key_words: &[[u32; 18]],
salt_words: &[[u32; 4]],
outs: &mut [[u8; 24]],
) {
debug_assert!((4..=31).contains(&cost));
debug_assert_eq!(key_words.len(), LANES);
debug_assert_eq!(salt_words.len(), LANES);
debug_assert_eq!(outs.len(), LANES);
match flavor() {
Flavor::Gather => unsafe { bcrypt8::<FLAVOR_GATHER>(cost, key_words, salt_words, outs) },
Flavor::Insert => unsafe { bcrypt8::<FLAVOR_INSERT>(cost, key_words, salt_words, outs) },
Flavor::Extract => unsafe { bcrypt8::<FLAVOR_EXTRACT>(cost, key_words, salt_words, outs) },
}
}
#[target_feature(enable = "avx2")]
pub unsafe fn bcrypt_lanes(
cost: u32,
key_words: &[[u32; 18]],
salt_words: &[[u32; 4]],
outs: &mut [[u8; 24]],
) {
debug_assert!((4..=31).contains(&cost));
debug_assert_eq!(key_words.len(), LANES);
debug_assert_eq!(salt_words.len(), LANES);
debug_assert_eq!(outs.len(), LANES);
unsafe { bcrypt_lanes_impl(cost, key_words, salt_words, outs) }
}
#[cfg(test)]
mod tests {
use super::*;
use crate::base64;
use crate::eks::{Backend, expand_key_words, salt_words};
fn key_words_for(password: &[u8]) -> [u32; 18] {
let mut key = [0u8; 72];
let copied = password.len().min(72);
key[..copied].copy_from_slice(&password[..copied]);
expand_key_words(&key, (copied + 1).min(72))
}
fn avx2_available() -> bool {
!cfg!(miri) && Backend::Avx2.is_available()
}
fn fixed_words() -> ([[u32; 18]; LANES], [[u32; 4]; LANES]) {
let mut rng = 0x853C_49E6_748F_EA9Bu64; let mut next_u32 = move || {
rng = rng.wrapping_add(0x9E37_79B9_7F4A_7C15);
let mut z = rng;
z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
(z ^ (z >> 31)) as u32
};
let mut kws = [[0u32; 18]; LANES];
let mut sws = [[0u32; 4]; LANES];
for w in kws.as_flattened_mut().iter_mut().chain(sws.as_flattened_mut()) {
*w = next_u32();
}
(kws, sws)
}
#[test]
fn flavors_agree() {
if !avx2_available() {
return;
}
let (kws, sws) = fixed_words();
let (mut gathered, mut inserted, mut extracted) =
([[0u8; 24]; LANES], [[0u8; 24]; LANES], [[0u8; 24]; LANES]);
unsafe {
bcrypt8::<FLAVOR_GATHER>(4, &kws, &sws, &mut gathered);
bcrypt8::<FLAVOR_INSERT>(4, &kws, &sws, &mut inserted);
bcrypt8::<FLAVOR_EXTRACT>(4, &kws, &sws, &mut extracted);
}
assert_eq!(gathered, inserted, "gather and insert flavors diverged");
assert_eq!(gathered, extracted, "gather and extract flavors diverged");
}
#[test]
fn lanes_match_scalar() {
if !avx2_available() {
return;
}
let vector_salt =
base64::decode_16(b"CCCCCCCCCCCCCCCCCCCCC.").expect("test salt must decode");
let passwords: [&[u8]; 8] = [
b"",
b"U*U",
b"hunter2",
&[0xAA; 72],
b"correct horse",
&[0x01],
&[0x55; 71],
&[0xFF; 100],
];
let kws: [[u32; 18]; 8] = core::array::from_fn(|i| key_words_for(passwords[i]));
let sws: [[u32; 4]; 8] = [
salt_words(&[0x11; 16]),
salt_words(&vector_salt),
salt_words(&[0x33; 16]),
salt_words(&[0x44; 16]),
salt_words(&[0x55; 16]),
salt_words(&[0x66; 16]),
salt_words(&[0x77; 16]),
salt_words(&[0x88; 16]),
];
let mut outs = [[0u8; 24]; 8];
unsafe { bcrypt_lanes(5, &kws, &sws, &mut outs) };
for lane in 0..LANES {
let mut expected = [0u8; 24];
crate::eks::scalar::bcrypt_lanes(
5,
&kws[lane..lane + 1],
&sws[lane..lane + 1],
core::slice::from_mut(&mut expected),
);
assert_eq!(outs[lane], expected, "lane {lane} diverged from scalar");
}
}
#[test]
fn flavor_pick_is_cached() {
if !avx2_available() {
return;
}
let first = flavor();
assert_ne!(CACHED_FLAVOR.load(Ordering::Relaxed), FLAVOR_UNINIT);
assert_eq!(flavor_to_u8(first), CACHED_FLAVOR.load(Ordering::Relaxed));
}
}