1b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss/* xf86drmRandom.c -- "Minimal Standard" PRNG Implementation 2b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * Created: Mon Apr 19 08:28:13 1999 by faith@precisioninsight.com 3b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * 4b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * Copyright 1999 Precision Insight, Inc., Cedar Park, Texas. 5b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * All Rights Reserved. 6b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * 7b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * Permission is hereby granted, free of charge, to any person obtaining a 8b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * copy of this software and associated documentation files (the "Software"), 9b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * to deal in the Software without restriction, including without limitation 10b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * the rights to use, copy, modify, merge, publish, distribute, sublicense, 11b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * and/or sell copies of the Software, and to permit persons to whom the 12b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * Software is furnished to do so, subject to the following conditions: 13b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * 14b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * The above copyright notice and this permission notice (including the next 15b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * paragraph) shall be included in all copies or substantial portions of the 16b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * Software. 17b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * 18b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 19b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 20b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 21b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * PRECISION INSIGHT AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR 22b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, 23b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 24b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * DEALINGS IN THE SOFTWARE. 25b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * 261c8b2b5e06f7967babfa49b9dc8bf24316bfe201Rik Faith * Authors: Rickard E. (Rik) Faith <faith@valinux.com> 271c8b2b5e06f7967babfa49b9dc8bf24316bfe201Rik Faith * 28b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * DESCRIPTION 29b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * 30b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * This file contains a simple, straightforward implementation of the Park 31b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * & Miller "Minimal Standard" PRNG [PM88, PMS93], which is a Lehmer 32b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * multiplicative linear congruential generator (MLCG) with a period of 33b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * 2^31-1. 34b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * 35b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * This implementation is intended to provide a reliable, portable PRNG 36b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * that is suitable for testing a hash table implementation and for 37b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * implementing skip lists. 38b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * 39b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * FUTURE ENHANCEMENTS 40b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * 41b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * If initial seeds are not selected randomly, two instances of the PRNG 42b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * can be correlated. [Knuth81, pp. 32-33] describes a shuffling technique 43b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * that can eliminate this problem. 44b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * 45b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * If PRNGs are used for simulation, the period of the current 46b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * implementation may be too short. [LE88] discusses methods of combining 47b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * MLCGs to produce much longer periods, and suggests some alternative 48b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * values for A and M. [LE90 and Sch92] also provide information on 49b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * long-period PRNGs. 50b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * 51b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * REFERENCES 52b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * 53b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * [Knuth81] Donald E. Knuth. The Art of Computer Programming. Volume 2: 54b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * Seminumerical Algorithms. Reading, Massachusetts: Addison-Wesley, 1981. 55b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * 56b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * [LE88] Pierre L'Ecuyer. "Efficient and Portable Combined Random Number 57b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * Generators". CACM 31(6), June 1988, pp. 742-774. 58b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * 59b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * [LE90] Pierre L'Ecuyer. "Random Numbers for Simulation". CACM 33(10, 60b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * October 1990, pp. 85-97. 61b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * 62b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * [PM88] Stephen K. Park and Keith W. Miller. "Random Number Generators: 63b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * Good Ones are Hard to Find". CACM 31(10), October 1988, pp. 1192-1201. 64b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * 65b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * [Sch92] Bruce Schneier. "Pseudo-Ransom Sequence Generator for 32-Bit 66b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * CPUs". Dr. Dobb's Journal 17(2), February 1992, pp. 34, 37-38, 40. 67b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * 68b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * [PMS93] Stephen K. Park, Keith W. Miller, and Paul K. Stockmeyer. In 69b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * "Technical Correspondence: Remarks on Choosing and Implementing Random 70b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * Number Generators". CACM 36(7), July 1993, pp. 105-110. 71b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss * 72b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss */ 73b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss 74b69b42634619076d4163ae144f0154880d1928cdGeorge Sapountzis#include <stdio.h> 75b69b42634619076d4163ae144f0154880d1928cdGeorge Sapountzis#include <stdlib.h> 76f28dddb5515cb1c16f8c29e025195ea29d9f01d4Adam Jackson 77b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss#define RANDOM_MAIN 0 78b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss 79b69b42634619076d4163ae144f0154880d1928cdGeorge Sapountzis#if !RANDOM_MAIN 80b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss# include "xf86drm.h" 81b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss#endif 82b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss 83b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss#define RANDOM_MAGIC 0xfeedbeef 84b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss#define RANDOM_DEBUG 0 85b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss 86b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss#if RANDOM_MAIN 87b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss#define RANDOM_ALLOC malloc 88b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss#define RANDOM_FREE free 89b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss#else 90b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss#define RANDOM_ALLOC drmMalloc 91b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss#define RANDOM_FREE drmFree 92b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss#endif 93b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss 94b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strausstypedef struct RandomState { 95b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss unsigned long magic; 96b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss unsigned long a; 97b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss unsigned long m; 98b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss unsigned long q; /* m div a */ 99b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss unsigned long r; /* m mod a */ 100b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss unsigned long check; 101b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss long seed; 102b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss} RandomState; 103b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss 104b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss#if RANDOM_MAIN 10522e41ef08338ae6dd59acbe6d4d8e50d83672816Adam Jacksonextern void *drmRandomCreate(unsigned long seed); 10622e41ef08338ae6dd59acbe6d4d8e50d83672816Adam Jacksonextern int drmRandomDestroy(void *state); 10722e41ef08338ae6dd59acbe6d4d8e50d83672816Adam Jacksonextern unsigned long drmRandom(void *state); 10822e41ef08338ae6dd59acbe6d4d8e50d83672816Adam Jacksonextern double drmRandomDouble(void *state); 109b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss#endif 110b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss 11122e41ef08338ae6dd59acbe6d4d8e50d83672816Adam Jacksonvoid *drmRandomCreate(unsigned long seed) 112b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss{ 113b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss RandomState *state; 114b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss 115b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss state = RANDOM_ALLOC(sizeof(*state)); 116b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss if (!state) return NULL; 117b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss state->magic = RANDOM_MAGIC; 118b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss#if 0 119b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss /* Park & Miller, October 1988 */ 120b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss state->a = 16807; 121b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss state->m = 2147483647; 122b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss state->check = 1043618065; /* After 10000 iterations */ 123b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss#else 124b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss /* Park, Miller, and Stockmeyer, July 1993 */ 125b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss state->a = 48271; 126b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss state->m = 2147483647; 127b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss state->check = 399268537; /* After 10000 iterations */ 128b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss#endif 129b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss state->q = state->m / state->a; 130b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss state->r = state->m % state->a; 131b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss 132b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss state->seed = seed; 133b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss /* Check for illegal boundary conditions, 134b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss and choose closest legal value. */ 135b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss if (state->seed <= 0) state->seed = 1; 136b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss if (state->seed >= state->m) state->seed = state->m - 1; 137b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss 138b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss return state; 139b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss} 140b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss 14122e41ef08338ae6dd59acbe6d4d8e50d83672816Adam Jacksonint drmRandomDestroy(void *state) 142b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss{ 143b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss RANDOM_FREE(state); 144b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss return 0; 145b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss} 146b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss 14722e41ef08338ae6dd59acbe6d4d8e50d83672816Adam Jacksonunsigned long drmRandom(void *state) 148b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss{ 149b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss RandomState *s = (RandomState *)state; 150b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss long hi; 151b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss long lo; 152b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss 153b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss hi = s->seed / s->q; 154b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss lo = s->seed % s->q; 155b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss s->seed = s->a * lo - s->r * hi; 156b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss if (s->seed <= 0) s->seed += s->m; 157b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss 158b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss return s->seed; 159b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss} 160b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss 16122e41ef08338ae6dd59acbe6d4d8e50d83672816Adam Jacksondouble drmRandomDouble(void *state) 162b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss{ 163b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss RandomState *s = (RandomState *)state; 164b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss 16522e41ef08338ae6dd59acbe6d4d8e50d83672816Adam Jackson return (double)drmRandom(state)/(double)s->m; 166b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss} 167b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss 168b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss#if RANDOM_MAIN 169b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Straussstatic void check_period(long seed) 170b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss{ 171b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss unsigned long count = 0; 172b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss unsigned long initial; 173b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss void *state; 174b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss 17522e41ef08338ae6dd59acbe6d4d8e50d83672816Adam Jackson state = drmRandomCreate(seed); 17622e41ef08338ae6dd59acbe6d4d8e50d83672816Adam Jackson initial = drmRandom(state); 177b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss ++count; 17822e41ef08338ae6dd59acbe6d4d8e50d83672816Adam Jackson while (initial != drmRandom(state)) { 179b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss if (!++count) break; 180b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss } 181b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss printf("With seed of %10ld, period = %10lu (0x%08lx)\n", 182b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss seed, count, count); 18322e41ef08338ae6dd59acbe6d4d8e50d83672816Adam Jackson drmRandomDestroy(state); 184b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss} 185b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss 186b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Straussint main(void) 187b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss{ 188b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss RandomState *state; 189b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss int i; 190b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss unsigned long rand; 191b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss 19222e41ef08338ae6dd59acbe6d4d8e50d83672816Adam Jackson state = drmRandomCreate(1); 193b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss for (i = 0; i < 10000; i++) { 19422e41ef08338ae6dd59acbe6d4d8e50d83672816Adam Jackson rand = drmRandom(state); 195b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss } 196b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss printf("After 10000 iterations: %lu (%lu expected): %s\n", 197b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss rand, state->check, 198b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss rand - state->check ? "*INCORRECT*" : "CORRECT"); 19922e41ef08338ae6dd59acbe6d4d8e50d83672816Adam Jackson drmRandomDestroy(state); 200b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss 201b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss printf("Checking periods...\n"); 202b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss check_period(1); 203b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss check_period(2); 204b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss check_period(31415926); 205b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss 206b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss return 0; 207b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss} 208b3a5766992019fc5f44cc9afd01b2617b76f47aDaryll Strauss#endif 209