diff options
Diffstat (limited to 'lib/libc/gen/arc4random_uniform.c')
| -rw-r--r-- | lib/libc/gen/arc4random_uniform.c | 71 |
1 files changed, 31 insertions, 40 deletions
diff --git a/lib/libc/gen/arc4random_uniform.c b/lib/libc/gen/arc4random_uniform.c index 06cd29c6dbe4..23455e545899 100644 --- a/lib/libc/gen/arc4random_uniform.c +++ b/lib/libc/gen/arc4random_uniform.c @@ -1,56 +1,47 @@ -/* $OpenBSD: arc4random_uniform.c,v 1.3 2019/01/20 02:59:07 bcook Exp $ */ - -/* - * Copyright (c) 2008, Damien Miller <djm@openbsd.org> +/*- + * SPDX-License-Identifier: 0BSD * - * Permission to use, copy, modify, and distribute this software for any - * purpose with or without fee is hereby granted, provided that the above - * copyright notice and this permission notice appear in all copies. + * Copyright (c) Robert Clausecker <fuz@FreeBSD.org> + * Based on a publication by Daniel Lemire. + * Public domain where applicable. * - * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * Daniel Lemire, "Fast Random Integer Generation in an Interval", + * Association for Computing Machinery, ACM Trans. Model. Comput. Simul., + * no. 1, vol. 29, pp. 1--12, New York, NY, USA, January 2019. */ #include <stdint.h> #include <stdlib.h> -/* - * Calculate a uniformly distributed random number less than upper_bound - * avoiding "modulo bias". - * - * Uniformity is achieved by generating new random numbers until the one - * returned is outside the range [0, 2**32 % upper_bound). This - * guarantees the selected random number will be inside - * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound) - * after reduction modulo upper_bound. - */ uint32_t arc4random_uniform(uint32_t upper_bound) { - uint32_t r, min; - - if (upper_bound < 2) - return 0; - - /* 2**32 % x == (2**32 - x) % x */ - min = -upper_bound % upper_bound; + uint64_t product; /* - * This could theoretically loop forever but each retry has - * p > 0.5 (worst case, usually far better) of selecting a - * number inside the range we need, so it should rarely need - * to re-roll. + * The paper uses these variable names: + * + * L -- log2(UINT32_MAX+1) + * s -- upper_bound + * x -- arc4random() return value + * m -- product + * l -- (uint32_t)product + * t -- threshold */ - for (;;) { - r = arc4random(); - if (r >= min) - break; + + if (upper_bound <= 1) + return (0); + + product = upper_bound * (uint64_t)arc4random(); + + if ((uint32_t)product < upper_bound) { + uint32_t threshold; + + /* threshold = (2**32 - upper_bound) % upper_bound */ + threshold = -upper_bound % upper_bound; + while ((uint32_t)product < threshold) + product = upper_bound * (uint64_t)arc4random(); } - return r % upper_bound; + return (product >> 32); } |