stdlib/arc4random_uniform.c

   1 /* Random pseudo generator number which returns a single 32 bit value
   2    uniformly distributed but with an upper_bound.
   3    Copyright (C) 2022 Free Software Foundation, Inc.
   4    This file is part of the GNU C Library.
   5
   6    The GNU C Library is free software; you can redistribute it and/or
   7    modify it under the terms of the GNU Lesser General Public
   8    License as published by the Free Software Foundation; either
   9    version 2.1 of the License, or (at your option) any later version.
  10
  11    The GNU C Library is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14    Lesser General Public License for more details.
  15
  16    You should have received a copy of the GNU Lesser General Public
  17    License along with the GNU C Library; if not, see
  18    <https://www.gnu.org/licenses/>.  */
  19
  20 #include <endian.h>
  21 #include <libc-lock.h>
  22 #include <stdlib.h>
  23 #include <sys/param.h>
  24
  25 /* Return the number of bytes which cover values up to the limit.  */
  26 __attribute__ ((const))
  27 static uint32_t
  28 byte_count (uint32_t n)
  29 {
  30   if (n < (1U << 8))
  31     return 1;
  32   else if (n < (1U << 16))
  33     return 2;
  34   else if (n < (1U << 24))
  35     return 3;
  36   else
  37     return 4;
  38 }
  39
  40 /* Fill the lower bits of the result with randomness, according to the
  41    number of bytes requested.  */
  42 static void
  43 random_bytes (uint32_t *result, uint32_t byte_count)
  44 {
  45   *result = 0;
  46   unsigned char *ptr = (unsigned char *) result;
  47   if (__BYTE_ORDER == __BIG_ENDIAN)
  48     ptr += 4 - byte_count;
  49   __arc4random_buf (ptr, byte_count);
  50 }
  51
  52 uint32_t
  53 __arc4random_uniform (uint32_t n)
  54 {
  55   if (n <= 1)
  56     /* There is no valid return value for a zero limit, and 0 is the
  57        only possible result for limit 1.  */
  58     return 0;
  59
  60   /* The bits variable serves as a source for bits.  Prefetch the
  61      minimum number of bytes needed.  */
  62   uint32_t count = byte_count (n);
  63   uint32_t bits_length = count * CHAR_BIT;
  64   uint32_t bits;
  65   random_bytes (&bits, count);
  66
  67   /* Powers of two are easy.  */
  68   if (powerof2 (n))
  69     return bits & (n - 1);
  70
  71   /* The general case.  This algorithm follows Jérémie Lumbroso,
  72      Optimal Discrete Uniform Generation from Coin Flips, and
  73      Applications (2013), who credits Donald E. Knuth and Andrew
  74      C. Yao, The complexity of nonuniform random number generation
  75      (1976), for solving the general case.
  76
  77      The implementation below unrolls the initialization stage of the
  78      loop, where v is less than n.  */
  79
  80   /* Use 64-bit variables even though the intermediate results are
  81      never larger than 33 bits.  This ensures the code is easier to
  82      compile on 64-bit architectures.  */
  83   uint64_t v;
  84   uint64_t c;
  85
  86   /* Initialize v and c.  v is the smallest power of 2 which is larger
  87      than n.*/
  88   {
  89     uint32_t log2p1 = 32 - __builtin_clz (n);
  90     v = 1ULL << log2p1;
  91     c = bits & (v - 1);
  92     bits >>= log2p1;
  93     bits_length -= log2p1;
  94   }
  95
  96   /* At the start of the loop, c is uniformly distributed within the
  97      half-open interval [0, v), and v < 2n < 2**33.  */
  98   while (true)
  99     {
 100       if (v >= n)
 101         {
 102           /* If the candidate is less than n, accept it.  */
 103           if (c < n)
 104             /* c is uniformly distributed on [0, n).  */
 105             return c;
 106           else
 107             {
 108               /* c is uniformly distributed on [n, v).  */
 109               v -= n;
 110               c -= n;
 111               /* The distribution was shifted, so c is uniformly
 112                  distributed on [0, v) again.  */
 113             }
 114         }
 115       /* v < n here.  */
 116
 117       /* Replenish the bit source if necessary.  */
 118       if (bits_length == 0)
 119         {
 120           /* Overwrite the least significant byte.  */
 121           random_bytes (&bits, 1);
 122           bits_length = CHAR_BIT;
 123         }
 124
 125       /* Double the range.  No overflow because v < n < 2**32.  */
 126       v *= 2;
 127       /* v < 2n here.  */
 128
 129       /* Extract a bit and append it to c.  c remains less than v and
 130          thus 2**33.  */
 131       c = (c << 1) | (bits & 1);
 132       bits >>= 1;
 133       --bits_length;
 134
 135       /* At this point, c is uniformly distributed on [0, v) again,
 136          and v < 2n < 2**33.  */
 137     }
 138 }
 139 libc_hidden_def (__arc4random_uniform)
 140 weak_alias (__arc4random_uniform, arc4random_uniform)