rhdl_ed25519_scalable_core/

config.rs

//! The planner: predicts throughput and resources for every profile and
//! picks one from a LUT and DSP budget.
//!
//! A [`Profile`] is `fb/sha/sc` plus `fused`; written as four numbers
//! (`15/11/3/1`) the last one is 1 for one batch-compress machine and 0 for
//! fused mode, the same order as `ED25519_SCALABLE_PROFILE`. Budgets ([`Budget`]) are
//! percentages of the project caps: [`LUT_CAP`] (260,000; up to 200 %) and
//! [`DSP_CAP`] (7,000; up to the U280's 9,024). The planner reports the
//! smallest LUT percentage that still gives a working signer
//! ([`min_lut_percent`]) and the DSP percentage beyond which more DSPs do not
//! help ([`useful_dsp_percent`]).
//!
//! # Throughput model
//!
//! [`Profile::cycles_per_sign`] is the slowest of these stages:
//!
//! | Stage | Cycles per signature | 15/11/3/1 |
//! |---|---|---:|
//! | fixed-base machines | `FB_BUNDLES / fb / UTIL_MACHINE` (fused: plus the SHA term) | 26.94 |
//! | SHA-512 rings | `3 · 81 / sha / UTIL_SHA` | 24.93 |
//! | scalar rings | `2 · 32 / sc / UTIL_RING` | 23.70 |
//! | batch compression | `CP_BUNDLES / CP_BATCH / UTIL_MACHINE` | 13.63 |
//! | compress credits | `(FB_BUNDLES·32 + CP_BUNDLES·CP_CONTEXTS + CREDIT_OVERHEAD) / 2048` | 23.25 |
//! | admission | 2 | 2.00 |
//!
//! The utilizations are conservative (the fixed-base machines measured
//! 0.99–0.997); [`CREDIT_OVERHEAD`] is fitted to measured runs. 15/11/3/1
//! measured 26.43 against the predicted 26.94.
//!
//! # Resource model
//!
//! [`yosys_calibrated`] uses Yosys leaf maps (in `mapping/`) plus structural
//! adjustments for blocks not yet mapped; [`structural`] is a hand estimate.
//! DSPs trade for LUTs the way Vivado does under `synth_design -max_dsp`: a
//! multiply tile without a DSP becomes fabric, and spare DSPs absorb wide
//! adders (`USE_DSP`).
//!
//! **The largest uncertainty**: about 8,600 of each multiplier's LUTs are
//! its 225 chain additions `P = PCIN + A·B`. Yosys packs that pattern into
//! DSPs for 7-series but not UltraScale+; Vivado infers such cascades.
//! [`calibrated`] assumes packing (15/11/3/1 ≈ 219k LUT); with
//! `yosys_calibrated(false)` it would not fit 260k. Only Vivado settles it.
//!
//! **Every resource number here is an estimate**, and the clock
//! ([`DESIGN_MHZ`]) is a target until routed.
//!
//! # Using it
//!
//! ```text
//! cargo run --release --bin ed25519_plan -- --lut 100 --dsp 100 --mhz 205
//! cargo run --release --bin ed25519_plan -- --lut 100 --dsp 100 --target 7000000
//! cargo run --release --bin ed25519_plan -- --sweep
//! cargo run --release --bin ed25519_plan -- --lut 100 --dsp 100 --out plans/s100
//! cargo tuner-ed25519        # at the repository root: the planner TUI, Ed25519 only
//! ```
//!
//! `--out` writes the plan, its `ED25519_SCALABLE_PROFILE` value and a
//! Vivado `synth.tcl` that rejects an over-budget result. The fast way to
//! iterate on the model is `tools/hostmodel` (no hardware build).

use std::fmt::Write as _;

/// Project LUT cap (100 %), in LUTs. A project budget, well below the
/// device's [`DEVICE_LUT`].
pub const LUT_CAP: u32 = 260_000;
/// Project DSP cap (100 %), in DSP48E2 blocks. Below the device's
/// [`DEVICE_DSP`], so DSP percentages may exceed 100 (up to ~128.9 %).
pub const DSP_CAP: u32 = 7_000;
/// Physical DSP48E2 count of the xcu280 (device data sheet). Hard ceiling
/// on any DSP budget.
pub const DEVICE_DSP: u32 = 9_024;
/// Design clock in MHz (the project's target frequency, not yet a routed
/// result). Used to turn cycles per signature into signatures per second.
pub const DESIGN_MHZ: f64 = 205.0;
/// Physical BRAM36 count of the xcu280. [`plan`] rejects profiles above it;
/// there is no separate project BRAM cap.
pub const DEVICE_BRAM36: u32 = 2_016;
/// Physical LUT count of the xcu280 (for reference; budgets use
/// [`LUT_CAP`]).
pub const DEVICE_LUT: u32 = 1_303_680;

