wai-quantum 0.3.41

//! The fabric — `wai.quantum.fabric`.
//!
//! The algorithm is the product; the fabric is where it runs. A quantum
//! processor is one accelerator among others: a CPU, a GPU, a neural or tensor
//! processor, a dataflow processor, an FPGA, an analog Ising machine. The same
//! kernel may run on any member that implements it. This module is the
//! contract every member is held to.
//!
//! - **Members** ([`Member`]): what silicon, how sure we are that it is there
//!   ([`Presence`]), and the kernels it implements, each with the [`Parity`]
//!   it has earned.
//! - **Parity** against the reference: the CPU kernels of this crate are the
//!   oracle. A member's kernel is bit-exact, within a measured bound,
//!   statistical (a sampling device, measured by the fidelity of its counts
//!   against the reference distribution), or uncertified. An uncertified
//!   kernel is never placed, and a receipt that states one does not verify.
//! - **Certification** ([`certify`]): run the reference and the member on the
//!   same inputs and compare every output. The worst case over the corpus is
//!   the parity. A [`Certificate`] names the kernel, the implementation, the
//!   member and the corpus generator it was earned on, so whoever holds it can
//!   re-run that corpus and check the digest.
//! - **Placement** ([`place`]): of the detected members whose certified
//!   parity meets what the caller requires, the one that spends the fewest
//!   joules per unit of work.
//! - **Receipt** ([`FabricReceipt`]): a signed statement that a result was
//!   computed by a kernel on a member, binding the kernel's certificate, the
//!   joules, and how the joules were acquired.
//!
//! Numerics decide how much parity a fabric can earn. Most accelerators carry
//! no 64-bit float, and some no 64-bit integer. The gate kernel of the
//! fixed-point core ([`KERNEL_CIRCUIT_APPLY`]) needs neither: for the
//! amplitudes and gate entries of a valid circuit, each product fits in 64
//! bits and each result in 32. So a fabric with only 32-bit integer lanes can
//! reproduce it bit for bit. [`lanes`] is that kernel written with only the
//! operations such a fabric has, and its certificate against the native
//! simulator is bit-exact. The floating-point modules can earn bit-exactness
//! only on a fabric with 64-bit floats and the same order of operations;
//! elsewhere their parity is a measured bound.
//!
//! # Checked
//!
//! - **The lane multiply is the native one.** Over random operands across the
//!   whole amplitude range, and the edges (`±1`, one unit either side of zero,
//!   half the most negative 32-bit value), the 32-bit-lane multiply equals the
//!   native one in every bit, and its wide product equals the 64-bit product
//!   for every input including the most negative 32-bit value.
//! - **The lane simulator is the native one.** Random circuits of every gate
//!   the core supports, dyadic phases to `P(32)` and up to three controls, on
//!   up to ten qubits: every final amplitude bit-identical. The lane kernel
//!   runs the general 2×2 path for every gate, where the native one takes
//!   shortcuts; the shortcuts are exact by construction, and the certificate
//!   confirms it. The lane simulator refuses every circuit the native one
//!   refuses.
//! - **Parity is compared, not asserted.** Bit-identical outputs certify
//!   bit-exact; a one-unit difference certifies `Within` that bound; a NaN or
//!   an infinity on either side, or a length or scale mismatch, certifies
//!   nothing. Corpora that differ hash differently, however their outputs are
//!   split, and circuits that differ encode differently.
//! - **A sampling device is certified by its counts.** [`certify_sampling`]
//!   folds the classical fidelity of each case's counts against the
//!   reference weights, with the weights and counts in the corpus digest.
//! - **Placement serves only a certificate that is for this kernel, this
//!   implementation and this member,** earned on a corpus unless it is the CPU
//!   reference itself; it prefers fewer joules per operation, a known figure
//!   over none, and is deterministic on ties. A bound does not stand in for a
//!   fidelity.
//! - **Receipts verify, refuse tampering, refuse an uncertified kernel, and
//!   refuse a joule figure without its acquisition class.** Moving bytes
//!   between the named fields changes what is signed.
//!
//! # Honest boundaries
//!
//! - **Only detected members are placed, and the CPU is the only one
//!   detected.** On x86-64 and aarch64, detection asks the running CPU for
//!   its vector units. On other targets it reports the units the binary was
//!   compiled for among those it knows (WebAssembly SIMD, 32-bit Arm NEON,
//!   the RISC-V vector extension) and says so, with the standard library
//!   alone. Other members can be listed as reachable or declared; they are
//!   placed once a probe detects them and their own run of the corpus
//!   certifies them.
//! - **A certificate names the member it ran on.** Run on another platform,
//!   the same corpus gives the same parity and corpus digest, and a
//!   certificate that differs in its member.
//! - **Lanes on the CPU are a stand-in.** They prove the algorithm a 32-bit
//!   integer fabric would run, not that fabric's hardware.
//! - **Only the gate kernel is in lanes.** Sampling, probability weights and
//!   fidelities in the core use 128-bit sums and are not ported.

use crate::quantum::{Circuit, FRAC, MAX_QUBITS, ONE, QuantumError};
use crate::quantum_energy::{EnergyClass, check_label};
use crate::quantum_ops::content_hash;
use ed25519_dalek::{Signature, Signer, SigningKey, Verifier, VerifyingKey};
use serde_json::{Map, Value, json};

pub use crate::quantum_ops::CAP_QUANTUM_FABRIC;

/// The kernel that applies one controlled one-qubit gate to the fixed-point
/// state vector, the step every circuit of the core is made of.
pub const KERNEL_CIRCUIT_APPLY: &str = "wai.quantum.circuit/apply";

/// The implementation name of the crate's own kernel.
pub const REFERENCE: &str = "reference";

/// The corpus [`certify_lanes`] draws, by name and version.
pub const GENERATOR_RANDOM_CIRCUITS: &str = "wai.quantum.circuit/random-v1";

const DOMAIN_FABRIC: &[u8] = b"wai:quantum-fabric\x01";
const DOMAIN_FABRIC_ID: &[u8] = b"wai:quantum-fabric-id\x01";
const DOMAIN_CERT: &[u8] = b"wai:quantum-fabric-certificate\x01";
const DOMAIN_CORPUS: &[u8] = b"wai:quantum-fabric-corpus\x01";

/// A variable-length field: its length, then its bytes, so no two sequences
/// of fields encode alike.
fn put(o: &mut Vec<u8>, bytes: &[u8]) {
    o.extend_from_slice(&(bytes.len() as u64).to_be_bytes());
    o.extend_from_slice(bytes);
}

// ---------------------------------------------------------------------------
// Members
// ---------------------------------------------------------------------------

/// A class of compute silicon.
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum FabricClass {
    /// General-purpose cores and their vector units.
    Cpu,
    /// A matrix coprocessor beside the CPU cores.
    CpuMatrix,
    /// An integrated or discrete GPU.
    Gpu,
    /// A neural processor.
    Npu,
    /// A tensor processor.
    Tensor,
    /// A dataflow or wafer-scale processor.
    Dataflow,
    /// Reconfigurable logic.
    Fpga,
    /// A quantum processor.
    Qpu,
    /// An analog Ising machine: coupled oscillators, optical or electronic.
    AnalogIsing,
}

impl FabricClass {
    pub const ALL: [FabricClass; 9] =
        [FabricClass::Cpu, FabricClass::CpuMatrix, FabricClass::Gpu, FabricClass::Npu, FabricClass::Tensor, FabricClass::Dataflow, FabricClass::Fpga, FabricClass::Qpu, FabricClass::AnalogIsing];

    pub fn label(self) -> &'static str {
        match self {
            FabricClass::Cpu => "cpu",
            FabricClass::CpuMatrix => "cpu-matrix",
            FabricClass::Gpu => "gpu",
            FabricClass::Npu => "npu",
            FabricClass::Tensor => "tensor",
            FabricClass::Dataflow => "dataflow",
            FabricClass::Fpga => "fpga",
            FabricClass::Qpu => "qpu",
            FabricClass::AnalogIsing => "analog-ising",
        }
    }

    pub fn from_label(s: &str) -> Option<FabricClass> {
        FabricClass::ALL.into_iter().find(|c| c.label() == s)
    }
}

