wai-quantum 0.4.1

//! 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. [`Certification`] does the same
//!   one case at a time, for a member whose outputs arrive asynchronously, and
//!   [`Corpus`] names the circuits: random-v1, or fabric-v1, which adds wide
//!   circuits so that every dispatch shape a member uses is exercised.
//! - **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 needs neither: for a valid circuit of at most
//! [`lanes::horizon`] gates, every amplitude stays inside 32 bits, so a fabric
//! with only 32-bit integer lanes reproduces it bit for bit; past that horizon
//! a 32-bit member must check each result, as [`lanes::simulate_checked`]
//! does. [`lanes`] is that kernel written with only the operations such a
//! fabric has, and its certificate against the native simulator is bit-exact.
//! [`plan`] is the program an accelerator member runs for a circuit, with a
//! CPU executor of exactly that program, and [`wgsl`] is the same kernel in
//! WGSL for a WebGPU member, with its host layout and the argument that it 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.
//!
//! The gate kernel is named once per capability, because the capabilities'
//! phase tables differ: [`KERNEL_CIRCUIT_APPLY`] for `wai.quantum.circuit`
//! ([`Gateset::V1`]) and [`KERNEL_CIRCUIT2_APPLY`] for `wai.quantum.circuit2`
//! ([`Gateset::V2`]). A certificate names its kernel, so it holds for one
//! table only.
//!
//! # 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 (random-v1) and up to seventeen (fabric-v1), under each
//!   gateset: every final amplitude bit-identical. The corpus digest of each
//!   gateset's certificate is pinned for both corpora, so a certificate issued
//!   under either one can be re-earned. 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.
//! - **The range guard is exact.** [`lanes::apply_words`] computes every
//!   output as an exact 64-bit value beside the stored 32-bit lane, and flags
//!   a gate exactly when the reference's result leaves 32 bits: over random
//!   gates and states across the whole 32-bit range, the stored lanes equal
//!   [`lanes::apply`]'s and the flag equals a 128-bit recomputation. Valid
//!   circuits, the QFT and a long run of phase gates never raise it; the
//!   horizon below which it cannot rise is pinned per gateset. The executor of
//!   [`plan`] equals the native simulator over both corpora, from more than
//!   one start state, and refuses what it 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, and a certificate earned under one gateset does not serve the
//!   other gateset's kernel.
//! - **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.** [`detect_local`] detects the CPU:
//!   on x86-64 and aarch64 it 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. With
//!   `quantum_fabric_webgpu`, each WebGPU adapter that passes the arithmetic
//!   probe in this process is detected too; it is placed once its own run of
//!   the corpus certifies it. 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; the WebGPU member
//!   (feature `quantum_fabric_webgpu`) runs them on real 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, Gateset, 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, with the
/// `wai.quantum.circuit` table ([`Gateset::V1`]).
pub const KERNEL_CIRCUIT_APPLY: &str = "wai.quantum.circuit/apply";

/// The same kernel with the `wai.quantum.circuit2` table ([`Gateset::V2`]).
pub const KERNEL_CIRCUIT2_APPLY: &str = "wai.quantum.circuit2/apply";

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

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

/// The corpus [`certify_lanes`] draws for [`Gateset::V2`]: the same circuits as
/// [`GENERATOR_RANDOM_CIRCUITS`], in the circuit2 gateset.
pub const GENERATOR_RANDOM_CIRCUITS2: &str = "wai.quantum.circuit2/random-v1";

/// The gate kernel's name for circuits in `gs`: [`KERNEL_CIRCUIT_APPLY`] or
/// [`KERNEL_CIRCUIT2_APPLY`].
pub const fn apply_kernel(gs: Gateset) -> &'static str {
    match gs {
        Gateset::V1 => KERNEL_CIRCUIT_APPLY,
        Gateset::V2 => KERNEL_CIRCUIT2_APPLY,
    }
}

/// The name of the random corpus [`certify_lanes`] draws in `gs`:
/// [`GENERATOR_RANDOM_CIRCUITS`] or [`GENERATOR_RANDOM_CIRCUITS2`].
pub const fn random_generator(gs: Gateset) -> &'static str {
    match gs {
        Gateset::V1 => GENERATOR_RANDOM_CIRCUITS,
        Gateset::V2 => GENERATOR_RANDOM_CIRCUITS2,
    }
}

/// The corpus every fabric member is certified on, for `wai.quantum.circuit`:
/// the random-v1 circuits, then wide circuits of 11 to 17 qubits drawn from the
/// same stream, so every dispatch shape a member uses is exercised.
pub const GENERATOR_FABRIC: &str = "wai.quantum.circuit/fabric-v1";

/// The same corpus as [`GENERATOR_FABRIC`], in the circuit2 gateset.
pub const GENERATOR_FABRIC2: &str = "wai.quantum.circuit2/fabric-v1";

