15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright 2005-2009 The RE2 Authors. All Rights Reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// license that can be found in the LICENSE file. 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Modified from Google perftools's tcmalloc_unittest.cc. 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "util/random.h" 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace re2 { 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)int32 ACMRandom::Next() { 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int32 M = 2147483647L; // 2^31-1 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int32 A = 16807; 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // In effect, we are computing seed_ = (seed_ * A) % M, where M = 2^31-1 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32 lo = A * (int32)(seed_ & 0xFFFF); 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32 hi = A * (int32)((uint32)seed_ >> 16); 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) lo += (hi & 0x7FFF) << 16; 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (lo > M) { 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) lo &= M; 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++lo; 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) lo += hi >> 15; 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (lo > M) { 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) lo &= M; 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++lo; 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return (seed_ = (int32) lo); 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)int32 ACMRandom::Uniform(int32 n) { 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Next() % n; 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace re2 35