/// How sure we are that a member exists.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Presence {
    /// A probe in this process found it.
    Detected,
    /// Credentials or an endpoint for it exist; nothing was contacted.
    Reachable,
    /// Configuration says it exists; nothing here can confirm it.
    Declared,
}

impl Presence {
    pub fn label(self) -> &'static str {
        match self {
            Presence::Detected => "detected",
            Presence::Reachable => "reachable",
            Presence::Declared => "declared",
        }
    }

    pub fn from_label(s: &str) -> Option<Presence> {
        [Presence::Detected, Presence::Reachable, Presence::Declared].into_iter().find(|p| p.label() == s)
    }
}

/// A kernel's standing against the reference.
#[derive(Clone, Copy, Debug, PartialEq)]
pub enum Parity {
    /// Every output bit-identical to the reference.
    BitExact,
    /// Every output within `max_ulp` units in the last place of the reference
    /// (for fixed point, least significant bits), and within `max_abs` of it.
    Within { max_ulp: u64, max_abs: f64 },
    /// A sampling device: the classical fidelity of its counts against the
    /// reference distribution, over `shots`.
    Statistical { fidelity: f64, shots: u64 },
    /// Never certified. Never placed.
    Uncertified,
}

impl Parity {
    /// Whether this standing satisfies a caller who requires `required`.
    ///
    /// Bit-exact satisfies everything: a kernel that reproduces the reference
    /// reproduces its distribution too. A bound satisfies a looser bound, but
    /// not a fidelity: how far each output may stray says nothing, on its
    /// own, about how far a distribution built from them strays. A fidelity
    /// satisfies a fidelity no higher, over no more shots. Nothing satisfies
    /// through `Uncertified`, in either place.
    pub fn meets(&self, required: &Parity) -> bool {
        match (self, required) {
            (Parity::Uncertified, _) | (_, Parity::Uncertified) => false,
            (Parity::BitExact, _) => true,
            (Parity::Within { max_ulp, max_abs }, Parity::Within { max_ulp: u, max_abs: a }) => max_ulp <= u && max_abs <= a,
            (Parity::Statistical { fidelity, shots }, Parity::Statistical { fidelity: f, shots: s }) => fidelity >= f && shots >= s,
            _ => false,
        }
    }

    /// The weaker of two standings: what a corpus earns is its worst case.
    fn worst(self, other: Parity) -> Parity {
        match (self, other) {
            (Parity::Uncertified, _) | (_, Parity::Uncertified) => Parity::Uncertified,
            (Parity::BitExact, p) | (p, Parity::BitExact) => p,
            (Parity::Within { max_ulp: u1, max_abs: a1 }, Parity::Within { max_ulp: u2, max_abs: a2 }) => Parity::Within { max_ulp: u1.max(u2), max_abs: a1.max(a2) },
            (Parity::Statistical { fidelity: f1, shots: s1 }, Parity::Statistical { fidelity: f2, shots: s2 }) => Parity::Statistical { fidelity: f1.min(f2), shots: s1.min(s2) },
            // A bound and a sample answer different questions; their union
            // certifies neither.
            _ => Parity::Uncertified,
        }
    }

    /// The signed encoding: a tag, then fixed-width fields in big-endian order.
    fn write_signed(&self, o: &mut Vec<u8>) {
        match *self {
            Parity::Uncertified => o.push(0),
            Parity::BitExact => o.push(1),
            Parity::Within { max_ulp, max_abs } => {
                o.push(2);
                o.extend_from_slice(&max_ulp.to_be_bytes());
                o.extend_from_slice(&max_abs.to_bits().to_be_bytes());
            }
            Parity::Statistical { fidelity, shots } => {
                o.push(3);
                o.extend_from_slice(&fidelity.to_bits().to_be_bytes());
                o.extend_from_slice(&shots.to_be_bytes());
            }
        }
    }

    fn to_json(self) -> Value {
        match self {
            Parity::Uncertified => json!({"tier": "uncertified"}),
            Parity::BitExact => json!({"tier": "bit-exact"}),
            Parity::Within { max_ulp, max_abs } => json!({"tier": "within", "max_ulp": max_ulp, "max_abs_bits": format!("{:016x}", max_abs.to_bits())}),
            Parity::Statistical { fidelity, shots } => json!({"tier": "statistical", "fidelity_bits": format!("{:016x}", fidelity.to_bits()), "shots": shots}),
        }
    }

    fn from_json(v: &Value) -> Option<Parity> {
        let bits = |k: &str| v.get(k)?.as_str().filter(|s| s.len() == 16).and_then(|s| u64::from_str_radix(s, 16).ok()).map(f64::from_bits);
        Some(match v.get("tier")?.as_str()? {
            "uncertified" => Parity::Uncertified,
            "bit-exact" => Parity::BitExact,
            "within" => Parity::Within { max_ulp: v.get("max_ulp")?.as_u64()?, max_abs: bits("max_abs_bits")? },
            "statistical" => Parity::Statistical { fidelity: bits("fidelity_bits")?, shots: v.get("shots")?.as_u64()? },
            _ => return None,
        })
    }
}

/// One implementation of a kernel on a member, with its certificate and,
/// when known, its energy per operation.
#[derive(Clone, Debug, PartialEq)]
pub struct KernelEntry {
    pub kernel: String,
    /// Which implementation: [`REFERENCE`], or the name of the port.
    pub implementation: String,
    pub certificate: Certificate,
    /// Nanojoules per operation, and how that figure was acquired.
    pub energy: Option<(u64, EnergyClass)>,
}

/// One member of the fabric.
#[derive(Clone, Debug, PartialEq)]
pub struct Member {
    /// Stable identifier, `local/cpu-aarch64` for instance.
    pub id: String,
    pub class: FabricClass,
    pub presence: Presence,
    pub kernels: Vec<KernelEntry>,
    /// What detection found: architecture, vector units and how they were
    /// learned, threads.
    pub detail: String,
}

/// The vector units of the running CPU: asked of the CPU at run time where
/// the platform allows, otherwise those the binary was compiled for.
fn vector_units() -> (Vec<&'static str>, &'static str) {
    #[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
    {
        let mut v = Vec::new();
        if std::is_x86_feature_detected!("sse4.2") {
            v.push("sse4.2");
        }
        if std::is_x86_feature_detected!("avx2") {
            v.push("avx2");
        }
        if std::is_x86_feature_detected!("avx512f") {
            v.push("avx512f");
        }
        (v, "asked of the CPU")
    }
    #[cfg(target_arch = "aarch64")]
    {
        let mut v = Vec::new();
        if std::arch::is_aarch64_feature_detected!("neon") {
            v.push("neon");
        }
        if std::arch::is_aarch64_feature_detected!("sve") {
            v.push("sve");
        }
        (v, "asked of the CPU")
    }
    #[cfg(not(any(target_arch = "x86", target_arch = "x86_64", target_arch = "aarch64")))]
    {
        let mut v = Vec::new();
        if cfg!(target_feature = "simd128") {
            v.push("simd128");
        }
        if cfg!(all(target_arch = "arm", target_feature = "neon")) {
            v.push("neon");
        }
        if cfg!(all(any(target_arch = "riscv32", target_arch = "riscv64"), target_feature = "v")) {
            v.push("v");
        }
        (v, "compiled for, of simd128, neon, v")
    }
}

