main.c (13375B)
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 #include "stdlib/random/base/minstd_shuffle.h" 26 27 // Forward declarations: 28 static inline int8_t next( struct BasePRNGObject *obj, uint64_t *out ); 29 static inline int8_t normalized( struct BasePRNGObject *obj, double *out ); 30 static inline void minstd_shuffle_free( struct BasePRNGObject *obj ); 31 32 // Define the LCG multiplier: 33 static const uint32_t A = 16807; 34 35 // Define the maximum signed 32-bit integer: 2147483647 => 0x7fffffff => 01111111111111111111111111111111 36 static const uint32_t MAX_INT32 = 0x7fffffff; 37 38 // Define the normalization constant: 39 static const double NORMALIZATION_CONSTANT = 2147483646.0; // MAX_INT32 - 1 40 41 // Define the shuffle table size: 42 static const int32_t SHUFFLE_TABLE_SIZE = 32; // WARNING: this should match the type definition!! 43 44 // Define the number of "warm-ups": 45 static const int32_t NUM_WARMUPS = 8; 46 47 /** 48 * MINSTD PRNG whose output is shuffled. 49 * 50 * @private 51 */ 52 static const struct BasePRNG minstd_shuffle_prng = { 53 "minstd-shuffle", // name 54 (uint64_t)1, // min 55 (uint64_t)MAX_INT32-1, // max: (2^{31}-1) - 1 56 0.0, // min (normalized) 57 (MAX_INT32-2) / NORMALIZATION_CONSTANT, // max (normalized): (MAX-1)/MAX 58 sizeof( stdlib_base_random_minstd_shuffle_state_t ), // state_size 59 &next, // next() 60 &normalized, // normalized() 61 &minstd_shuffle_free // free() 62 }; 63 64 /** 65 * Returns a pseudorandom integer. 66 * 67 * ## Notes 68 * 69 * - The function returns `-1` if unable to generate a pseudorandom integer and `0` otherwise. 70 * 71 * @private 72 * @param obj PRNG object 73 * @param out output address 74 * @return status code 75 */ 76 static inline int8_t next( struct BasePRNGObject *obj, uint64_t *out ) { 77 uint32_t *state; 78 int32_t i; 79 if ( obj == NULL || obj->prng != &minstd_shuffle_prng ) { 80 return -1; 81 } 82 // Retrieve the state object: 83 stdlib_base_random_minstd_shuffle_state_t *so = (stdlib_base_random_minstd_shuffle_state_t *)( obj->state ); 84 85 // Retrieve the current state: 86 state = so->state; 87 88 // Determine the index of the next pseudorandom value: 89 i = (int32_t)( (double)SHUFFLE_TABLE_SIZE * ( (double)state[0]/(double)MAX_INT32 ) ); 90 91 // Get the output value: 92 state[ 0 ] = so->table[ i ]; 93 94 // Generate a new state to replace the one we just pulled out of the shuffle table (explicitly casting to 64-bit to handle integer overflow): 95 state[ 1 ] = (A*(uint64_t)state[1]) % MAX_INT32; 96 97 // Add the new state to the shuffle table: 98 so->table[ i ] = state[ 1 ]; 99 100 // Set the output value: 101 *out = (uint64_t)( state[ 0 ] ); 102 103 return 0; 104 } 105 106 /** 107 * Returns a pseudorandom double-precision floating-point number on the interval `[0,1)`. 108 * 109 * ## Notes 110 * 111 * - The function returns `-1` if unable to generate a pseudorandom number and `0` otherwise. 112 * 113 * @private 114 * @param obj PRNG object 115 * @param out output address 116 * @return status code 117 */ 118 static inline int8_t normalized( struct BasePRNGObject *obj, double *out ) { 119 uint64_t state; 120 int8_t status = next( obj, &state ); 121 if ( status != 0 ) { 122 return -1; 123 } 124 // Note: casting `state` to a double here is fine, as `state` will never exceed the maximum "safe" double-precision floating-point number: 125 *out = ((double)state-1.0) / NORMALIZATION_CONSTANT; 126 127 return 0; 128 } 129 130 /** 131 * Frees a PRNG's allocated memory. 132 * 133 * @private 134 * @param obj PRNG object 135 */ 136 static inline void minstd_shuffle_free( struct BasePRNGObject *obj ) { 137 if ( obj == NULL || obj->prng != &minstd_shuffle_prng ) { 138 return; 139 } 140 free( obj->state ); 141 free( obj ); 142 } 143 144 /** 145 * Creates a shuffle table. 146 * 147 * ## Notes 148 * 149 * - The function returns `-1` if unable to resolve a PRNG seed and `0` otherwise. 150 * 151 * @private 152 * @param obj MINSTD PRNG object 153 * @param table pointer to output shuffle table 154 * @return status code 155 */ 156 static inline int8_t create_table( struct BasePRNGObject *obj, uint32_t *table ) { 157 int8_t status; 158 uint64_t v; 159 int32_t i; 160 161 // "Warm-up" the PRNG... 162 for ( i = 0; i < NUM_WARMUPS; i++ ) { 163 status = obj->prng->next( obj, &v ); 164 if ( status != 0 ) { 165 return status; 166 } 167 } 168 // Initialize the shuffle table... 169 for ( i = SHUFFLE_TABLE_SIZE-1; i >= 0; i-- ) { 170 status = obj->prng->next( obj, &v ); 171 if ( status != 0 ) { 172 return status; 173 } 174 table[ i ] = (uint32_t)v; 175 } 176 return 0; 177 } 178 179 /** 180 * Returns a pointer to a dynamically allocated PRNG. 181 * 182 * ## Notes 183 * 184 * - The user is responsible for freeing the allocated memory. 185 * - A provided `seed` is mapped to the interval `[1,2147483646]`. 186 * 187 * @param seed PRNG seed 188 * @return pointer to a dynamically allocated PRNG or, if unable to allocate memory, a null pointer 189 * 190 * @example 191 * #include <stdlib.h> 192 * #include <stdio.h> 193 * #include <stdint.h> 194 * #include "stdlib/random/base.h" 195 * #include "stdlib/random/base/minstd_shuffle.h" 196 * 197 * // Create a PRNG: 198 * struct BasePRNGObject *obj = stdlib_base_random_minstd_shuffle_allocate( 12345 ); 199 * if ( obj == NULL ) { 200 * fprintf( stderr, "Error allocating memory.\n" ); 201 * exit( 1 ); 202 * } 203 * 204 * uint64_t r; 205 * int8_t status = obj->prng->next( obj, &r ); 206 * if ( status != 0 ) { 207 * fprintf( stderr, "Unexpected result.\n" ); 208 * exit( 1 ); 209 * } 210 * 211 * // ... 212 * 213 * status = obj->prng->next( obj, &r ); 214 * 215 * // ... 216 * 217 * status = obj->prng->next( obj, &r ); 218 * 219 * // ... 220 * 221 * // Free allocated memory: 222 * stdlib_base_random_minstd_shuffle_free( obj ); 223 */ 224 struct BasePRNGObject * stdlib_base_random_minstd_shuffle_allocate( const int32_t seed ) { 225 uint32_t iseed; 226 int8_t status; 227 228 struct BasePRNGObject *obj = malloc( sizeof( struct BasePRNGObject ) ); 229 if ( obj == NULL ) { 230 return NULL; 231 } 232 stdlib_base_random_minstd_shuffle_state_t *state = malloc( sizeof( stdlib_base_random_minstd_shuffle_state_t ) ); 233 if ( state == NULL ) { 234 free( obj ); // prevent memory leaks 235 return NULL; 236 } 237 // Ensure that the provided seed is within allowed bounds... 238 if ( seed == 0 ) { 239 iseed = 1; 240 } else if ( seed == MAX_INT32 ) { 241 iseed = MAX_INT32 - 1; 242 } else if ( seed < 0 ) { 243 iseed = -seed; 244 } else { 245 iseed = seed; 246 } 247 state->seed = (uint32_t)iseed; 248 249 obj->prng = &minstd_shuffle_prng; 250 obj->state = state; 251 252 // Allocate a MINSTD PRNG for initializing the shuffle table: 253 struct BasePRNGObject *minstd = stdlib_base_random_minstd_allocate( iseed ); 254 if ( minstd == NULL ) { 255 minstd_shuffle_free( obj ); // prevent memory leaks 256 return NULL; 257 } 258 // Create the shuffle table: 259 status = create_table( minstd, state->table ); 260 261 // Free the MINSTD PRNG: 262 stdlib_base_random_minstd_free( minstd ); // prevent memory leaks 263 264 // Check if creating the shuffle table failed: 265 if ( status != 0 ) { 266 minstd_shuffle_free( obj ); // prevent memory leaks 267 return NULL; 268 } 269 // Set the PRNG state: 270 state->state[ 0 ] = state->table[ 0 ]; // shuffled 271 state->state[ 1 ] = state->table[ 0 ]; // non-shuffled 272 273 return obj; 274 } 275 276 /** 277 * Frees a PRNG's allocated memory. 278 * 279 * @param obj PRNG object 280 * 281 * @example 282 * #include <stdlib.h> 283 * #include <stdio.h> 284 * #include <stdint.h> 285 * #include "stdlib/random/base.h" 286 * #include "stdlib/random/base/minstd_shuffle.h" 287 * 288 * // Create a PRNG: 289 * struct BasePRNGObject *obj = stdlib_base_random_minstd_shuffle_allocate( 12345 ); 290 * if ( obj == NULL ) { 291 * fprintf( stderr, "Error allocating memory.\n" ); 292 * exit( 1 ); 293 * } 294 * 295 * uint64_t r; 296 * int8_t status = obj->prng->next( obj, &r ); 297 * if ( status != 0 ) { 298 * fprintf( stderr, "Unexpected result.\n" ); 299 * exit( 1 ); 300 * } 301 * 302 * // ... 303 * 304 * status = obj->prng->next( obj, &r ); 305 * 306 * // ... 307 * 308 * status = obj->prng->next( obj, &r ); 309 * 310 * // ... 311 * 312 * // Free allocated memory: 313 * stdlib_base_random_minstd_shuffle_free( obj ); 314 */ 315 void stdlib_base_random_minstd_shuffle_free( struct BasePRNGObject *obj ) { 316 if ( obj == NULL || obj->prng != &minstd_shuffle_prng ) { 317 return; 318 } 319 obj->prng->free( obj ); 320 } 321 322 /** 323 * Returns a PRNG seed. 324 * 325 * ## Notes 326 * 327 * - The function returns `-1` if unable to resolve a PRNG seed and `0` otherwise. 328 * 329 * @param obj PRNG object 330 * @param out output address 331 * @return status code 332 * 333 * @example 334 * #include <stdlib.h> 335 * #include <stdio.h> 336 * #include <stdint.h> 337 * #include "stdlib/random/base.h" 338 * #include "stdlib/random/base/minstd_shuffle.h" 339 * 340 * // Create a PRNG: 341 * struct BasePRNGObject *obj = stdlib_base_random_minstd_shuffle_allocate( 12345 ); 342 * if ( obj == NULL ) { 343 * fprintf( stderr, "Error allocating memory.\n" ); 344 * exit( 1 ); 345 * } 346 * 347 * int32_t seed; 348 * int8_t status = stdlib_base_random_minstd_shuffle_seed( obj, &seed ); 349 * if ( status != 0 ) { 350 * fprintf( stderr, "Error encountered when attempting to retrieve the PRNG seed.\n" ); 351 * exit( 1 ); 352 * } 353 * 354 * // Use the seed to, e.g., create another PRNG which will generate the same sequence... 355 * 356 * // Free allocated memory: 357 * stdlib_base_random_minstd_shuffle_free( obj ); 358 */ 359 int8_t stdlib_base_random_minstd_shuffle_seed( const struct BasePRNGObject *obj, int32_t *out ) { 360 if ( obj == NULL || obj->prng != &minstd_shuffle_prng ) { 361 return -1; 362 } 363 // Retrieve the state object: 364 const stdlib_base_random_minstd_shuffle_state_t *state = (stdlib_base_random_minstd_shuffle_state_t *)( obj->state ); 365 366 // Set the output value: 367 *out = (int32_t)( state->seed ); 368 369 return 0; 370 } 371 372 /** 373 * Returns a **copy** of the current PRNG state. 374 * 375 * ## Notes 376 * 377 * - The user is responsible for freeing the allocated memory. 378 * 379 * @param obj PRNG object 380 * @return pointer to a copy of the PRNG's internal state or, if unable to allocate memory, a null pointer 381 * 382 * @example 383 * #include <stdlib.h> 384 * #include <stdio.h> 385 * #include <stdint.h> 386 * #include "stdlib/random/base.h" 387 * #include "stdlib/random/base/minstd_shuffle.h" 388 * 389 * // Create a PRNG: 390 * struct BasePRNGObject *obj = stdlib_base_random_minstd_shuffle_allocate( 12345 ); 391 * if ( obj == NULL ) { 392 * fprintf( stderr, "Error allocating memory.\n" ); 393 * exit( 1 ); 394 * } 395 * 396 * void *state = stdlib_base_random_minstd_shuffle_state( obj ); 397 * if ( state == NULL ) { 398 * fprintf( stderr, "Unable to retrieve PRNG state.\n" ); 399 * exit( 1 ); 400 * } 401 * 402 * // 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... 403 * 404 * // Free allocated memory: 405 * stdlib_base_random_minstd_shuffle_free( obj ); 406 * free( state ); 407 */ 408 void * stdlib_base_random_minstd_shuffle_state( const struct BasePRNGObject *obj ) { 409 if ( obj == NULL || obj->prng != &minstd_shuffle_prng ) { 410 return NULL; 411 } 412 void *state = malloc( obj->prng->state_size ); 413 if ( state == NULL ) { 414 return NULL; 415 } 416 memcpy( state, obj->state, obj->prng->state_size ); 417 return state; 418 } 419 420 /** 421 * Sets the PRNG state. 422 * 423 * ## Notes 424 * 425 * - The function returns `-1` if unable to set a PRNG state and `0` otherwise. 426 * 427 * @param obj PRNG object 428 * @param state state 429 * @return status code 430 * 431 * @example 432 * #include <stdlib.h> 433 * #include <stdio.h> 434 * #include <stdint.h> 435 * #include "stdlib/random/base.h" 436 * #include "stdlib/random/base/minstd_shuffle.h" 437 * 438 * // Create a PRNG: 439 * struct BasePRNGObject *obj = stdlib_base_random_minstd_shuffle_allocate( 12345 ); 440 * if ( obj == NULL ) { 441 * fprintf( stderr, "Error allocating memory.\n" ); 442 * exit( 1 ); 443 * } 444 * 445 * uint64_t r; 446 * int8_t status = obj->prng->next( obj, &r ); 447 * if ( status != 0 ) { 448 * fprintf( stderr, "Unexpected result.\n" ); 449 * exit( 1 ); 450 * } 451 * 452 * // ... 453 * 454 * status = obj->prng->next( obj, &r ); 455 * 456 * // ... 457 * 458 * status = obj->prng->next( obj, &r ); 459 * 460 * // ... 461 * 462 * // Retrieve the current PRNG state... 463 * void *state = stdlib_base_random_minstd_shuffle_state( obj ); 464 * if ( state == NULL ) { 465 * fprintf( stderr, "Error encountered when attempting to retrieve PRNG state.\n" ); 466 * exit( 1 ); 467 * } 468 * 469 * // ... 470 * 471 * status = obj->prng->next( obj, &r ); 472 * 473 * // ... 474 * 475 * status = obj->prng->next( obj, &r ); 476 * 477 * // ... 478 * 479 * // Reset the PRNG to a previous state... 480 * status = stdlib_base_random_minstd_shuffle_set( obj, state ); 481 * if ( status != 0 ) { 482 * fprintf( stderr, "Error encountered when attempting to set PRNG state.\n" ); 483 * exit( 1 ); 484 * } 485 * 486 * // ... 487 * 488 * status = obj->prng->next( obj, &r ); 489 * 490 * // ... 491 * 492 * status = obj->prng->next( obj, &r ); 493 * 494 * // ... 495 * 496 * // Free allocated memory: 497 * stdlib_base_random_minstd_shuffle_free( obj ); 498 * free( state ); 499 */ 500 int8_t stdlib_base_random_minstd_shuffle_set( struct BasePRNGObject *obj, const void *state ) { 501 if ( obj == NULL || state == NULL || obj->prng != &minstd_shuffle_prng ) { 502 return -1; 503 } 504 memcpy( obj->state, state, obj->prng->state_size ); 505 return 0; 506 }