wai-quantum 0.6.0

//! The fabric's matrix-extension member: the gate's fixed-point arithmetic in
//! the CPU's streaming vector mode (SME), where the matrix unit executes it.
//! Every instruction the kernel uses is base SME's: none needs SME2.
//!
//! **Why it is bit-exact.** The kernel is the same transcription of
//! [`lanes::apply_words`] as the CUDA kernel, in 64-bit vector lanes: each
//! operand is loaded sign-extended to 64 bits, each `fx(a, b) = (a·b + 2^29) >> 30`
//! is a 64-bit multiply, an add and an arithmetic shift, exact, and each row is
//! the sum of four. The host gathers the pairs a gate selects, the kernel forms
//! the four rows of eight pairs at a time (with 512-bit vectors), and the host
//! checks each row's range and keeps its low 32 bits, as
//! [`lanes::apply_words`] does.
//!
//! **Where it runs.** The kernel enters streaming mode (`smstart sm`) and
//! leaves it (`smstop sm`); its vector instructions exist only in that mode on
//! these processors, so a kernel that ran at all ran there. Discovery reads the
//! processor's feature flags (macOS `hw.optional.arm.FEAT_SME`; on Linux the
//! kernel's `AT_HWCAP2` bit 23, which an emulator supplies for its guest). Under an emulator, the runner declares it
//! (`WAI_QUANTUM_SME_EMULATOR`) and every certificate says so.
//!
//! The kernel's text, between the markers below, is the implementation id's
//! input; three mutants, compiled in, must each be caught.

use crate::quantum::{Amp, Circuit, Gateset, MAX_QUBITS, ONE, QuantumError, StateVector};
use crate::quantum_fabric::lanes::{self, GateWords, Lane};
use crate::quantum_fabric::plan::{self, Config, LaneRun, Program, Step};
use crate::quantum_fabric::{Certificate, Certification, Corpus, FabricClass, KernelEntry, Member, MemberError, Presence, Provenance, RunFuture, RunMeter, Runner, apply_kernel};

/// One probe case: [`lanes::mul_wide`] and [`lanes::fxmul_wide`] as
/// `(high, low)` words.
pub type ProbeOutput = ((u32, u32), (u32, u32));

/// Why the matrix extension is not a member, or a run has no state.
#[derive(Debug, PartialEq, Eq)]
#[non_exhaustive]
pub enum SmeError {
    Unavailable(String),
    Circuit(QuantumError),
    TooWide { n_qubits: u8, max: u8 },
    OutOfRange { gate: u32 },
    Internal(&'static str),
    Probe { a: i32, b: i32 },
}

impl std::fmt::Display for SmeError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            SmeError::Unavailable(why) => write!(f, "no matrix extension: {why}"),
            SmeError::Circuit(e) => write!(f, "{e}"),
            SmeError::TooWide { n_qubits, max } => write!(f, "{n_qubits} qubits; this member holds at most {max}"),
            SmeError::OutOfRange { gate } => write!(f, "the result of op {gate} leaves 32 bits"),
            SmeError::Internal(why) => write!(f, "host defect: {why}"),
            SmeError::Probe { a, b } => write!(f, "the kernel's arithmetic differs from the CPU's at ({a}, {b})"),
        }
    }
}

impl std::error::Error for SmeError {}

impl From<SmeError> for MemberError {
    fn from(e: SmeError) -> MemberError {
        match e {
            SmeError::TooWide { n_qubits, max } => MemberError::TooWide { n_qubits, max },
            SmeError::OutOfRange { gate } => MemberError::OutOfRange { gate },
            SmeError::Circuit(e) => MemberError::Circuit(e),
            other => MemberError::Other(other.to_string()),
        }
    }
}

/// The kernels a member runs: the conforming one, or a mutant.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum Variant {
    Conforming,
    /// The rounding constant is half what it should be.
    M1,
    /// The product is shifted by one bit too few.
    M2,
    /// Row 0's real part adds its last term instead of subtracting it.
    M3,
}

impl Variant {
    pub const MUTANTS: [Variant; 3] = [Variant::M1, Variant::M2, Variant::M3];
}

