blob: 9c05cf727916741d2f122a654595d89dfad7e893 [file] [log] [blame]
/*
* Copyright (c) 2000 Silicon Graphics, Inc. All Rights Reserved.
*
* This program is free software; you can redistribute it and/or modify it
* under the terms of version 2 of the GNU General Public License as
* published by the Free Software Foundation.
*
* This program is distributed in the hope that it would be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
*
* Further, this software is distributed without any warranty that it is
* free of the rightful claim of any third person regarding infringement
* or the like. Any license provided herein, whether implied or
* otherwise, applies only to this software file. Patent licenses, if
* any, provided herein do not apply to combinations of this program with
* other software, or any other product whatsoever.
*
* You should have received a copy of the GNU General Public License along
* with this program; if not, write the Free Software Foundation, Inc., 59
* Temple Place - Suite 330, Boston MA 02111-1307, USA.
*
* Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
* Mountain View, CA 94043, or:
*
* http://www.sgi.com
*
* For further information regarding this notice, see:
*
* http://oss.sgi.com/projects/GenInfo/NoticeExplan/
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include "random_range.h"
/*
* Internal format of the range array set up by parse_range()
*/
struct range {
int min;
int max;
int mult;
};
/*
* parse_ranges() is a function to parse a comma-separated list of range
* tokens each having the following form:
*
* num
* or
* min:max[:mult]
*
* any of the values may be blank (ie. min::mult, :max, etc.) and default
* values for missing arguments may be supplied by the caller.
*
* The special first form is short hand for 'num:num'.
*
* After parsing the string, the ranges are put into an array of integers,
* which is malloc'd by the routine. The min, max, and mult entries of each
* range can be extracted from the array using the range_min(), range_max(),
* and range_mult() functions.
*
* It is the responsibility of the caller to free the space allocated by
* parse_ranges() - a single call to free() will free the space.
*
* str The string to parse - assumed to be a comma-separated
* list of tokens having the above format.
* defmin default value to plug in for min, if it is missing
* defmax default value to plug in for max, if it is missing
* defmult default value to plug in for mult, if missing
* parse_func A user-supplied function pointer, which parse_ranges()
* can call to parse the min, max, and mult strings. This
* allows for customized number formats. The function
* MUST have the following prototype:
* parse_func(char *str, int *val)
* The function should return -1 if str cannot be parsed
* into an integer, or >= 0 if it was successfully
* parsed. The resulting integer will be stored in
* *val. If parse_func is NULL, parse_ranges will parse
* the tokens in a manner consistent with the the sscanf
* %i format.
* range_ptr A user-supplied char **, which will be set to point
* at malloc'd space which holds the parsed range
* values. If range_ptr is NULL, parse_ranges() just
* parses the string. The data returned in range_ptr
* should not be processed directly - use the functions
* range_min(), range_max(), and range_mult() to access
* data for a given range.
* errptr user-supplied char ** which can be set to point to a
* static error string. If errptr is NULL, it is ignored.
*
* parse_range() returns -1 on error, or the number of ranges parsed.
*/
static int str_to_int();
static long long divider(long long, long long, long long, long long);
int
parse_ranges(str, defmin, defmax, defmult, parse_func, rangeptr, errptr)
char *str;
int defmin;
int defmax;
int defmult;
int (*parse_func)();
char **rangeptr;
char **errptr;
{
int ncommas;
char *tmpstr, *cp, *tok, *n1str, *n2str, *multstr;
struct range *rp, *ranges;
static char errmsg[256];
if (errptr != NULL) {
*errptr = errmsg;
}
for (ncommas = 0, cp = str; *cp != '\0'; cp++) {
if (*cp == ',') {
ncommas++;
}
}
if (parse_func == NULL) {
parse_func = str_to_int;
}
tmpstr = strdup(str);
ranges = (struct range *)malloc((ncommas+1) * sizeof(struct range));
rp = ranges;
tok = strtok(tmpstr, ",");
while (tok != NULL) {
n1str = tok;
n2str = NULL;
multstr = NULL;
rp->min = defmin;
rp->max = defmax;
rp->mult = defmult;
if ((cp = strchr(n1str, ':')) != NULL) {
*cp = '\0';
n2str = cp+1;
if ((cp = strchr(n2str, ':')) != NULL) {
*cp = '\0';
multstr = cp+1;
}
}
/*
* Parse the 'min' field - if it is zero length (:n2[:mult]
* format), retain the default value, otherwise, pass the
* string to the parse function.
*/
if ((int)strlen(n1str) > 0) {
if ((*parse_func)(n1str, &rp->min) < 0) {
sprintf(errmsg, "error parsing string %s into an integer", n1str);
free(tmpstr);
free(ranges);
return -1;
}
}
/*
* Process the 'max' field - if one was not present (n1 format)
* set max equal to min. If the field was present, but
* zero length (n1: format), retain the default. Otherwise
* pass the string to the parse function.
*/
if (n2str == NULL) {
rp->max = rp->min;
} else if ((int)strlen(n2str) > 0) {
if ((*parse_func)(n2str, &rp->max) < 0) {
sprintf(errmsg, "error parsing string %s into an integer", n2str);
free(tmpstr);
free(ranges);
return -1;
}
}
/*
* Process the 'mult' field - if one was not present
* (n1:n2 format), or the field was zero length (n1:n2: format)
* then set the mult field to defmult - otherwise pass then
* mult field to the parse function.
*/
if (multstr != NULL && (int)strlen(multstr) > 0) {
if ((*parse_func)(multstr, &rp->mult) < 0) {
sprintf(errmsg, "error parsing string %s into an integer", multstr);
free(tmpstr);
free(ranges);
return -1;
}
}
rp++;
tok = strtok(NULL, ",");
}
free(tmpstr);
if (rangeptr != NULL) {
*rangeptr = (char *)ranges;
} else {
free(ranges); /* just running in parse mode */
}
return (rp - ranges);
}
/*
* The default integer-parsing function
*/
static int
str_to_int(str, ip)
char *str;
int *ip;
{
char c;
if (sscanf(str, "%i%c", ip, &c) != 1) {
return -1;
} else {
return 0;
}
}
/*
* Three simple functions to return the min, max, and mult values for a given
* range. It is assumed that rbuf is a range buffer set up by parse_ranges(),
* and that r is a valid range within that buffer.
*/
int
range_min(rbuf, r)
char *rbuf;
int r;
{
return ((struct range *)rbuf)[r].min;
}
int
range_max(rbuf, r)
char *rbuf;
int r;
{
return ((struct range *)rbuf)[r].max;
}
int
range_mult(rbuf, r)
char *rbuf;
int r;
{
return ((struct range *)rbuf)[r].mult;
}
/*****************************************************************************
* random_range(int start, int end, int mult, char **errp)
*
* Returns a psuedo-random number which is >= 'start', <= 'end', and a multiple
* of 'mult'. Start and end may be any valid integer, but mult must be an
* integer > 0. errp is a char ** which will be set to point to a static
* error message buffer if it is not NULL, and an error occurs.
*
* The errp is the only way to check if the routine fails - currently the only
* failure conditions are:
*
* mult < 1
* no numbers in the start-end range that are a multiple of 'mult'
*
* If random_range_fails, and errp is a valid pointer, it will point to an
* internal error buffer. If errp is a vaild pointer, and random_range
* is successful, errp will be set to NULL.
*
* Note - if mult is 1 (the most common case), there are error conditions
* possible, and errp need not be used.
*
* Note: Uses lrand48(), assuming that set_random_seed() uses srand48() when
* setting the seed.
*****************************************************************************/
long
random_range(min, max, mult, errp)
int min;
int max;
int mult;
char **errp;
{
int r, nmults, orig_min, orig_max, orig_mult, tmp;
extern long lrand48();
static char errbuf[128];
/*
* Sanity check
*/
if (mult < 1) {
if (errp != NULL) {
sprintf(errbuf, "mult arg must be greater than 0");
*errp = errbuf;
}
return -1;
}
/*
* Save original parameter values for use in error message
*/
orig_min = min;
orig_max = max;
orig_mult = mult;
/*
* switch min/max if max < min
*/
if (max < min) {
tmp = max;
max = min;
min = tmp;
}
/*
* select the random number
*/
if ((r = min % mult)) /* bump to the next higher 'mult' multiple */
min += mult - r;
if ((r = max % mult)) /* reduce to the next lower 'mult' multiple */
max -= r;
if (min > max) { /* no 'mult' multiples between min & max */
if (errp != NULL) {
sprintf(errbuf, "no numbers in the range %d:%d that are a multiple of %d", orig_min, orig_max, orig_mult);
*errp = errbuf;
}
return -1;
}
if (errp != NULL) {
*errp = NULL;
}
nmults = ((max - min) / mult) + 1;
#if CRAY
/*
* If max is less than 2gb, then the value can fit in 32 bits
* and the standard lrand48() routine can be used.
*/
if ( max <= (long)2147483647 ) {
return (long) (min + (((long)lrand48() % nmults) * mult));
} else {
/*
* max is greater than 2gb - meeds more than 32 bits.
* Since lrand48 only will get a number up to 32bits.
*/
long randnum;
randnum=divider(min, max, 0, -1);
return (long) (min + ((randnum % nmults) * mult));
}
#else
return (min + ((lrand48() % nmults) * mult));
#endif
}
/*
* Just like random_range, but all values are longs.
*/
long
random_rangel(min, max, mult, errp)
long min;
long max;
long mult;
char **errp;
{
long r, nmults, orig_min, orig_max, orig_mult, tmp;
extern long lrand48();
static char errbuf[128];
/*
* Sanity check
*/
if (mult < 1) {
if (errp != NULL) {
sprintf(errbuf, "mult arg must be greater than 0");
*errp = errbuf;
}
return -1;
}
/*
* Save original parameter values for use in error message
*/
orig_min = min;
orig_max = max;
orig_mult = mult;
/*
* switch min/max if max < min
*/
if (max < min) {
tmp = max;
max = min;
min = tmp;
}
/*
* select the random number
*/
if ((r = min % mult)) /* bump to the next higher 'mult' multiple */
min += mult - r;
if ((r = max % mult)) /* reduce to the next lower 'mult' multiple */
max -= r;
if (min > max) { /* no 'mult' multiples between min & max */
if (errp != NULL) {
sprintf(errbuf,
"no numbers in the range %ld:%ld that are a multiple of %ld",
orig_min, orig_max, orig_mult);
*errp = errbuf;
}
return -1;
}
if (errp != NULL) {
*errp = NULL;
}
nmults = ((max - min) / mult) + 1;
#if CRAY || (_MIPS_SZLONG == 64)
/*
* If max is less than 2gb, then the value can fit in 32 bits
* and the standard lrand48() routine can be used.
*/
if ( max <= (long)2147483647 ) {
return (long) (min + (((long)lrand48() % nmults) * mult));
} else {
/*
* max is greater than 2gb - meeds more than 32 bits.
* Since lrand48 only will get a number up to 32bits.
*/
long randnum;
randnum=divider(min, max, 0, -1);
return (long) (min + ((randnum % nmults) * mult));
}
#else
return (min + ((lrand48() % nmults) * mult));
#endif
}
/*
* Attempts to be just like random_range, but everything is long long (64 bit)
*/
long long
random_rangell(min, max, mult, errp)
long long min;
long long max;
long long mult;
char **errp;
{
long long r, nmults, orig_min, orig_max, orig_mult, tmp;
long long randnum;
extern long lrand48();
static char errbuf[128];
/*
* Sanity check
*/
if (mult < 1) {
if (errp != NULL) {
sprintf(errbuf, "mult arg must be greater than 0");
*errp = errbuf;
}
return -1;
}
/*
* Save original parameter values for use in error message
*/
orig_min = min;
orig_max = max;
orig_mult = mult;
/*
* switch min/max if max < min
*/
if (max < min) {
tmp = max;
max = min;
min = tmp;
}
/*
* select the random number
*/
if ((r = min % mult)) /* bump to the next higher 'mult' multiple */
min += mult - r;
if ((r = max % mult)) /* reduce to the next lower 'mult' multiple */
max -= r;
if (min > max) { /* no 'mult' multiples between min & max */
if (errp != NULL) {
sprintf(errbuf,
"no numbers in the range %lld:%lld that are a multiple of %lld",
orig_min, orig_max, orig_mult);
*errp = errbuf;
}
return -1;
}
if (errp != NULL) {
*errp = NULL;
}
nmults = ((max - min) / mult) + 1;
/*
* If max is less than 2gb, then the value can fit in 32 bits
* and the standard lrand48() routine can be used.
*/
if ( max <= (long)2147483647 ) {
return (long long) (min + (((long long)lrand48() % nmults) * mult));
} else {
/*
* max is greater than 2gb - meeds more than 32 bits.
* Since lrand48 only will get a number up to 32bits.
*/
randnum=divider(min, max, 0, -1);
return (long long) (min + ((randnum % nmults) * mult));
}
}
/*
* This functional will recusively call itself to return a random
* number min and max. It was designed to work the 64bit numbers
* even when compiled as 32 bit process.
* algorithm: to use the official lrand48() routine - limited to 32 bits.
* find the difference between min and max (max-min).
* if the difference is 2g or less, use the random number gotton from lrand48().
* Determine the midway point between min and max.
* if the midway point is less than 2g from min or max,
* randomly add the random number gotton from lrand48() to
* either min or the midpoint.
* Otherwise, call outself with min and max being min and midway value or
* midway value and max. This will reduce the range in half.
*/
static long long
divider(long long min, long long max, long long cnt, long long rand)
{
long long med, half, diff;
/*
* prevent run away code. We are dividing by two each count.
* if we get to a count of more than 32, we should have gotten
* to 2gb.
*/
if ( cnt > 32 )
return -1;
/*
* Only get a random number the first time.
*/
if ( cnt == 0 || rand < -1 ) {
rand = (long long)lrand48(); /* 32 bit random number */
}
diff = max - min;
if ( diff <= 2147483647 )
return min + rand;
half = diff/(long long)2; /* half the distance between min and max */
med = min + half; /* med way point between min and max */
#if DEBUG
printf("divider: min=%lld, max=%lld, cnt=%lld, rand=%lld\n", min, max, cnt, rand);
printf(" diff = %lld, half = %lld, med = %lld\n", diff, half, med);
#endif
if ( half <= 2147483647 ) {
/*
* If half is smaller than 2gb, we can use the random number
* to pick the number within the min to med or med to max
* if the cnt bit of rand is zero or one, respectively.
*/
if ( rand & (1<<cnt) )
return med + rand;
else
return min + rand;
} else {
/*
* recursively call ourself to reduce the value to the bottom half
* or top half (bit cnt is set).
*/
if ( rand & (1<<cnt) ) {
return divider(med, max, cnt+1, rand);
} else {
return divider(min, med, cnt+1, rand);
}
}
}
/*****************************************************************************
* random_range_seed(s)
*
* Sets the random seed to s. Uses srand48(), assuming that lrand48() will
* be used in random_range().
*****************************************************************************/
void
random_range_seed(s)
long s;
{
extern void srand48();
srand48(s);
}
/****************************************************************************
* random_bit(mask)
*
* This function randomly returns a single bit from the bits
* set in mask. If mask is zero, zero is returned.
*
****************************************************************************/
long
random_bit(long mask)
{
int nbits = 0; /* number of set bits in mask */
long bit; /* used to count bits and num of set bits choosen */
int nshift; /* used to count bit shifts */
if ( mask == 0 )
return 0;
/*
* get the number of bits set in mask
*/
#ifndef CRAY
bit=1L;
for ( nshift=0; (unsigned int)nshift<sizeof(long)*8; nshift++) {
if ( mask & bit )
nbits++;
bit=bit<<1;
}
#else
nbits=_popcnt(mask);
#endif /* if CRAY */
/*
* randomly choose a bit.
*/
bit=random_range(1, nbits, 1, NULL);
/*
* shift bits until you determine which bit was randomly choosen.
* nshift will hold the number of shifts to make.
*/
nshift=0;
while (bit) {
/* check if the current one's bit is set */
if ( mask & 1L ) {
bit--;
}
mask = mask >> 1;
nshift++;
}
return 01L << (nshift-1);
}
#if RANDOM_BIT_UNITTEST
/*
* The following is a unit test main function for random_bit().
*/
main(argc, argv)
int argc;
char **argv;
{
int ind;
int cnt, iter;
long mask, ret;
printf("test for first and last bit set\n");
mask=1L;
ret=random_bit(mask);
printf("random_bit(%#o) returned %#o\n", mask, ret);
mask=1L<<(sizeof(long)*8-1);
ret=random_bit(mask);
printf("random_bit(%#o) returned %#o\n", mask, ret);
if ( argc >= 3 ) {
iter=atoi(argv[1]);
for (ind=2; ind<argc; ind++) {
printf("Calling random_bit %d times for mask %#o\n", iter, mask);
sscanf(argv[ind], "%i", &mask);
for (cnt=0; cnt<iter; cnt++) {
ret=random_bit(mask);
printf("random_bit(%#o) returned %#o\n", mask, ret);
}
}
}
exit(0);
}
#endif /* end if RANDOM_BIT_UNITTEST */
#if UNIT_TEST
/*
* The following is a unit test main function for random_range*().
*/
#define PARTNUM 10 /* used to determine even distribution of random numbers */
#define MEG 1024*1024*1024
#define GIG 1073741824
int
main(argc, argv)
int argc;
char **argv;
{
int ind;
int cnt, iter=10;
int imin=0, imult=1, itmin, itmax=0;
#if CRAY
int imax=6*GIG; /* higher than 32 bits */
#else
int imax=1048576;
#endif
long lret, lmin=0, lmult=1, ltmin, ltmax=0;
#if CRAY || (_MIPS_SZLONG == 64)
long lmax=6*(long)GIG; /* higher than 32 bits */
#else
long lmax=1048576;
#endif
long long llret, llmin=0, llmult=1, lltmin, lltmax=0;
long long llmax=(long long)80*(long long)GIG;
long part;
long long lpart;
long cntarr[PARTNUM];
long valbound[PARTNUM];
long long lvalbound[PARTNUM];
for (ind=0; ind<PARTNUM; ind++ )
cntarr[ind]=0;
if ( argc < 2 ) {
printf("Usage: %s func [iterations] \n", argv[0]);
printf("func can be random_range, random_rangel, random_rangell\n");
exit(1);
}
if ( argc >= 3 ) {
if ( sscanf(argv[2], "%i", &iter) != 1 ) {
printf("Usage: %s [func iterations] \n", argv[0]);
printf("argv[2] is not a number\n");
exit(1);
}
}
/*
* random_rangel ()
*/
if ( strcmp(argv[1], "random_rangel") == 0 ) {
ltmin=lmax;
part = lmax/PARTNUM;
for(ind=0; ind<PARTNUM; ind++) {
valbound[ind]=part*ind;
}
for(cnt=0; cnt<iter; cnt++) {
lret=random_rangel(lmin, lmax, lmult, NULL);
if ( iter < 100 )
printf("%ld\n", lret);
if ( lret < ltmin )
ltmin = lret;
if ( lret > ltmax )
ltmax = lret;
for(ind=0; ind<PARTNUM-1; ind++) {
if ( valbound[ind] < lret && lret <= valbound[ind+1] ) {
cntarr[ind]++;
break;
}
}
if ( lret > valbound[PARTNUM-1] ) {
cntarr[PARTNUM-1]++;
}
}
for(ind=0; ind<PARTNUM-1; ind++) {
printf("%2d %-13ld to %-13ld %5ld %4.4f\n", ind+1,
valbound[ind], valbound[ind+1], cntarr[ind],
(float)(cntarr[ind]/(float)iter));
}
printf("%2d %-13ld to %-13ld %5ld %4.4f\n", PARTNUM,
valbound[PARTNUM-1], lmax, cntarr[PARTNUM-1],
(float)(cntarr[PARTNUM-1]/(float)iter));
printf(" min=%ld, max=%ld\n", ltmin, ltmax);
} else if ( strcmp(argv[1], "random_rangell") == 0 ) {
/*
* random_rangell() unit test
*/
lltmin=llmax;
lpart = llmax/PARTNUM;
for(ind=0; ind<PARTNUM; ind++) {
lvalbound[ind]=(long long)(lpart*ind);
}
for(cnt=0; cnt<iter; cnt++) {
llret=random_rangell(llmin, llmax, llmult, NULL);
if ( iter < 100 )
printf("random_rangell returned %lld\n", llret);
if ( llret < lltmin )
lltmin = llret;
if ( llret > lltmax )
lltmax = llret;
for(ind=0; ind<PARTNUM-1; ind++) {
if ( lvalbound[ind] < llret && llret <= lvalbound[ind+1] ) {
cntarr[ind]++;
break;
}
}
if ( llret > lvalbound[PARTNUM-1] ) {
cntarr[PARTNUM-1]++;
}
}
for(ind=0; ind<PARTNUM-1; ind++) {
printf("%2d %-13lld to %-13lld %5ld %4.4f\n", ind+1,
lvalbound[ind], lvalbound[ind+1], cntarr[ind],
(float)(cntarr[ind]/(float)iter));
}
printf("%2d %-13lld to %-13lld %5ld %4.4f\n", PARTNUM,
lvalbound[PARTNUM-1], llmax, cntarr[PARTNUM-1],
(float)(cntarr[PARTNUM-1]/(float)iter));
printf(" min=%lld, max=%lld\n", lltmin, lltmax);
} else {
/*
* random_range() unit test
*/
itmin=imax;
part = imax/PARTNUM;
for(ind=0; ind<PARTNUM; ind++) {
valbound[ind]=part*ind;
}
for(cnt=0; cnt<iter; cnt++) {
lret=random_range(imin, imax, imult, NULL);
if ( iter < 100 )
printf("%ld\n", lret);
if ( lret < itmin )
itmin = lret;
if ( lret > itmax )
itmax = lret;
for(ind=0; ind<PARTNUM-1; ind++) {
if ( valbound[ind] < lret && lret <= valbound[ind+1] ) {
cntarr[ind]++;
break;
}
}
if ( lret > valbound[PARTNUM-1] ) {
cntarr[PARTNUM-1]++;
}
}
for(ind=0; ind<PARTNUM-1; ind++) {
printf("%2d %-13ld to %-13ld %5ld %4.4f\n", ind+1,
valbound[ind], valbound[ind+1], cntarr[ind],
(float)(cntarr[ind]/(float)iter));
}
printf("%2d %-13ld to %-13ld %5ld %4.4f\n", PARTNUM,
valbound[PARTNUM-1], (long)imax, cntarr[PARTNUM-1],
(float)(cntarr[PARTNUM-1]/(float)iter));
printf(" min=%d, max=%d\n", itmin, itmax);
}
exit(0);
}
#endif