[apple/libc.git] / gen / FreeBSD / arc4random.c

/*
 * Copyright (c) 1996, David Mazieres <dm@uun.org>
 * Copyright (c) 2008, Damien Miller <djm@openbsd.org>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

/*
 * Arc4 random number generator for OpenBSD.
 *
 * This code is derived from section 17.1 of Applied Cryptography,
 * second edition, which describes a stream cipher allegedly
 * compatible with RSA Labs "RC4" cipher (the actual description of
 * which is a trade secret).  The same algorithm is used as a stream
 * cipher called "arcfour" in Tatu Ylonen's ssh package.
 *
 * Here the stream cipher has been modified always to include the time
 * when initializing the state.  That makes it impossible to
 * regenerate the same random sequence twice, so this can't be used
 * for encryption, but will generate good random numbers.
 *
 * RC4 is a registered trademark of RSA Laboratories.
 */

#include <sys/cdefs.h>
__FBSDID("$FreeBSD: src/lib/libc/gen/arc4random.c,v 1.25 2008/09/09 09:46:36 ache Exp $");

#include <sys/types.h>
#include <sys/time.h>
#include <sys/param.h>
#include <sys/random.h>
#include <fcntl.h>
#include <unistd.h>
#include <pthread.h>

#include <TargetConditionals.h>
#if !TARGET_OS_DRIVERKIT
#define OS_CRASH_ENABLE_EXPERIMENTAL_LIBTRACE 1
#endif
#include <os/assumes.h>
#include <os/lock.h>

#include "string.h"
#include "libc_private.h"

#if defined(__APPLE__) && !defined(VARIANT_STATIC)
#include <corecrypto/ccrng.h>

static struct ccrng_state *rng;

static void
arc4_init(void)
{
	int err;

	if (rng != NULL) return;

	rng = ccrng(&err);
	if (rng == NULL) {
#if OS_CRASH_ENABLE_EXPERIMENTAL_LIBTRACE
		os_crash("arc4random: unable to get ccrng() handle (%d)", err);
#else
		os_crash("arc4random: unable to get ccrng() handle");
#endif
	}
}

void
arc4random_addrandom(__unused u_char *dat, __unused int datlen)
{
	/* NOP - deprecated */
}

uint32_t
arc4random(void)
{
	uint32_t rand;

	arc4random_buf(&rand, sizeof(rand));

	return rand;
}

void
arc4random_buf(void *buf, size_t buf_size)
{
	arc4_init();
	ccrng_generate(rng, buf_size, buf);
}

void
arc4random_stir(void)
{
	/* NOP */
}

uint32_t
arc4random_uniform(uint32_t upper_bound)
{
	uint64_t rand;

	arc4_init();
	ccrng_uniform(rng, upper_bound, &rand);

	return (uint32_t)rand;
}

__private_extern__ void
_arc4_fork_child(void)
{
	/* NOP */
}

#else /* __APPLE__ && !VARIANT_STATIC */

#define	RANDOMDEV	"/dev/random"

static void
_my_getentropy(uint8_t *buf, size_t size){
    int fd;
	ssize_t ret;
	if (getentropy(buf, size) == 0) {
		return;
	}

	// The above should never fail, but we'll try /dev/random anyway
	fd = open(RANDOMDEV, O_RDONLY, 0);
	if (fd == -1) {
#if !defined(VARIANT_STATIC)
		os_crash("arc4random: unable to open /dev/random");
#else
		abort();
#endif
	}
shortread:
	ret = read(fd, buf, size);
	if (ret == -1) {
#if !defined(VARIANT_STATIC)
		os_crash("arc4random: unable to read from /dev/random");
#else
		abort();
#endif
	} else if ((size_t)ret < size) {
		size -= (size_t)ret;
		buf += ret;
		goto shortread;
	}
	(void)close(fd);
}

struct arc4_stream {
	u_int8_t i;
	u_int8_t j;
	u_int8_t s[256];
};

#define KEYSIZE		128

