/* Copyright (c) 2014-2018 Dovecot authors, see the included COPYING file */

#include "lib.h"

#include "randgen.h"

#if defined(HAVE_ARC4RANDOM) && !defined(FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION)

#ifdef HAVE_LIBBSD

#include <bsd/stdlib.h>

#endif

uint32_t i_rand(void)

{

  return arc4random();

}

uint32_t i_rand_limit(uint32_t upper_bound)

{

  i_assert(upper_bound > 0);

  return arc4random_uniform(upper_bound);

}

#else

uint32_t i_rand(void)

{

  uint32_t value;

  random_fill(&value, sizeof(value));

  return value;

}

/*

 * The following generates a random number in the range [0, upper_bound)

 * with each possible value having equal probability of occurring.

 *

 * This algorithm is not original, but it is dense enough that a detailed

 * explanation is in order.

 *

 * The big problem is that we want a uniformly random values.  If one were

 * to do `i_rand() % upper_bound`, the result probability distribution would

 * depend on the value of the upper bound.  When the upper bound is a power

 * of 2, the distribution is uniform.  If it is not a power of 2, the

 * distribution is skewed.

 *

 * The naive modulo approach breaks down because the division effectively

 * splits the whole range of input values into a number of fixed sized

 * "buckets", but with non-power-of-2 bound the last bucket is not the full

 * size.

 *

 * To fix this bias, we reduce the input range such that the remaining

 * values can be split exactly into equal sized buckets.

 *

 * For example, let's assume that i_rand() produces a uint8_t to simplify

 * the math, and that we want a random number [0, 9] - in other words,

 * upper_bound == 10.

 *

 * `i_rand() % 10` makes buckets 10 numbers wide, but the last bucket is only

 * 6 numbers wide (250..255).  Therefore, 0..5 will occur more frequently

 * than 6..9.

 *

 * If we reduce the input range to [0, 250), the result of the mod 10 will

 * be uniform.  Interestingly, the same can be accomplished if we reduce the

 * input range to [6, 255].

 *

 * This minimum value can be calculated as: 256 % 10 = 6.

 *

 * Or more generically: (UINT32_MAX + 1) % upper_bound.

 *

 * Then, we can pick random numbers until we get one that is >= this

 * minimum.  Once we have it, we can simply mod it by the limit to get our

 * answer.

 *

 * For our example of modding by 10, we pick random numbers until they are

 * greater than or equal to 6.  Once we have one, we have a value in the

 * range [6, 255] which when modded by 10 yields uniformly distributed

 * values [0, 9].

 *

 * There are two things to consider while implementing this algorithm:

 *

 * 1. Division by 0: Getting called with a 0 upper bound doesn't make sense,

 *    therefore we simply assert that the passed in bound is non-zero.

 *

 * 2. 32-bit performance: The above expression to calculate the minimum

 *    value requires 64-bit division.  This generally isn't a problem on

 *    64-bit systems, but 32-bit systems often end up calling a software

 *    implementation (e.g., `__umoddi3`).  This is undesirable.

 *

 *    Therefore, we rewrite the expression as:

 *

 *    ~(upper_bound - 1) % upper_bound

 *

 *    This is harder to understand, but it is 100% equivalent.

 */

uint32_t i_rand_limit(uint32_t upper_bound)

{

  i_assert(upper_bound > 0);

  uint32_t val;

  uint32_t min = UNSIGNED_MINUS(upper_bound) % upper_bound;

  while((val = i_rand()) < min);

  return val % upper_bound;

}

#endif