/// One block's resources, per instance. [`Profile::estimate`] multiplies
/// each row by the instance count and then trades DSPs for LUTs using
/// `tiles`/`lut_per_tile` and `adder_dsps`/`lut_per_adder_dsp`.
#[derive(Clone, Copy, Debug, Default, PartialEq)]
pub struct BlockCost {
    /// Fabric LUTs with every multiply tile in a DSP and adders in fabric
    /// (the baseline before any DSP trade).
    pub lut: u32,
    /// Flip-flops. Not traded against DSPs.
    pub ff: u32,
    /// DSP-mappable multiply tiles (17 x 22 or smaller). Each tile uses one
    /// DSP48E2 when DSPs are available.
    pub tiles: u32,
    /// LUTs one tile costs when mapped to fabric instead of a DSP
    /// (structural estimate in both tables).
    pub lut_per_tile: u32,
    /// Wide fabric adders that `USE_DSP` could move into DSPs, counted in
    /// DSPs they would occupy. Only spare DSPs (after tiles) take them.
    pub adder_dsps: u32,
    /// LUTs saved per DSP when those adders move (structural estimate).
    pub lut_per_adder_dsp: u32,
    /// BRAM36 primitives (BRAM18s rounded into BRAM36 equivalents).
    pub bram36: u32,
}

/// Per-block costs used by [`Profile::estimate`]. Built either by
/// [`structural`] (hand estimate) or [`yosys_calibrated`] (Yosys leaf maps
/// plus structural adjustments); replace rows with Vivado measurements as
/// they become available.
#[derive(Clone, Copy, Debug)]
pub struct CostTable {
    /// Fixed-base field machine (multiplier, adder, scanner, banks). One per
    /// `Profile::fb`.
    pub fb_machine: BlockCost,
    /// Batch-compress field machine (64 contexts of 32 points). Zero or one
    /// instance (none in fused mode).
    pub cp_machine: BlockCost,
    /// Interleaved SHA-512 ring. One per `Profile::sha`.
    pub sha_ring: BlockCost,
    /// Digit-serial scalar ring. One per `Profile::sc`.
    pub scalar_ring: BlockCost,
    /// Controller base cost (admission, contexts, routing between blocks),
    /// one instance.
    pub controller: BlockCost,
    /// Extra controller LUTs per fixed-base machine (arbitration, masks).
    pub controller_lut_per_fb: u32,
    /// Where these numbers came from; printed in every report so an estimate
    /// is never mistaken for a measurement.
    pub source: &'static str,
}

/// The built-in structural estimate: hand-counted from the block structure,
/// never synthesized. The crate's unit tests use it because it does not
/// depend on mapping results.
pub fn structural() -> CostTable {
    CostTable {
        fb_machine: BlockCost {
            lut: 9_000,
            ff: 22_000,
            tiles: 225,
            lut_per_tile: 265,
            adder_dsps: 30,
            lut_per_adder_dsp: 40,
            bram36: 75,
        },
        cp_machine: BlockCost {
            lut: 7_000,
            ff: 20_000,
            tiles: 225,
            lut_per_tile: 265,
            adder_dsps: 18,
            lut_per_adder_dsp: 40,
            bram36: 360,
        },
        sha_ring: BlockCost {
            lut: 3_000,
            ff: 7_000,
            tiles: 0,
            lut_per_tile: 0,
            adder_dsps: 38,
            lut_per_adder_dsp: 32,
            bram36: 0,
        },
        scalar_ring: BlockCost {
            lut: 3_000,
            ff: 11_000,
            tiles: 23,
            lut_per_tile: 300,
            adder_dsps: 12,
            lut_per_adder_dsp: 40,
            bram36: 0,
        },
        controller: BlockCost {
            lut: 7_000,
            ff: 9_000,
            tiles: 0,
            lut_per_tile: 0,
            adder_dsps: 0,
            lut_per_adder_dsp: 0,
            bram36: 80,
        },
        controller_lut_per_fb: 300,
        source: "structural estimate (unsynthesized)",
    }
}