/// The name of the fabric corpus in `gs`: [`GENERATOR_FABRIC`] or
/// [`GENERATOR_FABRIC2`].
pub const fn fabric_generator(gs: Gateset) -> &'static str {
    match gs {
        Gateset::V1 => GENERATOR_FABRIC,
        Gateset::V2 => GENERATOR_FABRIC2,
    }
}

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 the gate kernel for each gateset, [`KERNEL_CIRCUIT_APPLY`]
/// and [`KERNEL_CIRCUIT2_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}");
    let reference = |kernel: &str| KernelEntry { kernel: kernel.into(), implementation: REFERENCE.into(), certificate: Certificate::reference(kernel, &id), energy: None };
    Member {
        kernels: Gateset::ALL.into_iter().map(|gs| reference(apply_kernel(gs))).collect(),
        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>"` (with ` wide=<w>` after
    /// it for fabric-v1, [`Corpus::generator`]), 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`], one case at a time, for members whose outputs arrive
/// asynchronously (a GPU, a browser): there is no need to hold the corpus.
/// The same cases in the same order give the same [`Certificate`].
#[derive(Clone, Debug)]
pub struct Certification {
    hasher: blake3::Hasher,
    parity: Option<Parity>,
    cases: u64,
}

impl Certification {
    /// Starts the corpus digest with the domain [`certify`] uses.
    pub fn new() -> Certification {
        let mut hasher = blake3::Hasher::new();
        hasher.update(DOMAIN_CORPUS);
        Certification { hasher, parity: None, cases: 0 }
    }

    /// Folds one case in exactly as [`certify`] does: the input, the
    /// reference's bytes and the member's bytes, each prefixed with its length
    /// (u64, little-endian); the parity is the worst so far.
    pub fn add(&mut self, input: &[u8], reference: &Output, member: &Output) {
        let (r, m) = (reference.bytes(), member.bytes());
        for bytes in [input, r.as_slice(), m.as_slice()] {
            self.hasher.update(&(bytes.len() as u64).to_le_bytes());
            self.hasher.update(bytes);
        }
        let p = compare(reference, member);
        self.parity = Some(self.parity.map_or(p, |q| q.worst(p)));
        self.cases += 1;
    }

    /// The cases folded in so far.
    pub fn cases(&self) -> u64 {
        self.cases
    }

    /// The certificate the cases so far earn. With no case it certifies
    /// nothing.
    pub fn finish(self, kernel: &str, implementation: &str, member: &str, generator: &str) -> Certificate {
        Certificate {
            kernel: kernel.into(),
            implementation: implementation.into(),
            member: member.into(),
            generator: generator.into(),
            parity: self.parity.unwrap_or(Parity::Uncertified),
            cases: self.cases,
            corpus: *self.hasher.finalize().as_bytes(),
        }
    }
}

impl Default for Certification {
    fn default() -> Self {
        Self::new()
    }
}

/// 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 c = Certification::new();
    for (input, reference, out) in cases {
        c.add(&input, &reference, &out);
    }
    c.finish(kernel, implementation, member, generator)
}

/// A certification corpus of the gate kernel: which circuits, from which seed.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Corpus {
    /// `cases` circuits of [`lanes::random_circuit`] from `seed` (random-v1).
    Random { seed: u64, cases: usize },
    /// random-v1's `cases`, then `wide` circuits of
    /// [`lanes::random_wide_circuit`] continuing the same stream (fabric-v1).
    Fabric { seed: u64, cases: usize, wide: usize },
}

/// The corpus members are placed on: fabric-v1, seed 7, 200 random-v1
/// circuits and 24 wide ones.
pub const FABRIC_DEFAULT: Corpus = Corpus::Fabric { seed: 7, cases: 200, wide: 24 };

impl Corpus {
    /// The certificate's generator string:
    /// `"<generator> seed=<seed> cases=<cases>"` for random-v1
    /// ([`random_generator`], the string [`certify_lanes`] has always
    /// written), and `"<generator> seed=<seed> cases=<cases> wide=<wide>"` for
    /// fabric-v1 ([`fabric_generator`]).
    pub fn generator(&self, gs: Gateset) -> String {
        match *self {
            Corpus::Random { seed, cases } => format!("{} seed={seed} cases={cases}", random_generator(gs)),
            Corpus::Fabric { seed, cases, wide } => format!("{} seed={seed} cases={cases} wide={wide}", fabric_generator(gs)),
        }
    }

    /// The corpus's short name: `"random-v1"` or `"fabric-v1"`.
    pub fn name(&self) -> &'static str {
        match self {
            Corpus::Random { .. } => "random-v1",
            Corpus::Fabric { .. } => "fabric-v1",
        }
    }

    /// The circuits, in order. Both gatesets draw the same ops.
    pub fn circuits(&self, gs: Gateset) -> Vec<Circuit> {
        let (seed, cases, wide) = match *self {
            Corpus::Random { seed, cases } => (seed, cases, 0),
            Corpus::Fabric { seed, cases, wide } => (seed, cases, wide),
        };
        let mut s = seed;
        let mut v: Vec<Circuit> = (0..cases).map(|_| lanes::random_circuit(&mut s, gs)).collect();
        v.extend((0..wide).map(|_| lanes::random_wide_circuit(&mut s, gs)));
        v
    }
}

/// Certify the 32-bit-lane port of the gate kernel for `gs`
/// ([`apply_kernel`]), as implementation `"lanes32"` on `member`, against the
/// native simulator on `circuits` random circuits in `gs` drawn from `seed`
/// ([`random_generator`]). The two gatesets draw the same ops from the same
/// seed; their certificates differ in kernel, generator and corpus. The same
/// as [`lanes::certify_corpus`] on [`Corpus::Random`].
pub fn certify_lanes(gs: Gateset, member: &str, circuits: usize, seed: u64) -> Certificate {
    lanes::certify_corpus(gs, member, Corpus::Random { seed, cases: circuits })
}

