From debbugs-submit-bounces@debbugs.gnu.org Fri Jul 16 17:17:38 2010 Received: (at submit) by debbugs.gnu.org; 16 Jul 2010 21:17:38 +0000 Received: from localhost ([127.0.0.1] helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1OZsHq-0001qV-4I for submit@debbugs.gnu.org; Fri, 16 Jul 2010 17:17:38 -0400 Received: from mx10.gnu.org ([199.232.76.166]) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1OZsHn-0001qQ-BE for submit@debbugs.gnu.org; Fri, 16 Jul 2010 17:17:36 -0400 Received: from lists.gnu.org ([199.232.76.165]:53001) by monty-python.gnu.org with esmtps (TLS-1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.60) (envelope-from ) id 1OZsI1-0001Rj-M2 for submit@debbugs.gnu.org; Fri, 16 Jul 2010 17:17:49 -0400 Received: from [140.186.70.92] (port=48944 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1OZsHz-0005oJ-SL for bug-coreutils@gnu.org; Fri, 16 Jul 2010 17:17:48 -0400 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,T_RP_MATCHES_RCVD autolearn=unavailable version=3.3.1 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1OZsHy-00037R-O0 for bug-coreutils@gnu.org; Fri, 16 Jul 2010 17:17:47 -0400 Received: from kiwi.cs.ucla.edu ([131.179.128.19]:58235) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1OZsHy-00037A-A1 for bug-coreutils@gnu.org; Fri, 16 Jul 2010 17:17:46 -0400 Received: from [131.179.64.200] (Penguin.CS.UCLA.EDU [131.179.64.200]) by kiwi.cs.ucla.edu (8.13.8+Sun/8.13.8/UCLACS-6.0) with ESMTP id o6GLHgKS023218 for ; Fri, 16 Jul 2010 14:17:42 -0700 (PDT) Message-ID: <4C40CC76.2050407@cs.ucla.edu> Date: Fri, 16 Jul 2010 14:17:42 -0700 From: Paul Eggert Organization: UCLA Computer Science Department User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.1.10) Gecko/20100527 Thunderbird/3.0.5 MIME-Version: 1.0 To: Bug Coreutils Subject: [PATCH] randread: don't require -lrt Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-detected-operating-system: by eggs.gnu.org: Solaris 10 (beta) X-detected-operating-system: by monty-python.gnu.org: GNU/Linux 2.6, seldom 2.4 (older, 4) X-Spam-Score: -5.1 (-----) X-Debbugs-Envelope-To: submit X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.11 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -5.1 (-----) In looking at the random part of coreutils some more, I see some issues. 1. Apps that use random numbers typically must link to -lrt, for a very small benefit (nanosecond resolution rather than microsecond resolution time stamp for random seed). Often this "benefit" is illusory as the time stamps really are not nanosecond resolution. 2. If /dev/urandom is available, it should be used to seed the ISAAC generator. This will cost more than invoking gettimeofday() but it's far more random. 3. We could get about 2X CPU performance on 64-bit machines by using ISAAC64 instead of ISAAC. The patch below implements (1); I haven't installed it. I'd like to do (2) and (3) too, but thought I'd ask for feedback first. >From aa279ddf6d766ca8f280295632d14cfbf4926c5b Mon Sep 17 00:00:00 2001 From: Paul R. Eggert Date: Fri, 16 Jul 2010 14:02:08 -0700 Subject: [PATCH] randread: don't require -lrt Programs like 'sort' were linking to -lrt in order to get clock_gettime, but this was misguided: it wasted considerable resources while gaining at most 10 bits of entropy. Almost nobody needs the entropy, and there are better ways to get much better entropy for people who do need it. * gl/lib/rand-isaac.c (isaac_seed): Include not "gethrxtime.h". (isaac_seed): Use gettimeofday rather than gethrxtime. * gl/modules/randread (Depends-on): Depend on gettimeofday and not gethrxtime. * src/Makefile.am (mktemp_LDADD, shred_LDADD, shuf_LDADD, sort_LDADD): (tac_LDADD): Omit $(LIB_GETHRXTIME); no longer needed. --- gl/lib/rand-isaac.c | 6 +++--- gl/modules/randread | 2 +- src/Makefile.am | 7 +------ 3 files changed, 5 insertions(+), 10 deletions(-) diff --git a/gl/lib/rand-isaac.c b/gl/lib/rand-isaac.c index 52d53a3..377caa6 100644 --- a/gl/lib/rand-isaac.c +++ b/gl/lib/rand-isaac.c @@ -35,10 +35,9 @@ #include "rand-isaac.h" #include +#include #include -#include "gethrxtime.h" - /* This index operation is more efficient on many processors */ #define ind(mm, x) \ @@ -292,7 +291,8 @@ isaac_seed (struct isaac_state *s) { gid_t t = getgid (); ISAAC_SEED (s, t); } { - xtime_t t = gethrxtime (); + struct timeval t; + gettimeofday (&t, NULL); ISAAC_SEED (s, t); } diff --git a/gl/modules/randread b/gl/modules/randread index 9870cc8..efc7958 100644 --- a/gl/modules/randread +++ b/gl/modules/randread @@ -11,7 +11,7 @@ Depends-on: error exitfail fopen-safer -gethrxtime +gettimeofday quotearg stdbool stdint diff --git a/src/Makefile.am b/src/Makefile.am index d87fbb5..1a19fa6 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -328,13 +328,8 @@ ls_LDADD += $(LIB_CLOCK_GETTIME) pr_LDADD += $(LIB_CLOCK_GETTIME) touch_LDADD += $(LIB_CLOCK_GETTIME) -# for gethrxtime, randint, randread, gen_tempname, mkstemp +# for gethrxtime dd_LDADD += $(LIB_GETHRXTIME) -mktemp_LDADD += $(LIB_GETHRXTIME) -shred_LDADD += $(LIB_GETHRXTIME) -shuf_LDADD += $(LIB_GETHRXTIME) -sort_LDADD += $(LIB_GETHRXTIME) -tac_LDADD += $(LIB_GETHRXTIME) # for cap_get_file ls_LDADD += $(LIB_CAP) -- 1.7.1 From debbugs-submit-bounces@debbugs.gnu.org Fri Jul 16 18:34:45 2010 Received: (at 6658) by debbugs.gnu.org; 16 Jul 2010 22:34:45 +0000 Received: from localhost ([127.0.0.1] helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1OZtUT-0002PV-6c for submit@debbugs.gnu.org; Fri, 16 Jul 2010 18:34:45 -0400 Received: from smtp1-g21.free.fr ([212.27.42.1]) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1OZtUP-0002PP-GJ for 6658@debbugs.gnu.org; Fri, 16 Jul 2010 18:34:43 -0400 Received: from mx.meyering.net (unknown [82.230.74.64]) by smtp1-g21.free.fr (Postfix) with ESMTP id EC5619400AA; Sat, 17 Jul 2010 00:34:50 +0200 (CEST) Received: by rho.meyering.net (Acme Bit-Twister, from userid 1000) id 35AC2F55A; Sat, 17 Jul 2010 00:34:49 +0200 (CEST) From: Jim Meyering To: Paul Eggert Subject: Re: bug#6658: [PATCH] randread: don't require -lrt In-Reply-To: <4C40CC76.2050407@cs.ucla.edu> (Paul Eggert's message of "Fri, 16 Jul 2010 14:17:42 -0700") References: <4C40CC76.2050407@cs.ucla.edu> Date: Sat, 17 Jul 2010 00:34:49 +0200 Message-ID: <87zkxrqcmu.fsf@meyering.net> Lines: 22 MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Spam-Score: -3.3 (---) X-Debbugs-Envelope-To: 6658 Cc: 6658@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.11 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -3.3 (---) Paul Eggert wrote: > In looking at the random part of coreutils some more, I see some > issues. > > 1. Apps that use random numbers typically must link to -lrt, > for a very small benefit (nanosecond resolution rather than > microsecond resolution time stamp for random seed). Often > this "benefit" is illusory as the time stamps really are not > nanosecond resolution. > > 2. If /dev/urandom is available, it should be used to seed > the ISAAC generator. This will cost more than invoking > gettimeofday() but it's far more random. > > 3. We could get about 2X CPU performance on 64-bit machines by using > ISAAC64 instead of ISAAC. > > The patch below implements (1); I haven't installed it. I'd like to > do (2) and (3) too, but thought I'd ask for feedback first. These are all welcome changes, and the patch for (1) looks fine. Thanks! From debbugs-submit-bounces@debbugs.gnu.org Fri Jul 16 21:19:31 2010 Received: (at 6658) by debbugs.gnu.org; 17 Jul 2010 01:19:31 +0000 Received: from localhost ([127.0.0.1] helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1OZw3u-0003QC-MH for submit@debbugs.gnu.org; Fri, 16 Jul 2010 21:19:30 -0400 Received: from mail1.slb.deg.dub.stisp.net ([84.203.253.98]) by debbugs.gnu.org with smtp (Exim 4.69) (envelope-from ) id 1OZw3s-0003Q7-QW for 6658@debbugs.gnu.org; Fri, 16 Jul 2010 21:19:29 -0400 Received: (qmail 37140 invoked from network); 17 Jul 2010 01:19:42 -0000 Received: from unknown (HELO ?192.168.2.25?) (84.203.137.218) by mail1.slb.deg.dub.stisp.net with SMTP; 17 Jul 2010 01:19:42 -0000 Message-ID: <4C41052C.8020106@draigBrady.com> Date: Sat, 17 Jul 2010 02:19:40 +0100 From: =?ISO-8859-1?Q?P=E1draig_Brady?= User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.1.8) Gecko/20100227 Thunderbird/3.0.3 MIME-Version: 1.0 To: Paul Eggert Subject: Re: bug#6658: [PATCH] randread: don't require -lrt References: <4C40CC76.2050407@cs.ucla.edu> In-Reply-To: <4C40CC76.2050407@cs.ucla.edu> X-Enigmail-Version: 1.0.1 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-Spam-Score: -2.7 (--) X-Debbugs-Envelope-To: 6658 Cc: 6658@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.11 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -2.7 (--) On 16/07/10 22:17, Paul Eggert wrote: > In looking at the random part of coreutils some more, I see some > issues. > > 1. Apps that use random numbers typically must link to -lrt, > for a very small benefit (nanosecond resolution rather than > microsecond resolution time stamp for random seed). Often > this "benefit" is illusory as the time stamps really are not > nanosecond resolution. > > 2. If /dev/urandom is available, it should be used to seed > the ISAAC generator. This will cost more than invoking > gettimeofday() but it's far more random. > > 3. We could get about 2X CPU performance on 64-bit machines by using > ISAAC64 instead of ISAAC. > > The patch below implements (1); I haven't installed it. I'd like to > do (2) and (3) too, but thought I'd ask for feedback first. All changes make sense. `shred` doesn't need the entropy anyway as it's just scribbling random data to make it more difficult to recover data, and to hide its tracks. Performance wise `shred` probably won't run faster as it should saturate any disk, but using less CPU is good: `sort -R` and `shuf` should benefit also. thanks, Pádraig. From debbugs-submit-bounces@debbugs.gnu.org Tue Jul 20 12:59:20 2010 Received: (at 6658) by debbugs.gnu.org; 20 Jul 2010 16:59:20 +0000 Received: from localhost ([127.0.0.1] helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1ObGA4-0003dc-4D for submit@debbugs.gnu.org; Tue, 20 Jul 2010 12:59:20 -0400 Received: from kiwi.cs.ucla.edu ([131.179.128.19]) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1ObGA2-0003dX-8z for 6658@debbugs.gnu.org; Tue, 20 Jul 2010 12:59:19 -0400 Received: from [131.179.64.200] (Penguin.CS.UCLA.EDU [131.179.64.200]) by kiwi.cs.ucla.edu (8.13.8+Sun/8.13.8/UCLACS-6.0) with ESMTP id o6KGxfDF021646; Tue, 20 Jul 2010 09:59:41 -0700 (PDT) Message-ID: <4C45D5FD.1000506@cs.ucla.edu> Date: Tue, 20 Jul 2010 09:59:41 -0700 From: Paul Eggert Organization: UCLA Computer Science Department User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.1.10) Gecko/20100527 Thunderbird/3.0.5 MIME-Version: 1.0 To: Jim Meyering Subject: [PATCH] randread: use /dev/urandom to seed, not just getpid etc References: <4C40CC76.2050407@cs.ucla.edu> <87zkxrqcmu.fsf@meyering.net> In-Reply-To: <87zkxrqcmu.fsf@meyering.net> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-Spam-Score: -3.4 (---) X-Debbugs-Envelope-To: 6658 Cc: 6658@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.11 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -3.4 (---) OK, I installed part (2) of the patch: it uses /dev/urandom rather than the getpid()/gettimeofday() yucky stuff, when /dev/urandom is available. One downside to this patch is that on hosts where mkstemp doesn't work and we're using our substitute, each invocation of mkstemp opens /dev/urandom, reads a few bytes, and closes it. I don't view this as a big problem, because (a) it's only for hosts with broken mkstemp and they should fix their mkstemp and (b) creating a temp file is a big-deal operation anyway and the extra overhead of opening /dev/urandom doesn't add much. I considered working around the problem anyway, but couldn't come up with a simple, clean and fast workaround under the constraint that mkstemp must be thread-safe (the current randread stuff does not allow competing threads to read from the same random source). Perhaps later, if there's interest. >From 3403f96997bc6ff441696e11a892f2389891aaa7 Mon Sep 17 00:00:00 2001 From: Paul R. Eggert Date: Tue, 20 Jul 2010 09:50:37 -0700 Subject: [PATCH] randread: use /dev/urandom to seed, not just getpid etc * gl/lib/rand-isaac.c (isaac_seed_start): New arg SEEDED. (isaac_seed): New args FD and BYTES_BOUND. Read from FD if possible. Don't bother with low-quality sources if FD has enough bytes. * gl/lib/rand-isaac.h: New size_t arg for isaac_seed. * gl/lib/randread.c: Include fcntl.h, unistd.h. (NAME_OF_NONCE_DEVICE): New #define. (nonce_device): New static var. (randread_new): Use nonce device if available. --- gl/lib/rand-isaac.c | 49 +++++++++++++++++++++++++++++++++---------------- gl/lib/rand-isaac.h | 3 ++- gl/lib/randread.c | 11 ++++++++++- 3 files changed, 45 insertions(+), 18 deletions(-) diff --git a/gl/lib/rand-isaac.c b/gl/lib/rand-isaac.c index 377caa6..f73144a 100644 --- a/gl/lib/rand-isaac.c +++ b/gl/lib/rand-isaac.c @@ -209,9 +209,10 @@ isaac_init (struct isaac_state *s, uint32_t const *seed, size_t seedsize) } #endif -/* Initialize *S to a somewhat-random value. */ +/* Initialize *S to a somewhat-random value. The first SEEDED bytes + in S->mm are already seeded with random data. */ static void -isaac_seed_start (struct isaac_state *s) +isaac_seed_start (struct isaac_state *s, size_t seeded) { static uint32_t const iv[8] = { @@ -228,11 +229,12 @@ isaac_seed_start (struct isaac_state *s) mix (iv[0], iv[1], iv[2], iv[3], iv[4], iv[5], iv[6], iv[7]); #endif - memset (s->mm, 0, sizeof s->mm); + memset ((char *) s->mm + seeded, 0, sizeof s->mm - seeded); memcpy (s->iv, iv, sizeof s->iv); /* s->c gets used for a data pointer during the seeding phase */ - s->a = s->b = s->c = 0; + s->a = s->b = 0; + s->c = seeded; } /* Add a buffer of seed material. */ @@ -279,22 +281,37 @@ isaac_seed_finish (struct isaac_state *s) #define ISAAC_SEED(s,x) isaac_seed_data (s, &(x), sizeof (x)) /* Initialize *S to a somewhat-random value; this starts seeding, - seeds with somewhat-random data, and finishes seeding. */ + seeds with somewhat-random data, and finishes seeding. If FD is + nonnegative, seed by reading at most BYTES_BOUNDS bytes from it. */ void -isaac_seed (struct isaac_state *s) +isaac_seed (struct isaac_state *s, int fd, size_t bytes_bound) { - isaac_seed_start (s); + /* Get some data from FD if available. */ + ssize_t seeded = 0; + if (0 <= fd) + { + if (sizeof s->mm < bytes_bound) + bytes_bound = sizeof s->mm; + seeded = read (fd, s->mm, bytes_bound); + if (seeded < 0) + seeded = 0; + } - { pid_t t = getpid (); ISAAC_SEED (s, t); } - { pid_t t = getppid (); ISAAC_SEED (s, t); } - { uid_t t = getuid (); ISAAC_SEED (s, t); } - { gid_t t = getgid (); ISAAC_SEED (s, t); } + isaac_seed_start (s, seeded); - { - struct timeval t; - gettimeofday (&t, NULL); - ISAAC_SEED (s, t); - } + if (seeded < sizeof s->mm) + { + { pid_t t = getpid (); ISAAC_SEED (s, t); } + { pid_t t = getppid (); ISAAC_SEED (s, t); } + { uid_t t = getuid (); ISAAC_SEED (s, t); } + { gid_t t = getgid (); ISAAC_SEED (s, t); } + + { + struct timeval t; + gettimeofday (&t, NULL); + ISAAC_SEED (s, t); + } + } isaac_seed_finish (s); } diff --git a/gl/lib/rand-isaac.h b/gl/lib/rand-isaac.h index 6559dc8..052dc9f 100644 --- a/gl/lib/rand-isaac.h +++ b/gl/lib/rand-isaac.h @@ -21,6 +21,7 @@ #ifndef RAND_ISAAC_H # define RAND_ISAAC_H +# include # include /* Size of the state tables to use. ISAAC_LOG should be at least 3, @@ -37,7 +38,7 @@ struct isaac_state uint32_t a, b, c; /* Extra index variables */ }; -void isaac_seed (struct isaac_state *); +void isaac_seed (struct isaac_state *, int, size_t); void isaac_refill (struct isaac_state *, uint32_t[ISAAC_WORDS]); #endif diff --git a/gl/lib/randread.c b/gl/lib/randread.c index 94b9928..a681c8d 100644 --- a/gl/lib/randread.c +++ b/gl/lib/randread.c @@ -24,12 +24,14 @@ #include #include #include +#include #include #include #include #include #include #include +#include #include "gettext.h" #define _(msgid) gettext (msgid) @@ -60,6 +62,10 @@ # define ALIGNED_POINTER(ptr, type) ((size_t) (ptr) % alignof (type) == 0) #endif +#ifndef NAME_OF_NONCE_DEVICE +#define NAME_OF_NONCE_DEVICE "/dev/urandom" +#endif + /* The maximum buffer size used for reads of random data. Using the value 2 * ISAAC_BYTES makes this the largest power of two that would not otherwise cause struct randread_source to grow. */ @@ -164,8 +170,11 @@ randread_new (char const *name, size_t bytes_bound) setvbuf (source, s->buf.c, _IOFBF, MIN (sizeof s->buf.c, bytes_bound)); else { + int nonce_device = open (NAME_OF_NONCE_DEVICE, O_RDONLY | O_BINARY); s->buf.isaac.buffered = 0; - isaac_seed (&s->buf.isaac.state); + isaac_seed (&s->buf.isaac.state, nonce_device, bytes_bound); + if (0 <= nonce_device) + close (nonce_device); } return s; -- 1.7.1 From debbugs-submit-bounces@debbugs.gnu.org Tue Jul 20 19:18:40 2010 Received: (at 6658) by debbugs.gnu.org; 20 Jul 2010 23:18:40 +0000 Received: from localhost ([127.0.0.1] helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1ObM59-0006GF-Dg for submit@debbugs.gnu.org; Tue, 20 Jul 2010 19:18:39 -0400 Received: from mail1.slb.deg.dub.stisp.net ([84.203.253.98]) by debbugs.gnu.org with smtp (Exim 4.69) (envelope-from ) id 1ObM57-0006GA-5H for 6658@debbugs.gnu.org; Tue, 20 Jul 2010 19:18:38 -0400 Received: (qmail 19934 invoked from network); 20 Jul 2010 23:19:01 -0000 Received: from unknown (HELO ?192.168.2.25?) (84.203.137.218) by mail1.slb.deg.dub.stisp.net with SMTP; 20 Jul 2010 23:19:01 -0000 Message-ID: <4C462ECF.2000401@draigBrady.com> Date: Wed, 21 Jul 2010 00:18:39 +0100 From: =?ISO-8859-1?Q?P=E1draig_Brady?= User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.1.8) Gecko/20100227 Thunderbird/3.0.3 MIME-Version: 1.0 To: Paul Eggert Subject: Re: bug#6658: [PATCH] randread: use /dev/urandom to seed, not just getpid etc References: <4C40CC76.2050407@cs.ucla.edu> <87zkxrqcmu.fsf@meyering.net> <4C45D5FD.1000506@cs.ucla.edu> In-Reply-To: <4C45D5FD.1000506@cs.ucla.edu> X-Enigmail-Version: 1.0.1 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-Spam-Score: -2.7 (--) X-Debbugs-Envelope-To: 6658 Cc: Jim Meyering , 6658@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.11 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -2.7 (--) On 20/07/10 17:59, Paul Eggert wrote: > OK, I installed part (2) of the patch: it uses /dev/urandom > rather than the getpid()/gettimeofday() yucky stuff, > when /dev/urandom is available. /dev/urandom is very widely available, so this should work for most systems. > One downside to this patch is that on hosts where mkstemp > doesn't work and we're using our substitute, each invocation > of mkstemp opens /dev/urandom, reads a few bytes, and closes it. > I don't view this as a big problem, because (a) it's only for > hosts with broken mkstemp and they should fix their mkstemp and > (b) creating a temp file is a big-deal operation anyway and > the extra overhead of opening /dev/urandom doesn't add much. I agree. Running a million iterations of each seeder: orig 3s new (1 byte from urandom) 8s new (16 bytes from urandom) 11s The patch looks good. cheers, Pádraig. From debbugs-submit-bounces@debbugs.gnu.org Fri Jul 23 18:20:58 2010 Received: (at 6658) by debbugs.gnu.org; 23 Jul 2010 22:20:58 +0000 Received: from localhost ([127.0.0.1] helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1OcQbu-0007pl-9M for submit@debbugs.gnu.org; Fri, 23 Jul 2010 18:20:57 -0400 Received: from kiwi.cs.ucla.edu ([131.179.128.19]) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1OcQbo-0007pW-Su for 6658@debbugs.gnu.org; Fri, 23 Jul 2010 18:20:53 -0400 Received: from [131.179.64.200] (Penguin.CS.UCLA.EDU [131.179.64.200]) by kiwi.cs.ucla.edu (8.13.8+Sun/8.13.8/UCLACS-6.0) with ESMTP id o6NMKjsu003710; Fri, 23 Jul 2010 15:20:46 -0700 (PDT) Message-ID: <4C4A15BD.1090402@cs.ucla.edu> Date: Fri, 23 Jul 2010 15:20:45 -0700 From: Paul Eggert Organization: UCLA Computer Science Department User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.1.10) Gecko/20100527 Thunderbird/3.0.5 MIME-Version: 1.0 To: Jim Meyering Subject: Re: bug#6658: [PATCH] randread: don't require -lrt References: <4C40CC76.2050407@cs.ucla.edu> <87zkxrqcmu.fsf@meyering.net> In-Reply-To: <87zkxrqcmu.fsf@meyering.net> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-Spam-Score: -2.1 (--) X-Debbugs-Envelope-To: 6658 Cc: 6658@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.11 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -3.4 (---) >> 3. We could get about 2X CPU performance on 64-bit machines by using >> ISAAC64 instead of ISAAC. >> > These are all welcome changes, and the patch for (1) looks fine. OK, here's the change for (3), which I just pushed. I verified that it improved performance of random-number generation by 2x on my 64-bit host (RHEL 5 host with a Xeon E5620; the benchmark performance improvement was actually a tiny bit better than 2x speedup). On this platform isaac_refill now generates pseudorandom data at around 2.5 GB/s, which is quite a bit faster than /dev/urandom's 7.5 MB/s (as measured with dd). On 32-bit hosts the code behaves as before, though I expect it runs a bit faster than before (I haven't checked this). Perhaps this stuff should be moved to gnulib? I can't recall if there was any good reason to leave it in coreutils. >From bcc6639ccd1e09744c12319f9e198e81a18511ea Mon Sep 17 00:00:00 2001 From: Paul R. Eggert Date: Fri, 23 Jul 2010 15:07:27 -0700 Subject: [PATCH] randread: run 2x faster on 64-bit hosts, don't assume no padding bits * gl/lib/rand-isaac.c: Remove the I/O; this belongs elsewhere. Add support for ISAAC64. Port to hosts with padding bits. Add self to author list. Include , for CHAR_BIT. Don't include string.h, sys/time.h, unistd.h. (min, just): New functions. (IF32): New macros. (ind, ISAAC_STEP, isaac_refill, mix, isaac_init, isaac_seed): Add support for ISAAC64. Port to hosts with padding bits. (ind): Now an inline function rather than a macro; no need for it to be a macro with modern compilers. (ISAAC_STEP): Renamed from isaac_step, since it's not function-like. Don't bother to pass args that are always the same. All uses changed. (ISAAC_STEP, ISAAC_SEED): Move to inside the only function body that can use it. (ISAAC_MIX): Renamed from isaac_mix, since it's now a macro and is no longer function-like. Don't bother saving and restoring state; no longer needed now that we're not a function. All uses changed. (isaac_seed_start, isaac_seed_data, isaac_seed_finish): Remove. (isaac_seed): Take just the one arg; the caller now sets s->m. * gl/lib/rand-isaac.h: Use _GL_RAND_ISAAC_H to protect, instead of RAND_ISAAC_H. Try out " #" rather than "# " for indenting. (ISAAC_BITS_LOG, ISAAC_BITS): New macros. (ISAAC_WORDS_LOG): Renamed from ISAAC_LOG. (isaac_word): New type. All uses of uint32_t changed to isaac_word, to support ISAAC64. (struct isaac_state): Rename member MM to M, and make it public. (isaac_seed, isaac_refill): Adjust to new API. * gl/lib/randread.c: Include sys/time.h. (get_nonce): New function, containing the nonce stuff that used to be in rand-isaac.c but better belongs here. (randread_new): Use it. * gl/modules/randread (Depends-on): Add inline. * gl/modules/randread-tests: New file. * gl/tests/test-rand-isaac.c: New file. --- gl/lib/rand-isaac.c | 373 ++++++++++++---------------- gl/lib/rand-isaac.h | 53 +++-- gl/lib/randread.c | 60 ++++- gl/modules/randread | 1 + gl/modules/randread-tests | 10 + gl/tests/test-rand-isaac.c | 604 ++++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 862 insertions(+), 239 deletions(-) create mode 100644 gl/modules/randread-tests create mode 100644 gl/tests/test-rand-isaac.c diff --git a/gl/lib/rand-isaac.c b/gl/lib/rand-isaac.c index f73144a..efa9ba2 100644 --- a/gl/lib/rand-isaac.c +++ b/gl/lib/rand-isaac.c @@ -1,4 +1,4 @@ -/* Bob Jenkins's cryptographic random number generator, ISAAC. +/* Bob Jenkins's cryptographic random number generators, ISAAC and ISAAC64. Copyright (C) 1999-2006, 2009-2010 Free Software Foundation, Inc. Copyright (C) 1997, 1998, 1999 Colin Plumb. @@ -16,7 +16,7 @@ You should have received a copy of the GNU General Public License along with this program. If not, see . - Written by Colin Plumb. */ + Written by Colin Plumb and Paul Eggert. */ /* * -------------------------------------------------------------------- @@ -34,59 +34,90 @@ #include "rand-isaac.h" -#include -#include -#include +#include +/* The minimum of two sizes A and B. */ +static inline size_t +min (size_t a, size_t b) +{ + return (a < b ? a : b); +} -/* This index operation is more efficient on many processors */ -#define ind(mm, x) \ - (* (uint32_t *) ((char *) (mm) \ - + ((x) & (ISAAC_WORDS - 1) * sizeof (uint32_t)))) +/* A if 32-bit ISAAC, B if 64-bit. This is a macro, not an inline + function, to prevent undefined behavior if the unused argument + shifts by more than a word width. */ +#define IF32(a, b) (ISAAC_BITS == 32 ? (a) : (b)) -/* - * The central step. This uses two temporaries, x and y. mm is the - * whole state array, while m is a pointer to the current word. off is - * the offset from m to the word ISAAC_WORDS/2 words away in the mm array, - * i.e. +/- ISAAC_WORDS/2. - */ -#define isaac_step(mix, a, b, mm, m, off, r) \ -( \ - a = ((a) ^ (mix)) + (m)[off], \ - x = *(m), \ - *(m) = y = ind (mm, x) + (a) + (b), \ - *(r) = b = ind (mm, (y) >> ISAAC_LOG) + x \ -) +/* Discard bits outside the desired range. On typical machines, any + decent compiler should optimize this function call away to nothing. + But machines with pad bits in integers may need to do more work. */ +static inline isaac_word +just (isaac_word a) +{ + isaac_word desired_bits = ((isaac_word) 1 << 1 << (ISAAC_BITS - 1)) - 1; + return a & desired_bits; +} -/* Use and update *S to generate random data to fill R. */ -void -isaac_refill (struct isaac_state *s, uint32_t r[ISAAC_WORDS]) +/* The index operation. On typical machines whose words are exactly + the right size, this is optimized to a mask, an addition, and an + indirect load. Atypical machines need more work. */ +static inline isaac_word +ind (isaac_word const *m, isaac_word x) { - uint32_t a, b; /* Caches of a and b */ - uint32_t x, y; /* Temps needed by isaac_step macro */ - uint32_t *m = s->mm; /* Pointer into state array */ + return (sizeof *m * CHAR_BIT == ISAAC_BITS + ? (* (isaac_word *) ((char *) m + + (x & ((ISAAC_WORDS - 1) * sizeof *m)))) + : m[(x / (ISAAC_BITS / CHAR_BIT)) & (ISAAC_WORDS - 1)]); +} - a = s->a; - b = s->b + (++s->c); +/* Use and update *S to generate random data to fill RESULT. */ +void +isaac_refill (struct isaac_state *s, isaac_word result[ISAAC_WORDS]) +{ + /* Caches of S->a and S->b. */ + isaac_word a = s->a; + isaac_word b = s->b + (++s->c); + + /* Pointers into state array and into result. */ + isaac_word *m = s->m; + isaac_word *r = result; + + enum { HALF = ISAAC_WORDS / 2 }; + + /* The central step. S->m is the whole state array, while M is a + pointer to the current word. OFF is the offset from M to the + word ISAAC_WORDS/2 words away in the SM array, i.e. +/- + ISAAC_WORDS/2. A and B are state variables, and R the result. + This updates A, B, M[I], and R[I]. */ + #define ISAAC_STEP(i, off, mix) \ + { \ + isaac_word x, y; \ + a = (IF32 (a, 0) ^ (mix)) + m[off + (i)]; \ + x = m[i]; \ + m[i] = y = ind (s->m, x) + a + b; \ + r[i] = b = just (ind (s->m, y >> ISAAC_WORDS_LOG) + x); \ + } do { - isaac_step (a << 13, a, b, s->mm, m, ISAAC_WORDS / 2, r); - isaac_step (a >> 6, a, b, s->mm, m + 1, ISAAC_WORDS / 2, r + 1); - isaac_step (a << 2, a, b, s->mm, m + 2, ISAAC_WORDS / 2, r + 2); - isaac_step (a >> 16, a, b, s->mm, m + 3, ISAAC_WORDS / 2, r + 3); + ISAAC_STEP (0, HALF, IF32 ( a << 13, ~ (a ^ (a << 21)))); + ISAAC_STEP (1, HALF, IF32 (just (a) >> 6, a ^ (just (a) >> 5))); + ISAAC_STEP (2, HALF, IF32 ( a << 2, a ^ ( a << 12))); + ISAAC_STEP (3, HALF, IF32 (just (a) >> 16, a ^ (just (a) >> 33))); r += 4; } - while ((m += 4) < s->mm + ISAAC_WORDS / 2); + while ((m += 4) < s->m + HALF); + do { - isaac_step (a << 13, a, b, s->mm, m, -ISAAC_WORDS / 2, r); - isaac_step (a >> 6, a, b, s->mm, m + 1, -ISAAC_WORDS / 2, r + 1); - isaac_step (a << 2, a, b, s->mm, m + 2, -ISAAC_WORDS / 2, r + 2); - isaac_step (a >> 16, a, b, s->mm, m + 3, -ISAAC_WORDS / 2, r + 3); + ISAAC_STEP (0, -HALF, IF32 ( a << 13, ~ (a ^ (a << 21)))); + ISAAC_STEP (1, -HALF, IF32 (just (a) >> 6, a ^ (just (a) >> 5))); + ISAAC_STEP (2, -HALF, IF32 ( a << 2, a ^ ( a << 12))); + ISAAC_STEP (3, -HALF, IF32 (just (a) >> 16, a ^ (just (a) >> 33))); r += 4; } - while ((m += 4) < s->mm + ISAAC_WORDS); + while ((m += 4) < s->m + ISAAC_WORDS); + s->a = a; s->b = b; } @@ -95,223 +126,133 @@ isaac_refill (struct isaac_state *s, uint32_t r[ISAAC_WORDS]) * The basic seed-scrambling step for initialization, based on Bob * Jenkins' 256-bit hash. */ -#define mix(a,b,c,d,e,f,g,h) \ - ( a ^= b << 11, d += a, \ - b += c, b ^= c >> 2, e += b, \ - c += d, c ^= d << 8, f += c, \ - d += e, d ^= e >> 16, g += d, \ - e += f, e ^= f << 10, h += e, \ - f += g, f ^= g >> 4, a += f, \ - g += h, g ^= h << 8, b += g, \ - h += a, h ^= a >> 9, c += h, \ - a += b ) - -/* The basic ISAAC initialization pass. */ -static void -isaac_mix (struct isaac_state *s, uint32_t const seed[/* ISAAC_WORDS */]) -{ - int i; - uint32_t a = s->iv[0]; - uint32_t b = s->iv[1]; - uint32_t c = s->iv[2]; - uint32_t d = s->iv[3]; - uint32_t e = s->iv[4]; - uint32_t f = s->iv[5]; - uint32_t g = s->iv[6]; - uint32_t h = s->iv[7]; - - for (i = 0; i < ISAAC_WORDS; i += 8) - { - a += seed[i]; - b += seed[i + 1]; - c += seed[i + 2]; - d += seed[i + 3]; - e += seed[i + 4]; - f += seed[i + 5]; - g += seed[i + 6]; - h += seed[i + 7]; - - mix (a, b, c, d, e, f, g, h); - - s->mm[i] = a; - s->mm[i + 1] = b; - s->mm[i + 2] = c; - s->mm[i + 3] = d; - s->mm[i + 4] = e; - s->mm[i + 5] = f; - s->mm[i + 6] = g; - s->mm[i + 7] = h; +#if ISAAC_BITS == 32 + #define mix(a, b, c, d, e, f, g, h) \ + { \ + a ^= b << 11; d += a; \ + b += c; b ^= just (c) >> 2; e += b; \ + c += d; c ^= d << 8; f += c; \ + d += e; d ^= just (e) >> 16; g += d; \ + e += f; e ^= f << 10; h += e; \ + f += g; f ^= just (g) >> 4; a += f; \ + g += h; g ^= h << 8; b += g; \ + h += a; h ^= just (a) >> 9; c += h; \ + a += b; \ + } +#else + #define mix(a, b, c, d, e, f, g, h) \ + { \ + a -= e; f ^= just (h) >> 9; h += a; \ + b -= f; g ^= a << 9; a += b; \ + c -= g; h ^= just (b) >> 23; b += c; \ + d -= h; a ^= c << 15; c += d; \ + e -= a; b ^= just (d) >> 14; d += e; \ + f -= b; c ^= e << 20; e += f; \ + g -= c; d ^= just (f) >> 17; f += g; \ + h -= d; e ^= g << 14; g += h; \ } +#endif - s->iv[0] = a; - s->iv[1] = b; - s->iv[2] = c; - s->iv[3] = d; - s->iv[4] = e; - s->iv[5] = f; - s->iv[6] = g; - s->iv[7] = h; -} + +/* The basic ISAAC initialization pass. */ +#define ISAAC_MIX(s, a, b, c, d, e, f, g, h, seed) \ + { \ + int i; \ + \ + for (i = 0; i < ISAAC_WORDS; i += 8) \ + { \ + a += seed[i]; \ + b += seed[i + 1]; \ + c += seed[i + 2]; \ + d += seed[i + 3]; \ + e += seed[i + 4]; \ + f += seed[i + 5]; \ + g += seed[i + 6]; \ + h += seed[i + 7]; \ + mix (a, b, c, d, e, f, g, h); \ + s->m[i] = a; \ + s->m[i + 1] = b; \ + s->m[i + 2] = c; \ + s->m[i + 3] = d; \ + s->m[i + 4] = e; \ + s->m[i + 5] = f; \ + s->m[i + 6] = g; \ + s->m[i + 7] = h; \ + } \ + } #if 0 /* Provided for reference only; not used in this code */ /* * Initialize the ISAAC RNG with the given seed material. * Its size MUST be a multiple of ISAAC_BYTES, and may be - * stored in the s->mm array. + * stored in the s->m array. * * This is a generalization of the original ISAAC initialization code * to support larger seed sizes. For seed sizes of 0 and ISAAC_BYTES, * it is identical. */ static void -isaac_init (struct isaac_state *s, uint32_t const *seed, size_t seedsize) +isaac_init (struct isaac_state *s, isaac_word const *seed, size_t seedsize) { - static uint32_t const iv[8] = - { - 0x1367df5a, 0x95d90059, 0xc3163e4b, 0x0f421ad8, - 0xd92a4a78, 0xa51a3c49, 0xc4efea1b, 0x30609119}; - int i; + isaac_word a, b, c, d, e, f, g, h; -# if 0 - /* The initialization of iv is a precomputed form of: */ - for (i = 0; i < 7; i++) - iv[i] = 0x9e3779b9; /* the golden ratio */ - for (i = 0; i < 4; ++i) /* scramble it */ - mix (iv[0], iv[1], iv[2], iv[3], iv[4], iv[5], iv[6], iv[7]); -# endif + a = b = c = d = e = f = g = h = /* the golden ratio */ + IF32 (UINT32_C (0x9e3779b9), UINT64_C (0x9e3779b97f4a7c13)); + for (int i = 0; i < 4; i++) /* scramble it */ + mix (a, b, c, d, e, f, g, h); s->a = s->b = s->c = 0; - for (i = 0; i < 8; i++) - s->iv[i] = iv[i]; - if (seedsize) { /* First pass (as in reference ISAAC code) */ - isaac_mix (s, seed); + ISAAC_MIX (s, a, b, c, d, e, f, g, h, seed); /* Second and subsequent passes (extension to ISAAC) */ while (seedsize -= ISAAC_BYTES) { seed += ISAAC_WORDS; for (i = 0; i < ISAAC_WORDS; i++) - s->mm[i] += seed[i]; - isaac_mix (s, s->mm); + s->m[i] += seed[i]; + ISAAC_MIX (s, a, b, c, d, e, f, g, h, s->m); } } else { /* The no seed case (as in reference ISAAC code) */ for (i = 0; i < ISAAC_WORDS; i++) - s->mm[i] = 0; + s->m[i] = 0; } /* Final pass */ - isaac_mix (s, s->mm); + ISAAC_MIX (s, a, b, c, d, e, f, g, h, s->m); } #endif -/* Initialize *S to a somewhat-random value. The first SEEDED bytes - in S->mm are already seeded with random data. */ -static void -isaac_seed_start (struct isaac_state *s, size_t seeded) +/* Initialize *S to a somewhat-random value, derived from a seed + stored in S->m. */ +void +isaac_seed (struct isaac_state *s) { - static uint32_t const iv[8] = - { - 0x1367df5a, 0x95d90059, 0xc3163e4b, 0x0f421ad8, - 0xd92a4a78, 0xa51a3c49, 0xc4efea1b, 0x30609119 - }; + isaac_word a = IF32 (UINT32_C (0x1367df5a), UINT64_C (0x647c4677a2884b7c)); + isaac_word b = IF32 (UINT32_C (0x95d90059), UINT64_C (0xb9f8b322c73ac862)); + isaac_word c = IF32 (UINT32_C (0xc3163e4b), UINT64_C (0x8c0ea5053d4712a0)); + isaac_word d = IF32 (UINT32_C (0x0f421ad8), UINT64_C (0xb29b2e824a595524)); + isaac_word e = IF32 (UINT32_C (0xd92a4a78), UINT64_C (0x82f053db8355e0ce)); + isaac_word f = IF32 (UINT32_C (0xa51a3c49), UINT64_C (0x48fe4a0fa5a09315)); + isaac_word g = IF32 (UINT32_C (0xc4efea1b), UINT64_C (0xae985bf2cbfc89ed)); + isaac_word h = IF32 (UINT32_C (0x30609119), UINT64_C (0x98f5704f6c44c0ab)); #if 0 - /* The initialization of iv is a precomputed form of: */ - int i; - for (i = 0; i < 7; i++) - iv[i] = 0x9e3779b9; /* the golden ratio */ - for (i = 0; i < 4; ++i) /* scramble it */ - mix (iv[0], iv[1], iv[2], iv[3], iv[4], iv[5], iv[6], iv[7]); + /* The initialization of a through h is a precomputed form of: */ + a = b = c = d = e = f = g = h = /* the golden ratio */ + IF32 (UINT32_C (0x9e3779b9), UINT64_C (0x9e3779b97f4a7c13)); + for (int i = 0; i < 4; i++) /* scramble it */ + mix (a, b, c, d, e, f, g, h); #endif - memset ((char *) s->mm + seeded, 0, sizeof s->mm - seeded); - memcpy (s->iv, iv, sizeof s->iv); - - /* s->c gets used for a data pointer during the seeding phase */ - s->a = s->b = 0; - s->c = seeded; -} - -/* Add a buffer of seed material. */ -static void -isaac_seed_data (struct isaac_state *s, void const *buffer, size_t size) -{ - unsigned char const *buf = buffer; - unsigned char *p; - size_t avail; - size_t i; - - avail = sizeof s->mm - s->c; /* s->c is used as a write pointer */ - - /* Do any full buffers that are necessary */ - while (size > avail) - { - p = (unsigned char *) s->mm + s->c; - for (i = 0; i < avail; i++) - p[i] ^= buf[i]; - buf += avail; - size -= avail; - isaac_mix (s, s->mm); - s->c = 0; - avail = sizeof s->mm; - } - - /* And the final partial block */ - p = (unsigned char *) s->mm + s->c; - for (i = 0; i < size; i++) - p[i] ^= buf[i]; - s->c = size; -} - - -/* End of seeding phase; get everything ready to produce output. */ -static void -isaac_seed_finish (struct isaac_state *s) -{ - isaac_mix (s, s->mm); - isaac_mix (s, s->mm); - /* Now reinitialize c to start things off right */ - s->c = 0; -} -#define ISAAC_SEED(s,x) isaac_seed_data (s, &(x), sizeof (x)) - -/* Initialize *S to a somewhat-random value; this starts seeding, - seeds with somewhat-random data, and finishes seeding. If FD is - nonnegative, seed by reading at most BYTES_BOUNDS bytes from it. */ -void -isaac_seed (struct isaac_state *s, int fd, size_t bytes_bound) -{ - /* Get some data from FD if available. */ - ssize_t seeded = 0; - if (0 <= fd) - { - if (sizeof s->mm < bytes_bound) - bytes_bound = sizeof s->mm; - seeded = read (fd, s->mm, bytes_bound); - if (seeded < 0) - seeded = 0; - } - - isaac_seed_start (s, seeded); - - if (seeded < sizeof s->mm) - { - { pid_t t = getpid (); ISAAC_SEED (s, t); } - { pid_t t = getppid (); ISAAC_SEED (s, t); } - { uid_t t = getuid (); ISAAC_SEED (s, t); } - { gid_t t = getgid (); ISAAC_SEED (s, t); } + /* Mix S->m so that every part of the seed affects every part of the + state. */ + ISAAC_MIX (s, a, b, c, d, e, f, g, h, s->m); + ISAAC_MIX (s, a, b, c, d, e, f, g, h, s->m); - { - struct timeval t; - gettimeofday (&t, NULL); - ISAAC_SEED (s, t); - } - } - - isaac_seed_finish (s); + s->a = s->b = s->c = 0; } diff --git a/gl/lib/rand-isaac.h b/gl/lib/rand-isaac.h index 052dc9f..6e5af06 100644 --- a/gl/lib/rand-isaac.h +++ b/gl/lib/rand-isaac.h @@ -1,4 +1,4 @@ -/* Bob Jenkins's cryptographic random number generator, ISAAC. +/* Bob Jenkins's cryptographic random number generators, ISAAC and ISAAC64. Copyright (C) 1999-2005, 2009-2010 Free Software Foundation, Inc. Copyright (C) 1997, 1998, 1999 Colin Plumb. @@ -16,29 +16,50 @@ You should have received a copy of the GNU General Public License along with this program. If not, see . - Written by Colin Plumb. */ + Written by Colin Plumb and Paul Eggert. */ -#ifndef RAND_ISAAC_H -# define RAND_ISAAC_H +#ifndef _GL_RAND_ISAAC_H +#define _GL_RAND_ISAAC_H -# include -# include +#include +#include -/* Size of the state tables to use. ISAAC_LOG should be at least 3, +/* Log base 2 of the number of useful bits in an ISAAC word. It must + be either 5 or 6. By default, this uses a value that should be + faster for this architecture. */ +#ifndef ISAAC_BITS_LOG + #if SIZE_MAX >> 31 >> 31 < 3 /* SIZE_MAX < 2**64 - 1 */ + #define ISAAC_BITS_LOG 5 + #else + #define ISAAC_BITS_LOG 6 + #endif +#endif + +/* The number of bits in an ISAAC word. */ +#define ISAAC_BITS (1 << ISAAC_BITS_LOG) + +#if ISAAC_BITS == 32 + typedef uint_least32_t isaac_word; +#else + typedef uint_least64_t isaac_word; +#endif + +/* Size of the state tables to use. ISAAC_WORDS_LOG should be at least 3, and smaller values give less security. */ -# define ISAAC_LOG 8 -# define ISAAC_WORDS (1 << ISAAC_LOG) -# define ISAAC_BYTES (ISAAC_WORDS * sizeof (uint32_t)) +#define ISAAC_WORDS_LOG 8 +#define ISAAC_WORDS (1 << ISAAC_WORDS_LOG) +#define ISAAC_BYTES (ISAAC_WORDS * sizeof (isaac_word)) -/* RNG state variables. The members of this structure are private. */ +/* State variables for the random number generator. The M member + should be seeded with nonce data before calling isaac_seed. The + other members are private. */ struct isaac_state { - uint32_t mm[ISAAC_WORDS]; /* Main state array */ - uint32_t iv[8]; /* Seeding initial vector */ - uint32_t a, b, c; /* Extra index variables */ + isaac_word m[ISAAC_WORDS]; /* Main state array */ + isaac_word a, b, c; /* Extra variables */ }; -void isaac_seed (struct isaac_state *, int, size_t); -void isaac_refill (struct isaac_state *, uint32_t[ISAAC_WORDS]); +void isaac_seed (struct isaac_state *); +void isaac_refill (struct isaac_state *, isaac_word[ISAAC_WORDS]); #endif diff --git a/gl/lib/randread.c b/gl/lib/randread.c index a681c8d..dcaeee4 100644 --- a/gl/lib/randread.c +++ b/gl/lib/randread.c @@ -31,6 +31,7 @@ #include #include #include +#include #include #include "gettext.h" @@ -106,7 +107,7 @@ struct randread_source /* Up to a buffer's worth of pseudorandom data. */ union { - uint32_t w[ISAAC_WORDS]; + isaac_word w[ISAAC_WORDS]; unsigned char b[ISAAC_BYTES]; } data; } isaac; @@ -139,6 +140,52 @@ simple_new (FILE *source, void const *handler_arg) return s; } +/* Put a nonce value into BUFFER, with size BUFSIZE, but do not get + more than BYTES_BOUND bytes' worth of random information from any + nonce device. */ + +static void +get_nonce (void *buffer, size_t bufsize, size_t bytes_bound) +{ + char *buf = buffer; + ssize_t seeded = 0; + + /* Get some data from FD if available. */ + int fd = open (NAME_OF_NONCE_DEVICE, O_RDONLY | O_BINARY); + if (0 <= fd) + { + seeded = read (fd, buf, MIN (bufsize, bytes_bound)); + if (seeded < 0) + seeded = 0; + close (fd); + } + + /* If there's no nonce device, use a poor approximation + by getting the time of day, etc. */ +# define ISAAC_SEED(type, initialize_v) \ + if (seeded < bufsize) \ + { \ + type v; \ + size_t nbytes = MIN (sizeof v, bufsize - seeded); \ + initialize_v; \ + memcpy (buf + seeded, &v, nbytes); \ + seeded += nbytes; \ + } + ISAAC_SEED (struct timeval, gettimeofday (&v, NULL)); + ISAAC_SEED (pid_t, v = getpid ()); + ISAAC_SEED (pid_t, v = getppid ()); + ISAAC_SEED (uid_t, v = getuid ()); + ISAAC_SEED (uid_t, v = getgid ()); + +#ifdef lint + /* Normally we like having the extra randomness from uninitialized + parts of BUFFER. However, omit this randomness if we want to + avoid false-positives from memory-checking debugging tools. */ + memset (buf + seeded, 0, bufsize - seeded); +#endif +} + + /* Create and initialize a random data source from NAME, or use a reasonable default source if NAME is null. BYTES_BOUND is an upper bound on the number of bytes that will be needed. If zero, it is a @@ -170,11 +217,10 @@ randread_new (char const *name, size_t bytes_bound) setvbuf (source, s->buf.c, _IOFBF, MIN (sizeof s->buf.c, bytes_bound)); else { - int nonce_device = open (NAME_OF_NONCE_DEVICE, O_RDONLY | O_BINARY); s->buf.isaac.buffered = 0; - isaac_seed (&s->buf.isaac.state, nonce_device, bytes_bound); - if (0 <= nonce_device) - close (nonce_device); + get_nonce (s->buf.isaac.state.m, sizeof s->buf.isaac.state.m, + bytes_bound); + isaac_seed (&s->buf.isaac.state); } return s; @@ -245,9 +291,9 @@ readisaac (struct isaac *isaac, unsigned char *p, size_t size) /* If P is aligned, write to *P directly to avoid the overhead of copying from the buffer. */ - if (ALIGNED_POINTER (p, uint32_t)) + if (ALIGNED_POINTER (p, isaac_word)) { - uint32_t *wp = (uint32_t *) p; + isaac_word *wp = (isaac_word *) p; while (ISAAC_BYTES <= size) { isaac_refill (&isaac->state, wp); diff --git a/gl/modules/randread b/gl/modules/randread index efc7958..1c4a905 100644 --- a/gl/modules/randread +++ b/gl/modules/randread @@ -10,6 +10,7 @@ lib/randread.h Depends-on: error exitfail +inline fopen-safer gettimeofday quotearg diff --git a/gl/modules/randread-tests b/gl/modules/randread-tests new file mode 100644 index 0000000..b608ac6 --- /dev/null +++ b/gl/modules/randread-tests @@ -0,0 +1,10 @@ +Files: +tests/test-rand-isaac.c + +Depends-on: + +configure.ac: + +Makefile.am: +TESTS += test-rand-isaac +check_PROGRAMS += test-rand-isaac diff --git a/gl/tests/test-rand-isaac.c b/gl/tests/test-rand-isaac.c new file mode 100644 index 0000000..330b18f --- /dev/null +++ b/gl/tests/test-rand-isaac.c @@ -0,0 +1,604 @@ +/* Test the ISAAC or ISAAC64 pseudorandom number generator. + + Copyright (C) 2010 Free Software Foundation, Inc. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . */ + +/* Written by Paul Eggert. */ + +#include + +#include "rand-isaac.h" + +#include +#include +#include +#include +#include + +/* FIXME: once/if in gnulib, use #include "macros.h" in place of this */ +#define ASSERT(expr) \ + do \ + { \ + if (!(expr)) \ + { \ + fprintf (stderr, "%s:%d: assertion failed\n", __FILE__, __LINE__); \ + fflush (stderr); \ + abort (); \ + } \ + } \ + while (0) + +/* This expected output was generated by running the programs in + , as last modified + on 2010-01-22. The 32-bit numbers were output by rand.c, and the + 64-bit by isaac64.c, both on x86, as those programs are not + portable to 64-bit platforms. */ + +static isaac_word const expected[2][ISAAC_WORDS] = + { + #if ISAAC_BITS == 32 + { + UINT32_C (0xf650e4c8), UINT32_C (0xe448e96d), + UINT32_C (0x98db2fb4), UINT32_C (0xf5fad54f), + UINT32_C (0x433f1afb), UINT32_C (0xedec154a), + UINT32_C (0xd8370487), UINT32_C (0x46ca4f9a), + UINT32_C (0x5de3743e), UINT32_C (0x88381097), + UINT32_C (0xf1d444eb), UINT32_C (0x823cedb6), + UINT32_C (0x6a83e1e0), UINT32_C (0x4a5f6355), + UINT32_C (0xc7442433), UINT32_C (0x25890e2e), + UINT32_C (0x7452e319), UINT32_C (0x57161df6), + UINT32_C (0x38a824f3), UINT32_C (0x002ed713), + UINT32_C (0x29f55449), UINT32_C (0x51c08d83), + UINT32_C (0xd78cb99e), UINT32_C (0xa0cc74f3), + UINT32_C (0x8f651659), UINT32_C (0xcbc8b7c2), + UINT32_C (0xf5f71c69), UINT32_C (0x12ad6419), + UINT32_C (0xe5792e1b), UINT32_C (0x860536b8), + UINT32_C (0x09b3ce98), UINT32_C (0xd45d6d81), + UINT32_C (0xf3b26129), UINT32_C (0x17e38f85), + UINT32_C (0x29cf72ce), UINT32_C (0x349947b0), + UINT32_C (0xc998f9ff), UINT32_C (0xb5e13dae), + UINT32_C (0x32ae2a2b), UINT32_C (0xf7cf814c), + UINT32_C (0x8ebfa303), UINT32_C (0xcf22e064), + UINT32_C (0x0b923200), UINT32_C (0xeca4d58a), + UINT32_C (0xef53cec4), UINT32_C (0xd0f7b37d), + UINT32_C (0x9c411a2a), UINT32_C (0xffdf8a80), + UINT32_C (0xb40e27bc), UINT32_C (0xb4d2f976), + UINT32_C (0x44b89b08), UINT32_C (0xf37c71d5), + UINT32_C (0x1a70e7e9), UINT32_C (0x0bdb9c30), + UINT32_C (0x60dc5207), UINT32_C (0xb3c3f24b), + UINT32_C (0xd7386806), UINT32_C (0x229749b5), + UINT32_C (0x4e232cd0), UINT32_C (0x91dabc65), + UINT32_C (0xa70e1101), UINT32_C (0x8b87437e), + UINT32_C (0x5781414f), UINT32_C (0xcdbc62e2), + UINT32_C (0x8107c9ff), UINT32_C (0x69d2e4ae), + UINT32_C (0x3b18e752), UINT32_C (0xb143b688), + UINT32_C (0x6f4e0772), UINT32_C (0x95138769), + UINT32_C (0x943c3c74), UINT32_C (0xafc17a97), + UINT32_C (0x0fd43963), UINT32_C (0x6a529b0b), + UINT32_C (0xd8c58a6a), UINT32_C (0xa8bcc22d), + UINT32_C (0x2db35dfe), UINT32_C (0xa7a2f402), + UINT32_C (0x6cb167db), UINT32_C (0x538e1f4e), + UINT32_C (0x7275e277), UINT32_C (0x1d3b8e97), + UINT32_C (0xecc5dc91), UINT32_C (0x15e3a5b9), + UINT32_C (0x03696614), UINT32_C (0x30ab93ec), + UINT32_C (0xac9fe69d), UINT32_C (0x7bc76811), + UINT32_C (0x60eda8da), UINT32_C (0x28833522), + UINT32_C (0xd5295ebc), UINT32_C (0x5adb60e7), + UINT32_C (0xf7e1cdd0), UINT32_C (0x97166d14), + UINT32_C (0xb67ec13a), UINT32_C (0x210f3925), + UINT32_C (0x64af0fef), UINT32_C (0x0d028684), + UINT32_C (0x3aea3dec), UINT32_C (0xb058bafb), + UINT32_C (0xb8b0ccfc), UINT32_C (0xf2b5cc05), + UINT32_C (0xe3a662d9), UINT32_C (0x814bc24c), + UINT32_C (0x2364a1aa), UINT32_C (0x37c0ed05), + UINT32_C (0x2b36505c), UINT32_C (0x451e7ec8), + UINT32_C (0x5d2a542f), UINT32_C (0xe43d0fbb), + UINT32_C (0x91c8d925), UINT32_C (0x60d4d5f8), + UINT32_C (0x12a0594b), UINT32_C (0x9e8a51da), + UINT32_C (0xcd49ebdb), UINT32_C (0x1b0dcdc1), + UINT32_C (0xcd57c7f7), UINT32_C (0xe6344451), + UINT32_C (0x7ded386f), UINT32_C (0x2f36fa86), + UINT32_C (0xa6d12101), UINT32_C (0x33bc405d), + UINT32_C (0xb388d96c), UINT32_C (0xdb6dbe96), + UINT32_C (0xfe29661c), UINT32_C (0x13edc0cb), + UINT32_C (0xcb0eee4a), UINT32_C (0x70cc94ae), + UINT32_C (0xde11ed34), UINT32_C (0x0606cf9f), + UINT32_C (0x3a6ce389), UINT32_C (0x23d74f4e), + UINT32_C (0xa37f63ff), UINT32_C (0x917bdec2), + UINT32_C (0xd73f72d4), UINT32_C (0x0e7e0e67), + UINT32_C (0x3d77d9a2), UINT32_C (0x13add922), + UINT32_C (0x8891b3db), UINT32_C (0x01a9bd70), + UINT32_C (0x56a001e3), UINT32_C (0xd51f093d), + UINT32_C (0xcc033ce3), UINT32_C (0x5ad0d3b0), + UINT32_C (0x34105a8c), UINT32_C (0x6a123f57), + UINT32_C (0xbd2e5024), UINT32_C (0x7364944b), + UINT32_C (0xe89b1a3b), UINT32_C (0x21835c4d), + UINT32_C (0x9f39e2d9), UINT32_C (0xd405ded8), + UINT32_C (0x294d37e5), UINT32_C (0xbccaaeed), + UINT32_C (0x35a124b5), UINT32_C (0x6708a2bc), + UINT32_C (0xb00960ba), UINT32_C (0x2a98121a), + UINT32_C (0x4d8fae82), UINT32_C (0x0bb3263f), + UINT32_C (0x12595a19), UINT32_C (0x6a107589), + UINT32_C (0x0809e494), UINT32_C (0x21c171ec), + UINT32_C (0x884d6825), UINT32_C (0x14c8009b), + UINT32_C (0xb0b84e7b), UINT32_C (0x03fb88f4), + UINT32_C (0x28e7cb78), UINT32_C (0x9388b13b), + UINT32_C (0xdd2dc1d5), UINT32_C (0x848f520a), + UINT32_C (0x07c28cd1), UINT32_C (0x68a39358), + UINT32_C (0x72c9137d), UINT32_C (0x127dd430), + UINT32_C (0xc613f157), UINT32_C (0x8c2f0d55), + UINT32_C (0xf7d3f39f), UINT32_C (0x309bfb78), + UINT32_C (0x8406b137), UINT32_C (0x46c0a6f5), + UINT32_C (0x3718d597), UINT32_C (0x08607f04), + UINT32_C (0x76904b6d), UINT32_C (0x04db4e13), + UINT32_C (0xcd7411a7), UINT32_C (0xb510ce0e), + UINT32_C (0xbfc7f7cc), UINT32_C (0xb83f957a), + UINT32_C (0xfdfef62d), UINT32_C (0xc35e4580), + UINT32_C (0x3ff1e524), UINT32_C (0x4112d96c), + UINT32_C (0x02c9b944), UINT32_C (0xd5990dfb), + UINT32_C (0xe7e26581), UINT32_C (0x0d9c7e7e), + UINT32_C (0x826dfa89), UINT32_C (0x66f1e0ab), + UINT32_C (0x30bcc764), UINT32_C (0xeadebeac), + UINT32_C (0xed35e5ee), UINT32_C (0x0c571a7d), + UINT32_C (0xe4f3a26a), UINT32_C (0xf7f58f7b), + UINT32_C (0xadf6bc23), UINT32_C (0x5d023e65), + UINT32_C (0x1ed3ff4e), UINT32_C (0xec46b0b6), + UINT32_C (0xd2a93b51), UINT32_C (0xe75b41c9), + UINT32_C (0x7e315aeb), UINT32_C (0x61119a5a), + UINT32_C (0x53245b79), UINT32_C (0x33f6d7b1), + UINT32_C (0xcae8deba), UINT32_C (0x50fc8194), + UINT32_C (0xafa92a6d), UINT32_C (0xc87c8006), + UINT32_C (0x4188bfcd), UINT32_C (0x8bace62e), + UINT32_C (0x78ffa568), UINT32_C (0x5597ec0f), + UINT32_C (0xb4415f7d), UINT32_C (0x08294766), + UINT32_C (0xad567643), UINT32_C (0x09c36f90), + UINT32_C (0x3dde9f39), UINT32_C (0x4a0a283c), + UINT32_C (0x18080c8e), UINT32_C (0x080c79ec), + UINT32_C (0x79ae4c10), UINT32_C (0xcb9e1563), + UINT32_C (0x7cdd662f), UINT32_C (0x62d31911), + UINT32_C (0xa4ca0cf1), UINT32_C (0x5cf824cd), + UINT32_C (0x3b708f99), UINT32_C (0x1e16614c), + UINT32_C (0xb6b9d766), UINT32_C (0x5de87abb), + UINT32_C (0x7229ea81), UINT32_C (0xd5b2d750), + UINT32_C (0x56e6cd21), UINT32_C (0xfe1e42d5), + UINT32_C (0x96da2655), UINT32_C (0xc2b9aa36), + UINT32_C (0xb8f6fd4a), UINT32_C (0x6a158d10), + UINT32_C (0x01913fd3), UINT32_C (0xaf7d1fb8), + UINT32_C (0x0b5e435f), UINT32_C (0x90c10757), + UINT32_C (0x6554abda), UINT32_C (0x7a68710f) + }, + { + UINT32_C (0x82ac484f), UINT32_C (0xd7e1c7be), + UINT32_C (0x95c85eaa), UINT32_C (0x94a302f4), + UINT32_C (0x4d3cfbda), UINT32_C (0x786b2908), + UINT32_C (0x1010b275), UINT32_C (0x82d53d12), + UINT32_C (0x21e2a51c), UINT32_C (0x3d1e9150), + UINT32_C (0xb059261d), UINT32_C (0xd0638e1a), + UINT32_C (0x31860f05), UINT32_C (0x81f2864d), + UINT32_C (0xff4cfc35), UINT32_C (0x0451516d), + UINT32_C (0xbd086f26), UINT32_C (0xbc5654c1), + UINT32_C (0x65dfa427), UINT32_C (0xa82427f5), + UINT32_C (0x582e3014), UINT32_C (0xb8d2486d), + UINT32_C (0xc79a1749), UINT32_C (0x9a1d7745), + UINT32_C (0x8766bb54), UINT32_C (0x1e04a7f7), + UINT32_C (0x3d3dff8a), UINT32_C (0xd5ec6bf4), + UINT32_C (0xdbef7d9f), UINT32_C (0x36ec0ea3), + UINT32_C (0x1feb2e4f), UINT32_C (0x15cfcc5c), + UINT32_C (0xd8c423fb), UINT32_C (0xd0ef3cc9), + UINT32_C (0xeb244925), UINT32_C (0xba5590c8), + UINT32_C (0xa5f48ac4), UINT32_C (0x33c5321c), + UINT32_C (0x613b67b2), UINT32_C (0x479c3a22), + UINT32_C (0xe21339cc), UINT32_C (0x10d210aa), + UINT32_C (0x931dd7e2), UINT32_C (0xef05ee06), + UINT32_C (0xb82f2703), UINT32_C (0xa385cb2c), + UINT32_C (0x5d67133c), UINT32_C (0x877eb7b4), + UINT32_C (0x1e3437f7), UINT32_C (0x5afb43ae), + UINT32_C (0x53c078f3), UINT32_C (0x94d90481), + UINT32_C (0x1d964589), UINT32_C (0x08063a85), + UINT32_C (0xe1322228), UINT32_C (0x1956b1e5), + UINT32_C (0x31860f13), UINT32_C (0x2e7b022f), + UINT32_C (0x21182ca3), UINT32_C (0x96f703ac), + UINT32_C (0x46819e2e), UINT32_C (0x0d28fe52), + UINT32_C (0x3724d4dc), UINT32_C (0xa0eabe6b), + UINT32_C (0xc66699fd), UINT32_C (0xc6112fdd), + UINT32_C (0x19c1e69c), UINT32_C (0x04d3658a), + UINT32_C (0x4b55dd99), UINT32_C (0x31907d62), + UINT32_C (0xf854b522), UINT32_C (0x4d678f26), + UINT32_C (0x22ae0582), UINT32_C (0xeafed133), + UINT32_C (0xe4a51d21), UINT32_C (0x84bd6dd6), + UINT32_C (0xc1a51375), UINT32_C (0x3f28ee63), + UINT32_C (0xfb737b1a), UINT32_C (0x70a1660e), + UINT32_C (0x8a8dfaa3), UINT32_C (0x1be79937), + UINT32_C (0xf7476978), UINT32_C (0x513c1764), + UINT32_C (0x531ac6bf), UINT32_C (0x12c06908), + UINT32_C (0x001cdb95), UINT32_C (0x1a4b6a53), + UINT32_C (0xd067fce5), UINT32_C (0x12b2cfb6), + UINT32_C (0x9ddb477f), UINT32_C (0x740e0066), + UINT32_C (0x39ddf25a), UINT32_C (0xcc8bfa2d), + UINT32_C (0xf1b20eaf), UINT32_C (0x64f2632c), + UINT32_C (0x9783cdee), UINT32_C (0x63bfd4d8), + UINT32_C (0x0084cfe5), UINT32_C (0x75f4e9e2), + UINT32_C (0x19b48fd0), UINT32_C (0x6c48ddd8), + UINT32_C (0x7a36af93), UINT32_C (0x71865c4c), + UINT32_C (0x9ce0199d), UINT32_C (0x867027d7), + UINT32_C (0x2cb7b77f), UINT32_C (0x84ef01da), + UINT32_C (0x72f5972f), UINT32_C (0x040f7074), + UINT32_C (0xdf9afa29), UINT32_C (0xc921f94e), + UINT32_C (0x75c08a36), UINT32_C (0x18c1ef9a), + UINT32_C (0xd649a428), UINT32_C (0xc5b71937), + UINT32_C (0x8a30738a), UINT32_C (0xd97cd348), + UINT32_C (0x858129a6), UINT32_C (0x239e3b0a), + UINT32_C (0xbbb8abc4), UINT32_C (0x80fac4c2), + UINT32_C (0xecfcf20b), UINT32_C (0xd9d711f9), + UINT32_C (0xe2a4ef71), UINT32_C (0xb5fe87c0), + UINT32_C (0xbe8b06b2), UINT32_C (0xaafef5a7), + UINT32_C (0x9c15db3b), UINT32_C (0x0aeb8165), + UINT32_C (0x4389a84a), UINT32_C (0x253b1d7a), + UINT32_C (0x19047c79), UINT32_C (0x7cdc78a2), + UINT32_C (0xd20adf03), UINT32_C (0x56f55a71), + UINT32_C (0x3e730fa8), UINT32_C (0xfd8650d8), + UINT32_C (0x959e234e), UINT32_C (0xb7546681), + UINT32_C (0xdad1b22a), UINT32_C (0x142a6e85), + UINT32_C (0x8ef4bce6), UINT32_C (0x68235b9d), + UINT32_C (0x85a13f85), UINT32_C (0x74096ae7), + UINT32_C (0xa949bea2), UINT32_C (0x29322d0d), + UINT32_C (0xd5683858), UINT32_C (0x82846526), + UINT32_C (0x403dae08), UINT32_C (0x6dd1943a), + UINT32_C (0xe1279bff), UINT32_C (0x9e7e4f04), + UINT32_C (0x1c3a4524), UINT32_C (0x484525e4), + UINT32_C (0x81d4cc5f), UINT32_C (0xe24124c0), + UINT32_C (0x037464c0), UINT32_C (0xbf1bd691), + UINT32_C (0x26ceb003), UINT32_C (0x275ead3a), + UINT32_C (0xc5bde908), UINT32_C (0x26414ff3), + UINT32_C (0xa30519ad), UINT32_C (0xd7b43abe), + UINT32_C (0x2ce5d3d5), UINT32_C (0x88412761), + UINT32_C (0x97ca2070), UINT32_C (0xe5fbb9c7), + UINT32_C (0x276df0b4), UINT32_C (0x308f751f), + UINT32_C (0x37a97df6), UINT32_C (0xc9cd808c), + UINT32_C (0xfe4cb380), UINT32_C (0x3d469303), + UINT32_C (0xaee19096), UINT32_C (0xc0d5d42a), + UINT32_C (0x4e823ad3), UINT32_C (0xf5f9cc3b), + UINT32_C (0x4286619c), UINT32_C (0x9ca45e1c), + UINT32_C (0x66c97340), UINT32_C (0x891aec49), + UINT32_C (0x45bae606), UINT32_C (0xc798f047), + UINT32_C (0x52649d6c), UINT32_C (0xce86fdfc), + UINT32_C (0x80c6e402), UINT32_C (0xd6ec2f2b), + UINT32_C (0x27c82282), UINT32_C (0x1fe26ce0), + UINT32_C (0x92f57ea7), UINT32_C (0xde462f4d), + UINT32_C (0x07497cae), UINT32_C (0x5a48755c), + UINT32_C (0x721502dd), UINT32_C (0x6cbe7935), + UINT32_C (0x836d8003), UINT32_C (0x9ead7f70), + UINT32_C (0x9ab3a42f), UINT32_C (0x4c8652d6), + UINT32_C (0x32e39273), UINT32_C (0xe8fa3860), + UINT32_C (0x1da4f25a), UINT32_C (0x0cd6ef81), + UINT32_C (0x02503f7d), UINT32_C (0x8854a0a1), + UINT32_C (0x9a30c4e8), UINT32_C (0x88157153), + UINT32_C (0x05efe294), UINT32_C (0x57c4c925), + UINT32_C (0x2887d96f), UINT32_C (0xc1a71e3c), + UINT32_C (0xe9f84163), UINT32_C (0x2d0985de), + UINT32_C (0xd21e796c), UINT32_C (0x6fb5ce56), + UINT32_C (0x02614abf), UINT32_C (0xc3c7be2c), + UINT32_C (0xb54fed6f), UINT32_C (0xa617a083), + UINT32_C (0xc3142d8f), UINT32_C (0x6079e4ce), + UINT32_C (0xceffc147), UINT32_C (0x1d0cb81b), + UINT32_C (0xdc153e5f), UINT32_C (0xe36ef5bb), + UINT32_C (0xd531161a), UINT32_C (0x165b1015), + UINT32_C (0x7aa114ed), UINT32_C (0x3f7579b3), + UINT32_C (0xf7f395f1), UINT32_C (0xbc6172c7), + UINT32_C (0xa86f875e), UINT32_C (0x0e6c51b3), + UINT32_C (0xcdfec2af), UINT32_C (0x73c0e762), + UINT32_C (0x824c2009), UINT32_C (0xc5a87748), + UINT32_C (0x94d40125), UINT32_C (0x8aba3ffb), + UINT32_C (0xd32be060), UINT32_C (0x8c17eff0), + UINT32_C (0x21e2547e), UINT32_C (0x07cffad9), + UINT32_C (0x05340e15), UINT32_C (0xf3310c92), + UINT32_C (0x9d8d1908), UINT32_C (0x86ba527f), + UINT32_C (0xf943f672), UINT32_C (0xef73fbf0), + UINT32_C (0x46d95ca5), UINT32_C (0xc54cd95b), + UINT32_C (0x9d855e89), UINT32_C (0x4bb5af29) + } + #else + { + UINT64_C (0x12a8f216af9418c2), UINT64_C (0xd4490ad526f14431), + UINT64_C (0xb49c3b3995091a36), UINT64_C (0x5b45e522e4b1b4ef), + UINT64_C (0xa1e9300cd8520548), UINT64_C (0x49787fef17af9924), + UINT64_C (0x03219a39ee587a30), UINT64_C (0xebe9ea2adf4321c7), + UINT64_C (0x804456af10f5fb53), UINT64_C (0xd74bbe77e6116ac7), + UINT64_C (0x7c0828dd624ec390), UINT64_C (0x14a195640116f336), + UINT64_C (0x2eab8ca63ce802d7), UINT64_C (0xc6e57a78fbd986e0), + UINT64_C (0x58efc10b06a2068d), UINT64_C (0xabeeddb2dde06ff1), + UINT64_C (0x0b090a7560a968e3), UINT64_C (0x2cf9c8ca052f6e9f), + UINT64_C (0x116d0016cb948f09), UINT64_C (0xa59e0bd101731a28), + UINT64_C (0x63767572ae3d6174), UINT64_C (0xab4f6451cc1d45ec), + UINT64_C (0xc2a1e7b5b459aeb5), UINT64_C (0x2472f6207c2d0484), + UINT64_C (0xe699ed85b0dfb40d), UINT64_C (0xd4347f66ec8941c3), + UINT64_C (0xf4d14597e660f855), UINT64_C (0x8b889d624d44885d), + UINT64_C (0x258e5a80c7204c4b), UINT64_C (0xaf0c317d32adaa8a), + UINT64_C (0x9c4cd6257c5a3603), UINT64_C (0xeb3593803173e0ce), + UINT64_C (0x36f60e2ba4fa6800), UINT64_C (0x38b6525c21a42b0e), + UINT64_C (0xf4f5d05c10cab243), UINT64_C (0xcf3f4688801eb9aa), + UINT64_C (0x1ddc0325259b27de), UINT64_C (0xb9571fa04dc089c8), + UINT64_C (0xd7504dfa8816edbb), UINT64_C (0x1fe2cca76517db90), + UINT64_C (0x261e4e4c0a333a9d), UINT64_C (0x219b97e26ffc81bd), + UINT64_C (0x66b4835d9eafea22), UINT64_C (0x4cc317fb9cddd023), + UINT64_C (0x50b704cab602c329), UINT64_C (0xedb454e7badc0805), + UINT64_C (0x9e17e49642a3e4c1), UINT64_C (0x66c1a2a1a60cd889), + UINT64_C (0x7983eed3740847d5), UINT64_C (0x298af231c85bafab), + UINT64_C (0x2680b122baa28d97), UINT64_C (0x734de8181f6ec39a), + UINT64_C (0x53898e4c3910da55), UINT64_C (0x1761f93a44d5aefe), + UINT64_C (0xe4dbf0634473f5d2), UINT64_C (0x4ed0fe7e9dc91335), + UINT64_C (0xd18d8549d140caea), UINT64_C (0x1cfc8bed0d681639), + UINT64_C (0xca1e3785a9e724e5), UINT64_C (0xb67c1fa481680af8), + UINT64_C (0xdfea21ea9e7557e3), UINT64_C (0xd6b6d0ecc617c699), + UINT64_C (0xfa7e393983325753), UINT64_C (0xa09e8c8c35ab96de), + UINT64_C (0x8fe88b57305e2ab6), UINT64_C (0x89039d79d6fc5c5c), + UINT64_C (0x9bfb227ebdf4c5ce), UINT64_C (0x7f7cc39420a3a545), + UINT64_C (0x3f6c6af859d80055), UINT64_C (0xc8763c5b08d1908c), + UINT64_C (0x469356c504ec9f9d), UINT64_C (0x26e6db8ffdf5adfe), + UINT64_C (0x3a938fee32d29981), UINT64_C (0x2c5e9deb57ef4743), + UINT64_C (0x1e99b96e70a9be8b), UINT64_C (0x764dbeae7fa4f3a6), + UINT64_C (0xaac40a2703d9bea0), UINT64_C (0x1a8c1e992b941148), + UINT64_C (0x73aa8a564fb7ac9e), UINT64_C (0x604d51b25fbf70e2), + UINT64_C (0xdd69a0d8ab3b546d), UINT64_C (0x65ca5b96b7552210), + UINT64_C (0x2fd7e4b9e72cd38c), UINT64_C (0x51d2b1ab2ddfb636), + UINT64_C (0x9d1d84fcce371425), UINT64_C (0xa44cfe79ae538bbe), + UINT64_C (0xde68a2355b93cae6), UINT64_C (0x9fc10d0f989993e0), + UINT64_C (0x94ebc8abcfb56dae), UINT64_C (0xd7a023a73260b45c), + UINT64_C (0x72c8834a5957b511), UINT64_C (0x8f8419a348f296bf), + UINT64_C (0x1e152328f3318dea), UINT64_C (0x4838d65f6ef6748f), + UINT64_C (0xd6bf7baee43cac40), UINT64_C (0x13328503df48229f), + UINT64_C (0x7440fb816508c4fe), UINT64_C (0x9d266d6a1cc0542c), + UINT64_C (0x4dda48153c94938a), UINT64_C (0x74c04bf1790c0efe), + UINT64_C (0xe1925c71285279f5), UINT64_C (0x8a8e849eb32781a5), + UINT64_C (0x073973751f12dd5e), UINT64_C (0xa319ce15b0b4db31), + UINT64_C (0x6dd856d94d259236), UINT64_C (0x67378d8eccef96cb), + UINT64_C (0x9fc477de4ed681da), UINT64_C (0xf3b8b6675a6507ff), + UINT64_C (0xc3a9dc228caac9e9), UINT64_C (0xc37b45b3f8d6f2ba), + UINT64_C (0xb559eb1d04e5e932), UINT64_C (0x1b0cab936e65c744), + UINT64_C (0xaf08da9177dda93d), UINT64_C (0xac12fb171817eee7), + UINT64_C (0x1fff7ac80904bf45), UINT64_C (0xa9119b60369ffebd), + UINT64_C (0xbfced1b0048eac50), UINT64_C (0xb67b7896167b4c84), + UINT64_C (0x9b3cdb65f82ca382), UINT64_C (0xdbc27ab5447822bf), + UINT64_C (0x10dcd78e3851a492), UINT64_C (0xb438c2b67f98e5e9), + UINT64_C (0x43954b3252dc25e5), UINT64_C (0xab9090168dd05f34), + UINT64_C (0xce68341f79893389), UINT64_C (0x36833336d068f707), + UINT64_C (0xdcdd7d20903d0c25), UINT64_C (0xda3a361b1c5157b1), + UINT64_C (0x7f9d1a2e1ebe1327), UINT64_C (0x5d0a12f27ad310d1), + UINT64_C (0x3bc36e078f7515d7), UINT64_C (0x4da8979a0041e8a9), + UINT64_C (0x950113646d1d6e03), UINT64_C (0x7b4a38e32537df62), + UINT64_C (0x8a1b083821f40cb4), UINT64_C (0x3d5774a11d31ab39), + UINT64_C (0x7a76956c3eafb413), UINT64_C (0x7f5126dbba5e0ca7), + UINT64_C (0x12153635b2c0cf57), UINT64_C (0x7b3f0195fc6f290f), + UINT64_C (0x5544f7d774b14aef), UINT64_C (0x56c074a581ea17fe), + UINT64_C (0xe7f28ecd2d49eecd), UINT64_C (0xe479ee5b9930578c), + UINT64_C (0x9ff38fed72e9052f), UINT64_C (0x9f65789a6509a440), + UINT64_C (0x0981dcd296a8736d), UINT64_C (0x5873888850659ae7), + UINT64_C (0xc678b6d860284a1c), UINT64_C (0x63e22c147b9c3403), + UINT64_C (0x92fae24291f2b3f1), UINT64_C (0x829626e3892d95d7), + UINT64_C (0xcffe1939438e9b24), UINT64_C (0x79999cdff70902cb), + UINT64_C (0x8547eddfb81ccb94), UINT64_C (0x7b77497b32503b12), + UINT64_C (0x97fcaacbf030bc24), UINT64_C (0x6ced1983376fa72b), + UINT64_C (0x7e75d99d94a70f4d), UINT64_C (0xd2733c4335c6a72f), + UINT64_C (0xdbc0d2b6ab90a559), UINT64_C (0x94628d38d0c20584), + UINT64_C (0x64972d68dee33360), UINT64_C (0xb9c11d5b1e43a07e), + UINT64_C (0x2de0966daf2f8b1c), UINT64_C (0x2e18bc1ad9704a68), + UINT64_C (0xd4dba84729af48ad), UINT64_C (0xb7a0b174cff6f36e), + UINT64_C (0xe94c39a54a98307f), UINT64_C (0xaa70b5b4f89695a2), + UINT64_C (0x3bdbb92c43b17f26), UINT64_C (0xcccb7005c6b9c28d), + UINT64_C (0x18a6a990c8b35ebd), UINT64_C (0xfc7c95d827357afa), + UINT64_C (0x1fca8a92fd719f85), UINT64_C (0x1dd01aafcd53486a), + UINT64_C (0x49353fea39ba63b1), UINT64_C (0xf85b2b4fbcde44b7), + UINT64_C (0xbe7444e39328a0ac), UINT64_C (0x3e2b8bcbf016d66d), + UINT64_C (0x964e915cd5e2b207), UINT64_C (0x1725cabfcb045b00), + UINT64_C (0x7fbf21ec8a1f45ec), UINT64_C (0x11317ba87905e790), + UINT64_C (0x2fe4b17170e59750), UINT64_C (0xe8d9ecbe2cf3d73f), + UINT64_C (0xb57d2e985e1419c7), UINT64_C (0x0572b974f03ce0bb), + UINT64_C (0xa8d7e4dab780a08d), UINT64_C (0x4715ed43e8a45c0a), + UINT64_C (0xc330de426430f69d), UINT64_C (0x23b70edb1955c4bf), + UINT64_C (0x098954d51fff6580), UINT64_C (0x8107fccf064fcf56), + UINT64_C (0x852f54934da55cc9), UINT64_C (0x09c7e552bc76492f), + UINT64_C (0xe9f6760e32cd8021), UINT64_C (0xa3bc941d0a5061cb), + UINT64_C (0xba89142e007503b8), UINT64_C (0xdc842b7e2819e230), + UINT64_C (0xbbe83f4ecc2bdecb), UINT64_C (0xcd454f8f19c5126a), + UINT64_C (0xc62c58f97dd949bf), UINT64_C (0x693501d628297551), + UINT64_C (0xb9ab4ce57f2d34f3), UINT64_C (0x9255abb50d532280), + UINT64_C (0xebfafa33d7254b59), UINT64_C (0xe9f6082b05542e4e), + UINT64_C (0x35dd37d5871448af), UINT64_C (0xb03031a8b4516e84), + UINT64_C (0xb3f256d8aca0b0b9), UINT64_C (0x0fd22063edc29fca), + UINT64_C (0xd9a11fbb3d9808e4), UINT64_C (0x3a9bf55ba91f81ca), + UINT64_C (0xc8c93882f9475f5f), UINT64_C (0x947ae053ee56e63c), + UINT64_C (0xc7d9f16864a76e94), UINT64_C (0x7bd94e1d8e17debc), + UINT64_C (0xd873db391292ed4f), UINT64_C (0x30f5611484119414), + UINT64_C (0x565c31f7de89ea27), UINT64_C (0xd0e4366228b03343), + UINT64_C (0x325928ee6e6f8794), UINT64_C (0x6f423357e7c6a9f9), + UINT64_C (0x99170a5dc3115544), UINT64_C (0x59b97885e2f2ea28), + UINT64_C (0xbc4097b116c524d2), UINT64_C (0x7a13f18bbedc4ff5), + UINT64_C (0x071582401c38434d), UINT64_C (0xb422061193d6f6a7), + UINT64_C (0xb4b81b3fa97511e2), UINT64_C (0x65d34954daf3cebd), + UINT64_C (0xb344c470397bba52), UINT64_C (0xbac7a9a18531294b), + UINT64_C (0xecb53939887e8175), UINT64_C (0x565601c0364e3228), + UINT64_C (0xef1955914b609f93), UINT64_C (0x16f50edf91e513af), + UINT64_C (0x56963b0dca418fc0), UINT64_C (0xd60f6dcedc314222), + UINT64_C (0x364f6ffa464ee52e), UINT64_C (0x6c3b8e3e336139d3), + UINT64_C (0xf943aee7febf21b8), UINT64_C (0x088e049589c432e0), + UINT64_C (0xd49503536abca345), UINT64_C (0x3a6c27934e31188a), + UINT64_C (0x957baf61700cff4e), UINT64_C (0x37624ae5a48fa6e9), + UINT64_C (0x501f65edb3034d07), UINT64_C (0x907f30421d78c5de), + UINT64_C (0x1a804aadb9cfa741), UINT64_C (0x0ce2a38c344a6eed), + UINT64_C (0xd363eff5f0977996), UINT64_C (0x2cd16e2abd791e33), + UINT64_C (0x58627e1a149bba21), UINT64_C (0x7f9b6af1ebf78baf) + }, + { + UINT64_C (0xd20d8c88c8ffe65f), UINT64_C (0x917f1dd5f8886c61), + UINT64_C (0x56986e2ef3ed091b), UINT64_C (0x5fa7867caf35e149), + UINT64_C (0x81a1549fd6573da5), UINT64_C (0x96fbf83a12884624), + UINT64_C (0xe728e8c83c334074), UINT64_C (0xf1bcc3d275afe51a), + UINT64_C (0x71f1ce2490d20b07), UINT64_C (0xe6c42178c4bbb92e), + UINT64_C (0x0a9c32d5eae45305), UINT64_C (0x0c335248857fa9e7), + UINT64_C (0x142de49fff7a7c3d), UINT64_C (0x64a53dc924fe7ac9), + UINT64_C (0x9f6a419d382595f4), UINT64_C (0x150f361dab9dec26), + UINT64_C (0xc61bb3a141e50e8c), UINT64_C (0x2785338347f2ba08), + UINT64_C (0x7ca9723fbb2e8988), UINT64_C (0xce2f8642ca0712dc), + UINT64_C (0x59300222b4561e00), UINT64_C (0xc2b5a03f71471a6f), + UINT64_C (0xd5f9e858292504d5), UINT64_C (0x65fa4f227a2b6d79), + UINT64_C (0x93cbe0b699c2585d), UINT64_C (0x1d95b0a5fcf90bc6), + UINT64_C (0x17efee45b0dee640), UINT64_C (0x9e4c1269baa4bf37), + UINT64_C (0xd79476a84ee20d06), UINT64_C (0x0a56a5f0bfe39272), + UINT64_C (0x7eba726d8c94094b), UINT64_C (0x5e5637885f29bc2b), + UINT64_C (0xd586bd01c5c217f6), UINT64_C (0x233003b5a6cfe6ad), + UINT64_C (0x24c0e332b70019b0), UINT64_C (0x9da058c67844f20c), + UINT64_C (0xe4d9429322cd065a), UINT64_C (0x1fab64ea29a2ddf7), + UINT64_C (0x8af38731c02ba980), UINT64_C (0x7dc7785b8efdfc80), + UINT64_C (0x486289ddcc3d6780), UINT64_C (0x222bbfae61725606), + UINT64_C (0x2bc60a63a6f3b3f2), UINT64_C (0x177e00f9fc32f791), + UINT64_C (0x522e23f3925e319e), UINT64_C (0x9c2ed44081ce5fbd), + UINT64_C (0x964781ce734b3c84), UINT64_C (0xf05d129681949a4c), + UINT64_C (0x046e3ecaaf453ce9), UINT64_C (0x962aceefa82e1c84), + UINT64_C (0xf5b4b0b0d2deeeb4), UINT64_C (0x1af3dbe25d8f45da), + UINT64_C (0xf9f4892ed96bd438), UINT64_C (0xc4c118bfe78feaae), + UINT64_C (0x07a69afdcc42261a), UINT64_C (0xf8549e1a3aa5e00d), + UINT64_C (0x2102ae466ebb1148), UINT64_C (0xe87fbb46217a360e), + UINT64_C (0x310cb380db6f7503), UINT64_C (0xb5fdfc5d3132c498), + UINT64_C (0xdaf8e9829fe96b5f), UINT64_C (0xcac09afbddd2cdb4), + UINT64_C (0xb862225b055b6960), UINT64_C (0x55b6344cf97aafae), + UINT64_C (0xff577222c14f0a3a), UINT64_C (0x4e4b705b92903ba4), + UINT64_C (0x730499af921549ff), UINT64_C (0x13ae978d09fe5557), + UINT64_C (0xd9e92aa246bf719e), UINT64_C (0x7a4c10ec2158c4a6), + UINT64_C (0x49cad48cebf4a71e), UINT64_C (0xcf05daf5ac8d77b0), + UINT64_C (0xabbdcdd7ed5c0860), UINT64_C (0x9853eab63b5e0b35), + UINT64_C (0x352787baa0d7c22f), UINT64_C (0xc7f6aa2de59aea61), + UINT64_C (0x03727073c2e134b1), UINT64_C (0x5a0f544dd2b1fb18), + UINT64_C (0x74f85198b05a2e7d), UINT64_C (0x963ef2c96b33be31), + UINT64_C (0x4659d2b743848a2c), UINT64_C (0x19ebb029435dcb0f), + UINT64_C (0x4e9d2827355fc492), UINT64_C (0xccec0a73b49c9921), + UINT64_C (0x46c9feb55d120902), UINT64_C (0x8d2636b81555a786), + UINT64_C (0x30c05b1ba332f41c), UINT64_C (0xf6f7fd1431714200), + UINT64_C (0x1a4ff12616eefc89), UINT64_C (0x990a98fd5071d263), + UINT64_C (0x84547ddc3e203c94), UINT64_C (0x07a3aec79624c7da), + UINT64_C (0x8a328a1cedfe552c), UINT64_C (0xd1e649de1e7f268b), + UINT64_C (0x2d8d5432157064c8), UINT64_C (0x4ae7d6a36eb5dbcb), + UINT64_C (0x57e3306d881edb4f), UINT64_C (0x0a804d18b7097475), + UINT64_C (0xe74733427b72f0c1), UINT64_C (0x24b33c9d7ed25117), + UINT64_C (0xe805a1e290cf2456), UINT64_C (0x3b544ebe544c19f9), + UINT64_C (0x3e666e6f69ae2c15), UINT64_C (0xfb152fe3ff26da89), + UINT64_C (0xb49b52e587a1ee60), UINT64_C (0xac042e70f8b383f2), + UINT64_C (0x89c350c893ae7dc1), UINT64_C (0xb592bf39b0364963), + UINT64_C (0x190e714fada5156e), UINT64_C (0xec8177f83f900978), + UINT64_C (0x91b534f885818a06), UINT64_C (0x81536d601170fc20), + UINT64_C (0xd4c718bc4ae8ae5f), UINT64_C (0x9eedeca8e272b933), + UINT64_C (0x10e8b35af3eeab37), UINT64_C (0x0e09b88e1914f7af), + UINT64_C (0x3fa9ddfb67e2f199), UINT64_C (0xb10bb459132d0a26), + UINT64_C (0x2c046f22062dc67d), UINT64_C (0x5e90277e7cb39e2d), + UINT64_C (0xd6b04d3b7651dd7e), UINT64_C (0xe34a1d250e7a8d6b), + UINT64_C (0x53c065c6c8e63528), UINT64_C (0x1bdea12e35f6a8c9), + UINT64_C (0x21874b8b4d2dbc4f), UINT64_C (0x3a88a0fbbcb05c63), + UINT64_C (0x43ed7f5a0fae657d), UINT64_C (0x230e343dfba08d33), + UINT64_C (0xb5b4071dbfc73a66), UINT64_C (0x8f9887e6078735a1), + UINT64_C (0x08de8a1c7797da9b), UINT64_C (0xfcb6be43a9f2fe9b), + UINT64_C (0x049a7f41061a9e60), UINT64_C (0x9f91508bffcfc14a), + UINT64_C (0xe3273522064480ca), UINT64_C (0xcd04f3ff001a4778), + UINT64_C (0x6bfa9aae5ec05779), UINT64_C (0x371f77e76bb8417e), + UINT64_C (0x3550c2321fd6109c), UINT64_C (0xfb4a3d794a9a80d2), + UINT64_C (0xf43c732873f24c13), UINT64_C (0xaa9119ff184cccf4), + UINT64_C (0xb69e38a8965c6b65), UINT64_C (0x1f2b1d1f15f6dc9c), + UINT64_C (0x67fef95d92607890), UINT64_C (0x31865ced6120f37d), + UINT64_C (0x3a6853c7e70757a7), UINT64_C (0x32ab0edb696703d3), + UINT64_C (0xee97f453f06791ed), UINT64_C (0x6dc93d9526a50e68), + UINT64_C (0x78edefd694af1eed), UINT64_C (0x9c1169fa2777b874), + UINT64_C (0x50065e535a213cf6), UINT64_C (0xde0c89a556b9ae70), + UINT64_C (0xd1e0ccd25bb9c169), UINT64_C (0x6b17b224bad6bf27), + UINT64_C (0x6b02e63195ad0cf8), UINT64_C (0x455a4b4cfe30e3f5), + UINT64_C (0x9338e69c052b8e7b), UINT64_C (0x5092ef950a16da0b), + UINT64_C (0x7c45d833aff07862), UINT64_C (0xa5b1cfdba0ab4067), + UINT64_C (0x6ad047c430a12104), UINT64_C (0x6c47bec883a7de39), + UINT64_C (0x944f6de09134dfb6), UINT64_C (0x9aeba33ac6ecc6b0), + UINT64_C (0x52e762596bf68235), UINT64_C (0x22af003ab672e811), + UINT64_C (0xb5635c95ff7296e2), UINT64_C (0xed2df21216235097), + UINT64_C (0x4a29c6465a314cd1), UINT64_C (0xd83cc2687a19255f), + UINT64_C (0x506c11b9d90e8b1d), UINT64_C (0x57277707199b8175), + UINT64_C (0xcaf21ecd4377b28c), UINT64_C (0xc0c0f5a60ef4cdcf), + UINT64_C (0x93b633abfa3469f8), UINT64_C (0xe846963877671a17), + UINT64_C (0x59ac2c7873f910a3), UINT64_C (0x660d3257380841ee), + UINT64_C (0xd813f2fab7f5c5ca), UINT64_C (0x4112cf68649a260e), + UINT64_C (0x443f64ec5a371195), UINT64_C (0xb0774d261cc609db), + UINT64_C (0x720bf5f26f4d2eaa), UINT64_C (0x1c2559e30f0946be), + UINT64_C (0xe328e230e3e2b3fb), UINT64_C (0x087e79e5a57d1d13), + UINT64_C (0x08dd9bdfd96b9f63), UINT64_C (0x64d0e29eea8838b3), + UINT64_C (0xddf957bc36d8b9ca), UINT64_C (0x6ffe73e81b637fb3), + UINT64_C (0x1a4e4822eb4d7a59), UINT64_C (0x5d94337fbfaf7f5b), + UINT64_C (0xd30c088ba61ea5ef), UINT64_C (0x9d765e419fb69f6d), + UINT64_C (0x9e21f4f903b33fd9), UINT64_C (0xb4d8f77bc3e56167), + UINT64_C (0x733ea705fae4fa77), UINT64_C (0xa4ec0132764ca04b), + UINT64_C (0x7976033a39f7d952), UINT64_C (0x106f72fe81e2c590), + UINT64_C (0x8c90fd9b083f4558), UINT64_C (0xfd080d236da814ba), + UINT64_C (0x7b64978555326f9f), UINT64_C (0x60e8ed72c0dff5d1), + UINT64_C (0xb063e962e045f54d), UINT64_C (0x959f587d507a8359), + UINT64_C (0x758f450c88572e0b), UINT64_C (0x1b6baca2ae4e125b), + UINT64_C (0x61cf4f94c97df93d), UINT64_C (0x2738259634305c14), + UINT64_C (0xd39bb9c3a48db6cf), UINT64_C (0x8215e577001332c8), + UINT64_C (0xa1082c0466df6c0a), UINT64_C (0xef02cdd06ffdb432), + UINT64_C (0xfc87614baf287e07), UINT64_C (0x240ab57a8b888b20), + UINT64_C (0xbf8d5108e27e0d48), UINT64_C (0x61bdd1307c66e300), + UINT64_C (0xb925a6cd0421aff3), UINT64_C (0x3e003e616a6591e9), + UINT64_C (0x94c3251f06f90cf3), UINT64_C (0xbf84470805e69b5f), + UINT64_C (0x98f076a4f7a2322e), UINT64_C (0x70cb6af7c2d5bcf0), + UINT64_C (0xb64be8d8b25396c1), UINT64_C (0xa9aa4d20db084e9b), + UINT64_C (0x2e6d02c36017f67f), UINT64_C (0xefed53d75fd64e6b), + UINT64_C (0xd9f1f30ccd97fb09), UINT64_C (0xa2ebee47e2fbfce1), + UINT64_C (0xb8d91274b9e9d4fb), UINT64_C (0x1db956e450275779), + UINT64_C (0x4fc8e9560f91b123), UINT64_C (0x63573ff03e224774), + UINT64_C (0x0647dfedcd894a29), UINT64_C (0x7884d9bc6cb569d8), + UINT64_C (0x7fba195410e5ca30), UINT64_C (0x106c09b972d2e822), + UINT64_C (0x241260ed4ad1e87d), UINT64_C (0x64c8e531bff53b55), + UINT64_C (0xca672b91e9e4fa16), UINT64_C (0x3871700761b3f743), + UINT64_C (0xf95cffa23af5f6f4), UINT64_C (0x8d14dedb30be846e), + UINT64_C (0x3b097adaf088f94e), UINT64_C (0x21e0bd5026c619bf), + UINT64_C (0x1bda0492e7e4586e), UINT64_C (0xd23c8e176d113600), + UINT64_C (0x252f59cf0d9f04bb), UINT64_C (0xb3598080ce64a656), + UINT64_C (0x993e1de72d36d310), UINT64_C (0xa2853b80f17f58ee), + UINT64_C (0x1877b51e57a764d5), UINT64_C (0x001f837cc7350524) + } + #endif + }; + +int +main (int argc, char **argv) +{ + unsigned int i; + isaac_word r[ISAAC_WORDS]; + int iterations; + + /* Seed with zeros, and discard the first buffer of output, + as that's what the standard programs do. */ + static struct isaac_state s; + isaac_seed (&s); + isaac_refill (&s, r); + + for (i = 0; i < sizeof expected / sizeof expected[0]; i++) + { + isaac_refill (&s, r); + ASSERT (memcmp (r, expected[i], sizeof r) == 0); + } + + /* If invoked with a positive argument, run a benchmark; + if with a negative, run a do-nothing benchmark. */ + for (iterations = argc <= 1 ? 0 : atoi (argv[1]); + iterations != 0; + iterations += (iterations < 0 ? 1 : -1)) + if (0 <= iterations) + isaac_refill (&s, r); + + return 0; +} -- 1.7.1 From debbugs-submit-bounces@debbugs.gnu.org Fri Jul 23 19:40:32 2010 Received: (at 6658-done) by debbugs.gnu.org; 23 Jul 2010 23:40:32 +0000 Received: from localhost ([127.0.0.1] helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1OcRqx-0008T8-7Q for submit@debbugs.gnu.org; Fri, 23 Jul 2010 19:40:31 -0400 Received: from mail1.slb.deg.dub.stisp.net ([84.203.253.98]) by debbugs.gnu.org with smtp (Exim 4.69) (envelope-from ) id 1OcRqu-0008T2-Ra for 6658-done@debbugs.gnu.org; Fri, 23 Jul 2010 19:40:29 -0400 Received: (qmail 13334 invoked from network); 23 Jul 2010 23:40:26 -0000 Received: from unknown (HELO ?192.168.2.25?) (84.203.137.218) by mail1.slb.deg.dub.stisp.net with SMTP; 23 Jul 2010 23:40:26 -0000 Message-ID: <4C4A2846.3050204@draigBrady.com> Date: Sat, 24 Jul 2010 00:39:50 +0100 From: =?ISO-8859-1?Q?P=E1draig_Brady?= User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.1.8) Gecko/20100227 Thunderbird/3.0.3 MIME-Version: 1.0 To: Paul Eggert Subject: Re: bug#6658: [PATCH] randread: don't require -lrt References: <4C40CC76.2050407@cs.ucla.edu> <87zkxrqcmu.fsf@meyering.net> <4C4A15BD.1090402@cs.ucla.edu> In-Reply-To: <4C4A15BD.1090402@cs.ucla.edu> X-Enigmail-Version: 1.0.1 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-Spam-Score: -2.7 (--) X-Debbugs-Envelope-To: 6658-done Cc: Jim Meyering , 6658-done@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.11 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -2.7 (--) On 23/07/10 23:20, Paul Eggert wrote: >>> 3. We could get about 2X CPU performance on 64-bit machines by using >>> ISAAC64 instead of ISAAC. >>> >> These are all welcome changes, and the patch for (1) looks fine. > > OK, here's the change for (3), which I just pushed. I verified that > it improved performance of random-number generation by 2x on my > 64-bit host (RHEL 5 host with a Xeon E5620; the benchmark performance > improvement was actually a tiny bit better than 2x speedup). On this > platform isaac_refill now generates pseudorandom data at around 2.5 GB/s, > which is quite a bit faster than /dev/urandom's 7.5 MB/s > (as measured with dd). Very nice. > On 32-bit hosts the code behaves as before, though I expect it runs a > bit faster than before (I haven't checked this). Same performance on 32 bit here: $ git pull origin $ gcc -march=pentium-m -O2 -I lib gl/tests/test-rand-isaac.c lib/libcoreutils.a $ time ./a.out 10000000 real 0m13.093s $ (cd lib && make) CC randread.o CC rand-isaac.o AR libcoreutils.a $gcc -march=pentium-m -O2 -I lib gl/tests/test-rand-isaac.c lib/libcoreutils.a $ time ./a.out 10000000 real 0m13.115s Note I needed to comment out the ASSERT check when linking with the old rand-isaac. Is that a bug in the old implementation or just a change? > > Perhaps this stuff should be moved to gnulib? I can't recall if there > was any good reason to leave it in coreutils. > Inertia more than anything I think. > +++ b/gl/tests/test-rand-isaac.c > + > +/* FIXME: once/if in gnulib, use #include "macros.h" in place of this */ > +#define ASSERT(expr) \ Hmm, I just used macros.h in test-mbsalign.c which seems ok I'm marking this rand update series as done. cheers, Pádraig. From debbugs-submit-bounces@debbugs.gnu.org Sat Jul 24 02:23:23 2010 Received: (at 6658) by debbugs.gnu.org; 24 Jul 2010 06:23:23 +0000 Received: from localhost ([127.0.0.1] helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1OcY8p-0002hz-Lz for submit@debbugs.gnu.org; Sat, 24 Jul 2010 02:23:23 -0400 Received: from kiwi.cs.ucla.edu ([131.179.128.19]) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1OcY8n-0002hs-OV for 6658@debbugs.gnu.org; Sat, 24 Jul 2010 02:23:23 -0400 Received: from [131.179.64.200] (Penguin.CS.UCLA.EDU [131.179.64.200]) by kiwi.cs.ucla.edu (8.13.8+Sun/8.13.8/UCLACS-6.0) with ESMTP id o6O6NI2T006330; Fri, 23 Jul 2010 23:23:19 -0700 (PDT) Message-ID: <4C4A86D6.4040804@cs.ucla.edu> Date: Fri, 23 Jul 2010 23:23:18 -0700 From: Paul Eggert Organization: UCLA Computer Science Department User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.1.10) Gecko/20100527 Thunderbird/3.0.5 MIME-Version: 1.0 To: 6658@debbugs.gnu.org, P@draigBrady.com Subject: Re: bug#6658: [PATCH] randread: don't require -lrt References: <4C40CC76.2050407@cs.ucla.edu> <87zkxrqcmu.fsf@meyering.net> <4C4A15BD.1090402@cs.ucla.edu> <4C4A2846.3050204@draigBrady.com> In-Reply-To: <4C4A2846.3050204@draigBrady.com> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable X-MIME-Autoconverted: from 8bit to quoted-printable by kiwi.cs.ucla.edu id o6O6NI2T006330 X-Spam-Score: -3.4 (---) X-Debbugs-Envelope-To: 6658 X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.11 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -3.4 (---) On 07/23/10 16:39, P=E1draig Brady wrote: > Note I needed to comment out the ASSERT check > when linking with the old rand-isaac. > Is that a bug in the old implementation or just a change? It's a change to the API for rand-isaac. Combining the new test program with the old implementation would lead to undefined behavior, though it sounds like it sort of worked since the change was just to the seeding code. I changed all callers, so the API change shouldn't be a problem. Ah well, I was hoping 32-bit would be a tiny bit faster, but perhaps next time. Thanks for checking it. From unknown Tue Aug 19 05:09:48 2025 Received: (at fakecontrol) by fakecontrolmessage; To: internal_control@debbugs.gnu.org From: Debbugs Internal Request Subject: Internal Control Message-Id: bug archived. Date: Sat, 21 Aug 2010 11:24:05 +0000 User-Agent: Fakemail v42.6.9 # This is a fake control message. # # The action: # bug archived. thanks # This fakemail brought to you by your local debbugs # administrator