/// Leaf costs from Yosys 0.55 `synth_xilinx -family xcup` maps of the
/// generated netlists (`mapping`), with `packed` selecting
/// whether the multiplier's 225 column-chain additions are absorbed into the
/// DSP48E2 post-adders (`P = PCIN + A*B`).
///
/// Yosys 0.55 does not pack those additions for UltraScale+ (it does for
/// 7-series, and Vivado infers such MACC cascades), so `packed = false` is
/// the raw Yosys count and `packed = true` subtracts the 8,600 LUTs and
/// 9,675 FFs of those adders and accumulator registers. Neither is Vivado
/// utilization. The controller has not been mapped separately; its row stays
/// a structural estimate.
pub fn yosys_calibrated(packed: bool) -> CostTable {
    // LUTs and FFs of the multiplier's chain adders and their accumulator
    // registers (from the Yosys map); subtracted from both field machines
    // when the post-adders are assumed packed into DSPs.
    let (mul_adder_lut, mul_adder_ff) = if packed { (8_600, 9_675) } else { (0, 0) };
    CostTable {
        // Yosys map: 17,805 LUT + 133 RAM32M16 (8 LUTs each) + 28,053 FF, 225 DSP,
        // 70 BRAM36 + 3 BRAM18 (counted as 72 BRAM36),
        // plus ~500 LUT for the second bank-L slot and wider scan fields (structural).
        fb_machine: BlockCost {
            lut: 19_370 - mul_adder_lut,
            ff: 28_053 - mul_adder_ff,
            tiles: 225,
            lut_per_tile: 265,
            adder_dsps: 30,
            lut_per_adder_dsp: 40,
            bram36: 72,
        },
        // Not mapped yet: fixed-base machine without the scanner's table,
        // 64 contexts, banks M and I 2^12 / 2^13 deep (structural adjustment).
        cp_machine: BlockCost {
            lut: 17_500 - mul_adder_lut,
            ff: 27_000 - mul_adder_ff,
            tiles: 225,
            lut_per_tile: 265,
            adder_dsps: 18,
            lut_per_adder_dsp: 40,
            bram36: 340,
        },
        // Yosys map: 4,577 LUT, 7,263 FF.
        sha_ring: BlockCost {
            lut: 4_577,
            ff: 7_263,
            tiles: 0,
            lut_per_tile: 0,
            adder_dsps: 38,
            lut_per_adder_dsp: 32,
            bram36: 0,
        },
        // Yosys map: 4,285 LUT, 14,550 FF, 23 DSP.
        scalar_ring: BlockCost {
            lut: 4_285,
            ff: 14_550,
            tiles: 23,
            lut_per_tile: 300,
            adder_dsps: 12,
            lut_per_adder_dsp: 40,
            bram36: 0,
        },
        // Not mapped: structural estimate, larger than `structural()`'s.
        controller: BlockCost {
            lut: 12_000,
            ff: 11_000,
            tiles: 0,
            lut_per_tile: 0,
            adder_dsps: 0,
            lut_per_adder_dsp: 0,
            bram36: 90,
        },
        controller_lut_per_fb: 400,
        source: if packed {
            "Yosys xcup leaf map, DSP post-adders packed (Vivado-like); controller structural"
        } else {
            "raw Yosys xcup leaf map (post-adders in fabric); controller structural"
        },
    }
}

/// The planner's default cost table: [`yosys_calibrated`] with packed
/// post-adders. Use `yosys_calibrated(false)` for the pessimistic bound.
pub fn calibrated() -> CostTable {
    yosys_calibrated(true)
}

/// Bundles (issue slots) in the fixed-base program, from the microcode
/// compiler (see `programs`). Each bundle occupies one machine slot, so this
/// is the machine time per signature in cycles at full utilization.
pub const FB_BUNDLES: u32 = 392;
/// Bundles of the fused fixed-base + per-point inversion program (compiler
/// output). Used instead of [`FB_BUNDLES`] in fused mode.
pub const FUSED_BUNDLES: u32 = 657;
/// Bundles of one 32-point batch compression (compiler output); shared by
/// the [`CP_BATCH`] points of the batch.
pub const CP_BUNDLES: u32 = 423;
/// Points per compression batch (one batch inversion amortized over them).
pub const CP_BATCH: u32 = 32;
/// Batch-compress machine contexts (barrel slots, each holding one batch).
pub const CP_CONTEXTS: u32 = 64;
/// Sign contexts (requests in flight). Caps the compress credit pool.
pub const SIGN_CONTEXTS: u32 = 2048;
/// Credit hold time in cycles beyond the two programs' issue latency
/// (queueing, batch filling, hashing). Calibrated from native simulation: with 1,024
/// credits, 12/6/2/1 and 13/8/2/1 measured 45.7 and 44.1 cycles/signature,
/// i.e. ~45k cycles per credit against 15.7k + 22.0k of issue latency for
/// the programs of that time (492 fixed-base bundles, the older compress
/// machine). With today's programs the issue latency in the formula is
/// `FB_BUNDLES·32 + CP_BUNDLES·CP_CONTEXTS` = 12,544 + 27,072 cycles.
/// Rechecked 2026-10-19 on fix13 8,0,2,1: 1,026 signatures in flight at
/// 46.46 cycles/signature is a mean hold of ~47.7k cycles, i.e. 39.6k + 8.1k.
pub const CREDIT_OVERHEAD: f64 = 8_000.0;

