main.c (10942B)
1 /** 2 * @license Apache-2.0 3 * 4 * Copyright (c) 2018 The Stdlib Authors. 5 * 6 * Licensed under the Apache License, Version 2.0 (the "License"); 7 * you may not use this file except in compliance with the License. 8 * You may obtain a copy of the License at 9 * 10 * http://www.apache.org/licenses/LICENSE-2.0 11 * 12 * Unless required by applicable law or agreed to in writing, software 13 * distributed under the License is distributed on an "AS IS" BASIS, 14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15 * See the License for the specific language governing permissions and 16 * limitations under the License. 17 */ 18 19 // Note: keep project includes in alphabetical order... 20 #include <stdlib.h> 21 #include <stdint.h> 22 #include <string.h> 23 #include "stdlib/random/base.h" 24 #include "stdlib/random/base/minstd.h" 25 26 // Forward declarations: 27 static inline int8_t next( struct BasePRNGObject *obj, uint64_t *out ); 28 static inline int8_t normalized( struct BasePRNGObject *obj, double *out ); 29 static inline void minstd_free( struct BasePRNGObject *obj ); 30 31 // Define the LCG multiplier: 32 static const uint32_t A = 16807; 33 34 // Define the maximum signed 32-bit integer: 2147483647 => 0x7fffffff => 01111111111111111111111111111111 35 static const uint32_t MAX_INT32 = 0x7fffffff; 36 37 // Define the normalization constant: 38 static const double NORMALIZATION_CONSTANT = 2147483646.0; // MAX_INT32 - 1 39 40 /** 41 * MINSTD PRNG. 42 * 43 * @private 44 */ 45 static const struct BasePRNG minstd_prng = { 46 "minstd", // name 47 (uint64_t)1, // min 48 (uint64_t)MAX_INT32-1, // max: (2^{31}-1) - 1 49 0.0, // min (normalized) 50 (MAX_INT32-2) / NORMALIZATION_CONSTANT, // max (normalized): (MAX-1)/MAX 51 sizeof( stdlib_base_random_minstd_state_t ), // state_size 52 &next, // next() 53 &normalized, // normalized() 54 &minstd_free // free() 55 }; 56 57 /** 58 * Returns a pseudorandom integer. 59 * 60 * ## Notes 61 * 62 * - The function returns `-1` if unable to generate a pseudorandom integer and `0` otherwise. 63 * 64 * @private 65 * @param obj PRNG object 66 * @param out output address 67 * @return status code 68 */ 69 static inline int8_t next( struct BasePRNGObject *obj, uint64_t *out ) { 70 if ( obj == NULL || obj->prng != &minstd_prng ) { 71 return -1; 72 } 73 // Retrieve the state object: 74 stdlib_base_random_minstd_state_t *so = (stdlib_base_random_minstd_state_t *)( obj->state ); 75 76 // Retrieve the current state: 77 uint32_t state = so->state; 78 79 // Explicitly cast to 64-bit to handle integer overflow: 80 state = (A*(uint64_t)state) % MAX_INT32; 81 82 // Update the PRNG state: 83 so->state = state; 84 85 // Set the output value: 86 *out = (uint64_t)state; 87 88 return 0; 89 } 90 91 /** 92 * Returns a pseudorandom double-precision floating-point number on the interval `[0,1)`. 93 * 94 * ## Notes 95 * 96 * - The function returns `-1` if unable to generate a pseudorandom number and `0` otherwise. 97 * 98 * @private 99 * @param obj PRNG object 100 * @param out output address 101 * @return status code 102 */ 103 static inline int8_t normalized( struct BasePRNGObject *obj, double *out ) { 104 uint64_t state; 105 int8_t status = next( obj, &state ); 106 if ( status != 0 ) { 107 return -1; 108 } 109 // Note: casting `state` to a double here is fine, as `state` will never exceed the maximum "safe" double-precision floating-point number: 110 *out = ((double)state-1.0) / NORMALIZATION_CONSTANT; 111 112 return 0; 113 } 114 115 /** 116 * Frees a PRNG's allocated memory. 117 * 118 * @private 119 * @param obj PRNG object 120 */ 121 static inline void minstd_free( struct BasePRNGObject *obj ) { 122 if ( obj == NULL || obj->prng != &minstd_prng ) { 123 return; 124 } 125 free( obj->state ); 126 free( obj ); 127 } 128 129 /** 130 * Returns a pointer to a dynamically allocated PRNG. 131 * 132 * ## Notes 133 * 134 * - The user is responsible for freeing the allocated memory. 135 * - A provided `seed` is mapped to the interval `[1,2147483646]`. 136 * 137 * @param seed PRNG seed 138 * @return pointer to a dynamically allocated PRNG or, if unable to allocate memory, a null pointer 139 * 140 * @example 141 * #include <stdlib.h> 142 * #include <stdio.h> 143 * #include <stdint.h> 144 * #include "stdlib/random/base.h" 145 * #include "stdlib/random/base/minstd.h" 146 * 147 * // Create a PRNG: 148 * struct BasePRNGObject *obj = stdlib_base_random_minstd_allocate( 12345 ); 149 * if ( obj == NULL ) { 150 * fprintf( stderr, "Error allocating memory.\n" ); 151 * exit( 1 ); 152 * } 153 * 154 * uint64_t r; 155 * int8_t status = obj->prng->next( obj, &r ); 156 * if ( status != 0 ) { 157 * fprintf( stderr, "Unexpected result.\n" ); 158 * exit( 1 ); 159 * } 160 * 161 * // ... 162 * 163 * status = obj->prng->next( obj, &r ); 164 * 165 * // ... 166 * 167 * status = obj->prng->next( obj, &r ); 168 * 169 * // ... 170 * 171 * // Free allocated memory: 172 * stdlib_base_random_minstd_free( obj ); 173 */ 174 struct BasePRNGObject * stdlib_base_random_minstd_allocate( const int32_t seed ) { 175 uint32_t iseed; 176 177 struct BasePRNGObject *obj = malloc( sizeof( struct BasePRNGObject ) ); 178 if ( obj == NULL ) { 179 return NULL; 180 } 181 stdlib_base_random_minstd_state_t *state = malloc( sizeof( stdlib_base_random_minstd_state_t ) ); 182 if ( state == NULL ) { 183 free( obj ); // prevent memory leaks 184 return NULL; 185 } 186 // Ensure that the provided seed is within allowed bounds... 187 if ( seed == 0 ) { 188 iseed = 1; 189 } else if ( seed == MAX_INT32 ) { 190 iseed = MAX_INT32 - 1; 191 } else if ( seed < 0 ) { 192 iseed = -seed; 193 } else { 194 iseed = seed; 195 } 196 state->seed = (uint32_t)iseed; 197 state->state = (uint32_t)iseed; 198 199 obj->prng = &minstd_prng; 200 obj->state = state; 201 202 return obj; 203 } 204 205 /** 206 * Frees a PRNG's allocated memory. 207 * 208 * @param obj PRNG object 209 * 210 * @example 211 * #include <stdlib.h> 212 * #include <stdio.h> 213 * #include <stdint.h> 214 * #include "stdlib/random/base.h" 215 * #include "stdlib/random/base/minstd.h" 216 * 217 * // Create a PRNG: 218 * struct BasePRNGObject *obj = stdlib_base_random_minstd_allocate( 12345 ); 219 * if ( obj == NULL ) { 220 * fprintf( stderr, "Error allocating memory.\n" ); 221 * exit( 1 ); 222 * } 223 * 224 * uint64_t r; 225 * int8_t status = obj->prng->next( obj, &r ); 226 * if ( status != 0 ) { 227 * fprintf( stderr, "Unexpected result.\n" ); 228 * exit( 1 ); 229 * } 230 * 231 * // ... 232 * 233 * status = obj->prng->next( obj, &r ); 234 * 235 * // ... 236 * 237 * status = obj->prng->next( obj, &r ); 238 * 239 * // ... 240 * 241 * // Free allocated memory: 242 * stdlib_base_random_minstd_free( obj ); 243 */ 244 void stdlib_base_random_minstd_free( struct BasePRNGObject *obj ) { 245 if ( obj == NULL || obj->prng != &minstd_prng ) { 246 return; 247 } 248 obj->prng->free( obj ); 249 } 250 251 /** 252 * Returns a PRNG seed. 253 * 254 * ## Notes 255 * 256 * - The function returns `-1` if unable to resolve a PRNG seed and `0` otherwise. 257 * 258 * @param obj PRNG object 259 * @param out output address 260 * @return status code 261 * 262 * @example 263 * #include <stdlib.h> 264 * #include <stdio.h> 265 * #include <stdint.h> 266 * #include "stdlib/random/base.h" 267 * #include "stdlib/random/base/minstd.h" 268 * 269 * // Create a PRNG: 270 * struct BasePRNGObject *obj = stdlib_base_random_minstd_allocate( 12345 ); 271 * if ( obj == NULL ) { 272 * fprintf( stderr, "Error allocating memory.\n" ); 273 * exit( 1 ); 274 * } 275 * 276 * int32_t seed; 277 * int8_t status = stdlib_base_random_minstd_seed( obj, &seed ); 278 * if ( status != 0 ) { 279 * fprintf( stderr, "Error encountered when attempting to retrieve the PRNG seed.\n" ); 280 * exit( 1 ); 281 * } 282 * 283 * // Use the seed to, e.g., create another PRNG which will generate the same sequence... 284 * 285 * // Free allocated memory: 286 * stdlib_base_random_minstd_free( obj ); 287 */ 288 int8_t stdlib_base_random_minstd_seed( const struct BasePRNGObject *obj, int32_t *out ) { 289 if ( obj == NULL || obj->prng != &minstd_prng ) { 290 return -1; 291 } 292 // Retrieve the MINSTD state object: 293 const stdlib_base_random_minstd_state_t *state = (stdlib_base_random_minstd_state_t *)( obj->state ); 294 295 // Set the output value: 296 *out = (int32_t)( state->seed ); 297 298 return 0; 299 } 300 301 /** 302 * Returns a **copy** of the current PRNG state. 303 * 304 * ## Notes 305 * 306 * - The user is responsible for freeing the allocated memory. 307 * 308 * @param obj PRNG object 309 * @return pointer to a copy of the PRNG's internal state or, if unable to allocate memory, a null pointer 310 * 311 * @example 312 * #include <stdlib.h> 313 * #include <stdio.h> 314 * #include <stdint.h> 315 * #include "stdlib/random/base.h" 316 * #include "stdlib/random/base/minstd.h" 317 * 318 * // Create a PRNG: 319 * struct BasePRNGObject *obj = stdlib_base_random_minstd_allocate( 12345 ); 320 * if ( obj == NULL ) { 321 * fprintf( stderr, "Error allocating memory.\n" ); 322 * exit( 1 ); 323 * } 324 * 325 * void *state = stdlib_base_random_minstd_state( obj ); 326 * if ( state == NULL ) { 327 * fprintf( stderr, "Unable to retrieve PRNG state.\n" ); 328 * exit( 1 ); 329 * } 330 * 331 * // Use the captured state to, e.g., sync another PRNG or to reset a PRNG to a particular state in order to "replay" generated values at a later point in time... 332 * 333 * // Free allocated memory: 334 * stdlib_base_random_minstd_free( obj ); 335 * free( state ); 336 */ 337 void * stdlib_base_random_minstd_state( const struct BasePRNGObject *obj ) { 338 if ( obj == NULL || obj->prng != &minstd_prng ) { 339 return NULL; 340 } 341 void *state = malloc( obj->prng->state_size ); 342 if ( state == NULL ) { 343 return NULL; 344 } 345 memcpy( state, obj->state, obj->prng->state_size ); 346 return state; 347 } 348 349 /** 350 * Sets the PRNG state. 351 * 352 * ## Notes 353 * 354 * - The function returns `-1` if unable to set a PRNG state and `0` otherwise. 355 * 356 * @param obj PRNG object 357 * @param state state 358 * @return status code 359 * 360 * @example 361 * #include <stdlib.h> 362 * #include <stdio.h> 363 * #include <stdint.h> 364 * #include "stdlib/random/base.h" 365 * #include "stdlib/random/base/minstd.h" 366 * 367 * // Create a PRNG: 368 * struct BasePRNGObject *obj = stdlib_base_random_minstd_allocate( 12345 ); 369 * if ( obj == NULL ) { 370 * fprintf( stderr, "Error allocating memory.\n" ); 371 * exit( 1 ); 372 * } 373 * 374 * uint64_t r; 375 * int8_t status = obj->prng->next( obj, &r ); 376 * if ( status != 0 ) { 377 * fprintf( stderr, "Unexpected result.\n" ); 378 * exit( 1 ); 379 * } 380 * 381 * // ... 382 * 383 * status = obj->prng->next( obj, &r ); 384 * 385 * // ... 386 * 387 * status = obj->prng->next( obj, &r ); 388 * 389 * // ... 390 * 391 * // Retrieve the current PRNG state... 392 * void *state = stdlib_base_random_minstd_state( obj ); 393 * if ( state == NULL ) { 394 * fprintf( stderr, "Error encountered when attempting to retrieve PRNG state.\n" ); 395 * exit( 1 ); 396 * } 397 * 398 * // ... 399 * 400 * status = obj->prng->next( obj, &r ); 401 * 402 * // ... 403 * 404 * status = obj->prng->next( obj, &r ); 405 * 406 * // ... 407 * 408 * // Reset the PRNG to a previous state... 409 * status = stdlib_base_random_minstd_set( obj, state ); 410 * if ( status != 0 ) { 411 * fprintf( stderr, "Error encountered when attempting to set PRNG state.\n" ); 412 * exit( 1 ); 413 * } 414 * 415 * // ... 416 * 417 * status = obj->prng->next( obj, &r ); 418 * 419 * // ... 420 * 421 * status = obj->prng->next( obj, &r ); 422 * 423 * // ... 424 * 425 * // Free allocated memory: 426 * stdlib_base_random_minstd_free( obj ); 427 * free( state ); 428 */ 429 int8_t stdlib_base_random_minstd_set( struct BasePRNGObject *obj, const void *state ) { 430 if ( obj == NULL || state == NULL || obj->prng != &minstd_prng ) { 431 return -1; 432 } 433 memcpy( obj->state, state, obj->prng->state_size ); 434 return 0; 435 }