/// The member this process runs on: the CPU, offering the reference
/// implementation of [`KERNEL_CIRCUIT_APPLY`]. A port such as the 32-bit
/// lanes joins it once [`certify_lanes`] has certified it.
pub fn detect_local() -> Member {
    let arch = std::env::consts::ARCH;
    let (units, how) = vector_units();
    let threads = if cfg!(target_arch = "wasm32") { 1 } else { std::thread::available_parallelism().map_or(1, |n| n.get()) };
    let units = if units.is_empty() { "none found".to_string() } else { units.join(", ") };
    let id = format!("local/cpu-{arch}");
    Member {
        kernels: vec![KernelEntry { kernel: KERNEL_CIRCUIT_APPLY.into(), implementation: REFERENCE.into(), certificate: Certificate::reference(KERNEL_CIRCUIT_APPLY, &id), energy: None }],
        id,
        class: FabricClass::Cpu,
        presence: Presence::Detected,
        detail: format!("{arch}; vector units ({how}): {units}; threads: {threads}"),
    }
}

/// Whether `entry`'s certificate is one placement may rely on for `kernel`
/// on `member`: for this kernel, implementation and member, and earned on a
/// corpus, unless it is a CPU's own reference.
fn certified_for(member: &Member, entry: &KernelEntry, kernel: &str) -> bool {
    let c = &entry.certificate;
    let own = c.kernel == kernel && c.implementation == entry.implementation && c.member == member.id;
    let earned = c.cases > 0 || (entry.implementation == REFERENCE && member.class == FabricClass::Cpu);
    entry.kernel == kernel && own && earned
}

/// Of the detected members whose certificate for `kernel` is their own and
/// whose parity meets `required`, the implementation with the fewest
/// nanojoules per operation. One with a known figure comes before one
/// without; ties fall to the member id, then to the reference implementation,
/// then to the implementation's name, so placement is the same on every run.
pub fn place<'a>(members: &'a [Member], kernel: &str, required: &Parity) -> Option<(&'a Member, &'a KernelEntry)> {
    let key = |m: &Member, k: &KernelEntry| (k.energy.is_none(), k.energy.as_ref().map_or(0, |e| e.0), m.id.clone(), k.implementation != REFERENCE, k.implementation.clone());
    let mut best: Option<(&Member, &KernelEntry)> = None;
    for m in members.iter().filter(|m| m.presence == Presence::Detected) {
        for k in m.kernels.iter().filter(|k| certified_for(m, k, kernel) && k.certificate.parity.meets(required)) {
            if best.is_none_or(|(bm, bk)| key(m, k) < key(bm, bk)) {
                best = Some((m, k));
            }
        }
    }
    best
}

// ---------------------------------------------------------------------------
// Certification
// ---------------------------------------------------------------------------

/// One output of a kernel run, as the harness compares it.
#[derive(Clone, Debug, PartialEq)]
pub enum Output {
    /// Packed bits: any difference is a failure.
    Bits(Vec<u64>),
    /// Fixed point with `frac` fractional bits.
    Fixed { values: Vec<i64>, frac: u32 },
    Float(Vec<f64>),
}

impl Output {
    /// A tag, the value count, the scale for fixed point, then the values:
    /// one output's bytes never read as part of another's.
    fn bytes(&self) -> Vec<u8> {
        let mut o = Vec::new();
        match self {
            Output::Bits(v) => {
                o.push(1);
                o.extend_from_slice(&(v.len() as u64).to_le_bytes());
                v.iter().for_each(|x| o.extend_from_slice(&x.to_le_bytes()));
            }
            Output::Fixed { values, frac } => {
                o.push(2);
                o.extend_from_slice(&(values.len() as u64).to_le_bytes());
                o.extend_from_slice(&frac.to_le_bytes());
                values.iter().for_each(|x| o.extend_from_slice(&x.to_le_bytes()));
            }
            Output::Float(v) => {
                o.push(3);
                o.extend_from_slice(&(v.len() as u64).to_le_bytes());
                v.iter().for_each(|x| o.extend_from_slice(&x.to_bits().to_le_bytes()));
            }
        }
        o
    }
}

/// A float's place on the line of all floats: neighbours differ by one.
fn ordered(x: f64) -> i128 {
    let b = x.to_bits() as i64;
    if b < 0 { i64::MIN as i128 - b as i128 } else { b as i128 }
}

/// The parity a member's output earns against the reference's on one input.
pub fn compare(reference: &Output, member: &Output) -> Parity {
    match (reference, member) {
        (Output::Bits(r), Output::Bits(m)) => {
            if r == m { Parity::BitExact } else { Parity::Uncertified }
        }
        (Output::Fixed { values: r, frac: fr }, Output::Fixed { values: m, frac: fm }) => {
            if fr != fm || r.len() != m.len() || *fr >= 64 {
                return Parity::Uncertified;
            }
            if r == m {
                return Parity::BitExact;
            }
            let ulp = r.iter().zip(m).map(|(a, b)| (*a as i128 - *b as i128).unsigned_abs()).max().unwrap_or(0);
            let Ok(ulp) = u64::try_from(ulp) else { return Parity::Uncertified };
            Parity::Within { max_ulp: ulp, max_abs: ulp as f64 * 2f64.powi(-(*fr as i32)) }
        }
        (Output::Float(r), Output::Float(m)) => {
            if r.len() != m.len() || r.iter().chain(m).any(|x| !x.is_finite()) {
                return Parity::Uncertified;
            }
            if r.iter().zip(m).all(|(a, b)| a.to_bits() == b.to_bits()) {
                return Parity::BitExact;
            }
            let (mut ulp, mut abs) = (0u128, 0f64);
            for (a, b) in r.iter().zip(m) {
                ulp = ulp.max((ordered(*a) - ordered(*b)).unsigned_abs());
                abs = abs.max((a - b).abs());
            }
            match u64::try_from(ulp) {
                Ok(u) => Parity::Within { max_ulp: u, max_abs: abs },
                Err(_) => Parity::Uncertified,
            }
        }
        _ => Parity::Uncertified,
    }
}

/// The classical fidelity `(Σ √(p_i q_i))²` of a sampling device's counts,
/// `q = counts / shots`, against the reference weights `p`, normalised to a
/// distribution here. Refuses weights that are negative, not finite or sum to
/// zero, mismatched lengths, no shots, and a shot total past 64 bits.
pub fn statistical(reference: &[f64], counts: &[u64]) -> Parity {
    let total: f64 = reference.iter().sum();
    let shots = counts.iter().try_fold(0u64, |acc, &c| acc.checked_add(c));
    let Some(shots) = shots else { return Parity::Uncertified };
    if reference.len() != counts.len() || shots == 0 || !total.is_finite() || total <= 0.0 || reference.iter().any(|p| !p.is_finite() || *p < 0.0) {
        return Parity::Uncertified;
    }
    let overlap: f64 = reference.iter().zip(counts).map(|(p, &c)| (p / total * c as f64 / shots as f64).sqrt()).sum();
    // At most one by Cauchy–Schwarz; rounding may not push it past.
    Parity::Statistical { fidelity: (overlap * overlap).min(1.0), shots }
}

/// What a kernel implementation on a member has earned against the
/// reference, and the corpus it earned it on.
#[derive(Clone, Debug, PartialEq)]
pub struct Certificate {
    pub kernel: String,
    pub implementation: String,
    /// The member id the corpus ran on.
    pub member: String,
    /// The corpus generator and its parameters, enough to draw the corpus
    /// again: `"<generator> seed=<seed> cases=<n>"`, or `"definition"` for
    /// the reference.
    pub generator: String,
    pub parity: Parity,
    /// Cases compared; zero for the reference itself.
    pub cases: u64,
    /// BLAKE3 over each case's input and both outputs, each length-prefixed,
    /// in order; zero for the reference.
    pub corpus: [u8; 32],
}

impl Certificate {
    /// A CPU reference's own standing: bit-exact by definition, on no corpus.
    pub fn reference(kernel: &str, member: &str) -> Certificate {
        Certificate { kernel: kernel.into(), implementation: REFERENCE.into(), member: member.into(), generator: "definition".into(), parity: Parity::BitExact, cases: 0, corpus: [0; 32] }
    }

