From b17b9021ecf9b16c265d0a6b60faa761b34eae35 Mon Sep 17 00:00:00 2001 From: Ben Longbons Date: Tue, 12 Feb 2013 20:18:58 -0800 Subject: Replace mt_rand with Also add some utility methods and classes. --- src/common/core.cpp | 5 +- src/common/md5calc.cpp | 7 +-- src/common/mt_rand.cpp | 123 ------------------------------------------------ src/common/mt_rand.hpp | 24 ---------- src/common/random.cpp | 8 ++++ src/common/random.hpp | 69 +++++++++++++++++++++++++++ src/common/random.t.hpp | 23 +++++++++ src/common/random2.hpp | 74 +++++++++++++++++++++++++++++ 8 files changed, 179 insertions(+), 154 deletions(-) delete mode 100644 src/common/mt_rand.cpp delete mode 100644 src/common/mt_rand.hpp create mode 100644 src/common/random.cpp create mode 100644 src/common/random.hpp create mode 100644 src/common/random.t.hpp create mode 100644 src/common/random2.hpp (limited to 'src/common') diff --git a/src/common/core.cpp b/src/common/core.cpp index ae0e3eb..994de93 100644 --- a/src/common/core.cpp +++ b/src/common/core.cpp @@ -8,7 +8,7 @@ #include #include -#include "mt_rand.hpp" +#include "random.hpp" #include "socket.hpp" #include "timer.hpp" @@ -68,9 +68,6 @@ bool runflag = true; */ int main(int argc, char **argv) { - /// Note that getpid() and getppid() may be very close - mt_seed(time(NULL) ^ (getpid() << 16) ^ (getppid() << 8)); - do_socket(); do_init(argc, argv); diff --git a/src/common/md5calc.cpp b/src/common/md5calc.cpp index c9c2415..1625912 100644 --- a/src/common/md5calc.cpp +++ b/src/common/md5calc.cpp @@ -2,7 +2,7 @@ #include -#include "mt_rand.hpp" +#include "random.hpp" #include "../poison.hpp" @@ -305,8 +305,9 @@ const char *MD5_saltcrypt(const char *key, const char *salt) const char *make_salt(void) { static char salt[6]; - for (int i=0; i<5; i++) - salt[i] = MPRAND(48, 78); + for (int i = 0; i < 5; i++) + // 126 would probably actually be okay + salt[i] = random_::in(48, 125); return salt; } diff --git a/src/common/mt_rand.cpp b/src/common/mt_rand.cpp deleted file mode 100644 index fbbf71f..0000000 --- a/src/common/mt_rand.cpp +++ /dev/null @@ -1,123 +0,0 @@ -/* -// This is the ``Mersenne Twister'' random number generator MT19937, which -// generates pseudorandom integers uniformly distributed in 0..(2^32 - 1) -// starting from any odd seed in 0..(2^32 - 1). This version is a recode -// by Shawn Cokus (Cokus@math.washington.edu) on March 8, 1998 of a version by -// Takuji Nishimura (who had suggestions from Topher Cooper and Marc Rieffel in -// July-August 1997). -// -// Effectiveness of the recoding (on Goedel2.math.washington.edu, a DEC Alpha -// running OSF/1) using GCC -O3 as a compiler: before recoding: 51.6 sec. to -// generate 300 million random numbers; after recoding: 24.0 sec. for the same -// (i.e., 46.5% of original time), so speed is now about 12.5 million random -// number generations per second on this machine. -// -// According to the URL -// (and paraphrasing a bit in places), the Mersenne Twister is ``designed -// with consideration of the flaws of various existing generators,'' has -// a period of 2^19937 - 1, gives a sequence that is 623-dimensionally -// equidistributed, and ``has passed many stringent tests, including the -// die-hard test of G. Marsaglia and the load test of P. Hellekalek and -// S. Wegenkittl.'' It is efficient in memory usage (typically using 2506 -// to 5012 bytes of static data, depending on data type sizes, and the code -// is quite short as well). It generates random numbers in batches of 624 -// at a time, so the caching and pipelining of modern systems is exploited. -// It is also divide- and mod-free. -// -// This library is free software; you can redistribute it and/or modify it -// under the terms of the GNU Library General Public License as published by -// the Free Software Foundation (either version 2 of the License or, at your -// option, any later version). This library is distributed in the hope that -// it will be useful, but WITHOUT ANY WARRANTY, without even the implied -// warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See -// the GNU Library General Public License for more details. You should have -// received a copy of the GNU Library General Public License along with this -// library; if not, write to the Free Software Foundation, Inc., 59 Temple -// Place, Suite 330, Boston, MA 02111-1307, USA. -// -// The code as Shawn received it included the following notice: -// -// Copyright (C) 1997 Makoto Matsumoto and Takuji Nishimura. When -// you use this, send an e-mail to with -// an appropriate reference to your work. -// -// It would be nice to CC: when you write. -// -*/ - -#include "mt_rand.hpp" - -#include - -#include "../poison.hpp" - -#define N 624 // length of state vector -#define M 397 // a period parameter -#define K 0x9908B0DFU // a magic constant - -#define hiBit(u) ((u) & 0x80000000U) // mask all but highest bit of u -#define loBit(u) ((u) & 0x00000001U) // mask all but lowest bit of u -#define loBits(u) ((u) & 0x7FFFFFFFU) // mask the highest bit of u -#define mixBits(u, v) (hiBit(u)|loBits(v)) // move hi bit of u to hi bit of v - -static -uint32_t state[N+1]; // state vector the +1 is needed due to the coding -static -uint32_t *next; // next random value is computed from here -static -int left = -1; // can *next++ this many times before reloading - -void mt_seed(uint32_t seed) -{ - uint32_t x = seed | 1U; - uint32_t *s = state; - left = 0; - - for (int j = N; *s++ = x, --j; x *= 69069U); -} - -static -void mt_reload(void) -{ - // if mt_seed has never been called - if (left < -1) - mt_seed(time(NULL)); - - // conceptually, these are indices into the state that wrap - uint32_t *p0 = state; - uint32_t *p2 = state + 2; - uint32_t *pM = state + M; - - uint32_t s0 = state[0]; - uint32_t s1 = state[1]; - - // regenerate the lower N-M elements of the state - for (int j = N-M+1; --j != 0; s0 = s1, s1 = *p2++) - *p0++ = *pM++ ^ (mixBits(s0, s1) >> 1) ^ (loBit(s1) ? K : 0U); - - pM = state; - // regenerate the next M-1 elements of the state - // note that s1 is set to state[N] at the end, but discarded - for (int j = M; --j != 0; s0 = s1, s1 = *p2++) - *p0++ = *pM++ ^ (mixBits(s0, s1) >> 1) ^ (loBit(s1) ? K : 0U); - - // regenerate the last 1 element of the state - s1 = state[0]; - *p0 = *pM ^ (mixBits(s0, s1) >> 1) ^ (loBit(s1) ? K : 0U); - - // ready for the normal mt_random algorithm - left = N; - next = state; -} - -uint32_t mt_random(void) -{ - if (--left < 0) - mt_reload(); - - uint32_t y = *next++; - y ^= (y >> 11); - y ^= (y << 7) & 0x9D2C5680U; - y ^= (y << 15) & 0xEFC60000U; - return y ^ (y >> 18); -} diff --git a/src/common/mt_rand.hpp b/src/common/mt_rand.hpp deleted file mode 100644 index ae5986b..0000000 --- a/src/common/mt_rand.hpp +++ /dev/null @@ -1,24 +0,0 @@ -#ifndef MT_RAND_HPP -#define MT_RAND_HPP - -# include "sanity.hpp" - -/// Initialize the generator (called automatically with time() if you don't) -void mt_seed(uint32_t seed); -/// Get a random number -uint32_t mt_random(void); - -/** - * ModuloRand and ModuloPlusRand - * These macros are used to replace the vast number of calls to rand()%mod - * TODO eliminate the rest of the calls to rand() - * MRAND(10) returns 0..9 - * MPRAND(5,10) returns 5..14 - */ -// The cast is essential because the result is sometimes -// compared with a possibly negative number. -// Because it's using modulus, high numbers shouldn't happen anyway. -# define MRAND(mod) ((int)(mt_random() % (mod))) -# define MPRAND(add, mod) ((add) + MRAND(mod)) - -#endif // MT_RAND_HPP diff --git a/src/common/random.cpp b/src/common/random.cpp new file mode 100644 index 0000000..273dcec --- /dev/null +++ b/src/common/random.cpp @@ -0,0 +1,8 @@ +#include "random2.hpp" + +#include "../poison.hpp" + +namespace random_ +{ + std::mt19937 generate{std::random_device()()}; +} // namespace random_ diff --git a/src/common/random.hpp b/src/common/random.hpp new file mode 100644 index 0000000..44057ed --- /dev/null +++ b/src/common/random.hpp @@ -0,0 +1,69 @@ +#ifndef RANDOM_HPP +#define RANDOM_HPP + +# include "random.t.hpp" + +# include "sanity.hpp" + +# include + +// This is not namespace random since that collides with a C function, +// but this can be revisited when everything goes into namespace tmwa. +namespace random_ +{ + /// Get a random number from 0 .. 2**32 - 1 + extern std::mt19937 generate; + + /// Get a random number from 0 .. bound - 1 + inline + int to(int bound) + { + std::uniform_int_distribution dist(0, bound - 1); + return dist(generate); + } + + /// Get a random number from low .. high (inclusive!) + inline + int in(int low, int high) + { + std::uniform_int_distribution dist(low, high); + return dist(generate); + } + + inline + bool coin() + { + // sigh, can't specify directly ... + std::uniform_int_distribution dist(false, true); + return dist(generate); + } + + inline + bool chance(Fraction f) + { + if (f.num <= 0) + return false; + if (f.num >= f.den) + return true; + return random_::to(f.den) < f.num; + } + + // C is usually one of: + // std::vector + // std::initializer_list + // std::array + template + auto choice(C&& c) -> decltype(*c.begin()) + { + return *(c.begin() + random_::to(c.size())); + } + + // allow bare braces + template + T choice(std::initializer_list&& il) + { + return random_::choice(il); + } +} // namespace random_ + +#endif // RANDOM_HPP diff --git a/src/common/random.t.hpp b/src/common/random.t.hpp new file mode 100644 index 0000000..98a6c59 --- /dev/null +++ b/src/common/random.t.hpp @@ -0,0 +1,23 @@ +#ifndef RANDOM_T_HPP +#define RANDOM_T_HPP + +namespace random_ +{ + struct Fraction + { + int num, den; + }; + + template + struct Fixed + { + T num; + + operator Fraction() + { + return {num, den}; + } + }; +} // namespace random_ + +#endif // RANDOM_T_HPP diff --git a/src/common/random2.hpp b/src/common/random2.hpp new file mode 100644 index 0000000..86deddf --- /dev/null +++ b/src/common/random2.hpp @@ -0,0 +1,74 @@ +#ifndef RANDOM2_HPP +#define RANDOM2_HPP + +# include "random.hpp" +# include "utils2.hpp" + +# include + +namespace random_ +{ + namespace detail + { + struct RandomIterator + { + int bound; + int current; + bool frist; + + void operator ++() + { + frist = false; + // TODO: reimplement in terms of LFSRs, so that certain + // blockage patterns don't favor adjacent cells. + current = current + 1; + if (current == bound) + current = 0; + } + int operator *() + { + return current; + } + }; + + inline + bool operator == (RandomIterator l, RandomIterator r) + { + return l.current == r.current && l.frist == r.frist; + } + + inline + bool operator != (RandomIterator l, RandomIterator r) + { + return !(l == r); + } + } + + /// Yield every cell from 0 .. bound - 1 in some order. + /// The starting position is random, but not the order itself. + /// + /// Expected usage: + /// for (int i : random_::iterator(vec.size())) + /// if (vec[i].okay()) + /// return frob(vec[i]); + inline + IteratorPair iterator(int bound) + { + int current = random_::to(bound); + return + { + detail::RandomIterator{bound, current, true}, + detail::RandomIterator{bound, current, false} + }; + } + + /// similar to std::random_shuffle(c.begin(), c.end()), but guaranteed + /// to use a good source of randomness. + template + void shuffle(C&& c) + { + std::random_shuffle(c.begin(), c.end(), random_::to); + } +} // namespace random_ + +#endif // RANDOM2_HPP -- cgit v1.2.3-60-g2f50