1 | // Copyright (c) 2011 The LevelDB Authors. All rights reserved. |
2 | // Use of this source code is governed by a BSD-style license that can be |
3 | // found in the LICENSE file. See the AUTHORS file for names of contributors. |
4 | |
5 | #ifndef STORAGE_LEVELDB_UTIL_RANDOM_H_ |
6 | #define STORAGE_LEVELDB_UTIL_RANDOM_H_ |
7 | |
8 | #include <cstdint> |
9 | |
10 | namespace leveldb { |
11 | |
12 | // A very simple random number generator. Not especially good at |
13 | // generating truly random bits, but good enough for our needs in this |
14 | // package. |
15 | class Random { |
16 | private: |
17 | uint32_t seed_; |
18 | |
19 | public: |
20 | explicit Random(uint32_t s) : seed_(s & 0x7fffffffu) { |
21 | // Avoid bad seeds. |
22 | if (seed_ == 0 || seed_ == 2147483647L) { |
23 | seed_ = 1; |
24 | } |
25 | } |
26 | uint32_t Next() { |
27 | static const uint32_t M = 2147483647L; // 2^31-1 |
28 | static const uint64_t A = 16807; // bits 14, 8, 7, 5, 2, 1, 0 |
29 | // We are computing |
30 | // seed_ = (seed_ * A) % M, where M = 2^31-1 |
31 | // |
32 | // seed_ must not be zero or M, or else all subsequent computed values |
33 | // will be zero or M respectively. For all other values, seed_ will end |
34 | // up cycling through every number in [1,M-1] |
35 | uint64_t product = seed_ * A; |
36 | |
37 | // Compute (product % M) using the fact that ((x << 31) % M) == x. |
38 | seed_ = static_cast<uint32_t>((product >> 31) + (product & M)); |
39 | // The first reduction may overflow by 1 bit, so we may need to |
40 | // repeat. mod == M is not possible; using > allows the faster |
41 | // sign-bit-based test. |
42 | if (seed_ > M) { |
43 | seed_ -= M; |
44 | } |
45 | return seed_; |
46 | } |
47 | // Returns a uniformly distributed value in the range [0..n-1] |
48 | // REQUIRES: n > 0 |
49 | uint32_t Uniform(int n) { return Next() % n; } |
50 | |
51 | // Randomly returns true ~"1/n" of the time, and false otherwise. |
52 | // REQUIRES: n > 0 |
53 | bool OneIn(int n) { return (Next() % n) == 0; } |
54 | |
55 | // Skewed: pick "base" uniformly from range [0,max_log] and then |
56 | // return "base" random bits. The effect is to pick a number in the |
57 | // range [0,2^max_log-1] with exponential bias towards smaller numbers. |
58 | uint32_t Skewed(int max_log) { return Uniform(1 << Uniform(max_log + 1)); } |
59 | }; |
60 | |
61 | } // namespace leveldb |
62 | |
63 | #endif // STORAGE_LEVELDB_UTIL_RANDOM_H_ |
64 | |