static struct arc4_stream rs = {
	.i = 0,
	.j = 0,
	.s = {
		  0,   1,   2,   3,   4,   5,   6,   7,   8,   9,  10,  11,  12,  13,  14,  15,
		 16,  17,  18,  19,  20,  21,  22,  23,  24,  25,  26,  27,  28,  29,  30,  31,
		 32,  33,  34,  35,  36,  37,  38,  39,  40,  41,  42,  43,  44,  45,  46,  47,
		 48,  49,  50,  51,  52,  53,  54,  55,  56,  57,  58,  59,  60,  61,  62,  63,
		 64,  65,  66,  67,  68,  69,  70,  71,  72,  73,  74,  75,  76,  77,  78,  79,
		 80,  81,  82,  83,  84,  85,  86,  87,  88,  89,  90,  91,  92,  93,  94,  95,
		 96,  97,  98,  99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111,
		112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127,
		128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143,
		144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159,
		160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175,
		176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191,
		192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207,
		208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223,
		224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239,
		240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255
	}
};
static int rs_stired;

static inline u_int8_t arc4_getbyte(void);
static void arc4_stir(void);

static struct {
	struct timeval	tv;
	pid_t		pid;
	u_int8_t	rnd[KEYSIZE];
} rdat;
static volatile int rs_data_available = 0;

static inline void
arc4_addrandom(u_char *dat, int datlen)
{
	int     n;
	u_int8_t si;

	rs.i--;
	for (n = 0; n < 256; n++) {
		rs.i = (rs.i + 1);
		si = rs.s[rs.i];
		rs.j = (rs.j + si + dat[n % datlen]);
		rs.s[rs.i] = rs.s[rs.j];
		rs.s[rs.j] = si;
	}
	rs.j = rs.i;
}

static void
arc4_fetch(void)
{
	_my_getentropy((uint8_t*)&rdat, KEYSIZE);
}

static os_unfair_lock arc4_lock = OS_UNFAIR_LOCK_INIT;
static int arc4_count;

static void
arc4_stir(void)
{
	int n;
	/*
	 * If we don't have data, we need some now before we can integrate
	 * it into the static buffers
	 */
	if (!rs_data_available)
	{
		arc4_fetch();
	}
	rs_data_available = 0;
	__sync_synchronize();

	arc4_addrandom((u_char *)&rdat, KEYSIZE);

	/*
	 * Throw away the first N bytes of output, as suggested in the
	 * paper "Weaknesses in the Key Scheduling Algorithm of RC4"
	 * by Fluher, Mantin, and Shamir.  N=1024 is based on
	 * suggestions in the paper "(Not So) Random Shuffles of RC4"
	 * by Ilya Mironov.
	 */
	for (n = 0; n < 1024; n++)
		(void) arc4_getbyte();
	arc4_count = 1600000;
	rs_stired = 1;
}

static inline u_int8_t
arc4_getbyte(void)
{
	u_int8_t si, sj;

	rs.i = (rs.i + 1);
	si = rs.s[rs.i];
	rs.j = (rs.j + si);
	sj = rs.s[rs.j];
	rs.s[rs.i] = sj;
	rs.s[rs.j] = si;

	return (rs.s[(si + sj) & 0xff]);
}

static inline u_int32_t
arc4_getword(void)
{
	u_int32_t val;

	val = arc4_getbyte() << 24;
	val |= arc4_getbyte() << 16;
	val |= arc4_getbyte() << 8;
	val |= arc4_getbyte();

	return (val);
}

/* 7944700: force restir in child */
__private_extern__ void
_arc4_fork_child(void)
{
	arc4_lock = OS_UNFAIR_LOCK_INIT;
	rs_stired = 0;
	rs_data_available = 0;
}

static inline int
arc4_check_stir(void)
{
	if (!rs_stired || arc4_count <= 0) {
		arc4_stir();
		return 1;
	}
	return 0;
}

void
arc4random_addrandom(u_char *dat, int datlen)
{
	os_unfair_lock_lock(&arc4_lock);
	arc4_check_stir();
	arc4_addrandom(dat, datlen);
	os_unfair_lock_unlock(&arc4_lock);
}

u_int32_t
arc4random(void)
{
	u_int32_t rnd;

	os_unfair_lock_lock(&arc4_lock);

	int did_stir = arc4_check_stir();
	rnd = arc4_getword();
	arc4_count -= 4;

	os_unfair_lock_unlock(&arc4_lock);
	if (did_stir)
	{
		/* stirring used up our data pool, we need to read in new data outside of the lock */
		arc4_fetch();
		rs_data_available = 1;
		__sync_synchronize();
	}

	return (rnd);
}

