Ian Hodson | 2ee91b4 | 2012-05-14 12:29:36 +0100 | [diff] [blame] | 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 | |
| 11 | int32 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 | |
| 30 | int32 ACMRandom::Uniform(int32 n) { |
| 31 | return Next() % n; |
| 32 | } |
| 33 | |
| 34 | } // namespace re2 |