// kernel-begin
/// The kernels' text: the probe (each `a·b` and `fx(a, b)`) and the rows of a
/// gate. `$rnd` is the rounding constant, `$sh` the shift, `$s` the sign of
/// row 0's last real term.
macro_rules! rows_text {
    ($rnd:literal, $sh:literal, $s:literal) => {
        concat!(
            ".arch_extension sme\n",
            "smstart sm\n",
            "ptrue p0.d\n",
            "ldr x9, [{m}, #0]\nmov z16.d, x9\n",
            "ldr x9, [{m}, #8]\nmov z17.d, x9\n",
            "ldr x9, [{m}, #16]\nmov z18.d, x9\n",
            "ldr x9, [{m}, #24]\nmov z19.d, x9\n",
            "ldr x9, [{m}, #32]\nmov z20.d, x9\n",
            "ldr x9, [{m}, #40]\nmov z21.d, x9\n",
            "ldr x9, [{m}, #48]\nmov z22.d, x9\n",
            "ldr x9, [{m}, #56]\nmov z23.d, x9\n",
            "mov x9, #", $rnd, "\nmov z31.d, x9\n",
            "mov x10, #0\n",
            "2:\n",
            "whilelt p1.d, x10, {n}\n",
            "b.none 3f\n",
            "ld1sw {{z0.d}}, p1/z, [{a0r}, x10, lsl #2]\n",
            "ld1sw {{z1.d}}, p1/z, [{a0i}, x10, lsl #2]\n",
            "ld1sw {{z2.d}}, p1/z, [{a1r}, x10, lsl #2]\n",
            "ld1sw {{z3.d}}, p1/z, [{a1i}, x10, lsl #2]\n",
            // Row 0, real.
            "movprfx z4, z0\nmul z4.d, p0/m, z4.d, z16.d\nadd z4.d, z4.d, z31.d\nasr z4.d, z4.d, #", $sh, "\nmov z8.d, z4.d\n",
            "movprfx z4, z1\nmul z4.d, p0/m, z4.d, z17.d\nadd z4.d, z4.d, z31.d\nasr z4.d, z4.d, #", $sh, "\nsub z8.d, z8.d, z4.d\n",
            "movprfx z4, z2\nmul z4.d, p0/m, z4.d, z18.d\nadd z4.d, z4.d, z31.d\nasr z4.d, z4.d, #", $sh, "\nadd z8.d, z8.d, z4.d\n",
            "movprfx z4, z3\nmul z4.d, p0/m, z4.d, z19.d\nadd z4.d, z4.d, z31.d\nasr z4.d, z4.d, #", $sh, "\n", $s, " z8.d, z8.d, z4.d\n",
            // Row 0, imaginary.
            "movprfx z4, z1\nmul z4.d, p0/m, z4.d, z16.d\nadd z4.d, z4.d, z31.d\nasr z4.d, z4.d, #", $sh, "\nmov z9.d, z4.d\n",
            "movprfx z4, z0\nmul z4.d, p0/m, z4.d, z17.d\nadd z4.d, z4.d, z31.d\nasr z4.d, z4.d, #", $sh, "\nadd z9.d, z9.d, z4.d\n",
            "movprfx z4, z3\nmul z4.d, p0/m, z4.d, z18.d\nadd z4.d, z4.d, z31.d\nasr z4.d, z4.d, #", $sh, "\nadd z9.d, z9.d, z4.d\n",
            "movprfx z4, z2\nmul z4.d, p0/m, z4.d, z19.d\nadd z4.d, z4.d, z31.d\nasr z4.d, z4.d, #", $sh, "\nadd z9.d, z9.d, z4.d\n",
            // Row 1, real.
            "movprfx z4, z0\nmul z4.d, p0/m, z4.d, z20.d\nadd z4.d, z4.d, z31.d\nasr z4.d, z4.d, #", $sh, "\nmov z10.d, z4.d\n",
            "movprfx z4, z1\nmul z4.d, p0/m, z4.d, z21.d\nadd z4.d, z4.d, z31.d\nasr z4.d, z4.d, #", $sh, "\nsub z10.d, z10.d, z4.d\n",
            "movprfx z4, z2\nmul z4.d, p0/m, z4.d, z22.d\nadd z4.d, z4.d, z31.d\nasr z4.d, z4.d, #", $sh, "\nadd z10.d, z10.d, z4.d\n",
            "movprfx z4, z3\nmul z4.d, p0/m, z4.d, z23.d\nadd z4.d, z4.d, z31.d\nasr z4.d, z4.d, #", $sh, "\nsub z10.d, z10.d, z4.d\n",
            // Row 1, imaginary.
            "movprfx z4, z1\nmul z4.d, p0/m, z4.d, z20.d\nadd z4.d, z4.d, z31.d\nasr z4.d, z4.d, #", $sh, "\nmov z11.d, z4.d\n",
            "movprfx z4, z0\nmul z4.d, p0/m, z4.d, z21.d\nadd z4.d, z4.d, z31.d\nasr z4.d, z4.d, #", $sh, "\nadd z11.d, z11.d, z4.d\n",
            "movprfx z4, z3\nmul z4.d, p0/m, z4.d, z22.d\nadd z4.d, z4.d, z31.d\nasr z4.d, z4.d, #", $sh, "\nadd z11.d, z11.d, z4.d\n",
            "movprfx z4, z2\nmul z4.d, p0/m, z4.d, z23.d\nadd z4.d, z4.d, z31.d\nasr z4.d, z4.d, #", $sh, "\nadd z11.d, z11.d, z4.d\n",
            "st1d {{z8.d}}, p1, [{o0r}, x10, lsl #3]\n",
            "st1d {{z9.d}}, p1, [{o0i}, x10, lsl #3]\n",
            "st1d {{z10.d}}, p1, [{o1r}, x10, lsl #3]\n",
            "st1d {{z11.d}}, p1, [{o1i}, x10, lsl #3]\n",
            "incd x10\n",
            "b 2b\n",
            "3:\n",
            "smstop sm\n",
        )
    };
}

