diff options
Diffstat (limited to 'src/bin/perfdhcp/random_number_generator.h')
-rw-r--r-- | src/bin/perfdhcp/random_number_generator.h | 202 |
1 files changed, 202 insertions, 0 deletions
diff --git a/src/bin/perfdhcp/random_number_generator.h b/src/bin/perfdhcp/random_number_generator.h new file mode 100644 index 0000000..ce5a386 --- /dev/null +++ b/src/bin/perfdhcp/random_number_generator.h @@ -0,0 +1,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 |