xref: /netbsd-src/external/mpl/bind/dist/lib/isc/random.c (revision f0fde9902fd4d72ded2807793acc7bfaa1ebf243)
1 /*	$NetBSD: random.c,v 1.5 2021/02/19 16:42:19 christos Exp $	*/
2 
3 /*
4  * Copyright (C) Internet Systems Consortium, Inc. ("ISC")
5  *
6  * This Source Code Form is subject to the terms of the Mozilla Public
7  * License, v. 2.0. If a copy of the MPL was not distributed with this
8  * file, you can obtain one at https://mozilla.org/MPL/2.0/.
9  *
10  * See the COPYRIGHT file distributed with this work for additional
11  * information regarding copyright ownership.
12  */
13 
14 /*
15  * Portions of isc_random_uniform():
16  *
17  * Copyright (c) 1996, David Mazieres <dm@uun.org>
18  * Copyright (c) 2008, Damien Miller <djm@openbsd.org>
19  *
20  * Permission to use, copy, modify, and distribute this software for any
21  * purpose with or without fee is hereby granted, provided that the above
22  * copyright notice and this permission notice appear in all copies.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
25  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
26  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
27  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
28  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
29  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
30  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
31  */
32 
33 #include <inttypes.h>
34 #include <stdlib.h>
35 #include <string.h>
36 #include <unistd.h>
37 
38 #include <isc/once.h>
39 #include <isc/platform.h>
40 #include <isc/random.h>
41 #include <isc/result.h>
42 #include <isc/thread.h>
43 #include <isc/types.h>
44 #include <isc/util.h>
45 
46 #include "entropy_private.h"
47 
48 /*
49  * The specific implementation for PRNG is included as a C file
50  * that has to provide a static variable named seed, and a function
51  * uint32_t next(void) that provides next random number.
52  *
53  * The implementation must be thread-safe.
54  */
55 
56 /*
57  * Two contestants have been considered: the xoroshiro family of the
58  * functions by Villa&Blackman, and PCG by O'Neill.  After
59  * consideration, the xoshiro128starstar function has been chosen as
60  * the uint32_t random number provider because it is very fast and has
61  * good enough properties for our usage pattern.
62  */
63 #include "xoshiro128starstar.c"
64 
65 ISC_THREAD_LOCAL isc_once_t isc_random_once = ISC_ONCE_INIT;
66 
67 static void
68 isc_random_initialize(void) {
69 	int useed[4] = { 0, 0, 0, 1 };
70 #if FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
71 	/*
72 	 * Set a constant seed to help in problem reproduction should fuzzing
73 	 * find a crash or a hang.  The seed array must be non-zero else
74 	 * xoshiro128starstar will generate an infinite series of zeroes.
75 	 */
76 #else  /* if FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION */
77 	isc_entropy_get(useed, sizeof(useed));
78 #endif /* if FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION */
79 	memmove(seed, useed, sizeof(seed));
80 }
81 
82 uint8_t
83 isc_random8(void) {
84 	RUNTIME_CHECK(isc_once_do(&isc_random_once, isc_random_initialize) ==
85 		      ISC_R_SUCCESS);
86 	return (next() & 0xff);
87 }
88 
89 uint16_t
90 isc_random16(void) {
91 	RUNTIME_CHECK(isc_once_do(&isc_random_once, isc_random_initialize) ==
92 		      ISC_R_SUCCESS);
93 	return (next() & 0xffff);
94 }
95 
96 uint32_t
97 isc_random32(void) {
98 	RUNTIME_CHECK(isc_once_do(&isc_random_once, isc_random_initialize) ==
99 		      ISC_R_SUCCESS);
100 	return (next());
101 }
102 
103 void
104 isc_random_buf(void *buf, size_t buflen) {
105 	int i;
106 	uint32_t r;
107 
108 	REQUIRE(buf != NULL);
109 	REQUIRE(buflen > 0);
110 
111 	RUNTIME_CHECK(isc_once_do(&isc_random_once, isc_random_initialize) ==
112 		      ISC_R_SUCCESS);
113 
114 	for (i = 0; i + sizeof(r) <= buflen; i += sizeof(r)) {
115 		r = next();
116 		memmove((uint8_t *)buf + i, &r, sizeof(r));
117 	}
118 	r = next();
119 	memmove((uint8_t *)buf + i, &r, buflen % sizeof(r));
120 	return;
121 }
122 
123 uint32_t
124 isc_random_uniform(uint32_t upper_bound) {
125 	/* Copy of arc4random_uniform from OpenBSD */
126 	uint32_t r, min;
127 
128 	RUNTIME_CHECK(isc_once_do(&isc_random_once, isc_random_initialize) ==
129 		      ISC_R_SUCCESS);
130 
131 	if (upper_bound < 2) {
132 		return (0);
133 	}
134 
135 #if (ULONG_MAX > 0xffffffffUL)
136 	min = 0x100000000UL % upper_bound;
137 #else  /* if (ULONG_MAX > 0xffffffffUL) */
138 	/* Calculate (2**32 % upper_bound) avoiding 64-bit math */
139 	if (upper_bound > 0x80000000) {
140 		min = 1 + ~upper_bound; /* 2**32 - upper_bound */
141 	} else {
142 		/* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */
143 		min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound;
144 	}
145 #endif /* if (ULONG_MAX > 0xffffffffUL) */
146 
147 	/*
148 	 * This could theoretically loop forever but each retry has
149 	 * p > 0.5 (worst case, usually far better) of selecting a
150 	 * number inside the range we need, so it should rarely need
151 	 * to re-roll.
152 	 */
153 	for (;;) {
154 		r = next();
155 		if (r >= min) {
156 			break;
157 		}
158 	}
159 
160 	return (r % upper_bound);
161 }
162