X-Git-Url: https://git.verplant.org/?a=blobdiff_plain;f=src%2Frandom_generator.cpp;h=c3608e8b8b737e229101b5ec52ba6f2b84ce0acc;hb=8b8e1c3576cedddb1d88eafa5fd4804e8257793c;hp=c8eac09d4c9f7473995ec4f2721c4efcaa6c1fce;hpb=d1b1b4272a84696689574b3bcdc2ee5bd39a9796;p=supertux.git diff --git a/src/random_generator.cpp b/src/random_generator.cpp index c8eac09d4..c3608e8b8 100644 --- a/src/random_generator.cpp +++ b/src/random_generator.cpp @@ -1,5 +1,5 @@ // $Id$ -// +// // A strong random number generator // // Copyright (C) 2006 Allen King @@ -9,16 +9,16 @@ // Redistribution and use in source and binary forms, with or without // modification, are permitted provided that the following conditions // are met: -// -// 1. Redistributions of source code must retain the above copyright -// notice, this list of conditions and the following disclaimer. +// +// 1. Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. // 2. Redistributions in binary form must reproduce the above copyright // notice, this list of conditions and the following disclaimer in the -// documentation and/or other materials provided with the distribution. +// documentation and/or other materials provided with the distribution. // 3. Neither the name of the project nor the names of its contributors // may be used to endorse or promote products derived from this software -// without specific prior written permission. -// +// without specific prior written permission. +// // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND // ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE @@ -28,23 +28,25 @@ // OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) // HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY -// OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +// OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF // SUCH DAMAGE. // Transliterated into C++ Allen King 060417, from sources on // http://www.jbox.dk/sanos/source/lib/random.c.html - +#include #include +#include +#include #include "random_generator.hpp" -#include "scripting/squirrel_util.hpp" RandomGenerator systemRandom; // global random number generator RandomGenerator::RandomGenerator() { assert(sizeof(int) >= 4); initialized = 0; + debug = 0; // change this by hand for debug initialize(); } @@ -52,30 +54,51 @@ RandomGenerator::~RandomGenerator() { } int RandomGenerator::srand(int x) { - while (x == 0) // random seed of zero means - x = (time(0) % RAND_MAX); // randomize with time - assert(x < RAND_MAX); // only allow posative 31-bit seeds - assert(sizeof(int) >= 4); - srandom(x); + int x0 = x; + while (x <= 0) // random seed of zero means + x = time(0) % RandomGenerator::rand_max; // randomize with time + + if (debug > 0) + printf("==== srand(%10d) (%10d) rand_max=%x =====\n", + x, x0, RandomGenerator::rand_max); + + RandomGenerator::srandom(x); return x; // let caller know seed used } -int RandomGenerator::rand() { return random(); } +int RandomGenerator::rand() { + int rv; // a positive int + while ((rv = RandomGenerator::random()) <= 0) // neg or zero causes probs + ; + if (debug > 0) + printf("==== rand(): %10d =====\n", rv); + return rv; +} int RandomGenerator::rand(int v) { - assert(v != 0 && v <= RAND_MAX); // illegal arg: 0 or too big - return RandomGenerator::random() % v; + assert(v >= 0 && v <= RandomGenerator::rand_max); // illegal arg + + // remove biases, esp. when v is large (e.g. v == (rand_max/4)*3;) + int rv, maxV =(RandomGenerator::rand_max / v) * v; + assert(maxV <= RandomGenerator::rand_max); + while ((rv = RandomGenerator::random()) >= maxV) + ; + return rv % v; // mod it down to 0..(maxV-1) } int RandomGenerator::rand(int u, int v) { - assert(v > u); + assert(v > u); return u + RandomGenerator::rand(v-u); } double RandomGenerator::randf(double v) { float rv; - while ((rv = (double)RandomGenerator::random() / RAND_MAX * v) >= v) - ; // never return v! + do { + rv = ((double)RandomGenerator::random())/RandomGenerator::rand_max * v; + } while (rv >= v); // rounding might cause rv==v + + if (debug > 0) + printf("==== rand(): %f =====\n", rv); return rv; } @@ -84,23 +107,23 @@ double RandomGenerator::randf(double u, double v) { } //----------------------------------------------------------------------- -// +// // Copyright (C) 2002 Michael Ringgaard. All rights reserved. // Copyright (C) 1983, 1993 The Regents of the University of California. // // Redistribution and use in source and binary forms, with or without // modification, are permitted provided that the following conditions // are met: -// -// 1. Redistributions of source code must retain the above copyright -// notice, this list of conditions and the following disclaimer. +// +// 1. Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. // 2. Redistributions in binary form must reproduce the above copyright // notice, this list of conditions and the following disclaimer in the -// documentation and/or other materials provided with the distribution. +// documentation and/or other materials provided with the distribution. // 3. Neither the name of the project nor the names of its contributors // may be used to endorse or promote products derived from this software -// without specific prior written permission. -// +// without specific prior written permission. +// // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND // ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE @@ -110,9 +133,9 @@ double RandomGenerator::randf(double u, double v) { // OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) // HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY -// OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +// OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF // SUCH DAMAGE. -// +// //**#include @@ -124,7 +147,7 @@ double RandomGenerator::randf(double u, double v) { // then initialized to contain information for random number generation with // that much state information. Good sizes for the amount of state // information are 32, 64, 128, and 256 bytes. The state can be switched by -// calling the setstate() routine with the same array as was initiallized +// calling the setstate() routine with the same array as was initialized // with initstate(). By default, the package runs with 128 bytes of state // information and generates far better random numbers than a linear // congruential generator. If the amount of state information is less than @@ -228,7 +251,7 @@ void RandomGenerator::initialize() { randtbl[30] = 0x535b6b41; randtbl[31] = 0xf3bec5da; -// static long randtbl[DEG_3 + 1] = +// static long randtbl[DEG_3 + 1] = // { // TYPE_3; // 0x991539b1, 0x16a5bce3, 0x6774a4cd, 0x3e01511e, 0x4e508aaa, 0x61048c05, @@ -279,7 +302,7 @@ void RandomGenerator::initialize() { // // Compute x = (7^5 * x) mod (2^31 - 1) -// wihout overflowing 31 bits: +// without overflowing 31 bits: // (2^31 - 1) = 127773 * (7^5) + 2836 // From "Random number generators: good ones are hard to find", // Park and Miller, Communications of the ACM, vol. 31, no. 10, @@ -318,7 +341,7 @@ void RandomGenerator::srandom(unsigned long x) state[0] = x; if (rand_type == TYPE_0) lim = NSHUFF; - else + else { for (i = 1; i < rand_deg; i++) state[i] = good_rand(state[i - 1]); fptr = &state[rand_sep]; @@ -358,13 +381,13 @@ void RandomGenerator::srandomdev() done = 0; fd = open("/dev/urandom", O_RDONLY); - if (fd >= 0) + if (fd >= 0) { if (read(fd, state, len) == len) done = 1; close(fd); } - if (!done) + if (!done) { struct timeval tv; @@ -373,7 +396,7 @@ void RandomGenerator::srandomdev() return; } - if (rand_type != TYPE_0) + if (rand_type != TYPE_0) { fptr = &state[rand_sep]; rptr = &state[0]; @@ -413,37 +436,37 @@ char * RandomGenerator::initstate(unsigned long seed, char *arg_state, long n) if (n < BREAK_0) return NULL; - if (n < BREAK_1) + if (n < BREAK_1) { rand_type = TYPE_0; rand_deg = DEG_0; rand_sep = SEP_0; - } - else if (n < BREAK_2) + } + else if (n < BREAK_2) { rand_type = TYPE_1; rand_deg = DEG_1; rand_sep = SEP_1; - } - else if (n < BREAK_3) + } + else if (n < BREAK_3) { rand_type = TYPE_2; rand_deg = DEG_2; rand_sep = SEP_2; - } - else if (n < BREAK_4) + } + else if (n < BREAK_4) { rand_type = TYPE_3; rand_deg = DEG_3; rand_sep = SEP_3; - } - else + } + else { rand_type = TYPE_4; rand_deg = DEG_4; rand_sep = SEP_4; } - + state = (long *) (long_arg_state + 1); // First location end_ptr = &state[rand_deg]; // Must set end_ptr before srandom srandom(seed); @@ -485,7 +508,7 @@ char * RandomGenerator::setstate(char *arg_state) else state[-1] = MAX_TYPES * (rptr - state) + rand_type; - switch(type) + switch(type) { case TYPE_0: case TYPE_1: @@ -499,7 +522,7 @@ char * RandomGenerator::setstate(char *arg_state) } state = (long *) (new_state + 1); - if (rand_type != TYPE_0) + if (rand_type != TYPE_0) { rptr = &state[rear]; fptr = &state[(rear + rand_sep) % rand_deg]; @@ -536,22 +559,22 @@ long RandomGenerator::random() throw std::runtime_error("uninitialized RandomGenerator object"); } - if (rand_type == TYPE_0) + if (rand_type == TYPE_0) { i = state[0]; state[0] = i = (good_rand(i)) & 0x7fffffff; - } - else + } + else { f = fptr; r = rptr; *f += *r; i = (*f >> 1) & 0x7fffffff; // Chucking least random bit - if (++f >= end_ptr) + if (++f >= end_ptr) { f = state; ++r; } - else if (++r >= end_ptr) + else if (++r >= end_ptr) r = state; fptr = f; rptr = r;