rand.c revision 354ebb48db8e66a853a58379a4808d5dcd1ceac3
155d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak/* 255d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak * Copyright (c) International Business Machines Corp., 2001-2004 355d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak * 455d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak * This program is free software; you can redistribute it and/or modify 555d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak * it under the terms of the GNU General Public License as published by 655d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak * the Free Software Foundation; either version 2 of the License, or 755d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak * (at your option) any later version. 855d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak * 955d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak * This program is distributed in the hope that it will be useful, 1055d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak * but WITHOUT ANY WARRANTY; without even the implied warranty of 1155d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See 1255d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak * the GNU General Public License for more details. 1355d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak * 1455d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak * You should have received a copy of the GNU General Public License 1555d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak * along with this program; if not, write to the Free Software 164548c6cf9bcdd96d8303caa4130ab638b61f8a30Wanlong Gao * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 1755d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak */ 1855d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak#include <stdlib.h> 1955d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak#include <stdio.h> 2055d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak#include <sys/types.h> 2155d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak#include <sys/stat.h> 2255d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak#include <sys/time.h> 2355d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak#include <fcntl.h> 2455d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak#include <unistd.h> 2555d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak#include <limits.h> 2655d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak#include <inttypes.h> 2755d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak#include <assert.h> 2855d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak 2955d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak#include "config.h" 3055d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak#include "rand.h" 3155d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak#include "util.h" 3255d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak 3355d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak#define RANDSRC "/dev/urandom" 3455d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak 3555d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modakstatic int randfd = -1; 3655d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak 3755d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak/* close the file after we're done with the benchmark */ 3855d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modakvoid randcleanup(void) 3955d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak{ 4055d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak if (randfd > 0) 4155d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak close(randfd); 4255d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak} 4355d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak 4455d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak/* We fill up the array with random bits from RANDSRC here and set index */ 4555d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak/* to 0 */ 4655d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak/* pre: state->size must be set and state->mt must be allocated! */ 47354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gaostatic void sgenrand(randdata_t * state) 4855d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak{ 4955d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak int got = 0; 5055d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak got = read(randfd, state->mt, state->size); 5155d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak if (got != state->size) { 52354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gao int i; 5355d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak /* fall back on lrand48 */ 5455d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak /* printf("fallback_rand\n"); */ 5555d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak 56354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gao for (i = got; i < state->size; i += 4) { 57354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gao long int rand = 0; 5855d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak#ifdef HAVE_LRAND48 5955d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak lrand48_r(&(state->data), &rand); 6055d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak#else 6155d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak rand = random(); 6255d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak#endif 6355d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak assert(rand != 0); 64354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gao state->mt[i] = (rand >> 24) & (512 - 1); 65354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gao state->mt[i + 1] = (rand >> 16) & (512 - 1); 66354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gao state->mt[i + 2] = (rand >> 8) & (512 - 1); 67354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gao state->mt[i + 3] = (rand) & (512 - 1); 6855d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak } 6955d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak 7055d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak } 7155d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak state->mti = 0; 7255d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak} 7355d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak 7455d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak/* returns 8 random bits */ 75354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gaostatic uint8_t genrand8(randdata_t * state) 7655d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak{ 7755d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak unsigned long ret = 0; 7855d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak if (state->mti >= state->size) { 7955d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak/* sgenrand(state); */ 8055d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak state->mti = 0; 8155d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak } 8255d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak ret = state->mt[state->mti]; 8355d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak state->mti++; 8455d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak return ret; 8555d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak} 8655d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak 8755d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak/* returns 32 random bits */ 88354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gaostatic uint32_t genrand32(randdata_t * state) 8955d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak{ 9055d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak uint8_t bytes[4]; 9155d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak uint32_t ret = 0; 9255d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak 9355d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak bytes[0] = genrand8(state); 9455d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak bytes[1] = genrand8(state); 9555d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak bytes[2] = genrand8(state); 9655d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak bytes[3] = genrand8(state); 9755d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak 98354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gao ret = *((uint32_t *) bytes); /* !!! hack */ 9955d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak return ret; 10055d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak} 10155d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak 102354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gaovoid init_random(randdata_t * state, uint32_t iter) 10355d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak{ 10455d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak struct timeval time; 10555d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak if (iter == 0) 10655d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak state->size = MIN_RANDBUF_SIZE * AVG_ITR_RNDBTS; 10755d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak else if (iter > MAX_RANDBUF_SIZE) 10855d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak state->size = MAX_RANDBUF_SIZE * AVG_ITR_RNDBTS; 10955d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak else 11055d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak state->size = iter * AVG_ITR_RNDBTS; 11155d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak 11255d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak state->mt = ffsb_malloc(state->size); 11355d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak 11455d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak /* !!!! racy? add pthread_once stuff later */ 11555d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak if ((randfd < 0) && (randfd = open(RANDSRC, O_RDONLY)) < 0) { 11655d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak perror("open " RANDSRC); 11755d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak exit(1); 11855d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak } 11955d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak sgenrand(state); 12055d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak gettimeofday(&time, NULL); 12155d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak#ifdef HAVE_LRAND48 12255d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak srand48_r(time.tv_sec, &state->data); 12355d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak#endif 12455d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak} 12555d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak 126354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gaovoid destroy_random(randdata_t * rd) 12755d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak{ 12855d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak free(rd->mt); 12955d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak} 13055d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak 13155d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak/* 13255d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak * I've taken the liberty of slightly redesigning this stuff. 13355d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak * Instead of simply getting the full word of random bits 13455d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak * and throwing away most of it using the mod operator, 13555d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak * we should only get byte-sized chunks of random bits and 13655d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak * construct our random number that way with less wasteage - SR 13755d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak */ 138354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gaouint32_t getrandom(randdata_t * state, uint32_t mod) 13955d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak{ 14055d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak 141354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gao uint8_t bytes[4] = { 0, 0, 0, 0 }; 142354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gao uint32_t ret; 143354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gao int num_bytes = 4; 144354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gao int i; 14555d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak 146354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gao if ((mod == 0) || (mod == 1)) 147354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gao return 0; 14855d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak 149354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gao if (!(mod >> 8)) 150354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gao num_bytes = 1; 151354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gao else if (!(mod >> 16)) 152354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gao num_bytes = 2; 153354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gao else if (!(mod >> 24)) 154354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gao num_bytes = 3; 15555d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak 156354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gao for (i = 0; i < num_bytes; i++) 157354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gao bytes[i] = genrand8(state); 15855d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak 159354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gao ret = (bytes[3] << 24) + (bytes[2] << 16) + (bytes[1] << 8) + bytes[0]; 16055d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak 161354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gao return ret % mod; 16255d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak} 16355d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak 164354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gaouint64_t getllrandom(randdata_t * state, uint64_t mod) 16555d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak{ 16655d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak uint64_t result = 0; 167354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gao uint64_t high = 0; 168354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gao uint32_t low = 0; 16955d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak 17055d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak if (mod == 0) 17155d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak return 0; 17255d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak 17355d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak /* ULONG_MAX comes from limits.h */ 17455d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak if (mod < ULONG_MAX) 175354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gao return (uint64_t) getrandom(state, (uint32_t) mod); 17655d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak 17755d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak high = genrand32(state); 17855d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak 179354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gao low = genrand32(state); 18055d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak 18155d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak result = high << 32; 182354ebb48db8e66a853a58379a4808d5dcd1ceac3Wanlong Gao result |= (uint64_t) low; 18355d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak 18455d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak assert(result != 0); 18555d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak assert(result > 0); 18655d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak 18755d04e4a11434fcdb0435b7fd0f8b1daf38bf3c4subrata_modak return result % mod; 188ec6edca7aa42b6affd989ef91b5897f96795e40fChris Dearman} 189