nx_fnv.nx source
↩ module page · 99 lines · 3067 B
1// fnv.nx -- FNV-1a non-cryptographic hash (Fowler-Noll-Vo).
2//
3// Canonical: this is the substrate-wide canonical FNV-1a 64-bit
4// implementation per [[feedback-no-tool-proliferation-bit-level]].
5// All other primitives needing FNV-1a MUST `import "nx_fnv.nx"`
6// and compose fnv1a / fnv1a_init / fnv1a_update / fnv1a_cstr;
7// re-implementing FNV inline is refused per the cardinal.
8//
9// 64-bit FNV-1a. Used for: hash table keying, file
10// fingerprinting, Bloom filter mixing, deduplication. NOT for
11// security -- an attacker who controls input can construct
12// collisions. For cryptographic hashing use sha256 / sha512 /
13// sha3.
14//
15// Algorithm (Fowler-Noll-Vo 1991; rfc draft-eastlake-fnv):
16// hash = FNV_OFFSET_BASIS
17// for each byte b in input:
18// hash = hash XOR b
19// hash = hash * FNV_PRIME
20//
21// FNV-1a (xor-then-multiply) has better avalanche than plain
22// FNV-1 (multiply-then-xor) so we implement 1a.
23//
24// 64-bit constants (Eastlake RFC draft):
25// offset_basis = 0xCBF29CE484222325
26// prime = 0x100000001B3
27//
28// Invariants:
29// F1 Empty input hashes to offset_basis (14695981039346656037).
30// F2 Identical byte sequences always hash to the same value
31// across runs / machines / endianness (state is plain i64
32// arithmetic, no byte-order dependence).
33// F3 Multiplication overflows are wrapped mod 2^64 by the
34// underlying i64 arithmetic -- matches reference spec.
35
36// nx_safety_envelope:
37// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
38// sil_target: SIL1
39// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
40// verdict: NOT_YET_EVALUATED
41
42import "nx_syscalls.nx"
43
44const FNV_OFFSET_BASIS: i64 = 0xCBF29CE484222325
45const FNV_PRIME: i64 = 0x100000001B3
46
47// Hash a byte buffer.
48func fnv1a(data: *u8, n: i64) -> i64 {
49 var h: i64 = FNV_OFFSET_BASIS
50 var i: i64 = 0
51 while i < n {
52 h = h ^ data[i]
53 h = h * FNV_PRIME
54 i = i + 1
55 }
56 return h
57}
58
59// Incremental API: start a hash state.
60func fnv1a_init() -> i64 {
61 return FNV_OFFSET_BASIS
62}
63
64// Feed bytes into an existing state; returns new state.
65func fnv1a_update(state: i64, data: *u8, n: i64) -> i64 {
66 var h: i64 = state
67 var i: i64 = 0
68 while i < n {
69 h = h ^ data[i]
70 h = h * FNV_PRIME
71 i = i + 1
72 }
73 return h
74}
75
76// Convenience: hash a NUL-terminated C-style string.
77func fnv1a_cstr(s: *u8) -> i64 {
78 var i: i64 = 0
79 while s[i] != 0 { i = i + 1 }
80 return fnv1a(s, i)
81}
82
83// Compile-only smoke -- verify empty input gives offset_basis
84// and two different inputs hash differently.
85func main() -> i64 {
86 let empty: i64 = fnv1a(0 as *u8, 0)
87 if empty != FNV_OFFSET_BASIS { return 1 }
88
89 let ha: i64 = fnv1a("hello", 5)
90 let hb: i64 = fnv1a("world", 5)
91 if ha == hb { return 2 }
92
93 // Incremental matches one-shot.
94 var st: i64 = fnv1a_init()
95 st = fnv1a_update(st, "hel", 3)
96 st = fnv1a_update(st, "lo", 2)
97 if st != ha { return 3 }
98 return 0
99}