wai-quantum 0.4.1

//! The gate kernel in WGSL, and everything a WebGPU member needs that is not
//! the device. Pure Rust: compiled and tested on every target.
//!
//! [`SHADER`] is the kernel: [`lanes`] transcribed line for line into WGSL,
//! with every value a `u32` holding a 32-bit two's-complement pattern, and an
//! exact 64-bit copy of every result beside it so that the kernel reports any
//! result that leaves 32 bits. Its entry point `apply` runs one gate over the
//! whole state, one invocation per amplitude pair, in place; `probe` runs the
//! wide multiply and the exact `fx` on listed operands. Around it, this module
//! holds what a host needs: the implementation id ([`implementation_id`]), the
//! 64-byte gate record ([`gate_record`]), the dispatch grid ([`grid`],
//! [`gate_grid`]), the id of a member built on an adapter
//! ([`AdapterIdentity`]), and the textual edits of the kernel a device must be
//! caught running ([`MUTANTS`]).
//!
//! The state is two planes, `re` and `im`, each `2^n` `u32` words. The report
//! is two atomic words: `report[0]` collects bit 1 (a result left 32 bits),
//! bit 2 (an index outside the state) and bit 4 (a malformed record), and
//! `report[1]` the lowest op-log index that set bit 1. The host writes
//! `(0, 0xffffffff)` before a run.
//!
//! # Why the kernel is bit-exact
//!
//! **Lemma 1 (the same function).** Line for line:
//!
//! | [`lanes`] (Rust) | WGSL | Why equal |
//! |---|---|---|
//! | `a < 0` | `neg(a)` | the two's-complement sign bit |
//! | `a.unsigned_abs()` | `select(a, 0u - a, neg(a))` | for `a < 0`, \|a\| = 2^32 − pattern(a) = `0u − a` modulo 2^32, the most negative value (→ 2^31) included |
//! | `x >> 16`, `x & 0xffff` | the same | logical shift and mask |
//! | `wrapping_mul` of halves | `*` | every partial product is below 2^32: exact in both |
//! | `wrapping_add`, `u32::from(mid < p01)` | `+`, `bit(mid < p01)` | `u32` addition modulo 2^32; `u32` comparison |
//! | `p00.wrapping_add(mid << 16)` | `p00 + (mid << 16u)` | `<<` discards the high bits in both |
//! | `(!lo).wrapping_add(1)`, … | `~lo + 1u`, … | complement, then addition modulo 2^32 |
//! | `fxmul`: `lo2`, `hi2`, `(lo2 >> 30) \| (hi2 << 2)` | `fx64(..).y` | identical expressions |
//! | `cmul`, `cadd` with wrapping 32-bit operations | the low words of `add64`, `sub64` | the low word of a 64-bit sum is the 32-bit wrapping sum of the low words |
//! | `(a0, a1)` read before both stores | `a0`, `a1` loaded before any store | the same data dependence |
//!
//! No partial product reaches 2^32 (`x0·y1 ≤ 0xffff·0x8000`), so no `u32`
//! multiply wraps; `mid_carry` is always zero and is kept so that the
//! transcription stays literal. The only intended wraps are the carry
//! additions, `mid << 16u`, the two's-complement negation, and the low words of
//! `add64` and `sub64`. So for every state and every record, the stored words
//! equal those of [`lanes::apply_words`], and report bit 1 is raised exactly
//! when it returns `Some(false)`. For a record whose `pairs` is half the
//! state's length, report bit 4 is raised exactly when it returns `None`: the
//! same predicate on `tbit` and `ctrl`.
//!
//! **Lemma 2 (`fx64` is exact).** `mul_wide` is exact for every pair of 32-bit
//! values; `|a·b| ≤ 2^62`, so adding 2^29 cannot overflow 64 bits; and an
//! arithmetic shift of `(hi2:lo2)` by 30 has as its low word bits 30 to 61,
//! `(lo2 >> 30) | (hi2 << 2)`, and as its high word `hi2 >> 30` with the sign
//! copied into bits 2 to 31, which is `EXT30`. Each output part is a sum of four
//! such values, each at most about 2^32 in size, so `add64` and `sub64` hold
//! it exactly, and `fits` (the high word repeats the low word's sign) is true
//! exactly when the value is a 32-bit one.
//!
//! **Lemma 3 (no dynamic error).** The map from `p` to `i`, a zero inserted at
//! bit `t`, is strictly increasing on `[0, 2^(n−1))` with inverse "delete bit
//! `t`": a bijection onto the indices with bit `t` clear, the set
//! [`lanes::apply`] visits. `p = id.y·row_stride + id.x` with
//! `id.x < row_stride` is injective, and the host's grid ([`gate_grid`])
//! covers every `p` below `pairs`. Every array access is guarded by
//! `arrayLength` and `i < j`, and a malformed record never reaches an access.
//! The pairs partition the indices, so no two invocations touch one location;
//! `report` is touched only by atomics; the record and `arrayLength` are only
//! read.
//!
//! **Lemma 4 (order does not matter).** Each invocation reads and writes only
//! its own pair, so a dispatch's result does not depend on the order in which
//! invocations run, and equals the sequential loop of [`lanes::apply`], whose
//! iterations also touch disjoint pairs. Dispatches run in queue order, each its
//! own usage scope. The final values of `atomicOr` and `atomicMin` do not depend
//! on order.
//!
//! **Theorem.** On an implementation that conforms for the constructs the
//! kernel uses (`u32` `+ − *` modulo 2^32; `~ & | ^`; shifts by literal amounts
//! below 32; `== != <`; `select`; relaxed `atomicOr` and `atomicMin`;
//! little-endian buffer layout; dispatches in queue order), dispatching `apply`
//! once per gate in op-log order over [`gate_grid`] gives the lanes and
//! `out_of_range` of [`plan::execute`]. With the exact range guard, if no gate
//! is reported, the state equals that of
//! [`Circuit::simulate_from`](crate::quantum::Circuit::simulate_from); a valid
//! circuit of at most [`lanes::horizon`] gates cannot have a gate reported.
//!
//! The kernel holds no signed type, no float, no division, no conversion or
//! bitcast, no workgroup memory and no barrier, and every shift amount is a
//! literal between 1 and 31: so the kernel brings no signed overflow, no shift
//! by 32 or more and no signed right shift into any language it is translated
//! to. The rules are checked on the translator's own reading of the text by
//! the unpublished crate `wai/tools/quantum-wgsl-check`.
//!
//! # What the argument does not cover
//!
//! Whether a device and its shader compiler conform is not proved here. A
//! member earns that per adapter: by reproducing the pinned corpus digests of
//! [`FABRIC_DEFAULT`](super::FABRIC_DEFAULT), and by being caught running each
//! of [`MUTANTS`]. Any edit to [`SHADER`] or to the host layout is a new
//! implementation, with a new [`implementation_id`], whose certificates must be
//! earned again.
//!
//! [`lanes`]: super::lanes
//! [`lanes::apply`]: super::lanes::apply
//! [`lanes::apply_words`]: super::lanes::apply_words
//! [`lanes::horizon`]: super::lanes::horizon
//! [`plan::execute`]: super::plan::execute

