(wrong string) ée

From: <git_AT_suckless.org>
Date: Sun, 27 Mar 2016 18:04:19 +0200 (CEST)

commit f6106595fd75379982d487196162bea6a6ca0795
Author: Mattias Andrée <maandree_AT_kth.se>
AuthorDate: Sun Mar 27 18:03:57 2016 +0200
Commit: Mattias Andrée <maandree_AT_kth.se>
CommitDate: Sun Mar 27 18:03:57 2016 +0200

    Add rand(3), lrand(3), and random(3) to zrand
    
    Signed-off-by: Mattias Andrée <maandree_AT_kth.se>

diff --git a/.gitignore b/.gitignore
index 2c97130..e6e3050 100644
--- a/.gitignore
+++ b/.gitignore
_AT_@ -6,3 +6,4 @@
 /test
 /test-random.c
 /benchmark
+/benchmark-zrand
diff --git a/Makefile b/Makefile
index c256d4c..18f0ff8 100644
--- a/Makefile
+++ b/Makefile
_AT_@ -94,6 +94,9 @@ benchmark: bench/benchmark.c bench/$(BENCHMARK_LIB).h
         $(CC) $(LDFLAGS) $(CFLAGS) $(CPPFLAGS) -o $_AT_ bench/benchmark.c $(BENCHMARK_$(BENCHMARK_LIB))
 endif
 
+benchmark-zrand: bench/benchmark-zrand.c libzahl.a
+ $(CC) $(LDFLAGS) $(CFLAGS) $(CPPFLAGS) -o $_AT_ $^
+
 check: test
         ./test
 
diff --git a/TODO b/TODO
index 5c69340..68a5b1d 100644
--- a/TODO
+++ b/TODO
_AT_@ -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
new file mode 100644
index 0000000..a7e9fb4
--- /dev/null
+++ b/bench/benchmark-zrand.c
_AT_@ -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
index d756db8..68084f2 100644
--- a/bench/benchmark.c
+++ b/bench/benchmark.c
_AT_@ -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
index 1e43a43..7f4332c 100644
--- a/config.mk
+++ b/config.mk
_AT_@ -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
index 5945ad8..3d70452 100644
--- a/src/zrand.c
+++ b/src/zrand.c
_AT_@ -2,6 +2,8 @@
 #include "internals.h"
 
 #include <fcntl.h>
+#include <stdlib.h>
+#include <time.h>
 #include <unistd.h>
 
 #ifndef FAST_RANDOM_PATHNAME
_AT_@ -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;
_AT_@ -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);
         }
_AT_@ -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;
_AT_@ -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
index e49a6a0..6e30510 100644
--- a/zahl.h
+++ b/zahl.h
_AT_@ -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 {
Received on Sun Mar 27 2016 - 18:04:19 CEST

This archive was generated by hypermail 2.3.0 : Sun Mar 27 2016 - 18:12:22 CEST