macro_rules! probe_text {
    ($rnd:literal, $sh:literal) => {
        concat!(
            ".arch_extension sme\n",
            "smstart sm\n",
            "ptrue p0.d\n",
            "mov x9, #", $rnd, "\nmov z31.d, x9\n",
            "mov x10, #0\n",
            "2:\n",
            "whilelt p1.d, x10, {n}\n",
            "b.none 3f\n",
            "ld1sw {{z0.d}}, p1/z, [{a}, x10, lsl #2]\n",
            "ld1sw {{z1.d}}, p1/z, [{b}, x10, lsl #2]\n",
            "movprfx z4, z0\nmul z4.d, p0/m, z4.d, z1.d\n",
            "add z5.d, z4.d, z31.d\nasr z5.d, z5.d, #", $sh, "\n",
            "st1d {{z4.d}}, p1, [{prod}, x10, lsl #3]\n",
            "st1d {{z5.d}}, p1, [{fx}, x10, lsl #3]\n",
            "incd x10\n",
            "b 2b\n",
            "3:\n",
            "smstop sm\n",
        )
    };
}
// kernel-end

/// One kernel, conforming or a mutant: the rows of `n` pairs.
macro_rules! rows_fn {
    ($name:ident, $rnd:literal, $sh:literal, $s:literal) => {
        #[cfg(target_arch = "aarch64")]
        #[allow(clippy::too_many_arguments)]
        /// # Safety
        ///
        /// The processor has SME; every slice holds `n` values.
        unsafe fn $name(m: &[i64; 8], n: usize, a0r: &[i32], a0i: &[i32], a1r: &[i32], a1i: &[i32], o0r: &mut [i64], o0i: &mut [i64], o1r: &mut [i64], o1i: &mut [i64]) {
            debug_assert!([a0r.len(), a0i.len(), a1r.len(), a1i.len(), o0r.len(), o0i.len(), o1r.len(), o1i.len()].iter().all(|&l| l >= n));
            // SAFETY: the caller's contract; streaming mode is entered and left
            // inside the block, and every vector and predicate register it
            // writes is declared clobbered (leaving streaming mode resets them).
            unsafe {
                std::arch::asm!(
                    rows_text!($rnd, $sh, $s),
                    m = in(reg) m.as_ptr(),
                    n = in(reg) n,
                    a0r = in(reg) a0r.as_ptr(),
                    a0i = in(reg) a0i.as_ptr(),
                    a1r = in(reg) a1r.as_ptr(),
                    a1i = in(reg) a1i.as_ptr(),
                    o0r = in(reg) o0r.as_mut_ptr(),
                    o0i = in(reg) o0i.as_mut_ptr(),
                    o1r = in(reg) o1r.as_mut_ptr(),
                    o1i = in(reg) o1i.as_mut_ptr(),
                    out("x9") _, out("x10") _, out("p0") _, out("p1") _,
                    out("v0") _, out("v1") _, out("v2") _, out("v3") _, out("v4") _, out("v5") _, out("v6") _, out("v7") _,
                    out("v8") _, out("v9") _, out("v10") _, out("v11") _, out("v12") _, out("v13") _, out("v14") _, out("v15") _,
                    out("v16") _, out("v17") _, out("v18") _, out("v19") _, out("v20") _, out("v21") _, out("v22") _, out("v23") _,
                    out("v24") _, out("v25") _, out("v26") _, out("v27") _, out("v28") _, out("v29") _, out("v30") _, out("v31") _,
                    options(nostack),
                );
            }
        }
    };
}