/// Sustainable utilization of a SHA-512 ring, as a fraction of its ideal
/// rate (conservative simulation fit, see `cycles_per_sign`).
pub const UTIL_SHA: f64 = 0.886;
/// Sustainable utilization of a barrel field machine (0.997 measured in
/// simulation; 0.97 kept as margin). Planned builds on the shared SHA line
/// (native simulation, 2026-10-16): 9,0,2,1 ran 41.83 cycles/signature on a
/// full line (effective utilization 1.04; this model says 44.90), 44.76 on
/// a fold10 line (0.97) and 4,0,1,1 96.18 on fold4 (1.02; model 101.03), so
/// the margin covers the slowest measured line.
pub const UTIL_MACHINE: f64 = 0.97;
/// Assumed sustainable utilization of a scalar ring (not measured).
pub const UTIL_RING: f64 = 0.9;

/// A buildable signer profile: how many of each replicated block the
/// signer instantiates. [`Profile::env_value`] turns it into the
/// `ED25519_SCALABLE_PROFILE` string that `build.rs` reads.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Profile {
    /// Fixed-base machines (each a 32-context barrel field machine).
    pub fb: u32,
    /// SHA-512 rings (nonce and challenge hashing).
    pub sha: u32,
    /// Scalar rings (the mod-L scalar jobs).
    pub sc: u32,
    /// No compress machine; each fixed-base program inverts its own point.
    /// Saves the compress machine's area at the cost of a longer fixed-base
    /// program ([`FUSED_BUNDLES`]).
    pub fused: bool,
}

/// Resource and throughput estimate of a profile under a DSP limit, as
/// returned by [`Profile::estimate`]. All values are model output, not
/// measurements.
#[derive(Clone, Debug)]
pub struct Estimate {
    /// The profile being estimated.
    pub profile: Profile,
    /// Estimated LUTs, after the DSP/LUT trade.
    pub lut: u32,
    /// Estimated FFs.
    pub ff: u32,
    /// Estimated DSPs used (tiles first, then adders), at most `max_dsp`.
    pub dsp: u32,
    /// Estimated BRAM36.
    pub bram36: u32,
    /// DSP limit passed to synthesis (`synth_design -max_dsp`).
    pub max_dsp: u32,
    /// Whether adders should be pushed into DSPs (`USE_DSP`); true when any
    /// adder DSPs were assigned.
    pub adders_in_dsp: bool,
    /// Steady-state cycles per signature (slowest stage of the cycle model).
    pub cycles_per_sign: f64,
    /// Name of the limiting stage.
    pub bottleneck: &'static str,
    /// Signatures per second at the assumed clock (`mhz · 1e6 /
    /// cycles_per_sign`), a projection.
    pub signs_per_sec: f64,
}

/// Cycle model, build string and resource estimate of a profile.
impl Profile {
    /// Steady-state cycles per signature and the limiting stage.
    ///
    /// Each stage's cost is its per-signature service time divided by its
    /// instance count and sustainable utilization; the pipeline runs at the
    /// rate of the slowest stage, so the maximum is returned.
    pub fn cycles_per_sign(&self) -> (f64, &'static str) {
        // Fused mode runs the longer program that also inverts the point.
        let fb_bundles = if self.fused { FUSED_BUNDLES } else { FB_BUNDLES };
        // Ideal service time per signature divided by the sustainable
        // utilization. The SHA factor was fitted to 12/6/2/1 (45.7 measured
        // against an ideal 40.5), a run later found to be credit-limited, so
        // it is conservative; 13/8/2/1 measured 37.97 against the fixed-base
        // ideal 37.85 (utilization 0.997, modeled as 0.97).
        // Three blocks per signature, ~81 cycles per block per ring.
        let sha = 3.0 * 81.0 / self.sha as f64 / UTIL_SHA;
        // One bundle per machine cycle, machines work in parallel.
        let fb = fb_bundles as f64 / self.fb as f64 / UTIL_MACHINE;
        let mut stages = vec![
            // In fused mode a request's admission credit is a fixed-base
            // context, held from admission through hashing, so SHA time adds
            // to the context's occupancy instead of overlapping it (1/1/1/0
            // measured ~1,000 cycles/signature against this model's 1,055).
            if self.fused {
                (fb + sha, "fixed-base contexts (credit held through SHA)")
            } else {
                (fb, "fixed-base machines")
            },
            (sha, "SHA-512 rings"),
            // Two 31-step jobs per signature, one step per cycle per ring
            // (modeled as 32 cycles each).
            (2.0 * 32.0 / self.sc as f64 / UTIL_RING, "scalar rings"),
            // Free-context FIFO and SHA dispatch admit one request per 2 cycles.
            (2.0, "admission"),
        ];
        if !self.fused {
            // Little's law: a compress-slot credit is held from admission
            // until its batch retires. Hold time in cycles = fixed-base
            // program latency on a 32-context barrel (one bundle every 32
            // cycles) + compress program latency on a 64-context barrel +
            // the fitted overhead.
            let hold = (FB_BUNDLES * 32 + CP_BUNDLES * CP_CONTEXTS) as f64 + CREDIT_OVERHEAD;
            // Credits = compress slots (64 x 32 = 2,048), capped by the sign
            // contexts. Rate = credits / hold, so cycles per signature =
            // hold / credits.
            let credits = (CP_CONTEXTS * CP_BATCH).min(SIGN_CONTEXTS) as f64;
            stages.push((hold / credits, "compress credits (latency x rate)"));
            // One compress program serves a whole batch of CP_BATCH points.
            stages.push((
                CP_BUNDLES as f64 / CP_BATCH as f64 / UTIL_MACHINE,
                "batch compression",
            ));
        }
        // The slowest stage limits throughput.
        stages
            .into_iter()
            .fold((0.0, "none"), |a, b| if b.0 > a.0 { b } else { a })
    }

