nx_random.nx source
↩ module page · 169 lines · 5215 B
1// nx_random.nx -- xoshiro256++ pseudo-random number generator.
2//
3// Used by:
4// - Fuzzing harness (nx_fuzz)
5// - Sampling / property-based testing
6// - Deterministic ID generation (UUIDv7-style)
7// - Stack-canary seeding (when nx_argv builds AT_RANDOM auxv)
8// - Hash-table key randomization (DoS-resistance)
9//
10// xoshiro256++ is the modern recommendation from Blackman + Vigna
11// (2019). Period 2^256 - 1, fast (4 ops per output), passes all
12// of TestU01 / PractRand. Better than Mersenne Twister for
13// general-purpose use.
14//
15// NOT a CSPRNG. For cryptographic randomness use the kernel
16// getrandom() syscall via nx_csprng (deferred to a separate module).
17//
18// Reference: https://prng.di.unimi.it/xoshiro256plusplus.c
19
20// nx_safety_envelope:
21// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
22// sil_target: SIL1
23// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
24// verdict: NOT_YET_EVALUATED
25
26import "syscalls.nx"
27
28struct NxRng {
29 s0: i64,
30 s1: i64,
31 s2: i64,
32 s3: i64,
33}
34
35const NX_RNG_BYTES: i64 = 32
36
37// 64-bit rotate left.
38func nx_rng_rotl(x: i64, k: i64) -> i64 {
39 let m: i64 = 0xFFFFFFFFFFFFFFFF
40 let lo: i64 = (x << k) & m
41 let hi: i64 = (x >> (64 - k)) & ((1 << (64 - k)) - 1)
42 return (lo | hi) & m
43}
44
45// SplitMix64 -- used to expand a single 64-bit seed into the four
46// state words of xoshiro256++. Vigna's recommendation.
47func nx_rng_splitmix(state_ptr: *i64) -> i64 {
48 let z0: i64 = (*state_ptr) + 0x9E3779B97F4A7C15
49 *state_ptr = z0
50 var z: i64 = z0
51 z = (z ^ ((z >> 30) & 0x3FFFFFFFFFFFFFFF)) * 0xBF58476D1CE4E5B9
52 z = (z ^ ((z >> 27) & 0x1FFFFFFFFFFFFFFF)) * 0x94D049BB133111EB
53 z = z ^ ((z >> 31) & 0x1FFFFFFFFF)
54 return z
55}
56
57// Build a fresh RNG from a seed. Uses SplitMix64 to fill all four
58// state words deterministically, so two RNGs with the same seed
59// produce identical streams.
60func nx_rng_new(seed: i64) -> *NxRng {
61 let raw: *u8 = sys_mmap(NX_RNG_BYTES)
62 let r: *NxRng = raw as *NxRng
63 let sm_raw: *u8 = sys_mmap(8)
64 let sm: *i64 = sm_raw as *i64
65 *sm = seed
66 r.s0 = nx_rng_splitmix(sm)
67 r.s1 = nx_rng_splitmix(sm)
68 r.s2 = nx_rng_splitmix(sm)
69 r.s3 = nx_rng_splitmix(sm)
70 return r
71}
72
73// One xoshiro256++ step. Returns a uniform u64 (we treat it as i64
74// in NishiLang; high bit may be set).
75func nx_rng_next(r: *NxRng) -> i64 {
76 let result: i64 = nx_rng_rotl(r.s0 + r.s3, 23) + r.s0
77 let t: i64 = (r.s1 << 17) & 0xFFFFFFFFFFFFFFFF
78 r.s2 = r.s2 ^ r.s0
79 r.s3 = r.s3 ^ r.s1
80 r.s1 = r.s1 ^ r.s2
81 r.s0 = r.s0 ^ r.s3
82 r.s2 = r.s2 ^ t
83 r.s3 = nx_rng_rotl(r.s3, 45)
84 return result
85}
86
87// Uniform random integer in [0, bound). Standard Lemire 2019
88// rejection-free method (lightly adapted). Uses the high 64 bits
89// of the 128-bit product for the bias; we do it via 32-bit halves
90// since NishiLang doesn't have u128.
91func nx_rng_below(r: *NxRng, bound: i64) -> i64 {
92 if bound <= 0 { return 0 }
93 let v: i64 = nx_rng_next(r)
94 // Use modulo for now; real Lemire requires 128-bit mul which
95 // we can't express cleanly today. Bias is < 1 part in 2^32
96 // for any sensible bound.
97 let mask: i64 = 0x7FFFFFFFFFFFFFFF
98 let pos: i64 = v & mask
99 return pos - (pos / bound) * bound
100}
101
102// Uniform random byte (0..255).
103func nx_rng_byte(r: *NxRng) -> i64 {
104 return nx_rng_next(r) & 0xFF
105}
106
107// Fill `dst[0..n]` with random bytes.
108func nx_rng_fill(r: *NxRng, dst: *u8, n: i64) -> i64 {
109 var i: i64 = 0
110 var word: i64 = 0
111 var bytes_left: i64 = 0
112 while i < n {
113 if bytes_left == 0 {
114 word = nx_rng_next(r)
115 bytes_left = 8
116 }
117 dst[i] = word & 0xFF
118 word = (word >> 8) & 0x00FFFFFFFFFFFFFF
119 bytes_left = bytes_left - 1
120 i = i + 1
121 }
122 return 0
123}
124
125// ---- self-test ---------------------------------------------------
126
127func main() -> i64 {
128 // Determinism: two RNGs with the same seed match.
129 let r1: *NxRng = nx_rng_new(42)
130 let r2: *NxRng = nx_rng_new(42)
131 var i: i64 = 0
132 while i < 10 {
133 let a: i64 = nx_rng_next(r1)
134 let b: i64 = nx_rng_next(r2)
135 if a != b { return __syscall(93, 1, 0, 0, 0, 0, 0) }
136 i = i + 1
137 }
138
139 // Different seeds -> different first output.
140 let r3: *NxRng = nx_rng_new(43)
141 let v_42: i64 = nx_rng_next(nx_rng_new(42))
142 let v_43: i64 = nx_rng_next(r3)
143 if v_42 == v_43 { return __syscall(93, 2, 0, 0, 0, 0, 0) }
144
145 // below() respects bound.
146 let r4: *NxRng = nx_rng_new(7)
147 var k: i64 = 0
148 while k < 1000 {
149 let x: i64 = nx_rng_below(r4, 100)
150 if x < 0 { return __syscall(93, 3, 0, 0, 0, 0, 0) }
151 if x >= 100 { return __syscall(93, 4, 0, 0, 0, 0, 0) }
152 k = k + 1
153 }
154
155 // fill writes n bytes.
156 let buf: *u8 = sys_mmap(64)
157 nx_rng_fill(r4, buf, 64)
158 // At least one byte should be nonzero (bit pigeonhole says yes
159 // with overwhelming probability).
160 var nonzero: i64 = 0
161 var j: i64 = 0
162 while j < 64 {
163 if buf[j] != 0 { nonzero = 1 }
164 j = j + 1
165 }
166 if nonzero == 0 { return __syscall(93, 5, 0, 0, 0, 0, 0) }
167
168 return 0
169}