void
arc4random_buf(void *_buf, size_t n)
{
	u_char *buf = (u_char *)_buf;
	int did_stir = 0;

	os_unfair_lock_lock(&arc4_lock);

	while (n--) {
		if (arc4_check_stir())
		{
			did_stir = 1;
		}
		buf[n] = arc4_getbyte();
		arc4_count--;
	}

	os_unfair_lock_unlock(&arc4_lock);
	if (did_stir)
	{
		/* stirring used up our data pool, we need to read in new data outside of the lock */
		arc4_fetch();
		rs_data_available = 1;
		__sync_synchronize();
	}
}

void
arc4random_stir(void)
{
	os_unfair_lock_lock(&arc4_lock);
	arc4_stir();
	os_unfair_lock_unlock(&arc4_lock);
}

/*
 * Calculate a uniformly distributed random number less than upper_bound
 * avoiding "modulo bias".
 *
 * Uniformity is achieved by trying successive ranges of bits from the random
 * value, each large enough to hold the desired upper bound, until a range
 * holding a value less than the bound is found.
 */
uint32_t
arc4random_uniform(uint32_t upper_bound)
{
	if (upper_bound < 2)
		return 0;

	// find smallest 2**n -1 >= upper_bound
	int zeros = __builtin_clz(upper_bound);
	int bits = CHAR_BIT * sizeof(uint32_t) - zeros;
	uint32_t mask = 0xFFFFFFFFU >> zeros;

	do {
		uint32_t value = arc4random();

		// If low 2**n-1 bits satisfy the requested condition, return result
		uint32_t result = value & mask;
		if (result < upper_bound) {
			return result;
		}

		// otherwise consume remaining bits of randomness looking for a satisfactory result.
		int bits_left = zeros;
		while (bits_left >= bits) {
			value >>= bits;
			result = value & mask;
			if (result < upper_bound) {
				return result;
			}
			bits_left -= bits;
		}
	} while (1);
}

#endif /* __APPLE__ */
Commit	Line	Data
5b2abdfb	1	/*
1f2f436a A	2	* Copyright (c) 1996, David Mazieres <dm@uun.org>
	3	* Copyright (c) 2008, Damien Miller <djm@openbsd.org>
	4	*
	5	* Permission to use, copy, modify, and distribute this software for any
	6	* purpose with or without fee is hereby granted, provided that the above
	7	* copyright notice and this permission notice appear in all copies.
5b2abdfb	8	*
1f2f436a A	9	* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
	10	* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
	11	* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
	12	* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
	13	* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
	14	* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
	15	* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
5b2abdfb A	16	*/
	17
	18	/*
1f2f436a A	19	* Arc4 random number generator for OpenBSD.
1f2f436a A	20	*
5b2abdfb A	21	* This code is derived from section 17.1 of Applied Cryptography,
	22	* second edition, which describes a stream cipher allegedly
	23	* compatible with RSA Labs "RC4" cipher (the actual description of
	24	* which is a trade secret). The same algorithm is used as a stream
	25	* cipher called "arcfour" in Tatu Ylonen's ssh package.
	26	*
	27	* Here the stream cipher has been modified always to include the time
	28	* when initializing the state. That makes it impossible to
	29	* regenerate the same random sequence twice, so this can't be used
	30	* for encryption, but will generate good random numbers.
	31	*
	32	* RC4 is a registered trademark of RSA Laboratories.
	33	*/
	34
224c7076	35	#include <sys/cdefs.h>
1f2f436a	36	__FBSDID("$FreeBSD: src/lib/libc/gen/arc4random.c,v 1.25 2008/09/09 09:46:36 ache Exp $");
224c7076	37
224c7076 A	38	#include <sys/types.h>
224c7076 A	39	#include <sys/time.h>
974e3884 A	40	#include <sys/param.h>
974e3884 A	41	#include <sys/random.h>
5b2abdfb A	42	#include <fcntl.h>
5b2abdfb A	43	#include <unistd.h>
224c7076	44	#include <pthread.h>
507116e3 A	45
	46	#include <TargetConditionals.h>
	47	#if !TARGET_OS_DRIVERKIT
	48	#define OS_CRASH_ENABLE_EXPERIMENTAL_LIBTRACE 1
	49	#endif
