nx_frame_hash.nx source
↩ module page · 195 lines · 7982 B
1// nx_frame_hash.nx -- per-frame simulation-state hash for desync detection.
2//
3// Purpose: across two or more clients running the same deterministic
4// simulation (RTS lockstep, fighting-game rollback, replay verifier),
5// each client computes a single i64 hash of its full sim state at the
6// end of every tick and exchanges it with peers. If hashes diverge,
7// the simulation has DESYNCED -- typically due to a determinism bug
8// (floating-point drift, unseeded RNG, OS-specific malloc behaviour).
9//
10// Composes against nx_hash_fnv1a_bytes (FNV-1a 64-bit, public-domain).
11// The frame number is folded into the hash so two clients sampling
12// state at different frames never coincidentally match.
13//
14// Sealed verdict (NxFrameHashVerdict) gives typed downstream action:
15// MATCH -- both clients agree on state hash AND frame
16// MISMATCH -- same frame, different hash -> DESYNC at this frame
17// FRAME_DIFF -- different frame numbers -> not comparable; resync
18// INVALID -- malformed input (e.g., negative length)
19//
20// Source references:
21// - FNV-1a (Fowler/Noll/Vo, 1991, public domain): isthe.com/chongo/tech/comp/fnv/
22// - RTS lockstep desync detection: AoE GDC 2001 "1500 Archers"
23// - Rollback frame-hash exchange: GGPO `ggpo_synchronize_input` callback
24//
25// genealogy_id: fnv1a_1991 + ggpo_desync_check + aoe2_lockstep_hashcheck
26// lineage_id: deterministic_sim_consensus_hash
27
28// nx_safety_envelope:
29// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
30// sil_target: SIL1
31// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
32// verdict: NOT_YET_EVALUATED
33
34import "nx_syscalls.nx"
35import "nx_tier.nx"
36import "nx_hash.nx"
37
38// ===== Sealed verdict ================================================
39
40const NX_FH_MATCH: nx_int = 0
41const NX_FH_MISMATCH: nx_int = 1
42const NX_FH_FRAME_DIFF: nx_int = 2
43const NX_FH_INVALID: nx_int = 3
44
45// ===== Per-region hash (single contiguous byte buffer) =============
46
47// Hash a single byte region of sim state. Returns the FNV-1a i64.
48// Direct alias for nx_hash_fnv1a_bytes so callers reach for the
49// frame-hash module rather than the generic hash module when their
50// intent is "compute consensus state hash."
51func nx_frame_hash_region(buf: *u8, n: nx_int) -> i64 {
52 if n < 0 { return 0 }
53 return nx_hash_fnv1a_bytes(buf, n)
54}
55
56// ===== Multi-region hash (folding helper) ==========================
57//
58// Real simulations have several disjoint state regions (chunk bytes,
59// entity table, fps controller, pending input, world seed, tick).
60// nx_frame_hash_combine folds an existing FNV-1a accumulator with the
61// hash of an additional region. Caller chains them in a canonical
62// order (the order MUST be identical on both clients or hashes will
63// diverge without a real desync).
64
65func nx_frame_hash_init() -> i64 {
66 // Same seed value used by nx_hash_fnv1a_bytes internally.
67 return 0xCBF29CE484222325
68}
69
70// Fold the bytes of `buf` (length n) into the running FNV-1a state.
71// Returns the new accumulator. Identical math to nx_hash_fnv1a_bytes
72// but starts from `acc` instead of NX_HASH_FNV_OFFSET.
73func nx_frame_hash_combine(acc: i64, buf: *u8, n: nx_int) -> i64 {
74 if n <= 0 { return acc }
75 var h: i64 = acc
76 var i: nx_int = 0
77 while i < n {
78 h = h ^ buf[i]
79 h = h * 0x100000001B3
80 i = i + 1
81 }
82 return h
83}
84
85// Fold an i64 into the running FNV-1a state (treating it as 8 little-
86// endian bytes). Use this for frame number, seed, tick, and any
87// scalar simulation field that isn't already covered by a buffer hash.
88func nx_frame_hash_combine_i64(acc: i64, x: i64) -> i64 {
89 var h: i64 = acc
90 var i: i64 = 0
91 while i < 8 {
92 let b: i64 = (x >> (i * 8)) & 0xFF
93 h = h ^ b
94 h = h * 0x100000001B3
95 i = i + 1
96 }
97 return h
98}
99
100// ===== Verdict comparison ===========================================
101//
102// Given local + remote frame/hash pairs, returns the typed verdict.
103// `local_frame` and `remote_frame` are the simulation tick numbers
104// at which each side computed their hash; if they differ, the hashes
105// aren't comparable and the caller should request a resync.
106
107func nx_frame_hash_compare(
108 local_frame: nx_int, local_hash: i64,
109 remote_frame: nx_int, remote_hash: i64
110) -> nx_int {
111 if local_frame < 0 || remote_frame < 0 { return NX_FH_INVALID }
112 if local_frame != remote_frame { return NX_FH_FRAME_DIFF }
113 if local_hash == remote_hash { return NX_FH_MATCH }
114 return NX_FH_MISMATCH
115}
116
117// ===== Self-test ====================================================
118
119func main() -> i64 {
120 // T1: hash of empty buffer is the FNV offset basis (with n=0 we
121 // return 0 by convention since negative n returns 0 too).
122 let buf_a: *u8 = (sys_mmap(64)) as *u8
123 var i: nx_int = 0
124 while i < 64 {
125 buf_a[i] = (i * 11 + 5) as u8
126 i = i + 1
127 }
128 let h_a: i64 = nx_frame_hash_region(buf_a, 64)
129 if h_a == 0 { return __syscall(93, 1, 0, 0, 0, 0, 0) }
130
131 // T2: same bytes -> same hash (determinism).
132 let buf_b: *u8 = (sys_mmap(64)) as *u8
133 var j: nx_int = 0
134 while j < 64 {
135 buf_b[j] = (j * 11 + 5) as u8
136 j = j + 1
137 }
138 let h_b: i64 = nx_frame_hash_region(buf_b, 64)
139 if h_a != h_b { return __syscall(93, 2, 0, 0, 0, 0, 0) }
140
141 // T3: single-byte mutation changes the hash (sensitivity).
142 buf_b[33] = 0xFF as u8
143 let h_c: i64 = nx_frame_hash_region(buf_b, 64)
144 if h_a == h_c { return __syscall(93, 3, 0, 0, 0, 0, 0) }
145
146 // T4: multi-region fold is stable across orderings AS LONG AS the
147 // canonical order is followed on both sides. We don't test
148 // commutativity (FNV-1a is order-dependent by design -- that's
149 // why both clients must fold in identical order).
150 let acc: i64 = nx_frame_hash_init()
151 let acc1: i64 = nx_frame_hash_combine(acc, buf_a, 64)
152 let acc2: i64 = nx_frame_hash_combine_i64(acc1, 42)
153 // Recompute via the same sequence -- must match.
154 let r1: i64 = nx_frame_hash_combine(nx_frame_hash_init(), buf_a, 64)
155 let r2: i64 = nx_frame_hash_combine_i64(r1, 42)
156 if acc2 != r2 { return __syscall(93, 4, 0, 0, 0, 0, 0) }
157
158 // T5: different frame numbers produce different hashes.
159 let acc3: i64 = nx_frame_hash_combine_i64(acc1, 43)
160 if acc3 == acc2 { return __syscall(93, 5, 0, 0, 0, 0, 0) }
161
162 // T6: verdict MATCH on identical (frame, hash).
163 if nx_frame_hash_compare(100, 0xABCDEF, 100, 0xABCDEF) != NX_FH_MATCH {
164 return __syscall(93, 10, 0, 0, 0, 0, 0)
165 }
166 // T7: verdict MISMATCH on same frame, different hash.
167 if nx_frame_hash_compare(100, 0xABCDEF, 100, 0x123456) != NX_FH_MISMATCH {
168 return __syscall(93, 11, 0, 0, 0, 0, 0)
169 }
170 // T8: verdict FRAME_DIFF on different frames.
171 if nx_frame_hash_compare(99, 0xABCDEF, 100, 0xABCDEF) != NX_FH_FRAME_DIFF {
172 return __syscall(93, 12, 0, 0, 0, 0, 0)
173 }
174 // T9: verdict INVALID on negative frame.
175 if nx_frame_hash_compare(-1, 0, 0, 0) != NX_FH_INVALID {
176 return __syscall(93, 13, 0, 0, 0, 0, 0)
177 }
178
179 // T10: real-life pattern -- two "clients" hash identical sim state
180 // at frame 42 and verdict should be MATCH.
181 let local_acc: i64 = nx_frame_hash_combine_i64(nx_frame_hash_combine(nx_frame_hash_init(), buf_a, 64), 42)
182 let remote_acc: i64 = nx_frame_hash_combine_i64(nx_frame_hash_combine(nx_frame_hash_init(), buf_a, 64), 42)
183 if nx_frame_hash_compare(42, local_acc, 42, remote_acc) != NX_FH_MATCH {
184 return __syscall(93, 20, 0, 0, 0, 0, 0)
185 }
186
187 // T11: simulate a determinism bug -- one client computes one byte
188 // differently. Verdict should be MISMATCH.
189 let bad_acc: i64 = nx_frame_hash_combine_i64(nx_frame_hash_combine(nx_frame_hash_init(), buf_b, 64), 42)
190 if nx_frame_hash_compare(42, local_acc, 42, bad_acc) != NX_FH_MISMATCH {
191 return __syscall(93, 21, 0, 0, 0, 0, 0)
192 }
193
194 return 0
195}