use super::lanes::GateWords;
use super::{FabricClass, put};
use crate::quantum::MAX_QUBITS;

/// The kernel, `lanes32.wgsl`, exactly as it is compiled.
pub const SHADER: &str = include_str!("lanes32.wgsl");

/// The implementation name the id starts with.
pub const IMPLEMENTATION: &str = "wgsl-lanes32";

/// Version of the host-side layout: planar `u32` planes, the 64-byte gate
/// record, the grid rule. Bumped on any change to them; it is part of the
/// implementation id.
pub const HOST_LAYOUT: u32 = 1;

/// Invocations per workgroup, as the kernel declares.
pub const WORKGROUP: u32 = 64;

/// Workgroups along x, at most. Production and certification use the same
/// value, so two-dimensional grids (14 qubits or more) occur inside the
/// certification corpus.
pub const X_GROUPS_MAX: u32 = 64;

/// Bytes of one gate record, the kernel's `Gate` uniform.
pub const GATE_RECORD_BYTES: usize = 64;

const DOMAIN_IMPLEMENTATION: &[u8] = b"wai:quantum-fabric-wgsl\x01";
const DOMAIN_MEMBER: &[u8] = b"wai:quantum-fabric-webgpu-member\x01";

fn hex(bytes: &[u8]) -> String {
    bytes.iter().map(|b| format!("{b:02x}")).collect()
}

