1 // SPDX-License-Identifier: GPL-2.0
3 * Copyright (c) 2000 Silicon Graphics, Inc.
10 #include "random_range.h"
13 * Internal format of the range array set up by parse_range()
23 * parse_ranges() is a function to parse a comma-separated list of range
24 * tokens each having the following form:
30 * any of the values may be blank (ie. min::mult, :max, etc.) and default
31 * values for missing arguments may be supplied by the caller.
33 * The special first form is short hand for 'num:num'.
35 * After parsing the string, the ranges are put into an array of integers,
36 * which is malloc'd by the routine. The min, max, and mult entries of each
37 * range can be extracted from the array using the range_min(), range_max(),
38 * and range_mult() functions.
40 * It is the responsibility of the caller to free the space allocated by
41 * parse_ranges() - a single call to free() will free the space.
43 * str The string to parse - assumed to be a comma-separated
44 * list of tokens having the above format.
45 * defmin default value to plug in for min, if it is missing
46 * defmax default value to plug in for max, if it is missing
47 * defmult default value to plug in for mult, if missing
48 * parse_func A user-supplied function pointer, which parse_ranges()
49 * can call to parse the min, max, and mult strings. This
50 * allows for customized number formats. The function
51 * MUST have the following prototype:
52 * parse_func(char *str, int *val)
53 * The function should return -1 if str cannot be parsed
54 * into an integer, or >= 0 if it was successfully
55 * parsed. The resulting integer will be stored in
56 * *val. If parse_func is NULL, parse_ranges will parse
57 * the tokens in a manner consistent with the the sscanf
59 * range_ptr A user-supplied char **, which will be set to point
60 * at malloc'd space which holds the parsed range
61 * values. If range_ptr is NULL, parse_ranges() just
62 * parses the string. The data returned in range_ptr
63 * should not be processed directly - use the functions
64 * range_min(), range_max(), and range_mult() to access
65 * data for a given range.
66 * errptr user-supplied char ** which can be set to point to a
67 * static error string. If errptr is NULL, it is ignored.
69 * parse_range() returns -1 on error, or the number of ranges parsed.
72 static int str_to_int();
73 static long long divider(long long, long long, long long, long long);
76 parse_ranges(str, defmin, defmax, defmult, parse_func, rangeptr, errptr)
86 char *tmpstr, *cp, *tok, *n1str, *n2str, *multstr;
87 struct range *rp, *ranges;
88 static char errmsg[256];
94 for (ncommas = 0, cp = str; *cp != '\0'; cp++) {
100 if (parse_func == NULL) {
101 parse_func = str_to_int;
104 tmpstr = strdup(str);
105 ranges = (struct range *)malloc((ncommas+1) * sizeof(struct range));
108 tok = strtok(tmpstr, ",");
109 while (tok != NULL) {
118 if ((cp = strchr(n1str, ':')) != NULL) {
122 if ((cp = strchr(n2str, ':')) != NULL) {
129 * Parse the 'min' field - if it is zero length (:n2[:mult]
130 * format), retain the default value, otherwise, pass the
131 * string to the parse function.
134 if ((int)strlen(n1str) > 0) {
135 if ((*parse_func)(n1str, &rp->min) < 0) {
136 sprintf(errmsg, "error parsing string %s into an integer", n1str);
144 * Process the 'max' field - if one was not present (n1 format)
145 * set max equal to min. If the field was present, but
146 * zero length (n1: format), retain the default. Otherwise
147 * pass the string to the parse function.
152 } else if ((int)strlen(n2str) > 0) {
153 if ((*parse_func)(n2str, &rp->max) < 0) {
154 sprintf(errmsg, "error parsing string %s into an integer", n2str);
162 * Process the 'mult' field - if one was not present
163 * (n1:n2 format), or the field was zero length (n1:n2: format)
164 * then set the mult field to defmult - otherwise pass then
165 * mult field to the parse function.
168 if (multstr != NULL && (int)strlen(multstr) > 0) {
169 if ((*parse_func)(multstr, &rp->mult) < 0) {
170 sprintf(errmsg, "error parsing string %s into an integer", multstr);
178 tok = strtok(NULL, ",");
183 if (rangeptr != NULL) {
184 *rangeptr = (char *)ranges;
186 free(ranges); /* just running in parse mode */
189 return (rp - ranges);
193 * The default integer-parsing function
203 if (sscanf(str, "%i%c", ip, &c) != 1) {
211 * Three simple functions to return the min, max, and mult values for a given
212 * range. It is assumed that rbuf is a range buffer set up by parse_ranges(),
213 * and that r is a valid range within that buffer.
221 return ((struct range *)rbuf)[r].min;
229 return ((struct range *)rbuf)[r].max;
237 return ((struct range *)rbuf)[r].mult;
240 /*****************************************************************************
241 * random_range(int start, int end, int mult, char **errp)
243 * Returns a psuedo-random number which is >= 'start', <= 'end', and a multiple
244 * of 'mult'. Start and end may be any valid integer, but mult must be an
245 * integer > 0. errp is a char ** which will be set to point to a static
246 * error message buffer if it is not NULL, and an error occurs.
248 * The errp is the only way to check if the routine fails - currently the only
249 * failure conditions are:
252 * no numbers in the start-end range that are a multiple of 'mult'
254 * If random_range_fails, and errp is a valid pointer, it will point to an
255 * internal error buffer. If errp is a vaild pointer, and random_range
256 * is successful, errp will be set to NULL.
258 * Note - if mult is 1 (the most common case), there are error conditions
259 * possible, and errp need not be used.
261 * Note: Uses lrand48(), assuming that set_random_seed() uses srand48() when
263 *****************************************************************************/
266 random_range(min, max, mult, errp)
272 int r, nmults, orig_min, orig_max, orig_mult, tmp;
273 extern long lrand48();
274 static char errbuf[128];
282 sprintf(errbuf, "mult arg must be greater than 0");
289 * Save original parameter values for use in error message
297 * switch min/max if max < min
307 * select the random number
310 if ((r = min % mult)) /* bump to the next higher 'mult' multiple */
313 if ((r = max % mult)) /* reduce to the next lower 'mult' multiple */
316 if (min > max) { /* no 'mult' multiples between min & max */
318 sprintf(errbuf, "no numbers in the range %d:%d that are a multiple of %d", orig_min, orig_max, orig_mult);
328 nmults = ((max - min) / mult) + 1;
329 return (min + ((lrand48() % nmults) * mult));
333 * Just like random_range, but all values are longs.
336 random_rangel(min, max, mult, errp)
342 long r, nmults, orig_min, orig_max, orig_mult, tmp;
343 extern long lrand48();
344 static char errbuf[128];
352 sprintf(errbuf, "mult arg must be greater than 0");
359 * Save original parameter values for use in error message
367 * switch min/max if max < min
377 * select the random number
380 if ((r = min % mult)) /* bump to the next higher 'mult' multiple */
383 if ((r = max % mult)) /* reduce to the next lower 'mult' multiple */
386 if (min > max) { /* no 'mult' multiples between min & max */
389 "no numbers in the range %ld:%ld that are a multiple of %ld",
390 orig_min, orig_max, orig_mult);
400 nmults = ((max - min) / mult) + 1;
401 #if (_MIPS_SZLONG == 64)
403 * If max is less than 2gb, then the value can fit in 32 bits
404 * and the standard lrand48() routine can be used.
406 if ( max <= (long)2147483647 ) {
407 return (long) (min + (((long)lrand48() % nmults) * mult));
410 * max is greater than 2gb - meeds more than 32 bits.
411 * Since lrand48 only will get a number up to 32bits.
414 randnum=divider(min, max, 0, -1);
415 return (long) (min + ((randnum % nmults) * mult));
419 return (min + ((lrand48() % nmults) * mult));
424 * Attempts to be just like random_range, but everything is long long (64 bit)
427 random_rangell(min, max, mult, errp)
433 long long r, nmults, orig_min, orig_max, orig_mult, tmp;
435 extern long lrand48();
436 static char errbuf[128];
444 sprintf(errbuf, "mult arg must be greater than 0");
451 * Save original parameter values for use in error message
459 * switch min/max if max < min
469 * select the random number
472 if ((r = min % mult)) /* bump to the next higher 'mult' multiple */
475 if ((r = max % mult)) /* reduce to the next lower 'mult' multiple */
478 if (min > max) { /* no 'mult' multiples between min & max */
481 "no numbers in the range %lld:%lld that are a multiple of %lld",
482 orig_min, orig_max, orig_mult);
492 nmults = ((max - min) / mult) + 1;
494 * If max is less than 2gb, then the value can fit in 32 bits
495 * and the standard lrand48() routine can be used.
497 if ( max <= (long)2147483647 ) {
498 return (long long) (min + (((long long)lrand48() % nmults) * mult));
501 * max is greater than 2gb - meeds more than 32 bits.
502 * Since lrand48 only will get a number up to 32bits.
504 randnum=divider(min, max, 0, -1);
505 return (long long) (min + ((randnum % nmults) * mult));
511 * This functional will recusively call itself to return a random
512 * number min and max. It was designed to work the 64bit numbers
513 * even when compiled as 32 bit process.
514 * algorithm: to use the official lrand48() routine - limited to 32 bits.
515 * find the difference between min and max (max-min).
516 * if the difference is 2g or less, use the random number gotton from lrand48().
517 * Determine the midway point between min and max.
518 * if the midway point is less than 2g from min or max,
519 * randomly add the random number gotton from lrand48() to
520 * either min or the midpoint.
521 * Otherwise, call outself with min and max being min and midway value or
522 * midway value and max. This will reduce the range in half.
525 divider(long long min, long long max, long long cnt, long long rand)
527 long long med, half, diff;
530 * prevent run away code. We are dividing by two each count.
531 * if we get to a count of more than 32, we should have gotten
538 * Only get a random number the first time.
540 if ( cnt == 0 || rand < -1 ) {
541 rand = (long long)lrand48(); /* 32 bit random number */
546 if ( diff <= 2147483647 )
549 half = diff/(long long)2; /* half the distance between min and max */
550 med = min + half; /* med way point between min and max */
553 printf("divider: min=%lld, max=%lld, cnt=%lld, rand=%lld\n", min, max, cnt, rand);
554 printf(" diff = %lld, half = %lld, med = %lld\n", diff, half, med);
557 if ( half <= 2147483647 ) {
559 * If half is smaller than 2gb, we can use the random number
560 * to pick the number within the min to med or med to max
561 * if the cnt bit of rand is zero or one, respectively.
563 if ( rand & (1<<cnt) )
569 * recursively call ourself to reduce the value to the bottom half
570 * or top half (bit cnt is set).
572 if ( rand & (1<<cnt) ) {
573 return divider(med, max, cnt+1, rand);
575 return divider(min, med, cnt+1, rand);
583 /*****************************************************************************
584 * random_range_seed(s)
586 * Sets the random seed to s. Uses srand48(), assuming that lrand48() will
587 * be used in random_range().
588 *****************************************************************************/
594 extern void srand48();
599 /****************************************************************************
602 * This function randomly returns a single bit from the bits
603 * set in mask. If mask is zero, zero is returned.
605 ****************************************************************************/
607 random_bit(long mask)
609 int nbits = 0; /* number of set bits in mask */
610 long bit; /* used to count bits and num of set bits choosen */
611 int nshift; /* used to count bit shifts */
617 * get the number of bits set in mask
620 for ( nshift=0; nshift<sizeof(long)*8; nshift++) {
627 * randomly choose a bit.
629 bit=random_range(1, nbits, 1, NULL);
632 * shift bits until you determine which bit was randomly choosen.
633 * nshift will hold the number of shifts to make.
638 /* check if the current one's bit is set */
646 return 01L << (nshift-1);
651 #if RANDOM_BIT_UNITTEST
653 * The following is a unit test main function for random_bit().
663 printf("test for first and last bit set\n");
665 ret=random_bit(mask);
666 printf("random_bit(%#o) returned %#o\n", mask, ret);
668 mask=1L<<(sizeof(long)*8-1);
669 ret=random_bit(mask);
670 printf("random_bit(%#o) returned %#o\n", mask, ret);
674 for (ind=2; ind<argc; ind++) {
675 printf("Calling random_bit %d times for mask %#o\n", iter, mask);
676 sscanf(argv[ind], "%i", &mask);
677 for (cnt=0; cnt<iter; cnt++) {
678 ret=random_bit(mask);
679 printf("random_bit(%#o) returned %#o\n", mask, ret);
686 #endif /* end if RANDOM_BIT_UNITTEST */
691 * The following is a unit test main function for random_range*().
694 #define PARTNUM 10 /* used to determine even distribution of random numbers */
695 #define MEG 1024*1024*1024
696 #define GIG 1073741824
704 int imin=0, imult=1, itmin, itmax=0;
707 long lret, lmin=0, lmult=1, ltmin, ltmax=0;
708 #if (_MIPS_SZLONG == 64)
709 long lmax=6*(long)GIG; /* higher than 32 bits */
713 long long llret, llmin=0, llmult=1, lltmin, lltmax=0;
714 long long llmax=(long long)80*(long long)GIG;
718 long cntarr[PARTNUM];
719 long valbound[PARTNUM];
720 long long lvalbound[PARTNUM];
722 for (ind=0; ind<PARTNUM; ind++ )
726 printf("Usage: %s func [iterations] \n", argv[0]);
727 printf("func can be random_range, random_rangel, random_rangell\n");
732 if ( sscanf(argv[2], "%i", &iter) != 1 ) {
733 printf("Usage: %s [func iterations] \n", argv[0]);
734 printf("argv[2] is not a number\n");
743 if ( strcmp(argv[1], "random_rangel") == 0 ) {
746 for(ind=0; ind<PARTNUM; ind++) {
747 valbound[ind]=part*ind;
750 for(cnt=0; cnt<iter; cnt++) {
751 lret=random_rangel(lmin, lmax, lmult, NULL);
753 printf("%ld\n", lret);
758 for(ind=0; ind<PARTNUM-1; ind++) {
759 if ( valbound[ind] < lret && lret <= valbound[ind+1] ) {
764 if ( lret > valbound[PARTNUM-1] ) {
768 for(ind=0; ind<PARTNUM-1; ind++) {
769 printf("%2d %-13ld to %-13ld %5ld %4.4f\n", ind+1,
770 valbound[ind], valbound[ind+1], cntarr[ind],
771 (float)(cntarr[ind]/(float)iter));
773 printf("%2d %-13ld to %-13ld %5ld %4.4f\n", PARTNUM,
774 valbound[PARTNUM-1], lmax, cntarr[PARTNUM-1],
775 (float)(cntarr[PARTNUM-1]/(float)iter));
776 printf(" min=%ld, max=%ld\n", ltmin, ltmax);
778 } else if ( strcmp(argv[1], "random_rangell") == 0 ) {
780 * random_rangell() unit test
783 lpart = llmax/PARTNUM;
784 for(ind=0; ind<PARTNUM; ind++) {
785 lvalbound[ind]=(long long)(lpart*ind);
788 for(cnt=0; cnt<iter; cnt++) {
789 llret=random_rangell(llmin, llmax, llmult, NULL);
791 printf("random_rangell returned %lld\n", llret);
792 if ( llret < lltmin )
794 if ( llret > lltmax )
797 for(ind=0; ind<PARTNUM-1; ind++) {
798 if ( lvalbound[ind] < llret && llret <= lvalbound[ind+1] ) {
803 if ( llret > lvalbound[PARTNUM-1] ) {
807 for(ind=0; ind<PARTNUM-1; ind++) {
808 printf("%2d %-13lld to %-13lld %5ld %4.4f\n", ind+1,
809 lvalbound[ind], lvalbound[ind+1], cntarr[ind],
810 (float)(cntarr[ind]/(float)iter));
812 printf("%2d %-13lld to %-13lld %5ld %4.4f\n", PARTNUM,
813 lvalbound[PARTNUM-1], llmax, cntarr[PARTNUM-1],
814 (float)(cntarr[PARTNUM-1]/(float)iter));
815 printf(" min=%lld, max=%lld\n", lltmin, lltmax);
819 * random_range() unit test
823 for(ind=0; ind<PARTNUM; ind++) {
824 valbound[ind]=part*ind;
827 for(cnt=0; cnt<iter; cnt++) {
828 lret=random_range(imin, imax, imult, NULL);
830 printf("%ld\n", lret);
836 for(ind=0; ind<PARTNUM-1; ind++) {
837 if ( valbound[ind] < lret && lret <= valbound[ind+1] ) {
842 if ( lret > valbound[PARTNUM-1] ) {
846 for(ind=0; ind<PARTNUM-1; ind++) {
847 printf("%2d %-13ld to %-13ld %5ld %4.4f\n", ind+1,
848 valbound[ind], valbound[ind+1], cntarr[ind],
849 (float)(cntarr[ind]/(float)iter));
851 printf("%2d %-13ld to %-13ld %5ld %4.4f\n", PARTNUM,
852 valbound[PARTNUM-1], (long)imax, cntarr[PARTNUM-1],
853 (float)(cntarr[PARTNUM-1]/(float)iter));
854 printf(" min=%d, max=%d\n", itmin, itmax);