    /// Compile-time profile string understood by `build.rs`:
    /// `"fb,sha,sc,compress"` with compress 1 for a batch-compress machine and
    /// 0 for fused mode.
    pub fn env_value(&self) -> String {
        format!(
            "{},{},{},{}",
            self.fb,
            self.sha,
            self.sc,
            if self.fused { 0 } else { 1 }
        )
    }

    /// Estimate resources under `max_dsp` DSPs with `table` block costs, and
    /// project throughput at `mhz` MHz.
    ///
    /// DSPs go where they save the most fabric: multiply tiles first, kinds
    /// in decreasing `lut_per_tile` (any tile without a DSP costs that many
    /// LUTs), then wide adders in decreasing `lut_per_adder_dsp`. Within a
    /// kind, instances are filled one after another, so a short budget
    /// leaves whole later instances in fabric, as a `-max_dsp` cap does.
    pub fn estimate(&self, table: &CostTable, max_dsp: u32, mhz: f64) -> Estimate {
        // Number of compress machines: none in fused mode.
        let cp = if self.fused { 0 } else { 1 };
        // (per-instance cost, instance count) for every block kind.
        let blocks: [(BlockCost, u32); 5] = [
            (table.fb_machine, self.fb),
            (table.cp_machine, cp),
            (table.sha_ring, self.sha),
            (table.scalar_ring, self.sc),
            (table.controller, 1),
        ];
        // Controller growth per fixed-base machine (arbitration, masks).
        let mut lut = table.controller_lut_per_fb * self.fb;
        let mut ff = 0;
        let mut bram = 0;
        // LUTs of tiles that did not get a DSP.
        let mut fabric_tile_lut = 0u64;
        // Baseline totals with all tiles in DSPs and adders in fabric.
        for (b, n) in blocks {
            lut += b.lut * n;
            ff += b.ff * n;
            bram += b.bram36 * n;
        }
        // Tiles take DSPs first, the kinds that lose the most LUTs per tile
        // first; a short budget leaves the least costly tiles in fabric.
        let mut by_tile = blocks;
        by_tile.sort_by(|a, b| b.0.lut_per_tile.cmp(&a.0.lut_per_tile));
        let mut dsp_left = max_dsp;
        let mut dsp = 0;
        for (b, n) in by_tile {
            for _ in 0..n {
                let in_dsp = b.tiles.min(dsp_left);
                dsp_left -= in_dsp;
                dsp += in_dsp;
                fabric_tile_lut += u64::from((b.tiles - in_dsp) * b.lut_per_tile);
            }
        }
        lut += fabric_tile_lut as u32;
        // Spare DSPs absorb wide adders, the largest savings per DSP first.
        let mut by_adder = blocks;
        by_adder.sort_by(|a, b| b.0.lut_per_adder_dsp.cmp(&a.0.lut_per_adder_dsp));
        let mut adders_in_dsp = false;
        for (b, n) in by_adder {
            for _ in 0..n {
                let moved = b.adder_dsps.min(dsp_left);
                if moved > 0 {
                    adders_in_dsp = true;
                }
                dsp_left -= moved;
                dsp += moved;
                lut = lut.saturating_sub(moved * b.lut_per_adder_dsp);
            }
        }
        let (cycles, bottleneck) = self.cycles_per_sign();
        Estimate {
            profile: *self,
            lut,
            ff,
            dsp,
            // The compress machine's BRAM is in the `cp_machine` row (count 0
            // when fused).
            bram36: bram,
            max_dsp,
            adders_in_dsp,
            cycles_per_sign: cycles,
            bottleneck,
            signs_per_sec: mhz * 1e6 / cycles,
        }
    }
}