/// 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 for as long as every result stays inside
/// 32 bits: always, for a valid circuit of at most [`horizon`](lanes::horizon)
/// gates, and [`apply_words`](lanes::apply_words) says exactly when it does
/// not. The gate entries are prepared by the host from the core's pinned table
/// and handed to the lanes as 32-bit values
/// ([`GateWords`](lanes::GateWords)).
pub mod lanes {
    use super::{Certificate, Certification, Circuit, Corpus, FRAC, MAX_QUBITS, Output, QuantumError, apply_kernel, plan};
    use crate::quantum::{BaseGate, Gate, Gateset, 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`. Within [`horizon`] gates an
    /// amplitude stays below `2^31` in magnitude and a gate entry is at most
    /// `2^30`, so the product is inside that range. For every pair of 32-bit
    /// inputs the result is the low 32 bits of the true one ([`fxmul_wide`]).
    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, from the gateset's table. Only for a
    /// validated gate.
    fn matrix(g: &Gate, gs: Gateset) -> [[Lane; 2]; 2] {
        let m = g.base.matrix(g.param, gs);
        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, c.gateset));
        }
        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 in `gs`: two to ten qubits, up to
    /// three distinct controls, dyadic phases up to `P(32)` and no parameter
    /// on any other gate, so it is valid in either gateset. The ops drawn from
    /// a seed are the same in both.
    pub fn random_circuit(s: &mut u64, gs: Gateset) -> Circuit {
        let n = 2 + (next(s) % 9) as u8;
        random_ops(s, gs, n)
    }

    /// A random circuit like [`random_circuit`], on 11 to 17 qubits.
    pub fn random_wide_circuit(s: &mut u64, gs: Gateset) -> Circuit {
        let n = 11 + (next(s) % 7) as u8;
        random_ops(s, gs, n)
    }

    /// The ops of a random circuit on `n` qubits: 10 to 59 of them.
    fn random_ops(s: &mut u64, gs: Gateset, n: u8) -> Circuit {
        let mut c = Circuit::with_gateset(n, gs);
        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
    }

    /// A port's lanes as the harness compares them: [`Output::Fixed`] of the
    /// lanes widened to 64 bits, `[re, im]` per amplitude, at [`FRAC`].
    pub fn output(lanes: &[Lane]) -> Output {
        Output::Fixed { values: lanes.iter().flat_map(|a| [i64::from(a[0]), i64::from(a[1])]).collect(), frac: FRAC }
    }

    /// The reference's output for a corpus circuit: `c.simulate_from(0)`, laid
    /// out as [`output`] lays out lanes.
    pub fn reference_output(c: &Circuit) -> Result<Output, QuantumError> {
        let native = c.simulate_from(0)?;
        Ok(Output::Fixed { values: native.amps.iter().flat_map(|a| [a.re, a.im]).collect(), frac: FRAC })
    }

    /// Certify the lane kernel on the CPU over `corpus`, against the native
    /// simulator: implementation `"lanes32"` of [`apply_kernel`]`(gs)` on
    /// `member`, with the generator string [`Corpus::generator`].
    pub fn certify_corpus(gs: Gateset, member: &str, corpus: Corpus) -> Certificate {
        let mut cert = Certification::new();
        for c in corpus.circuits(gs) {
            let reference = reference_output(&c).expect("corpus circuits are valid");
            let port = output(&simulate(&c).expect("corpus circuits are valid"));
            cert.add(&circuit_bytes(&c), &reference, &port);
        }
        cert.finish(apply_kernel(gs), "lanes32", member, &corpus.generator(gs))
    }

    // -----------------------------------------------------------------------
    // Gate words and the exact range guard
    // -----------------------------------------------------------------------

    /// One gate as a 32-bit-lane member takes it: the matrix entries as 32-bit
    /// two's-complement patterns (`m00.re, m00.im, m01.re, m01.im, m10.re,
    /// m10.im, m11.re, m11.im`), the target's bit and the controls' bits.
    #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
    pub struct GateWords {
        pub m: [u32; 8],
        pub tbit: u32,
        pub ctrl: u32,
    }

    /// The words of a validated gate of a circuit on at most
    /// [`MAX_QUBITS`] qubits: the entries of the gate's matrix in `gs` as
    /// 32-bit patterns, `tbit = 1 << target`, and `ctrl` the OR of
    /// `1 << c` over the controls (a control a circuit/1 gate repeats folds
    /// into one bit).
    pub fn gate_words(g: &Gate, gs: Gateset) -> GateWords {
        let m = g.base.matrix(g.param, gs);
        let w = |a: crate::quantum::Amp| [a.re as i32 as u32, a.im as i32 as u32];
        let ([a, b], [c, d], [e, f], [h, k]) = (w(m[0][0]), w(m[0][1]), w(m[1][0]), w(m[1][1]));
        GateWords { m: [a, b, c, d, e, f, h, k], tbit: 1 << g.target, ctrl: g.controls.iter().fold(0, |acc, &q| acc | 1 << q) }
    }

    /// The core's `fx(a, b) = (a·b + 2^29) >> 30`, exactly: the product of two
    /// 32-bit values is at most `2^62` in size, so the sum is inside 64 bits.
    fn fx_exact(a: i32, b: i32) -> i64 {
        (i64::from(a) * i64::from(b) + (1 << 29)) >> 30
    }

    /// The exact value of `fx(a, b) = (a·b + 2^29) >> 30` as a 64-bit
    /// two's-complement `(high, low)` pair, for every pair of 32-bit inputs;
    /// `low == fxmul(a, b) as u32`.
    pub fn fxmul_wide(a: i32, b: i32) -> (u32, u32) {
        let v = fx_exact(a, b);
        ((v >> 32) as u32, v as u32)
    }

    /// The operands every multiply probe runs pairwise: zero, `±1`, `±2`,
    /// `±2^29`, `±(2^30 − 1)`, `±2^30`, `±46341`, `±3·2^29`, `±65535`,
    /// `±65536`, and the largest, smallest and next-to-smallest 32-bit values.
    pub const PROBE_EDGES: [i32; 22] = [
        0,
        1,
        -1,
        2,
        -2,
        1 << 29,
        -(1 << 29),
        (1 << 30) - 1,
        -((1 << 30) - 1),
        1 << 30,
        -(1 << 30),
        46341,
        -46341,
        3 << 29,
        -(3 << 29),
        65535,
        -65535,
        65536,
        -65536,
        i32::MAX,
        i32::MIN,
        i32::MIN + 1,
    ];

    /// One gate on a state of `2^n` lanes (`n ≥ 1`): the general 2×2 path on
    /// every pair whose control bits are all set, from exact 64-bit values.
    /// The stored lanes are the low 32 bits of those values, and equal
    /// [`apply`]'s.
    ///
    /// Returns `Some(true)` if every exact output fits in 32 bits, and
    /// `Some(false)` if any does not: then the reference's result has left
    /// 32 bits and no lane can hold it. Returns `None`, with the state
    /// untouched, if the length is not a power of two of at least 2 or the
    /// words are malformed for it: `tbit` zero, not a power of two, or above
    /// half the length; `ctrl` sharing `tbit`; `ctrl` with a bit at or above
    /// the length.
    pub fn apply_words(amps: &mut [Lane], w: &GateWords) -> Option<bool> {
        let len = amps.len();
        if len < 2 || !len.is_power_of_two() {
            return None;
        }
        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 None;
        }
        let e = |k: usize| w.m[k] as i32;
        let mut fits = true;
        for i in 0..len {
            if i & tbit == 0 && i & ctrl == ctrl {
                let j = i | tbit;
                let (a0, a1) = (amps[i], amps[j]);
                let row = |r: usize| -> [i64; 2] {
                    let (mr, mi, nr, ni) = (e(4 * r), e(4 * r + 1), e(4 * r + 2), e(4 * r + 3));
                    [
                        fx_exact(mr, a0[0]) - fx_exact(mi, a0[1]) + fx_exact(nr, a1[0]) - fx_exact(ni, a1[1]),
                        fx_exact(mr, a0[1]) + fx_exact(mi, a0[0]) + fx_exact(nr, a1[1]) + fx_exact(ni, a1[0]),
                    ]
                };
                let (o0, o1) = (row(0), row(1));
                fits &= o0.iter().chain(&o1).all(|v| i32::try_from(*v).is_ok());
                // `as` keeps the low 32 bits.
                amps[i] = [o0[0] as i32, o0[1] as i32];
                amps[j] = [o1[0] as i32, o1[1] as i32];
            }
        }
        Some(fits)
    }

