1 /*
2 * random.c
3 * Copyright (C) 2009-2018 Joachim de Groot <jdegroot@web.de>
4 *
5 * NLarn is free software: you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License as published by the
7 * Free Software Foundation, either version 3 of the License, or
8 * (at your option) any later version.
9 *
10 * NLarn is distributed in the hope that it will be useful, but
11 * WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
13 * See the GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License along
16 * with this program. If not, see <http://www.gnu.org/licenses/>.
17 */
18
19 #ifdef __linux__
20 # define _XOPEN_SOURCE 700
21 #endif
22 #ifdef _WIN32
23 # define _CRT_RAND_S
24 #endif
25
26 #include <glib.h>
27 #include <stdint.h>
28 #include <stdlib.h>
29
30 #include "random.h"
31
32 /* The following code is taken from xoshiro128starstar.c,
33 * which is to be found on http://vigna.di.unimi.it/xorshift/ */
34
35 /* Written in 2018 by David Blackman and Sebastiano Vigna (vigna@acm.org)
36
37 To the extent possible under law, the author has dedicated all copyright
38 and related and neighboring rights to this software to the public domain
39 worldwide. This software is distributed without any warranty.
40
41 See <http://creativecommons.org/publicdomain/zero/1.0/>. */
42
43 /* This is xoshiro128** 1.0, our 32-bit all-purpose, rock-solid generator. It
44 has excellent (sub-ns) speed, a state size (128 bits) that is large
45 enough for mild parallelism, and it passes all tests we are aware of.
46
47 For generating just single-precision (i.e., 32-bit) floating-point
48 numbers, xoshiro128+ is even faster.
49
50 The state must be seeded so that it is not everywhere zero. */
51
52
rotl(const uint32_t x,int k)53 static inline uint32_t rotl(const uint32_t x, int k) {
54 return (x << k) | (x >> (32 - k));
55 }
56
57
58 static uint32_t s[4];
59
next(void)60 uint32_t next(void) {
61 const uint32_t result_starstar = rotl(s[0] * 5, 7) * 9;
62
63 const uint32_t t = s[1] << 9;
64
65 s[2] ^= s[0];
66 s[3] ^= s[1];
67 s[1] ^= s[2];
68 s[0] ^= s[3];
69
70 s[2] ^= t;
71
72 s[3] = rotl(s[3], 11);
73
74 return result_starstar;
75 }
76
77 /* end xoshiro128starstar.c excerpt */
78
79 static gboolean seeded = FALSE;
80
81 /* initialize RNG */
rand_seed()82 static void rand_seed()
83 {
84 g_assert(seeded == FALSE);
85
86 /* On Windows, use rand_s to seed out RNG; otherwise use random() */
87 #ifndef G_OS_WIN32
88 srandom(g_get_monotonic_time());
89 #endif
90
91 for (int i = 0; i < 4; i++)
92 {
93 #ifdef G_OS_WIN32
94 rand_s(&s[i]);
95 #else
96 s[i] = random();
97 #endif
98 }
99
100 seeded = TRUE;
101 }
102
rand_serialize()103 cJSON* rand_serialize()
104 {
105 g_assert(seeded == TRUE);
106
107 return cJSON_CreateIntArray((int*)&s, 4);
108 }
109
rand_deserialize(cJSON * r)110 void rand_deserialize(cJSON *r)
111 {
112 g_assert(r != NULL);
113 g_assert(cJSON_GetArraySize(r) == 4);
114
115 for (int i = 0; i < 4; i++)
116 {
117 cJSON* it = cJSON_GetArrayItem(r, i);
118 g_assert(cJSON_IsNumber(it));
119 s[i] = (guint64)it->valuedouble;
120 }
121
122 seeded = TRUE;
123 }
124
rand_0n(guint32 n)125 guint32 rand_0n(guint32 n)
126 {
127 if (!seeded)
128 {
129 rand_seed();
130 }
131
132 guint32 min = -n % n;
133 guint32 result;
134
135 switch (n)
136 {
137 case 0:
138 case 1:
139 return 0;
140 break;
141 case UINT32_MAX:
142 return next();
143 break;
144 default:
145 while ((result = next()) < min);
146
147 return result % n;
148 break;
149 }
150 }
151
divert(int value,int percent)152 int divert(int value, int percent)
153 {
154 int lower, upper;
155
156 g_assert(value > 0 && percent > 0);
157
158 lower = value - (value / percent);
159 upper = value + (value / percent);
160 if (lower == upper)
161 return value;
162
163 return rand_m_n(lower, upper);
164 }
165
shuffle(int array[],int length,int skip)166 void shuffle(int array[], int length, int skip)
167 {
168 for (int i = 0; i < length; i++)
169 {
170 /* fill the array in order */
171 array[i] = i;
172 }
173
174 for (int i = skip; i < (length / 2); i++)
175 {
176 /* randomize positions */
177 int npos = i + rand_0n(length - i);
178 int temp = array[i];
179 array[i] = array[npos];
180 array[npos] = temp;
181 }
182 }
183
184