/// Planner request: resource allowances and the clock to project at.
#[derive(Clone, Copy, Debug)]
pub struct Budget {
    /// LUT allowance, percent of [`LUT_CAP`] (0..=200).
    pub lut_percent: f64,
    /// DSP allowance, percent of [`DSP_CAP`] (0..=DEVICE_DSP/DSP_CAP).
    pub dsp_percent: f64,
    /// Assumed clock in MHz, for projection only (does not affect which
    /// profiles fit).
    pub mhz: f64,
    /// Stop growing once this rate is reached, in signatures per second
    /// (0 = maximize). Rates above it count as equal, so the smallest
    /// profile reaching it wins.
    pub target_sps: f64,
}

/// Conversion of the percentage sliders into absolute limits.
impl Budget {
    /// LUT limit in LUTs (rounded down).
    pub fn luts(&self) -> u32 {
        (LUT_CAP as f64 * self.lut_percent / 100.0).floor() as u32
    }
    /// DSP limit in DSPs (rounded down), never above the device.
    pub fn dsps(&self) -> u32 {
        ((DSP_CAP as f64 * self.dsp_percent / 100.0).floor() as u32).min(DEVICE_DSP)
    }
}

/// Every profile the planner considers: 1..=40 fixed-base machines,
/// 1..=24 SHA rings, 1..=6 scalar rings, with and without fusing (the same
/// ranges as [`crate::frontier`]). The search is exhaustive, so these
/// ranges bound what the planner can return; at 200 % of the LUT cap the
/// best profile stays well inside them.
pub fn candidates() -> Vec<Profile> {
    let mut out = Vec::new();
    for fb in 1..=40 {
        for sha in 1..=24 {
            for sc in 1..=6 {
                for fused in [false, true] {
                    // Fusing only pays off while one compress machine would idle.
                    if fused && fb > 4 {
                        continue;
                    }
                    out.push(Profile { fb, sha, sc, fused });
                }
            }
        }
    }
    out
}

/// Best profile for a budget: highest rate (capped at the target), then
/// fewest LUTs, then fewest DSPs. `None` when nothing fits. A profile fits
/// when its LUTs, DSPs and BRAM36 are within the budget and the device.
pub fn plan(budget: &Budget, table: &CostTable) -> Option<Estimate> {
    let luts = budget.luts();
    let dsps = budget.dsps();
    let mut best: Option<Estimate> = None;
    for p in candidates() {
        let e = p.estimate(table, dsps, budget.mhz);
        if e.lut > luts || e.dsp > dsps || e.bram36 > DEVICE_BRAM36 {
            continue;
        }
        // With a target, every rate at or above it compares equal, so the
        // tie-break (fewer LUTs) picks the smallest profile that reaches it.
        let capped = |x: f64| {
            if budget.target_sps > 0.0 {
                x.min(budget.target_sps)
            } else {
                x
            }
        };
        let better = match &best {
            None => true,
            Some(b) => {
                // Rates within one part per million are a tie (float noise),
                // broken by fewer LUTs, then fewer DSPs.
                let (r, rb) = (capped(e.signs_per_sec), capped(b.signs_per_sec));
                r > rb * 1.000_001
                    || ((r - rb).abs() <= rb * 1e-6
                        && (e.lut < b.lut || (e.lut == b.lut && e.dsp < b.dsp)))
            }
        };
        if better {
            best = Some(e);
        }
    }
    best
}

/// Smallest LUT percentage at which some profile fits under `dsp_percent`
/// (the lower end of the LUT slider), counting only profiles whose BRAM
/// fits the device. Infinity if no candidate exists.
pub fn min_lut_percent(dsp_percent: f64, table: &CostTable) -> f64 {
    // Reuse Budget's DSP rounding and device clamp; the LUT field is unused.
    let dsps = Budget {
        lut_percent: 0.0,
        dsp_percent,
        mhz: DESIGN_MHZ,
        target_sps: 0.0,
    }
    .dsps();
    candidates()
        .iter()
        .map(|p| p.estimate(table, dsps, DESIGN_MHZ))
        .filter(|e| e.bram36 <= DEVICE_BRAM36)
        .map(|e| e.lut)
        .min()
        .map(|l| 100.0 * l as f64 / LUT_CAP as f64)
        .unwrap_or(f64::INFINITY)
}

/// DSP percentage above which no profile within 200 % LUTs uses more DSPs:
/// the DSP count of the best plan with the largest LUT and DSP allowances.
pub fn useful_dsp_percent(table: &CostTable) -> f64 {
    // Maximum sliders: 200 % LUTs and the whole device's DSPs.
    let budget = Budget {
        lut_percent: 200.0,
        dsp_percent: 100.0 * DEVICE_DSP as f64 / DSP_CAP as f64,
        mhz: DESIGN_MHZ,
        target_sps: 0.0,
    };
    plan(&budget, table)
        .map(|e| 100.0 * e.dsp as f64 / DSP_CAP as f64)
        .unwrap_or(0.0)
}