    /// The content hash a receipt binds.
    pub fn hash(&self) -> [u8; 32] {
        let mut o = DOMAIN_CERT.to_vec();
        for s in [&self.kernel, &self.implementation, &self.member, &self.generator] {
            put(&mut o, s.as_bytes());
        }
        self.parity.write_signed(&mut o);
        o.extend_from_slice(&self.cases.to_be_bytes());
        o.extend_from_slice(&self.corpus);
        content_hash(&o)
    }
}

/// Certify `implementation` of `kernel` on `member`: each case is an input
/// and the reference's and the member's outputs on it. The parity is the
/// worst case's, and an empty corpus certifies nothing.
pub fn certify(kernel: &str, implementation: &str, member: &str, generator: &str, cases: impl IntoIterator<Item = (Vec<u8>, Output, Output)>) -> Certificate {
    let mut h = blake3::Hasher::new();
    h.update(DOMAIN_CORPUS);
    let mut parity: Option<Parity> = None;
    let mut n = 0u64;
    for (input, reference, member) in cases {
        for bytes in [input, reference.bytes(), member.bytes()] {
            h.update(&(bytes.len() as u64).to_le_bytes());
            h.update(&bytes);
        }
        let p = compare(&reference, &member);
        parity = Some(parity.map_or(p, |q| q.worst(p)));
        n += 1;
    }
    Certificate {
        kernel: kernel.into(),
        implementation: implementation.into(),
        member: member.into(),
        generator: generator.into(),
        parity: parity.unwrap_or(Parity::Uncertified),
        cases: n,
        corpus: *h.finalize().as_bytes(),
    }
}

/// Certify the 32-bit-lane port of [`KERNEL_CIRCUIT_APPLY`], as
/// implementation `"lanes32"` on `member`, against the native simulator on
/// `circuits` random circuits drawn from `seed`.
pub fn certify_lanes(member: &str, circuits: usize, seed: u64) -> Certificate {
    let mut s = seed;
    let cases = (0..circuits).map(move |_| {
        let c = lanes::random_circuit(&mut s);
        let native = c.simulate_from(0).expect("random circuits are valid");
        let lane = lanes::simulate(&c).expect("random circuits are valid");
        let reference = Output::Fixed { values: native.amps.iter().flat_map(|a| [a.re, a.im]).collect(), frac: FRAC };
        let port = Output::Fixed { values: lane.iter().flat_map(|a| [a[0] as i64, a[1] as i64]).collect(), frac: FRAC };
        (lanes::circuit_bytes(&c), reference, port)
    });
    certify(KERNEL_CIRCUIT_APPLY, "lanes32", member, &format!("{GENERATOR_RANDOM_CIRCUITS} seed={seed} cases={circuits}"), cases)
}

/// Certify a sampling implementation of `kernel` on `member`: each case is an
/// input, the reference's weights over the outcomes, and the counts the
/// device returned. Each case earns the classical fidelity of its counts
/// ([`statistical`]); the certificate holds the worst, and the corpus digest
/// covers the weights and counts.
pub fn certify_sampling(kernel: &str, implementation: &str, member: &str, generator: &str, cases: impl IntoIterator<Item = (Vec<u8>, Vec<f64>, Vec<u64>)>) -> Certificate {
    let mut h = blake3::Hasher::new();
    h.update(DOMAIN_CORPUS);
    let mut parity: Option<Parity> = None;
    let mut n = 0u64;
    for (input, weights, counts) in cases {
        for bytes in [input, Output::Float(weights.clone()).bytes(), Output::Bits(counts.clone()).bytes()] {
            h.update(&(bytes.len() as u64).to_le_bytes());
            h.update(&bytes);
        }
        let p = statistical(&weights, &counts);
        parity = Some(parity.map_or(p, |q| q.worst(p)));
        n += 1;
    }
    Certificate {
        kernel: kernel.into(),
        implementation: implementation.into(),
        member: member.into(),
        generator: generator.into(),
        parity: parity.unwrap_or(Parity::Uncertified),
        cases: n,
        corpus: *h.finalize().as_bytes(),
    }
}

// ---------------------------------------------------------------------------
// The receipt
// ---------------------------------------------------------------------------

/// A signed statement that a result was computed by a kernel on a member.
/// It binds the result's hash, which can be the hash of another receipt, so
/// it accompanies the receipts of this crate without changing them.
#[derive(Clone, Debug, PartialEq)]
pub struct FabricReceipt {
    pub result_hash: [u8; 32],
    pub kernel: String,
    pub implementation: String,
    pub member_id: String,
    pub class: FabricClass,
    pub presence: Presence,
    pub parity: Parity,
    pub certificate_hash: [u8; 32],
    pub joules_micro: u64,
    /// How the joules were acquired; required for a non-zero figure and
    /// absent for zero (unmetered).
    pub energy_class: Option<EnergyClass>,
    pub signer_pubkey: [u8; 32],
    pub signer_id: String,
    pub sig: [u8; 64],
}

impl FabricReceipt {
    fn signing_payload(&self) -> Vec<u8> {
        let mut o = DOMAIN_FABRIC.to_vec();
        o.extend_from_slice(&self.result_hash);
        for s in [&self.kernel, &self.implementation, &self.member_id] {
            put(&mut o, s.as_bytes());
        }
        put(&mut o, self.class.label().as_bytes());
        put(&mut o, self.presence.label().as_bytes());
        self.parity.write_signed(&mut o);
        o.extend_from_slice(&self.certificate_hash);
        o.extend_from_slice(&self.joules_micro.to_be_bytes());
        // The class as energy-measurement §2.7 encodes it: tag 0 for an
        // unmetered zero, otherwise the class's own tag and evidence.
        match &self.energy_class {
            None => o.push(0),
            Some(c) => c.write_signed(&mut o),
        }
        o.extend_from_slice(&self.signer_pubkey);
        put(&mut o, self.signer_id.as_bytes());
        o
    }

    /// Seal a result computed by `entry` on `member`, with `joules_micro`
    /// acquired as `energy_class` (none for an unmetered zero).
    pub fn seal(signer: &SigningKey, signer_id: impl Into<String>, result_hash: [u8; 32], member: &Member, entry: &KernelEntry, joules_micro: u64, energy_class: Option<EnergyClass>) -> FabricReceipt {
        let mut r = FabricReceipt {
            result_hash,
            kernel: entry.kernel.clone(),
            implementation: entry.implementation.clone(),
            member_id: member.id.clone(),
            class: member.class,
            presence: member.presence,
            parity: entry.certificate.parity,
            certificate_hash: entry.certificate.hash(),
            joules_micro,
            energy_class,
            signer_pubkey: signer.verifying_key().to_bytes(),
            signer_id: signer_id.into(),
            sig: [0; 64],
        };
        r.sig = signer.sign(&r.signing_payload()).to_bytes();
        r
    }

    /// The signature holds; the stated parity is not `Uncertified`; and the
    /// joules are labelled as the crate's energy rules require: a non-zero
    /// figure with a valid acquisition class, a zero figure with none. A
    /// verifier who holds the certificate checks it with
    /// [`Self::certificate_matches`].
    pub fn verify(&self) -> bool {
        if self.parity == Parity::Uncertified {
            return false;
        }
        let labelled = match &self.energy_class {
            None => self.joules_micro == 0,
            Some(c) => check_label(self.joules_micro, c).is_ok(),
        };
        if !labelled {
            return false;
        }
        let Ok(k) = VerifyingKey::from_bytes(&self.signer_pubkey) else {
            return false;
        };
        k.verify(&self.signing_payload(), &Signature::from_bytes(&self.sig)).is_ok()
    }

    /// Whether `certificate` is the one this receipt binds, and is for the
    /// kernel, implementation and member the receipt names.
    pub fn certificate_matches(&self, certificate: &Certificate) -> bool {
        certificate.hash() == self.certificate_hash
            && certificate.parity == self.parity
            && certificate.kernel == self.kernel
            && certificate.implementation == self.implementation
            && certificate.member == self.member_id
    }