974e3884 A	50	#include <os/assumes.h>
974e3884 A	51	#include <os/lock.h>
224c7076	52
974e3884	53	#include "string.h"
224c7076	54	#include "libc_private.h"
974e3884	55
507116e3 A	56	#if defined(__APPLE__) && !defined(VARIANT_STATIC)
507116e3 A	57	#include <corecrypto/ccrng.h>
974e3884	58
507116e3	59	static struct ccrng_state *rng;
974e3884	60
507116e3 A	61	static void
	62	arc4_init(void)
	63	{
	64	int err;
	65
	66	if (rng != NULL) return;
	67
	68	rng = ccrng(&err);
	69	if (rng == NULL) {
	70	#if OS_CRASH_ENABLE_EXPERIMENTAL_LIBTRACE
	71	os_crash("arc4random: unable to get ccrng() handle (%d)", err);
	72	#else
	73	os_crash("arc4random: unable to get ccrng() handle");
	74	#endif
	75	}
	76	}
	77
	78	void
	79	arc4random_addrandom(__unused u_char *dat, __unused int datlen)
	80	{
	81	/* NOP - deprecated */
	82	}
	83
	84	uint32_t
	85	arc4random(void)
	86	{
	87	uint32_t rand;
974e3884	88
507116e3 A	89	arc4random_buf(&rand, sizeof(rand));
	90
	91	return rand;
	92	}
	93
	94	void
	95	arc4random_buf(void *buf, size_t buf_size)
	96	{
	97	arc4_init();
	98	ccrng_generate(rng, buf_size, buf);
	99	}
	100
	101	void
	102	arc4random_stir(void)
	103	{
	104	/* NOP */
	105	}
	106
	107	uint32_t
	108	arc4random_uniform(uint32_t upper_bound)
	109	{
	110	uint64_t rand;
	111
	112	arc4_init();
	113	ccrng_uniform(rng, upper_bound, &rand);
	114
	115	return (uint32_t)rand;
	116	}
	117
	118	__private_extern__ void
	119	_arc4_fork_child(void)
	120	{
	121	/* NOP */
	122	}
	123
	124	#else /* __APPLE__ && !VARIANT_STATIC */
974e3884 A	125
	126	#define RANDOMDEV "/dev/random"
	127
	128	static void
	129	_my_getentropy(uint8_t *buf, size_t size){
	130	int fd;
	131	ssize_t ret;
	132	if (getentropy(buf, size) == 0) {
	133	return;
	134	}
	135
	136	// The above should never fail, but we'll try /dev/random anyway
	137	fd = open(RANDOMDEV, O_RDONLY, 0);
	138	if (fd == -1) {
	139	#if !defined(VARIANT_STATIC)
	140	os_crash("arc4random: unable to open /dev/random");
	141	#else
	142	abort();
	143	#endif
	144	}
	145	shortread:
	146	ret = read(fd, buf, size);
	147	if (ret == -1) {
	148	#if !defined(VARIANT_STATIC)
	149	os_crash("arc4random: unable to read from /dev/random");
	150	#else
	151	abort();
	152	#endif
	153	} else if ((size_t)ret < size) {
	154	size -= (size_t)ret;
	155	buf += ret;
	156	goto shortread;
	157	}
	158	(void)close(fd);
	159	}
	160
5b2abdfb A	161	struct arc4_stream {
	162	u_int8_t i;
	163	u_int8_t j;
	164	u_int8_t s[256];
	165	};
	166
1f2f436a	167	#define KEYSIZE 128
224c7076	168
1f2f436a A	169	static struct arc4_stream rs = {
	170	.i = 0,
	171	.j = 0,
	172	.s = {
	173	0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
	174	16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
	175	32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,
	176	48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63,
	177	64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79,
	178	80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95,
	179	96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111,
	180	112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127,
	181	128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143,
	182	144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159,
	183	160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175,
	184	176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191,
	185	192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207,
	186	208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223,
	187	224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239,
	188	240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255
	189	}
	190	};