/// Human-readable report of a plan: profile, budget, resource estimate with
/// its source, cycle model and the synthesis settings to use.
pub fn describe(e: &Estimate, budget: &Budget, table: &CostTable) -> String {
    let mut s = String::new();
    let p = e.profile;
    let _ = writeln!(
        s,
        "profile: {} fixed-base machine(s), {} SHA-512 ring(s), {} scalar ring(s), {}",
        p.fb,
        p.sha,
        p.sc,
        if p.fused {
            "fused compression"
        } else {
            "one batch-compress machine"
        }
    );
    let _ = writeln!(
        s,
        "budget:  {} LUT ({:.0}% of {}), {} DSP ({:.0}% of {})",
        budget.luts(),
        budget.lut_percent,
        LUT_CAP,
        budget.dsps(),
        budget.dsp_percent,
        DSP_CAP
    );
    let _ = writeln!(
        s,
        "estimate: {} LUT, {} FF, {} DSP, {} BRAM36  [{}]",
        e.lut, e.ff, e.dsp, e.bram36, table.source
    );
    let _ = writeln!(
        s,
        "model:   {:.2} cycles/signature (limited by {}), {:.3} M signatures/s at an ASSUMED {} MHz",
        e.cycles_per_sign,
        e.bottleneck,
        e.signs_per_sec / 1e6,
        budget.mhz
    );
    let _ = writeln!(
        s,
        "synthesis: -max_dsp {}{}",
        e.max_dsp,
        if e.adders_in_dsp {
            ", USE_DSP=yes on adder-heavy hierarchies"
        } else {
            ""
        }
    );
    s
}

/// JSON record of a plan (`schema` `scalable-plan-1`). `status` is always
/// `estimate-unmeasured`; measured counts come from the `measured.json` that
/// [`synth_tcl`] writes.
pub fn plan_json(e: &Estimate, b: &Budget) -> String {
    let p = e.profile;
    format!(
        r#"{{
  "schema": "scalable-plan-1",
  "status": "estimate-unmeasured",
  "budget": {{"lut_percent": {}, "dsp_percent": {}, "lut_limit": {}, "dsp_limit": {}, "assumed_mhz": {}, "target_sps": {}}},
  "profile": {{"fixed_base_machines": {}, "sha_rings": {}, "scalar_rings": {}, "compress_machine": {}}},
  "env": "ED25519_SCALABLE_PROFILE={}",
  "estimate": {{"lut": {}, "ff": {}, "dsp": {}, "bram36": {}, "cycles_per_sign": {:.3}, "bottleneck": "{}", "projected_sps": {:.0}}},
  "synthesis": {{"max_dsp": {}, "adders_in_dsp": {}}}
}}
"#,
        b.lut_percent,
        b.dsp_percent,
        b.luts(),
        b.dsps(),
        b.mhz,
        b.target_sps,
        p.fb,
        p.sha,
        p.sc,
        !p.fused,
        p.env_value(),
        e.lut,
        e.ff,
        e.dsp,
        e.bram36,
        e.cycles_per_sign,
        e.bottleneck,
        e.signs_per_sec,
        e.max_dsp,
        e.adders_in_dsp
    )
}

/// Vivado out-of-context synthesis gate enforcing the plan's budget.
///
/// The script synthesizes the exported Verilog with `-max_dsp`, writes the
/// utilization reports and `measured.json`, and fails if the measured LUTs
/// or DSPs exceed the budget.
pub fn synth_tcl(e: &Estimate, b: &Budget) -> String {
    let p = e.profile;
    // Top module name used by `export::selected_signer_hdl`.
    let top = "scalable_sign_core";
    // File stem matching what `export_scalable` writes for this profile.
    let stem = format!(
        "scalable_sign_core_{}_{}_{}_{}",
        p.fb,
        p.sha,
        p.sc,
        u8::from(!p.fused)
    );
    // Only emit USE_DSP properties when the estimate assigned adder DSPs.
    let use_dsp = if e.adders_in_dsp {
        // Wide adders of the SHA rings and field add/sub units into DSP48E2s.
        "set_property USE_DSP yes [get_cells -quiet -hierarchical -filter {NAME =~ *sha*}]\n\
         set_property USE_DSP yes [get_cells -quiet -hierarchical -filter {NAME =~ *add*}]\n"
    } else {
        ""
    };
    format!(
        r#"# Generated by ed25519_plan. Hardware comes exclusively from RHDL.
# vivado -mode batch -source synth.tcl -tclargs /abs/path/generated/{stem}.v
set_param general.maxThreads 4
if {{$argc != 1}} {{ error "expected the generated {stem}.v" }}
read_verilog [lindex $argv 0]
read_xdc constraints.xdc
synth_design -rtl -top {top} -part xcu280-fsvh2892-2L-e -mode out_of_context
{use_dsp}synth_design -top {top} -part xcu280-fsvh2892-2L-e -mode out_of_context -max_dsp {dsp}
report_utilization -file utilization.rpt
report_timing_summary -file synthesis_timing.rpt
set u [report_utilization -return_string]
if {{![regexp -line {{^\|\s*(CLB|Slice) LUTs\*?\s*\|\s*([0-9]+)\s*\|}} $u _ _ luts]}} {{ error "cannot parse LUTs" }}
if {{![regexp -line {{^\|\s*(CLB|Slice) Registers\s*\|\s*([0-9]+)\s*\|}} $u _ _ ffs]}} {{ error "cannot parse registers" }}
set dsps [llength [get_cells -hier -filter {{REF_NAME =~ DSP*}}]]
set fd [open measured.json w]
puts $fd [format {{{{"profile":"{env}","dsp_limit":{dsp},"requested_mhz":{mhz},"luts":%d,"ffs":%d,"dsps":%d,"evidence":"Vivado OOC synthesis utilization.rpt"}}}} $luts $ffs $dsps]
close $fd
if {{$luts > {lut} || $dsps > {dsp}}} {{ error "budget exceeded: $luts LUT, $dsps DSP" }}
write_checkpoint -force synthesized.dcp
"#,
        stem = stem,
        top = top,
        use_dsp = use_dsp,
        dsp = e.max_dsp,
        lut = b.luts(),
        mhz = b.mhz,
        env = p.env_value()
    )
}

