1/*
2 * *****************************************************************************
3 *
4 * Parts of this code are adapted from the following:
5 *
6 * PCG, A Family of Better Random Number Generators.
7 *
8 * You can find the original source code at:
9 *   https://github.com/imneme/pcg-c
10 *
11 * -----------------------------------------------------------------------------
12 *
13 * This code is under the following license:
14 *
15 * Copyright (c) 2014-2017 Melissa O'Neill and PCG Project contributors
16 * Copyright (c) 2018-2021 Gavin D. Howard and contributors.
17 *
18 * Permission is hereby granted, free of charge, to any person obtaining a copy
19 * of this software and associated documentation files (the "Software"), to deal
20 * in the Software without restriction, including without limitation the rights
21 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
22 * copies of the Software, and to permit persons to whom the Software is
23 * furnished to do so, subject to the following conditions:
24 *
25 * The above copyright notice and this permission notice shall be included in
26 * all copies or substantial portions of the Software.
27 *
28 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
29 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
30 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
31 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
32 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
33 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
34 * SOFTWARE.
35 *
36 * *****************************************************************************
37 *
38 * Code for the RNG.
39 *
40 */
41
42#include <assert.h>
43#include <stdlib.h>
44#include <string.h>
45#include <time.h>
46#include <fcntl.h>
47
48#ifndef _WIN32
49#include <unistd.h>
50#else // _WIN32
51#include <Windows.h>
52#include <bcrypt.h>
53#endif // _WIN32
54
55#include <status.h>
56#include <rand.h>
57#include <vm.h>
58
59#if BC_ENABLE_EXTRA_MATH && BC_ENABLE_RAND
60
61#if !BC_RAND_BUILTIN
62
63static BcRandState bc_rand_addition(uint_fast64_t a, uint_fast64_t b) {
64
65	BcRandState res;
66
67	res.lo = a + b;
68	res.hi = (res.lo < a);
69
70	return res;
71}
72
73static BcRandState bc_rand_addition2(BcRandState a, BcRandState b) {
74
75	BcRandState temp, res;
76
77	res = bc_rand_addition(a.lo, b.lo);
78	temp = bc_rand_addition(a.hi, b.hi);
79	res.hi += temp.lo;
80
81	return res;
82}
83
84static BcRandState bc_rand_multiply(uint_fast64_t a, uint_fast64_t b) {
85
86	uint_fast64_t al, ah, bl, bh, c0, c1, c2, c3;
87	BcRandState carry, res;
88
89	al = BC_RAND_TRUNC32(a);
90	ah = BC_RAND_CHOP32(a);
91	bl = BC_RAND_TRUNC32(b);
92	bh = BC_RAND_CHOP32(b);
93
94	c0 = al * bl;
95	c1 = al * bh;
96	c2 = ah * bl;
97	c3 = ah * bh;
98
99	carry = bc_rand_addition(c1, c2);
100
101	res = bc_rand_addition(c0, (BC_RAND_TRUNC32(carry.lo)) << 32);
102	res.hi += BC_RAND_CHOP32(carry.lo) + c3 + (carry.hi << 32);
103
104	return res;
105}
106
107static BcRandState bc_rand_multiply2(BcRandState a, BcRandState b) {
108
109	BcRandState c0, c1, c2, carry;
110
111	c0 = bc_rand_multiply(a.lo, b.lo);
112	c1 = bc_rand_multiply(a.lo, b.hi);
113	c2 = bc_rand_multiply(a.hi, b.lo);
114
115	carry = bc_rand_addition2(c1, c2);
116	carry.hi = carry.lo;
117	carry.lo = 0;
118
119	return bc_rand_addition2(c0, carry);
120}
121
122#endif // BC_RAND_BUILTIN
123
124static void bc_rand_setModified(BcRNGData *r) {
125
126#if BC_RAND_BUILTIN
127	r->inc |= (BcRandState) 1UL;
128#else // BC_RAND_BUILTIN
129	r->inc.lo |= (uint_fast64_t) 1UL;
130#endif // BC_RAND_BUILTIN
131}
132
133static void bc_rand_clearModified(BcRNGData *r) {
134
135#if BC_RAND_BUILTIN
136	r->inc &= ~((BcRandState) 1UL);
137#else // BC_RAND_BUILTIN
138	r->inc.lo &= ~(1UL);
139#endif // BC_RAND_BUILTIN
140}
141
142static void bc_rand_copy(BcRNGData *d, BcRNGData *s) {
143	bool unmod = BC_RAND_NOTMODIFIED(d);
144	memcpy(d, s, sizeof(BcRNGData));
145	if (!unmod) bc_rand_setModified(d);
146	else if (!BC_RAND_NOTMODIFIED(s)) bc_rand_clearModified(d);
147}
148
149#ifndef _WIN32
150static ulong bc_rand_frand(void* ptr) {
151
152	ulong buf[1];
153	int fd;
154	ssize_t nread;
155
156	assert(ptr != NULL);
157
158	fd = *((int*)ptr);
159
160	nread = read(fd, buf, sizeof(ulong));
161
162	if (BC_ERR(nread != sizeof(ulong))) bc_vm_fatalError(BC_ERR_FATAL_IO_ERR);
163
164	return *((ulong*)buf);
165}
166#else // _WIN32
167static ulong bc_rand_winrand(void* ptr) {
168
169	ulong buf[1];
170	NTSTATUS s;
171
172	BC_UNUSED(ptr);
173
174	buf[0] = 0;
175
176	s = BCryptGenRandom(NULL, (char*) buf, sizeof(ulong), BCRYPT_USE_SYSTEM_PREFERRED_RNG);
177
178	if (BC_ERR(!BCRYPT_SUCCESS(s))) buf[0] = 0;
179
180	return buf[0];
181}
182#endif // _WIN32
183
184static ulong bc_rand_rand(void *ptr) {
185
186	size_t i;
187	ulong res = 0;
188
189	BC_UNUSED(ptr);
190
191	for (i = 0; i < sizeof(ulong); ++i)
192		res |= ((ulong) (rand() & BC_RAND_SRAND_BITS)) << (i * CHAR_BIT);
193
194	return res;
195}
196
197static BcRandState bc_rand_inc(BcRNGData *r) {
198
199	BcRandState inc;
200
201#if BC_RAND_BUILTIN
202	inc = r->inc | 1;
203#else // BC_RAND_BUILTIN
204	inc.lo = r->inc.lo | 1;
205	inc.hi = r->inc.hi;
206#endif // BC_RAND_BUILTIN
207
208	return inc;
209}
210
211static void bc_rand_setInc(BcRNGData *r) {
212
213#if BC_RAND_BUILTIN
214	r->inc <<= 1UL;
215#else // BC_RAND_BUILTIN
216	r->inc.hi <<= 1UL;
217	r->inc.hi |= (r->inc.lo & (1UL << (BC_LONG_BIT - 1))) >> (BC_LONG_BIT - 1);
218	r->inc.lo <<= 1UL;
219#endif // BC_RAND_BUILTIN
220}
221
222static void bc_rand_seedState(BcRandState *state, ulong val1, ulong val2) {
223
224#if BC_RAND_BUILTIN
225	*state = ((BcRandState) val1) | ((BcRandState) val2) << (BC_LONG_BIT);
226#else // BC_RAND_BUILTIN
227	state->lo = val1;
228	state->hi = val2;
229#endif // BC_RAND_BUILTIN
230}
231
232static void bc_rand_seedRNG(BcRNGData *r, ulong state1, ulong state2,
233                            ulong inc1, ulong inc2)
234{
235	bc_rand_seedState(&r->state, state1, state2);
236	bc_rand_seedState(&r->inc, inc1, inc2);
237	bc_rand_setInc(r);
238}
239
240static void bc_rand_fill(BcRNGData *r, BcRandUlong fulong, void *ptr) {
241
242	ulong state1, state2, inc1, inc2;
243
244	state1 = fulong(ptr);
245	state2 = fulong(ptr);
246
247	inc1 = fulong(ptr);
248	inc2 = fulong(ptr);
249
250	bc_rand_seedRNG(r, state1, state2, inc1, inc2);
251}
252
253static void bc_rand_step(BcRNGData *r) {
254	BcRandState temp = bc_rand_mul2(r->state, bc_rand_multiplier);
255	r->state = bc_rand_add2(temp, bc_rand_inc(r));
256}
257
258static BcRand bc_rand_output(BcRNGData *r) {
259	return BC_RAND_ROT(BC_RAND_FOLD(r->state), BC_RAND_ROTAMT(r->state));
260}
261
262static void bc_rand_seedZeroes(BcRNG *r, BcRNGData *rng, size_t idx) {
263
264	BcRNGData *rng2;
265
266	if (r->v.len <= idx) return;
267
268	rng2 = bc_vec_item_rev(&r->v, idx);
269
270	if (BC_RAND_ZERO(rng2)) {
271		size_t i;
272		for (i = 1; i < r->v.len; ++i)
273			bc_rand_copy(bc_vec_item_rev(&r->v, i), rng);
274	}
275}
276
277void bc_rand_srand(BcRNGData *rng) {
278
279	int fd = 0;
280
281	BC_SIG_LOCK;
282
283#ifndef _WIN32
284	fd = open("/dev/urandom", O_RDONLY);
285
286	if (BC_NO_ERR(fd >= 0)) {
287		bc_rand_fill(rng, bc_rand_frand, &fd);
288		close(fd);
289	}
290	else {
291
292		fd = open("/dev/random", O_RDONLY);
293
294		if (BC_NO_ERR(fd >= 0)) {
295			bc_rand_fill(rng, bc_rand_frand, &fd);
296			close(fd);
297		}
298	}
299#else // _WIN32
300	bc_rand_fill(rng, bc_rand_winrand, NULL);
301#endif // _WIN32
302
303	while (BC_ERR(BC_RAND_ZERO(rng))) bc_rand_fill(rng, bc_rand_rand, NULL);
304
305	BC_SIG_UNLOCK;
306}
307
308static void bc_rand_propagate(BcRNG *r, BcRNGData *rng) {
309
310	if (r->v.len <= 1) return;
311
312	if (BC_RAND_NOTMODIFIED(rng)) {
313
314		size_t i;
315		bool go = true;
316
317		for (i = 1; go && i < r->v.len; ++i) {
318			BcRNGData *rng2 = bc_vec_item_rev(&r->v, i);
319			go = BC_RAND_NOTMODIFIED(rng2);
320			bc_rand_copy(rng2, rng);
321		}
322
323		bc_rand_seedZeroes(r, rng, i);
324	}
325	else bc_rand_seedZeroes(r, rng, 1);
326}
327
328BcRand bc_rand_int(BcRNG *r) {
329
330	BcRNGData *rng = bc_vec_top(&r->v);
331
332	if (BC_ERR(BC_RAND_ZERO(rng))) bc_rand_srand(rng);
333
334	bc_rand_step(rng);
335	bc_rand_propagate(r, rng);
336
337	return bc_rand_output(rng);
338}
339
340BcRand bc_rand_bounded(BcRNG *r, BcRand bound) {
341
342	BcRand rand, threshold = (0 - bound) % bound;
343
344	do {
345		rand = bc_rand_int(r);
346	} while (rand < threshold);
347
348	return rand % bound;
349}
350
351void bc_rand_seed(BcRNG *r, ulong state1, ulong state2, ulong inc1, ulong inc2)
352{
353	BcRNGData *rng = bc_vec_top(&r->v);
354
355	bc_rand_seedState(&rng->inc, inc1, inc2);
356	bc_rand_setInc(rng);
357	bc_rand_setModified(rng);
358
359	if (!state1 && !state2) {
360		memcpy(&rng->state, &rng->inc, sizeof(BcRandState));
361		bc_rand_step(rng);
362	}
363	else bc_rand_seedState(&rng->state, state1, state2);
364
365	bc_rand_propagate(r, rng);
366}
367
368static BcRandState bc_rand_getInc(BcRNGData *r) {
369
370	BcRandState res;
371
372#if BC_RAND_BUILTIN
373	res = r->inc >> 1;
374#else // BC_RAND_BUILTIN
375	res = r->inc;
376	res.lo >>= 1;
377	res.lo |= (res.hi & 1) << (BC_LONG_BIT - 1);
378	res.hi >>= 1;
379#endif // BC_RAND_BUILTIN
380
381	return res;
382}
383
384void bc_rand_getRands(BcRNG *r, BcRand *s1, BcRand *s2, BcRand *i1, BcRand *i2)
385{
386	BcRandState inc;
387	BcRNGData *rng = bc_vec_top(&r->v);
388
389	if (BC_ERR(BC_RAND_ZERO(rng))) bc_rand_srand(rng);
390
391	inc = bc_rand_getInc(rng);
392
393	*s1 = BC_RAND_TRUNC(rng->state);
394	*s2 = BC_RAND_CHOP(rng->state);
395
396	*i1 = BC_RAND_TRUNC(inc);
397	*i2 = BC_RAND_CHOP(inc);
398}
399
400void bc_rand_push(BcRNG *r) {
401	BcRNGData rng;
402	memset(&rng, 0, sizeof(BcRNGData));
403	if (r->v.len > 0) bc_rand_copy(&rng, bc_vec_top(&r->v));
404	bc_vec_push(&r->v, &rng);
405}
406
407void bc_rand_pop(BcRNG *r, bool reset) {
408	bc_vec_npop(&r->v, reset ? r->v.len - 1 : 1);
409}
410
411void bc_rand_init(BcRNG *r) {
412	BC_SIG_ASSERT_LOCKED;
413	bc_vec_init(&r->v, sizeof(BcRNGData), NULL);
414	bc_rand_push(r);
415}
416
417#ifndef NDEBUG
418void bc_rand_free(BcRNG *r) {
419	BC_SIG_ASSERT_LOCKED;
420	bc_vec_free(&r->v);
421}
422#endif // NDEBUG
423
424#endif // BC_ENABLE_EXTRA_MATH && BC_ENABLE_RAND
425