summaryrefslogtreecommitdiffstats
path: root/lib/csrand.c
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--lib/csrand.c150
1 files changed, 150 insertions, 0 deletions
diff --git a/lib/csrand.c b/lib/csrand.c
new file mode 100644
index 0000000..8ded343
--- /dev/null
+++ b/lib/csrand.c
@@ -0,0 +1,150 @@
+/*
+ * SPDX-FileCopyrightText: Alejandro Colomar <alx@kernel.org>
+ *
+ * SPDX-License-Identifier: BSD-3-Clause
+ */
+
+#include <config.h>
+
+#ident "$Id$"
+
+#include <limits.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+#if HAVE_SYS_RANDOM_H
+#include <sys/random.h>
+#endif
+#include "bit.h"
+#include "defines.h"
+#include "prototypes.h"
+#include "shadowlog.h"
+#include "sizeof.h"
+
+
+static uint32_t csrand32(void);
+static uint32_t csrand_uniform32(uint32_t n);
+static unsigned long csrand_uniform_slow(unsigned long n);
+
+
+/*
+ * Return a uniformly-distributed CS random u_long value.
+ */
+unsigned long
+csrand(void)
+{
+ FILE *fp;
+ unsigned long r;
+
+#ifdef HAVE_GETENTROPY
+ /* getentropy may exist but lack kernel support. */
+ if (getentropy(&r, sizeof(r)) == 0)
+ return r;
+#endif
+
+#ifdef HAVE_GETRANDOM
+ /* Likewise getrandom. */
+ if (getrandom(&r, sizeof(r), 0) == sizeof(r))
+ return r;
+#endif
+
+#ifdef HAVE_ARC4RANDOM_BUF
+ /* arc4random_buf can never fail. */
+ arc4random_buf(&r, sizeof(r));
+ return r;
+#endif
+
+ /* Use /dev/urandom as a last resort. */
+ fp = fopen("/dev/urandom", "r");
+ if (NULL == fp) {
+ goto fail;
+ }
+
+ if (fread(&r, sizeof(r), 1, fp) != 1) {
+ fclose(fp);
+ goto fail;
+ }
+
+ fclose(fp);
+ return r;
+
+fail:
+ fprintf(log_get_logfd(), _("Unable to obtain random bytes.\n"));
+ exit(1);
+}
+
+
+/*
+ * Return a uniformly-distributed CS random value in the interval [0, n-1].
+ */
+unsigned long
+csrand_uniform(unsigned long n)
+{
+ if (n == 0 || n > UINT32_MAX)
+ return csrand_uniform_slow(n);
+
+ return csrand_uniform32(n);
+}
+
+
+/*
+ * Return a uniformly-distributed CS random value in the interval [min, max].
+ */
+unsigned long
+csrand_interval(unsigned long min, unsigned long max)
+{
+ return csrand_uniform(max - min + 1) + min;
+}
+
+
+static uint32_t
+csrand32(void)
+{
+ return csrand();
+}
+
+
+/*
+ * Fast Random Integer Generation in an Interval
+ * ACM Transactions on Modeling and Computer Simulation 29 (1), 2019
+ * <https://arxiv.org/abs/1805.10941>
+ */
+static uint32_t
+csrand_uniform32(uint32_t n)
+{
+ uint32_t bound, rem;
+ uint64_t r, mult;
+
+ if (n == 0)
+ return csrand32();
+
+ bound = -n % n; // analogous to `2^32 % n`, since `x % y == (x-y) % y`
+
+ do {
+ r = csrand32();
+ mult = r * n;
+ rem = mult; // analogous to `mult % 2^32`
+ } while (rem < bound); // p = (2^32 % n) / 2^32; W.C.: n=2^31+1, p=0.5
+
+ r = mult >> WIDTHOF(n); // analogous to `mult / 2^32`
+
+ return r;
+}
+
+
+static unsigned long
+csrand_uniform_slow(unsigned long n)
+{
+ unsigned long r, max, mask;
+
+ max = n - 1;
+ mask = bit_ceil_wrapul(n) - 1;
+
+ do {
+ r = csrand();
+ r &= mask; // optimization
+ } while (r > max); // p = ((mask+1) % n) / (mask+1); W.C.: p=0.5
+
+ return r;
+}