macro_rules! probe_fn {
    ($name:ident, $rnd:literal, $sh:literal) => {
        #[cfg(target_arch = "aarch64")]
        /// # Safety
        ///
        /// The processor has SME; every slice holds `n` values.
        unsafe fn $name(n: usize, a: &[i32], b: &[i32], prod: &mut [i64], fx: &mut [i64]) {
            debug_assert!(a.len() >= n && b.len() >= n && prod.len() >= n && fx.len() >= n);
            // SAFETY: as for the rows.
            unsafe {
                std::arch::asm!(
                    probe_text!($rnd, $sh),
                    n = in(reg) n,
                    a = in(reg) a.as_ptr(),
                    b = in(reg) b.as_ptr(),
                    prod = in(reg) prod.as_mut_ptr(),
                    fx = in(reg) fx.as_mut_ptr(),
                    out("x9") _, out("x10") _, out("p0") _, out("p1") _,
                    out("v0") _, out("v1") _, out("v2") _, out("v3") _, out("v4") _, out("v5") _, out("v6") _, out("v7") _,
                    out("v8") _, out("v9") _, out("v10") _, out("v11") _, out("v12") _, out("v13") _, out("v14") _, out("v15") _,
                    out("v16") _, out("v17") _, out("v18") _, out("v19") _, out("v20") _, out("v21") _, out("v22") _, out("v23") _,
                    out("v24") _, out("v25") _, out("v26") _, out("v27") _, out("v28") _, out("v29") _, out("v30") _, out("v31") _,
                    options(nostack),
                );
            }
        }
    };
}

rows_fn!(rows_conforming, "0x20000000", "30", "sub");
rows_fn!(rows_m1, "0x10000000", "30", "sub");
rows_fn!(rows_m2, "0x20000000", "29", "sub");
rows_fn!(rows_m3, "0x20000000", "30", "add");
probe_fn!(probe_conforming, "0x20000000", "30");
probe_fn!(probe_m1, "0x10000000", "30");
probe_fn!(probe_m2, "0x20000000", "29");

/// The text the conforming kernels are assembled from.
pub const KERNEL_TEXT: &str = concat!(rows_text!("0x20000000", "30", "sub"), probe_text!("0x20000000", "30"));

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

/// Version of the host layout: the gather of a gate's pairs into four
/// columns, the 64-bit row outputs, and the host's range check. Part of the
/// implementation id.
pub const HOST_LAYOUT: u32 = 1;

