/* OPENBSD ORIGINAL: lib/libc/crypto/arc4random.c */

/*     $OpenBSD: arc4random.c,v 1.51 2015/01/15 06:57:18 deraadt Exp $ */

/*
 * Copyright (c) 1996, David Mazieres <dm@uun.org>
 * Copyright (c) 2008, Damien Miller <djm@openbsd.org>
 * Copyright (c) 2013, Markus Friedl <markus@openbsd.org>
 * Copyright (c) 2014, Theo de Raadt <deraadt@openbsd.org>
 * Copyright (c) 2015, Sami Farin
 *
 * 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.
 */

/*
 * ChaCha based random number generator for OpenBSD.
 * Sami Farin edition Thread-safe without locking.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/syscall.h>   /* For SYS_xxx definitions */
#include <errno.h>
#include <stdbool.h>
#include <math.h>

#include "charcrandom.h"

#ifdef __GNUC__
#define inline __inline
#else				/* !__GNUC__ */
#define inline
#endif				/* !__GNUC__ */

#define KEYSZ	((size_t)32)
#define IVSZ	((size_t)8)
#define BLOCKSZ	64
#define RSBUFSZ	(16*BLOCKSZ)

#define min(x,y) ({             \
        typeof(x) _min1 = (x);     \
        typeof(y) _min2 = (y);     \
        (void) (&_min1 == &_min2);    \
        _min1 < _min2 ? _min1 : _min2; })

#define max(x,y) ({             \
        typeof(x) _max1 = (x);     \
        typeof(y) _max2 = (y);     \
        (void) (&_max1 == &_max2);    \
        _max1 > _max2 ? _max1 : _max2; })

#define likely(x)       __builtin_expect(!!(x), 1)
#define unlikely(x)     __builtin_expect(!!(x), 0)

typedef struct {
  bool rs_initialized;
  pid_t rs_stir_pid;
  chacha_ctx rs;		/* chacha context for random keystream */
  uint8_t rs_buf[RSBUFSZ];	/* keystream blocks */
  size_t rs_have;		/* valid bytes at end of rs_buf */
  size_t rs_count;		/* bytes till reseed */
} charc_state;
static __thread charc_state charc __attribute__((aligned(128)));

static inline void _rs_rekey(uint8_t *dat, size_t datlen);

static inline void _rs_init(uint8_t *buf, size_t n)
{
	if (n < KEYSZ + IVSZ)
		return;
	chacha_keysetup(&charc.rs, buf, KEYSZ * 8);
	chacha_ivsetup(&charc.rs, buf + KEYSZ);
}

static bool _rs_random_bytes(void *p, size_t n)
{
	static FILE *frandom;
	long ret;

	if (!n) return true;

#if defined(SYS_getrandom) && defined(__linux__)
	do {
		/* <=256 byte requests always succeed */
		ret = syscall(SYS_getrandom, p, n, 0, 0, 0, 0);
	} while ((ret == -1) && (errno == EINTR));
	if (ret == n) return true;
#endif
        if (frandom == NULL) {
		frandom = fopen("/dev/urandom", "rb");
		if (frandom == NULL) {
			return false;
		}
		setbuf(frandom, NULL);
	}
	if (fread(p, 1, n, frandom) != n) {
		fclose(frandom);
		frandom = NULL;
		return false;
	}
	return true;
}

static void _rs_stir(void)
{
	uint8_t rnd[KEYSZ + IVSZ];

	if (_rs_random_bytes(rnd, sizeof(rnd)) == false) {
		fprintf(stderr, "Couldn't obtain random bytes\n");
                _exit(1);
	}

	if (!charc.rs_initialized) {
		charc.rs_initialized = 1;
		_rs_init(rnd, sizeof(rnd));
	} else {
		_rs_rekey(rnd, sizeof(rnd));
	}
	secure_memset(rnd, sizeof(rnd));

	/* invalidate rs_buf */
	charc.rs_have = 0;
	memset(charc.rs_buf, 0, RSBUFSZ);

	charc.rs_count = 1600000;
}

static inline void _rs_stir_if_needed(size_t len)
{
	pid_t pid = getpid(); /* maybe user does fork() without immediately doing exec() */

	if (unlikely(charc.rs_count <= len || !charc.rs_initialized || charc.rs_stir_pid != pid)) {
		charc.rs_stir_pid = pid;
		_rs_stir();
	}
	if (charc.rs_count <= len) {
		charc.rs_count = 0;
	} else {
		charc.rs_count -= len;
	}
}

