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