| // Copyright 2005-2009 The RE2 Authors. All Rights Reserved. |
| // Use of this source code is governed by a BSD-style |
| // license that can be found in the LICENSE file. |
| |
| // Modified from Google perftools's tcmalloc_unittest.cc. |
| |
| #include "util/random.h" |
| |
| namespace re2 { |
| |
| int32 ACMRandom::Next() { |
| const int32 M = 2147483647L; // 2^31-1 |
| const int32 A = 16807; |
| // In effect, we are computing seed_ = (seed_ * A) % M, where M = 2^31-1 |
| uint32 lo = A * (int32)(seed_ & 0xFFFF); |
| uint32 hi = A * (int32)((uint32)seed_ >> 16); |
| lo += (hi & 0x7FFF) << 16; |
| if (lo > M) { |
| lo &= M; |
| ++lo; |
| } |
| lo += hi >> 15; |
| if (lo > M) { |
| lo &= M; |
| ++lo; |
| } |
| return (seed_ = (int32) lo); |
| } |
| |
| int32 ACMRandom::Uniform(int32 n) { |
| return Next() % n; |
| } |
| |
| } // namespace re2 |
