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. 32 RandomNumberGenerator::RandomNumberGenerator(uint64_t Seed, llvm::StringRef) 33 : State(Seed) {} 34 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 } 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 51 bool RandomNumberGeneratorWrapper::getTrueWithProbability(float Probability) { 52 return RNG.next(MAX) < Probability * MAX; 53 } 54 55 } // end of namespace Ice 56
