third_party/re2/util/random.cc

   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