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
9namespace re2 {
10
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
30int32 ACMRandom::Uniform(int32 n) {
31  return Next() % n;
32}
33
34}  // namespace re2
35