    pub fn receipt_hash(&self) -> [u8; 32] {
        let mut h = blake3::Hasher::new();
        h.update(DOMAIN_FABRIC_ID);
        h.update(&self.signing_payload());
        h.update(&self.sig);
        *h.finalize().as_bytes()
    }

    pub fn to_json(&self) -> String {
        let hex = |b: &[u8]| b.iter().map(|x| format!("{x:02x}")).collect::<String>();
        let mut m = Map::new();
        m.insert("capability".into(), json!(CAP_QUANTUM_FABRIC));
        m.insert("result_hash".into(), json!(hex(&self.result_hash)));
        m.insert("kernel".into(), json!(self.kernel));
        m.insert("implementation".into(), json!(self.implementation));
        m.insert("member_id".into(), json!(self.member_id));
        m.insert("class".into(), json!(self.class.label()));
        m.insert("presence".into(), json!(self.presence.label()));
        m.insert("parity".into(), self.parity.to_json());
        m.insert("certificate_hash".into(), json!(hex(&self.certificate_hash)));
        m.insert("joules_micro".into(), json!(self.joules_micro));
        if let Some(c) = &self.energy_class {
            let mut e = Map::new();
            for (k, v) in c.json_fields() {
                e.insert(k.into(), v);
            }
            m.insert("energy_class".into(), Value::Object(e));
        }
        m.insert("signer_pubkey".into(), json!(hex(&self.signer_pubkey)));
        m.insert("signer_id".into(), json!(self.signer_id));
        m.insert("sig".into(), json!(hex(&self.sig)));
        Value::Object(m).to_string()
    }

    pub fn from_json(s: &str) -> Option<FabricReceipt> {
        let v: Value = serde_json::from_str(s).ok()?;
        if v.get("capability")?.as_str()? != CAP_QUANTUM_FABRIC {
            return None;
        }
        fn unhex<const N: usize>(s: &str) -> Option<[u8; N]> {
            if s.len() != 2 * N || !s.bytes().all(|b| b.is_ascii_hexdigit()) {
                return None;
            }
            let mut out = [0u8; N];
            for (i, c) in s.as_bytes().chunks(2).enumerate() {
                out[i] = u8::from_str_radix(std::str::from_utf8(c).ok()?, 16).ok()?;
            }
            Some(out)
        }
        let st = |k: &str| v.get(k).and_then(Value::as_str);
        let energy_class = match v.get("energy_class") {
            None => None,
            Some(e) => Some(EnergyClass::from_json_object(e.as_object()?).ok()??),
        };
        Some(FabricReceipt {
            result_hash: unhex(st("result_hash")?)?,
            kernel: st("kernel")?.into(),
            implementation: st("implementation")?.into(),
            member_id: st("member_id")?.into(),
            class: FabricClass::from_label(st("class")?)?,
            presence: Presence::from_label(st("presence")?)?,
            parity: Parity::from_json(v.get("parity")?)?,
            certificate_hash: unhex(st("certificate_hash")?)?,
            joules_micro: v.get("joules_micro")?.as_u64()?,
            energy_class,
            signer_pubkey: unhex(st("signer_pubkey")?)?,
            signer_id: st("signer_id")?.into(),
            sig: unhex(st("sig")?)?,
        })
    }
}

// ---------------------------------------------------------------------------
// The gate kernel in 32-bit lanes
// ---------------------------------------------------------------------------

/// The core's gate kernel in 32-bit lanes, using only what a fabric with
/// 32-bit integer lanes has: wrapping 32-bit add, subtract and multiply,
/// shifts and comparisons. A shader or a logic design that runs these steps
/// gets the native simulator's bits. The gate entries are prepared by the
/// host from the core's pinned table and handed to the lanes as 32-bit
/// values.
pub mod lanes {
    use super::{Circuit, MAX_QUBITS, QuantumError};
    use crate::quantum::{BaseGate, Gate, ONE};

    /// The 64-bit two's-complement product of two 32-bit values, as
    /// `(high, low)` words, built from 16-bit halves so that no partial
    /// product needs more than 32 bits.
    pub fn mul_wide(a: i32, b: i32) -> (u32, u32) {
        let negative = (a < 0) != (b < 0);
        let (x, y) = (a.unsigned_abs(), b.unsigned_abs());
        let (x1, x0) = (x >> 16, x & 0xffff);
        let (y1, y0) = (y >> 16, y & 0xffff);
        let p00 = x0.wrapping_mul(y0);
        let p01 = x0.wrapping_mul(y1);
        let p10 = x1.wrapping_mul(y0);
        let p11 = x1.wrapping_mul(y1);
        let mid = p01.wrapping_add(p10);
        let mid_carry = u32::from(mid < p01);
        let lo = p00.wrapping_add(mid << 16);
        let lo_carry = u32::from(lo < p00);
        let hi = p11.wrapping_add(mid >> 16).wrapping_add(mid_carry << 16).wrapping_add(lo_carry);
        if negative {
            let lo_n = (!lo).wrapping_add(1);
            let hi_n = (!hi).wrapping_add(u32::from(lo_n == 0));
            (hi_n, lo_n)
        } else {
            (hi, lo)
        }
    }

    /// The core's fixed-point multiply, `(a·b + 2^29) >> 30`, in lanes.
    /// Exact whenever the true result fits in 32 bits, which is exactly when
    /// `−2^61 − 2^29 ≤ a·b < 2^61 − 2^29`. The amplitudes and gate entries of
    /// a valid circuit are each at most `2^30` in size, so their products are
    /// at most `2^60` and always inside.
    pub fn fxmul(a: i32, b: i32) -> i32 {
        let (hi, lo) = mul_wide(a, b);
        let lo2 = lo.wrapping_add(1 << 29);
        let hi2 = hi.wrapping_add(u32::from(lo2 < lo));
        ((lo2 >> 30) | (hi2 << 2)) as i32
    }

    /// A complex amplitude: `[re, im]`.
    pub type Lane = [i32; 2];

    fn cmul(a: Lane, b: Lane) -> Lane {
        [fxmul(a[0], b[0]).wrapping_sub(fxmul(a[1], b[1])), fxmul(a[0], b[1]).wrapping_add(fxmul(a[1], b[0]))]
    }

    fn cadd(a: Lane, b: Lane) -> Lane {
        [a[0].wrapping_add(b[0]), a[1].wrapping_add(b[1])]
    }

    /// The gate's matrix in lanes. Only for a validated gate.
    fn matrix(g: &Gate) -> [[Lane; 2]; 2] {
        let m = g.base.matrix(g.param);
        let l = |a: crate::quantum::Amp| [a.re as i32, a.im as i32];
        [[l(m[0][0]), l(m[0][1])], [l(m[1][0]), l(m[1][1])]]
    }

    /// One controlled one-qubit gate, the general 2×2 path for every pair:
    /// the step a shader runs once per pair, in parallel. `target` must be a
    /// qubit of the state and outside `ctrl_mask`.
    pub fn apply(amps: &mut [Lane], target: u8, ctrl_mask: usize, m: [[Lane; 2]; 2]) {
        let tbit = 1usize << target;
        for i in 0..amps.len() {
            if i & tbit == 0 && i & ctrl_mask == ctrl_mask {
                let j = i | tbit;
                let (a0, a1) = (amps[i], amps[j]);
                amps[i] = cadd(cmul(m[0][0], a0), cmul(m[0][1], a1));
                amps[j] = cadd(cmul(m[1][0], a0), cmul(m[1][1], a1));
            }
        }
    }

    /// A circuit from `|0…0⟩`, gate by gate, in lanes. Refuses what the
    /// native simulator refuses, with the same error.
    pub fn simulate(c: &Circuit) -> Result<Vec<Lane>, QuantumError> {
        c.validate()?;
        if c.n_qubits > MAX_QUBITS {
            return Err(QuantumError::TooManyQubits(c.n_qubits));
        }
        let mut amps = vec![[0i32; 2]; 1usize << c.n_qubits];
        amps[0] = [ONE as i32, 0];
        for g in &c.ops {
            let mask = g.controls.iter().fold(0usize, |acc, &q| acc | (1usize << q));
            apply(&mut amps, g.target, mask, matrix(g));
        }
        Ok(amps)
    }

