ff_core/
hash.rs

1//! Small, stable hash helpers shared across ff-sdk + ff-scheduler +
2//! ff-engine. **Not** security-sensitive — these are for cardinality
3//! reduction (log digests) and deterministic-but-spread iteration
4//! (partition-scan start offsets). A single source of truth avoids
5//! drift if the algorithm changes.
6//!
7//! Both helpers implement FNV-1a 64-bit with the standard offset basis
8//! and prime (see <http://www.isthe.com/chongo/tech/comp/fnv/>). FNV-1a
9//! is fast (byte-at-a-time), has good avalanche on short keys, and
10//! produces stable output across platforms — important because these
11//! digests leak into logs that operators grep against.
12
13/// 8-hex-character FNV-1a digest of the input, suitable for inclusion
14/// in per-event log lines as a stable "what worker is this" identifier.
15/// The upper and lower 32 bits of the 64-bit hash are XOR-folded before
16/// hex formatting to keep both halves' entropy in the 8 chars.
17pub fn fnv1a_xor8hex(s: &str) -> String {
18    let h = fnv1a_u64(s.as_bytes());
19    format!("{:08x}", (h as u32) ^ ((h >> 32) as u32))
20}
21
22/// FNV-1a of the input, reduced modulo `modulus`. Returns 0 when
23/// `modulus == 0`. Used for deterministic-but-spread scan-start
24/// offsets (partition jitter). Callers pass a non-zero modulus.
25pub fn fnv1a_u16_mod(s: &str, modulus: u16) -> u16 {
26    if modulus == 0 {
27        return 0;
28    }
29    let h = fnv1a_u64(s.as_bytes());
30    (h as u16) % modulus
31}
32
33/// FNV-1a 64-bit over raw bytes. Kept public for callers that need the
34/// full hash width (rare — most sites want the folded/reduced helpers
35/// above).
36pub fn fnv1a_u64(bytes: &[u8]) -> u64 {
37    let mut h: u64 = 0xcbf2_9ce4_8422_2325; // FNV offset basis
38    for b in bytes {
39        h ^= u64::from(*b);
40        h = h.wrapping_mul(0x100_0000_01b3); // FNV prime
41    }
42    h
43}
44
45#[cfg(test)]
46mod tests {
47    use super::*;
48
49    #[test]
50    fn fnv1a_empty_is_offset_basis() {
51        assert_eq!(fnv1a_u64(b""), 0xcbf2_9ce4_8422_2325);
52    }
53
54    #[test]
55    fn fnv1a_stable() {
56        // Regression: the literal output for a fixed input. If this test
57        // flips, either the algorithm drifted or the seed changed.
58        assert_eq!(fnv1a_xor8hex("gpu,cuda").len(), 8);
59        assert_eq!(fnv1a_xor8hex("gpu,cuda"), fnv1a_xor8hex("gpu,cuda"));
60    }
61
62    #[test]
63    fn fnv1a_u16_mod_spread() {
64        // Different inputs usually land on different partitions. Not
65        // guaranteed (hash collisions exist) but the common case.
66        let a = fnv1a_u16_mod("worker-a", 256);
67        let b = fnv1a_u16_mod("worker-b", 256);
68        assert!(a < 256 && b < 256);
69        // Zero modulus returns 0.
70        assert_eq!(fnv1a_u16_mod("anything", 0), 0);
71    }
72}
ff_core/hash.rs

ff_core/
hash.rs