/// `"sme-lanes64/<16 hex>"` over a variant's kernel text and the layout.
pub fn implementation_id_of(v: Variant) -> String {
    let text = match v {
        Variant::Conforming => KERNEL_TEXT,
        Variant::M1 => concat!(rows_text!("0x10000000", "30", "sub"), probe_text!("0x10000000", "30")),
        Variant::M2 => concat!(rows_text!("0x20000000", "29", "sub"), probe_text!("0x20000000", "29")),
        Variant::M3 => concat!(rows_text!("0x20000000", "30", "add"), probe_text!("0x20000000", "30")),
    };
    let mut o = b"wai:quantum-fabric-sme\x01".to_vec();
    o.extend_from_slice(&(text.len() as u64).to_be_bytes());
    o.extend_from_slice(text.as_bytes());
    o.extend_from_slice(&HOST_LAYOUT.to_be_bytes());
    let h: String = blake3::hash(&o).as_bytes()[..8].iter().map(|b| format!("{b:02x}")).collect();
    format!("{IMPLEMENTATION}/{h}")
}

pub fn implementation_id() -> String {
    implementation_id_of(Variant::Conforming)
}

/// Whether this processor has SME, by its feature flags.
pub fn has_sme() -> Result<(), String> {
    #[cfg(not(target_arch = "aarch64"))]
    {
        Err("this processor is not aarch64".into())
    }
    #[cfg(all(target_arch = "aarch64", target_os = "macos"))]
    {
        let out = std::process::Command::new("sysctl").args(["-n", "hw.optional.arm.FEAT_SME"]).output().map_err(|e| format!("sysctl: {e}"))?;
        match String::from_utf8_lossy(&out.stdout).trim() {
            "1" => Ok(()),
            other => Err(format!("hw.optional.arm.FEAT_SME is {other:?}")),
        }
    }
    #[cfg(all(target_arch = "aarch64", target_os = "linux"))]
    {
        // The kernel's capability bits for this process: AT_HWCAP2 (26), whose
        // bit 23 is SME. An emulator supplies its own, where /proc/cpuinfo
        // would describe the host instead.
        const AT_HWCAP2: u64 = 26;
        const HWCAP2_SME: u64 = 1 << 23;
        let auxv = std::fs::read("/proc/self/auxv").map_err(|e| format!("/proc/self/auxv: {e}"))?;
        let hwcap2 = auxv.as_chunks::<16>().0.iter().find_map(|e| {
            let (k, v) = e.split_at(8);
            (u64::from_ne_bytes(k.try_into().expect("8 bytes")) == AT_HWCAP2).then(|| u64::from_ne_bytes(v.try_into().expect("8 bytes")))
        });
        match hwcap2 {
            Some(h) if h & HWCAP2_SME != 0 => Ok(()),
            Some(_) => Err("the kernel reports no SME (AT_HWCAP2 bit 23)".into()),
            None => Err("the kernel reports no AT_HWCAP2".into()),
        }
    }
    #[cfg(all(target_arch = "aarch64", not(any(target_os = "macos", target_os = "linux"))))]
    {
        Err("feature detection is written for macOS and Linux".into())
    }
}

/// What [`discover`] found.
#[derive(Debug)]
pub struct Discovery {
    pub found: Vec<SmeMember>,
    pub refused: Vec<(String, SmeError)>,
    pub unavailable: Option<String>,
}

/// The matrix extension, probed in this process, or why there is none.
pub fn discover() -> Discovery {
    let mut d = Discovery { found: Vec::new(), refused: Vec::new(), unavailable: None };
    if let Err(why) = has_sme() {
        d.unavailable = Some(why);
        return d;
    }
    match SmeMember::open(Variant::Conforming) {
        Ok(m) => d.found.push(m),
        Err(e) => d.refused.push((KEY.into(), e)),
    }
    d
}

/// The key a runner declares.
pub const KEY: &str = "cpu-matrix-sme";

/// The most qubits a run holds.
pub const MAX_SME_QUBITS: u8 = if 24 < MAX_QUBITS { 24 } else { MAX_QUBITS };

/// The matrix extension as a fabric member.
#[derive(Clone, Debug)]
pub struct SmeMember {
    variant: Variant,
    id: String,
    implementation: String,
    detail: String,
    provenance: Provenance,
    max_qubits: u8,
}