/// Write `plan.json`, `plan.txt`, `synth.tcl` and `constraints.xdc` to `dir`.
/// Nothing is launched; the files are inputs for a reserved synthesis host.
/// The XDC constrains the clock port to the budget's assumed clock (period
/// in ns = 1000 / MHz).
pub fn write_plan(
    dir: &std::path::Path,
    e: &Estimate,
    b: &Budget,
    table: &CostTable,
) -> std::io::Result<()> {
    std::fs::create_dir_all(dir)?;
    std::fs::write(dir.join("plan.json"), plan_json(e, b))?;
    std::fs::write(dir.join("plan.txt"), describe(e, b, table))?;
    std::fs::write(dir.join("synth.tcl"), synth_tcl(e, b))?;
    std::fs::write(
        dir.join("constraints.xdc"),
        format!(
            "create_clock -name core -period {:.6} [get_ports {{clock_reset[0]}}]\n",
            1000.0 / b.mhz
        ),
    )
}

/// Unit tests of the planner model. They use [`structural`] costs so they do
/// not change when mapping calibrations change.
#[cfg(test)]
mod tests {
    use super::*;

    /// The project goal is reachable on paper: at 100 % LUT and DSP and the
    /// design clock, some profile reaches 7 M signatures/s within the caps.
    #[test]
    fn seven_million_profile_fits_project_caps() {
        let table = structural();
        let budget = Budget {
            lut_percent: 100.0,
            dsp_percent: 100.0,
            mhz: DESIGN_MHZ,
            target_sps: 7.0e6,
        };
        let e = plan(&budget, &table).expect("a 7M/s profile within the caps");
        println!("{}", describe(&e, &budget, &table));
        assert!(e.signs_per_sec >= 7.0e6);
        assert!(e.lut <= LUT_CAP && e.dsp <= DSP_CAP);
    }

    /// With no DSPs at all some profile still fits within 200 % LUTs, and the
    /// plan uses zero DSPs and the fused (smallest) layout. This keeps the
    /// DSP slider's lower end meaningful.
    #[test]
    fn zero_dsp_still_has_a_functional_profile() {
        let table = structural();
        let min = min_lut_percent(0.0, &table);
        assert!(min.is_finite() && min <= 200.0, "min LUT% at 0 DSP: {min}");
        let budget = Budget {
            lut_percent: min.ceil(),
            dsp_percent: 0.0,
            mhz: DESIGN_MHZ,
            target_sps: 0.0,
        };
        let e = plan(&budget, &table).unwrap();
        assert_eq!(e.dsp, 0);
        assert!(e.profile.fused);
    }

    /// Raising the LUT allowance (20 % to 200 % in 10 % steps) never lowers
    /// the planned rate. The planner searches exhaustively, so a larger
    /// budget is a superset; a decrease would mean a broken comparison.
    #[test]
    fn more_lut_never_lowers_throughput() {
        let table = structural();
        let mut last = 0.0;
        for lut in (20..=200).step_by(10) {
            let b = Budget {
                lut_percent: lut as f64,
                dsp_percent: 100.0,
                mhz: DESIGN_MHZ,
                target_sps: 0.0,
            };
            if let Some(e) = plan(&b, &table) {
                assert!(e.signs_per_sec >= last);
                last = e.signs_per_sec;
            }
        }
    }
}