    fn next(s: &mut u64) -> u64 {
        *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)
    }

    /// A random circuit of the core's gates: two to ten qubits, up to three
    /// controls, dyadic phases up to `P(32)`.
    pub fn random_circuit(s: &mut u64) -> Circuit {
        let n = 2 + (next(s) % 9) as u8;
        let mut c = Circuit::new(n);
        let bases = [BaseGate::I, BaseGate::X, BaseGate::Y, BaseGate::Z, BaseGate::H, BaseGate::S, BaseGate::Sdg, BaseGate::T, BaseGate::Tdg, BaseGate::P];
        for _ in 0..(10 + next(s) % 50) {
            let base = bases[(next(s) % bases.len() as u64) as usize];
            let target = (next(s) % n as u64) as u8;
            let mut controls = Vec::new();
            for _ in 0..(next(s) % 4) {
                let q = (next(s) % n as u64) as u8;
                if q != target && !controls.contains(&q) {
                    controls.push(q);
                }
            }
            let param = if base == BaseGate::P { 1 + (next(s) % 32) as u16 } else { 0 };
            c.ops.push(Gate { base, controls, target, param });
        }
        c
    }

    /// A circuit's bytes for the certificate's corpus: every count
    /// length-prefixed, so different circuits never encode alike.
    pub fn circuit_bytes(c: &Circuit) -> Vec<u8> {
        let mut o = vec![c.n_qubits];
        for g in &c.ops {
            o.push(g.base.opcode());
            o.push(g.target);
            o.extend_from_slice(&g.param.to_le_bytes());
            o.extend_from_slice(&(g.controls.len() as u64).to_le_bytes());
            o.extend_from_slice(&g.controls);
        }
        o
    }
}

/// The fixed-point one is a 32-bit lane value.
const _: () = assert!(ONE <= i32::MAX as i64);

#[cfg(test)]
mod tests {
    use super::*;
    use crate::quantum::{BaseGate, Gate, fxmul};
    use crate::quantum_energy::{CounterFiltering, Uncertainty};

