/*
 * Simple random number generator for testing.
 * Copyright © 2022-2024 Nick Bowler
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 *
 * The RNG implementation is adapted from xoshiro256+ by David Blackman
 * and Sebastiano Vigna, originally distributed under the Creative Commons
 * Zero public domain dedication.
 */

#include <config.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <limits.h>
#include <inttypes.h>

#if !TEST_RNG_NO_EXTERNAL_API
#  include "test.h"
#endif

#define B64(x) ((x) & 0xffffffffffffffffull)
#define B32(x) ((x) & 0xffffffffu)

struct test_rng {
	unsigned long long state[4];
};

/* Rotate val left by n bits.  The behaviour is undefined if n is zero. */
static unsigned long long rot_left64(unsigned long long val, int n)
{
	return B64( (val << n) | (val >> (64 - n)) );
}

static unsigned long long xoshiro256p(unsigned long long *s)
{
	unsigned long long tmp, ret;

	ret = B64(s[0] + s[3]);
	tmp = B64(s[1] << 17);

	s[2] ^= s[0];
	s[3] ^= s[1];
	s[1] ^= s[2];
	s[0] ^= s[3];
	s[2] ^= tmp;
	s[3] = rot_left64(s[3], 45);

	return ret;
}

/*
 * 32-bit random number generator for seed expansion.
 *
 * The output filter is from the public domain MurmurHash3 by Austin Appleby.
 *
 * The state is incremented by the fractional part of the golden ratio,
 * i.e., floor( (sqrt(5)-1)/2 * 2**32 )
 */
static uint_least32_t splitmix32(uint_least32_t *state)
{
	uint_least32_t z;

	z = B32(*state += 0x9e3779b9);
	z = B32((z ^ (z >> 16)) * 0x85ebca6b);
	z = B32((z ^ (z >> 13)) * 0xc2b2ae35);

	return z ^ (z >> 16);
}

static uint_least64_t seed64(uint_least32_t *state)
{
	uint_least64_t x;

	x = splitmix32(state);
	return (x << 32) | splitmix32(state);
}

#if !TEST_RNG_NO_EXTERNAL_API
struct test_rng *test_rng_alloc(const char *seed_str)
{
	test_uintmax seed_val;
	struct test_rng *rng;
	uint_least32_t seed;

	if (!test_strtoumax(&seed_val, seed_str, 0xffffffff)) {
		print_error("%s: invalid seed", seed_str);
		return NULL;
	}
	seed = seed_val;

	rng = malloc_nofail(sizeof *rng);
	rng->state[0] = seed64(&seed);
	rng->state[1] = seed64(&seed);
	rng->state[2] = seed64(&seed);
	rng->state[3] = seed64(&seed);

	return rng;
}

void test_rng_free(struct test_rng *rng)
{
	free(rng);
}

/* Calculate the least power of two greater than val, minus 1. */
static unsigned rng_mask(unsigned val)
{
	val |= val >> 1;
	val |= val >> 2;
	val |= val >> 4;
	val |= val >> 8;

	if (UINT_MAX >= 65536)
		val |= val >> 16;

	return val;
}

unsigned test_rng_uniform_int(struct test_rng *rng, unsigned max)
{
	unsigned mask = rng_mask(max-1);
	unsigned long long val;

	do {
		val = ( xoshiro256p(rng->state) >> 32 ) & mask;
	} while (val >= max);

	return val;
}
#endif