katra_core/
hash.rs

1//! Deterministic hashing (FNV-1a 64).
2//!
3//! Katra3D uses fingerprints everywhere — file identity, access patterns,
4//! cache keys, semantic graph identity. Fingerprints must be **stable across
5//! runs, machines, and architectures**, so we implement FNV-1a directly
6//! instead of relying on randomized or platform-dependent hashers.
7//!
8//! FNV-1a is *not* a cryptographic hash. It is deliberately simple,
9//! auditable, and deterministic (KatraFlow §10: "simple, auditable
10//! techniques").
11
12/// FNV-1a 64-bit over raw bytes. `const` so schema hashes can be computed at
13/// compile time.
14pub const fn fnv1a(bytes: &[u8]) -> u64 {
15    let mut h: u64 = 0xcbf2_9ce4_8422_2325;
16    let mut i = 0usize;
17    while i < bytes.len() {
18        h ^= bytes[i] as u64;
19        h = h.wrapping_mul(0x0000_0100_0000_01b3);
20        i += 1;
21    }
22    h
23}
24
25/// FNV-1a over a string.
26pub fn fnv1a_str(s: &str) -> u64 {
27    fnv1a(s.as_bytes())
28}
29
30/// FNV-1a over a sequence of 64-bit parts (each part folded in little-endian).
31pub fn fnv1a_parts(parts: &[u64]) -> u64 {
32    let mut h: u64 = 0xcbf2_9ce4_8422_2325;
33    for &p in parts {
34        let mut shift = 0usize;
35        while shift < 8 {
36            h ^= (p >> (shift * 8)) & 0xff;
37            h = h.wrapping_mul(0x0000_0100_0000_01b3);
38            shift += 1;
39        }
40    }
41    h
42}
43
44/// Combine two hashes (for rolling fingerprints).
45pub fn fnv1a_combine(acc: u64, next: u64) -> u64 {
46    let mut h = acc ^ 0x9e37_79b9_7f4a_7c15;
47    let mut shift = 0usize;
48    while shift < 8 {
49        h ^= (next >> (shift * 8)) & 0xff;
50        h = h.wrapping_mul(0x0000_0100_0000_01b3);
51        shift += 1;
52    }
53    h
54}
55
56#[cfg(test)]
57mod tests {
58    use super::*;
59
60    #[test]
61    fn fnv1a_known_vector() {
62        // Well-known FNV-1a 64 vector: fnv1a("") == 0xcbf29ce484222325
63        assert_eq!(fnv1a(b""), 0xcbf2_9ce4_8422_2325);
64        // fnv1a("a") == 0xaf63dc4c8601ec8c
65        assert_eq!(fnv1a(b"a"), 0xaf63_dc4c_8601_ec8c);
66    }
67
68    #[test]
69    fn parts_combine_is_stable() {
70        assert_eq!(fnv1a_parts(&[1, 2, 3]), fnv1a_parts(&[1, 2, 3]));
71        assert_ne!(fnv1a_parts(&[1, 2, 3]), fnv1a_parts(&[1, 2, 4]));
72    }
73
74    #[test]
75    fn str_matches_bytes() {
76        assert_eq!(fnv1a_str("hello"), fnv1a(b"hello"));
77    }
78}
katra_core/hash.rs

katra_core/
hash.rs
