2 * Copyright (c) 2000 Silicon Graphics, Inc.
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License as
7 * published by the Free Software Foundation.
9 * This program is distributed in the hope that it would be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write the Free Software Foundation,
16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
22 #include "random_range.h"
25 * Internal format of the range array set up by parse_range()
35 * parse_ranges() is a function to parse a comma-separated list of range
36 * tokens each having the following form:
42 * any of the values may be blank (ie. min::mult, :max, etc.) and default
43 * values for missing arguments may be supplied by the caller.
45 * The special first form is short hand for 'num:num'.
47 * After parsing the string, the ranges are put into an array of integers,
48 * which is malloc'd by the routine. The min, max, and mult entries of each
49 * range can be extracted from the array using the range_min(), range_max(),
50 * and range_mult() functions.
52 * It is the responsibility of the caller to free the space allocated by
53 * parse_ranges() - a single call to free() will free the space.
55 * str The string to parse - assumed to be a comma-separated
56 * list of tokens having the above format.
57 * defmin default value to plug in for min, if it is missing
58 * defmax default value to plug in for max, if it is missing
59 * defmult default value to plug in for mult, if missing
60 * parse_func A user-supplied function pointer, which parse_ranges()
61 * can call to parse the min, max, and mult strings. This
62 * allows for customized number formats. The function
63 * MUST have the following prototype:
64 * parse_func(char *str, int *val)
65 * The function should return -1 if str cannot be parsed
66 * into an integer, or >= 0 if it was successfully
67 * parsed. The resulting integer will be stored in
68 * *val. If parse_func is NULL, parse_ranges will parse
69 * the tokens in a manner consistent with the the sscanf
71 * range_ptr A user-supplied char **, which will be set to point
72 * at malloc'd space which holds the parsed range
73 * values. If range_ptr is NULL, parse_ranges() just
74 * parses the string. The data returned in range_ptr
75 * should not be processed directly - use the functions
76 * range_min(), range_max(), and range_mult() to access
77 * data for a given range.
78 * errptr user-supplied char ** which can be set to point to a
79 * static error string. If errptr is NULL, it is ignored.
81 * parse_range() returns -1 on error, or the number of ranges parsed.
84 static int str_to_int();
85 static long long divider(long long, long long, long long, long long);
88 parse_ranges(str, defmin, defmax, defmult, parse_func, rangeptr, errptr)
98 char *tmpstr, *cp, *tok, *n1str, *n2str, *multstr;
99 struct range *rp, *ranges;
100 static char errmsg[256];
102 if (errptr != NULL) {
106 for (ncommas = 0, cp = str; *cp != '\0'; cp++) {
112 if (parse_func == NULL) {
113 parse_func = str_to_int;
116 tmpstr = strdup(str);
117 ranges = (struct range *)malloc((ncommas+1) * sizeof(struct range));
120 tok = strtok(tmpstr, ",");
121 while (tok != NULL) {
130 if ((cp = strchr(n1str, ':')) != NULL) {
134 if ((cp = strchr(n2str, ':')) != NULL) {
141 * Parse the 'min' field - if it is zero length (:n2[:mult]
142 * format), retain the default value, otherwise, pass the
143 * string to the parse function.
146 if ((int)strlen(n1str) > 0) {
147 if ((*parse_func)(n1str, &rp->min) < 0) {
148 sprintf(errmsg, "error parsing string %s into an integer", n1str);
156 * Process the 'max' field - if one was not present (n1 format)
157 * set max equal to min. If the field was present, but
158 * zero length (n1: format), retain the default. Otherwise
159 * pass the string to the parse function.
164 } else if ((int)strlen(n2str) > 0) {
165 if ((*parse_func)(n2str, &rp->max) < 0) {
166 sprintf(errmsg, "error parsing string %s into an integer", n2str);
174 * Process the 'mult' field - if one was not present
175 * (n1:n2 format), or the field was zero length (n1:n2: format)
176 * then set the mult field to defmult - otherwise pass then
177 * mult field to the parse function.
180 if (multstr != NULL && (int)strlen(multstr) > 0) {
181 if ((*parse_func)(multstr, &rp->mult) < 0) {
182 sprintf(errmsg, "error parsing string %s into an integer", multstr);
190 tok = strtok(NULL, ",");
195 if (rangeptr != NULL) {
196 *rangeptr = (char *)ranges;
198 free(ranges); /* just running in parse mode */
201 return (rp - ranges);
205 * The default integer-parsing function
215 if (sscanf(str, "%i%c", ip, &c) != 1) {
223 * Three simple functions to return the min, max, and mult values for a given
224 * range. It is assumed that rbuf is a range buffer set up by parse_ranges(),
225 * and that r is a valid range within that buffer.
233 return ((struct range *)rbuf)[r].min;
241 return ((struct range *)rbuf)[r].max;
249 return ((struct range *)rbuf)[r].mult;
252 /*****************************************************************************
253 * random_range(int start, int end, int mult, char **errp)
255 * Returns a psuedo-random number which is >= 'start', <= 'end', and a multiple
256 * of 'mult'. Start and end may be any valid integer, but mult must be an
257 * integer > 0. errp is a char ** which will be set to point to a static
258 * error message buffer if it is not NULL, and an error occurs.
260 * The errp is the only way to check if the routine fails - currently the only
261 * failure conditions are:
264 * no numbers in the start-end range that are a multiple of 'mult'
266 * If random_range_fails, and errp is a valid pointer, it will point to an
267 * internal error buffer. If errp is a vaild pointer, and random_range
268 * is successful, errp will be set to NULL.
270 * Note - if mult is 1 (the most common case), there are error conditions
271 * possible, and errp need not be used.
273 * Note: Uses lrand48(), assuming that set_random_seed() uses srand48() when
275 *****************************************************************************/
278 random_range(min, max, mult, errp)
284 int r, nmults, orig_min, orig_max, orig_mult, tmp;
285 extern long lrand48();
286 static char errbuf[128];
294 sprintf(errbuf, "mult arg must be greater than 0");
301 * Save original parameter values for use in error message
309 * switch min/max if max < min
319 * select the random number
322 if ((r = min % mult)) /* bump to the next higher 'mult' multiple */
325 if ((r = max % mult)) /* reduce to the next lower 'mult' multiple */
328 if (min > max) { /* no 'mult' multiples between min & max */
330 sprintf(errbuf, "no numbers in the range %d:%d that are a multiple of %d", orig_min, orig_max, orig_mult);
340 nmults = ((max - min) / mult) + 1;
341 return (min + ((lrand48() % nmults) * mult));
345 * Just like random_range, but all values are longs.
348 random_rangel(min, max, mult, errp)
354 long r, nmults, orig_min, orig_max, orig_mult, tmp;
355 extern long lrand48();
356 static char errbuf[128];
364 sprintf(errbuf, "mult arg must be greater than 0");
371 * Save original parameter values for use in error message
379 * switch min/max if max < min
389 * select the random number
392 if ((r = min % mult)) /* bump to the next higher 'mult' multiple */
395 if ((r = max % mult)) /* reduce to the next lower 'mult' multiple */
398 if (min > max) { /* no 'mult' multiples between min & max */
401 "no numbers in the range %ld:%ld that are a multiple of %ld",
402 orig_min, orig_max, orig_mult);
412 nmults = ((max - min) / mult) + 1;
413 #if (_MIPS_SZLONG == 64)
415 * If max is less than 2gb, then the value can fit in 32 bits
416 * and the standard lrand48() routine can be used.
418 if ( max <= (long)2147483647 ) {
419 return (long) (min + (((long)lrand48() % nmults) * mult));
422 * max is greater than 2gb - meeds more than 32 bits.
423 * Since lrand48 only will get a number up to 32bits.
426 randnum=divider(min, max, 0, -1);
427 return (long) (min + ((randnum % nmults) * mult));
431 return (min + ((lrand48() % nmults) * mult));
436 * Attempts to be just like random_range, but everything is long long (64 bit)
439 random_rangell(min, max, mult, errp)
445 long long r, nmults, orig_min, orig_max, orig_mult, tmp;
447 extern long lrand48();
448 static char errbuf[128];
456 sprintf(errbuf, "mult arg must be greater than 0");
463 * Save original parameter values for use in error message
471 * switch min/max if max < min
481 * select the random number
484 if ((r = min % mult)) /* bump to the next higher 'mult' multiple */
487 if ((r = max % mult)) /* reduce to the next lower 'mult' multiple */
490 if (min > max) { /* no 'mult' multiples between min & max */
493 "no numbers in the range %lld:%lld that are a multiple of %lld",
494 orig_min, orig_max, orig_mult);
504 nmults = ((max - min) / mult) + 1;
506 * If max is less than 2gb, then the value can fit in 32 bits
507 * and the standard lrand48() routine can be used.
509 if ( max <= (long)2147483647 ) {
510 return (long long) (min + (((long long)lrand48() % nmults) * mult));
513 * max is greater than 2gb - meeds more than 32 bits.
514 * Since lrand48 only will get a number up to 32bits.
516 randnum=divider(min, max, 0, -1);
517 return (long long) (min + ((randnum % nmults) * mult));
523 * This functional will recusively call itself to return a random
524 * number min and max. It was designed to work the 64bit numbers
525 * even when compiled as 32 bit process.
526 * algorithm: to use the official lrand48() routine - limited to 32 bits.
527 * find the difference between min and max (max-min).
528 * if the difference is 2g or less, use the random number gotton from lrand48().
529 * Determine the midway point between min and max.
530 * if the midway point is less than 2g from min or max,
531 * randomly add the random number gotton from lrand48() to
532 * either min or the midpoint.
533 * Otherwise, call outself with min and max being min and midway value or
534 * midway value and max. This will reduce the range in half.
537 divider(long long min, long long max, long long cnt, long long rand)
539 long long med, half, diff;
542 * prevent run away code. We are dividing by two each count.
543 * if we get to a count of more than 32, we should have gotten
550 * Only get a random number the first time.
552 if ( cnt == 0 || rand < -1 ) {
553 rand = (long long)lrand48(); /* 32 bit random number */
558 if ( diff <= 2147483647 )
561 half = diff/(long long)2; /* half the distance between min and max */
562 med = min + half; /* med way point between min and max */
565 printf("divider: min=%lld, max=%lld, cnt=%lld, rand=%lld\n", min, max, cnt, rand);
566 printf(" diff = %lld, half = %lld, med = %lld\n", diff, half, med);
569 if ( half <= 2147483647 ) {
571 * If half is smaller than 2gb, we can use the random number
572 * to pick the number within the min to med or med to max
573 * if the cnt bit of rand is zero or one, respectively.
575 if ( rand & (1<<cnt) )
581 * recursively call ourself to reduce the value to the bottom half
582 * or top half (bit cnt is set).
584 if ( rand & (1<<cnt) ) {
585 return divider(med, max, cnt+1, rand);
587 return divider(min, med, cnt+1, rand);
595 /*****************************************************************************
596 * random_range_seed(s)
598 * Sets the random seed to s. Uses srand48(), assuming that lrand48() will
599 * be used in random_range().
600 *****************************************************************************/
606 extern void srand48();
611 /****************************************************************************
614 * This function randomly returns a single bit from the bits
615 * set in mask. If mask is zero, zero is returned.
617 ****************************************************************************/
619 random_bit(long mask)
621 int nbits = 0; /* number of set bits in mask */
622 long bit; /* used to count bits and num of set bits choosen */
623 int nshift; /* used to count bit shifts */
629 * get the number of bits set in mask
632 for ( nshift=0; nshift<sizeof(long)*8; nshift++) {
639 * randomly choose a bit.
641 bit=random_range(1, nbits, 1, NULL);
644 * shift bits until you determine which bit was randomly choosen.
645 * nshift will hold the number of shifts to make.
650 /* check if the current one's bit is set */
658 return 01L << (nshift-1);
663 #if RANDOM_BIT_UNITTEST
665 * The following is a unit test main function for random_bit().
675 printf("test for first and last bit set\n");
677 ret=random_bit(mask);
678 printf("random_bit(%#o) returned %#o\n", mask, ret);
680 mask=1L<<(sizeof(long)*8-1);
681 ret=random_bit(mask);
682 printf("random_bit(%#o) returned %#o\n", mask, ret);
686 for (ind=2; ind<argc; ind++) {
687 printf("Calling random_bit %d times for mask %#o\n", iter, mask);
688 sscanf(argv[ind], "%i", &mask);
689 for (cnt=0; cnt<iter; cnt++) {
690 ret=random_bit(mask);
691 printf("random_bit(%#o) returned %#o\n", mask, ret);
698 #endif /* end if RANDOM_BIT_UNITTEST */
703 * The following is a unit test main function for random_range*().
706 #define PARTNUM 10 /* used to determine even distribution of random numbers */
707 #define MEG 1024*1024*1024
708 #define GIG 1073741824
716 int imin=0, imult=1, itmin, itmax=0;
719 long lret, lmin=0, lmult=1, ltmin, ltmax=0;
720 #if (_MIPS_SZLONG == 64)
721 long lmax=6*(long)GIG; /* higher than 32 bits */
725 long long llret, llmin=0, llmult=1, lltmin, lltmax=0;
726 long long llmax=(long long)80*(long long)GIG;
730 long cntarr[PARTNUM];
731 long valbound[PARTNUM];
732 long long lvalbound[PARTNUM];
734 for (ind=0; ind<PARTNUM; ind++ )
738 printf("Usage: %s func [iterations] \n", argv[0]);
739 printf("func can be random_range, random_rangel, random_rangell\n");
744 if ( sscanf(argv[2], "%i", &iter) != 1 ) {
745 printf("Usage: %s [func iterations] \n", argv[0]);
746 printf("argv[2] is not a number\n");
755 if ( strcmp(argv[1], "random_rangel") == 0 ) {
758 for(ind=0; ind<PARTNUM; ind++) {
759 valbound[ind]=part*ind;
762 for(cnt=0; cnt<iter; cnt++) {
763 lret=random_rangel(lmin, lmax, lmult, NULL);
765 printf("%ld\n", lret);
770 for(ind=0; ind<PARTNUM-1; ind++) {
771 if ( valbound[ind] < lret && lret <= valbound[ind+1] ) {
776 if ( lret > valbound[PARTNUM-1] ) {
780 for(ind=0; ind<PARTNUM-1; ind++) {
781 printf("%2d %-13ld to %-13ld %5ld %4.4f\n", ind+1,
782 valbound[ind], valbound[ind+1], cntarr[ind],
783 (float)(cntarr[ind]/(float)iter));
785 printf("%2d %-13ld to %-13ld %5ld %4.4f\n", PARTNUM,
786 valbound[PARTNUM-1], lmax, cntarr[PARTNUM-1],
787 (float)(cntarr[PARTNUM-1]/(float)iter));
788 printf(" min=%ld, max=%ld\n", ltmin, ltmax);
790 } else if ( strcmp(argv[1], "random_rangell") == 0 ) {
792 * random_rangell() unit test
795 lpart = llmax/PARTNUM;
796 for(ind=0; ind<PARTNUM; ind++) {
797 lvalbound[ind]=(long long)(lpart*ind);
800 for(cnt=0; cnt<iter; cnt++) {
801 llret=random_rangell(llmin, llmax, llmult, NULL);
803 printf("random_rangell returned %lld\n", llret);
804 if ( llret < lltmin )
806 if ( llret > lltmax )
809 for(ind=0; ind<PARTNUM-1; ind++) {
810 if ( lvalbound[ind] < llret && llret <= lvalbound[ind+1] ) {
815 if ( llret > lvalbound[PARTNUM-1] ) {
819 for(ind=0; ind<PARTNUM-1; ind++) {
820 printf("%2d %-13lld to %-13lld %5ld %4.4f\n", ind+1,
821 lvalbound[ind], lvalbound[ind+1], cntarr[ind],
822 (float)(cntarr[ind]/(float)iter));
824 printf("%2d %-13lld to %-13lld %5ld %4.4f\n", PARTNUM,
825 lvalbound[PARTNUM-1], llmax, cntarr[PARTNUM-1],
826 (float)(cntarr[PARTNUM-1]/(float)iter));
827 printf(" min=%lld, max=%lld\n", lltmin, lltmax);
831 * random_range() unit test
835 for(ind=0; ind<PARTNUM; ind++) {
836 valbound[ind]=part*ind;
839 for(cnt=0; cnt<iter; cnt++) {
840 lret=random_range(imin, imax, imult, NULL);
842 printf("%ld\n", lret);
848 for(ind=0; ind<PARTNUM-1; ind++) {
849 if ( valbound[ind] < lret && lret <= valbound[ind+1] ) {
854 if ( lret > valbound[PARTNUM-1] ) {
858 for(ind=0; ind<PARTNUM-1; ind++) {
859 printf("%2d %-13ld to %-13ld %5ld %4.4f\n", ind+1,
860 valbound[ind], valbound[ind+1], cntarr[ind],
861 (float)(cntarr[ind]/(float)iter));
863 printf("%2d %-13ld to %-13ld %5ld %4.4f\n", PARTNUM,
864 valbound[PARTNUM-1], (long)imax, cntarr[PARTNUM-1],
865 (float)(cntarr[PARTNUM-1]/(float)iter));
866 printf(" min=%d, max=%d\n", itmin, itmax);