bcrypt_rust/eks/mod.rs
1//! EksBlowfish backend selection: one batch kernel per instruction set, chosen
2//! by **runtime** CPU feature detection.
3//!
4//! bcrypt's cost loop is `2^cost` iterations of two key expansions, each 521
5//! strictly sequential Blowfish encryptions — one hash cannot be parallelized.
6//! The SIMD backends therefore hash N *independent* passwords in lockstep, one
7//! per vector lane, and are reached only through the batch entry points in
8//! `crate::core`. A single hash always runs on [`Backend::Scalar`].
9//!
10//! # Kernel contract
11//!
12//! Every backend exposes one `bcrypt_lanes` with the [`BcryptLanesFn`]
13//! signature, hashing exactly [`Backend::lanes`] passwords per call. Inputs are
14//! pre-digested by the caller (see `crate::core`):
15//!
16//! * `key_words[lane][i]` — the password's i-th cyclical big-endian key word
17//! (the 72-byte-padded, NUL-terminated bcrypt key stream reduced to the 18
18//! words the P-array XOR actually consumes);
19//! * `salt_words[lane][i]` — the lane's 16-byte salt as 4 big-endian words;
20//! * `outs[lane]` — receives the 24-byte ciphertext (of which callers encode 23).
21//!
22//! Pre-computing the words in safe scalar code keeps the byte-cycling logic in
23//! exactly one tested place; the kernels are pure lockstep vector code.
24//!
25//! # Cost model
26//!
27//! * Detection runs at most once per process. The result is cached in a
28//! [`AtomicU8`] read with [`Ordering::Relaxed`]. The initialisation race is
29//! benign: every thread computes the same answer, so a duplicated `detect()`
30//! only wastes a `cpuid`. The one expensive decision — the width shootout,
31//! when it applies — is single-flight behind a `OnceLock`: racing cold
32//! callers park until the winner publishes instead of each duplicating the
33//! ~0.4 s measurement and timing it under self-inflicted contention.
34//! * A batch call resolves the function pointer **once**, before chunking into
35//! lane-width groups (see `crate::core`). Nothing dispatches inside the
36//! per-group loop.
37//! * Per batch: one relaxed load plus one compare. Per group: one indirect
38//! call. A group is `lanes` full bcrypt hashes — expensive at any realistic
39//! cost — so dispatch overhead is nil.
40//!
41//! # The x86-64 width shootout (AVX2 vs AVX-512, AVX2x12 where it fits)
42//!
43//! Wider is not automatically faster for bcrypt. Every lane carries a 4 KiB
44//! mutable S-box working set, so the 16-lane AVX-512 kernel's struct-of-
45//! arrays touches 64 KiB per group — twice the 32 KiB L1d of Zen 3/4, whose
46//! 512-bit ops are also double-pumped — while Sapphire Rapids has a 6.0c zmm
47//! hardware gather and 48 KiB L1d, where the wide kernel pulls clearly ahead
48//! (`docs/research/research-x86-microarch.md`, §4–7). The measured spread on
49//! this crate confirms both sides: Zen 4 is at parity (avx2 888.6 vs avx512
50//! 889.2 hashes/s, cost 5 batch 16, rustc 1.99) while SPR-class cores favor
51//! AVX-512 decisively. No vendor table captures that split — Zen 5, mobile
52//! Zen 5 and Turin Dense all differ again — so [`detect`] settles it by
53//! *measurement*: with `std`, optimized code and no Miri, a CPU advertising
54//! both AVX2 and AVX-512F runs a one-time width shootout — the same fixed
55//! 48-password batch at cost 4 through the candidate backends' normal
56//! kernels (which also settles each backend's own flavor shootout), outputs
57//! asserted byte-identical across ALL arms before anything is timed (a
58//! mismatch is a kernel bug, not a tie), three interleaved timed reps each,
59//! min wins. The winner is cached in `CACHED_WIDTH`; a tie keeps the static
60//! order. The one-time cost is measured, not theoretical: ~0.4 s on the
61//! shared 4-vCPU Zen 4 sandbox (a cost-4 hash there is ~0.55 ms, and the
62//! batch is hashed four times per arm — once for the assert, three for the
63//! clock — plus each backend's own flavor shootout; the winner's would be
64//! paid by the first batch call anyway). Debug, `no_std` and Miri builds
65//! never time anything — they keep the static `Avx512`-first order.
66//!
67//! A third arm joins the shootout only where the cache geometry allows:
68//! [`Backend::Avx2x12`], twelve AVX2 lanes (eight ymm + four xmm) whose
69//! 48 KiB working set is exactly the L1d of Zen 5, Ice Lake and later Intel
70//! cores. [`l1d_size`] probes cpuid leaf 4 and admits the arm at ≥ 48 KiB.
71//! The candidate set is built from independent capabilities — `Avx512` when
72//! advertised, `Avx2` always, `Avx2x12` when the gate holds — so AVX2-only
73//! 48 KiB-L1d hosts (Alder/Raptor Lake client cores, where AVX-512 is fused
74//! off, and the homogeneous Xeon E-2400) measure the 12-lane arm too; with
75//! a single candidate (plain AVX2 hosts) no clock is spent at all. The arm
76//! is picked only on a strict timed win — ties keep the wider incumbent
77//! (`avx512 > avx2 > avx2x12`) — and the 12-lane kernel is never in the
78//! static fallback order. One caveat for hybrid parts: leaf 4 is
79//! per-logical-processor while the pick is process-global, so a pick
80//! measured on a P-core can later run on an E-core's 32 KiB L1d — a
81//! bounded, batch-only regression class that the AVX2 gather-flavor pick
82//! already has there (and detection running on an E-core fails closed).
83//!
84//! # `no_std`
85//!
86//! Runtime detection needs `std`. Without the `std` feature, [`detect`] falls
87//! back to compile-time `cfg(target_feature = ...)` and then to
88//! [`Backend::Scalar`].
89//!
90//! # Testing under Rosetta on aarch64-apple-darwin
91//!
92//! `is_x86_feature_detected!` expands to
93//! `cfg!(target_feature = "...") || runtime_cpuid_check()`, so a compile-time
94//! `target_feature` short-circuits it to `true`. That matters here because
95//! Rosetta 2 *executes* AVX2 but does not advertise it in `cpuid`:
96//!
97//! * `cargo test --target x86_64-apple-darwin` — [`detect`] stops at
98//! [`Backend::Sse41`] and `Backend::Avx2.is_available()` is `false`.
99//! * `RUSTFLAGS="-C target-feature=+avx2" cargo test --target x86_64-apple-darwin`
100//! — [`detect`] returns [`Backend::Avx2`] and it really runs.
101//! * Never add `+avx512f`: `is_available()` would then report `true` while the
102//! instruction itself traps with `SIGILL` (Rosetta has no AVX-512).
103//!
104//! # Forcing a backend: `BCRYPT_FORCE_BACKEND`
105//!
106//! `BCRYPT_FORCE_BACKEND=<name>` (std builds only) pins [`detect`] to one
107//! backend and skips the width shootout — an escape hatch for simulators
108//! and emulators that implement fewer instructions than the host CPU
109//! advertises. CodSpeed's Valgrind-based instrument has no AVX-512, so the
110//! benchmark CI pins `avx2`: it is the widest width the instrument fully
111//! implements, and one pinned backend keeps the performance history
112//! comparable across the Intel/AMD runner lottery. Unknown or unavailable
113//! names panic loudly; a silently ignored force would hide exactly the
114//! dispatch mistake it exists to pin down. Miri's Scalar pin outranks the
115//! variable — a forced SIMD backend would only crash the interpreter.
116
117use core::sync::atomic::{AtomicU8, Ordering};
118
119pub mod scalar;
120
121#[cfg(target_arch = "aarch64")]
122pub mod neon;
123
124#[cfg(target_arch = "x86_64")]
125pub mod avx2;
126
127#[cfg(target_arch = "x86_64")]
128pub mod avx2x12;
129
130#[cfg(target_arch = "x86_64")]
131pub mod avx512;
132
133#[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
134pub mod sse41;
135
136// WebAssembly has no runtime feature detection a module can survive (SIMD
137// instructions fail validation on engines that lack them), so the module
138// exists exactly when `cfg(all(target_arch = "wasm32", target_feature =
139// "simd128"))` held at compile time — the same condition
140// `have_wasm_simd128` answers from.
141#[cfg(all(target_arch = "wasm32", target_feature = "simd128"))]
142pub mod wasm128;
143
144// ---------------------------------------------------------------------------
145// Backend
146// ---------------------------------------------------------------------------
147
148/// Which `bcrypt_lanes` implementation to use.
149///
150/// A variant is added every time another ISA is ported, so this is
151/// `#[non_exhaustive]` — write a `_` arm downstream. [`Backend::ALL`] is a
152/// slice for the same reason: its length must not be part of the API.
153#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash, PartialOrd, Ord)]
154#[repr(u8)]
155#[non_exhaustive]
156pub enum Backend {
157 /// Portable scalar code, one lane. Always available.
158 Scalar = 0,
159 /// AArch64 NEON, 8 lanes.
160 Neon = 1,
161 /// x86 / x86-64 SSE4.1 (`pinsrd`/`pextrd` for lane construction), 4 lanes.
162 Sse41 = 2,
163 /// x86-64 AVX2, 8 lanes. Two internal flavours (hardware gather vs
164 /// load+insert); a one-time shootout picks per CPU — AMD Zen gathers are
165 /// microcoded and lose.
166 Avx2 = 3,
167 /// x86-64 AVX-512F, 16 lanes. Same flavour shootout as AVX2.
168 Avx512 = 4,
169 /// wasm32 fixed-width SIMD128, 8 lanes as two interleaved 4-lane
170 /// `v128` states (X2). Compile-time selected.
171 Wasm128 = 5,
172 /// x86-64 AVX2, 12 lanes as one 8-lane ymm group plus one 4-lane xmm
173 /// group in lockstep (48 KiB SoA working set, insert/extract lookup
174 /// flavours only — no gather). Never in the static fallback order:
175 /// reachable only through the measured width shootout on hosts whose
176 /// L1d is at least 48 KiB (Zen 5, Ice Lake+), or by explicit force.
177 Avx2x12 = 6,
178}
179
180/// The signature every backend's batch kernel has.
181///
182/// `key_words`, `salt_words` and `outs` must all have length
183/// [`Backend::lanes`] for the backend the pointer was resolved for.
184///
185/// # Safety
186///
187/// Calling one of these requires:
188///
189/// * the CPU to support the backend's instruction set — check
190/// [`Backend::is_available`], or get the pointer from [`bcrypt_lanes_fn`]
191/// fed by [`backend`];
192/// * the three slices to be valid and of exactly the backend's lane count;
193/// * no other thread to be writing `outs` at the same time.
194pub type BcryptLanesFn = unsafe fn(u32, &[[u32; 18]], &[[u32; 4]], &mut [[u8; 24]]);
195
196impl Backend {
197 /// Every backend, in ascending preference order.
198 pub const ALL: &'static [Backend] = &[
199 Backend::Scalar,
200 Backend::Neon,
201 Backend::Sse41,
202 Backend::Avx2,
203 Backend::Avx2x12,
204 Backend::Avx512,
205 Backend::Wasm128,
206 ];
207
208 /// Short lowercase name, handy for bench ids and test output.
209 #[inline]
210 #[must_use]
211 pub const fn name(self) -> &'static str {
212 match self {
213 Backend::Scalar => "scalar",
214 Backend::Neon => "neon",
215 Backend::Sse41 => "sse41",
216 Backend::Avx2 => "avx2",
217 Backend::Avx512 => "avx512",
218 Backend::Wasm128 => "wasm128",
219 Backend::Avx2x12 => "avx2_12",
220 }
221 }
222
223 /// Passwords hashed per kernel call — the vector width in 32-bit lanes.
224 #[inline]
225 #[must_use]
226 pub const fn lanes(self) -> usize {
227 match self {
228 Backend::Scalar => 1,
229 Backend::Neon => 8,
230 Backend::Sse41 => 4,
231 Backend::Avx2 => 8,
232 Backend::Avx512 => 16,
233 Backend::Avx2x12 => 12,
234 // The kernel's lane count lives next to the kernel; the
235 // module only exists on simd128-enabled wasm32, so off-arch
236 // builds keep the constant inline (the backend is never
237 // available there — the value is dead).
238 #[cfg(all(target_arch = "wasm32", target_feature = "simd128"))]
239 Backend::Wasm128 => wasm128::LANES,
240 #[cfg(not(all(target_arch = "wasm32", target_feature = "simd128")))]
241 Backend::Wasm128 => 8,
242 }
243 }
244
245 /// Whether this CPU can execute this backend *right now*.
246 ///
247 /// Unlike `detect`, this asks about one specific backend, so tests and
248 /// benches can loop over [`Backend::ALL`] and skip what the host cannot run.
249 #[inline]
250 #[must_use]
251 pub fn is_available(self) -> bool {
252 match self {
253 Backend::Scalar => true,
254 Backend::Neon => have_neon(),
255 Backend::Sse41 => have_sse41(),
256 Backend::Avx2 => have_avx2(),
257 Backend::Avx512 => have_avx512f(),
258 // The kernel is plain AVX2 code: any AVX2 CPU executes it
259 // correctly. The 48 KiB-L1d gate is a *selection* rule (the
260 // width shootout), not an availability rule — a forced
261 // `BCRYPT_FORCE_BACKEND=avx2_12` must run anywhere AVX2 does.
262 Backend::Avx2x12 => have_avx2(),
263 Backend::Wasm128 => have_wasm_simd128(),
264 }
265 }
266
267 #[inline]
268 const fn to_u8(self) -> u8 {
269 self as u8
270 }
271
272 /// Total inverse of [`Backend::to_u8`]; anything unknown maps to
273 /// [`Backend::Scalar`] so the cache can never produce a panic.
274 #[inline]
275 const fn from_u8(value: u8) -> Backend {
276 match value {
277 1 => Backend::Neon,
278 2 => Backend::Sse41,
279 3 => Backend::Avx2,
280 4 => Backend::Avx512,
281 5 => Backend::Wasm128,
282 6 => Backend::Avx2x12,
283 _ => Backend::Scalar,
284 }
285 }
286}
287
288impl core::fmt::Display for Backend {
289 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
290 f.write_str(self.name())
291 }
292}
293
294// ---------------------------------------------------------------------------
295// Per-feature probes
296// ---------------------------------------------------------------------------
297//
298// Each probe is defined twice under mutually exclusive `cfg`s, so exactly one
299// definition ever exists and there is no dead or unreachable code. With `std`
300// the probe is a real runtime check; without it, it degrades to the
301// compile-time `target_feature` cfg.
302
303#[cfg(all(feature = "std", target_arch = "x86_64"))]
304#[inline]
305fn have_avx512f() -> bool {
306 std::arch::is_x86_feature_detected!("avx512f")
307}
308#[cfg(not(all(feature = "std", target_arch = "x86_64")))]
309#[inline]
310fn have_avx512f() -> bool {
311 cfg!(all(target_arch = "x86_64", target_feature = "avx512f"))
312}
313
314#[cfg(all(feature = "std", target_arch = "x86_64"))]
315#[inline]
316fn have_avx2() -> bool {
317 std::arch::is_x86_feature_detected!("avx2")
318}
319#[cfg(not(all(feature = "std", target_arch = "x86_64")))]
320#[inline]
321fn have_avx2() -> bool {
322 cfg!(all(target_arch = "x86_64", target_feature = "avx2"))
323}
324
325#[cfg(all(feature = "std", any(target_arch = "x86", target_arch = "x86_64")))]
326#[inline]
327fn have_sse41() -> bool {
328 std::arch::is_x86_feature_detected!("sse4.1")
329}
330#[cfg(not(all(feature = "std", any(target_arch = "x86", target_arch = "x86_64"))))]
331#[inline]
332fn have_sse41() -> bool {
333 cfg!(all(
334 any(target_arch = "x86", target_arch = "x86_64"),
335 target_feature = "sse4.1"
336 ))
337}
338
339#[cfg(all(feature = "std", target_arch = "aarch64"))]
340#[inline]
341fn have_neon() -> bool {
342 // NEON (Advanced SIMD) is in the architectural baseline Apple and
343 // Windows guarantee for aarch64; probing the OS for it would be a
344 // formality, so on those platforms the answer is compile-time.
345 #[cfg(any(target_vendor = "apple", target_os = "windows"))]
346 {
347 true
348 }
349 #[cfg(not(any(target_vendor = "apple", target_os = "windows")))]
350 {
351 std::arch::is_aarch64_feature_detected!("neon")
352 }
353}
354#[cfg(not(all(feature = "std", target_arch = "aarch64")))]
355#[inline]
356fn have_neon() -> bool {
357 cfg!(all(target_arch = "aarch64", target_feature = "neon"))
358}
359
360/// wasm32 SIMD128. There is no runtime probe a wasm module can survive
361/// (SIMD instructions fail validation where unsupported), so the answer is
362/// purely compile-time: it is `true` exactly when the crate was built with
363/// `-C target-feature=+simd128`.
364#[cfg(all(target_arch = "wasm32", target_feature = "simd128"))]
365#[inline]
366fn have_wasm_simd128() -> bool {
367 true
368}
369#[cfg(not(all(target_arch = "wasm32", target_feature = "simd128")))]
370#[inline]
371fn have_wasm_simd128() -> bool {
372 false
373}
374
375// ---------------------------------------------------------------------------
376// Detection and caching
377// ---------------------------------------------------------------------------
378
379/// Sentinel meaning "detection has not run yet". Not a valid [`Backend`] value.
380const UNINIT: u8 = 0xFF;
381
382/// Cached [`Backend`] as a `u8`, or [`UNINIT`].
383static CACHED_BACKEND: AtomicU8 = AtomicU8::new(UNINIT);
384
385/// Run the feature cascade and return the best backend for this CPU.
386///
387/// Preference order: `Avx512 > Avx2 > Sse41` on x86(-64), `Neon` on AArch64,
388/// `Wasm128` on simd128-enabled wasm32, `Scalar` everywhere else. The probes
389/// are arch-gated, so the single cascade below cannot pick an off-arch backend.
390/// The one exception to the static order is the module-level width shootout:
391/// where it applies it can demote `Avx512` to `Avx2` — or, on hosts whose
392/// L1d is at least 48 KiB, to `Avx2x12` — by measurement.
393///
394/// `BCRYPT_FORCE_BACKEND` (std only) outranks all of this, cascade and
395/// shootout alike — see the module docs.
396///
397/// The cascade itself always re-runs (a few `cpuid` reads, each cached by the
398/// standard library); the one expensive decision — the width shootout, when
399/// it applies — is cached after the first call, so a repeated `detect()`
400/// stays cheap. Use [`backend`] for the fully cached value.
401#[must_use]
402pub fn detect() -> Backend {
403 if cfg!(miri) {
404 // Miri interprets the crate: its intrinsic support stops around
405 // SSE2, and wall-clock flavour shootouts mean nothing under an
406 // interpreter. Scalar is the one backend that behaves identically
407 // on every host Miri runs on, which is also what makes the Miri CI
408 // job arch-independent. The pin also outranks BCRYPT_FORCE_BACKEND:
409 // forcing a SIMD backend there would only crash the interpreter.
410 return Backend::Scalar;
411 }
412 // A forced backend outranks the cascade and the width shootout alike.
413 #[cfg(feature = "std")]
414 if let Some(forced) = forced_backend() {
415 return forced;
416 }
417 if have_avx512f() || have_avx2() {
418 // Which widths exist, and which actually wins, is a µarch question
419 // the width shootout answers where it can (module docs); a single
420 // candidate spends no clock.
421 width_pick()
422 } else if have_sse41() {
423 Backend::Sse41
424 } else if have_neon() {
425 Backend::Neon
426 } else if have_wasm_simd128() {
427 Backend::Wasm128
428 } else {
429 Backend::Scalar
430 }
431}
432
433/// Total inverse of [`Backend::name`].
434#[cfg(feature = "std")]
435fn backend_by_name(name: &str) -> Option<Backend> {
436 Backend::ALL.iter().copied().find(|b| b.name() == name)
437}
438
439/// The `BCRYPT_FORCE_BACKEND=<name>` escape hatch, or `None` when unset.
440/// Unknown or unavailable names panic loudly: a silently ignored force
441/// would hide exactly the dispatch mistake it exists to pin down.
442#[cfg(feature = "std")]
443fn forced_backend() -> Option<Backend> {
444 let raw = std::env::var_os("BCRYPT_FORCE_BACKEND")?;
445 let name = raw
446 .to_str()
447 .unwrap_or_else(|| panic!("BCRYPT_FORCE_BACKEND is not UTF-8"));
448 let backend = backend_by_name(name).unwrap_or_else(|| {
449 let valid = Backend::ALL
450 .iter()
451 .map(|b| b.name())
452 .collect::<std::vec::Vec<_>>()
453 .join(", ");
454 panic!("BCRYPT_FORCE_BACKEND={name}: unknown backend (valid: {valid})");
455 });
456 assert!(
457 backend.is_available(),
458 "BCRYPT_FORCE_BACKEND={name} but {name} is not available on this host"
459 );
460 Some(backend)
461}
462
463/// Detect and populate the cache. Outlined so [`backend`] stays tiny.
464#[cold]
465#[inline(never)]
466fn detect_and_cache() -> Backend {
467 let detected = detect();
468 // Relaxed is enough: the value is a plain `u8` with no associated data, and
469 // every thread that races here computes the same answer.
470 CACHED_BACKEND.store(detected.to_u8(), Ordering::Relaxed);
471 detected
472}
473
474/// The backend for this process: one relaxed atomic load on the hot path.
475///
476/// Deliberately not a `OnceLock` — acquire ordering would buy nothing here
477/// (there is no data to publish) and `OnceLock` needs `std`.
478#[inline]
479#[must_use]
480pub fn backend() -> Backend {
481 let cached = CACHED_BACKEND.load(Ordering::Relaxed);
482 if cached == UNINIT {
483 detect_and_cache()
484 } else {
485 Backend::from_u8(cached)
486 }
487}
488
489// ---------------------------------------------------------------------------
490// Width shootout: AVX2 vs AVX-512 vs AVX2x12 (x86-64, std, optimized,
491// non-Miri only)
492// ---------------------------------------------------------------------------
493
494/// The measured width-shootout winner as a `u8`. `OnceLock::get_or_init`
495/// makes the pick single-flight: racing cold callers park until the winner
496/// publishes, so the ~0.4 s measurement runs at most once per process and
497/// never under self-inflicted contention (which could stick the process
498/// with the wrong pick). Only ever holds [`Backend::Avx2`],
499/// [`Backend::Avx512`] or [`Backend::Avx2x12`].
500#[cfg(all(feature = "std", target_arch = "x86_64", not(debug_assertions), not(miri)))]
501static WIDTH_PICK: std::sync::OnceLock<u8> = std::sync::OnceLock::new();
502
503/// The L1 data cache size in bytes from cpuid leaf 4 (Deterministic Cache
504/// Parameters), or `None` when the leaf describes no L1 data cache. Only
505/// the width shootout asks: [`Backend::Avx2x12`] joins the arm list exactly
506/// when the answer is at least 48 KiB — the L1d of Zen 5, Ice Lake and
507/// later Intel cores, and exactly the 12-lane kernel's working set.
508#[cfg(all(feature = "std", target_arch = "x86_64", not(debug_assertions), not(miri)))]
509// cpuid is a plain read-only instruction, but on our MSRV (1.89) it is
510// still declared `unsafe fn`; newer rustc marks it safe, so the unsafe
511// blocks would warn there — allow(unused_unsafe) keeps both toolchains
512// warning-free.
513#[allow(unused_unsafe)]
514fn l1d_size() -> Option<usize> {
515 use core::arch::x86_64::{__cpuid, __cpuid_count};
516 // Leaf 4 exists on every CPU the shootout can run on (AVX-512F is
517 // decades newer), but a hypervisor could mask it — probe defensively.
518 // SAFETY: cpuid is a read-only, always-available instruction; it is
519 // declared `unsafe fn` only on the MSRV (see the fn-level note).
520 if unsafe { __cpuid(0) }.eax < 4 {
521 return None;
522 }
523 // Sub-leaves enumerate the cache hierarchy; type 0 ends the list. The
524 // 16-iteration cap is paranoia against a broken cpuid, never hit in
525 // practice (real hierarchies have ≤ 4 entries).
526 for sub_leaf in 0..16u32 {
527 // SAFETY: same as above — read-only instruction, unsafe only on
528 // the MSRV toolchain.
529 let r = unsafe { __cpuid_count(4, sub_leaf) };
530 let cache_type = r.eax & 0x1f;
531 if cache_type == 0 {
532 break;
533 }
534 // Type 1 = data cache, level field 1 = L1.
535 if cache_type == 1 && (r.eax >> 5) & 0x7 == 1 {
536 let line_size = (r.ebx & 0xfff) as usize + 1;
537 let partitions = ((r.ebx >> 12) & 0x3ff) as usize + 1;
538 let ways = ((r.ebx >> 22) & 0x3ff) as usize + 1;
539 let sets = r.ecx as usize + 1;
540 return Some(line_size * partitions * ways * sets);
541 }
542 }
543 None
544}
545
546/// Which x86-64 width actually wins on *this* CPU, measured. The candidate
547/// set is built from independent capabilities — `Avx512` when advertised,
548/// `Avx2` always, [`Backend::Avx2x12`] when the 48 KiB-L1d gate holds (its
549/// kernel is AVX2 code) — so AVX2-only 48 KiB hosts (Alder/Raptor Lake
550/// client, Xeon E-2400) measure the 12-lane arm too. A single candidate
551/// spends no clock at all; two or more run the one-time shootout behind
552/// [`WIDTH_PICK`]'s single-flight init (module docs).
553#[cfg(all(feature = "std", target_arch = "x86_64", not(debug_assertions), not(miri)))]
554fn width_pick() -> Backend {
555 let avx512 = have_avx512f();
556 let avx2 = have_avx2();
557 let x12 = avx2 && l1d_size().is_some_and(|bytes| bytes >= 48 * 1024);
558 if !avx2 {
559 // No shipping AVX-512F CPU lacks AVX2; keep the static answer.
560 return Backend::Avx512;
561 }
562 if !avx512 && !x12 {
563 // One candidate — nothing to measure.
564 return Backend::Avx2;
565 }
566 Backend::from_u8(*WIDTH_PICK.get_or_init(|| width_shootout(avx512, x12).to_u8()))
567}
568
569/// See the measuring variant above. Debug builds, `no_std` and Miri keep the
570/// static order: timing unoptimized/interpreted intrinsics measures the
571/// codegen mode, not the µarch — and without `std` there is no clock at all
572/// (the flavor shootouts make the same trade). The answer still follows
573/// capability, so an AVX2-only host never names a backend it lacks.
574#[cfg(not(all(feature = "std", target_arch = "x86_64", not(debug_assertions), not(miri))))]
575fn width_pick() -> Backend {
576 if have_avx512f() {
577 Backend::Avx512
578 } else {
579 Backend::Avx2
580 }
581}
582
583/// The one-time width shootout: the candidate x86-64 SIMD backends hash the
584/// same fixed deterministic 48-password batch at cost 4 — correctness first
585/// (outputs asserted byte-identical across ALL arms; a mismatch is a kernel
586/// bug, not a tie), then three interleaved timed reps each, min per arm.
587/// [`width_pick`] builds the arm list from capabilities: `Avx2` always,
588/// `Avx512` when advertised, [`Backend::Avx2x12`] when the 48 KiB-L1d gate
589/// holds (its kernel is AVX2 code, already proven present). Arms are in
590/// tie-preference order — `avx512 > avx2 > avx2x12` — and an arm must be
591/// STRICTLY faster
592/// than the reigning arm to take the title, so a tie keeps the wider
593/// incumbent and the 12-lane kernel is picked only on an outright win. The
594/// batch is 48 items — six AVX2 groups / three AVX-512 groups / four
595/// AVX2x12 groups, the lcm of the arm lane counts — so no padded tail
596/// distorts any side and every arm hashes the same 48 passwords, making
597/// raw elapsed time a per-hash comparison.
598#[cfg(all(feature = "std", target_arch = "x86_64", not(debug_assertions), not(miri)))]
599fn width_shootout(has_avx512: bool, has_x12: bool) -> Backend {
600 use std::time::Instant;
601
602 // SplitMix64, fixed seed: deterministic inputs (not a CSPRNG, nor does
603 // it need to be).
604 let mut rng = 0xBC79_7A5A_F1A0_0003u64;
605 let mut next_u32 = move || {
606 rng = rng.wrapping_add(0x9E37_79B9_7F4A_7C15);
607 let mut z = rng;
608 z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
609 z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
610 (z ^ (z >> 31)) as u32
611 };
612 const ITEMS: usize = 48;
613 let mut kws = [[0u32; 18]; ITEMS];
614 let mut sws = [[0u32; 4]; ITEMS];
615 for w in kws.as_flattened_mut().iter_mut().chain(sws.as_flattened_mut()) {
616 *w = next_u32();
617 }
618
619 // One backend's kernel over the whole batch, in lane-width groups — the
620 // same dispatch `crate::core`'s chunk loop performs.
621 fn run_batch(
622 kernel: BcryptLanesFn,
623 lanes: usize,
624 kws: &[[u32; 18]; ITEMS],
625 sws: &[[u32; 4]; ITEMS],
626 outs: &mut [[u8; 24]; ITEMS],
627 ) {
628 let mut base = 0;
629 while base < ITEMS {
630 // SAFETY: `width_pick` admitted every arm only when this CPU
631 // advertises its instruction set (the AVX2x12 kernel is AVX2
632 // code, and AVX2 is always present here). `ITEMS` is a multiple
633 // of every arm's lane count, so each group slice is exactly
634 // `lanes` long, and each `outs` group is exclusively owned by
635 // this frame.
636 unsafe {
637 kernel(
638 4,
639 &kws[base..base + lanes],
640 &sws[base..base + lanes],
641 &mut outs[base..base + lanes],
642 )
643 };
644 base += lanes;
645 }
646 }
647
648 // The arm list, in tie-preference order, from the capabilities
649 // `width_pick` established. Avx2 is always a candidate — its presence
650 // is what let detection reach the shootout at all — so the array is
651 // Avx2-initialized and only the conditional arms are written.
652 let mut arms = [(Backend::Avx2, bcrypt_lanes_fn(Backend::Avx2)); 3];
653 let mut n = 0;
654 if has_avx512 {
655 arms[n] = (Backend::Avx512, bcrypt_lanes_fn(Backend::Avx512));
656 n += 1;
657 }
658 n += 1;
659 if has_x12 {
660 arms[n] = (Backend::Avx2x12, bcrypt_lanes_fn(Backend::Avx2x12));
661 n += 1;
662 }
663 let arms = &arms[..n];
664
665 let mut outs = [[[0u8; 24]; ITEMS]; 3];
666 // Correctness before timing: these first calls also run each arm's own
667 // flavor shootout, so all kernels are fully warmed before the clock
668 // starts.
669 for (i, &(backend, kernel)) in arms.iter().enumerate() {
670 run_batch(kernel, backend.lanes(), &kws, &sws, &mut outs[i]);
671 assert_eq!(
672 outs[i], outs[0],
673 "width shootout: {} and {} kernels diverged — a kernel bug, not timing",
674 backend.name(),
675 arms[0].0.name(),
676 );
677 }
678 let mut best = [f64::MAX; 3];
679 for _ in 0..3 {
680 for (i, &(backend, kernel)) in arms.iter().enumerate() {
681 let start = Instant::now();
682 run_batch(kernel, backend.lanes(), &kws, &sws, &mut outs[i]);
683 best[i] = best[i].min(start.elapsed().as_secs_f64());
684 core::hint::black_box(&mut outs[i]);
685 }
686 }
687 // An arm takes the title only by being strictly faster than the
688 // reigning arm; arms are in tie-preference order, so ties keep the
689 // wider incumbent.
690 let (mut pick, mut pick_best) = (arms[0].0, best[0]);
691 for (i, &(backend, _)) in arms.iter().enumerate().skip(1) {
692 if best[i] < pick_best {
693 pick = backend;
694 pick_best = best[i];
695 }
696 }
697 pick
698}
699
700/// The `bcrypt_lanes` implementation for `backend`.
701///
702/// Resolve this **once per batch call**, outside every loop.
703///
704/// On an architecture that has no module for the requested backend, this
705/// returns the scalar implementation rather than failing to compile, so tests
706/// can iterate over [`Backend::ALL`] on any host. It does **not** check
707/// availability: a pointer for a backend this CPU lacks will fault when called.
708/// Use [`Backend::is_available`] first, or take the value from [`backend`].
709#[must_use]
710pub fn bcrypt_lanes_fn(backend: Backend) -> BcryptLanesFn {
711 // On-arch Neon, Sse41, Avx2, Avx512 and (compile-time-gated) Wasm128
712 // run their real kernels; every off-arch arm resolves to scalar.
713 match backend {
714 Backend::Scalar => scalar::bcrypt_lanes,
715 #[cfg(target_arch = "aarch64")]
716 Backend::Neon => neon::bcrypt_lanes,
717 #[cfg(not(target_arch = "aarch64"))]
718 Backend::Neon => scalar::bcrypt_lanes,
719 #[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
720 Backend::Sse41 => sse41::bcrypt_lanes,
721 #[cfg(not(any(target_arch = "x86", target_arch = "x86_64")))]
722 Backend::Sse41 => scalar::bcrypt_lanes,
723 #[cfg(target_arch = "x86_64")]
724 Backend::Avx2 => avx2::bcrypt_lanes,
725 #[cfg(not(target_arch = "x86_64"))]
726 Backend::Avx2 => scalar::bcrypt_lanes,
727 #[cfg(target_arch = "x86_64")]
728 Backend::Avx512 => avx512::bcrypt_lanes,
729 #[cfg(not(target_arch = "x86_64"))]
730 Backend::Avx512 => scalar::bcrypt_lanes,
731 #[cfg(target_arch = "x86_64")]
732 Backend::Avx2x12 => avx2x12::bcrypt_lanes,
733 #[cfg(not(target_arch = "x86_64"))]
734 Backend::Avx2x12 => scalar::bcrypt_lanes,
735 #[cfg(all(target_arch = "wasm32", target_feature = "simd128"))]
736 Backend::Wasm128 => wasm128::bcrypt_lanes,
737 #[cfg(not(all(target_arch = "wasm32", target_feature = "simd128")))]
738 Backend::Wasm128 => scalar::bcrypt_lanes,
739 }
740}
741
742/// Reduce a padded bcrypt key stream to the 18 cyclical big-endian words the
743/// P-array XOR consumes — OpenBSD `Blowfish_stream2word` applied 18 times.
744///
745/// `key` is the 72-byte buffer and `key_len` the cycling length (1..=72):
746/// word `i` is `key[j]<<24 | key[j+1]<<16 | key[j+2]<<8 | key[j+3]` with each
747/// index taken mod `key_len`. Only 18 words (72 bytes) are ever read, which is
748/// why a ≥72-byte password's appended NUL never participates.
749#[must_use]
750pub(crate) fn expand_key_words(key: &[u8; 72], key_len: usize) -> [u32; 18] {
751 debug_assert!((1..=72).contains(&key_len));
752 let mut words = [0u32; 18];
753 let mut j = 0usize;
754 for w in &mut words {
755 let mut word = 0u32;
756 for _ in 0..4 {
757 if j >= key_len {
758 j = 0;
759 }
760 word = (word << 8) | u32::from(key[j]);
761 j += 1;
762 }
763 *w = word;
764 }
765 words
766}
767
768/// The 16-byte salt as 4 big-endian words, matching `stream2word` on a
769/// 16-byte input (which never wraps: 16 is a multiple of 4).
770#[must_use]
771pub(crate) fn salt_words(salt: &[u8; 16]) -> [u32; 4] {
772 let mut words = [0u32; 4];
773 for (w, chunk) in words.iter_mut().zip(salt.chunks_exact(4)) {
774 *w = u32::from_be_bytes([chunk[0], chunk[1], chunk[2], chunk[3]]);
775 }
776 words
777}
778
779#[cfg(test)]
780mod tests {
781 use super::*;
782
783 #[test]
784 fn backend_u8_round_trip() {
785 for &b in Backend::ALL {
786 assert_eq!(Backend::from_u8(b.to_u8()), b);
787 }
788 // The sentinel and anything unknown must degrade, never panic.
789 assert_eq!(Backend::from_u8(UNINIT), Backend::Scalar);
790 assert_eq!(Backend::from_u8(200), Backend::Scalar);
791 }
792
793 #[test]
794 fn cache_agrees_with_detect() {
795 let first = backend();
796 assert_eq!(first, detect());
797 // Second call takes the cached path.
798 assert_eq!(backend(), first);
799 assert_ne!(CACHED_BACKEND.load(Ordering::Relaxed), UNINIT);
800 }
801
802 /// Where both x86-64 SIMD backends exist, detection's pick is one of
803 /// the shootout's arms and stable across calls — the winner is cached.
804 /// Hosts without both widths (including Miri, which pins Scalar, and
805 /// Rosetta, which lacks AVX-512) have no pick to make: skip.
806 #[cfg(feature = "std")]
807 #[test]
808 fn backend_by_name_round_trips_every_variant() {
809 for &b in Backend::ALL {
810 assert_eq!(backend_by_name(b.name()), Some(b));
811 }
812 // Exact, case-sensitive match only.
813 assert_eq!(backend_by_name("AVX2"), None);
814 assert_eq!(backend_by_name("avx-512"), None);
815 assert_eq!(backend_by_name(""), None);
816 }
817
818 #[test]
819 fn width_pick_is_stable_and_cached() {
820 // An active force bypasses the shootout entirely.
821 #[cfg(feature = "std")]
822 if std::env::var_os("BCRYPT_FORCE_BACKEND").is_some() {
823 return;
824 }
825 if cfg!(miri) || !Backend::Avx2.is_available() {
826 return;
827 }
828 let first = detect();
829 assert!(matches!(
830 first,
831 Backend::Avx2 | Backend::Avx512 | Backend::Avx2x12
832 ));
833 // Second call reads the cached pick: same answer, and where the
834 // shootout has at least two candidates its cache is populated.
835 assert_eq!(detect(), first);
836 #[cfg(all(feature = "std", target_arch = "x86_64", not(debug_assertions), not(miri)))]
837 if Backend::Avx512.is_available() || l1d_size().is_some_and(|bytes| bytes >= 48 * 1024) {
838 assert!(WIDTH_PICK.get().is_some());
839 }
840 }
841
842 #[test]
843 fn detected_backend_is_available() {
844 assert!(detect().is_available());
845 assert!(Backend::Scalar.is_available());
846 }
847
848 #[test]
849 fn detection_respects_the_architecture() {
850 // This test asserts unforced detection; an active force is doing
851 // exactly what it promises and must not trip the per-arch checks.
852 #[cfg(feature = "std")]
853 if std::env::var_os("BCRYPT_FORCE_BACKEND").is_some() {
854 return;
855 }
856 if cfg!(miri) {
857 // Detection is compile-time pinned to Scalar under Miri (the
858 // interpreter implements no SIMD intrinsics); the pin itself
859 // is what there is to check there.
860 assert_eq!(detect(), Backend::Scalar);
861 return;
862 }
863 if cfg!(target_arch = "aarch64") {
864 assert!(!have_sse41());
865 assert!(!have_avx2());
866 assert!(!have_avx512f());
867 // NEON is baseline on aarch64-apple-darwin.
868 if cfg!(target_vendor = "apple") {
869 assert_eq!(detect(), Backend::Neon);
870 } else {
871 assert!(matches!(detect(), Backend::Neon | Backend::Scalar));
872 }
873 }
874 if cfg!(target_arch = "x86_64") {
875 assert!(!have_neon());
876 assert!(matches!(
877 detect(),
878 Backend::Sse41
879 | Backend::Avx2
880 | Backend::Avx512
881 | Backend::Avx2x12
882 | Backend::Scalar
883 ));
884 }
885 if cfg!(target_arch = "wasm32") {
886 assert!(!have_sse41());
887 assert!(!have_avx2());
888 assert!(!have_avx512f());
889 assert!(!have_neon());
890 if cfg!(target_feature = "simd128") {
891 assert_eq!(detect(), Backend::Wasm128);
892 } else {
893 assert_eq!(detect(), Backend::Scalar);
894 }
895 }
896 }
897
898 #[test]
899 fn every_backend_resolves_to_a_function() {
900 for &b in Backend::ALL {
901 let f = bcrypt_lanes_fn(b);
902 // Function pointers may compare unequal even for the same
903 // function, and Miri exercises that freedom — the identity
904 // check is native-only; under Miri, resolving must not panic.
905 if b == Backend::Scalar && !cfg!(miri) {
906 let scalar = bcrypt_lanes_fn(Backend::Scalar);
907 assert!(core::ptr::fn_addr_eq(f, scalar));
908 }
909 }
910 }
911
912 #[test]
913 fn expand_key_words_cycles_big_endian() {
914 // "a" + NUL: key_len 2, words cycle over bytes [0x61, 0x00].
915 let mut key = [0u8; 72];
916 key[0] = b'a';
917 let w = expand_key_words(&key, 2);
918 assert_eq!(w[0], 0x61006100);
919 assert_eq!(w[17], 0x61006100);
920 // A full-length key: word i reads bytes 4i..4i+3, no wrap.
921 let key72: [u8; 72] = core::array::from_fn(|i| i as u8);
922 let w = expand_key_words(&key72, 72);
923 assert_eq!(w[0], 0x00010203);
924 assert_eq!(w[17], 0x44454647);
925 // key_len 71 wraps inside word 17: bytes 68,69,70, then byte 0.
926 let w = expand_key_words(&key72, 71);
927 assert_eq!(w[17], 0x44454600);
928 }
929
930 #[test]
931 fn salt_words_are_big_endian() {
932 let salt: [u8; 16] = core::array::from_fn(|i| (i + 1) as u8);
933 assert_eq!(
934 salt_words(&salt),
935 [0x01020304, 0x05060708, 0x090A0B0C, 0x0D0E0F10]
936 );
937 }
938}