Replace mt_rand with <random>

Also add some utility methods and classes.

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