1 //===- subzero/src/IceRNG.cpp - PRNG implementation -----------------------===//
2 //
3 // The Subzero Code Generator
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 ///
10 /// \file
11 /// \brief Implements the random number generator.
12 ///
13 //===----------------------------------------------------------------------===//
14
15 #include "IceRNG.h"
16
17 #include <climits>
18 #include <ctime>
19
20 namespace Ice {
21
22 namespace {
23 constexpr unsigned MAX = 2147483647;
24 } // end of anonymous namespace
25
26 // TODO(wala,stichnot): Switch to RNG implementation from LLVM or C++11.
27 //
28 // TODO(wala,stichnot): Make it possible to replay the RNG sequence in a
29 // subsequent run, for reproducing a bug. Print the seed in a comment in the
30 // asm output. Embed the seed in the binary via metadata that an attacker can't
31 // introspect.
RandomNumberGenerator(uint64_t Seed,llvm::StringRef)32 RandomNumberGenerator::RandomNumberGenerator(uint64_t Seed, llvm::StringRef)
33 : State(Seed) {}
34
RandomNumberGenerator(uint64_t Seed,RandomizationPassesEnum RandomizationPassID,uint64_t Salt)35 RandomNumberGenerator::RandomNumberGenerator(
36 uint64_t Seed, RandomizationPassesEnum RandomizationPassID, uint64_t Salt) {
37 constexpr unsigned NumBitsGlobalSeed = CHAR_BIT * sizeof(State);
38 constexpr unsigned NumBitsPassID = 4;
39 constexpr unsigned NumBitsSalt = 12;
40 static_assert(RPE_num < (1 << NumBitsPassID), "NumBitsPassID too small");
41 State = Seed ^ ((uint64_t)RandomizationPassID
42 << (NumBitsGlobalSeed - NumBitsPassID)) ^
43 (Salt << (NumBitsGlobalSeed - NumBitsPassID - NumBitsSalt));
44 }
next(uint64_t Max)45 uint64_t RandomNumberGenerator::next(uint64_t Max) {
46 // Lewis, Goodman, and Miller (1969)
47 State = (16807 * State) % MAX;
48 return State % Max;
49 }
50
getTrueWithProbability(float Probability)51 bool RandomNumberGeneratorWrapper::getTrueWithProbability(float Probability) {
52 return RNG.next(MAX) < Probability * MAX;
53 }
54
55 } // end of namespace Ice
56