12ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// Copyright 2005-2009 The RE2 Authors. All Rights Reserved. 22ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// Use of this source code is governed by a BSD-style 32ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// license that can be found in the LICENSE file. 42ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 52ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// Modified from Google perftools's tcmalloc_unittest.cc. 62ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 72ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson#include "util/random.h" 82ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 92ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodsonnamespace re2 { 102ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 112ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodsonint32 ACMRandom::Next() { 122ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson const int32 M = 2147483647L; // 2^31-1 132ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson const int32 A = 16807; 142ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson // In effect, we are computing seed_ = (seed_ * A) % M, where M = 2^31-1 152ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson uint32 lo = A * (int32)(seed_ & 0xFFFF); 162ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson uint32 hi = A * (int32)((uint32)seed_ >> 16); 172ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson lo += (hi & 0x7FFF) << 16; 182ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson if (lo > M) { 192ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson lo &= M; 202ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson ++lo; 212ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson } 222ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson lo += hi >> 15; 232ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson if (lo > M) { 242ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson lo &= M; 252ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson ++lo; 262ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson } 272ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson return (seed_ = (int32) lo); 282ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson} 292ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 302ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodsonint32 ACMRandom::Uniform(int32 n) { 312ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson return Next() % n; 322ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson} 332ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 342ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson} // namespace re2 35