1 /* ----> DO NOT REMOVE THE FOLLOWING NOTICE <----
2 *
3 * Copyright (c) 2014-2015 Datalight, Inc.
4 * All Rights Reserved Worldwide.
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; use version 2 of the License.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but "AS-IS," WITHOUT ANY WARRANTY; without even the implied warranty
12 * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License along
16 * with this program; if not, write to the Free Software Foundation, Inc.,
17 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
18 */
19
20 /* Businesses and individuals that for commercial or other reasons cannot
21 * comply with the terms of the GPLv2 license may obtain a commercial license
22 * before incorporating Reliance Edge into proprietary software for
23 * distribution in any form. Visit http://www.datalight.com/reliance-edge for
24 * more information.
25 */
26
27 /** @file
28 * @brief Implements a random number generator.
29 */
30 #include <redfs.h>
31 #include <redtestutils.h>
32
33
34 /* This is the global seed used by the random number generator when the caller
35 * has not provided a seed to either the RedRand32() or RedRand64() functions.
36 */
37 static uint64_t ullGlobalRandomNumberSeed;
38
39 /* Whether the above seed has been initialized.
40 */
41 static bool fGlobalSeedInited;
42
43
44 /** @brief Set the global seed used by the random number generator.
45 *
46 * The global seed gets used when RedRand64() or RedRand32() are called with
47 * a NULL seed argument.
48 *
49 * @param ullSeed The value to use as the global RNG seed.
50 */
RedRandSeed(uint64_t ullSeed)51 void RedRandSeed( uint64_t ullSeed )
52 {
53 ullGlobalRandomNumberSeed = ullSeed;
54 fGlobalSeedInited = true;
55 }
56
57
58 /** @brief Generate a 64-bit pseudo-random number.
59 *
60 * The period of this random number generator is 2^64 (1.8 x 1019). These
61 * parameters are the same as the default one-stream SPRNG lcg64 generator and
62 * it satisfies the requirements for a maximal period.
63 *
64 * The tempering value is used and an AND mask and is specifically selected to
65 * favor the distribution of lower bits.
66 *
67 * @param pullSeed A pointer to the seed to use. Set this value to NULL to
68 * use the internal global seed value.
69 *
70 * @return A pseudo-random number in the range [0, UINT64_MAX].
71 */
RedRand64(uint64_t * pullSeed)72 uint64_t RedRand64( uint64_t * pullSeed )
73 {
74 const uint64_t ullA = UINT64_SUFFIX( 2862933555777941757 );
75 const uint64_t ullC = UINT64_SUFFIX( 3037000493 );
76 const uint64_t ullT = UINT64_SUFFIX( 4921441182957829599 );
77 uint64_t ullN;
78 uint64_t * pullSeedPtr;
79 uint64_t ullLocalSeed;
80
81 if( pullSeed != NULL )
82 {
83 ullLocalSeed = *pullSeed;
84 pullSeedPtr = pullSeed;
85 }
86 else
87 {
88 if( !fGlobalSeedInited )
89 {
90 /* Unfortunately, the Reliance Edge OS services don't give us much
91 * to work with to initialize the global seed. There is no entropy
92 * abstraction, no tick count abstraction, and the timestamp
93 * abstraction uses an opaque type which is not guaranteed to be an
94 * integer. The best we can do is use the RTC.
95 *
96 * Tests using the RNG should be supplying a seed anyway, for
97 * reproducibility.
98 */
99 RedRandSeed( ( uint64_t ) RedOsClockGetTime() );
100 }
101
102 ullLocalSeed = ullGlobalRandomNumberSeed;
103 pullSeedPtr = &ullGlobalRandomNumberSeed;
104 }
105
106 ullN = ( ullLocalSeed * ullA ) + ullC;
107
108 *pullSeedPtr = ullN;
109
110 /* The linear congruential generator used above produces good pseudo-random
111 * 64-bit number sequences, however, as with any LCG, the period of the
112 * lower order bits is much shorter resulting in alternately odd/even pairs
113 * in bit zero.
114 *
115 * The result of the LGC above is tempered below with a series of XOR and
116 * shift operations to produce a more acceptable equidistribution of bits
117 * throughout the 64-bit range.
118 */
119 ullN ^= ( ullN >> 21U ) & ullT;
120 ullN ^= ( ullN >> 43U ) & ullT;
121 ullN ^= ( ullN << 23U ) & ~ullT;
122 ullN ^= ( ullN << 31U ) & ~ullT;
123
124 return ullN;
125 }
126
127
128 /** @brief Generate a 32-bit pseudo-random number.
129 *
130 * @note The 32-bit random number generator internally uses the 64-bit random
131 * number generator, returning the low 32-bits of the pseudo-random
132 * 64-bit value.
133 *
134 * @param pulSeed A pointer to the seed to use. Set this value to NULL to use
135 * the internal global seed value.
136 *
137 * @return A pseudo-random number in the range [0, UINT32_MAX].
138 */
RedRand32(uint32_t * pulSeed)139 uint32_t RedRand32( uint32_t * pulSeed )
140 {
141 uint64_t ullN;
142
143 if( pulSeed != NULL )
144 {
145 uint64_t ullLocalSeed;
146
147 ullLocalSeed = *pulSeed;
148 ullN = RedRand64( &ullLocalSeed );
149 *pulSeed = ( uint32_t ) ullLocalSeed;
150 }
151 else
152 {
153 ullN = RedRand64( NULL );
154 }
155
156 return ( uint32_t ) ullN;
157 }
158