src/core/random_func.hpp

   1 /*
   2  * This file is part of OpenTTD.
   3  * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
   4  * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
   5  * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
   6  */
   7
   8 /** @file random_func.hpp Pseudo random number generator. */
   9
  10 #ifndef RANDOM_FUNC_HPP
  11 #define RANDOM_FUNC_HPP
  12
  13 /**
  14  * Scale a uint32_t number to be within the range [0,\a limit).
  15  * @param value The value to scale.
  16  * @param limit The limit to scale to.
  17  * @return The scaled value.
  18  */
  19 static constexpr uint32_t ScaleToLimit(uint32_t value, uint32_t limit)
  20 {
  21         return ((uint64_t)value * (uint64_t)limit) >> 32;
  22 }
  23
  24 /**
  25  * Structure to encapsulate the pseudo random number generators.
  26  */
  27 struct Randomizer {
  28         /** The state of the randomizer */
  29         uint32_t state[2];
  30
  31         uint32_t Next();
  32         void SetSeed(uint32_t seed);
  33
  34         /**
  35          * Generate the next pseudo random number scaled to \a limit, excluding \a limit
  36          * itself.
  37          * @param limit Limit of the range to be generated from.
  38          * @return Random number in [0,\a limit)
  39          */
  40         inline uint32_t Next(uint32_t limit) { return ScaleToLimit(this->Next(), limit); }
  41 };
  42 extern Randomizer _random; ///< Random used in the game state calculations
  43 extern Randomizer _interactive_random; ///< Random used everywhere else, where it does not (directly) influence the game state
  44
  45 /** Stores the state of all random number generators */
  46 struct SavedRandomSeeds {
  47         Randomizer random;
  48         Randomizer interactive_random;
  49 };
  50
  51 /**
  52  * Saves the current seeds
  53  * @param storage Storage for saving
  54  */
  55 inline void SaveRandomSeeds(SavedRandomSeeds *storage)
  56 {
  57         storage->random = _random;
  58         storage->interactive_random = _interactive_random;
  59 }
  60
  61 /**
  62  * Restores previously saved seeds
  63  * @param storage Storage where SaveRandomSeeds() stored th seeds
  64  */
  65 inline void RestoreRandomSeeds(const SavedRandomSeeds &storage)
  66 {
  67         _random = storage.random;
  68         _interactive_random = storage.interactive_random;
  69 }
  70
  71 void SetRandomSeed(uint32_t seed);
  72 #ifdef RANDOM_DEBUG
  73         uint32_t Random(const std::source_location location = std::source_location::current());
  74 #else
  75         inline uint32_t Random([[maybe_unused]] const std::source_location location = std::source_location::current())
  76         {
  77                 return _random.Next();
  78         }
  79 #endif
  80
  81 /**
  82  * Pick a random number between 0 and \a limit - 1, inclusive. That means 0
  83  * can be returned and \a limit - 1 can be returned, but \a limit can not be
  84  * returned.
  85  * @param limit Limit for the range to be picked from.
  86  * @return A random number in [0,\a limit).
  87  */
  88 inline uint32_t RandomRange(uint32_t limit, const std::source_location location = std::source_location::current())
  89 {
  90         return ScaleToLimit(Random(location), limit);
  91 }
  92
  93 inline uint32_t InteractiveRandom()
  94 {
  95         return _interactive_random.Next();
  96 }
  97
  98 inline uint32_t InteractiveRandomRange(uint32_t limit)
  99 {
 100         return _interactive_random.Next(limit);
 101 }
 102
 103 /**
 104  * Checks if a given randomize-number is below a given probability.
 105  *
 106  * This function is used to check if the given probability by the fraction of (a/b)
 107  * is greater than low 16 bits of the given randomize-number r.
 108  *
 109  * Do not use this function twice on the same random 16 bits as it will yield
 110  * the same result. One can use a random number for two calls to Chance16I,
 111  * where one call sends the low 16 bits and the other the high 16 bits.
 112  *
 113  * @param a The numerator of the fraction
 114  * @param b The denominator of the fraction, must of course not be null
 115  * @param r The given randomize-number
 116  * @return True if the probability given by r is less or equal to (a/b)
 117  */
 118 inline bool Chance16I(const uint32_t a, const uint32_t b, const uint32_t r)
 119 {
 120         assert(b != 0);
 121         return (((uint16_t)r * b + b / 2) >> 16) < a;
 122 }
 123
 124 /**
 125  * Flips a coin with given probability.
 126  *
 127  * This function returns true with (a/b) probability.
 128  *
 129  * @see Chance16I()
 130  * @param a The nominator of the fraction
 131  * @param b The denominator of the fraction
 132  * @return True with (a/b) probability
 133  */
 134 inline bool Chance16(const uint32_t a, const uint32_t b, const std::source_location location = std::source_location::current())
 135 {
 136         return Chance16I(a, b, Random(location));
 137 }
 138
 139 /**
 140  * Flips a coin with a given probability and saves the randomize-number in a variable.
 141  *
 142  * This function uses the same parameters as Chance16. The third parameter
 143  * must be a variable the randomize-number from Random() is saved in.
 144  *
 145  * The low 16 bits of r will already be used and can therefore not be passed to
 146  * Chance16I. One can only send the high 16 bits to Chance16I.
 147  *
 148  * @see Chance16I()
 149  * @param a The numerator of the fraction
 150  * @param b The denominator of the fraction
 151  * @param r The variable to save the randomize-number from Random()
 152  * @return True in (a/b) percent
 153  */
 154 inline bool Chance16R(const uint32_t a, const uint32_t b, uint32_t &r, const std::source_location location = std::source_location::current())
 155 {
 156         r = Random(location);
 157         return Chance16I(a, b, r);
 158 }
 159
 160 void RandomBytesWithFallback(std::span<uint8_t> buf);
 161
 162 #endif /* RANDOM_FUNC_HPP */