2 files changed, 111 insertions, 0 deletions

diff --git a/crawl-ref/source/random.cc b/crawl-ref/source/random.cc
index 0ea2d12a59..a6b37de287 100644
--- a/crawl-ref/source/random.cc
+++ b/crawl-ref/source/random.cc
@@ -261,3 +261,79 @@ int fuzz_value(int val, int lowfuzz, int highfuzz, int naverage)
         hfuzz = highfuzz * val / 100;
     return val + random2avg(lfuzz + hfuzz + 1, naverage) - lfuzz;
 }
+
+// This is used when the front-end randomness is inconclusive.  There are
+// never more than two possibilities, which simplifies things.
+bool defer_rand::x_chance_in_y_contd(int x, int y, int index)
+{
+    if (x <= 0)
+        return (false);
+
+    if (x >= y)
+        return (true);
+
+    do
+    {
+        if (index == int(bits.size()))
+            bits.push_back(random_int());
+
+        uint64_t expn_rand_1 = uint64_t(bits[index++]) * y;
+        uint64_t expn_rand_2 = expn_rand_1 + y;
+        uint64_t expn_minimum_fail = uint64_t(x) << 32;
+
+        if (expn_minimum_fail <= expn_rand_1)
+            return (false);
+
+        if (expn_rand_2 <= expn_minimum_fail)
+            return (true);
+
+        // y = expn_rand_2 - expn_rand_1;  no-op
+        x = expn_minimum_fail - expn_rand_1;
+    } while(1);
+}
+
+int defer_rand::random2(int maxp1)
+{
+    if (maxp1 <= 1)
+        return (0);
+
+    if (bits.empty())
+        bits.push_back(random_int());
+
+    uint64_t expn_rand_1 = uint64_t(bits[0]) * maxp1;
+    uint64_t expn_rand_2 = expn_rand_1 + maxp1;
+
+    int val1 = int(expn_rand_1 >> 32);
+    int val2 = int(expn_rand_2 >> 32);
+
+    if (val2 == val1)
+        return (val1);
+
+    // val2 == val1 + 1
+    uint64_t expn_thresh = uint64_t(val2) << 32;
+
+    return x_chance_in_y_contd(int(expn_thresh - expn_rand_1),
+                               maxp1, 1)
+         ? val1 : val2;
+}
+
+defer_rand& defer_rand::operator[](int i)
+{
+    return children[i];
+}
+
+int defer_rand::random_range(int low, int high)
+{
+    ASSERT(low <= high);
+    return (low + random2(high - low + 1));
+}
+
+int defer_rand::random2avg(int max, int rolls)
+{
+    int sum = random2(max);
+
+    for (int i = 0; i < (rolls - 1); i++)
+        sum += random2(max + 1);
+
+    return (sum / rolls);
+}
diff --git a/crawl-ref/source/random.h b/crawl-ref/source/random.h
index b1bdbe5021..b4d48639c9 100644
--- a/crawl-ref/source/random.h
+++ b/crawl-ref/source/random.h
@@ -3,6 +3,9 @@
 
 #include "rng.h"
 
+#include <map>
+#include <vector>
+
 bool coinflip();
 int div_rand_round( int num, int den );
 int div_round_up( int num, int den );
@@ -42,6 +45,38 @@ public:
     ~rng_save_excursion()         { pop_rng_state(); }
 };
 
+// A defer_rand object represents an infinite tree of random values, allowing
+// for a much more functional approach to randomness.  defer_rand values which
+// have been used should not be copy-constructed.  Querying the same path
+// multiple times will always give the same result.
+
+// An important property of defer_rand is that, except for rounding,
+// float(r.random2(X)) / X == float(r.random2(Y)) / Y for all X and Y.  In
+// other words:
+//
+// * The parameter you use on any given call does not matter.
+// * The object stores the fraction, not a specific integer.
+// * random2() is monotonic in its argument.
+class defer_rand
+{
+    std::vector<unsigned long> bits;
+    std::map<int, defer_rand> children;
+
+    bool x_chance_in_y_contd(int x, int y, int index);
+public:
+    // TODO It would probably be a good idea to have some sort of random
+    // number generator API, and the ability to pass RNGs into any function
+    // that wants them.
+    bool x_chance_in_y(int x, int y) { return x_chance_in_y_contd(x,y,0); }
+    bool one_chance_in(int a_million) { return x_chance_in_y(1,a_million); }
+    int random2(int maxp1);
+
+    int random_range(int low, int high);
+    int random2avg(int max, int rolls);
+
+    defer_rand& operator[] (int i);
+};
+
 template<typename Iterator>
 int choose_random_weighted(Iterator beg, const Iterator end)
 {