224c7076 A	191	static int rs_stired;
224c7076 A	192
1f2f436a A	193	static inline u_int8_t arc4_getbyte(void);
1f2f436a A	194	static void arc4_stir(void);
5b2abdfb	195
1f2f436a A	196	static struct {
	197	struct timeval tv;
	198	pid_t pid;
	199	u_int8_t rnd[KEYSIZE];
	200	} rdat;
	201	static volatile int rs_data_available = 0;
5b2abdfb A	202
5b2abdfb A	203	static inline void
1f2f436a	204	arc4_addrandom(u_char *dat, int datlen)
5b2abdfb A	205	{
	206	int n;
	207	u_int8_t si;
	208
1f2f436a	209	rs.i--;
5b2abdfb	210	for (n = 0; n < 256; n++) {
1f2f436a A	211	rs.i = (rs.i + 1);
	212	si = rs.s[rs.i];
	213	rs.j = (rs.j + si + dat[n % datlen]);
	214	rs.s[rs.i] = rs.s[rs.j];
	215	rs.s[rs.j] = si;
5b2abdfb	216	}
1f2f436a	217	rs.j = rs.i;
5b2abdfb A	218	}
	219
	220	static void
1f2f436a	221	arc4_fetch(void)
5b2abdfb	222	{
974e3884	223	_my_getentropy((uint8_t*)&rdat, KEYSIZE);
1f2f436a	224	}
5b2abdfb	225
507116e3 A	226	static os_unfair_lock arc4_lock = OS_UNFAIR_LOCK_INIT;
	227	static int arc4_count;
	228
1f2f436a A	229	static void
	230	arc4_stir(void)
	231	{
	232	int n;
	233	/*
	234	* If we don't have data, we need some now before we can integrate
	235	* it into the static buffers
	236	*/
	237	if (!rs_data_available)
	238	{
	239	arc4_fetch();
	240	}
	241	rs_data_available = 0;
	242	__sync_synchronize();
	243
	244	arc4_addrandom((u_char *)&rdat, KEYSIZE);
224c7076 A	245
	246	/*
	247	* Throw away the first N bytes of output, as suggested in the
	248	* paper "Weaknesses in the Key Scheduling Algorithm of RC4"
	249	* by Fluher, Mantin, and Shamir. N=1024 is based on
	250	* suggestions in the paper "(Not So) Random Shuffles of RC4"
	251	* by Ilya Mironov.
	252	*/
	253	for (n = 0; n < 1024; n++)
1f2f436a A	254	(void) arc4_getbyte();
	255	arc4_count = 1600000;
	256	rs_stired = 1;
5b2abdfb A	257	}
	258
	259	static inline u_int8_t
1f2f436a	260	arc4_getbyte(void)
5b2abdfb A	261	{
	262	u_int8_t si, sj;
	263
1f2f436a A	264	rs.i = (rs.i + 1);
	265	si = rs.s[rs.i];
	266	rs.j = (rs.j + si);
	267	sj = rs.s[rs.j];
	268	rs.s[rs.i] = sj;
	269	rs.s[rs.j] = si;
224c7076	270
1f2f436a	271	return (rs.s[(si + sj) & 0xff]);
5b2abdfb A	272	}
	273
	274	static inline u_int32_t
1f2f436a	275	arc4_getword(void)
5b2abdfb A	276	{
5b2abdfb A	277	u_int32_t val;
224c7076	278
1f2f436a A	279	val = arc4_getbyte() << 24;
	280	val \|= arc4_getbyte() << 16;
	281	val \|= arc4_getbyte() << 8;
	282	val \|= arc4_getbyte();
224c7076 A	283
224c7076 A	284	return (val);
5b2abdfb A	285	}
5b2abdfb A	286
1f2f436a A	287	/* 7944700: force restir in child */
	288	__private_extern__ void
	289	_arc4_fork_child(void)