    /// Gates in order from `state`, as a 32-bit-lane member runs them: the
    /// lanes, and the lowest position in `gates` of a gate whose exact result
    /// left 32 bits. `None` if any gate's words are malformed for this state
    /// ([`apply_words`]).
    pub fn run_words(state: &[Lane], gates: &[GateWords]) -> Option<plan::LaneRun> {
        let mut amps = state.to_vec();
        let mut out_of_range = None;
        for (k, w) in gates.iter().enumerate() {
            if !apply_words(&mut amps, w)? && out_of_range.is_none() {
                out_of_range = Some(k as u32);
            }
        }
        Some(plan::LaneRun { amps, out_of_range })
    }

    /// [`Circuit::simulate_from`] in lanes, through [`plan::compile`] and
    /// [`plan::execute`], with the first op whose exact result left 32 bits.
    /// Refuses what the native simulator refuses, with the same error; the
    /// state starts at index `start % 2^n`, as the native one does.
    pub fn simulate_checked(c: &Circuit, start: usize) -> Result<plan::LaneRun, QuantumError> {
        Ok(plan::execute(&plan::compile(c, start)?))
    }

    /// `⌈√x⌉`.
    fn ceil_sqrt(x: u128) -> u128 {
        let r = x.isqrt();
        if r * r < x { r + 1 } else { r }
    }

    /// `2^60·δ` for [`horizon`], rounded up: the largest of
    /// `⌈√(|e|²·2^60)⌉ − 2^60` over every `P(k)` entry `e` of the table, and
    /// `⌈√(2h²·2^60)⌉ − 2^60` for `H`, whose entries are `±h`; zero if none
    /// exceeds one. Every other gate's matrix has one entry of size one in
    /// each row and column.
    pub(super) fn table_excess(gs: Gateset) -> u128 {
        const S: u128 = 1 << 60;
        let excess = |sq: u128| ceil_sqrt(sq * S).saturating_sub(S);
        let sq = |re: i64, im: i64| (re.unsigned_abs() as u128).pow(2) + (im.unsigned_abs() as u128).pow(2);
        let h = gs.inv_sqrt2();
        gs.table()[1..].iter().map(|p| excess(sq(p.re, p.im))).chain([excess(2 * sq(h, 0))]).max().unwrap_or(0)
    }

    /// The number of gates of a valid circuit in `gs` on `n_qubits`, from a
    /// basis state, that provably cannot take an amplitude out of 32 bits:
    /// every such circuit runs in lanes with the native simulator's bits.
    ///
    /// Each rounded product is off the exact one by at most half a unit, so a
    /// gate moves the state by at most `ε = 2√2·2^(n/2)·2^−30` (in units of
    /// one) beyond the fixed-point matrix's own action, and that matrix
    /// stretches the state by at most `1 + δ`, with `δ` the most by which the
    /// size of a `P(k)` entry of the table, or `√2·h` for `H`'s entries `±h`,
    /// exceeds one (zero if none does; every other gate's matrix has one entry
    /// of size one in each row and column). After `k` gates the state's norm
    /// is at most `(1 + δ)^k·(1 + kε)`, and a component reaches `2^31` units
    /// only once the norm reaches two. With `k(ε + 2δ) < 1`,
    /// `1 + kε < 2(1 − kδ)` and `(1 + δ)^k ≤ 1/(1 − kδ)`, so the norm stays
    /// below two. In integers at scale `2^60`:
    /// `(2^60 − 1) / (⌈√(2^(63+n))⌉ + 2·⌈2^60·δ⌉)`.
    pub fn horizon(n_qubits: u8, gs: Gateset) -> u64 {
        const S: u128 = 1 << 60;
        // From 58 qubits on, ε alone is more than one: no gate is safe. The
        // cut keeps `2^(63+n)` inside 128 bits.
        if n_qubits >= 58 {
            return 0;
        }
        let e = ceil_sqrt(1u128 << (63 + u32::from(n_qubits)));
        ((S - 1) / (e + 2 * table_excess(gs))) as u64
    }
}

pub mod plan;
pub mod wgsl;