    fn next(s: &mut u64) -> u64 {
        *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)
    }

    #[test]
    fn the_lane_multiply_is_the_native_one() {
        let one = ONE as i32;
        let edges = [0, 1, -1, 2, -2, one, -one, one - 1, -(one - 1), one / 2, -(one / 2), i32::MIN / 2, 46341, -46341];
        let mut cases: Vec<(i32, i32)> = edges.iter().flat_map(|&a| edges.iter().map(move |&b| (a, b))).collect();
        let mut s = 11u64;
        for _ in 0..200_000 {
            let a = (next(&mut s) % (2 * ONE as u64 + 1)) as i64 - ONE;
            let b = (next(&mut s) % (2 * ONE as u64 + 1)) as i64 - ONE;
            cases.push((a as i32, b as i32));
        }
        for (a, b) in cases {
            assert_eq!(lanes::fxmul(a, b) as i64, fxmul(a as i64, b as i64), "{a} × {b}");
        }
        // The wide product is the 64-bit product for every 32-bit input,
        // the most negative included.
        let wide = [0, 1, -1, i32::MAX, i32::MIN, i32::MIN + 1, one, -one, 65535, -65536];
        let mut all: Vec<(i32, i32)> = wide.iter().flat_map(|&a| wide.iter().map(move |&b| (a, b))).collect();
        for _ in 0..200_000 {
            all.push((next(&mut s) as i32, next(&mut s) as i32));
        }
        for (a, b) in all {
            let (hi, lo) = lanes::mul_wide(a, b);
            assert_eq!(((hi as u64) << 32 | lo as u64) as i64, a as i64 * b as i64, "{a} × {b} wide");
        }
        // The stated range is exact: just inside it the lanes agree, at its
        // edge the native result needs 33 bits and the lanes cannot hold it.
        let (a, b) = (1 << 30, i32::MAX); // a·b = 2^61 − 2^30
        assert_eq!(lanes::fxmul(a, b) as i64, fxmul(a as i64, b as i64));
        let (a, b) = (2_147_450_880, 1_073_758_208); // a·b = 2^61 − 2^29
        assert_eq!(a as i64 * b as i64, (1i64 << 61) - (1 << 29));
        assert_ne!(lanes::fxmul(a, b) as i64, fxmul(a as i64, b as i64));
    }

    #[test]
    fn the_lane_simulator_is_the_native_one() {
        let cert = certify_lanes("local/test", 300, 7);
        assert_eq!(cert.parity, Parity::BitExact, "{cert:?}");
        assert_eq!(cert.cases, 300);
        assert_eq!(cert.generator, format!("{GENERATOR_RANDOM_CIRCUITS} seed=7 cases=300"));
        // The same corpus, the same certificate; another seed, another corpus.
        assert_eq!(certify_lanes("local/test", 300, 7).hash(), cert.hash());
        assert_ne!(certify_lanes("local/test", 300, 8).corpus, cert.corpus);
        // The corpus is not trivial: some final states spread over many
        // amplitudes, with phases.
        let mut s = 7u64;
        let spread = (0..300).filter(|_| lanes::simulate(&lanes::random_circuit(&mut s)).unwrap().iter().filter(|a| a[0] != 0 || a[1] != 0).count() >= 4).count();
        assert!(spread >= 100, "{spread} of 300 circuits spread over four amplitudes or more");
    }

    #[test]
    fn the_lane_simulator_refuses_what_the_native_one_refuses() {
        let gate = |base, controls: Vec<u8>, target, param| Gate { base, controls, target, param };
        let bad = [
            (1, vec![gate(BaseGate::H, vec![], 0, 0), gate(BaseGate::P, vec![], 0, 0)]),
            (1, vec![gate(BaseGate::P, vec![], 0, 33)]),
            (1, vec![gate(BaseGate::X, vec![], 3, 0)]),
            (2, vec![gate(BaseGate::X, vec![0], 0, 0)]),
            (2, vec![gate(BaseGate::X, vec![5], 1, 0)]),
        ];
        for (n, ops) in bad {
            let c = Circuit { n_qubits: n, ops };
            let native = c.simulate_from(0).unwrap_err();
            assert_eq!(lanes::simulate(&c).unwrap_err(), native);
        }
        assert!(matches!(lanes::simulate(&Circuit::new(MAX_QUBITS + 1)), Err(QuantumError::TooManyQubits(_))));
    }

    #[test]
    fn parity_is_compared_not_asserted() {
        let fx = |v: Vec<i64>| Output::Fixed { values: v, frac: 30 };
        assert_eq!(compare(&fx(vec![5, -7]), &fx(vec![5, -7])), Parity::BitExact);
        assert_eq!(compare(&fx(vec![5, -7]), &fx(vec![5, -6])), Parity::Within { max_ulp: 1, max_abs: 1.0 / (1u64 << 30) as f64 });
        assert_eq!(compare(&fx(vec![5]), &Output::Fixed { values: vec![5], frac: 29 }), Parity::Uncertified);
        assert_eq!(compare(&Output::Fixed { values: vec![1], frac: 64 }, &Output::Fixed { values: vec![2], frac: 64 }), Parity::Uncertified);
        let one_up = f64::from_bits(1.0f64.to_bits() + 1);
        assert_eq!(compare(&Output::Float(vec![1.0, -0.5]), &Output::Float(vec![1.0, -0.5])), Parity::BitExact);
        assert_eq!(compare(&Output::Float(vec![1.0]), &Output::Float(vec![one_up])), Parity::Within { max_ulp: 1, max_abs: one_up - 1.0 });
        assert_eq!(compare(&Output::Float(vec![1.0]), &Output::Float(vec![f64::NAN])), Parity::Uncertified);
        assert_eq!(compare(&Output::Float(vec![f64::INFINITY]), &Output::Float(vec![f64::MAX])), Parity::Uncertified);
        assert_eq!(compare(&Output::Bits(vec![3]), &Output::Bits(vec![1])), Parity::Uncertified);
        // Across zero, neighbours are one apart.
        let tiny = f64::from_bits(1);
        assert_eq!(compare(&Output::Float(vec![tiny]), &Output::Float(vec![-tiny])), Parity::Within { max_ulp: 2, max_abs: 2.0 * tiny });
        // The worst case is the corpus's parity; nothing certifies an empty one.
        let c = certify("k", "port", "m", "g", vec![(vec![], fx(vec![1]), fx(vec![1])), (vec![], fx(vec![1]), fx(vec![3]))]);
        assert_eq!(c.parity, Parity::Within { max_ulp: 2, max_abs: 2.0 / (1u64 << 30) as f64 });
        assert_eq!(certify("k", "port", "m", "g", Vec::new()).parity, Parity::Uncertified);
        // Non-finite values certify nothing, even when they match.
        assert_eq!(compare(&Output::Float(vec![f64::NAN]), &Output::Float(vec![f64::NAN])), Parity::Uncertified);
        assert_eq!(compare(&Output::Float(vec![f64::INFINITY]), &Output::Float(vec![f64::INFINITY])), Parity::Uncertified);
        // Circuits that differ encode differently, however many controls.
        let x = |controls: Vec<u8>| Gate { base: BaseGate::X, controls, target: 1, param: 0 };
        let a = Circuit { n_qubits: 2, ops: vec![x(vec![0; 1280])] };
        let mut b = Circuit { n_qubits: 2, ops: vec![x(vec![])] };
        b.ops.extend((0..256).map(|_| Gate { base: BaseGate::I, controls: vec![], target: 0, param: 0 }));
        assert_ne!(lanes::circuit_bytes(&a), lanes::circuit_bytes(&b));
        // Outputs split differently between reference and member hash apart.
        let a = certify("k", "port", "m", "g", vec![(vec![], fx(vec![1, 2]), fx(vec![3]))]);
        let b = certify("k", "port", "m", "g", vec![(vec![], fx(vec![1]), fx(vec![2, 3]))]);
        assert_ne!(a.corpus, b.corpus);
    }

    #[test]
    fn a_sampling_device_is_held_to_a_distribution() {
        let Parity::Statistical { fidelity, shots } = statistical(&[0.5, 0.5], &[500, 500]) else { panic!() };
        assert!((fidelity - 1.0).abs() < 1e-12 && shots == 1000);
        let Parity::Statistical { fidelity, .. } = statistical(&[1.0, 0.0], &[500, 500]) else { panic!() };
        assert!((fidelity - 0.5).abs() < 1e-12);
        // Weights are normalised: the scale of the reference does not matter.
        assert_eq!(statistical(&[2.0, 2.0], &[500, 500]), statistical(&[0.5, 0.5], &[500, 500]));
        let Parity::Statistical { fidelity, .. } = statistical(&[1e12, 1e12], &[1, 1]) else { panic!() };
        assert!(fidelity <= 1.0);
        for bad in [statistical(&[0.0, 0.0], &[1, 1]), statistical(&[-0.5, 1.5], &[1, 1]), statistical(&[f64::NAN, 1.0], &[1, 1]), statistical(&[1.0], &[1, 1]), statistical(&[1.0, 1.0], &[0, 0]), statistical(&[1.0, 1.0], &[u64::MAX, 1])] {
            assert_eq!(bad, Parity::Uncertified);
        }
    }

    #[test]
    fn a_sampling_device_is_certified_by_its_counts() {
        let case = |counts: Vec<u64>| (vec![1u8], vec![0.5, 0.5], counts);
        let good = certify_sampling("k", "native", "remote/qpu", "g", vec![case(vec![500, 500]), case(vec![480, 520])]);
        let Parity::Statistical { fidelity, shots } = good.parity else { panic!("{good:?}") };
        assert!(fidelity > 0.999 && fidelity < 1.0 && shots == 1000, "{fidelity} {shots}");
        assert_eq!(good.cases, 2);
        let worse = certify_sampling("k", "native", "remote/qpu", "g", vec![case(vec![500, 500]), case(vec![900, 100])]);
        let Parity::Statistical { fidelity: f2, .. } = worse.parity else { panic!() };
        assert!(f2 < fidelity);
        assert_ne!(good.corpus, worse.corpus);
        assert_eq!(certify_sampling("k", "native", "remote/qpu", "g", Vec::new()).parity, Parity::Uncertified);
        // A bad case spoils the certificate.
        assert_eq!(certify_sampling("k", "native", "remote/qpu", "g", vec![case(vec![500, 500]), (vec![], vec![0.0, 0.0], vec![1, 1])]).parity, Parity::Uncertified);
    }

    #[test]
    fn requirements_are_met_in_order() {
        let within = |u, a| Parity::Within { max_ulp: u, max_abs: a };
        assert!(Parity::BitExact.meets(&Parity::BitExact));
        assert!(Parity::BitExact.meets(&within(0, 0.0)));
        assert!(Parity::BitExact.meets(&Parity::Statistical { fidelity: 1.0, shots: u64::MAX }));
        assert!(!within(1, 1e-9).meets(&Parity::BitExact));
        assert!(within(1, 1e-9).meets(&within(4, 1e-6)));
        assert!(!within(8, 1e-9).meets(&within(4, 1e-6)));
        // A bound is not a fidelity, however tight.
        assert!(!within(0, 0.0).meets(&Parity::Statistical { fidelity: 0.0, shots: 0 }));
        assert!(!within(u64::MAX, 1e9).meets(&Parity::Statistical { fidelity: 0.99, shots: 1000 }));
        let s = Parity::Statistical { fidelity: 0.995, shots: 10_000 };
        assert!(s.meets(&Parity::Statistical { fidelity: 0.99, shots: 1000 }));
        assert!(!s.meets(&Parity::Statistical { fidelity: 0.999, shots: 1000 }));
        assert!(!s.meets(&within(1_000_000, 1.0)));
        assert!(!Parity::Uncertified.meets(&Parity::Statistical { fidelity: 0.0, shots: 0 }));
        assert!(!Parity::BitExact.meets(&Parity::Uncertified));
    }

    fn entry(member: &str, implementation: &str, parity: Parity, nj: Option<u64>) -> KernelEntry {
        KernelEntry {
            kernel: KERNEL_CIRCUIT_APPLY.into(),
            implementation: implementation.into(),
            certificate: Certificate { kernel: KERNEL_CIRCUIT_APPLY.into(), implementation: implementation.into(), member: member.into(), generator: "g".into(), parity, cases: 1, corpus: [1; 32] },
            energy: nj.map(|e| (e, EnergyClass::ModelBased)),
        }
    }

    fn member(id: &str, class: FabricClass, presence: Presence, kernels: Vec<KernelEntry>) -> Member {
        Member { id: id.into(), class, presence, kernels, detail: String::new() }
    }

    #[test]
    fn placement_serves_the_cheapest_certified_kernel() {
        let members = vec![
            member("local/cpu", FabricClass::Cpu, Presence::Detected, vec![entry("local/cpu", REFERENCE, Parity::BitExact, Some(900))]),
            member("local/gpu", FabricClass::Gpu, Presence::Detected, vec![entry("local/gpu", "lanes32", Parity::BitExact, Some(40)), entry("local/gpu", "f32", Parity::Within { max_ulp: 3, max_abs: 1e-7 }, Some(10))]),
            member("local/npu", FabricClass::Npu, Presence::Detected, vec![entry("local/npu", "bf16", Parity::Uncertified, Some(1))]),
            member("remote/qpu", FabricClass::Qpu, Presence::Reachable, vec![entry("remote/qpu", "native", Parity::Statistical { fidelity: 0.99, shots: 4000 }, Some(0))]),
        ];
        let (m, k) = place(&members, KERNEL_CIRCUIT_APPLY, &Parity::BitExact).unwrap();
        assert_eq!((m.id.as_str(), k.implementation.as_str()), ("local/gpu", "lanes32"));
        let (m, k) = place(&members, KERNEL_CIRCUIT_APPLY, &Parity::Within { max_ulp: 4, max_abs: 1e-6 }).unwrap();
        assert_eq!((m.id.as_str(), k.implementation.as_str()), ("local/gpu", "f32"));
        // A fidelity requirement is met by bit-exact kernels only, here: the
        // f32 bound does not stand in for it, the uncertified kernel is never
        // placed, and the reachable member waits for detection.
        let (_, k) = place(&members, KERNEL_CIRCUIT_APPLY, &Parity::Statistical { fidelity: 0.9, shots: 100 }).unwrap();
        assert_eq!(k.implementation, "lanes32");
        assert!(place(&members[2..], KERNEL_CIRCUIT_APPLY, &Parity::Statistical { fidelity: 0.9, shots: 100 }).is_none());
        // A known figure, however large, comes before none.
        let known = vec![member("b", FabricClass::Cpu, Presence::Detected, vec![entry("b", "p", Parity::BitExact, Some(u64::MAX))]), member("a", FabricClass::Cpu, Presence::Detected, vec![entry("a", "p", Parity::BitExact, None)])];
        assert_eq!(place(&known, KERNEL_CIRCUIT_APPLY, &Parity::BitExact).unwrap().0.id, "b");
        // Ties fall to the member id, the same every run.
        let tie = vec![member("b", FabricClass::Cpu, Presence::Detected, vec![entry("b", REFERENCE, Parity::BitExact, None)]), member("a", FabricClass::Cpu, Presence::Detected, vec![entry("a", REFERENCE, Parity::BitExact, None)])];
        assert_eq!(place(&tie, KERNEL_CIRCUIT_APPLY, &Parity::BitExact).unwrap().0.id, "a");
        // The local CPU serves its reference, which a certified port of equal
        // cost does not displace.
        let mut local = detect_local();
        assert_eq!(local.presence, Presence::Detected);
        let id = local.id.clone();
        local.kernels.push(KernelEntry { kernel: KERNEL_CIRCUIT_APPLY.into(), implementation: "lanes32".into(), certificate: certify_lanes(&id, 5, 1), energy: None });
        assert_eq!(place(std::slice::from_ref(&local), KERNEL_CIRCUIT_APPLY, &Parity::BitExact).unwrap().1.implementation, REFERENCE);
    }

    #[test]
    fn placement_relies_only_on_a_certificate_of_its_own() {
        let ok = entry("local/gpu", "lanes32", Parity::BitExact, Some(1));
        let only = |k: KernelEntry, class| place(&[member("local/gpu", class, Presence::Detected, vec![k])], KERNEL_CIRCUIT_APPLY, &Parity::BitExact).is_some();
        assert!(only(ok.clone(), FabricClass::Gpu));
        // Another kernel's, another implementation's, another member's certificate.
        let mut k = ok.clone();
        k.certificate.kernel = "wai.quantum.other".into();
        assert!(!only(k, FabricClass::Gpu));
        let mut k = ok.clone();
        k.certificate.implementation = "f32".into();
        assert!(!only(k, FabricClass::Gpu));
        let mut k = ok.clone();
        k.certificate.member = "local/cpu".into();
        assert!(!only(k, FabricClass::Gpu));
        // A certificate earned on no corpus: only a CPU's own reference.
        let mut k = ok.clone();
        k.certificate.cases = 0;
        assert!(!only(k, FabricClass::Gpu));
        let reference = KernelEntry { kernel: KERNEL_CIRCUIT_APPLY.into(), implementation: REFERENCE.into(), certificate: Certificate::reference(KERNEL_CIRCUIT_APPLY, "local/gpu"), energy: None };
        assert!(!only(reference.clone(), FabricClass::Gpu));
        assert!(only(reference, FabricClass::Cpu));
    }

    #[test]
    fn receipts_verify_and_refuse() {
        let signer = SigningKey::from_bytes(&[7u8; 32]);
        let mut member = detect_local();
        let cert = certify_lanes(&member.id, 20, 3);
        member.kernels.push(KernelEntry { kernel: KERNEL_CIRCUIT_APPLY.into(), implementation: "lanes32".into(), certificate: cert.clone(), energy: None });
        let entry = member.kernels.last().unwrap().clone();
        let counter = EnergyClass::OnChipCounter { uncertainty: Uncertainty { relative_ppm: 50_000, window_us: 1_000 }, filtering: CounterFiltering::Off };
        for (joules, class) in [(1234, Some(counter.clone())), (0, None)] {
            let r = FabricReceipt::seal(&signer, "fabric-test", [9; 32], &member, &entry, joules, class);
            assert!(r.verify());
            assert!(r.certificate_matches(&cert));
            assert!(!r.certificate_matches(&certify_lanes(&member.id, 20, 4)));
            assert!(!r.certificate_matches(&certify_lanes("local/other", 20, 3)));
            let back = FabricReceipt::from_json(&r.to_json()).unwrap();
            assert_eq!(back, r);
            assert!(back.verify());
        }
        let r = FabricReceipt::seal(&signer, "fabric-test", [9; 32], &member, &entry, 1234, Some(counter.clone()));
        // Tampering: a joule, the member, the parity, the class.
        let mut t = r.clone();
        t.joules_micro += 1;
        assert!(!t.verify());
        let mut t = r.clone();
        t.member_id = "local/gpu".into();
        assert!(!t.verify());
        let mut t = r.clone();
        t.parity = Parity::Within { max_ulp: 1, max_abs: 1e-9 };
        assert!(!t.verify());
        let mut t = r.clone();
        t.energy_class = Some(EnergyClass::ModelBased);
        assert!(!t.verify());
        // The class follows the joules as energy-measurement §2.7 encodes it:
        // its own tag, here 2 for a model, with no byte before it.
        let modelled = FabricReceipt::seal(&signer, "fabric-test", [9; 32], &member, &entry, 1234, Some(EnergyClass::ModelBased));
        let payload = modelled.signing_payload();
        let at = payload.len() - 32 - 8 - "fabric-test".len() - 1;
        assert_eq!(payload[at], 2);
        assert_eq!(payload[at - 8..at], 1234u64.to_be_bytes());
        let unmetered = FabricReceipt::seal(&signer, "fabric-test", [9; 32], &member, &entry, 0, None).signing_payload();
        assert_eq!(unmetered[unmetered.len() - 32 - 8 - "fabric-test".len() - 1], 0);
        // Moving bytes between named fields changes what is signed.
        let mut t = r.clone();
        t.kernel = format!("{}\0{}", t.kernel, t.implementation);
        t.implementation = String::new();
        assert!(!t.verify());
        // A figure without its class, a class without a figure, an
        // uncertified kernel: none verifies, however well signed.
        assert!(!FabricReceipt::seal(&signer, "fabric-test", [9; 32], &member, &entry, 1234, None).verify());
        assert!(!FabricReceipt::seal(&signer, "fabric-test", [9; 32], &member, &entry, 0, Some(EnergyClass::ModelBased)).verify());
        let mut bad = entry.clone();
        bad.certificate.parity = Parity::Uncertified;
        assert!(!FabricReceipt::seal(&signer, "fabric-test", [9; 32], &member, &bad, 0, None).verify());
        // Malformed JSON is refused, not a panic.
        for junk in ["", "{}", "[1]", &r.to_json().replace("\"sig\":\"", "\"sig\":\"zz")] {
            assert!(FabricReceipt::from_json(junk).is_none());
        }
    }

    #[test]
    fn detection_says_how_it_learned() {
        let local = detect_local();
        assert_eq!(local.class, FabricClass::Cpu);
        assert!(local.detail.contains("asked of the CPU") || local.detail.contains("compiled for"), "{}", local.detail);
        assert_eq!(local.kernels.len(), 1);
        assert_eq!(local.kernels[0].certificate.member, local.id);
    }
}