2 * Copyright (c) 2000 Silicon Graphics, Inc. All Rights Reserved.
4 * This program is free software; you can redistribute it and/or modify it
5 * under the terms of version 2 of the GNU General Public License as
6 * published by the Free Software Foundation.
8 * This program is distributed in the hope that it would be useful, but
9 * WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
12 * Further, this software is distributed without any warranty that it is
13 * free of the rightful claim of any third person regarding infringement
14 * or the like. Any license provided herein, whether implied or
15 * otherwise, applies only to this software file. Patent licenses, if
16 * any, provided herein do not apply to combinations of this program with
17 * other software, or any other product whatsoever.
19 * You should have received a copy of the GNU General Public License along
20 * with this program; if not, write the Free Software Foundation, Inc., 59
21 * Temple Place - Suite 330, Boston MA 02111-1307, USA.
23 * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
24 * Mountain View, CA 94043, or:
28 * For further information regarding this notice, see:
30 * http://oss.sgi.com/projects/GenInfo/NoticeExplan/
36 #include "random_range.h"
39 * Internal format of the range array set up by parse_range()
49 * parse_ranges() is a function to parse a comma-separated list of range
50 * tokens each having the following form:
56 * any of the values may be blank (ie. min::mult, :max, etc.) and default
57 * values for missing arguments may be supplied by the caller.
59 * The special first form is short hand for 'num:num'.
61 * After parsing the string, the ranges are put into an array of integers,
62 * which is malloc'd by the routine. The min, max, and mult entries of each
63 * range can be extracted from the array using the range_min(), range_max(),
64 * and range_mult() functions.
66 * It is the responsibility of the caller to free the space allocated by
67 * parse_ranges() - a single call to free() will free the space.
69 * str The string to parse - assumed to be a comma-separated
70 * list of tokens having the above format.
71 * defmin default value to plug in for min, if it is missing
72 * defmax default value to plug in for max, if it is missing
73 * defmult default value to plug in for mult, if missing
74 * parse_func A user-supplied function pointer, which parse_ranges()
75 * can call to parse the min, max, and mult strings. This
76 * allows for customized number formats. The function
77 * MUST have the following prototype:
78 * parse_func(char *str, int *val)
79 * The function should return -1 if str cannot be parsed
80 * into an integer, or >= 0 if it was successfully
81 * parsed. The resulting integer will be stored in
82 * *val. If parse_func is NULL, parse_ranges will parse
83 * the tokens in a manner consistent with the the sscanf
85 * range_ptr A user-supplied char **, which will be set to point
86 * at malloc'd space which holds the parsed range
87 * values. If range_ptr is NULL, parse_ranges() just
88 * parses the string. The data returned in range_ptr
89 * should not be processed directly - use the functions
90 * range_min(), range_max(), and range_mult() to access
91 * data for a given range.
92 * errptr user-supplied char ** which can be set to point to a
93 * static error string. If errptr is NULL, it is ignored.
95 * parse_range() returns -1 on error, or the number of ranges parsed.
98 static int str_to_int();
99 static long long divider(long long, long long, long long, long long);
102 parse_ranges(str, defmin, defmax, defmult, parse_func, rangeptr, errptr)
112 char *tmpstr, *cp, *tok, *n1str, *n2str, *multstr;
113 struct range *rp, *ranges;
114 static char errmsg[256];
116 if (errptr != NULL) {
120 for (ncommas = 0, cp = str; *cp != '\0'; cp++) {
126 if (parse_func == NULL) {
127 parse_func = str_to_int;
130 tmpstr = strdup(str);
131 ranges = (struct range *)malloc((ncommas+1) * sizeof(struct range));
134 tok = strtok(tmpstr, ",");
135 while (tok != NULL) {
144 if ((cp = strchr(n1str, ':')) != NULL) {
148 if ((cp = strchr(n2str, ':')) != NULL) {
155 * Parse the 'min' field - if it is zero length (:n2[:mult]
156 * format), retain the default value, otherwise, pass the
157 * string to the parse function.
160 if ((int)strlen(n1str) > 0) {
161 if ((*parse_func)(n1str, &rp->min) < 0) {
162 sprintf(errmsg, "error parsing string %s into an integer", n1str);
170 * Process the 'max' field - if one was not present (n1 format)
171 * set max equal to min. If the field was present, but
172 * zero length (n1: format), retain the default. Otherwise
173 * pass the string to the parse function.
178 } else if ((int)strlen(n2str) > 0) {
179 if ((*parse_func)(n2str, &rp->max) < 0) {
180 sprintf(errmsg, "error parsing string %s into an integer", n2str);
188 * Process the 'mult' field - if one was not present
189 * (n1:n2 format), or the field was zero length (n1:n2: format)
190 * then set the mult field to defmult - otherwise pass then
191 * mult field to the parse function.
194 if (multstr != NULL && (int)strlen(multstr) > 0) {
195 if ((*parse_func)(multstr, &rp->mult) < 0) {
196 sprintf(errmsg, "error parsing string %s into an integer", multstr);
204 tok = strtok(NULL, ",");
209 if (rangeptr != NULL) {
210 *rangeptr = (char *)ranges;
212 free(ranges); /* just running in parse mode */
215 return (rp - ranges);
219 * The default integer-parsing function
229 if (sscanf(str, "%i%c", ip, &c) != 1) {
237 * Three simple functions to return the min, max, and mult values for a given
238 * range. It is assumed that rbuf is a range buffer set up by parse_ranges(),
239 * and that r is a valid range within that buffer.
247 return ((struct range *)rbuf)[r].min;
255 return ((struct range *)rbuf)[r].max;
263 return ((struct range *)rbuf)[r].mult;
266 /*****************************************************************************
267 * random_range(int start, int end, int mult, char **errp)
269 * Returns a psuedo-random number which is >= 'start', <= 'end', and a multiple
270 * of 'mult'. Start and end may be any valid integer, but mult must be an
271 * integer > 0. errp is a char ** which will be set to point to a static
272 * error message buffer if it is not NULL, and an error occurs.
274 * The errp is the only way to check if the routine fails - currently the only
275 * failure conditions are:
278 * no numbers in the start-end range that are a multiple of 'mult'
280 * If random_range_fails, and errp is a valid pointer, it will point to an
281 * internal error buffer. If errp is a vaild pointer, and random_range
282 * is successful, errp will be set to NULL.
284 * Note - if mult is 1 (the most common case), there are error conditions
285 * possible, and errp need not be used.
287 * Note: Uses lrand48(), assuming that set_random_seed() uses srand48() when
289 *****************************************************************************/
292 random_range(min, max, mult, errp)
298 int r, nmults, orig_min, orig_max, orig_mult, tmp;
299 extern long lrand48();
300 static char errbuf[128];
308 sprintf(errbuf, "mult arg must be greater than 0");
315 * Save original parameter values for use in error message
323 * switch min/max if max < min
333 * select the random number
336 if ((r = min % mult)) /* bump to the next higher 'mult' multiple */
339 if ((r = max % mult)) /* reduce to the next lower 'mult' multiple */
342 if (min > max) { /* no 'mult' multiples between min & max */
344 sprintf(errbuf, "no numbers in the range %d:%d that are a multiple of %d", orig_min, orig_max, orig_mult);
354 nmults = ((max - min) / mult) + 1;
357 * If max is less than 2gb, then the value can fit in 32 bits
358 * and the standard lrand48() routine can be used.
360 if ( max <= (long)2147483647 ) {
361 return (long) (min + (((long)lrand48() % nmults) * mult));
364 * max is greater than 2gb - meeds more than 32 bits.
365 * Since lrand48 only will get a number up to 32bits.
368 randnum=divider(min, max, 0, -1);
369 return (long) (min + ((randnum % nmults) * mult));
373 return (min + ((lrand48() % nmults) * mult));
379 * Just like random_range, but all values are longs.
382 random_rangel(min, max, mult, errp)
388 long r, nmults, orig_min, orig_max, orig_mult, tmp;
389 extern long lrand48();
390 static char errbuf[128];
398 sprintf(errbuf, "mult arg must be greater than 0");
405 * Save original parameter values for use in error message
413 * switch min/max if max < min
423 * select the random number
426 if ((r = min % mult)) /* bump to the next higher 'mult' multiple */
429 if ((r = max % mult)) /* reduce to the next lower 'mult' multiple */
432 if (min > max) { /* no 'mult' multiples between min & max */
435 "no numbers in the range %ld:%ld that are a multiple of %ld",
436 orig_min, orig_max, orig_mult);
446 nmults = ((max - min) / mult) + 1;
447 #if CRAY || (_MIPS_SZLONG == 64)
449 * If max is less than 2gb, then the value can fit in 32 bits
450 * and the standard lrand48() routine can be used.
452 if ( max <= (long)2147483647 ) {
453 return (long) (min + (((long)lrand48() % nmults) * mult));
456 * max is greater than 2gb - meeds more than 32 bits.
457 * Since lrand48 only will get a number up to 32bits.
460 randnum=divider(min, max, 0, -1);
461 return (long) (min + ((randnum % nmults) * mult));
465 return (min + ((lrand48() % nmults) * mult));
470 * Attempts to be just like random_range, but everything is long long (64 bit)
473 random_rangell(min, max, mult, errp)
479 long long r, nmults, orig_min, orig_max, orig_mult, tmp;
481 extern long lrand48();
482 static char errbuf[128];
490 sprintf(errbuf, "mult arg must be greater than 0");
497 * Save original parameter values for use in error message
505 * switch min/max if max < min
515 * select the random number
518 if ((r = min % mult)) /* bump to the next higher 'mult' multiple */
521 if ((r = max % mult)) /* reduce to the next lower 'mult' multiple */
524 if (min > max) { /* no 'mult' multiples between min & max */
527 "no numbers in the range %lld:%lld that are a multiple of %lld",
528 orig_min, orig_max, orig_mult);
538 nmults = ((max - min) / mult) + 1;
540 * If max is less than 2gb, then the value can fit in 32 bits
541 * and the standard lrand48() routine can be used.
543 if ( max <= (long)2147483647 ) {
544 return (long long) (min + (((long long)lrand48() % nmults) * mult));
547 * max is greater than 2gb - meeds more than 32 bits.
548 * Since lrand48 only will get a number up to 32bits.
550 randnum=divider(min, max, 0, -1);
551 return (long long) (min + ((randnum % nmults) * mult));
557 * This functional will recusively call itself to return a random
558 * number min and max. It was designed to work the 64bit numbers
559 * even when compiled as 32 bit process.
560 * algorithm: to use the official lrand48() routine - limited to 32 bits.
561 * find the difference between min and max (max-min).
562 * if the difference is 2g or less, use the random number gotton from lrand48().
563 * Determine the midway point between min and max.
564 * if the midway point is less than 2g from min or max,
565 * randomly add the random number gotton from lrand48() to
566 * either min or the midpoint.
567 * Otherwise, call outself with min and max being min and midway value or
568 * midway value and max. This will reduce the range in half.
571 divider(long long min, long long max, long long cnt, long long rand)
573 long long med, half, diff;
576 * prevent run away code. We are dividing by two each count.
577 * if we get to a count of more than 32, we should have gotten
584 * Only get a random number the first time.
586 if ( cnt == 0 || rand < -1 ) {
587 rand = (long long)lrand48(); /* 32 bit random number */
592 if ( diff <= 2147483647 )
595 half = diff/(long long)2; /* half the distance between min and max */
596 med = min + half; /* med way point between min and max */
599 printf("divider: min=%lld, max=%lld, cnt=%lld, rand=%lld\n", min, max, cnt, rand);
600 printf(" diff = %lld, half = %lld, med = %lld\n", diff, half, med);
603 if ( half <= 2147483647 ) {
605 * If half is smaller than 2gb, we can use the random number
606 * to pick the number within the min to med or med to max
607 * if the cnt bit of rand is zero or one, respectively.
609 if ( rand & (1<<cnt) )
615 * recursively call ourself to reduce the value to the bottom half
616 * or top half (bit cnt is set).
618 if ( rand & (1<<cnt) ) {
619 return divider(med, max, cnt+1, rand);
621 return divider(min, med, cnt+1, rand);
629 /*****************************************************************************
630 * random_range_seed(s)
632 * Sets the random seed to s. Uses srand48(), assuming that lrand48() will
633 * be used in random_range().
634 *****************************************************************************/
640 extern void srand48();
645 /****************************************************************************
648 * This function randomly returns a single bit from the bits
649 * set in mask. If mask is zero, zero is returned.
651 ****************************************************************************/
653 random_bit(long mask)
655 int nbits = 0; /* number of set bits in mask */
656 long bit; /* used to count bits and num of set bits choosen */
657 int nshift; /* used to count bit shifts */
663 * get the number of bits set in mask
668 for ( nshift=0; nshift<sizeof(long)*8; nshift++) {
679 * randomly choose a bit.
681 bit=random_range(1, nbits, 1, NULL);
684 * shift bits until you determine which bit was randomly choosen.
685 * nshift will hold the number of shifts to make.
690 /* check if the current one's bit is set */
698 return 01L << (nshift-1);
703 #if RANDOM_BIT_UNITTEST
705 * The following is a unit test main function for random_bit().
715 printf("test for first and last bit set\n");
717 ret=random_bit(mask);
718 printf("random_bit(%#o) returned %#o\n", mask, ret);
720 mask=1L<<(sizeof(long)*8-1);
721 ret=random_bit(mask);
722 printf("random_bit(%#o) returned %#o\n", mask, ret);
726 for (ind=2; ind<argc; ind++) {
727 printf("Calling random_bit %d times for mask %#o\n", iter, mask);
728 sscanf(argv[ind], "%i", &mask);
729 for (cnt=0; cnt<iter; cnt++) {
730 ret=random_bit(mask);
731 printf("random_bit(%#o) returned %#o\n", mask, ret);
738 #endif /* end if RANDOM_BIT_UNITTEST */
743 * The following is a unit test main function for random_range*().
746 #define PARTNUM 10 /* used to determine even distribution of random numbers */
747 #define MEG 1024*1024*1024
748 #define GIG 1073741824
756 int imin=0, imult=1, itmin, itmax=0;
758 int imax=6*GIG; /* higher than 32 bits */
763 long lret, lmin=0, lmult=1, ltmin, ltmax=0;
764 #if CRAY || (_MIPS_SZLONG == 64)
765 long lmax=6*(long)GIG; /* higher than 32 bits */
769 long long llret, llmin=0, llmult=1, lltmin, lltmax=0;
770 long long llmax=(long long)80*(long long)GIG;
774 long cntarr[PARTNUM];
775 long valbound[PARTNUM];
776 long long lvalbound[PARTNUM];
778 for (ind=0; ind<PARTNUM; ind++ )
782 printf("Usage: %s func [iterations] \n", argv[0]);
783 printf("func can be random_range, random_rangel, random_rangell\n");
788 if ( sscanf(argv[2], "%i", &iter) != 1 ) {
789 printf("Usage: %s [func iterations] \n", argv[0]);
790 printf("argv[2] is not a number\n");
799 if ( strcmp(argv[1], "random_rangel") == 0 ) {
802 for(ind=0; ind<PARTNUM; ind++) {
803 valbound[ind]=part*ind;
806 for(cnt=0; cnt<iter; cnt++) {
807 lret=random_rangel(lmin, lmax, lmult, NULL);
809 printf("%ld\n", lret);
814 for(ind=0; ind<PARTNUM-1; ind++) {
815 if ( valbound[ind] < lret && lret <= valbound[ind+1] ) {
820 if ( lret > valbound[PARTNUM-1] ) {
824 for(ind=0; ind<PARTNUM-1; ind++) {
825 printf("%2d %-13ld to %-13ld %5ld %4.4f\n", ind+1,
826 valbound[ind], valbound[ind+1], cntarr[ind],
827 (float)(cntarr[ind]/(float)iter));
829 printf("%2d %-13ld to %-13ld %5ld %4.4f\n", PARTNUM,
830 valbound[PARTNUM-1], lmax, cntarr[PARTNUM-1],
831 (float)(cntarr[PARTNUM-1]/(float)iter));
832 printf(" min=%ld, max=%ld\n", ltmin, ltmax);
834 } else if ( strcmp(argv[1], "random_rangell") == 0 ) {
836 * random_rangell() unit test
839 lpart = llmax/PARTNUM;
840 for(ind=0; ind<PARTNUM; ind++) {
841 lvalbound[ind]=(long long)(lpart*ind);
844 for(cnt=0; cnt<iter; cnt++) {
845 llret=random_rangell(llmin, llmax, llmult, NULL);
847 printf("random_rangell returned %lld\n", llret);
848 if ( llret < lltmin )
850 if ( llret > lltmax )
853 for(ind=0; ind<PARTNUM-1; ind++) {
854 if ( lvalbound[ind] < llret && llret <= lvalbound[ind+1] ) {
859 if ( llret > lvalbound[PARTNUM-1] ) {
863 for(ind=0; ind<PARTNUM-1; ind++) {
864 printf("%2d %-13lld to %-13lld %5ld %4.4f\n", ind+1,
865 lvalbound[ind], lvalbound[ind+1], cntarr[ind],
866 (float)(cntarr[ind]/(float)iter));
868 printf("%2d %-13lld to %-13lld %5ld %4.4f\n", PARTNUM,
869 lvalbound[PARTNUM-1], llmax, cntarr[PARTNUM-1],
870 (float)(cntarr[PARTNUM-1]/(float)iter));
871 printf(" min=%lld, max=%lld\n", lltmin, lltmax);
875 * random_range() unit test
879 for(ind=0; ind<PARTNUM; ind++) {
880 valbound[ind]=part*ind;
883 for(cnt=0; cnt<iter; cnt++) {
884 lret=random_range(imin, imax, imult, NULL);
886 printf("%ld\n", lret);
892 for(ind=0; ind<PARTNUM-1; ind++) {
893 if ( valbound[ind] < lret && lret <= valbound[ind+1] ) {
898 if ( lret > valbound[PARTNUM-1] ) {
902 for(ind=0; ind<PARTNUM-1; ind++) {
903 printf("%2d %-13ld to %-13ld %5ld %4.4f\n", ind+1,
904 valbound[ind], valbound[ind+1], cntarr[ind],
905 (float)(cntarr[ind]/(float)iter));
907 printf("%2d %-13ld to %-13ld %5ld %4.4f\n", PARTNUM,
908 valbound[PARTNUM-1], (long)imax, cntarr[PARTNUM-1],
909 (float)(cntarr[PARTNUM-1]/(float)iter));
910 printf(" min=%d, max=%d\n", itmin, itmax);