Back to index

libdrm  2.4.37
xf86drmRandom.c
Go to the documentation of this file.
00001 /* xf86drmRandom.c -- "Minimal Standard" PRNG Implementation
00002  * Created: Mon Apr 19 08:28:13 1999 by faith@precisioninsight.com
00003  *
00004  * Copyright 1999 Precision Insight, Inc., Cedar Park, Texas.
00005  * All Rights Reserved.
00006  *
00007  * Permission is hereby granted, free of charge, to any person obtaining a
00008  * copy of this software and associated documentation files (the "Software"),
00009  * to deal in the Software without restriction, including without limitation
00010  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
00011  * and/or sell copies of the Software, and to permit persons to whom the
00012  * Software is furnished to do so, subject to the following conditions:
00013  * 
00014  * The above copyright notice and this permission notice (including the next
00015  * paragraph) shall be included in all copies or substantial portions of the
00016  * Software.
00017  * 
00018  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
00019  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
00020  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
00021  * PRECISION INSIGHT AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
00022  * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
00023  * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
00024  * DEALINGS IN THE SOFTWARE.
00025  * 
00026  * Authors: Rickard E. (Rik) Faith <faith@valinux.com>
00027  *
00028  * DESCRIPTION
00029  *
00030  * This file contains a simple, straightforward implementation of the Park
00031  * & Miller "Minimal Standard" PRNG [PM88, PMS93], which is a Lehmer
00032  * multiplicative linear congruential generator (MLCG) with a period of
00033  * 2^31-1.
00034  *
00035  * This implementation is intended to provide a reliable, portable PRNG
00036  * that is suitable for testing a hash table implementation and for
00037  * implementing skip lists.
00038  *
00039  * FUTURE ENHANCEMENTS
00040  *
00041  * If initial seeds are not selected randomly, two instances of the PRNG
00042  * can be correlated.  [Knuth81, pp. 32-33] describes a shuffling technique
00043  * that can eliminate this problem.
00044  *
00045  * If PRNGs are used for simulation, the period of the current
00046  * implementation may be too short.  [LE88] discusses methods of combining
00047  * MLCGs to produce much longer periods, and suggests some alternative
00048  * values for A and M.  [LE90 and Sch92] also provide information on
00049  * long-period PRNGs.
00050  *
00051  * REFERENCES
00052  *
00053  * [Knuth81] Donald E. Knuth. The Art of Computer Programming.  Volume 2:
00054  * Seminumerical Algorithms.  Reading, Massachusetts: Addison-Wesley, 1981.
00055  *
00056  * [LE88] Pierre L'Ecuyer. "Efficient and Portable Combined Random Number
00057  * Generators".  CACM 31(6), June 1988, pp. 742-774.
00058  *
00059  * [LE90] Pierre L'Ecuyer. "Random Numbers for Simulation". CACM 33(10,
00060  * October 1990, pp. 85-97.
00061  *
00062  * [PM88] Stephen K. Park and Keith W. Miller. "Random Number Generators:
00063  * Good Ones are Hard to Find". CACM 31(10), October 1988, pp. 1192-1201.
00064  *
00065  * [Sch92] Bruce Schneier. "Pseudo-Ransom Sequence Generator for 32-Bit
00066  * CPUs".  Dr. Dobb's Journal 17(2), February 1992, pp. 34, 37-38, 40.
00067  *
00068  * [PMS93] Stephen K. Park, Keith W. Miller, and Paul K. Stockmeyer.  In
00069  * "Technical Correspondence: Remarks on Choosing and Implementing Random
00070  * Number Generators". CACM 36(7), July 1993, pp. 105-110.
00071  *
00072  */
00073 
00074 #include <stdio.h>
00075 #include <stdlib.h>
00076 
00077 #define RANDOM_MAIN 0
00078 
00079 #if !RANDOM_MAIN
00080 # include "xf86drm.h"
00081 #endif
00082 
00083 #define RANDOM_MAGIC 0xfeedbeef
00084 #define RANDOM_DEBUG 0
00085 
00086 #if RANDOM_MAIN
00087 #define RANDOM_ALLOC malloc
00088 #define RANDOM_FREE  free
00089 #else
00090 #define RANDOM_ALLOC drmMalloc
00091 #define RANDOM_FREE  drmFree
00092 #endif
00093 
00094 typedef struct RandomState {
00095     unsigned long magic;
00096     unsigned long a;
00097     unsigned long m;
00098     unsigned long q;        /* m div a */
00099     unsigned long r;        /* m mod a */
00100     unsigned long check;
00101     long          seed;
00102 } RandomState;
00103 
00104 #if RANDOM_MAIN
00105 extern void          *drmRandomCreate(unsigned long seed);
00106 extern int           drmRandomDestroy(void *state);
00107 extern unsigned long drmRandom(void *state);
00108 extern double        drmRandomDouble(void *state);
00109 #endif
00110 
00111 void *drmRandomCreate(unsigned long seed)
00112 {
00113     RandomState  *state;
00114 
00115     state           = RANDOM_ALLOC(sizeof(*state));
00116     if (!state) return NULL;
00117     state->magic    = RANDOM_MAGIC;
00118 #if 0
00119                             /* Park & Miller, October 1988 */
00120     state->a        = 16807;
00121     state->m        = 2147483647;
00122     state->check    = 1043618065; /* After 10000 iterations */
00123 #else
00124                             /* Park, Miller, and Stockmeyer, July 1993 */
00125     state->a        = 48271;
00126     state->m        = 2147483647;
00127     state->check    = 399268537; /* After 10000 iterations */
00128 #endif
00129     state->q        = state->m / state->a;
00130     state->r        = state->m % state->a;
00131 
00132     state->seed     = seed;
00133                             /* Check for illegal boundary conditions,
00134                                    and choose closest legal value. */
00135     if (state->seed <= 0)        state->seed = 1;
00136     if (state->seed >= state->m) state->seed = state->m - 1;
00137 
00138     return state;
00139 }
00140 
00141 int drmRandomDestroy(void *state)
00142 {
00143     RANDOM_FREE(state);
00144     return 0;
00145 }
00146 
00147 unsigned long drmRandom(void *state)
00148 {
00149     RandomState   *s = (RandomState *)state;
00150     long          hi;
00151     long          lo;
00152 
00153     hi      = s->seed / s->q;
00154     lo      = s->seed % s->q;
00155     s->seed = s->a * lo - s->r * hi;
00156     if (s->seed <= 0) s->seed += s->m;
00157 
00158     return s->seed;
00159 }
00160 
00161 double drmRandomDouble(void *state)
00162 {
00163     RandomState *s = (RandomState *)state;
00164     
00165     return (double)drmRandom(state)/(double)s->m;
00166 }
00167 
00168 #if RANDOM_MAIN
00169 static void check_period(long seed)
00170 {
00171     unsigned long count = 0;
00172     unsigned long initial;
00173     void          *state;
00174     
00175     state = drmRandomCreate(seed);
00176     initial = drmRandom(state);
00177     ++count;
00178     while (initial != drmRandom(state)) {
00179        if (!++count) break;
00180     }
00181     printf("With seed of %10ld, period = %10lu (0x%08lx)\n",
00182           seed, count, count);
00183     drmRandomDestroy(state);
00184 }
00185 
00186 int main(void)
00187 {
00188     RandomState   *state;
00189     int           i;
00190     unsigned long rand;
00191 
00192     state = drmRandomCreate(1);
00193     for (i = 0; i < 10000; i++) {
00194        rand = drmRandom(state);
00195     }
00196     printf("After 10000 iterations: %lu (%lu expected): %s\n",
00197           rand, state->check,
00198           rand - state->check ? "*INCORRECT*" : "CORRECT");
00199     drmRandomDestroy(state);
00200 
00201     printf("Checking periods...\n");
00202     check_period(1);
00203     check_period(2);
00204     check_period(31415926);
00205     
00206     return 0;
00207 }
00208 #endif