fnv.nx source

1// RETIRED 2026-07-30 -- moved here from runtime/fnv.nx. PRESERVED VERBATIM BELOW, NOT DELETED (rule 13). 2// 3// WHY IT WAS RETIRED: it defined `fnv1a`, `fnv1a_init`, `fnv1a_update` and `fnv1a_cstr` -- THE EXACT FOUR 4// SYMBOLS the canonical runtime/nx_fnv.nx defines -- with a byte-identical algorithm and identical 5// constants. The ONLY difference was `import "syscalls.nx"` vs `import "nx_syscalls.nx"`. 6// 7// TWO FILES CLAIMING TO BE THE CANONICAL HASH IS WORSE THAN NONE: nx_fnv.nx's own header carries the 8// cardinal law "All other primitives needing FNV-1a MUST import nx_fnv.nx ... never re-implement a hash 9// inline" -- but that law names a target that was AMBIGUOUS, and any organ importing both would collide 10// symbol-for-symbol. 11// 12// MEASURED BEFORE RETIRING (complete scan of buildroot, not a partial one): 13// runtime/fnv.nx 2577 B -- 0 importers 14// runtime/nx_fnv.nx 3067 B -- 7 importers <- canonical, keeps the name the law points at 15// A sovereign nx_shelltool scan returned 0 matches too, but reported PARTIAL (budget-exceeded at 15315 of 16// ~19940 files) -- and ZERO ON A PARTIAL SCAN IS NOT PROOF OF ABSENCE, so the count above is from a 17// complete scan. The tool was right to say so; the reading would have been wrong to trust. 18// 19// TO RESURRECT: copy this file back to runtime/fnv.nx and change the import to nx_syscalls.nx -- but do 20// not, because nx_fnv.nx already is this, and re-adding it re-creates the ambiguity. 21// license_tier: ORIGINAL No hw writes (Rule 26). 22// 23// ---------------- ORIGINAL CONTENT, VERBATIM ---------------- 24// fnv.nx -- FNV-1a non-cryptographic hash (Fowler-Noll-Vo). 25// 26// 64-bit FNV-1a. Used for: hash table keying, file 27// fingerprinting, Bloom filter mixing, deduplication. NOT for 28// security -- an attacker who controls input can construct 29// collisions. For cryptographic hashing use sha256 / sha512 / 30// sha3. 31// 32// Algorithm (Fowler-Noll-Vo 1991; rfc draft-eastlake-fnv): 33// hash = FNV_OFFSET_BASIS 34// for each byte b in input: 35// hash = hash XOR b 36// hash = hash * FNV_PRIME 37// 38// FNV-1a (xor-then-multiply) has better avalanche than plain 39// FNV-1 (multiply-then-xor) so we implement 1a. 40// 41// 64-bit constants (Eastlake RFC draft): 42// offset_basis = 0xCBF29CE484222325 43// prime = 0x100000001B3 44// 45// Invariants: 46// F1 Empty input hashes to offset_basis (14695981039346656037). 47// F2 Identical byte sequences always hash to the same value 48// across runs / machines / endianness (state is plain i64 49// arithmetic, no byte-order dependence). 50// F3 Multiplication overflows are wrapped mod 2^64 by the 51// underlying i64 arithmetic -- matches reference spec. 52// 53// import "syscalls.nx" 54// 55// const FNV_OFFSET_BASIS: i64 = 0xCBF29CE484222325 56// const FNV_PRIME: i64 = 0x100000001B3 57// 58// func fnv1a(data: *u8, n: i64) -> i64 { 59// var h: i64 = FNV_OFFSET_BASIS 60// var i: i64 = 0 61// while i < n { 62// h = h ^ data[i] 63// h = h * FNV_PRIME 64// i = i + 1 65// } 66// return h 67// } 68// 69// func fnv1a_init() -> i64 { return FNV_OFFSET_BASIS } 70// 71// func fnv1a_update(state: i64, data: *u8, n: i64) -> i64 { 72// var h: i64 = state 73// var i: i64 = 0 74// while i < n { 75// h = h ^ data[i] 76// h = h * FNV_PRIME 77// i = i + 1 78// } 79// return h 80// } 81// 82// func fnv1a_cstr(s: *u8) -> i64 { 83// var i: i64 = 0 84// while s[i] != 0 { i = i + 1 } 85// return fnv1a(s, i) 86// } 87// 88// func main() -> i64 { 89// let empty: i64 = fnv1a(0 as *u8, 0) 90// if empty != FNV_OFFSET_BASIS { return 1 } 91// let ha: i64 = fnv1a("hello", 5) 92// let hb: i64 = fnv1a("world", 5) 93// if ha == hb { return 2 } 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// }