Add uniform distribution to RNG

[rinon]

Summary

A cross-platform stable RNG with a uniform distribution in a given range is needed by D6983. std::uniform_int_distribution is unfortunately not identical across libraries, so we need our own.

[rinon]

@joerg suggested an alternative implementation: http://www.netbsd.org/~joerg/uniform-rng.diff

[jfb]

We can go with @joerg's proposal, but we would need a unit test for this IMO.

[jfb]

Is there interest in moving program diversification efforts forward, or should we close this work and rely on others to take it on?

[rinon]

Is there anyone using the RNG infrastructure downstream? If we close the other compile-time diversity patchsets, it might make sense to remove the RNG interface until such time as it is needed again.

[jfb]

In D7745#1093586, @rinon wrote:

Is there anyone using the RNG infrastructure downstream? If we close the other compile-time diversity patchsets, it might make sense to remove the RNG interface until such time as it is needed again.

Agreed.

include/llvm/Support/RandomNumberGenerator.h

 /// A random number generator.
 ///
 /// Instances of this class should not be shared across threads. The
 /// seed should be set by passing the -rng-seed=<uint64> option. Use
 /// Module::createRNG to create a new RNG instance for use with that
 /// module.
 class RandomNumberGenerator {
 public:
-  /// Returns a random number in the range [0, Max).
-  uint_fast64_t operator()();
+  typedef std::mt19937_64 RNG;
+  typedef RNG::result_type result_type;
+
+  /// Returns a random number in the range [0, RNG::max()).
+  result_type operator()();
+
+  /// Returns an unbiased random number in the range [0, Max). Max
+  /// must be <= RNG::max().
+  result_type operator()(result_type Max);
+
+  // Must define min and max to be compatible with URNG as used by
+  // std::uniform_*_distribution
+  static LLVM_CONSTEXPR result_type min() {
+    return RNG::min();
+  }
+  static LLVM_CONSTEXPR result_type max() {
+    return RNG::max();
+  }
 
 private:
   /// Seeds and salts the underlying RNG engine.
   ///
   /// This constructor should not be used directly. Instead use
   /// Module::createRNG to create a new RNG salted with the Module ID.
   RandomNumberGenerator(StringRef Salt);
 
   // 64-bit Mersenne Twister by Matsumoto and Nishimura, 2000
   // http://en.cppreference.com/w/cpp/numeric/random/mersenne_twister_engine
   // This RNG is deterministically portable across C++11
   // implementations.
-  std::mt19937_64 Generator;
+  RNG Generator;
 
   // Noncopyable.
   RandomNumberGenerator(const RandomNumberGenerator &other)
       LLVM_DELETED_FUNCTION;
   RandomNumberGenerator &
   operator=(const RandomNumberGenerator &other) LLVM_DELETED_FUNCTION;
 
   friend class Module;
 };
 }
 
 #endif

lib/Support/RandomNumberGenerator.cpp

 #include "llvm/Support/Debug.h"
 #include "llvm/Support/RandomNumberGenerator.h"
 
 using namespace llvm;
 
 // Tracking BUG: 19665
 // http://llvm.org/bugs/show_bug.cgi?id=19665
 //
-// Do not change to cl::opt<uint64_t> since this silently breaks argument parsing.
+// Do not change to cl::opt<uint64_t> since this silently breaks argument
+// parsing.
 static cl::opt<unsigned long long>
     Seed("rng-seed", cl::value_desc("seed"),
          cl::desc("Seed for the random number generator"), cl::init(0));
 
 RandomNumberGenerator::RandomNumberGenerator(StringRef Salt) {
-  DEBUG(
-    if (Seed == 0)
-      dbgs() << "Warning! Using unseeded random number generator.\n"
-  );
+  DEBUG(if (Seed == 0) dbgs()
+        << "Warning! Using unseeded random number generator.\n");
 
   // Combine seed and salts using std::seed_seq.
   // Data: Seed-low, Seed-high, Salt
   // Note: std::seed_seq can only store 32-bit values, even though we
   // are using a 64-bit RNG. This isn't a problem since the Mersenne
   // twister constructor copies these correctly into its initial state.
   std::vector<uint32_t> Data;
   Data.reserve(2 + Salt.size());
   Data.push_back(Seed);
   Data.push_back(Seed >> 32);
 
   std::copy(Salt.begin(), Salt.end(), Data.end());
 
   std::seed_seq SeedSeq(Data.begin(), Data.end());
   Generator.seed(SeedSeq);
 }
 
-uint_fast64_t RandomNumberGenerator::operator()() {
+RandomNumberGenerator::result_type RandomNumberGenerator::operator()() {
   return Generator();
 }
+
+// This function is derived from OpenBSD's libc, original license
+// follows:
+//
+// Copyright (c) 2008, Damien Miller <[e-mail]>
+//
+// Permission to use, copy, modify, and distribute this software for any
+// purpose with or without fee is hereby granted, provided that the above
+// copyright notice and this permission notice appear in all copies.
+//
+// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+// WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+// MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+// ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+// WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+// ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+// OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+
+// Calculate a uniformly distributed random number less than upper_bound
+// avoiding "modulo bias".
+//
+// Uniformity is achieved by generating new random numbers until the one
+// returned is outside the range [0, 2**32 % upper_bound).  This
+// guarantees the selected random number will be inside
+// [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
+// after reduction modulo upper_bound.
+RandomNumberGenerator::result_type
+RandomNumberGenerator::operator()(result_type upper_bound) {
+  result_type r, min;
+
+  if (upper_bound < 2)
+    return 0;
+
+  /* 2**32 % x == (2**32 - x) % x */
+  min = -upper_bound % upper_bound;
+
+  /*
+   * This could theoretically loop forever but each retry has
+   * p > 0.5 (worst case, usually far better) of selecting a
+   * number inside the range we need, so it should rarely need
+   * to re-roll.
+   */
+  for (;;) {
+    r = Generator();
+    if (r >= min)
+      break;
+  }
+
+  return r % upper_bound;
+}