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