5b2abdfb	290	{
974e3884	291	arc4_lock = OS_UNFAIR_LOCK_INIT;
1f2f436a A	292	rs_stired = 0;
1f2f436a A	293	rs_data_available = 0;
224c7076 A	294	}
224c7076 A	295
1f2f436a	296	static inline int
224c7076 A	297	arc4_check_stir(void)
224c7076 A	298	{
1f2f436a A	299	if (!rs_stired \|\| arc4_count <= 0) {
	300	arc4_stir();
	301	return 1;
224c7076	302	}
1f2f436a	303	return 0;
224c7076 A	304	}
224c7076 A	305
5b2abdfb	306	void
1f2f436a	307	arc4random_addrandom(u_char *dat, int datlen)
5b2abdfb	308	{
974e3884	309	os_unfair_lock_lock(&arc4_lock);
224c7076	310	arc4_check_stir();
1f2f436a	311	arc4_addrandom(dat, datlen);
974e3884	312	os_unfair_lock_unlock(&arc4_lock);
5b2abdfb A	313	}
	314
	315	u_int32_t
1f2f436a	316	arc4random(void)
5b2abdfb	317	{
224c7076 A	318	u_int32_t rnd;
224c7076 A	319
974e3884	320	os_unfair_lock_lock(&arc4_lock);
1f2f436a A	321
	322	int did_stir = arc4_check_stir();
	323	rnd = arc4_getword();
	324	arc4_count -= 4;
	325
974e3884	326	os_unfair_lock_unlock(&arc4_lock);
1f2f436a A	327	if (did_stir)
	328	{
	329	/* stirring used up our data pool, we need to read in new data outside of the lock */
	330	arc4_fetch();
	331	rs_data_available = 1;
	332	__sync_synchronize();
	333	}
224c7076 A	334
224c7076 A	335	return (rnd);
5b2abdfb A	336	}
5b2abdfb A	337
1f2f436a A	338	void
	339	arc4random_buf(void *_buf, size_t n)
	340	{
	341	u_char buf = (u_char )_buf;
	342	int did_stir = 0;
	343
974e3884	344	os_unfair_lock_lock(&arc4_lock);
1f2f436a A	345
	346	while (n--) {
	347	if (arc4_check_stir())
	348	{
	349	did_stir = 1;
	350	}
	351	buf[n] = arc4_getbyte();
	352	arc4_count--;
	353	}
974e3884 A	354
974e3884 A	355	os_unfair_lock_unlock(&arc4_lock);
1f2f436a A	356	if (did_stir)
	357	{
	358	/* stirring used up our data pool, we need to read in new data outside of the lock */
	359	arc4_fetch();
	360	rs_data_available = 1;
	361	__sync_synchronize();
	362	}
	363	}
	364
974e3884 A	365	void
	366	arc4random_stir(void)
	367	{
	368	os_unfair_lock_lock(&arc4_lock);
	369	arc4_stir();
	370	os_unfair_lock_unlock(&arc4_lock);
	371	}
	372
1f2f436a A	373	/*
	374	* Calculate a uniformly distributed random number less than upper_bound
	375	* avoiding "modulo bias".
	376	*
974e3884 A	377	* Uniformity is achieved by trying successive ranges of bits from the random
	378	* value, each large enough to hold the desired upper bound, until a range
	379	* holding a value less than the bound is found.
1f2f436a	380	*/
974e3884 A	381	uint32_t
974e3884 A	382	arc4random_uniform(uint32_t upper_bound)
1f2f436a	383	{
1f2f436a	384	if (upper_bound < 2)
974e3884	385	return 0;
1f2f436a	386
974e3884 A	387	// find smallest 2**n -1 >= upper_bound
	388	int zeros = __builtin_clz(upper_bound);
	389	int bits = CHAR_BIT * sizeof(uint32_t) - zeros;
	390	uint32_t mask = 0xFFFFFFFFU >> zeros;
1f2f436a	391
974e3884 A	392	do {
974e3884 A	393	uint32_t value = arc4random();
5b2abdfb	394
974e3884 A	395	// If low 2**n-1 bits satisfy the requested condition, return result
	396	uint32_t result = value & mask;
	397	if (result < upper_bound) {
	398	return result;
	399	}
5b2abdfb	400
974e3884 A	401	// otherwise consume remaining bits of randomness looking for a satisfactory result.
	402	int bits_left = zeros;
	403	while (bits_left >= bits) {
	404	value >>= bits;
	405	result = value & mask;
	406	if (result < upper_bound) {
	407	return result;
	408	}
	409	bits_left -= bits;
	410	}
	411	} while (1);
5b2abdfb	412	}
507116e3 A	413
507116e3 A	414	#endif /* __APPLE__ */