/// `"wgsl-lanes32/<16 hex>"`: the first 8 bytes of
/// BLAKE3(`"wai:quantum-fabric-wgsl\x01"` ‖ put([`SHADER`]) ‖ [`HOST_LAYOUT`]
/// as a big-endian `u32`), in hex. Any edit to the kernel's text or to the host
/// layout changes it.
pub fn implementation_id() -> String {
    let mut o = DOMAIN_IMPLEMENTATION.to_vec();
    put(&mut o, SHADER.as_bytes());
    o.extend_from_slice(&HOST_LAYOUT.to_be_bytes());
    format!("{IMPLEMENTATION}/{}", hex(&blake3::hash(&o).as_bytes()[..8]))
}

/// The 64-byte little-endian uniform record of one gate: `m[0..8]`, `tbit`,
/// `ctrl`, `pairs`, `row_stride`, `index`, then three zero words.
pub fn gate_record(w: &GateWords, pairs: u32, row_stride: u32, index: u32) -> [u8; GATE_RECORD_BYTES] {
    let mut r = [0u8; GATE_RECORD_BYTES];
    let words = w.m.into_iter().chain([w.tbit, w.ctrl, pairs, row_stride, index, 0, 0, 0]);
    for (k, v) in words.enumerate() {
        r[4 * k..4 * k + 4].copy_from_slice(&v.to_le_bytes());
    }
    r
}

/// A dispatch: `x` by `y` workgroups of [`WORKGROUP`] invocations, where the
/// invocation at `(gx, gy)` handles item `gy·row_stride + gx` if it is below
/// `items`.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Grid {
    pub x: u32,
    pub y: u32,
    pub row_stride: u32,
    pub items: u32,
}

/// Workgroups covering `items` invocations: `groups = ⌈items / 64⌉`,
/// `x = min(groups, max_x)`, `y = ⌈groups / x⌉`, `row_stride = 64·x`.
///
/// Panics if `items` or `max_x` is zero, or if `64·x` does not fit in 32 bits.
pub fn grid(items: u32, max_x: u32) -> Grid {
    assert!(items >= 1 && max_x >= 1, "a grid covers at least one item, with at least one workgroup along x");
    let groups = items.div_ceil(WORKGROUP);
    let x = groups.min(max_x);
    let row_stride = WORKGROUP.checked_mul(x).expect("the row stride fits in 32 bits");
    Grid { x, y: groups.div_ceil(x), row_stride, items }
}

/// The grid of one gate on `n_qubits`: `grid(2^(n−1), X_GROUPS_MAX)`, one
/// invocation per amplitude pair.
///
/// Panics unless `1 ≤ n_qubits ≤ MAX_QUBITS`.
pub fn gate_grid(n_qubits: u8) -> Grid {
    assert!((1..=MAX_QUBITS).contains(&n_qubits), "a gate acts on 1 to {MAX_QUBITS} qubits, not {n_qubits}");
    grid(1 << (n_qubits - 1), X_GROUPS_MAX)
}

/// What a WebGPU member is, as its id hashes it. The device module fills it
/// from the adapter's information and the granted limits; the fields are plain
/// values here so that the id is testable without a device.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct AdapterIdentity {
    /// `"metal"`, `"vulkan"`, `"dx12"` or `"webgpu"`.
    pub backend: String,
    pub name: String,
    pub vendor: u32,
    pub device: u32,
    /// `"discrete"`, `"integrated"`, `"virtual"`, `"cpu"` or `"other"`.
    pub device_type: String,
    pub pci_bus: String,
    pub driver: String,
    pub driver_info: String,
    /// What turns WGSL into the platform's shader language, as the device
    /// module names it: `"naga"` natively, followed where a bytecode compiler
    /// is pinned by the bytecode format it emits (`"naga+dxbc"` on DX12), and
    /// `"user-agent"` for a browser's own compiler.
    pub translator: String,
    pub max_storage_binding: u64,
    pub max_buffer: u64,
}

impl AdapterIdentity {
    fn software(&self) -> bool {
        self.device_type == "cpu"
    }

    /// [`FabricClass::Cpu`] for a software adapter (device type `"cpu"`),
    /// [`FabricClass::Gpu`] otherwise.
    pub fn class(&self) -> FabricClass {
        if self.software() { FabricClass::Cpu } else { FabricClass::Gpu }
    }

