1 /*
2 * Copyright (c) 2025 Apple Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28
29 #include "random.h"
30
31 #include <machine/machine_routines.h>
32
33 // written in 2015 by Sebastiano Vigna https://prng.di.unimi.it/splitmix64.c
34 static inline uint64_t
splitmix64_next(uint64_t * state)35 splitmix64_next(uint64_t *state)
36 {
37 uint64_t z = (*state += 0x9e3779b97f4a7c15);
38 z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
39 z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
40 return z ^ (z >> 31);
41 }
42
43 static inline uint64_t
rotl64(uint64_t x,int8_t r)44 rotl64(uint64_t x, int8_t r)
45 {
46 return (x << r) | (x >> (64 - r));
47 }
48
49 // fast alternative to x % n
50 static inline uint64_t
fast_bound(uint64_t x,uint64_t n)51 fast_bound(uint64_t x, uint64_t n)
52 {
53 uint128_t mul = (uint128_t)x * (uint128_t)n;
54 return (uint64_t)(mul >> 64);
55 }
56
57 // initial state as if random_set_seed(1337) was called
58 uint64_t romuduojr_x_state = 13161956497586561035ull;
59 uint64_t romuduojr_y_state = 14663483216071361993ull;
60
61 void
random_set_seed(uint64_t seed)62 random_set_seed(uint64_t seed)
63 {
64 romuduojr_x_state = splitmix64_next(&seed);
65 romuduojr_y_state = splitmix64_next(&seed);
66 }
67
68 uint64_t
random_next(void)69 random_next(void)
70 {
71 const uint64_t xp = romuduojr_x_state;
72 romuduojr_x_state = 15241094284759029579ull * romuduojr_y_state;
73 romuduojr_y_state = romuduojr_y_state - xp;
74 romuduojr_y_state = rotl64(romuduojr_y_state, 27);
75 return xp;
76 }
77
78 uint64_t
random_below(uint64_t upper_bound)79 random_below(uint64_t upper_bound)
80 {
81 return fast_bound(random_next(), upper_bound);
82 }
83