diff options
Diffstat (limited to 'generator/pgmnoise.c')
| -rw-r--r-- | generator/pgmnoise.c | 118 |
1 files changed, 80 insertions, 38 deletions
diff --git a/generator/pgmnoise.c b/generator/pgmnoise.c index e3e4eca6..ea35956b 100644 --- a/generator/pgmnoise.c +++ b/generator/pgmnoise.c @@ -7,12 +7,17 @@ #include "pm_c_util.h" #include "mallocvar.h" #include "nstring.h" +#include "rand.h" #include "shhopt.h" #include "pgm.h" +/* constants */ +static unsigned long int const ceil31bits = 0x7fffffffUL; +static unsigned long int const ceil32bits = 0xffffffffUL; -struct cmdlineInfo { + +struct CmdlineInfo { /* All the information the user supplied in the command line, in a form easy for the program to use. */ @@ -21,13 +26,15 @@ struct cmdlineInfo { unsigned int maxval; unsigned int randomseed; unsigned int randomseedSpec; + unsigned int verbose; }; static void -parseCommandLine(int argc, const char ** const argv, - struct cmdlineInfo * const cmdlineP) { +parseCommandLine(int argc, + const char ** const argv, + struct CmdlineInfo * const cmdlineP) { /*---------------------------------------------------------------------------- Note that the file spec array we return is stored in the storage that was passed to us as the argv array. @@ -46,6 +53,8 @@ parseCommandLine(int argc, const char ** const argv, &cmdlineP->randomseedSpec, 0); OPTENT3(0, "maxval", OPT_UINT, &cmdlineP->maxval, &maxvalSpec, 0); + OPTENT3(0, "verbose", OPT_FLAG, NULL, + &cmdlineP->verbose, 0); opt.opt_table = option_def; opt.short_allowed = FALSE; /* We have no short (old-fashioned) options */ @@ -57,7 +66,7 @@ parseCommandLine(int argc, const char ** const argv, if (maxvalSpec) { if (cmdlineP->maxval > PGM_OVERALLMAXVAL) - pm_error("Maxval too large: %u. Maximu is %u", + pm_error("Maxval too large: %u. Maximum is %u", cmdlineP->maxval, PGM_OVERALLMAXVAL); else if (cmdlineP->maxval == 0) pm_error("Maxval must not be zero"); @@ -95,38 +104,43 @@ parseCommandLine(int argc, const char ** const argv, static unsigned int -randPool(unsigned int const digits) { +randPool(unsigned int const nDigits, + struct pm_randSt * const randStP) { /*---------------------------------------------------------------------------- - Draw 'digits' bits from pool of random bits. If the number of random bits - in pool is insufficient, call rand() and add 31 bits to it. + Draw 'nDigits' bits from pool of random bits. If the number of random bits + in pool is insufficient, call pm_rand() and add N bits to it. + + N is 31 or 32. In raw mode we use N = 32 regardless of the actual number of + available bits. If there are only 31 available, we use zero for the MSB. - 'digits' must be at most 16. + 'nDigits' must be at most 16. - We assume that each call to rand() generates 31 bits, or RAND_MAX == - 2147483647. + We assume that each call to pm_rand() generates 31 or 32 bits, or + randStP->max == 2147483647 or 4294967295. - The underlying logic is flexible and endian-free. The above conditions - can be relaxed. + The underlying logic is flexible and endian-free. The above conditions can + be relaxed. -----------------------------------------------------------------------------*/ static unsigned long int hold=0; /* entropy pool */ static unsigned int len=0; /* number of valid bits in pool */ - unsigned int const mask = (1 << digits) - 1; - + unsigned int const mask = (1 << nDigits) - 1; + unsigned int const randbits = (randStP->max == ceil31bits) ? 31 : 32; unsigned int retval; - assert(RAND_MAX == 2147483647 && digits <= 16); + assert(randStP->max == ceil31bits || randStP->max == ceil32bits); + assert(nDigits <= 16); retval = hold; /* initial value */ - if (len > digits) { /* Enough bits in hold to satisfy request */ - hold >>= digits; - len -= digits; - } else { /* Load another 31 bits into hold */ - hold = rand(); + if (len > nDigits) { /* Enough bits in hold to satisfy request */ + hold >>= nDigits; + len -= nDigits; + } else { /* Load another 31 or 32 bits into hold */ + hold = pm_rand(randStP); retval |= (hold << len); - hold >>= (digits - len); - len = 31 - digits + len; + hold >>= (nDigits - len); + len = randbits - nDigits + len; } return (retval & mask); } @@ -134,36 +148,61 @@ randPool(unsigned int const digits) { static void -pgmnoise(FILE * const ofP, - unsigned int const cols, - unsigned int const rows, - gray const maxval) { +reportVerbose(struct pm_randSt * const randStP, + gray const maxval, + bool const usingPool) { + + pm_message("random seed: %u", randStP->seed); + pm_message("random max: %u maxval: %u", randStP->max, maxval); + pm_message("method: %s", usingPool ? "pool" : "modulo"); +} + + - bool const usingPool = !(RAND_MAX==2147483647 && (maxval & (maxval+1))); +static void +pgmnoise(FILE * const ofP, + unsigned int const cols, + unsigned int const rows, + gray const maxval, + bool const verbose, + struct pm_randSt * const randStP) { + + bool const usingPool = + (randStP->max==ceil31bits || randStP->max==ceil32bits) && + !(maxval & (maxval+1)); unsigned int const bitLen = pm_maxvaltobits(maxval); unsigned int row; gray * destrow; /* If maxval is 2^n-1, we draw exactly n bits from the pool. - Otherwise call rand() and determine gray value by modulo. + Otherwise call pm_rand() and determine gray value by modulo. In the latter case, there is a minuscule skew toward 0 (=black) because smaller numbers are produced more frequently by modulo. Thus we employ the pool method only when it is certain that no - skew will ensue. + skew will result. To illustrate the point, consider converting the outcome of one roll of a fair, six-sided die to 5 values (0 to 4) by N % 5. The - probability for values 1, 2, 3, 4 are 1/6, but 0 alone is 2/6. + probability for values 1, 2, 3, 4 is 1/6, but 0 alone is 2/6. Average is 10/6 or 1.6667, compared to 2.0 from an ideal generator which produces exactly 5 values. With two dice average improves to 70/36 or 1.9444. The more (distinct) dice we roll, or the more binary digits we draw, the smaller the skew. + + The pool method is economical. But there is an additional merit: + No bits are lost this way. This gives us a means to check the + integrity of the random number generator. + + - Akira Urushibata, March 2021 */ + if (verbose) + reportVerbose(randStP, maxval, usingPool); + destrow = pgm_allocrow(cols); pgm_writepgminit(ofP, cols, rows, maxval, 0); @@ -172,12 +211,11 @@ pgmnoise(FILE * const ofP, if (usingPool) { unsigned int col; for (col = 0; col < cols; ++col) - destrow[col] = randPool(bitLen); - } - else { + destrow[col] = randPool(bitLen, randStP); + } else { unsigned int col; for (col = 0; col < cols; ++col) - destrow[col] = rand() % (maxval + 1); + destrow[col] = pm_rand(randStP) % (maxval + 1); } pgm_writepgmrow(ofP, destrow, cols, maxval, 0); } @@ -191,18 +229,22 @@ int main(int argc, const char * argv[]) { - struct cmdlineInfo cmdline; + struct CmdlineInfo cmdline; + struct pm_randSt randSt; pm_proginit(&argc, argv); parseCommandLine(argc, argv, &cmdline); - srand(cmdline.randomseedSpec ? cmdline.randomseed : pm_randseed()); + pm_randinit(&randSt); + pm_srand2(&randSt, cmdline.randomseedSpec, cmdline.randomseed); + + pgmnoise(stdout, cmdline.width, cmdline.height, cmdline.maxval, + cmdline.verbose, &randSt); - pgmnoise(stdout, cmdline.width, cmdline.height, cmdline.maxval); + pm_randterm(&randSt); return 0; } - |