src/lib/crypt_ops/crypto_rand_numeric.c

   1 /**
   2  * \file crypto_rand_numeric.c
   3  *
   4  * \brief Functions for retrieving uniformly distributed numbers
   5  *   from our PRNGs.
   6  **/
   7
   8 #include "lib/crypt_ops/crypto_rand.h"
   9 #include "lib/log/util_bug.h"
  10
  11 /**
  12  * Implementation macro: yields code that returns a uniform unbiased
  13  * random number between 0 and limit.  "type" is the type of the number to
  14  * return; "maxval" is the largest possible value of "type"; and "fill_stmt"
  15  * is a code snippet that fills an object named "val" with random bits.
  16  **/
  17 #define IMPLEMENT_RAND_UNSIGNED(type, maxval, limit, fill_stmt)         \
  18   do {                                                                  \
  19     type val;                                                           \
  20     type cutoff;                                                        \
  21     tor_assert((limit) > 0);                                            \
  22                                                                         \
  23     /* We ignore any values that are >= 'cutoff,' to avoid biasing */   \
  24     /* the distribution with clipping at the upper end of the type's */ \
  25     /* range. */                                                        \
  26     cutoff = (maxval) - ((maxval)%(limit));                             \
  27     while (1) {                                                         \
  28       fill_stmt;                                                        \
  29       if (val < cutoff)                                                 \
  30         return val % (limit);                                           \
  31     }                                                                   \
  32   } while (0)
  33
  34 /**
  35  * Return a pseudorandom integer chosen uniformly from the values between 0
  36  * and <b>limit</b>-1 inclusive. limit must be strictly greater than 0, and
  37  * less than UINT_MAX. */
  38 unsigned
  39 crypto_rand_uint(unsigned limit)
  40 {
  41   tor_assert(limit < UINT_MAX);
  42   IMPLEMENT_RAND_UNSIGNED(unsigned, UINT_MAX, limit,
  43                           crypto_rand((char*)&val, sizeof(val)));
  44 }
  45
  46 /**
  47  * Return a pseudorandom integer, chosen uniformly from the values
  48  * between 0 and <b>max</b>-1 inclusive.  <b>max</b> must be between 1 and
  49  * INT_MAX+1, inclusive.
  50  */
  51 int
  52 crypto_rand_int(unsigned int max)
  53 {
  54   /* We can't use IMPLEMENT_RAND_UNSIGNED directly, since we're trying
  55    * to return a signed type. Instead we make sure that the range is
  56    * reasonable for a nonnegative int, use crypto_rand_uint(), and cast.
  57    */
  58   tor_assert(max <= ((unsigned int)INT_MAX)+1);
  59
  60   return (int)crypto_rand_uint(max);
  61 }
  62
  63 /**
  64  * Return a pseudorandom integer, chosen uniformly from the values i such
  65  * that min <= i < max.
  66  *
  67  * <b>min</b> MUST be in range [0, <b>max</b>).
  68  * <b>max</b> MUST be in range (min, INT_MAX].
  69  **/
  70 int
  71 crypto_rand_int_range(unsigned int min, unsigned int max)
  72 {
  73   tor_assert(min < max);
  74   tor_assert(max <= INT_MAX);
  75
  76   /* The overflow is avoided here because crypto_rand_int() returns a value
  77    * between 0 and (max - min) inclusive. */
  78   return min + crypto_rand_int(max - min);
  79 }
  80
  81 /**
  82  * As crypto_rand_int_range, but supports uint64_t.
  83  **/
  84 uint64_t
  85 crypto_rand_uint64_range(uint64_t min, uint64_t max)
  86 {
  87   tor_assert(min < max);
  88   return min + crypto_rand_uint64(max - min);
  89 }
  90
  91 /**
  92  * As crypto_rand_int_range, but supports time_t.
  93  **/
  94 time_t
  95 crypto_rand_time_range(time_t min, time_t max)
  96 {
  97   tor_assert(min < max);
  98   return min + (time_t)crypto_rand_uint64(max - min);
  99 }
 100
 101 /**
 102  * Return a pseudorandom 64-bit integer, chosen uniformly from the values
 103  * between 0 and <b>max</b>-1 inclusive.
 104  **/
 105 uint64_t
 106 crypto_rand_uint64(uint64_t max)
 107 {
 108   tor_assert(max < UINT64_MAX);
 109   IMPLEMENT_RAND_UNSIGNED(uint64_t, UINT64_MAX, max,
 110                           crypto_rand((char*)&val, sizeof(val)));
 111 }
 112
 113 #if SIZEOF_INT == 4
 114 #define UINT_MAX_AS_DOUBLE 4294967296.0
 115 #elif SIZEOF_INT == 8
 116 #define UINT_MAX_AS_DOUBLE 1.8446744073709552e+19
 117 #else
 118 #error SIZEOF_INT is neither 4 nor 8
 119 #endif /* SIZEOF_INT == 4 || ... */
 120
 121 /**
 122  * Return a pseudorandom double d, chosen uniformly from the range
 123  * 0.0 <= d < 1.0.
 124  **/
 125 double
 126 crypto_rand_double(void)
 127 {
 128   /* We just use an unsigned int here; we don't really care about getting
 129    * more than 32 bits of resolution */
 130   unsigned int u;
 131   crypto_rand((char*)&u, sizeof(u));
 132   return ((double)u) / UINT_MAX_AS_DOUBLE;
 133 }
 134
 135 /**
 136  * As crypto_rand_uint, but extract the result from a crypto_fast_rng_t
 137  */
 138 unsigned
 139 crypto_fast_rng_get_uint(crypto_fast_rng_t *rng, unsigned limit)
 140 {
 141   tor_assert(limit < UINT_MAX);
 142   IMPLEMENT_RAND_UNSIGNED(unsigned, UINT_MAX, limit,
 143                   crypto_fast_rng_getbytes(rng, (void*)&val, sizeof(val)));
 144 }
 145
 146 /**
 147  * As crypto_rand_uint64, but extract the result from a crypto_fast_rng_t.
 148  */
 149 uint64_t
 150 crypto_fast_rng_get_uint64(crypto_fast_rng_t *rng, uint64_t limit)
 151 {
 152   tor_assert(limit < UINT64_MAX);
 153   IMPLEMENT_RAND_UNSIGNED(uint64_t, UINT64_MAX, limit,
 154                   crypto_fast_rng_getbytes(rng, (void*)&val, sizeof(val)));
 155 }
 156
 157 /**
 158  * As crypto_rand_u32, but extract the result from a crypto_fast_rng_t.
 159  */
 160 uint32_t
 161 crypto_fast_rng_get_u32(crypto_fast_rng_t *rng)
 162 {
 163   uint32_t val;
 164   crypto_fast_rng_getbytes(rng, (void*)&val, sizeof(val));
 165   return val;
 166 }
 167
 168 /**
 169  * As crypto_rand_uint64_range(), but extract the result from a
 170  * crypto_fast_rng_t.
 171  */
 172 uint64_t
 173 crypto_fast_rng_uint64_range(crypto_fast_rng_t *rng,
 174                              uint64_t min, uint64_t max)
 175 {
 176   /* Handle corrupted input */
 177   if (BUG(min >= max)) {
 178     return min;
 179   }
 180
 181   return min + crypto_fast_rng_get_uint64(rng, max - min);
 182 }
 183
 184 /**
 185  * As crypto_rand_get_double() but extract the result from a crypto_fast_rng_t.
 186  */
 187 double
 188 crypto_fast_rng_get_double(crypto_fast_rng_t *rng)
 189 {
 190   unsigned int u;
 191   crypto_fast_rng_getbytes(rng, (void*)&u, sizeof(u));
 192   return ((double)u) / UINT_MAX_AS_DOUBLE;
 193 }
 194