    /// `"local/gpu-<backend>-<d12>"`, or `"local/swgpu-<backend>-<d12>"` for a
    /// software adapter. `d12` is the first 12 hex digits of
    /// BLAKE3(`"wai:quantum-fabric-webgpu-member\x01"` ‖ put(backend) ‖
    /// put(name) ‖ vendor ‖ device ‖ put(device_type) ‖ put(pci_bus) ‖
    /// put(driver) ‖ put(driver_info) ‖ put(translator) ‖ max_storage_binding ‖
    /// max_buffer), the numbers big-endian.
    ///
    /// Every such id sorts after every `local/cpu-<arch>`, so with no energy
    /// figures [`place`](super::place) keeps the CPU reference: a software
    /// adapter is class `Cpu`, but its id does not begin `local/cpu-`.
    pub fn member_id(&self) -> String {
        let mut o = DOMAIN_MEMBER.to_vec();
        put(&mut o, self.backend.as_bytes());
        put(&mut o, self.name.as_bytes());
        o.extend_from_slice(&self.vendor.to_be_bytes());
        o.extend_from_slice(&self.device.to_be_bytes());
        for s in [&self.device_type, &self.pci_bus, &self.driver, &self.driver_info, &self.translator] {
            put(&mut o, s.as_bytes());
        }
        o.extend_from_slice(&self.max_storage_binding.to_be_bytes());
        o.extend_from_slice(&self.max_buffer.to_be_bytes());
        let d12 = hex(&blake3::hash(&o).as_bytes()[..6]);
        format!("local/{}-{}-{d12}", self.prefix(), self.backend)
    }

    /// The key a runner declares in CI: `"<gpu|swgpu>-<backend>-<vendor in
    /// lowercase hex>"`, for instance `"gpu-metal-0"` or `"swgpu-vulkan-10005"`.
    pub fn key(&self) -> String {
        format!("{}-{}-{:x}", self.prefix(), self.backend, self.vendor)
    }

    fn prefix(&self) -> &'static str {
        if self.software() { "swgpu" } else { "gpu" }
    }
}

/// How a device that runs a mutant must be caught.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Detector {
    /// The arithmetic probe's outputs differ from the CPU's on the probe edges.
    Probe,
    /// The corpus digest differs from the pinned one.
    Certificate,
    /// A result that left 32 bits is not reported.
    Range,
}

/// A textual edit of [`SHADER`] that a conforming device must be caught
/// running.
#[derive(Clone, Copy, Debug)]
pub struct Mutant {
    pub name: &'static str,
    pub find: &'static str,
    pub replace: &'static str,
    pub detector: Detector,
}

/// The mutants. Each `find` occurs exactly once in [`SHADER`]. `mid_carry` is
/// always zero, so an edit of it would change nothing and is not among them.
pub const MUTANTS: [Mutant; 7] = [
    // fx64 takes the wrong 32 bits of the rounded product.
    Mutant { name: "M1", find: "let lo = (lo2 >> 30u) | (hi2 << 2u);", replace: "let lo = (lo2 >> 29u) | (hi2 << 3u);", detector: Detector::Probe },
    // mul_wide never negates.
    Mutant { name: "M2", find: "let negative = neg(a) != neg(b);", replace: "let negative = false;", detector: Detector::Probe },
    // The rounding constant is one short.
    Mutant { name: "M3", find: "const HALF: u32 = 0x20000000u;", replace: "const HALF: u32 = 0x1fffffffu;", detector: Detector::Probe },
    // The carry out of the low word is dropped.
    Mutant { name: "M4", find: "let lo_carry = bit(lo < p00);", replace: "let lo_carry = 0u;", detector: Detector::Probe },
    // The control test is inverted.
    Mutant { name: "M5", find: "if ((i & g.ctrl) != g.ctrl) { return; }", replace: "if ((i & g.ctrl) == g.ctrl) { return; }", detector: Detector::Certificate },
    // The range guard never fires.
    Mutant { name: "M6", find: "fn fits(v: vec2<u32>) -> bool { return v.x == select(0u, ONES, neg(v.y)); }", replace: "fn fits(v: vec2<u32>) -> bool { return true; }", detector: Detector::Range },
    // The arithmetic shift by 30 loses the sign.
    Mutant { name: "M7", find: "const EXT30: u32 = 0xfffffffcu;", replace: "const EXT30: u32 = 0x00000000u;", detector: Detector::Probe },
];