impl SmeMember {
    fn open(variant: Variant) -> Result<SmeMember, SmeError> {
        let emulator = std::env::var("WAI_QUANTUM_SME_EMULATOR").ok().filter(|s| !s.trim().is_empty());
        let provenance = emulator.as_ref().map_or(Provenance::Silicon, |e| Provenance::Emulator(e.trim().to_string()));
        let mut o = b"wai:quantum-fabric-sme-member\x01".to_vec();
        o.extend_from_slice(std::env::consts::ARCH.as_bytes());
        o.extend_from_slice(std::env::consts::OS.as_bytes());
        o.extend_from_slice(provenance.label().as_bytes());
        let id = format!("local/cpu-matrix-sme-{}", blake3::hash(&o).as_bytes()[..6].iter().map(|b| format!("{b:02x}")).collect::<String>());
        let member = SmeMember {
            variant,
            id,
            implementation: implementation_id_of(variant),
            detail: format!(
                "cpu-matrix; the processor's matrix extension in streaming mode (SME), 64-bit lanes; {}; up to {MAX_SME_QUBITS} qubits; unmetered",
                provenance.label()
            ),
            provenance,
            max_qubits: MAX_SME_QUBITS,
        };
        if variant == Variant::Conforming {
            let pairs = lanes::probe_pairs(4096, 0x5eed);
            let out = member.probe(&pairs)?;
            if let Some((a, b)) = lanes::first_mismatch(&pairs, &out) {
                return Err(SmeError::Probe { a, b });
            }
        }
        Ok(member)
    }

    /// The same processor running a mutant: for the mutation tests.
    #[doc(hidden)]
    pub fn with_variant(&self, v: Variant) -> SmeMember {
        SmeMember { variant: v, implementation: implementation_id_of(v), ..self.clone() }
    }

    #[doc(hidden)]
    pub fn with_max_qubits(&self, max_qubits: u8) -> SmeMember {
        SmeMember { max_qubits: max_qubits.min(self.max_qubits), ..self.clone() }
    }

    pub fn id(&self) -> &str {
        &self.id
    }

    pub fn key(&self) -> &str {
        KEY
    }

    pub fn class(&self) -> FabricClass {
        FabricClass::CpuMatrix
    }

    pub fn detail(&self) -> &str {
        &self.detail
    }

    pub fn implementation(&self) -> &str {
        &self.implementation
    }

    pub fn provenance(&self) -> &Provenance {
        &self.provenance
    }

    pub fn max_qubits(&self) -> u8 {
        self.max_qubits
    }

    pub fn config(&self) -> Config {
        Config::PER_GATE
    }

    /// The kernel's [`lanes::mul_wide`] and [`lanes::fxmul_wide`] of each pair.
    pub fn probe(&self, pairs: &[(i32, i32)]) -> Result<Vec<ProbeOutput>, SmeError> {
        #[cfg(target_arch = "aarch64")]
        {
            let n = pairs.len();
            let a: Vec<i32> = pairs.iter().map(|p| p.0).collect();
            let b: Vec<i32> = pairs.iter().map(|p| p.1).collect();
            let (mut prod, mut fx) = (vec![0i64; n], vec![0i64; n]);
            // SAFETY: discovery established SME; every slice holds n values.
            unsafe {
                match self.variant {
                    Variant::M1 => probe_m1(n, &a, &b, &mut prod, &mut fx),
                    Variant::M2 => probe_m2(n, &a, &b, &mut prod, &mut fx),
                    Variant::Conforming | Variant::M3 => probe_conforming(n, &a, &b, &mut prod, &mut fx),
                }
            }
            let split = |v: i64| ((v as u64 >> 32) as u32, v as u64 as u32);
            Ok(prod.iter().zip(&fx).map(|(&p, &f)| (split(p), split(f))).collect())
        }
        #[cfg(not(target_arch = "aarch64"))]
        {
            let _ = pairs;
            Err(SmeError::Unavailable("not aarch64".into()))
        }
    }

