1 // Copyright 2005-2009 The RE2 Authors. All Rights Reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 // Modified from Google perftools's tcmalloc_unittest.cc. 6 7 #include "util/random.h" 8 9 namespace re2 { 10 Next()11int32 ACMRandom::Next() { 12 const int32 M = 2147483647L; // 2^31-1 13 const int32 A = 16807; 14 // In effect, we are computing seed_ = (seed_ * A) % M, where M = 2^31-1 15 uint32 lo = A * (int32)(seed_ & 0xFFFF); 16 uint32 hi = A * (int32)((uint32)seed_ >> 16); 17 lo += (hi & 0x7FFF) << 16; 18 if (lo > M) { 19 lo &= M; 20 ++lo; 21 } 22 lo += hi >> 15; 23 if (lo > M) { 24 lo &= M; 25 ++lo; 26 } 27 return (seed_ = (int32) lo); 28 } 29 Uniform(int32 n)30int32 ACMRandom::Uniform(int32 n) { 31 return Next() % n; 32 } 33 34 } // namespace re2 35