/// [`SHADER`] with `m` applied. Panics unless `m.find` occurs exactly once.
pub fn mutate(m: &Mutant) -> String {
    let n = SHADER.matches(m.find).count();
    assert_eq!(n, 1, "mutant {}: `{}` occurs {n} times in the kernel", m.name, m.find);
    SHADER.replacen(m.find, m.replace, 1)
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::quantum::{BaseGate, Gate, Gateset};
    use crate::quantum_fabric::lanes::{self, Lane};
    use crate::quantum_fabric::{Certificate, Corpus, FABRIC_DEFAULT, KernelEntry, Member, Parity, Presence, apply_kernel, detect_local, place};

    /// Changes only with a reviewed edit to the kernel and to the argument in
    /// this module's documentation (or to the host layout, with
    /// [`HOST_LAYOUT`]): every certificate of the old id must then be earned
    /// again.
    const PINNED_IMPLEMENTATION: &str = "wgsl-lanes32/dc8e19f61e0e87ab";

    #[test]
    fn implementation_id_is_pinned() {
        let id = implementation_id();
        assert_eq!(id, PINNED_IMPLEMENTATION);
        let digest = id.strip_prefix("wgsl-lanes32/").expect("the implementation name");
        assert_eq!(digest.len(), 16);
        assert!(digest.bytes().all(|b| b.is_ascii_digit() || (b'a'..=b'f').contains(&b)), "{id}");
        assert_eq!(implementation_id(), id);
        // The kernel is stored with LF line endings.
        assert!(!SHADER.contains('\r'));
    }

    #[test]
    fn gate_record_layout() {
        let w = GateWords { m: [1, 2, 3, 4, 5, 6, 7, 8], tbit: 4, ctrl: 3 };
        let r = gate_record(&w, 16, 64, 9);
        let word = |k: usize| u32::from_le_bytes(r[4 * k..4 * k + 4].try_into().unwrap());
        for k in 0..8 {
            assert_eq!(r[4 * k..4 * k + 4], (k as u32 + 1).to_le_bytes(), "m[{k}]");
        }
        assert_eq!((word(8), word(9), word(10), word(11), word(12)), (4, 3, 16, 64, 9));
        assert_eq!(r[52..64], [0; 12]);
        // Little-endian: the low byte first.
        let r = gate_record(&GateWords { m: [0x8000_0001, 0, 0, 0, 0, 0, 0, 0], tbit: 1, ctrl: 0 }, 1, 64, 0x0102_0304);
        assert_eq!(r[0..4], [0x01, 0x00, 0x00, 0x80]);
        assert_eq!(r[48..52], [0x04, 0x03, 0x02, 0x01]);
    }

    #[test]
    fn grids_cover_every_item_once() {
        for n in 1..=26u32 {
            let items = 1u32 << (n - 1);
            for max_x in [1, 3, X_GROUPS_MAX] {
                let g = grid(items, max_x);
                assert_eq!((g.items, g.row_stride), (items, WORKGROUP * g.x));
                assert!(g.x >= 1 && g.x <= max_x && g.y >= 1, "{g:?}");
                let per_row = u64::from(g.x) * u64::from(WORKGROUP);
                assert!(per_row * u64::from(g.y) >= u64::from(items), "n = {n}, {g:?}");
                assert!(per_row * u64::from(g.y - 1) < u64::from(items), "n = {n}, {g:?}");
                if max_x == X_GROUPS_MAX {
                    assert!(g.y <= 65535, "n = {n}, {g:?}");
                    assert_eq!(gate_grid(n as u8), g);
                }
                if n <= 12 {
                    let mut hits = vec![0u32; items as usize];
                    for gy in 0..g.y {
                        for gx in 0..g.row_stride {
                            let p = gy * g.row_stride + gx;
                            if p < items {
                                hits[p as usize] += 1;
                            }
                        }
                    }
                    assert!(hits.iter().all(|&h| h == 1), "n = {n}, {g:?}");
                }
            }
            // The dispatch shapes fabric-v1 is checked to cover: up to 6
            // qubits part of one workgroup, 7 to 13 one row, 14 or more a grid.
            let g = gate_grid(n as u8);
            assert_eq!(n <= 6, items < WORKGROUP, "n = {n}");
            assert_eq!((7..=13).contains(&n), items >= WORKGROUP && g.y == 1, "n = {n}");
            assert_eq!(n >= 14, g.y > 1, "n = {n}");
        }
    }

    /// The kernel's index map: `p` with a zero inserted at the target bit.
    fn insert0(p: u32, tbit: u32) -> u32 {
        let low = p & (tbit - 1);
        ((p ^ low) << 1) | low
    }

    #[test]
    fn the_index_map_is_a_bijection() {
        for n in 1..=12u32 {
            for t in 0..n {
                let tbit = 1u32 << t;
                let mapped: Vec<u32> = (0..1u32 << (n - 1)).map(|p| insert0(p, tbit)).collect();
                let clear: Vec<u32> = (0..1u32 << n).filter(|i| i & tbit == 0).collect();
                // Strictly increasing and onto the indices with bit t clear.
                assert_eq!(mapped, clear, "n = {n}, t = {t}");
            }
        }
    }

    fn hardware() -> AdapterIdentity {
        AdapterIdentity {
            backend: "metal".into(),
            name: "Test GPU".into(),
            vendor: 0,
            device: 0,
            device_type: "integrated".into(),
            pci_bus: String::new(),
            driver: String::new(),
            driver_info: String::new(),
            translator: "naga".into(),
            max_storage_binding: 1 << 28,
            max_buffer: 1 << 28,
        }
    }

    fn software() -> AdapterIdentity {
        AdapterIdentity {
            backend: "vulkan".into(),
            name: "Test software rasterizer".into(),
            vendor: 0x10005,
            device: 0,
            device_type: "cpu".into(),
            pci_bus: String::new(),
            driver: "test-driver".into(),
            driver_info: "1.0".into(),
            translator: "naga".into(),
            max_storage_binding: 1 << 27,
            max_buffer: 1 << 28,
        }
    }

    /// The ids of [`hardware`] and [`software`]. They change only with a
    /// reviewed change to what a member id hashes; every certificate earned
    /// under an old id must then be earned again.
    const PINNED_HARDWARE: &str = "local/gpu-metal-a47619e299a8";
    const PINNED_SOFTWARE: &str = "local/swgpu-vulkan-917c9bb1d948";

    #[test]
    fn member_ids_are_pinned() {
        let (hw, sw) = (hardware(), software());
        assert_eq!((hw.member_id(), sw.member_id()), (PINNED_HARDWARE.to_string(), PINNED_SOFTWARE.to_string()));
        assert_eq!((hw.class(), sw.class()), (FabricClass::Gpu, FabricClass::Cpu));
        assert_eq!((hw.key(), sw.key()), ("gpu-metal-0".to_string(), "swgpu-vulkan-10005".to_string()));
        // Every field is in the id.
        let edits: [fn(&mut AdapterIdentity); 11] = [
            |a| a.backend.push('x'),
            |a| a.name.push('x'),
            |a| a.vendor ^= 1,
            |a| a.device ^= 1,
            |a| a.device_type = if a.device_type == "cpu" { "virtual".into() } else { "discrete".into() },
            |a| a.pci_bus.push('0'),
            |a| a.driver.push('x'),
            |a| a.driver_info.push('x'),
            |a| a.translator.push_str("+bytecode"),
            |a| a.max_storage_binding += 1,
            |a| a.max_buffer += 1,
        ];
        for base in [hw, sw] {
            for (k, edit) in edits.iter().enumerate() {
                let mut a = base.clone();
                edit(&mut a);
                assert_ne!(a.member_id(), base.member_id(), "field {k} of {base:?}");
            }
        }
        // Fields do not run into each other.
        let mut a = hardware();
        let mut b = hardware();
        (a.driver, a.driver_info) = ("ab".into(), String::new());
        (b.driver, b.driver_info) = ("a".into(), "b".into());
        assert_ne!(a.member_id(), b.member_id());
    }

    #[test]
    fn the_cpu_reference_is_placed_first_when_nothing_is_metered() {
        for arch in ["aarch64", "x86_64", "x86", "wasm32", "riscv64", "arm", "s390x", "powerpc64", "loongarch64"] {
            let cpu = format!("local/cpu-{arch}");
            assert!(cpu.as_str() < PINNED_HARDWARE && cpu.as_str() < PINNED_SOFTWARE, "{cpu}");
        }
        let local = detect_local();
        for gs in Gateset::ALL {
            let kernel = apply_kernel(gs);
            let member = |a: &AdapterIdentity| {
                let id = a.member_id();
                let certificate = Certificate {
                    kernel: kernel.into(),
                    implementation: implementation_id(),
                    member: id.clone(),
                    generator: FABRIC_DEFAULT.generator(gs),
                    parity: Parity::BitExact,
                    cases: 224,
                    corpus: [7; 32],
                };
                let entry = KernelEntry { kernel: kernel.into(), implementation: implementation_id(), certificate, energy: None };
                Member { id, class: a.class(), presence: Presence::Detected, kernels: vec![entry], detail: String::new() }
            };
            let (gpu, swgpu) = (member(&hardware()), member(&software()));
            // Each member is placeable on its own.
            for m in [&gpu, &swgpu] {
                let (placed, k) = place(std::slice::from_ref(m), kernel, &Parity::BitExact).unwrap();
                assert_eq!((placed.id.as_str(), k.implementation.as_str()), (m.id.as_str(), implementation_id().as_str()));
            }
            // Beside the CPU, with no energy figure anywhere, the reference stays.
            for members in [vec![local.clone(), gpu.clone()], vec![gpu.clone(), swgpu.clone(), local.clone()]] {
                let (m, k) = place(&members, kernel, &Parity::BitExact).unwrap();
                assert_eq!((m.id.as_str(), k.implementation.as_str()), (local.id.as_str(), crate::quantum_fabric::REFERENCE), "{gs:?}");
            }
        }
    }

    #[test]
    fn mutants_apply_once() {
        let names: Vec<&str> = MUTANTS.iter().map(|m| m.name).collect();
        assert_eq!(names, ["M1", "M2", "M3", "M4", "M5", "M6", "M7"]);
        for m in &MUTANTS {
            let text = mutate(m);
            assert_ne!(text, SHADER, "{}", m.name);
            assert_eq!(text.matches(m.replace).count(), 1, "{}", m.name);
            assert_eq!(text.len() as isize - SHADER.len() as isize, m.replace.len() as isize - m.find.len() as isize);
        }
        let detectors: Vec<Detector> = MUTANTS.iter().map(|m| m.detector).collect();
        use Detector::*;
        assert_eq!(detectors, [Probe, Probe, Probe, Probe, Certificate, Range, Probe]);
    }

    /// The kernel's `mul_wide` and `fx64` in Rust, line for line, with one of
    /// the probe-detected mutants applied (or none): `[hi, lo, fx_hi, fx_lo]`,
    /// what the probe entry point writes.
    fn probe_mirror(a: u32, b: u32, mutant: &str) -> [u32; 4] {
        let neg = |x: u32| x & 0x8000_0000 != 0;
        let bit = |c: bool| u32::from(c);
        let half: u32 = if mutant == "M3" { 0x1fff_ffff } else { 0x2000_0000 };
        let ext30: u32 = if mutant == "M7" { 0 } else { 0xffff_fffc };
        // mul_wide
        let negative = if mutant == "M2" { false } else { neg(a) != neg(b) };
        let x = if neg(a) { 0u32.wrapping_sub(a) } else { a };
        let y = if neg(b) { 0u32.wrapping_sub(b) } else { b };
        let (x1, x0, y1, y0) = (x >> 16, x & 0xffff, y >> 16, y & 0xffff);
        let (p00, p01, p10, p11) = (x0 * y0, x0 * y1, x1 * y0, x1 * y1);
        let mid = p01.wrapping_add(p10);
        let mid_carry = bit(mid < p01);
        let lo = p00.wrapping_add(mid << 16);
        let lo_carry = if mutant == "M4" { 0 } else { bit(lo < p00) };
        let hi = p11.wrapping_add(mid >> 16).wrapping_add(mid_carry << 16).wrapping_add(lo_carry);
        let (hi, lo) = if negative {
            let lo_n = (!lo).wrapping_add(1);
            ((!hi).wrapping_add(bit(lo_n == 0)), lo_n)
        } else {
            (hi, lo)
        };
        // fx64
        let lo2 = lo.wrapping_add(half);
        let hi2 = hi.wrapping_add(bit(lo2 < lo));
        let fx_lo = if mutant == "M1" { (lo2 >> 29) | (hi2 << 3) } else { (lo2 >> 30) | (hi2 << 2) };
        let fx_hi = (hi2 >> 30) | if neg(hi2) { ext30 } else { 0 };
        [hi, lo, fx_hi, fx_lo]
    }

    fn probe_reference(a: i32, b: i32) -> [u32; 4] {
        let ((hi, lo), (fx_hi, fx_lo)) = (lanes::mul_wide(a, b), lanes::fxmul_wide(a, b));
        [hi, lo, fx_hi, fx_lo]
    }

    /// `apply_words` with the control test inverted (M5): a pair is updated
    /// when its control bits are not all set.
    fn apply_inverted_control(amps: &mut [Lane], w: &GateWords) {
        let fx = |a: i32, b: i32| {
            let (hi, lo) = lanes::fxmul_wide(a, b);
            ((u64::from(hi) << 32) | u64::from(lo)) as i64
        };
        let e = |k: usize| w.m[k] as i32;
        let (tbit, ctrl) = (w.tbit as usize, w.ctrl as usize);
        for i in 0..amps.len() {
            if i & tbit == 0 && i & ctrl != ctrl {
                let j = i | tbit;
                let (a0, a1) = (amps[i], amps[j]);
                let row = |r: usize| -> Lane {
                    let (mr, mi, nr, ni) = (e(4 * r), e(4 * r + 1), e(4 * r + 2), e(4 * r + 3));
                    [
                        (fx(mr, a0[0]) - fx(mi, a0[1]) + fx(nr, a1[0]) - fx(ni, a1[1])) as i32,
                        (fx(mr, a0[1]) + fx(mi, a0[0]) + fx(nr, a1[1]) + fx(ni, a1[0])) as i32,
                    ]
                };
                (amps[i], amps[j]) = (row(0), row(1));
            }
        }
    }

    #[test]
    fn mutant_witnesses_exist() {
        let edges = lanes::PROBE_EDGES;
        let pairs: Vec<(i32, i32)> = edges.iter().flat_map(|&a| edges.iter().map(move |&b| (a, b))).collect();
        // The mirror without a mutant is the CPU's arithmetic, on the edges
        // and across the whole 32-bit range.
        let mut s = 17u64;
        let mut next = || {
            s = s.wrapping_add(0x9E37_79B9_7F4A_7C15);
            let mut z = s;
            z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
            z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
            z ^ (z >> 31)
        };
        let random: Vec<(i32, i32)> = (0..20_000).map(|_| (next() as i32, next() as i32)).collect();
        for &(a, b) in pairs.iter().chain(&random) {
            assert_eq!(probe_mirror(a as u32, b as u32, ""), probe_reference(a, b), "{a} × {b}");
        }
        // Each probe-detected mutant changes the probe's output on some pair
        // of edges. The counts are the ones computed, independently of this
        // crate, when the mutants were chosen.
        for (name, differing) in [("M1", 436), ("M2", 220), ("M3", 80), ("M4", 48), ("M7", 184)] {
            let m = MUTANTS.iter().find(|m| m.name == name).unwrap();
            assert_eq!(m.detector, Detector::Probe);
            let count = pairs.iter().filter(|&&(a, b)| probe_mirror(a as u32, b as u32, name) != probe_reference(a, b)).count();
            assert!(count >= 1, "{name}");
            assert_eq!(count, differing, "{name}");
        }
        // M5 changes the output of a random-v1 circuit, so the certificate's
        // digest moves.
        let mut changed = 0;
        for c in (Corpus::Random { seed: 7, cases: 200 }).circuits(Gateset::V1) {
            let mut amps = vec![[0i32; 2]; 1 << c.n_qubits];
            amps[0] = [crate::quantum::ONE as i32, 0];
            for g in &c.ops {
                apply_inverted_control(&mut amps, &lanes::gate_words(g, c.gateset));
            }
            if lanes::output(&amps) != lanes::reference_output(&c).unwrap() {
                changed += 1;
            }
        }
        assert!(changed >= 1);
        // M6 is witnessed by `z_on_the_most_negative_lane_is_flagged`: a
        // correct guard raises the flag there, and M6's never does.
        let z = lanes::gate_words(&Gate { base: BaseGate::Z, controls: vec![], target: 0, param: 0 }, Gateset::V2);
        assert_eq!(lanes::apply_words(&mut [[0, 0], [i32::MIN, 0]], &z), Some(false));
    }
}