commit f6106595fd75379982d487196162bea6a6ca0795
parent c5f0bedd07467c089b0eca567828508abfcc9b6d
Author: Mattias Andrée <maandree@kth.se>
Date: Sun, 27 Mar 2016 18:03:57 +0200
Add rand(3), lrand(3), and random(3) to zrand
Signed-off-by: Mattias Andrée <maandree@kth.se>
Diffstat:
8 files changed, 211 insertions(+), 32 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -6,3 +6,4 @@
/test
/test-random.c
/benchmark
+/benchmark-zrand
diff --git a/Makefile b/Makefile
@@ -94,6 +94,9 @@ benchmark: bench/benchmark.c bench/$(BENCHMARK_LIB).h
$(CC) $(LDFLAGS) $(CFLAGS) $(CPPFLAGS) -o $@ bench/benchmark.c $(BENCHMARK_$(BENCHMARK_LIB))
endif
+benchmark-zrand: bench/benchmark-zrand.c libzahl.a
+ $(CC) $(LDFLAGS) $(CFLAGS) $(CPPFLAGS) -o $@ $^
+
check: test
./test
diff --git a/TODO b/TODO
@@ -19,3 +19,5 @@ Test optimisation of zmul:
Would zmul be faster if we split only one of the
factors until they are both approximately the same
size?
+
+Add entropy test for zrand.
diff --git a/bench/benchmark-zrand.c b/bench/benchmark-zrand.c
@@ -0,0 +1,63 @@
+#include <time.h>
+#include <stdio.h>
+
+#include "../zahl.h"
+
+
+#ifndef CLOCK_MONOTONIC_RAW
+# define CLOCK_MONOTONIC_RAW CLOCK_MONOTONIC
+#endif
+
+
+#define BENCHMARK(INSTRUCTION, FAST)\
+ do {\
+ i = FAST ? 1000000L : 1000L;\
+ clock_gettime(CLOCK_MONOTONIC_RAW, &start);\
+ while (i--) {\
+ INSTRUCTION;\
+ }\
+ clock_gettime(CLOCK_MONOTONIC_RAW, &end);\
+ end.tv_sec -= start.tv_sec;\
+ end.tv_nsec -= start.tv_nsec;\
+ if (end.tv_nsec < 0) {\
+ end.tv_nsec += 1000000000L;\
+ end.tv_sec -= 1;\
+ }\
+ printf("%s: %lli.%09li %s\n",\
+ #INSTRUCTION,\
+ (long long int)(end.tv_sec), end.tv_nsec,\
+ FAST ? "µs" : "ms");\
+ } while (0)
+
+
+int
+main(int argc, char *argv[])
+{
+ struct timespec start, end;
+ z_t r, n;
+ jmp_buf jmp;
+ size_t i;
+
+ if (setjmp(jmp)) {
+ zperror(argv[0]);
+ return 1;
+ }
+ zsetup(jmp);
+ zinit(r);
+ zinit(n);
+
+ zsetu(n, 1);
+ zlsh(n, n, 64000L - 1L);
+ zset(r, n);
+
+ BENCHMARK(zrand(r, FAST_RANDOM, MODUNIFORM, n), 0);
+ BENCHMARK(zrand(r, LIBC_RAND_RANDOM, MODUNIFORM, n), 0);
+ BENCHMARK(zrand(r, LIBC_RANDOM_RANDOM, MODUNIFORM, n), 0);
+ BENCHMARK(zrand(r, LIBC_RAND48_RANDOM, MODUNIFORM, n), 0);
+
+ zfree(r);
+ zfree(n);
+ zunsetup();
+ return 0;
+ (void) argc;
+}
diff --git a/bench/benchmark.c b/bench/benchmark.c
@@ -117,8 +117,8 @@ main(int argc, char *argv[])
BENCHMARK(zsets(c, "5495468234592964023447280368442884381000481887"), 0);
BENCHMARK(zstr_length(a, 10), 0);
BENCHMARK(zstr(a, buf), 0);
- BENCHMARK(zrand(c, FAST_RANDOM, QUASIUNIFORM, a), 0);
- BENCHMARK(zrand(c, FAST_RANDOM, UNIFORM, a), 0);
+ BENCHMARK(zrand(c, DEFAULT_RANDOM, QUASIUNIFORM, a), 0);
+ BENCHMARK(zrand(c, DEFAULT_RANDOM, UNIFORM, a), 0);
BENCHMARK(zptest(d, a, 5), 0);
BENCHMARK(zsave(a, buf), 1);
BENCHMARK(zload(a, buf), 1);
diff --git a/config.mk b/config.mk
@@ -12,7 +12,9 @@ RANLIB = ranlib
# you have to add -DFAST_RANDOM_PATHNAME=... to CPPFLAGS, and
# unless /dev/random exists and is a blocking secure random number generator
# you have to add -DSECURE_RANDOM_PATHNAME=... to CPPFLAGS.
+# Remove -DGOOD_RAND if the higher bits have higher entropy in the lower
+# bits in rand(3), this was historically the case.
-CPPFLAGS = -D_DEFAULT_SOURCE -D_BSD_SOURCE -D_XOPEN_SOURCE=700
+CPPFLAGS = -D_DEFAULT_SOURCE -D_BSD_SOURCE -D_XOPEN_SOURCE=700 -DGOOD_RAND
CFLAGS = -std=c99 -flto -O3 -Wall -pedantic
LDFLAGS = -s
diff --git a/src/zrand.c b/src/zrand.c
@@ -2,6 +2,8 @@
#include "internals.h"
#include <fcntl.h>
+#include <stdlib.h>
+#include <time.h>
#include <unistd.h>
#ifndef FAST_RANDOM_PATHNAME
@@ -14,23 +16,110 @@
static void
-zrand_get_random_bits(z_t r, size_t bits, int fd)
+zrand_libc_rand(void *out, size_t n, void *statep)
{
- size_t read_total = 0, n, chars = CEILING_BITS_TO_CHARS(bits);
- ssize_t read_just;
- zahl_char_t mask = 1;
- char *buf;
+ static char inited = 0;
- ENSURE_SIZE(r, chars);
- buf = (char *)(r->chars);
+ unsigned int ri;
+ double rd;
+ unsigned char *buf = out;
+
+ if (!inited) {
+ inited = 1;
+ srand((intptr_t)out | time(NULL));
+ }
+
+ while (n--) {
+ ri = rand();
+ rd = (double)ri / ((double)RAND_MAX + 1);
+#ifdef GOOD_RAND
+ rd *= 256 * 256;
+ ri = (unsigned int)rd;
+ buf[n] = (unsigned char)((ri >> 0) & 255);
+ if (!n--) break;
+ buf[n] = (unsigned char)((ri >> 8) & 255);
+#else
+ rd *= 256;
+ buf[n] = (unsigned char)rd;
+#endif
+ }
+
+ (void) statep;
+}
+
+static void
+zrand_libc_rand48(void *out, size_t n, void *statep)
+{
+ static char inited = 0;
+
+ long int r0, r1;
+ unsigned char *buf = out;
- for (n = chars * sizeof(zahl_char_t); n;) {
+ if (!inited) {
+ inited = 1;
+ srand48((intptr_t)out | time(NULL));
+ }
+
+ while (n--) {
+ r0 = lrand48() & 15;
+ r1 = lrand48() & 15;
+ buf[n] = (r0 << 4) | r1;
+ }
+
+ (void) statep;
+}
+
+static void
+zrand_libc_random(void *out, size_t n, void *statep)
+{
+ static char inited = 0;
+
+ long int ri;
+ unsigned char *buf = out;
+
+ if (!inited) {
+ inited = 1;
+ srandom((intptr_t)out | time(NULL));
+ }
+
+ while (n--) {
+ ri = random();
+ buf[n] = (unsigned char)((ri >> 0) & 255);
+ if (!n--) break;
+ buf[n] = (unsigned char)((ri >> 8) & 255);
+ if (!n--) break;
+ buf[n] = (unsigned char)((ri >> 16) & 255);
+ }
+
+ (void) statep;
+}
+
+static void
+zrand_fd(void *out, size_t n, void *statep)
+{
+ int fd = *(int *)statep;
+ ssize_t read_just;
+ size_t read_total = 0;
+ char *buf = out;
+
+ while (n) {
read_just = read(fd, buf + read_total, n);
if (unlikely(read_just < 0))
libzahl_failure(errno);
read_total += (size_t)read_just;
n -= (size_t)read_just;
}
+}
+
+static void
+zrand_get_random_bits(z_t r, size_t bits, void (*fun)(void *, size_t, void *), void *statep)
+{
+ size_t n, chars = CEILING_BITS_TO_CHARS(bits);
+ zahl_char_t mask = 1;
+
+ ENSURE_SIZE(r, chars);
+
+ fun(r->chars, chars * sizeof(zahl_char_t), statep);
bits = BITS_IN_LAST_CHAR(bits);
mask <<= bits;
@@ -50,19 +139,41 @@ zrand_get_random_bits(z_t r, size_t bits, int fd)
void
zrand(z_t r, enum zranddev dev, enum zranddist dist, z_t n)
{
+#define RANDOM_UNIFORM(RETRY)\
+ do {\
+ if (unlikely(znegative(n)))\
+ libzahl_failure(-ZERROR_NEGATIVE);\
+ bits = zbits(n);\
+ do\
+ zrand_get_random_bits(r, bits, random_fun, statep);\
+ while (RETRY && unlikely(zcmpmag(r, n) > 0));\
+ } while (0)
+
+
const char *pathname = 0;
size_t bits;
- int fd;
+ int fd = -1;
+ void *statep = 0;
+ void (*random_fun)(void *, size_t, void *) = &zrand_fd;
switch (dev) {
- case DEFAULT_RANDOM:
- case FASTEST_RANDOM:
case FAST_RANDOM:
pathname = FAST_RANDOM_PATHNAME;
break;
case SECURE_RANDOM:
pathname = SECURE_RANDOM_PATHNAME;
break;
+ case LIBC_RAND_RANDOM:
+ random_fun = &zrand_libc_rand;
+ break;
+ case DEFAULT_RANDOM:
+ case FASTEST_RANDOM:
+ case LIBC_RANDOM_RANDOM:
+ random_fun = &zrand_libc_random;
+ break;
+ case LIBC_RAND48_RANDOM:
+ random_fun = &zrand_libc_rand48;
+ break;
default:
libzahl_failure(EINVAL);
}
@@ -72,34 +183,27 @@ zrand(z_t r, enum zranddev dev, enum zranddist dist, z_t n)
return;
}
- fd = open(pathname, O_RDONLY);
- if (unlikely(fd < 0))
- libzahl_failure(errno);
+ if (pathname) {
+ fd = open(pathname, O_RDONLY);
+ if (unlikely(fd < 0))
+ libzahl_failure(errno);
+ statep = &fd;
+ }
switch (dist) {
case QUASIUNIFORM:
- if (unlikely(znegative(n)))
- libzahl_failure(-ZERROR_NEGATIVE);
- bits = zbits(n);
- zrand_get_random_bits(r, bits, fd);
+ RANDOM_UNIFORM(0);
zadd(r, r, libzahl_const_1);
zmul(r, r, n);
zrsh(r, r, bits);
break;
case UNIFORM:
- if (unlikely(znegative(n)))
- libzahl_failure(-ZERROR_NEGATIVE);
- bits = zbits(n);
- do
- zrand_get_random_bits(r, bits, fd);
- while (unlikely(zcmpmag(r, n) > 0));
+ RANDOM_UNIFORM(1);
break;
case MODUNIFORM:
- if (unlikely(znegative(n)))
- libzahl_failure(-ZERROR_NEGATIVE);
- zrand_get_random_bits(r, zbits(n), fd);
+ RANDOM_UNIFORM(0);
if (unlikely(zcmpmag(r, n) > 0))
zsub(r, r, n);
break;
@@ -108,5 +212,6 @@ zrand(z_t r, enum zranddev dev, enum zranddist dist, z_t n)
libzahl_failure(EINVAL);
}
- close(fd);
+ if (fd >= 0)
+ close(fd);
}
diff --git a/zahl.h b/zahl.h
@@ -50,7 +50,10 @@ enum zranddev {
FAST_RANDOM = 0, /* Random numbers are generated directly from /dev/urandom. */
SECURE_RANDOM, /* Random numbers are generated directly from /dev/random. */
DEFAULT_RANDOM, /* Select the default random number generator. */
- FASTEST_RANDOM /* Select the fastest random number generator. */
+ FASTEST_RANDOM, /* Select the fastest random number generator. */
+ LIBC_RAND_RANDOM, /* Use rand(3). */
+ LIBC_RANDOM_RANDOM, /* Use random(3). */
+ LIBC_RAND48_RANDOM /* Use lrand48(3). */
};
enum zranddist {
