From 01c165cd1b2ac601d5ae73d3cb5e82ccdd94ac94 Mon Sep 17 00:00:00 2001 From: Le Chi Thu Date: Tue, 3 Apr 2012 01:23:00 +0200 Subject: Initial commit --- ltp_framework/lib/random_range.c | 917 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 917 insertions(+) create mode 100644 ltp_framework/lib/random_range.c (limited to 'ltp_framework/lib/random_range.c') diff --git a/ltp_framework/lib/random_range.c b/ltp_framework/lib/random_range.c new file mode 100644 index 0000000..b1bde84 --- /dev/null +++ b/ltp_framework/lib/random_range.c @@ -0,0 +1,917 @@ +/* + * 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 +#include +#include +#include +#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<> 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= 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 ltmax) + ltmax = lret; + for (ind=0; ind valbound[PARTNUM-1]) { + cntarr[PARTNUM-1]++; + } + } + for (ind=0; ind lltmax) + lltmax = llret; + + for (ind=0; ind lvalbound[PARTNUM-1]) { + cntarr[PARTNUM-1]++; + } + } + for (ind=0; ind itmax) + itmax = lret; + + for (ind=0; ind valbound[PARTNUM-1]) { + cntarr[PARTNUM-1]++; + } + } + for (ind=0; ind