| 1 |
/* xf86drmRandom.c -- "Minimal Standard" PRNG Implementation |
| 2 |
* Created: Mon Apr 19 08:28:13 1999 by [email protected] |
| 3 |
* |
| 4 |
* Copyright 1999 Precision Insight, Inc., Cedar Park, Texas. |
| 5 |
* All Rights Reserved. |
| 6 |
* |
| 7 |
* Permission is hereby granted, free of charge, to any person obtaining a |
| 8 |
* copy of this software and associated documentation files (the "Software"), |
| 9 |
* to deal in the Software without restriction, including without limitation |
| 10 |
* the rights to use, copy, modify, merge, publish, distribute, sublicense, |
| 11 |
* and/or sell copies of the Software, and to permit persons to whom the |
| 12 |
* Software is furnished to do so, subject to the following conditions: |
| 13 |
* |
| 14 |
* The above copyright notice and this permission notice (including the next |
| 15 |
* paragraph) shall be included in all copies or substantial portions of the |
| 16 |
* Software. |
| 17 |
* |
| 18 |
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| 19 |
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
| 20 |
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL |
| 21 |
* PRECISION INSIGHT AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR |
| 22 |
* OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, |
| 23 |
* ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER |
| 24 |
* DEALINGS IN THE SOFTWARE. |
| 25 |
* |
| 26 |
* Authors: Rickard E. (Rik) Faith <[email protected]> |
| 27 |
* |
| 28 |
* DESCRIPTION |
| 29 |
* |
| 30 |
* This file contains a simple, straightforward implementation of the Park |
| 31 |
* & Miller "Minimal Standard" PRNG [PM88, PMS93], which is a Lehmer |
| 32 |
* multiplicative linear congruential generator (MLCG) with a period of |
| 33 |
* 2^31-1. |
| 34 |
* |
| 35 |
* This implementation is intended to provide a reliable, portable PRNG |
| 36 |
* that is suitable for testing a hash table implementation and for |
| 37 |
* implementing skip lists. |
| 38 |
* |
| 39 |
* FUTURE ENHANCEMENTS |
| 40 |
* |
| 41 |
* If initial seeds are not selected randomly, two instances of the PRNG |
| 42 |
* can be correlated. [Knuth81, pp. 32-33] describes a shuffling technique |
| 43 |
* that can eliminate this problem. |
| 44 |
* |
| 45 |
* If PRNGs are used for simulation, the period of the current |
| 46 |
* implementation may be too short. [LE88] discusses methods of combining |
| 47 |
* MLCGs to produce much longer periods, and suggests some alternative |
| 48 |
* values for A and M. [LE90 and Sch92] also provide information on |
| 49 |
* long-period PRNGs. |
| 50 |
* |
| 51 |
* REFERENCES |
| 52 |
* |
| 53 |
* [Knuth81] Donald E. Knuth. The Art of Computer Programming. Volume 2: |
| 54 |
* Seminumerical Algorithms. Reading, Massachusetts: Addison-Wesley, 1981. |
| 55 |
* |
| 56 |
* [LE88] Pierre L'Ecuyer. "Efficient and Portable Combined Random Number |
| 57 |
* Generators". CACM 31(6), June 1988, pp. 742-774. |
| 58 |
* |
| 59 |
* [LE90] Pierre L'Ecuyer. "Random Numbers for Simulation". CACM 33(10, |
| 60 |
* October 1990, pp. 85-97. |
| 61 |
* |
| 62 |
* [PM88] Stephen K. Park and Keith W. Miller. "Random Number Generators: |
| 63 |
* Good Ones are Hard to Find". CACM 31(10), October 1988, pp. 1192-1201. |
| 64 |
* |
| 65 |
* [Sch92] Bruce Schneier. "Pseudo-Ransom Sequence Generator for 32-Bit |
| 66 |
* CPUs". Dr. Dobb's Journal 17(2), February 1992, pp. 34, 37-38, 40. |
| 67 |
* |
| 68 |
* [PMS93] Stephen K. Park, Keith W. Miller, and Paul K. Stockmeyer. In |
| 69 |
* "Technical Correspondence: Remarks on Choosing and Implementing Random |
| 70 |
* Number Generators". CACM 36(7), July 1993, pp. 105-110. |
| 71 |
* |
| 72 |
*/ |
| 73 |
|
| 74 |
#include <stdio.h> |
| 75 |
#include <stdlib.h> |
| 76 |
|
| 77 |
#include "xf86drm.h" |
| 78 |
#include "xf86drmRandom.h" |
| 79 |
|
| 80 |
#define RANDOM_MAGIC 0xfeedbeef |
| 81 |
|
| 82 |
void *drmRandomCreate(unsigned long seed) |
| 83 |
{ |
| 84 |
RandomState *state; |
| 85 |
|
| 86 |
state = (RandomState *)drmMalloc(sizeof(*state)); |
| 87 |
if (!state) return nullptr; |
| 88 |
state->magic = RANDOM_MAGIC; |
| 89 |
#if 0 |
| 90 |
/* Park & Miller, October 1988 */ |
| 91 |
state->a = 16807; |
| 92 |
state->m = 2147483647; |
| 93 |
state->check = 1043618065; /* After 10000 iterations */ |
| 94 |
#else |
| 95 |
/* Park, Miller, and Stockmeyer, July 1993 */ |
| 96 |
state->a = 48271; |
| 97 |
state->m = 2147483647; |
| 98 |
state->check = 399268537; /* After 10000 iterations */ |
| 99 |
#endif |
| 100 |
state->q = state->m / state->a; |
| 101 |
state->r = state->m % state->a; |
| 102 |
|
| 103 |
state->seed = seed; |
| 104 |
/* Check for illegal boundary conditions, |
| 105 |
and choose closest legal value. */ |
| 106 |
if (state->seed <= 0) state->seed = 1; |
| 107 |
if (state->seed >= state->m) state->seed = state->m - 1; |
| 108 |
|
| 109 |
return state; |
| 110 |
} |
| 111 |
|
| 112 |
int drmRandomDestroy(void *state) |
| 113 |
{ |
| 114 |
drmFree(state); |
| 115 |
return 0; |
| 116 |
} |
| 117 |
|
| 118 |
unsigned long drmRandom(void *state) |
| 119 |
{ |
| 120 |
RandomState *s = (RandomState *)state; |
| 121 |
unsigned long hi; |
| 122 |
unsigned long lo; |
| 123 |
|
| 124 |
hi = s->seed / s->q; |
| 125 |
lo = s->seed % s->q; |
| 126 |
s->seed = s->a * lo - s->r * hi; |
| 127 |
if ((s->a * lo) <= (s->r * hi)) s->seed += s->m; |
| 128 |
|
| 129 |
return s->seed; |
| 130 |
} |