rprand.h (11693B)
1 /********************************************************************************************** 2 * 3 * rprand v1.0 - A simple and easy-to-use pseudo-random numbers generator (PRNG) 4 * 5 * FEATURES: 6 * - Pseudo-random values generation, 32 bits: [0..4294967295] 7 * - Sequence generation avoiding duplicate values 8 * - Using standard and proven prng algorithm (Xoshiro128**) 9 * - State initialized with a separate generator (SplitMix64) 10 * 11 * LIMITATIONS: 12 * - No negative numbers, up to the user to manage them 13 * 14 * POSSIBLE IMPROVEMENTS: 15 * - Support 64 bits generation 16 * 17 * ADDITIONAL NOTES: 18 * This library implements two pseudo-random number generation algorithms: 19 * 20 * - Xoshiro128** : https://prng.di.unimi.it/xoshiro128starstar.c 21 * - SplitMix64 : https://prng.di.unimi.it/splitmix64.c 22 * 23 * SplitMix64 is used to initialize the Xoshiro128** state, from a provided seed 24 * 25 * It's suggested to use SplitMix64 to initialize the state of the generators starting from 26 * a 64-bit seed, as research has shown that initialization must be performed with a generator 27 * radically different in nature from the one initialized to avoid correlation on similar seeds. 28 * 29 * CONFIGURATION: 30 * #define RPRAND_IMPLEMENTATION 31 * Generates the implementation of the library into the included file. 32 * If not defined, the library is in header only mode and can be included in other headers 33 * or source files without problems. But only ONE file should hold the implementation. 34 * 35 * DEPENDENCIES: none 36 * 37 * VERSIONS HISTORY: 38 * 1.0 (01-Jun-2023) First version 39 * 40 * 41 * LICENSE: zlib/libpng 42 * 43 * Copyright (c) 2023 Ramon Santamaria (@raysan5) 44 * 45 * This software is provided "as-is", without any express or implied warranty. In no event 46 * will the authors be held liable for any damages arising from the use of this software. 47 * 48 * Permission is granted to anyone to use this software for any purpose, including commercial 49 * applications, and to alter it and redistribute it freely, subject to the following restrictions: 50 * 51 * 1. The origin of this software must not be misrepresented; you must not claim that you 52 * wrote the original software. If you use this software in a product, an acknowledgment 53 * in the product documentation would be appreciated but is not required. 54 * 55 * 2. Altered source versions must be plainly marked as such, and must not be misrepresented 56 * as being the original software. 57 * 58 * 3. This notice may not be removed or altered from any source distribution. 59 * 60 **********************************************************************************************/ 61 62 #ifndef RPRAND_H 63 #define RPRAND_H 64 65 #define RPRAND_VERSION "1.0" 66 67 // Function specifiers in case library is build/used as a shared library (Windows) 68 // NOTE: Microsoft specifiers to tell compiler that symbols are imported/exported from a .dll 69 #if defined(_WIN32) 70 #if defined(BUILD_LIBTYPE_SHARED) 71 #define RPRAND __declspec(dllexport) // We are building the library as a Win32 shared library (.dll) 72 #elif defined(USE_LIBTYPE_SHARED) 73 #define RPRAND __declspec(dllimport) // We are using the library as a Win32 shared library (.dll) 74 #endif 75 #endif 76 77 // Function specifiers definition 78 #ifndef RPRANDAPI 79 #define RPRANDAPI // Functions defined as 'extern' by default (implicit specifiers) 80 #endif 81 82 //---------------------------------------------------------------------------------- 83 // Defines and Macros 84 //---------------------------------------------------------------------------------- 85 // Allow custom memory allocators 86 #ifndef RPRAND_CALLOC 87 #define RPRAND_CALLOC(ptr,sz) calloc(ptr,sz) 88 #endif 89 #ifndef RPRAND_FREE 90 #define RPRAND_FREE(ptr) free(ptr) 91 #endif 92 93 // Simple log system to avoid RPNG_LOG() calls if required 94 // NOTE: Avoiding those calls, also avoids const strings memory usage 95 #define RPRAND_SHOW_LOG_INFO 96 #if defined(RPNG_SHOW_LOG_INFO) 97 #define RPRAND_LOG(...) printf(__VA_ARGS__) 98 #else 99 #define RPRAND_LOG(...) 100 #endif 101 102 //---------------------------------------------------------------------------------- 103 // Types and Structures Definition 104 //---------------------------------------------------------------------------------- 105 //... 106 107 #ifdef __cplusplus 108 extern "C" { // Prevents name mangling of functions 109 #endif 110 111 //---------------------------------------------------------------------------------- 112 // Global Variables Definition 113 //---------------------------------------------------------------------------------- 114 //... 115 116 //---------------------------------------------------------------------------------- 117 // Module Functions Declaration 118 //---------------------------------------------------------------------------------- 119 RPRANDAPI void rprand_set_seed(unsigned long long seed); // Set rprand_state for Xoshiro128**, seed is 64bit 120 RPRANDAPI int rprand_get_value(int min, int max); // Get random value within a range, min and max included 121 122 RPRANDAPI int *rprand_load_sequence(unsigned int count, int min, int max); // Load pseudo-random numbers sequence with no duplicates 123 RPRANDAPI void rprand_unload_sequence(int *sequence); // Unload pseudo-random numbers sequence 124 125 #ifdef __cplusplus 126 } 127 #endif 128 129 #endif // RPRAND_H 130 131 /*********************************************************************************** 132 * 133 * RPRAND IMPLEMENTATION 134 * 135 ************************************************************************************/ 136 137 #if defined(RPRAND_IMPLEMENTATION) 138 139 #include <stdlib.h> // Required for: calloc(), free(), abs() 140 #include <stdint.h> // Required for data types: uint32_t, uint64_t 141 142 //---------------------------------------------------------------------------------- 143 // Types and Structures Definition 144 //---------------------------------------------------------------------------------- 145 // ... 146 147 //---------------------------------------------------------------------------------- 148 // Global Variables Definition 149 //---------------------------------------------------------------------------------- 150 static uint64_t rprand_seed = 0xAABBCCDD; // SplitMix64 default seed (aligned to rprand_state) 151 static uint32_t rprand_state[4] = { // Xoshiro128** state, initialized by SplitMix64 152 0x96ea83c1, 153 0x218b21e5, 154 0xaa91febd, 155 0x976414d4 156 }; 157 158 //---------------------------------------------------------------------------------- 159 // Module internal functions declaration 160 //---------------------------------------------------------------------------------- 161 static uint32_t rprand_xoshiro(void); // Xoshiro128** generator (uses global rprand_state) 162 static uint64_t rprand_splitmix64(void); // SplitMix64 generator (uses seed to generate rprand_state) 163 164 //---------------------------------------------------------------------------------- 165 // Module functions definition 166 //---------------------------------------------------------------------------------- 167 // Set rprand_state for Xoshiro128** 168 // NOTE: We use a custom generation algorithm using SplitMix64 169 void rprand_set_seed(unsigned long long seed) 170 { 171 rprand_seed = (uint64_t)seed; // Set SplitMix64 seed for further use 172 173 // To generate the Xoshiro128** state, we use SplitMix64 generator first 174 // We generate 4 pseudo-random 64bit numbers that we combine using their LSB|MSB 175 rprand_state[0] = (uint32_t)(rprand_splitmix64() & 0xffffffff); 176 rprand_state[1] = (uint32_t)((rprand_splitmix64() & 0xffffffff00000000) >> 32); 177 rprand_state[2] = (uint32_t)(rprand_splitmix64() & 0xffffffff); 178 rprand_state[3] = (uint32_t)((rprand_splitmix64() & 0xffffffff00000000) >> 32); 179 } 180 181 // Get random value within a range, min and max included 182 int rprand_get_value(int min, int max) 183 { 184 int value = rprand_xoshiro()%(abs(max - min) + 1) + min; 185 186 return value; 187 } 188 189 // Load pseudo-random numbers sequence with no duplicates, min and max included 190 int *rprand_load_sequence(unsigned int count, int min, int max) 191 { 192 int *sequence = NULL; 193 194 if (count > (unsigned int)(abs(max - min) + 1)) 195 { 196 RPRAND_LOG("WARNING: Sequence count required is greater than range provided\n"); 197 //count = (max - min); 198 return sequence; 199 } 200 201 sequence = (int *)RPRAND_CALLOC(count, sizeof(int)); 202 203 int value = 0; 204 bool value_is_dup = false; 205 206 for (unsigned int i = 0; i < count;) 207 { 208 value = ((unsigned int)rprand_xoshiro()%(abs(max - min) + 1)) + min; 209 210 for (unsigned int j = 0; j < i; j++) 211 { 212 if (sequence[j] == value) 213 { 214 value_is_dup = true; 215 break; 216 } 217 } 218 219 if (!value_is_dup) 220 { 221 sequence[i] = value; 222 i++; 223 } 224 225 value_is_dup = false; 226 } 227 228 return sequence; 229 } 230 231 // Unload pseudo-random numbers sequence 232 void rprand_unload_sequence(int *sequence) 233 { 234 RPRAND_FREE(sequence); 235 sequence = NULL; 236 } 237 238 //---------------------------------------------------------------------------------- 239 // Module internal functions definition 240 //---------------------------------------------------------------------------------- 241 static inline uint32_t rprand_rotate_left(const uint32_t x, int k) 242 { 243 return (x << k) | (x >> (32 - k)); 244 } 245 246 // Xoshiro128** generator info: 247 // 248 // Written in 2018 by David Blackman and Sebastiano Vigna (vigna@acm.org) 249 // 250 // To the extent possible under law, the author has dedicated all copyright 251 // and related and neighboring rights to this software to the public domain 252 // worldwide. This software is distributed without any warranty. 253 // 254 // See <http://creativecommons.org/publicdomain/zero/1.0/>. 255 // 256 // This is xoshiro128** 1.1, one of our 32-bit all-purpose, rock-solid 257 // generators. It has excellent speed, a state size (128 bits) that is 258 // large enough for mild parallelism, and it passes all tests we are aware 259 // of. 260 // 261 // Note that version 1.0 had mistakenly s[0] instead of s[1] as state 262 // word passed to the scrambler. 263 // 264 // For generating just single-precision (i.e., 32-bit) floating-point 265 // numbers, xoshiro128+ is even faster. 266 // 267 // The state must be seeded so that it is not everywhere zero. 268 // 269 uint32_t rprand_xoshiro(void) 270 { 271 const uint32_t result = rprand_rotate_left(rprand_state[1]*5, 7)*9; 272 const uint32_t t = rprand_state[1] << 9; 273 274 rprand_state[2] ^= rprand_state[0]; 275 rprand_state[3] ^= rprand_state[1]; 276 rprand_state[1] ^= rprand_state[2]; 277 rprand_state[0] ^= rprand_state[3]; 278 279 rprand_state[2] ^= t; 280 281 rprand_state[3] = rprand_rotate_left(rprand_state[3], 11); 282 283 return result; 284 } 285 286 // SplitMix64 generator info: 287 // 288 // Written in 2015 by Sebastiano Vigna (vigna@acm.org) 289 // 290 // To the extent possible under law, the author has dedicated all copyright 291 // and related and neighboring rights to this software to the public domain 292 // worldwide. This software is distributed without any warranty. 293 // 294 // See <http://creativecommons.org/publicdomain/zero/1.0/>. 295 // 296 // 297 // This is a fixed-increment version of Java 8's SplittableRandom generator 298 // See http://dx.doi.org/10.1145/2714064.2660195 and 299 // http://docs.oracle.com/javase/8/docs/api/java/util/SplittableRandom.html 300 // 301 // It is a very fast generator passing BigCrush, and it can be useful if 302 // for some reason you absolutely want 64 bits of state. 303 uint64_t rprand_splitmix64() 304 { 305 uint64_t z = (rprand_seed += 0x9e3779b97f4a7c15); 306 z = (z ^ (z >> 30))*0xbf58476d1ce4e5b9; 307 z = (z ^ (z >> 27))*0x94d049bb133111eb; 308 return z ^ (z >> 31); 309 } 310 311 #endif // RPRAND_IMPLEMENTATION