synaptic_wiring/topology/
digest.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2
3//! Deterministic topology digest for [`SynapticGraph`].
4//!
5//! Replay, checkpoint provenance, and cross-runtime comparisons need a stable
6//! identifier of the *logical* graph that does not depend on CSR insertion
7//! order, map iteration, pointer layout, host endianness, or JSON formatting.
8//!
9//! # Schema v1
10//!
11//! The printable value is:
12//!
13//! ```text
14//! synaptic-wiring.topology.digest.v1:sha256:<64 lowercase hex chars>
15//! ```
16//!
17//! The SHA-256 preimage is the concatenation of:
18//!
19//! 1. Domain separator [`TOPOLOGY_DIGEST_DOMAIN`] as UTF-8, then a NUL byte
20//!    so the separator cannot prefix-collide with the payload.
21//! 2. Schema version [`TOPOLOGY_DIGEST_SCHEMA_VERSION`] as little-endian `u16`.
22//! 3. Neuron count as little-endian `u64`.
23//! 4. Edge count as little-endian `u64`.
24//! 5. One 23-byte record per logical edge, sorted in canonical order
25//!    `(source, target, delay, polarity_tag, weight_bits)`:
26//!    - `source`: little-endian `u64` (CSR row index)
27//!    - `target`: little-endian `u64` (zero-extended [`crate::NeuronId`])
28//!    - `weight_bits`: little-endian `u32` of [`f32::to_bits`] (IEEE 754
29//!      bit pattern of the **signed** CSR weight)
30//!    - `delay`: little-endian [`crate::DelayTicks`]
31//!    - `polarity_tag`: `0` = [`Polarity::Excitatory`], `1` =
32//!      [`Polarity::Inhibitory`]
33//!
34//! Bumping the schema version or domain separator produces a new printable
35//! prefix; v1 values stay comparable forever.
36//!
37//! # Float canonicalization
38//!
39//! Schema v1 hashes the IEEE bit pattern. Construction and serde already
40//! reject NaN and infinities, so a valid graph never contains them.
41//! IEEE signed zero (`+0.0` vs `-0.0`) is **not** collapsed: the two bit
42//! patterns digest differently, which is tested.
43
44use std::fmt;
45use std::str::FromStr;
46
47use serde::de::{Deserializer, Error as DeError};
48use serde::{Deserialize, Serialize, Serializer};
49use sha2::{Digest, Sha256};
50
51use super::graph::SynapticGraph;
52use crate::types::Polarity;
53
54/// Schema version mixed into the v1 preimage and reported by
55/// [`TopologyDigest::schema_version`].
56pub const TOPOLOGY_DIGEST_SCHEMA_VERSION: u16 = 1;
57
58/// Domain separator (UTF-8) that prefixes the SHA-256 preimage and the
59/// printable manifest form. Changing this is a new digest family.
60pub const TOPOLOGY_DIGEST_DOMAIN: &str = "synaptic-wiring.topology.digest.v1";
61
62/// Hash algorithm name embedded in the printable manifest form.
63pub const TOPOLOGY_DIGEST_ALGORITHM: &str = "sha256";
64
65/// NUL terminator after the domain separator in the hash preimage.
66const DOMAIN_TERMINATOR: u8 = 0;
67
68/// Printable, versioned digest of a graph's logical topology.
69///
70/// The [`fmt::Display`] form is stable and safe to store in manifests:
71/// `{domain}:{algorithm}:{hex}`.
72#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
73pub struct TopologyDigest {
74    schema_version: u16,
75    hash: [u8; 32],
76}
77
78impl TopologyDigest {
79    /// Compute the schema-v1 digest of `graph`.
80    ///
81    /// Edges are collected from the CSR and sorted into canonical order, so
82    /// two graphs built from the same logical synapses in different insertion
83    /// orders compare equal. Runtime mesh state (tick, delay buffer) is not
84    /// part of the digest.
85    #[must_use]
86    pub fn from_graph(graph: &SynapticGraph) -> Self {
87        let edges = canonical_edges(graph);
88        Self {
89            schema_version: TOPOLOGY_DIGEST_SCHEMA_VERSION,
90            hash: hash_v1(graph.neuron_count() as u64, &edges),
91        }
92    }
93
94    /// Schema version that produced this digest.
95    #[must_use]
96    pub fn schema_version(&self) -> u16 {
97        self.schema_version
98    }
99
100    /// Hash algorithm name (`sha256` for schema v1).
101    #[must_use]
102    pub fn algorithm(&self) -> &'static str {
103        TOPOLOGY_DIGEST_ALGORITHM
104    }
105
106    /// Domain separator mixed into this digest family.
107    #[must_use]
108    pub fn domain(&self) -> &'static str {
109        TOPOLOGY_DIGEST_DOMAIN
110    }
111
112    /// Raw 32-byte SHA-256 hash.
113    #[must_use]
114    pub fn as_bytes(&self) -> &[u8; 32] {
115        &self.hash
116    }
117
118    /// Lowercase hex encoding of the SHA-256 hash (64 characters).
119    #[must_use]
120    pub fn to_hex(&self) -> String {
121        hex_encode(&self.hash)
122    }
123}
124
125impl fmt::Display for TopologyDigest {
126    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
127        write!(
128            f,
129            "{TOPOLOGY_DIGEST_DOMAIN}:{TOPOLOGY_DIGEST_ALGORITHM}:{}",
130            self.to_hex()
131        )
132    }
133}
134
135impl FromStr for TopologyDigest {
136    type Err = TopologyDigestParseError;
137
138    fn from_str(s: &str) -> Result<Self, Self::Err> {
139        let (domain, algorithm, hex) = split_manifest(s)?;
140        if domain != TOPOLOGY_DIGEST_DOMAIN {
141            return Err(TopologyDigestParseError(format!(
142                "unsupported digest domain {domain:?}"
143            )));
144        }
145        if algorithm != TOPOLOGY_DIGEST_ALGORITHM {
146            return Err(TopologyDigestParseError(format!(
147                "unsupported digest algorithm {algorithm:?}"
148            )));
149        }
150        Ok(Self {
151            schema_version: TOPOLOGY_DIGEST_SCHEMA_VERSION,
152            hash: hex_decode_sha256(hex)?,
153        })
154    }
155}
156
157impl Serialize for TopologyDigest {
158    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
159        serializer.serialize_str(&self.to_string())
160    }
161}
162
163impl<'de> Deserialize<'de> for TopologyDigest {
164    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
165        let s = String::deserialize(deserializer)?;
166        s.parse().map_err(DeError::custom)
167    }
168}
169
170/// Error from parsing a printable [`TopologyDigest`].
171#[derive(Debug, Clone, PartialEq, Eq)]
172pub struct TopologyDigestParseError(String);
173
174impl TopologyDigestParseError {
175    fn format() -> Self {
176        Self(format!(
177            "expected {TOPOLOGY_DIGEST_DOMAIN}:{TOPOLOGY_DIGEST_ALGORITHM}:<64 hex chars>"
178        ))
179    }
180}
181
182impl fmt::Display for TopologyDigestParseError {
183    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
184        f.write_str(&self.0)
185    }
186}
187
188impl std::error::Error for TopologyDigestParseError {}
189
190impl SynapticGraph {
191    /// Deterministic, versioned digest of this graph's logical topology.
192    ///
193    /// See [`TopologyDigest`] for the schema, domain separator, and float
194    /// bit-pattern rules. Equivalent graphs built through different insertion
195    /// orders produce the same value.
196    ///
197    /// ```
198    /// use synaptic_wiring::topology::SynapticGraph;
199    /// use synaptic_wiring::types::{Polarity, SynapseDescriptor};
200    ///
201    /// let a = [
202    ///     SynapseDescriptor {
203    ///         source: 0,
204    ///         target: 1,
205    ///         weight: 0.5,
206    ///         delay: 2,
207    ///         polarity: Polarity::Excitatory,
208    ///     },
209    ///     SynapseDescriptor {
210    ///         source: 1,
211    ///         target: 0,
212    ///         weight: 0.25,
213    ///         delay: 1,
214    ///         polarity: Polarity::Inhibitory,
215    ///     },
216    /// ];
217    /// let mut b = a;
218    /// b.swap(0, 1);
219    ///
220    /// let ga = SynapticGraph::from_descriptors(2, &a).unwrap();
221    /// let gb = SynapticGraph::from_descriptors(2, &b).unwrap();
222    /// assert_eq!(ga.topology_digest(), gb.topology_digest());
223    /// ```
224    #[must_use]
225    pub fn topology_digest(&self) -> TopologyDigest {
226        TopologyDigest::from_graph(self)
227    }
228}
229
230#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
231struct CanonicalEdge {
232    source: u64,
233    target: u64,
234    delay: u16,
235    polarity: u8,
236    weight_bits: u32,
237}
238
239fn canonical_edges(graph: &SynapticGraph) -> Vec<CanonicalEdge> {
240    let mut edges = Vec::with_capacity(graph.synapse_count());
241    for src in 0..graph.neuron_count() {
242        let source = src as u64;
243        for (target, weight, delay, polarity) in graph.outgoing(src) {
244            debug_assert!(
245                weight.is_finite(),
246                "valid graphs reject non-finite weights before digest"
247            );
248            edges.push(CanonicalEdge {
249                source,
250                target: u64::from(target),
251                delay,
252                polarity: polarity_tag(polarity),
253                weight_bits: weight.to_bits(),
254            });
255        }
256    }
257    edges.sort_unstable();
258    edges
259}
260
261fn hash_v1(neuron_count: u64, edges: &[CanonicalEdge]) -> [u8; 32] {
262    let mut hasher = Sha256::new();
263    hasher.update(TOPOLOGY_DIGEST_DOMAIN.as_bytes());
264    hasher.update([DOMAIN_TERMINATOR]);
265    hasher.update(TOPOLOGY_DIGEST_SCHEMA_VERSION.to_le_bytes());
266    hasher.update(neuron_count.to_le_bytes());
267    hasher.update((edges.len() as u64).to_le_bytes());
268    for edge in edges {
269        hasher.update(edge.source.to_le_bytes());
270        hasher.update(edge.target.to_le_bytes());
271        hasher.update(edge.weight_bits.to_le_bytes());
272        hasher.update(edge.delay.to_le_bytes());
273        hasher.update([edge.polarity]);
274    }
275    hasher.finalize().into()
276}
277
278fn polarity_tag(polarity: Polarity) -> u8 {
279    match polarity {
280        Polarity::Excitatory => 0,
281        Polarity::Inhibitory => 1,
282    }
283}
284
285fn split_manifest(s: &str) -> Result<(&str, &str, &str), TopologyDigestParseError> {
286    let (domain, rest) = s
287        .split_once(':')
288        .ok_or_else(TopologyDigestParseError::format)?;
289    let (algorithm, hex) = rest
290        .split_once(':')
291        .ok_or_else(TopologyDigestParseError::format)?;
292    Ok((domain, algorithm, hex))
293}
294
295fn hex_encode(bytes: &[u8]) -> String {
296    const HEX: &[u8; 16] = b"0123456789abcdef";
297    let mut out = String::with_capacity(bytes.len() * 2);
298    for &b in bytes {
299        out.push(HEX[(b >> 4) as usize] as char);
300        out.push(HEX[(b & 0x0f) as usize] as char);
301    }
302    out
303}
304
305fn hex_decode_sha256(hex: &str) -> Result<[u8; 32], TopologyDigestParseError> {
306    if hex.len() != 64 {
307        return Err(TopologyDigestParseError(format!(
308            "digest hex must be 64 characters, got {}",
309            hex.len()
310        )));
311    }
312    let mut out = [0u8; 32];
313    let bytes = hex.as_bytes();
314    for (i, slot) in out.iter_mut().enumerate() {
315        let hi = hex_nibble(bytes[i * 2])?;
316        let lo = hex_nibble(bytes[i * 2 + 1])?;
317        *slot = (hi << 4) | lo;
318    }
319    Ok(out)
320}
321
322fn hex_nibble(b: u8) -> Result<u8, TopologyDigestParseError> {
323    match b {
324        b'0'..=b'9' => Ok(b - b'0'),
325        b'a'..=b'f' => Ok(b - b'a' + 10),
326        b'A'..=b'F' => Ok(b - b'A' + 10),
327        _ => Err(TopologyDigestParseError(format!(
328            "invalid hex digit {:?}",
329            b as char
330        ))),
331    }
332}
synaptic_wiring/topology/digest.rs

synaptic_wiring/topology/
digest.rs
