rhdl_dsig_scalable_core/sbox_placement.rs
1//! Where each AES S-box lives: LUTs, block RAM or UltraRAM.
2//!
3//! # Why this question matters
4//!
5//! The default chain hash, Haraka-512, is built from AES rounds. The heart
6//! of an AES round is the *S-box*: a fixed table that replaces each byte with
7//! another byte. Every chain lane needs hundreds of them, and a slice has
8//! three lanes ([`crate::slice_chain`]). Built from LUTs (the FPGA's small
9//! logic cells), S-boxes eat a large share of the LUT budget. But the U280
10//! also has on-chip RAM blocks that the design does not otherwise fill. A ROM
11//! is just a RAM that nobody writes, so an S-box can live in a RAM block
12//! instead, freeing its LUTs.
13//!
14//! Every S-box is a 256 × 8 ROM. The same ROM costs very different things in
15//! the three places a U280 can hold it:
16//!
17//! | Place | Cost per S-box | Notes |
18//! |---|---|---|
19//! | LUT ROM | ~32 CLB LUTs | the default; LUTs are the binding budget |
20//! | Block RAM | 1 BRAM18 (½ BRAM36 tile) | preloaded by the bitstream |
21//! | UltraRAM | 1 URAM | **cannot be preloaded**: a per-lane loader writes it after reset |
22//!
23//! A lane has 494 live S-boxes ([`LIVE_SBOX`]). The build chooses, per lane,
24//! how many go to UltraRAM and how many to block RAM:
25//!
26//! ```text
27//! DSIG_SBOX_PLACEMENT="uram=136,bram=358" cargo build ... # per lane
28//! ```
29//!
30//! They are assigned in order of (round, position) over the live S-boxes:
31//! UltraRAM first, then block RAM, the rest stay in LUTs. [`ULTRA_MASK`] and
32//! [`BLOCK_MASK`] record the result as one 64-bit mask per AES round; the
33//! S-box stages read them as compile-time constants, so only UltraRAM boxes
34//! get a write port.
35//!
36//! A second, coarser choice is per round. `DSIG_TABLE_MASK` (bit `r` = AES
37//! round `r`, only rounds 3..=8) computes whole rounds with block-RAM
38//! *T-tables* ([`TableChainStepLane`](crate::chain_step::TableChainStepLane)):
39//! a 256 × 32 ROM that returns an S-box output already multiplied into its
40//! MixColumns column, so a table round saves the S-boxes *and* most of the
41//! MixColumns XORs. [`TABLE_MASK`] holds it. Table rounds have no S-box
42//! stages, so the placement above skips them: with `DSIG_TABLE_MASK=0x1f8`
43//! only the 142 live S-boxes of rounds 0, 1, 2 and 9 are left to place.
44//!
45//! [`config`](crate::config) predicts what a placement costs and how fast it is.
46//! (The LUT figure in the table above is an estimate; `config` explains how
47//! it was derived.)
48//!
49//! # How the pieces fit
50//!
51//! ```text
52//! DSIG_SBOX_PLACEMENT ─▶ build.rs ─▶ $OUT_DIR/sbox_placement.rs
53//! URAM_PER_LANE, BRAM_PER_LANE
54//! │ include!
55//! ▼
56//! chain_step::LIVE_SBOX ─────────▶ masks() ─▶ ULTRA_MASK, BLOCK_MASK
57//! │
58//! ▼
59//! S-box stages (crate::aes_table) pick LUT / BRAM / URAM
60//! ```
61//!
62//! The decision is made when the crate is compiled, not at run time: a
63//! different placement is a different bitstream. This lets synthesis see
64//! plain constants and build only the memory each S-box needs.
65
66use crate::chain_step::LIVE_SBOX;
67use crate::haraka::AES_ROUNDS;
68
69// Brings in `URAM_PER_LANE` and `BRAM_PER_LANE`, written by `build.rs` from
70// the `DSIG_SBOX_PLACEMENT` environment variable (and the `sbox-bram`
71// feature). Both count S-boxes per lane; their sum is at most 494.
72include!(concat!(env!("OUT_DIR"), "/sbox_placement.rs"));
73
74/// Which positions of each round are UltraRAM S-boxes.
75///
76/// One entry per AES round ([`AES_ROUNDS`] = 10). Bit `k` of entry `r` is set
77/// when S-box `k` (of the 64 byte positions) in round `r` sits in UltraRAM.
78pub const ULTRA_MASK: [usize; AES_ROUNDS] = masks().0;
79/// Which positions of each round are block-RAM S-boxes.
80///
81/// Same layout as [`ULTRA_MASK`]. The two masks never overlap; a position in
82/// neither is a LUT ROM (or not live at all).
83pub const BLOCK_MASK: [usize; AES_ROUNDS] = masks().1;
84/// The lane has at least one UltraRAM S-box, so it must be loaded after reset.
85///
86/// UltraRAM starts empty, so such a lane includes a loader that writes the
87/// 256 table entries after reset. Until it finishes, the lane reports
88/// `ready = false` and the factory starts no keys.
89pub const LANE_NEEDS_LOAD: bool = URAM_PER_LANE > 0;
90
91/// Computes `(ULTRA_MASK, BLOCK_MASK)` at compile time.
92///
93/// Walks the live S-boxes in (round, position) order, two positions (`2p`,
94/// `2p + 1`) at a time, because one dual-port [`SboxPair`](crate::aes_table::SboxPair)
95/// serves both. The first `URAM_PER_LANE` go to UltraRAM, the next
96/// `BRAM_PER_LANE` to block RAM, and the rest stay in LUTs; a pair that
97/// straddles a boundary goes whole to the earlier kind. A fixed order makes the placement reproducible: the
98/// same environment variable always gives the same hardware.
99const fn masks() -> ([usize; AES_ROUNDS], [usize; AES_ROUNDS]) {
100 // One 64-bit mask per round for each kind of RAM, initially empty.
101 let mut ultra = [0_usize; AES_ROUNDS];
102 let mut block = [0_usize; AES_ROUNDS];
103 // Live S-boxes handed out so far, across all rounds.
104 let mut assigned = 0;
105 let mut round = 0;
106 while round < AES_ROUNDS {
107 // Boxes are placed in pairs (positions `2p`, `2p + 1`), because one
108 // dual-port memory serves both (`aes_table::SboxPair`).
109 let mut p = 0;
110 while p < 32 {
111 let (k0, k1) = (2 * p, 2 * p + 1);
112 // Live boxes of this pair. Dead S-boxes (constant or unused
113 // output) cost nothing; a T-table round (`TABLE_MASK`) has no
114 // S-box stages to place.
115 let live = if (TABLE_MASK >> round) & 1 == 0 {
116 LIVE_SBOX[round][k0] as usize + LIVE_SBOX[round][k1] as usize
117 } else {
118 0
119 };
120 if live > 0 {
121 // The pair's live boxes, as mask bits.
122 let bits = ((LIVE_SBOX[round][k0] as usize) << k0) | ((LIVE_SBOX[round][k1] as usize) << k1);
123 if assigned < URAM_PER_LANE {
124 ultra[round] |= bits;
125 } else if assigned < URAM_PER_LANE + BRAM_PER_LANE {
126 block[round] |= bits;
127 }
128 assigned += live;
129 }
130 p += 1;
131 }
132 round += 1;
133 }
134 (ultra, block)
135}
136
137/// Unit test of the mask computation.
138#[cfg(test)]
139mod tests {
140 use super::*;
141
142 /// The masks place exactly the requested number of boxes, never the same
143 /// box twice, and only live boxes.
144 #[test]
145 fn masks_hold_exactly_the_requested_live_boxes() {
146 // Number of set bits over all rounds.
147 let count = |masks: [usize; AES_ROUNDS]| masks.iter().map(|m| m.count_ones() as usize).sum::<usize>();
148 // Whole pairs are placed, so a count may overshoot by the one box
149 // that shares a pair with the last requested one.
150 let placeable: usize = (0..AES_ROUNDS)
151 .filter(|r| (TABLE_MASK >> r) & 1 == 0)
152 .map(|r| LIVE_SBOX[r].iter().filter(|&&live| live).count())
153 .sum();
154 let (ultra, block) = (count(ULTRA_MASK), count(BLOCK_MASK));
155 assert!(ultra >= URAM_PER_LANE.min(placeable) && ultra <= URAM_PER_LANE + 1);
156 let both = (URAM_PER_LANE + BRAM_PER_LANE).min(placeable);
157 assert!(ultra + block >= both && ultra + block <= both + 1);
158 // Both live boxes of a pair share one memory, so one style.
159 for round in 0..AES_ROUNDS {
160 for p in 0..32 {
161 let style = |m: usize| (m >> (2 * p)) & 0b11;
162 let live = (LIVE_SBOX[round][2 * p] as usize) | ((LIVE_SBOX[round][2 * p + 1] as usize) << 1);
163 for m in [ULTRA_MASK[round], BLOCK_MASK[round]] {
164 assert!(style(m) == 0 || style(m) == live, "round {round} pair {p}");
165 }
166 }
167 }
168 for round in 0..AES_ROUNDS {
169 assert_eq!(ULTRA_MASK[round] & BLOCK_MASK[round], 0);
170 for k in 0..64 {
171 if (ULTRA_MASK[round] | BLOCK_MASK[round]) >> k & 1 == 1 {
172 assert!(LIVE_SBOX[round][k], "only live boxes are placed");
173 assert!((TABLE_MASK >> round) & 1 == 0, "no RAM S-box in a T-table round");
174 }
175 }
176 }
177 }
178}