haiku.git

/*
 * Copyright 2013 Haiku, Inc. All rights reserved.
 * Distributed under the terms of the MIT License.
 *
 * Authors:
 *		Paweł Dziepak, pdziepak@quarnos.org
 */


#include <util/Random.h>

#include <OS.h>


static uint32	sFastLast	= 0;
static uint32	sLast		= 0;
static uint32	sSecureLast	= 0;

// MD4 helper definitions, based on RFC 1320
#define F(x, y, z)	(((x) & (y)) | (~(x) & (z)))
#define G(x, y, z)	(((x) & (y)) | ((x) & (z)) | ((y) & (z)))
#define H(x, y, z)	((x) ^ (y) ^ (z))

#define STEP(f, a, b, c, d, xk, s)	\
	(a += f((b), (c), (d)) + (xk), a = (a << (s)) | (a >> (32 - (s))))


// MD4 based hash function. Simplified in order to improve performance.
static uint32
hash(uint32* data)
{
		const uint32 kMD4Round2 = 0x5a827999;
		const uint32 kMD4Round3 = 0x6ed9eba1;

		uint32 a = 0x67452301;
		uint32 b = 0xefcdab89;
		uint32 c = 0x98badcfe;
		uint32 d = 0x10325476;

		STEP(F, a, b, c, d, data[0], 3);
		STEP(F, d, a, b, c, data[1], 7);
		STEP(F, c, d, a, b, data[2], 11);
		STEP(F, b, c, d, a, data[3], 19);
		STEP(F, a, b, c, d, data[4], 3);
		STEP(F, d, a, b, c, data[5], 7);
		STEP(F, c, d, a, b, data[6], 11);
		STEP(F, b, c, d, a, data[7], 19);

		STEP(G, a, b, c, d, data[1] + kMD4Round2, 3);
		STEP(G, d, a, b, c, data[5] + kMD4Round2, 5);
		STEP(G, c, d, a, b, data[6] + kMD4Round2, 9);
		STEP(G, b, c, d, a, data[2] + kMD4Round2, 13);
		STEP(G, a, b, c, d, data[3] + kMD4Round2, 3);
		STEP(G, d, a, b, c, data[7] + kMD4Round2, 5);
		STEP(G, c, d, a, b, data[4] + kMD4Round2, 9);
		STEP(G, b, c, d, a, data[0] + kMD4Round2, 13);

		STEP(H, a, b, c, d, data[1] + kMD4Round3, 3);
		STEP(H, d, a, b, c, data[6] + kMD4Round3, 9);
		STEP(H, c, d, a, b, data[5] + kMD4Round3, 11);
		STEP(H, b, c, d, a, data[2] + kMD4Round3, 15);
		STEP(H, a, b, c, d, data[3] + kMD4Round3, 3);
		STEP(H, d, a, b, c, data[4] + kMD4Round3, 9);
		STEP(H, c, d, a, b, data[7] + kMD4Round3, 11);
		STEP(H, b, c, d, a, data[0] + kMD4Round3, 15);

		return b;
}


// In the following functions there are race conditions when many threads
// attempt to update static variable last. However, since such conflicts
// are non-deterministic it is not a big problem.


// A simple linear congruential generator
unsigned int
fast_random_value()
{
	if (sFastLast == 0)
		sFastLast = system_time();

	uint32 random = sFastLast * 1103515245 + 12345;
	sFastLast = random;
	return (random >> 16) & 0x7fff;
}


// Taken from "Random number generators: good ones are hard to find",
// Park and Miller, Communications of the ACM, vol. 31, no. 10,
// October 1988, p. 1195.
unsigned int
random_value()
{
	if (sLast == 0)
		sLast = system_time();

	uint32 hi = sLast / 127773;
	uint32 lo = sLast % 127773;

	int32 random = 16807 * lo - 2836 * hi;
	if (random <= 0)
		random += MAX_RANDOM_VALUE;
	sLast = random;
	return random % (MAX_RANDOM_VALUE + 1);
}


unsigned int
secure_random_value()
{
	static int32 count = 0;

	uint32 data[8];
	data[0] = atomic_add(&count, 1);
	data[1] = system_time();
	data[2] = find_thread(NULL);
	data[3] = smp_get_current_cpu();
	data[4] = real_time_clock();
	data[5] = sFastLast;
	data[6] = sLast;
	data[7] = sSecureLast;

	uint32 random = hash(data);
	sSecureLast = random;
	return random;
}