summaryrefslogtreecommitdiff
path: root/src/common
diff options
context:
space:
mode:
Diffstat (limited to 'src/common')
-rw-r--r--src/common/core.cpp5
-rw-r--r--src/common/md5calc.cpp7
-rw-r--r--src/common/mt_rand.cpp123
-rw-r--r--src/common/mt_rand.hpp24
-rw-r--r--src/common/random.cpp8
-rw-r--r--src/common/random.hpp69
-rw-r--r--src/common/random.t.hpp23
-rw-r--r--src/common/random2.hpp74
8 files changed, 179 insertions, 154 deletions
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 <cstdlib>
#include <ctime>
-#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 <cstring>
-#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 <http://www.math.keio.ac.jp/~matumoto/emt.html>
-// (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 <matumoto@math.keio.ac.jp> with
-// an appropriate reference to your work.
-//
-// It would be nice to CC: <Cokus@math.washington.edu> when you write.
-//
-*/
-
-#include "mt_rand.hpp"
-
-#include <ctime>
-
-#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 <random>
+
+// 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<int> 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<int> dist(low, high);
+ return dist(generate);
+ }
+
+ inline
+ bool coin()
+ {
+ // sigh, can't specify <bool> directly ...
+ std::uniform_int_distribution<int> 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<T>
+ // std::initializer_list<T>
+ // std::array<T, n>
+ template<class C>
+ auto choice(C&& c) -> decltype(*c.begin())
+ {
+ return *(c.begin() + random_::to(c.size()));
+ }
+
+ // allow bare braces
+ template<class T>
+ T choice(std::initializer_list<T>&& 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<class T, T den>
+ 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 <algorithm>
+
+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<detail::RandomIterator> 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<class C>
+ void shuffle(C&& c)
+ {
+ std::random_shuffle(c.begin(), c.end(), random_::to);
+ }
+} // namespace random_
+
+#endif // RANDOM2_HPP
generated by cgit v1.2.3-60-g2f50 (git 2.42.0) at 2024-07-07 12:54:54 +0000