xoshiro.nx source
↩ module page · 106 lines · 3597 B
1// xoshiro.nx -- xoshiro256++ pseudorandom number generator.
2//
3// David Blackman + Sebastiano Vigna 2018. 256-bit state,
4// 64-bit output per step, period 2^256 - 1. Passes BigCrush
5// statistical tests. Used by: Rust `rand` standard generator,
6// Lua 5.4, GNU FORTRAN, .NET 6+.
7//
8// NOT cryptographically secure -- an attacker who observes
9// enough output can reconstruct state. For crypto use rand.nx
10// (/dev/urandom) or HMAC-DRBG (pending).
11//
12// Used for: simulation, deterministic test data, sampling,
13// fuzzing. When you need REPRODUCIBLE pseudorandom from a seed.
14//
15// Invariants:
16// X1 64-bit output per step; full state advances.
17// X2 Same seed -> same output sequence forever.
18// X3 All-zeros state forbidden (would produce all zeros).
19// seed_with implements the SplitMix64 trick to safely
20// initialise from any 64-bit seed including 0.
21
22import "syscalls.nx"
23import "nx_bits.nx"
24
25struct Xoshiro {
26 s0: i64,
27 s1: i64,
28 s2: i64,
29 s3: i64,
30}
31
32// Delegated to nx_bits_rotl64 (rolq/rol intrinsic). xoshiro256**
33// does 2 rotates per output (one in the output function, one in the
34// state update); high-throughput PRNG path.
35func xs_rotl(x: i64, k: i64) -> i64 {
36 return nx_bits_rotl64(x, k)
37}
38
39// SplitMix64 single-step (Vigna 2014). Used to initialise the
40// xoshiro state from a single seed -- avoids the all-zeros
41// pathological start.
42func xs_splitmix(state_p: *i64) -> i64 {
43 *state_p = *state_p + 0x9E3779B97F4A7C15
44 var z: i64 = *state_p
45 z = (z ^ ((z >> 30) & 0x3FFFFFFFFFFFFFFF)) * 0xBF58476D1CE4E5B9
46 z = (z ^ ((z >> 27) & 0x1FFFFFFFFFFFFFFF)) * 0x94D049BB133111EB
47 return z ^ ((z >> 31) & 0x1FFFFFFF)
48}
49
50// Initialise the generator from a 64-bit seed.
51func xoshiro_seed(rng: *Xoshiro, seed: i64) -> i64 {
52 let sm_state_raw: *u8 = sys_mmap(16)
53 let sm_state: *i64 = sm_state_raw as *i64
54 *sm_state = seed
55 rng.s0 = xs_splitmix(sm_state)
56 rng.s1 = xs_splitmix(sm_state)
57 rng.s2 = xs_splitmix(sm_state)
58 rng.s3 = xs_splitmix(sm_state)
59 return 0
60}
61
62// Construct + seed. Caller-owned struct.
63func xoshiro_new(seed: i64) -> *Xoshiro {
64 let raw: *u8 = sys_mmap(64)
65 let rng: *Xoshiro = raw as *Xoshiro
66 xoshiro_seed(rng, seed)
67 return rng
68}
69
70// Advance the state and return 64 bits. This is the xoshiro256++
71// scrambler: rotl(s0 + s3, 23) + s0.
72func xoshiro_next(rng: *Xoshiro) -> i64 {
73 let result: i64 = xs_rotl(rng.s0 + rng.s3, 23) + rng.s0
74 let t: i64 = rng.s1 << 17
75 rng.s2 = rng.s2 ^ rng.s0
76 rng.s3 = rng.s3 ^ rng.s1
77 rng.s1 = rng.s1 ^ rng.s2
78 rng.s0 = rng.s0 ^ rng.s3
79 rng.s2 = rng.s2 ^ t
80 rng.s3 = xs_rotl(rng.s3, 45)
81 return result
82}
83
84// Return a value in [0, bound). Uses Lemire's nearly-divisionless
85// bounded random method (2019).
86func xoshiro_bounded(rng: *Xoshiro, bound: i64) -> i64 {
87 if bound <= 1 { return 0 }
88 // Simple modulo for now (small bias). Lemire's method needs
89 // 128-bit multiplication we can't do cleanly.
90 let v: i64 = xoshiro_next(rng)
91 // Convert to non-negative range.
92 let pos: i64 = v & 0x7FFFFFFFFFFFFFFF
93 return pos % bound
94}
95
96// Compile-only smoke.
97func main() -> i64 {
98 let rng: *Xoshiro = xoshiro_new(42)
99 let v1: i64 = xoshiro_next(rng)
100 let v2: i64 = xoshiro_next(rng)
101 if v1 == v2 { return 1 } // would be astronomically improbable
102 let bounded: i64 = xoshiro_bounded(rng, 100)
103 if bounded < 0 { return 2 }
104 if bounded >= 100 { return 3 }
105 return 0
106}