qualia_core_db/net/qdnf/route/
spf.rs1use crate::net::qdnf::errors::QdnfError;
4use crate::net::qdnf::types::DniCoordinate;
5
6pub const MAX_NODES: usize = 16;
7pub const MAX_NEXT_HOPS: usize = 3;
8
9#[repr(C)]
10#[derive(Clone, Copy, Debug, PartialEq, Eq)]
11pub struct LinkMetric {
12 pub from: u8,
13 pub to: u8,
14 pub cost: u16,
15 pub bidirectional: bool,
16}
17
18#[repr(C)]
19#[derive(Clone, Copy, Debug, PartialEq, Eq)]
20pub struct NextHop {
21 pub node: u8,
22 pub cost: u16,
23}
24
25#[repr(C)]
26#[derive(Clone, Copy, Debug, PartialEq, Eq)]
27pub struct SpfTable {
28 pub dest: [u8; MAX_NODES],
29 pub hops: [[NextHop; MAX_NEXT_HOPS]; MAX_NODES],
30 pub hop_counts: [u8; MAX_NODES],
31 pub nodes: usize,
32 pub origin: u8,
33 pub potentials: [u16; MAX_NODES],
35}
36
37impl SpfTable {
38 pub const EMPTY: Self = Self {
39 dest: [0; MAX_NODES],
40 hops: [[NextHop { node: 0, cost: 0 }; MAX_NEXT_HOPS]; MAX_NODES],
41 hop_counts: [0; MAX_NODES],
42 nodes: 0,
43 origin: 0,
44 potentials: [u16::MAX; MAX_NODES],
45 };
46
47 #[inline]
49 pub const fn dual_witness(&self) -> SpfDualWitness {
50 SpfDualWitness {
51 origin: self.origin,
52 potentials: self.potentials,
53 }
54 }
55}
56
57#[repr(C)]
59#[derive(Clone, Copy, Debug, PartialEq, Eq)]
60pub struct SpfDualWitness {
61 pub origin: u8,
62 pub potentials: [u16; MAX_NODES],
63}
64
65pub fn compute_spf(origin: u8, links: &[LinkMetric], out: &mut SpfTable) -> Result<(), QdnfError> {
67 *out = SpfTable::EMPTY;
68 let mut dist = [u16::MAX; MAX_NODES];
69 let mut prev = [u8::MAX; MAX_NODES];
70 let mut used = [false; MAX_NODES];
71 if (origin as usize) >= MAX_NODES {
72 return Err(QdnfError::Range);
73 }
74 dist[origin as usize] = 0;
75 for _ in 0..MAX_NODES {
76 let mut best = u16::MAX;
77 let mut u = usize::MAX;
78 for (i, (d, taken)) in dist.iter().zip(used.iter()).enumerate() {
79 if !taken && *d < best {
80 best = *d;
81 u = i;
82 } else if !taken && *d == best && u != usize::MAX && i < u {
83 u = i;
84 }
85 }
86 if u == usize::MAX {
87 break;
88 }
89 used[u] = true;
90 for link in links {
91 if !link.bidirectional {
92 continue;
93 }
94 if link.from as usize != u && link.to as usize != u {
95 continue;
96 }
97 let v = if link.from as usize == u {
98 link.to as usize
99 } else {
100 link.from as usize
101 };
102 if v >= MAX_NODES {
103 return Err(QdnfError::Range);
104 }
105 let cand = match dist[u].checked_add(link.cost) {
106 Some(c) => c,
107 None => return Err(QdnfError::Range),
108 };
109 if cand < dist[v] || (cand == dist[v] && (u as u8) < prev[v]) {
110 dist[v] = cand;
111 prev[v] = u as u8;
112 }
113 }
114 }
115 let mut n = 0usize;
116 for (i, d) in dist.iter().enumerate() {
117 if *d == u16::MAX {
118 continue;
119 }
120 out.dest[n] = i as u8;
121 if i as u8 == origin {
122 out.hop_counts[n] = 0;
123 } else {
124 let mut hop = i as u8;
125 let mut guard = 0;
126 while prev[hop as usize] != origin && prev[hop as usize] != u8::MAX && guard < MAX_NODES
127 {
128 hop = prev[hop as usize];
129 guard += 1;
130 }
131 out.hops[n][0] = NextHop {
132 node: hop,
133 cost: *d,
134 };
135 out.hop_counts[n] = 1;
136 }
137 n += 1;
138 }
139 out.nodes = n;
140 out.origin = origin;
141 out.potentials = dist;
142 Ok(())
143}
144
145pub fn verify_spf_dual_witness(
150 origin: u8,
151 dest: u8,
152 links: &[LinkMetric],
153 potentials: &[u16; MAX_NODES],
154 selected_path: &[u8],
155) -> Result<(), QdnfError> {
156 if (origin as usize) >= MAX_NODES || (dest as usize) >= MAX_NODES {
157 return Err(QdnfError::Range);
158 }
159 if selected_path.is_empty()
160 || selected_path[0] != origin
161 || selected_path[selected_path.len() - 1] != dest
162 {
163 return Err(QdnfError::Malformed);
164 }
165 if potentials[origin as usize] != 0 {
166 return Err(QdnfError::Conflict);
167 }
168 let mut e = 0usize;
170 while e < links.len() {
171 let link = links[e];
172 if link.bidirectional {
173 let u = link.from as usize;
174 let v = link.to as usize;
175 if u >= MAX_NODES || v >= MAX_NODES {
176 return Err(QdnfError::Range);
177 }
178 if potentials[u] != u16::MAX {
179 let bound = potentials[u]
180 .checked_add(link.cost)
181 .ok_or(QdnfError::Range)?;
182 if potentials[v] > bound {
183 return Err(QdnfError::Conflict);
184 }
185 }
186 if potentials[v] != u16::MAX {
187 let bound = potentials[v]
188 .checked_add(link.cost)
189 .ok_or(QdnfError::Range)?;
190 if potentials[u] > bound {
191 return Err(QdnfError::Conflict);
192 }
193 }
194 }
195 e += 1;
196 }
197 let mut k = 0usize;
199 while k + 1 < selected_path.len() {
200 let u = selected_path[k];
201 let v = selected_path[k + 1];
202 if (u as usize) >= MAX_NODES || (v as usize) >= MAX_NODES {
203 return Err(QdnfError::Range);
204 }
205 let mut min_w = u16::MAX;
206 let mut found = false;
207 let mut j = 0usize;
208 while j < links.len() {
209 let link = links[j];
210 if link.bidirectional
211 && ((link.from == u && link.to == v) || (link.from == v && link.to == u))
212 && (!found || link.cost < min_w)
213 {
214 min_w = link.cost;
215 found = true;
216 }
217 j += 1;
218 }
219 if !found {
220 return Err(QdnfError::NoRoute);
221 }
222 let du = potentials[u as usize];
223 let dv = potentials[v as usize];
224 if du == u16::MAX || dv == u16::MAX {
225 return Err(QdnfError::Conflict);
226 }
227 let expected_dv = du.checked_add(min_w).ok_or(QdnfError::Range)?;
228 if dv != expected_dv {
229 return Err(QdnfError::Conflict);
230 }
231 k += 1;
232 }
233 Ok(())
234}
235
236pub fn dni_node(coord: DniCoordinate) -> u8 {
238 (coord.node_id & 0xff) as u8
239}
240
241#[cfg(test)]
242mod tests {
243 use super::*;
244
245 #[test]
246 fn three_node_path_a_b_c() {
247 let links = [
248 LinkMetric {
249 from: 0,
250 to: 1,
251 cost: 1,
252 bidirectional: true,
253 },
254 LinkMetric {
255 from: 1,
256 to: 2,
257 cost: 1,
258 bidirectional: true,
259 },
260 ];
261 let mut table = SpfTable::EMPTY;
262 compute_spf(0, &links, &mut table).unwrap();
263 let dest_c = table.dest.iter().position(|d| *d == 2).unwrap();
264 assert_eq!(out_hop(&table, dest_c), 1);
265 }
266
267 fn out_hop(table: &SpfTable, idx: usize) -> u8 {
268 table.hops[idx][0].node
269 }
270
271 #[test]
272 fn one_sided_link_is_ignored() {
273 let links = [LinkMetric {
274 from: 0,
275 to: 1,
276 cost: 1,
277 bidirectional: false,
278 }];
279 let mut table = SpfTable::EMPTY;
280 compute_spf(0, &links, &mut table).unwrap();
281 assert!(table.dest.iter().take(table.nodes).all(|d| *d == 0));
282 }
283
284 #[test]
285 fn bellman_ford_dual_witness_verifies_optimal_path_and_rejects_suboptimal() {
286 let links = [
287 LinkMetric {
288 from: 0,
289 to: 1,
290 cost: 2,
291 bidirectional: true,
292 },
293 LinkMetric {
294 from: 1,
295 to: 2,
296 cost: 3,
297 bidirectional: true,
298 },
299 LinkMetric {
300 from: 0,
301 to: 2,
302 cost: 9,
303 bidirectional: true,
304 },
305 ];
306 let mut table = SpfTable::EMPTY;
307 compute_spf(0, &links, &mut table).unwrap();
308 let w = table.dual_witness();
309 assert_eq!(w.potentials[0], 0);
310 assert_eq!(w.potentials[1], 2);
311 assert_eq!(w.potentials[2], 5);
312
313 assert_eq!(
315 verify_spf_dual_witness(0, 2, &links, &w.potentials, &[0, 1, 2]),
316 Ok(())
317 );
318 assert_eq!(
320 verify_spf_dual_witness(0, 2, &links, &w.potentials, &[0, 2]),
321 Err(QdnfError::Conflict)
322 );
323 let mut dishonest = w.potentials;
325 dishonest[2] = 9;
326 assert_eq!(
327 verify_spf_dual_witness(0, 2, &links, &dishonest, &[0, 2]),
328 Err(QdnfError::Conflict)
329 );
330 }
331}