    /// The four rows of each pair, from the kernel.
    #[cfg(target_arch = "aarch64")]
    fn rows(&self, m: &[i64; 8], cols: &[Vec<i32>; 4]) -> [Vec<i64>; 4] {
        let n = cols[0].len();
        let mut o = [vec![0i64; n], vec![0i64; n], vec![0i64; n], vec![0i64; n]];
        let [o0r, o0i, o1r, o1i] = &mut o;
        // SAFETY: discovery established SME; every slice holds n values.
        unsafe {
            let f = match self.variant {
                Variant::Conforming => rows_conforming,
                Variant::M1 => rows_m1,
                Variant::M2 => rows_m2,
                Variant::M3 => rows_m3,
            };
            f(m, n, &cols[0], &cols[1], &cols[2], &cols[3], o0r, o0i, o1r, o1i);
        }
        o
    }

    /// Gates in order from `state`, as [`lanes::run_words`] runs them.
    pub fn run_lanes(&self, state: &[Lane], gates: &[GateWords]) -> Result<LaneRun, SmeError> {
        let len = state.len();
        if len < 2 || !len.is_power_of_two() {
            return Err(SmeError::Internal("a state that is not 2^n lanes, n at least 1"));
        }
        let n = len.trailing_zeros() as u8;
        if n > self.max_qubits {
            return Err(SmeError::TooWide { n_qubits: n, max: self.max_qubits });
        }
        let planned: Vec<(&GateWords, u32)> = gates.iter().zip(0u32..).collect();
        self.execute(state.to_vec(), &planned)
    }

    fn execute(&self, mut amps: Vec<Lane>, gates: &[(&GateWords, u32)]) -> Result<LaneRun, SmeError> {
        let len = amps.len();
        for (w, _) in gates {
            let (tbit, ctrl) = (w.tbit as usize, w.ctrl as usize);
            if tbit == 0 || !tbit.is_power_of_two() || tbit > len / 2 || ctrl & tbit != 0 || ctrl & !(len - 1) != 0 {
                return Err(SmeError::Internal("malformed gate words for this state"));
            }
        }
        #[cfg(not(target_arch = "aarch64"))]
        {
            let _ = (&mut amps, gates);
            return Err(SmeError::Unavailable("not aarch64".into()));
        }
        #[cfg(target_arch = "aarch64")]
        {
            let mut report: Option<u32> = None;
            for &(w, index) in gates {
                let m: [i64; 8] = w.m.map(|x| i64::from(x as i32));
                let (tbit, ctrl) = (w.tbit as usize, w.ctrl as usize);
                let mut at = Vec::new();
                let mut cols: [Vec<i32>; 4] = Default::default();
                for p in 0..len / 2 {
                    let low = p & (tbit - 1);
                    let i = ((p - low) << 1) | low;
                    if i & ctrl != ctrl {
                        continue;
                    }
                    at.push(i);
                    let (a0, a1) = (amps[i], amps[i | tbit]);
                    cols[0].push(a0[0]);
                    cols[1].push(a0[1]);
                    cols[2].push(a1[0]);
                    cols[3].push(a1[1]);
                }
                let [o0r, o0i, o1r, o1i] = self.rows(&m, &cols);
                for (k, &i) in at.iter().enumerate() {
                    let rows = [o0r[k], o0i[k], o1r[k], o1i[k]];
                    if rows.iter().any(|&v| i32::try_from(v).is_err()) {
                        report = Some(report.map_or(index, |r| r.min(index)));
                    }
                    let low = |v: i64| v as u64 as u32 as i32;
                    amps[i] = [low(rows[0]), low(rows[1])];
                    amps[i | tbit] = [low(rows[2]), low(rows[3])];
                }
            }
            Ok(LaneRun { amps, out_of_range: report })
        }
    }

