magi/
rng.rs

1//! A seeded PRNG, so that label assignment and session ids are reproducible
2//! from a run id.
3//!
4//! magi needs exactly two random things — which candidate gets which label, and
5//! a UUID for each Claude session — and both must be replayable when a run is
6//! resumed. A 20-line SplitMix64 covers that without a dependency whose version
7//! could change the shuffle out from under a resumed run.
8
9/// SplitMix64. Fixed algorithm: the sequence for a given seed is part of magi's
10/// on-disk contract, because a resumed run must recompute the same labels.
11#[derive(Debug, Clone)]
12pub struct SplitMix64(u64);
13
14impl SplitMix64 {
15    /// Seed the generator.
16    pub fn new(seed: u64) -> Self {
17        Self(seed)
18    }
19
20    /// Seed from an arbitrary string (FNV-1a), for per-seat derivation.
21    pub fn from_key(s: &str) -> Self {
22        Self::new(fnv1a(s))
23    }
24
25    /// Next 64 bits.
26    pub fn next_u64(&mut self) -> u64 {
27        self.0 = self.0.wrapping_add(0x9E37_79B9_7F4A_7C15);
28        let mut z = self.0;
29        z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
30        z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
31        z ^ (z >> 31)
32    }
33
34    /// Uniform-enough value in `0..n`. `n` must be non-zero.
35    pub fn below(&mut self, n: usize) -> usize {
36        debug_assert!(n > 0);
37        (self.next_u64() % n as u64) as usize
38    }
39
40    /// Fisher-Yates, in place.
41    pub fn shuffle<T>(&mut self, items: &mut [T]) {
42        for i in (1..items.len()).rev() {
43            let j = self.below(i + 1);
44            items.swap(i, j);
45        }
46    }
47
48    /// A syntactically valid RFC 4122 version 4 UUID.
49    ///
50    /// `claude --session-id` rejects anything else, and minting the id
51    /// ourselves means the first turn and every resume agree on it without
52    /// having to parse it back out of the CLI's output.
53    pub fn uuid_v4(&mut self) -> String {
54        let mut b = [0u8; 16];
55        for chunk in b.chunks_mut(8) {
56            let v = self.next_u64().to_le_bytes();
57            chunk.copy_from_slice(&v[..chunk.len()]);
58        }
59        b[6] = (b[6] & 0x0f) | 0x40;
60        b[8] = (b[8] & 0x3f) | 0x80;
61        let h = |r: &[u8]| r.iter().map(|x| format!("{x:02x}")).collect::<String>();
62        format!(
63            "{}-{}-{}-{}-{}",
64            h(&b[0..4]),
65            h(&b[4..6]),
66            h(&b[6..8]),
67            h(&b[8..10]),
68            h(&b[10..16])
69        )
70    }
71}
72
73/// FNV-1a over the bytes of `s`.
74pub fn fnv1a(s: &str) -> u64 {
75    let mut h: u64 = 0xcbf2_9ce4_8422_2325;
76    for byte in s.as_bytes() {
77        h ^= u64::from(*byte);
78        h = h.wrapping_mul(0x100_0000_01b3);
79    }
80    h
81}
82
83/// Entropy for a fresh run id: wall clock nanoseconds mixed with the pid.
84pub fn entropy() -> u64 {
85    let nanos = std::time::SystemTime::now()
86        .duration_since(std::time::UNIX_EPOCH)
87        .map(|d| d.as_nanos() as u64)
88        .unwrap_or(0);
89    let mut r = SplitMix64::new(nanos ^ (u64::from(std::process::id()) << 32));
90    r.next_u64()
91}
92
93#[cfg(test)]
94mod tests {
95    use super::*;
96
97    #[test]
98    fn same_seed_same_shuffle() {
99        let mut a = SplitMix64::new(42);
100        let mut b = SplitMix64::new(42);
101        let mut xs = [0, 1, 2, 3, 4, 5, 6, 7];
102        let mut ys = xs;
103        a.shuffle(&mut xs);
104        b.shuffle(&mut ys);
105        assert_eq!(xs, ys);
106    }
107
108    #[test]
109    fn shuffle_is_a_permutation() {
110        let mut r = SplitMix64::new(7);
111        let mut xs: Vec<usize> = (0..64).collect();
112        r.shuffle(&mut xs);
113        let mut sorted = xs.clone();
114        sorted.sort_unstable();
115        assert_eq!(sorted, (0..64).collect::<Vec<_>>());
116        assert_ne!(xs, sorted, "a 64-element shuffle should move something");
117    }
118
119    #[test]
120    fn shuffle_handles_degenerate_lengths() {
121        let mut r = SplitMix64::new(1);
122        let mut empty: [u8; 0] = [];
123        r.shuffle(&mut empty);
124        let mut one = [9];
125        r.shuffle(&mut one);
126        assert_eq!(one, [9]);
127    }
128
129    #[test]
130    fn uuid_v4_shape_and_variant_bits() {
131        let mut r = SplitMix64::new(99);
132        let id = r.uuid_v4();
133        let parts: Vec<&str> = id.split('-').collect();
134        assert_eq!(
135            parts.iter().map(|p| p.len()).collect::<Vec<_>>(),
136            [8, 4, 4, 4, 12]
137        );
138        assert!(id.chars().all(|c| c.is_ascii_hexdigit() || c == '-'));
139        assert_eq!(&parts[2][..1], "4", "version nibble");
140        assert!(
141            matches!(&parts[3][..1], "8" | "9" | "a" | "b"),
142            "variant nibble: {id}"
143        );
144        assert_ne!(id, SplitMix64::new(100).uuid_v4());
145    }
146
147    #[test]
148    fn seat_seeds_differ_per_seat() {
149        assert_ne!(
150            SplitMix64::from_key("judge-1").uuid_v4(),
151            SplitMix64::from_key("judge-2").uuid_v4()
152        );
153    }
154}
magi/rng.rs

magi/
rng.rs