/// 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, Gateset, 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() {
        for gs in Gateset::ALL {
            let cert = certify_lanes(gs, "local/test", 300, 7);
            assert_eq!(cert.parity, Parity::BitExact, "{cert:?}");
            assert_eq!(cert.cases, 300);
            assert_eq!(cert.generator, format!("{} seed=7 cases=300", random_generator(gs)));
            // The same corpus, the same certificate; another seed, another corpus.
            assert_eq!(certify_lanes(gs, "local/test", 300, 7).hash(), cert.hash());
            assert_ne!(certify_lanes(gs, "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, gs)).unwrap().iter().filter(|a| a[0] != 0 || a[1] != 0).count() >= 4).count();
            assert!(spread >= 100, "{gs:?}: {spread} of 300 circuits spread over four amplitudes or more");
        }
    }

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

    /// The lanes32 corpus of each gateset, seed 7, 200 cases. The circuit/1
    /// digest is the one 0.3.41 certified, so its certificates can still be
    /// re-earned; the circuit2 digest is computed with the correctly rounded
    /// table. The digests must never be edited to make this test pass.
    #[test]
    fn the_lanes32_corpus_of_each_gateset_is_pinned() {
        let v1 = certify_lanes(Gateset::V1, "local/test", 200, 7);
        assert_eq!(v1.parity, Parity::BitExact, "{v1:?}");
        assert_eq!(hex(&v1.corpus), "d18454c639acfd9c7b66450f4ded1aac4ab46cc10a7bedbcf4958a96e204fb36");
        let v2 = certify_lanes(Gateset::V2, "local/test", 200, 7);
        assert_eq!(v2.parity, Parity::BitExact, "{v2:?}");
        assert_eq!(hex(&v2.corpus), "3dbde276c1095bf827faec71d5980e050f8a55a5ba7d97cd3bbdaec3f43a13b2");
    }

    #[test]
    fn a_v2_certificate_is_its_own() {
        let v1 = certify_lanes(Gateset::V1, "local/test", 40, 7);
        let v2 = certify_lanes(Gateset::V2, "local/test", 40, 7);
        assert_eq!((v1.kernel.as_str(), v2.kernel.as_str()), (KERNEL_CIRCUIT_APPLY, KERNEL_CIRCUIT2_APPLY));
        assert_eq!(v1.generator, format!("{GENERATOR_RANDOM_CIRCUITS} seed=7 cases=40"));
        assert_eq!(v2.generator, format!("{GENERATOR_RANDOM_CIRCUITS2} seed=7 cases=40"));
        assert_eq!(v2.parity, Parity::BitExact, "{v2:?}");
        // The two gatesets draw the same ops from a seed; only the gateset,
        // and so the outputs, differ.
        let (mut a, mut b) = (7u64, 7u64);
        for _ in 0..40 {
            let (x, y) = (lanes::random_circuit(&mut a, Gateset::V1), lanes::random_circuit(&mut b, Gateset::V2));
            assert_eq!((x.n_qubits, &x.ops), (y.n_qubits, &y.ops));
            assert_eq!((x.gateset, y.gateset), (Gateset::V1, Gateset::V2));
            y.validate().unwrap();
        }
        assert_ne!(v1.corpus, v2.corpus);
        assert_ne!(v1.hash(), v2.hash());
        // Each serves its own kernel only, even filed under the other's.
        let mut member = detect_local();
        member.id = "local/test".into();
        let filed = |kernel: &str, cert: &Certificate| KernelEntry { kernel: kernel.into(), implementation: "lanes32".into(), certificate: cert.clone(), energy: Some((1, EnergyClass::ModelBased)) };
        for (gs, cert) in [(Gateset::V1, &v1), (Gateset::V2, &v2)] {
            let other = Gateset::ALL.into_iter().find(|&o| o != gs).unwrap();
            let mut m = member.clone();
            m.kernels = vec![filed(apply_kernel(gs), cert)];
            assert_eq!(place(std::slice::from_ref(&m), apply_kernel(gs), &Parity::BitExact).unwrap().1.implementation, "lanes32");
            m.kernels = vec![filed(apply_kernel(other), cert)];
            assert!(place(std::slice::from_ref(&m), apply_kernel(other), &Parity::BitExact).is_none(), "a {gs:?} certificate served {}", apply_kernel(other));
            assert!(place(std::slice::from_ref(&m), apply_kernel(gs), &Parity::BitExact).is_none());
        }
    }

    /// Five circuits the native simulator refuses, in each gateset.
    pub(super) fn refused_circuits() -> Vec<Circuit> {
        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)]),
        ];
        Gateset::ALL.into_iter().flat_map(|gateset| bad.clone().into_iter().map(move |(n_qubits, ops)| Circuit { n_qubits, ops, gateset })).collect()
    }

    #[test]
    fn the_lane_simulator_refuses_what_the_native_one_refuses() {
        for c in refused_circuits() {
            let native = c.simulate_from(0).unwrap_err();
            assert_eq!(lanes::simulate(&c).unwrap_err(), native);
            assert_eq!(lanes::simulate_checked(&c, 0).unwrap_err(), native);
        }
        assert!(matches!(lanes::simulate(&Circuit::new(MAX_QUBITS + 1)), Err(QuantumError::TooManyQubits(_))));
        assert!(matches!(lanes::simulate_checked(&Circuit::new(MAX_QUBITS + 1), 0), 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])], gateset: Gateset::V2 };
        let mut b = Circuit { n_qubits: 2, ops: vec![x(vec![])], gateset: Gateset::V2 };
        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(Gateset::V1, &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(Gateset::V1, &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(Gateset::V1, &member.id, 20, 4)));
            assert!(!r.certificate_matches(&certify_lanes(Gateset::V1, "local/other", 20, 3)));
            assert!(!r.certificate_matches(&certify_lanes(Gateset::V2, &member.id, 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);
        // The reference kernel of each gateset, each placeable on its own.
        let kernels: Vec<&str> = local.kernels.iter().map(|k| k.kernel.as_str()).collect();
        assert_eq!(kernels, [KERNEL_CIRCUIT_APPLY, KERNEL_CIRCUIT2_APPLY]);
        for k in &local.kernels {
            assert_eq!((k.certificate.member.as_str(), k.certificate.kernel.as_str(), k.implementation.as_str()), (local.id.as_str(), k.kernel.as_str(), REFERENCE));
        }
        for gs in Gateset::ALL {
            let (_, k) = place(std::slice::from_ref(&local), apply_kernel(gs), &Parity::BitExact).unwrap();
            assert_eq!((k.kernel.as_str(), k.implementation.as_str()), (apply_kernel(gs), REFERENCE));
        }
    }

    fn widened(lanes: &[lanes::Lane]) -> Vec<[i64; 2]> {
        lanes.iter().map(|a| [i64::from(a[0]), i64::from(a[1])]).collect()
    }

    fn native(c: &Circuit, start: usize) -> Vec<[i64; 2]> {
        c.simulate_from(start).unwrap().amps.iter().map(|a| [a.re, a.im]).collect()
    }

    #[test]
    fn certification_is_certify() {
        let mut s = 7u64;
        let cases: Vec<(Vec<u8>, Output, Output)> = (0..50)
            .map(|_| {
                let c = lanes::random_circuit(&mut s, Gateset::V1);
                (lanes::circuit_bytes(&c), lanes::reference_output(&c).unwrap(), lanes::output(&lanes::simulate(&c).unwrap()))
            })
            .collect();
        // The same cases with one member output a unit off, so that the worst
        // case is not the first.
        let mut off = cases.clone();
        let Output::Fixed { values, .. } = &mut off[17].2 else { panic!() };
        values[0] += 1;
        for (corpus, parity) in [(cases, Parity::BitExact), (off, Parity::Within { max_ulp: 1, max_abs: 1.0 / (1u64 << 30) as f64 }), (Vec::new(), Parity::Uncertified)] {
            let whole = certify("k", "port", "m", "g", corpus.clone());
            let mut one = Certification::new();
            for (input, reference, member) in &corpus {
                one.add(input, reference, member);
            }
            assert_eq!(one.cases(), corpus.len() as u64);
            let one = one.finish("k", "port", "m", "g");
            assert_eq!(one, whole);
            assert_eq!((one.parity, one.cases), (parity, corpus.len() as u64));
        }
        let empty = Certification::default().finish("k", "port", "m", "g");
        assert_eq!((empty.parity, empty.cases), (Parity::Uncertified, 0));
        assert_eq!(empty, certify("k", "port", "m", "g", Vec::new()));
    }

    #[test]
    fn fxmul_wide_is_the_exact_product() {
        let mut pairs: Vec<(i32, i32)> = lanes::PROBE_EDGES.iter().flat_map(|&a| lanes::PROBE_EDGES.iter().map(move |&b| (a, b))).collect();
        let mut s = 11u64;
        for _ in 0..400_000 {
            pairs.push((next(&mut s) as i32, next(&mut s) as i32));
        }
        for (a, b) in pairs {
            let (hi, lo) = lanes::fxmul_wide(a, b);
            let exact = (i128::from(a) * i128::from(b) + (1 << 29)) >> 30;
            assert_eq!(i128::from(((u64::from(hi) << 32) | u64::from(lo)) as i64), exact, "{a} × {b}");
            assert_eq!(lo, lanes::fxmul(a, b) as u32, "{a} × {b}");
        }
        let mut edges = lanes::PROBE_EDGES.to_vec();
        edges.sort();
        edges.dedup();
        assert_eq!(edges.len(), lanes::PROBE_EDGES.len());
    }

    #[test]
    fn apply_words_is_apply() {
        let fx = |a: i32, b: i32| (i128::from(a) * i128::from(b) + (1 << 29)) >> 30;
        let mut s = 13u64;
        let (mut inside, mut outside) = (0, 0);
        for case in 0..2000 {
            let n = 1 + (next(&mut s) % 10) as u8;
            let len = 1usize << n;
            // A third of the cases across the whole 32-bit range, some of the
            // values edges; a third with every output inside 32 bits; a third
            // at the boundary, where a sum of four products may leave it.
            let mode = case % 3;
            let value = |s: &mut u64, shift: u32| -> i32 {
                if mode == 0 && next(s).is_multiple_of(4) { lanes::PROBE_EDGES[(next(s) % 22) as usize] } else { (next(s) as i32) >> shift }
            };
            let (entry_shift, state_shift) = [(0, 0), (1, 3), (1, 1)][mode];
            let entries: [i32; 8] = std::array::from_fn(|_| value(&mut s, entry_shift));
            let state: Vec<lanes::Lane> = (0..len).map(|_| [value(&mut s, state_shift), value(&mut s, state_shift)]).collect();
            let target = (next(&mut s) % u64::from(n)) as u8;
            let tbit = 1usize << target;
            let ctrl = if next(&mut s).is_multiple_of(2) { 0 } else { (next(&mut s) as usize) & (len - 1) & !tbit };
            let m = [[[entries[0], entries[1]], [entries[2], entries[3]]], [[entries[4], entries[5]], [entries[6], entries[7]]]];
            let w = lanes::GateWords { m: entries.map(|e| e as u32), tbit: tbit as u32, ctrl: ctrl as u32 };
            let (mut a, mut b) = (state.clone(), state.clone());
            let fits = lanes::apply_words(&mut a, &w).unwrap();
            lanes::apply(&mut b, target, ctrl, m);
            assert_eq!(a, b, "case {case}");
            let mut want = true;
            for i in (0..len).filter(|i| i & tbit == 0 && i & ctrl == ctrl) {
                let (a0, a1) = (state[i], state[i | tbit]);
                for [p, q] in m {
                    let re = fx(p[0], a0[0]) - fx(p[1], a0[1]) + fx(q[0], a1[0]) - fx(q[1], a1[1]);
                    let im = fx(p[0], a0[1]) + fx(p[1], a0[0]) + fx(q[0], a1[1]) + fx(q[1], a1[0]);
                    want &= i32::try_from(re).is_ok() && i32::try_from(im).is_ok();
                }
            }
            assert_eq!(fits, want, "case {case}");
            if fits { inside += 1 } else { outside += 1 }
        }
        assert!(inside >= 100 && outside >= 100, "{inside} inside, {outside} outside");
    }

    #[test]
    fn malformed_words_are_refused() {
        let mut s = 5u64;
        let state: Vec<lanes::Lane> = (0..8).map(|_| [next(&mut s) as i32, next(&mut s) as i32]).collect();
        let good = lanes::GateWords { m: [ONE as u32, 0, 0, 0, 0, 0, ONE as u32, 0], tbit: 2, ctrl: 1 };
        let mut a = state.clone();
        assert_eq!(lanes::apply_words(&mut a, &good), Some(true));
        assert_eq!(a, state);
        // tbit 0, 3 and 8; ctrl sharing tbit; ctrl at or above the length.
        for (tbit, ctrl) in [(0, 0), (3, 0), (8, 0), (2, 2), (2, 3), (1, 8), (4, 9)] {
            let mut a = state.clone();
            assert_eq!(lanes::apply_words(&mut a, &lanes::GateWords { tbit, ctrl, ..good }), None, "tbit {tbit} ctrl {ctrl}");
            assert_eq!(a, state);
        }
        // A state that is not a power of two of at least two lanes.
        for len in [0, 1, 3, 6] {
            let mut a = vec![[1, 2]; len];
            assert_eq!(lanes::apply_words(&mut a, &lanes::GateWords { tbit: 1, ctrl: 0, ..good }), None);
            assert_eq!(a, vec![[1, 2]; len]);
        }
        assert_eq!(lanes::run_words(&state, &[good, lanes::GateWords { tbit: 8, ..good }]), None);
    }

    #[test]
    fn z_on_the_most_negative_lane_is_flagged() {
        let gate = |base| Gate { base, controls: vec![], target: 0, param: 0 };
        for gs in Gateset::ALL {
            let (z, i) = (lanes::gate_words(&gate(BaseGate::Z), gs), lanes::gate_words(&gate(BaseGate::I), gs));
            let state = [[0, 0], [i32::MIN, 0]];
            let mut amps = state.to_vec();
            assert_eq!(lanes::apply_words(&mut amps, &z), Some(false));
            assert_eq!(amps, state);
            // The exact value is 2^31, one past the largest lane.
            assert_eq!(lanes::fxmul_wide(-(ONE as i32), i32::MIN), (0, 1 << 31));
            // A run names the first gate that left 32 bits.
            assert_eq!(lanes::run_words(&state, &[i, z, i]).unwrap().out_of_range, Some(1));
            assert_eq!(lanes::run_words(&state, &[z, i, z]).unwrap().out_of_range, Some(0));
            assert_eq!(lanes::run_words(&state, &[i, i]).unwrap(), plan::LaneRun { amps: state.to_vec(), out_of_range: None });
        }
    }

    #[test]
    fn simulate_checked_is_simulate() {
        for gs in Gateset::ALL {
            for c in (Corpus::Random { seed: 7, cases: 300 }).circuits(gs) {
                let dim = 1usize << c.n_qubits;
                for start in [0, 1, dim + 3] {
                    let run = lanes::simulate_checked(&c, start).unwrap();
                    assert_eq!(run.out_of_range, None);
                    assert_eq!(widened(&run.amps), native(&c, start));
                }
                assert_eq!(lanes::simulate_checked(&c, dim + 3), lanes::simulate_checked(&c, 3));
                // The same gates as words, from the same state.
                let mut basis = vec![[0, 0]; dim];
                basis[0] = [ONE as i32, 0];
                let words: Vec<lanes::GateWords> = c.ops.iter().map(|g| lanes::gate_words(g, gs)).collect();
                assert_eq!(lanes::run_words(&basis, &words), Some(lanes::simulate_checked(&c, 0).unwrap()));
            }
        }
    }

    #[test]
    fn a_rounded_product_is_never_negated() {
        let v2 = [[759250126, 0], [1, 0], [759250126, 0], [1, 0]];
        let v1 = [[759250122, 0], [0, 0], [759250122, 0], [0, 0]];
        for (gs, want) in [(Gateset::V2, v2), (Gateset::V1, v1)] {
            let mut c = Circuit::with_gateset(2, gs);
            c.h(0).h(1).h(0);
            assert_eq!(native(&c, 0), widened(&want));
            assert_eq!(lanes::simulate(&c).unwrap(), want);
            let run = lanes::simulate_checked(&c, 0).unwrap();
            assert_eq!((run.amps.as_slice(), run.out_of_range), (want.as_slice(), None));
            // H with `m11·a_j` computed as `−(m01·a_j)`: one rounded product,
            // negated, where the table rounds `−h·a_j` on its own.
            let h = gs.inv_sqrt2() as i32;
            let mut a = [[ONE as i32, 0], [0, 0], [0, 0], [0, 0]];
            for t in [0, 1, 0] {
                let bit = 1usize << t;
                for i in (0..4).filter(|i| i & bit == 0) {
                    let j = i | bit;
                    for k in 0..2 {
                        let (p, q) = (lanes::fxmul(h, a[i][k]), lanes::fxmul(h, a[j][k]));
                        (a[i][k], a[j][k]) = (p + q, p - q);
                    }
                }
            }
            match gs {
                // A tie: fx(h, h) = 2^29 exactly, and fx(h, 2^29) and
                // fx(−h, 2^29) differ by more than a sign.
                Gateset::V2 => {
                    assert_eq!((a[1][0], a[3][0]), (0, 0));
                    assert_ne!(a, want);
                }
                // An even h: no tie, the same bits either way.
                Gateset::V1 => assert_eq!(a, want),
            }
        }
    }

    #[test]
    fn the_guard_horizon_is_pinned() {
        assert_eq!((lanes::table_excess(Gateset::V1), lanes::table_excess(Gateset::V2)), (0, 386_868_465));
        for (n, v1, v2) in [(10, 11_863_283, 11_769_578), (20, 370_727, 370_635), (26, 46_340, 46_339)] {
            assert_eq!((lanes::horizon(n, Gateset::V1), lanes::horizon(n, Gateset::V2)), (v1, v2), "n = {n}");
        }
        for n in 1..=26 {
            assert!(lanes::horizon(n, Gateset::V1) >= lanes::horizon(n, Gateset::V2), "n = {n}");
            for gs in Gateset::ALL {
                assert!(lanes::horizon(n, gs) <= lanes::horizon(n - 1, gs), "{gs:?} n = {n}");
            }
        }
        // Rounding alone can carry a state of 57 qubits or more out of 32
        // bits in one gate.
        for gs in Gateset::ALL {
            assert_eq!((lanes::horizon(56, gs), lanes::horizon(57, gs), lanes::horizon(58, gs), lanes::horizon(u8::MAX, gs)), (1, 0, 0, 0));
        }
    }

    #[test]
    fn valid_circuits_stay_in_lanes() {
        for gs in Gateset::ALL {
            for c in (Corpus::Random { seed: 7, cases: 1000 }).circuits(gs) {
                assert_eq!(lanes::simulate_checked(&c, 0).unwrap().out_of_range, None);
            }
            for n in 1..=16 {
                let mut c = Circuit::qft(n);
                c.gateset = gs;
                assert_eq!(lanes::simulate_checked(&c, 0).unwrap().out_of_range, None, "qft({n}) {gs:?}");
            }
            // A long run of H, T and P(3..=32) on four qubits.
            let mut c = Circuit::with_gateset(4, gs);
            let mut s = 21u64;
            for _ in 0..10_000 {
                let q = (next(&mut s) % 4) as u8;
                match next(&mut s) % 3 {
                    0 => c.h(q),
                    1 => c.t(q),
                    _ => c.p(3 + (next(&mut s) % 30) as u16, q),
                };
            }
            assert!(c.ops.len() as u64 <= lanes::horizon(4, gs));
            let run = lanes::simulate_checked(&c, 0).unwrap();
            assert_eq!(run.out_of_range, None, "{gs:?}");
            assert_eq!(widened(&run.amps), native(&c, 0), "{gs:?}");
        }
    }

    #[test]
    fn fabric_corpus_starts_with_random_v1() {
        let random_v1 = Corpus::Random { seed: 7, cases: 200 };
        assert_eq!((FABRIC_DEFAULT.name(), random_v1.name()), ("fabric-v1", "random-v1"));
        for (gs, pin) in [(Gateset::V1, "d18454c639acfd9c7b66450f4ded1aac4ab46cc10a7bedbcf4958a96e204fb36"), (Gateset::V2, "3dbde276c1095bf827faec71d5980e050f8a55a5ba7d97cd3bbdaec3f43a13b2")] {
            let fabric = FABRIC_DEFAULT.circuits(gs);
            assert_eq!(fabric.len(), 224);
            assert_eq!(fabric[..200], random_v1.circuits(gs)[..]);
            // One stream: random-v1's circuits, then the wide ones after them.
            let mut s = 7u64;
            for c in &fabric[..200] {
                assert_eq!(*c, lanes::random_circuit(&mut s, gs));
            }
            for c in &fabric[200..] {
                assert_eq!(*c, lanes::random_wide_circuit(&mut s, gs));
                assert!((11..=17).contains(&c.n_qubits), "{}", c.n_qubits);
            }
            let cert = lanes::certify_corpus(gs, "local/test", random_v1);
            assert_eq!(hex(&cert.corpus), pin);
            assert_eq!(cert.generator, format!("{} seed=7 cases=200", random_generator(gs)));
            assert_eq!(cert, certify_lanes(gs, "local/test", 200, 7));
        }
    }

    /// The fabric-v1 corpus of each gateset, seed 7, 200 + 24 cases. The
    /// digests were computed by this test's first run, when the corpus was
    /// introduced; they must never be edited to make this test pass.
    #[test]
    fn the_fabric_v1_corpus_of_each_gateset_is_pinned() {
        for (gs, pin) in [(Gateset::V1, "41c726a0ac80f7defef92e15ecf893bdb7a3076b5e7f670fa0b7142e5c033df7"), (Gateset::V2, "9a84b55af68f1a8b07390b234cf562dd8d85cef3185a697ab85690c8790a7809")] {
            let cert = lanes::certify_corpus(gs, "local/test", FABRIC_DEFAULT);
            assert_eq!(cert.parity, Parity::BitExact, "{cert:?}");
            assert_eq!(cert.cases, 224);
            assert_eq!(cert.generator, format!("{} seed=7 cases=200 wide=24", fabric_generator(gs)));
            assert_eq!(hex(&cert.corpus), pin, "{gs:?}");
        }
    }

    /// With 64 invocations to a workgroup, one per amplitude pair, and at most
    /// 64 workgroups to a row: up to 6 qubits fill part of one workgroup, 7 to
    /// 13 one row, and 14 or more a grid (`wgsl::tests::grids_cover_every_item_once`
    /// checks these bounds against `wgsl::gate_grid`). If a count is ever zero
    /// for the fixed seed, the corpus gains wide circuits; the assertion is
    /// never relaxed.
    #[test]
    fn fabric_v1_covers_every_dispatch_shape() {
        for gs in Gateset::ALL {
            let cs = FABRIC_DEFAULT.circuits(gs);
            let circuits = |f: &dyn Fn(&Circuit) -> bool| cs.iter().filter(|c| f(c)).count();
            let ops = |f: &dyn Fn(&Gate) -> bool| cs.iter().flat_map(|c| &c.ops).filter(|g| f(g)).count();
            let shapes = [
                ("circuit on at most 6 qubits", circuits(&|c| c.n_qubits <= 6)),
                ("circuit on 7 to 13 qubits", circuits(&|c| (7..=13).contains(&c.n_qubits))),
                ("circuit on 14 qubits or more", circuits(&|c| c.n_qubits >= 14)),
                ("op with a control", ops(&|g| !g.controls.is_empty())),
                ("op with two controls or more", ops(&|g| g.controls.len() >= 2)),
                ("op on a target of 10 or more", ops(&|g| g.target >= 10)),
                ("P(k) with k of 19 or more", ops(&|g| g.base == BaseGate::P && g.param >= 19)),
            ];
            for (what, count) in shapes {
                assert!(count > 0, "{gs:?}: no {what}");
            }
        }
    }

    #[test]
    fn gate_words_are_the_table() {
        use BaseGate::*;
        let gates = [I, X, Y, Z, H, S, Sdg, T, Tdg].map(|b| (b, 0u16)).into_iter().chain((1..=32).map(|k| (P, k)));
        for gs in Gateset::ALL {
            for (base, param) in gates.clone() {
                for (target, controls) in [(0u8, vec![]), (3, vec![0, 5]), (25, vec![24, 1, 7])] {
                    let g = Gate { base, controls: controls.clone(), target, param };
                    let w = lanes::gate_words(&g, gs);
                    let m = base.matrix(param, gs);
                    let table: Vec<i64> = [m[0][0], m[0][1], m[1][0], m[1][1]].iter().flat_map(|a| [a.re, a.im]).collect();
                    assert_eq!(w.m.map(|x| i64::from(x as i32)).to_vec(), table, "{base:?}({param}) {gs:?}");
                    assert_eq!(w.m.to_vec(), table.iter().map(|&e| e as i32 as u32).collect::<Vec<_>>());
                    assert_eq!(w.tbit, 1 << target);
                    assert_eq!(w.ctrl, controls.iter().fold(0u32, |acc, &c| acc | 1 << c));
                }
            }
        }
        // A circuit/1 gate may repeat a control: one bit.
        let c = Circuit { n_qubits: 2, ops: vec![Gate { base: X, controls: vec![0, 0], target: 1, param: 0 }], gateset: Gateset::V1 };
        c.validate().unwrap();
        assert_eq!(lanes::gate_words(&c.ops[0], Gateset::V1).ctrl, 1);
    }
}