1/*
2 * Copyright 2013 Haiku, Inc. All rights reserved.
3 * Distributed under the terms of the MIT License.
4 *
5 * Authors:
6 *		Pawe�� Dziepak, pdziepak@quarnos.org
7 */
8
9
10#include <util/Random.h>
11
12#include <OS.h>
13
14
15static uint32	sFastLast	= 0;
16static uint32	sLast		= 0;
17static uint32	sSecureLast	= 0;
18
19// MD4 helper definitions, based on RFC 1320
20#define F(x, y, z)	(((x) & (y)) | (~(x) & (z)))
21#define G(x, y, z)	(((x) & (y)) | ((x) & (z)) | ((y) & (z)))
22#define H(x, y, z)	((x) ^ (y) ^ (z))
23
24#define STEP(f, a, b, c, d, xk, s)	\
25	(a += f((b), (c), (d)) + (xk), a = (a << (s)) | (a >> (32 - (s))))
26
27
28// MD4 based hash function. Simplified in order to improve performance.
29static uint32
30hash(uint32* data)
31{
32		const uint32 kMD4Round2 = 0x5a827999;
33		const uint32 kMD4Round3 = 0x6ed9eba1;
34
35		uint32 a = 0x67452301;
36		uint32 b = 0xefcdab89;
37		uint32 c = 0x98badcfe;
38		uint32 d = 0x10325476;
39
40		STEP(F, a, b, c, d, data[0], 3);
41		STEP(F, d, a, b, c, data[1], 7);
42		STEP(F, c, d, a, b, data[2], 11);
43		STEP(F, b, c, d, a, data[3], 19);
44		STEP(F, a, b, c, d, data[4], 3);
45		STEP(F, d, a, b, c, data[5], 7);
46		STEP(F, c, d, a, b, data[6], 11);
47		STEP(F, b, c, d, a, data[7], 19);
48
49		STEP(G, a, b, c, d, data[1] + kMD4Round2, 3);
50		STEP(G, d, a, b, c, data[5] + kMD4Round2, 5);
51		STEP(G, c, d, a, b, data[6] + kMD4Round2, 9);
52		STEP(G, b, c, d, a, data[2] + kMD4Round2, 13);
53		STEP(G, a, b, c, d, data[3] + kMD4Round2, 3);
54		STEP(G, d, a, b, c, data[7] + kMD4Round2, 5);
55		STEP(G, c, d, a, b, data[4] + kMD4Round2, 9);
56		STEP(G, b, c, d, a, data[0] + kMD4Round2, 13);
57
58		STEP(H, a, b, c, d, data[1] + kMD4Round3, 3);
59		STEP(H, d, a, b, c, data[6] + kMD4Round3, 9);
60		STEP(H, c, d, a, b, data[5] + kMD4Round3, 11);
61		STEP(H, b, c, d, a, data[2] + kMD4Round3, 15);
62		STEP(H, a, b, c, d, data[3] + kMD4Round3, 3);
63		STEP(H, d, a, b, c, data[4] + kMD4Round3, 9);
64		STEP(H, c, d, a, b, data[7] + kMD4Round3, 11);
65		STEP(H, b, c, d, a, data[0] + kMD4Round3, 15);
66
67		return b;
68}
69
70
71// In the following functions there are race conditions when many threads
72// attempt to update static variable last. However, since such conflicts
73// are non-deterministic it is not a big problem.
74
75
76// A simple linear congruential generator
77unsigned int
78fast_random_value()
79{
80	if (sFastLast == 0)
81		sFastLast = system_time();
82
83	uint32 random = sFastLast * 1103515245 + 12345;
84	sFastLast = random;
85	return (random >> 16) & 0x7fff;
86}
87
88
89// Taken from "Random number generators: good ones are hard to find",
90// Park and Miller, Communications of the ACM, vol. 31, no. 10,
91// October 1988, p. 1195.
92unsigned int
93random_value()
94{
95	if (sLast == 0)
96		sLast = system_time();
97
98	uint32 hi = sLast / 127773;
99	uint32 lo = sLast % 127773;
100
101	int32 random = 16807 * lo - 2836 * hi;
102	if (random <= 0)
103		random += MAX_RANDOM_VALUE;
104	sLast = random;
105	return random % (MAX_RANDOM_VALUE + 1);
106}
107
108
109unsigned int
110secure_random_value()
111{
112	static int32 count = 0;
113
114	uint32 data[8];
115	data[0] = atomic_add(&count, 1);
116	data[1] = system_time();
117	data[2] = find_thread(NULL);
118	data[3] = smp_get_current_cpu();
119	data[4] = real_time_clock();
120	data[5] = sFastLast;
121	data[6] = sLast;
122	data[7] = sSecureLast;
123
124	uint32 random = hash(data);
125	sSecureLast = random;
126	return random;
127}
128
129