    pub fn run_program(&self, p: &Program) -> Result<LaneRun, SmeError> {
        let n = p.n_qubits;
        if n == 0 {
            return Ok(LaneRun { amps: vec![[ONE as i32, 0]], out_of_range: None });
        }
        if n > self.max_qubits {
            return Err(SmeError::TooWide { n_qubits: n, max: self.max_qubits });
        }
        if p.start >= 1usize << n {
            return Err(SmeError::Internal("the start is outside the state"));
        }
        let mut gates = Vec::with_capacity(p.steps.len());
        for step in &p.steps {
            let Step::Gate { gate } = *step else { return Err(SmeError::Internal("a tile step; this member runs gate steps only")) };
            let g = p.gates.get(gate as usize).ok_or(SmeError::Internal("a step names a gate the program does not hold"))?;
            if !g.is_well_formed() {
                return Err(SmeError::Internal("malformed gate words for this state"));
            }
            gates.push((&g.words, g.index));
        }
        let mut amps = vec![[0i32, 0]; 1usize << n];
        amps[p.start] = [ONE as i32, 0];
        self.execute(amps, &gates)
    }

    pub fn simulate_from(&self, c: &Circuit, start: usize) -> Result<StateVector, SmeError> {
        let p = plan::compile_with(c, start, &self.config()).map_err(SmeError::Circuit)?;
        if p.n_qubits > self.max_qubits {
            return Err(SmeError::TooWide { n_qubits: p.n_qubits, max: self.max_qubits });
        }
        let run = self.run_program(&p)?;
        if let Some(gate) = run.out_of_range {
            return Err(SmeError::OutOfRange { gate });
        }
        Ok(StateVector { n_qubits: p.n_qubits, amps: run.amps.iter().map(|l| Amp { re: i64::from(l[0]), im: i64::from(l[1]) }).collect() })
    }

    pub fn simulate(&self, c: &Circuit) -> Result<StateVector, SmeError> {
        self.simulate_from(c, 0)
    }

    /// The certificate of [`apply_kernel`]`(gs)` on this member, with its
    /// provenance.
    pub fn certify(&self, gs: Gateset, corpus: Corpus) -> Result<Certificate, SmeError> {
        let mut cert = Certification::new();
        for c in corpus.circuits(gs) {
            let reference = lanes::reference_output(&c).map_err(SmeError::Circuit)?;
            let run = self.run_program(&plan::compile_with(&c, 0, &self.config()).map_err(SmeError::Circuit)?)?;
            if let Some(gate) = run.out_of_range {
                return Err(SmeError::OutOfRange { gate });
            }
            cert.add(&lanes::circuit_bytes(&c), &reference, &lanes::output(&run.amps));
        }
        Ok(cert.finish(apply_kernel(gs), &self.implementation, &self.id, &corpus.generator(gs)).with_provenance(self.provenance.clone()))
    }

    pub fn member(&self, corpus: Corpus) -> Result<Member, SmeError> {
        let mut kernels = Vec::new();
        for gs in Gateset::ALL {
            kernels.push(KernelEntry { kernel: apply_kernel(gs).into(), implementation: self.implementation.clone(), certificate: self.certify(gs, corpus)?, energy: None });
        }
        Ok(Member { id: self.id.clone(), class: FabricClass::CpuMatrix, presence: Presence::Detected, kernels, detail: self.detail.clone() })
    }
}

impl Runner for SmeMember {
    fn member_id(&self) -> String {
        self.id.clone()
    }

    fn run<'r>(&'r self, implementation: &'r str, c: &'r Circuit, start: usize, _meter: &'r mut dyn RunMeter) -> RunFuture<'r> {
        Box::pin(async move {
            if implementation != self.implementation {
                return Err(MemberError::Other(format!("member {} runs implementation {}, not {implementation:?}", self.id, self.implementation)));
            }
            Ok((self.simulate_from(c, start)?, 0, None))
        })
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn every_variant_has_its_own_implementation_id() {
        let ids: std::collections::BTreeSet<String> = [Variant::Conforming, Variant::M1, Variant::M2, Variant::M3].into_iter().map(implementation_id_of).collect();
        assert_eq!(ids.len(), 4);
        assert!(implementation_id().starts_with("sme-lanes64/"));
        assert!(KERNEL_TEXT.contains("smstart sm") && KERNEL_TEXT.contains("smstop sm"));
    }

    #[test]
    fn the_member_id_sorts_after_the_cpu_reference() {
        assert!("local/cpu-matrix-sme-000000000000" > "local/cpu-aarch64");
    }
}