static inline void _rs_rekey(uint8_t *dat, size_t datlen)
{
	/* fill rs_buf with the keystream */
	chacha_encrypt_bytes(&charc.rs, charc.rs_buf, charc.rs_buf, RSBUFSZ);
	/* mix in optional user provided data */
	if (dat) {
		size_t i, m;

		m = min(datlen, KEYSZ + IVSZ);
		for (i = 0; i < m; i++)
			charc.rs_buf[i] ^= dat[i];
	}
	/* immediately reinit for backtracking resistance */
	_rs_init(charc.rs_buf, KEYSZ + IVSZ);
	memset(charc.rs_buf, 0, KEYSZ + IVSZ);
	charc.rs_have = RSBUFSZ - KEYSZ - IVSZ;
}

static void _rs_random_buf(void *_buf, size_t n)
{
	uint8_t *buf = (uint8_t*)_buf;
	uint8_t *keystream;
	size_t m;

	_rs_stir_if_needed(n);
	while (n > 0) {
		if (likely(charc.rs_have > 0)) {
			m = min(n, charc.rs_have);
			keystream = charc.rs_buf + RSBUFSZ - charc.rs_have;
			memcpy(buf, keystream, m);
			memset(keystream, 0, m);
			buf += m;
			n -= m;
			charc.rs_have -= m;
		}
		if (charc.rs_have == 0)
			_rs_rekey(NULL, 0);
	}
}

/* API functions start */
uint16_t charcrandom_u16(void)
{
	uint16_t res;

	_rs_random_buf(&res, sizeof(res));
	return res;
}

uint32_t charcrandom_u32(void)
{
	uint32_t res;

	_rs_random_buf(&res, sizeof(res));
	return res;
}

uint64_t charcrandom_u64(void)
{
	uint64_t res;

	_rs_random_buf(&res, sizeof(res));
	return res;
}

void charcrandom_addrandom(uint8_t *dat, size_t datlen)
{
	size_t m;

	if (!charc.rs_initialized)
		_rs_stir();
	while (datlen > 0) {
		m = min(datlen, KEYSZ + IVSZ);
		_rs_rekey(dat, m);
		dat += m;
		datlen -= m;
	}
}

void charcrandom_buf(void *buf, size_t n)
{
	_rs_random_buf(buf, n);
}

/*
 * Calculate a uniformly distributed random number less than upper_bound
 * avoiding "modulo bias".
 *
 * Uniformity is achieved by generating new random numbers until the one
 * returned is outside the range [0, 2**32 % upper_bound).  This
 * guarantees the selected random number will be inside
 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
 * after reduction modulo upper_bound.
 */
uint32_t charcrandom_uniform32(uint32_t upper_bound)
{
	uint32_t r, mini;

	if (upper_bound < 2)
		return 0;

	/* 2**32 % x == (2**32 - x) % x */
	mini = -upper_bound % upper_bound;

	/*
	 * This could theoretically loop forever but each retry has
	 * p > 0.5 (worst case, usually far better) of selecting a
	 * number inside the range we need, so it should rarely need
	 * to re-roll.
	 */
	for (;;) {
		r = charcrandom_u32();
		if (likely(r >= mini))
			break;
	}

	return r % upper_bound;
}

uint64_t charcrandom_uniform64(uint64_t upper_bound)
{
	uint64_t r, mini;

	if (upper_bound < 2)
		return 0;

	mini = -upper_bound % upper_bound;

	for (;;) {
		r = charcrandom_u64();
		if (likely(r >= mini))
			break;
	}

	return r % upper_bound;
}
/* The following function is released under BSD 3 clause license.
 *
 * Copyright (C) 2016 Salvatore Sanfilippo. All Rights Resereved.
 * This code is released under the BSD 3 clause license. */
/* Return a random number with normal distribution and the specified
 * mean and variance. It uses the "polar method" but does not cache one
 * of the previously generated random numbers, it just returns a single
 * one per iteration in order for the function to be completely stateless. */
double charcrandom_normrand(double mean, double variance) {
	double v1, v2, s;

	do {
		/* Generate two uniform random numbers in the -1,1 range. */
		v1 = (double)charcrandom_u64() / UINT64_MAX * 2.0 - 1.0;
		v2 = (double)charcrandom_u64() / UINT64_MAX * 2.0 - 1.0;
		s = v1*v1 + v2*v2;
	} while (s >= 1.0);

	/* Obtain a number with unit normal distibution. */
	v1 = sqrt(-2.0 * log(s) / s) * v1;
	/* Convert it to requested mean and variance. */
	return mean + sqrt(variance) * v1;
}