Skip to main content

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}