1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
|
// Copyright (C) 2010-2021 Internet Systems Consortium, Inc. ("ISC")
//
// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at http://mozilla.org/MPL/2.0/.
#ifndef NSAS_RANDOM_NUMBER_GENERATOR_H
#define NSAS_RANDOM_NUMBER_GENERATOR_H
#include <algorithm>
#include <cmath>
#include <iterator>
#include <numeric>
#include <vector>
#include <exceptions/exceptions.h>
#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_int.hpp>
#include <boost/random/uniform_real.hpp>
#include <boost/random/variate_generator.hpp>
/// PLEASE DO NOT USE THIS IN CRYPTOGRAPHICALLY SENSITIVE CODE.
namespace isc {
namespace perfdhcp {
class InvalidLimits : public isc::BadValue {
public:
InvalidLimits(const char* file, size_t line, const char* what) :
isc::BadValue(file, line, what) {}
};
class SumNotOne : public isc::BadValue {
public:
SumNotOne(const char* file, size_t line, const char* what) :
isc::BadValue(file, line, what) {}
};
class InvalidProbValue : public isc::BadValue {
public:
InvalidProbValue(const char* file, size_t line, const char* what) :
isc::BadValue(file, line, what) {}
};
/// \brief Uniform random integer generator
///
/// Generate uniformly distributed integers in range of [min, max]
class UniformRandomIntegerGenerator{
public:
/// \brief Constructor
///
/// \param min The minimum number in the range
/// \param max The maximum number in the range
UniformRandomIntegerGenerator(int min, int max):
min_(std::min(min, max)), max_(std::max(min, max)),
dist_(min_, max_), generator_(rng_, dist_)
{
// To preserve the restriction of the underlying uniform_int class (and
// to retain compatibility with earlier versions of the class), we will
// abort if the minimum and maximum given are the wrong way round.
if (min > max) {
isc_throw(InvalidLimits, "minimum limit is greater than maximum "
"when initializing UniformRandomIntegerGenerator");
}
// Init with the current time
rng_.seed(time(NULL));
}
/// \brief Generate uniformly distributed integer
int operator()() { return generator_(); }
private:
/// Hide default and copy constructor
UniformRandomIntegerGenerator();///< Default constructor
UniformRandomIntegerGenerator(const UniformRandomIntegerGenerator&); ///< Copy constructor
int min_; ///< The minimum integer that can generate
int max_; ///< The maximum integer that can generate
boost::uniform_int<> dist_; ///< Distribute uniformly.
boost::mt19937 rng_; ///< Mersenne Twister: A 623-dimensionally equidistributed uniform pseudo-random number generator
boost::variate_generator<boost::mt19937&, boost::uniform_int<> > generator_; ///< Uniform generator
};
/// \brief Weighted random integer generator
///
/// Generate random integers according different probabilities
class WeightedRandomIntegerGenerator {
public:
/// \brief Constructor
///
/// \param probabilities The probabilities for all the integers, the probability must be
/// between 0 and 1.0, the sum of probabilities must be equal to 1.
/// For example, if the probabilities contains the following values:
/// 0.5 0.3 0.2, the 1st integer will be generated more frequently than the
/// other integers and the probability is proportional to its value.
/// \param min The minimum integer that generated, other integers will be
/// min, min + 1, ..., min + probabilities.size() - 1
WeightedRandomIntegerGenerator(const std::vector<double>& probabilities,
size_t min = 0):
dist_(0, 1.0), uniform_real_gen_(rng_, dist_), min_(min)
{
// The probabilities must be valid. Checking is quite an expensive
// operation, so is only done in a debug build.
areProbabilitiesValid(probabilities);
// Calculate the partial sum of probabilities
std::partial_sum(probabilities.begin(), probabilities.end(),
std::back_inserter(cumulative_));
// Init with the current time
rng_.seed(time(NULL));
}
/// \brief Default constructor
///
WeightedRandomIntegerGenerator():
dist_(0, 1.0), uniform_real_gen_(rng_, dist_), min_(0)
{
}
/// \brief Reset the probabilities
///
/// Change the weights of each integers
/// \param probabilities The probabilities for all the integers
/// \param min The minimum integer that generated
void reset(const std::vector<double>& probabilities, size_t min = 0)
{
// The probabilities must be valid.
areProbabilitiesValid(probabilities);
// Reset the cumulative sum
cumulative_.clear();
// Calculate the partial sum of probabilities
std::partial_sum(probabilities.begin(), probabilities.end(),
std::back_inserter(cumulative_));
// Reset the minimum integer
min_ = min;
}
/// \brief Generate weighted random integer
size_t operator()()
{
return std::lower_bound(cumulative_.begin(), cumulative_.end(), uniform_real_gen_())
- cumulative_.begin() + min_;
}
private:
/// \brief Check the validation of probabilities vector
///
/// The probability must be in range of [0, 1.0] and the sum must be equal
/// to 1.0. Empty probabilities are also valid.
///
/// Checking the probabilities is quite an expensive operation, so it is
/// only done during a debug build (via a call through assert()). However,
/// instead of letting assert() call abort(), if this method encounters an
/// error, an exception is thrown. This makes unit testing somewhat easier.
///
/// \param probabilities Vector of probabilities.
/// \throw InvalidProbValue or SumNotOne when not valid.
void areProbabilitiesValid(const std::vector<double>& probabilities) const
{
double sum = probabilities.empty() ? 1.0 : 0.0;
for (const double it : probabilities) {
//The probability must be in [0, 1.0]
if (it < 0.0 || it > 1.0) {
isc_throw(InvalidProbValue,
"probability must be in the range 0..1");
}
sum += it;
}
double epsilon = 0.0001;
// The sum must be equal to 1
if (std::fabs(sum - 1.0) >= epsilon) {
isc_throw(SumNotOne, "Sum of probabilities is not equal to 1");
}
return;
}
std::vector<double> cumulative_; ///< Partial sum of the probabilities
boost::mt19937 rng_; ///< Mersenne Twister: A 623-dimensionally equidistributed uniform pseudo-random number generator
boost::uniform_real<> dist_; ///< Uniformly distributed real numbers
// Shortcut typedef
// This typedef is placed directly before its use, as the sunstudio
// compiler could not handle it being anywhere else (don't know why)
typedef boost::variate_generator<boost::mt19937&, boost::uniform_real<> > UniformRealGenerator;
UniformRealGenerator uniform_real_gen_; ///< Uniformly distributed random real numbers generator
size_t min_; ///< The minimum integer that will be generated
};
} // namespace perfdhcp
} // namespace isc
#endif//NSAS_RANDOM_NUMBER_GENERATOR_H
|
