From 58a7ead41d056909784bfab9323c5f44f577d3d0 Mon Sep 17 00:00:00 2001 From: Jim Meyering Date: Sat, 1 Sep 2007 09:54:45 +0200 Subject: Convert coreutils' rand*.{c,h,m4} into modules. First step: move these files to gl/lib: * lib/rand-isaac.c, lib/rand-isaac.h * lib/randint.c, lib/randint.h * lib/randperm.c, lib/randperm.h * lib/randread.c, lib/randread.h Step 2: add modules/rand* and remove now-unneeded .m4 files. * gl/modules/randint: New file. * gl/modules/randperm: New file. * gl/modules/randread: New file. * m4/randint.m4: Remove file. * m4/randperm.m4: Remove file. * m4/randread.m4: Remove file. Step 3: use the new modules * bootstrap.conf (gnulib_modules): Add randint and randperm. * m4/prereq.m4 (gl_RANDINT, gl_RANDREAD, gl_RANDPERM): Don't require; These have been removed. (gl_ROOT_DEV_INO): Don't require; already handled via bootstrap.conf. --- gl/lib/rand-isaac.c | 300 ++++++++++++++++++++++++++++++++++++++++++++++++++++ gl/lib/rand-isaac.h | 43 ++++++++ gl/lib/randint.c | 227 +++++++++++++++++++++++++++++++++++++++ gl/lib/randint.h | 51 +++++++++ gl/lib/randperm.c | 102 ++++++++++++++++++ gl/lib/randperm.h | 4 + gl/lib/randread.c | 297 +++++++++++++++++++++++++++++++++++++++++++++++++++ gl/lib/randread.h | 33 ++++++ 8 files changed, 1057 insertions(+) create mode 100644 gl/lib/rand-isaac.c create mode 100644 gl/lib/rand-isaac.h create mode 100644 gl/lib/randint.c create mode 100644 gl/lib/randint.h create mode 100644 gl/lib/randperm.c create mode 100644 gl/lib/randperm.h create mode 100644 gl/lib/randread.c create mode 100644 gl/lib/randread.h (limited to 'gl/lib') diff --git a/gl/lib/rand-isaac.c b/gl/lib/rand-isaac.c new file mode 100644 index 000000000..cd69fbfde --- /dev/null +++ b/gl/lib/rand-isaac.c @@ -0,0 +1,300 @@ +/* Bob Jenkins's cryptographic random number generator, ISAAC. + + Copyright (C) 1999-2006 Free Software Foundation, Inc. + Copyright (C) 1997, 1998, 1999 Colin Plumb. + + 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 Colin Plumb. */ + +/* + * -------------------------------------------------------------------- + * We need a source of random numbers for some data. + * Cryptographically secure is desirable, but it's not life-or-death + * so I can be a little bit experimental in the choice of RNGs here. + * + * This generator is based somewhat on RC4, but has analysis + * + * pointing to it actually being better. I like it because it's nice + * and fast, and because the author did good work analyzing it. + * -------------------------------------------------------------------- + */ +#include + +#include "rand-isaac.h" + +#include +#include + +#include "gethrxtime.h" + + +/* This index operation is more efficient on many processors */ +#define ind(mm, x) \ + (* (uint32_t *) ((char *) (mm) \ + + ((x) & (ISAAC_WORDS - 1) * sizeof (uint32_t)))) + +/* + * 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 \ +) + +/* Use and update *S to generate random data to fill R. */ +void +isaac_refill (struct isaac_state *s, uint32_t r[ISAAC_WORDS]) +{ + 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 */ + + a = s->a; + b = s->b + (++s->c); + + 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); + r += 4; + } + while ((m += 4) < s->mm + ISAAC_WORDS / 2); + 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); + r += 4; + } + while ((m += 4) < s->mm + ISAAC_WORDS); + s->a = a; + s->b = b; +} + +/* + * 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; + } + + 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; +} + +#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. + * + * 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) +{ + static uint32_t const iv[8] = + { + 0x1367df5a, 0x95d90059, 0xc3163e4b, 0x0f421ad8, + 0xd92a4a78, 0xa51a3c49, 0xc4efea1b, 0x30609119}; + int i; + +# 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 + 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); + /* 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); + } + } + else + { + /* The no seed case (as in reference ISAAC code) */ + for (i = 0; i < ISAAC_WORDS; i++) + s->mm[i] = 0; + } + + /* Final pass */ + isaac_mix (s, s->mm); +} +#endif + +/* Initialize *S to a somewhat-random value. */ +static void +isaac_seed_start (struct isaac_state *s) +{ + static uint32_t const iv[8] = + { + 0x1367df5a, 0x95d90059, 0xc3163e4b, 0x0f421ad8, + 0xd92a4a78, 0xa51a3c49, 0xc4efea1b, 0x30609119 + }; + +#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]); +#endif + + memset (s->mm, 0, sizeof s->mm); + 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; +} + +/* 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. */ +void +isaac_seed (struct isaac_state *s) +{ + isaac_seed_start (s); + + { 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); } + + { + xtime_t t = gethrxtime (); + ISAAC_SEED (s, t); + } + + isaac_seed_finish (s); +} diff --git a/gl/lib/rand-isaac.h b/gl/lib/rand-isaac.h new file mode 100644 index 000000000..94ca74f53 --- /dev/null +++ b/gl/lib/rand-isaac.h @@ -0,0 +1,43 @@ +/* Bob Jenkins's cryptographic random number generator, ISAAC. + + Copyright (C) 1999-2005 Free Software Foundation, Inc. + Copyright (C) 1997, 1998, 1999 Colin Plumb. + + 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 Colin Plumb. */ + +#ifndef RAND_ISAAC_H +# define RAND_ISAAC_H + +# include + +/* Size of the state tables to use. ISAAC_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)) + +/* RNG state variables. The members of this structure 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 */ + }; + +void isaac_seed (struct isaac_state *); +void isaac_refill (struct isaac_state *, uint32_t[ISAAC_WORDS]); + +#endif diff --git a/gl/lib/randint.c b/gl/lib/randint.c new file mode 100644 index 000000000..53e8c3269 --- /dev/null +++ b/gl/lib/randint.c @@ -0,0 +1,227 @@ +/* Generate random integers. + + Copyright (C) 2006 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 "randint.h" + +#include +#include +#include +#include + + +#if TEST +# include +# include + +int +main (int argc, char **argv) +{ + randint i; + randint n = strtoumax (argv[1], NULL, 10); + randint choices = strtoumax (argv[2], NULL, 10); + char const *name = argv[3]; + struct randint_source *ints = randint_all_new (name, SIZE_MAX); + + for (i = 0; i < n; i++) + printf ("%"PRIuMAX"\n", randint_choose (ints, choices)); + + return (randint_all_free (ints) == 0 ? EXIT_SUCCESS : EXIT_FAILURE); +} +#endif + + +#include "xalloc.h" + +#ifndef MAX +# define MAX(a,b) ((a) < (b) ? (b) : (a)) +#endif + +/* A source of random data for generating random integers. */ +struct randint_source +{ + /* The source of random bytes. */ + struct randread_source *source; + + /* RANDNUM is a buffered random integer, whose information has not + yet been delivered to the caller. It is uniformly distributed in + the range 0 <= RANDNUM <= RANDMAX. If RANDMAX is zero, then + RANDNUM must be zero (and in some sense it is not really + "random"). */ + randint randnum; + randint randmax; +}; + +/* Create a new randint_source from SOURCE. */ + +struct randint_source * +randint_new (struct randread_source *source) +{ + struct randint_source *s = xmalloc (sizeof *s); + s->source = source; + s->randnum = s->randmax = 0; + return s; +} + +/* Create a new randint_source by creating a randread_source from + NAME and ESTIMATED_BYTES. Return NULL (setting errno) if + unsuccessful. */ + +struct randint_source * +randint_all_new (char const *name, size_t bytes_bound) +{ + struct randread_source *source = randread_new (name, bytes_bound); + return (source ? randint_new (source) : NULL); +} + +/* Return the random data source of *S. */ + +struct randread_source * +randint_get_source (struct randint_source const *s) +{ + return s->source; +} + +/* HUGE_BYTES is true on hosts hosts where randint and unsigned char + have the same width and where shifting by the word size therefore + has undefined behavior. */ +enum { HUGE_BYTES = RANDINT_MAX == UCHAR_MAX }; + +/* Return X shifted left by CHAR_BIT bits. */ +static inline randint shift_left (randint x) +{ + return HUGE_BYTES ? 0 : x << CHAR_BIT; +} + +/* Return X shifted right by CHAR_BIT bits. */ +static inline randint +shift_right (randint x) +{ + return HUGE_BYTES ? 0 : x >> CHAR_BIT; +} + + +/* Consume random data from *S to generate a random number in the range + 0 .. GENMAX. */ + +randint +randint_genmax (struct randint_source *s, randint genmax) +{ + struct randread_source *source = s->source; + randint randnum = s->randnum; + randint randmax = s->randmax; + randint choices = genmax + 1; + + for (;;) + { + if (randmax < genmax) + { + /* Calculate how many input bytes will be needed, and read + the bytes. */ + + size_t i = 0; + randint rmax = randmax; + unsigned char buf[sizeof randnum]; + + do + { + rmax = shift_left (rmax) + UCHAR_MAX; + i++; + } + while (rmax < genmax); + + randread (source, buf, i); + + /* Increase RANDMAX by appending random bytes to RANDNUM and + UCHAR_MAX to RANDMAX until RANDMAX is no less than + GENMAX. This may lose up to CHAR_BIT bits of information + if shift_right (RANDINT_MAX) < GENMAX, but it is not + worth the programming hassle of saving these bits since + GENMAX is rarely that large in practice. */ + + i = 0; + + do + { + randnum = shift_left (randnum) + buf[i]; + randmax = shift_left (randmax) + UCHAR_MAX; + i++; + } + while (randmax < genmax); + } + + if (randmax == genmax) + { + s->randnum = s->randmax = 0; + return randnum; + } + else + { + /* GENMAX < RANDMAX, so attempt to generate a random number + by taking RANDNUM modulo GENMAX+1. This will choose + fairly so long as RANDNUM falls within an integral + multiple of GENMAX+1; otherwise, LAST_USABLE_CHOICE < RANDNUM, + so discard this attempt and try again. + + Since GENMAX cannot be RANDINT_MAX, CHOICES cannot be + zero and there is no need to worry about dividing by + zero. */ + + randint excess_choices = randmax - genmax; + randint unusable_choices = excess_choices % choices; + randint last_usable_choice = randmax - unusable_choices; + randint reduced_randnum = randnum % choices; + + if (randnum <= last_usable_choice) + { + s->randnum = randnum / choices; + s->randmax = excess_choices / choices; + return reduced_randnum; + } + + /* Retry, but retain the randomness from the fact that RANDNUM fell + into the range LAST_USABLE_CHOICE+1 .. RANDMAX. */ + randnum = reduced_randnum; + randmax = unusable_choices - 1; + } + } +} + +/* Clear *S so that it no longer contains undelivered random data. */ + +void +randint_free (struct randint_source *s) +{ + memset (s, 0, sizeof *s); + free (s); +} + +/* Likewise, but also clear the underlying randread object. Return + 0 if successful, -1 (setting errno) otherwise. */ + +int +randint_all_free (struct randint_source *s) +{ + int r = randread_free (s->source); + int e = errno; + randint_free (s); + errno = e; + return r; +} diff --git a/gl/lib/randint.h b/gl/lib/randint.h new file mode 100644 index 000000000..1e96ccb50 --- /dev/null +++ b/gl/lib/randint.h @@ -0,0 +1,51 @@ +/* Generate random integers. + + Copyright (C) 2006 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. */ + +#ifndef RANDINT_H + +# define RANDINT_H 1 + +# include + +# include "randread.h" + +/* An unsigned integer type, used for random integers, and its maximum + value. */ +typedef uintmax_t randint; +# define RANDINT_MAX UINTMAX_MAX + +struct randint_source; + +struct randint_source *randint_new (struct randread_source *); +struct randint_source *randint_all_new (char const *, size_t); +struct randread_source *randint_get_source (struct randint_source const *); +randint randint_genmax (struct randint_source *, randint genmax); + +/* Consume random data from *S to generate a random number in the range + 0 .. CHOICES-1. CHOICES must be nonzero. */ +static inline randint +randint_choose (struct randint_source *s, randint choices) +{ + return randint_genmax (s, choices - 1); +} + +void randint_free (struct randint_source *); +int randint_all_free (struct randint_source *); + +#endif diff --git a/gl/lib/randperm.c b/gl/lib/randperm.c new file mode 100644 index 000000000..0aaa5e2ff --- /dev/null +++ b/gl/lib/randperm.c @@ -0,0 +1,102 @@ +/* Generate random permutations. + + Copyright (C) 2006, 2007 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 "randperm.h" + +#include + +#include "xalloc.h" + +/* Return the ceiling of the log base 2 of N. If N is zero, return + an unspecified value. */ + +static size_t +ceil_lg (size_t n) +{ + size_t b = 0; + for (n--; n != 0; n /= 2) + b++; + return b; +} + +/* Return an upper bound on the number of random bytes needed to + generate the first H elements of a random permutation of N + elements. H must not exceed N. */ + +size_t +randperm_bound (size_t h, size_t n) +{ + /* Upper bound on number of bits needed to generate the first number + of the permutation. */ + size_t lg_n = ceil_lg (n); + + /* Upper bound on number of bits needed to generated the first H elements. */ + size_t ar = lg_n * h; + + /* Convert the bit count to a byte count. */ + size_t bound = (ar + CHAR_BIT - 1) / CHAR_BIT; + + return bound; +} + +/* From R, allocate and return a malloc'd array of the first H elements + of a random permutation of N elements. H must not exceed N. + Return NULL if H is zero. */ + +size_t * +randperm_new (struct randint_source *r, size_t h, size_t n) +{ + size_t *v; + + switch (h) + { + case 0: + v = NULL; + break; + + case 1: + v = xmalloc (sizeof *v); + v[0] = randint_choose (r, n); + break; + + default: + { + size_t i; + + v = xnmalloc (n, sizeof *v); + for (i = 0; i < n; i++) + v[i] = i; + + for (i = 0; i < h; i++) + { + size_t j = i + randint_choose (r, n - i); + size_t t = v[i]; + v[i] = v[j]; + v[j] = t; + } + + v = xnrealloc (v, h, sizeof *v); + } + break; + } + + return v; +} diff --git a/gl/lib/randperm.h b/gl/lib/randperm.h new file mode 100644 index 000000000..79bbf9fe6 --- /dev/null +++ b/gl/lib/randperm.h @@ -0,0 +1,4 @@ +#include "randint.h" +#include +size_t randperm_bound (size_t, size_t); +size_t *randperm_new (struct randint_source *, size_t, size_t); diff --git a/gl/lib/randread.c b/gl/lib/randread.c new file mode 100644 index 000000000..9f65db676 --- /dev/null +++ b/gl/lib/randread.c @@ -0,0 +1,297 @@ +/* Generate buffers of random data. + + Copyright (C) 2006 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 "randread.h" + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include "gettext.h" +#define _(msgid) gettext (msgid) + +#include "rand-isaac.h" +#include "stdio-safer.h" +#include "unlocked-io.h" +#include "xalloc.h" + +#ifndef MIN +# define MIN(a, b) ((a) < (b) ? (a) : (b)) +#endif + +#ifndef __attribute__ +# if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8) || __STRICT_ANSI__ +# define __attribute__(x) +# endif +#endif + +#ifndef ATTRIBUTE_UNUSED +# define ATTRIBUTE_UNUSED __attribute__ ((__unused__)) +#endif + +#if _STRING_ARCH_unaligned +# define ALIGNED_POINTER(ptr, type) true +#else +# define alignof(type) offsetof (struct { char c; type x; }, x) +# define ALIGNED_POINTER(ptr, type) ((size_t) (ptr) % alignof (type) == 0) +#endif + +#ifndef DEFAULT_RANDOM_FILE +# define DEFAULT_RANDOM_FILE "/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. */ +#define RANDREAD_BUFFER_SIZE (2 * ISAAC_BYTES) + +/* A source of random data for generating random buffers. */ +struct randread_source +{ + /* Stream to read random bytes from. If null, the behavior is + undefined; the current implementation uses ISAAC in this case, + but this is for old-fashioned implementations that lack + /dev/urandom and callers should not rely on this. */ + FILE *source; + + /* Function to call, and its argument, if there is an input error or + end of file when reading from the stream; errno is nonzero if + there was an error. If this function returns, it should fix the + problem before returning. The default handler assumes that + handler_arg is the file name of the source. */ + void (*handler) (void const *); + void const *handler_arg; + + /* The buffer for SOURCE. It's kept here to simplify storage + allocation and to make it easier to clear out buffered random + data. */ + union + { + /* The stream buffer, if SOURCE is not null. */ + char c[RANDREAD_BUFFER_SIZE]; + + /* The buffered ISAAC pseudorandom buffer, if SOURCE is null. */ + struct isaac + { + /* The number of bytes that are buffered at the end of data.b. */ + size_t buffered; + + /* State of the ISAAC generator. */ + struct isaac_state state; + + /* Up to a buffer's worth of pseudorandom data. */ + union + { + uint32_t w[ISAAC_WORDS]; + unsigned char b[ISAAC_BYTES]; + } data; + } isaac; + } buf; +}; + + +/* The default error handler. */ + +static void +randread_error (void const *file_name) +{ + if (file_name) + error (exit_failure, errno, + _(errno == 0 ? "%s: end of file" : "%s: read error"), + quotearg_colon (file_name)); + abort (); +} + +/* Simply return a new randread_source object with the default error + handler. */ + +static struct randread_source * +simple_new (FILE *source, void const *handler_arg) +{ + struct randread_source *s = xmalloc (sizeof *s); + s->source = source; + s->handler = randread_error; + s->handler_arg = handler_arg; + return s; +} + +/* 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 + hard bound; otherwise it is just an estimate. + + If NAME is not null, NAME is saved for use as the argument of the + default handler. Unless a non-default handler is used, NAME's + lifetime should be at least that of the returned value. + + Return NULL (setting errno) on failure. */ + +struct randread_source * +randread_new (char const *name, size_t bytes_bound) +{ + if (bytes_bound == 0) + return simple_new (NULL, NULL); + else + { + char const *file_name = (name ? name : DEFAULT_RANDOM_FILE); + FILE *source = fopen_safer (file_name, "rb"); + struct randread_source *s; + + if (! source) + { + if (name) + return NULL; + file_name = NULL; + } + + s = simple_new (source, file_name); + + if (source) + setvbuf (source, s->buf.c, _IOFBF, MIN (sizeof s->buf.c, bytes_bound)); + else + { + s->buf.isaac.buffered = 0; + isaac_seed (&s->buf.isaac.state); + } + + return s; + } +} + + +/* Set S's handler and its argument. HANDLER (HANDLER_ARG) is called + when there is a read error or end of file from the random data + source; errno is nonzero if there was an error. If HANDLER + returns, it should fix the problem before returning. The default + handler assumes that handler_arg is the file name of the source; it + does not return. */ + +void +randread_set_handler (struct randread_source *s, void (*handler) (void const *)) +{ + s->handler = handler; +} + +void +randread_set_handler_arg (struct randread_source *s, void const *handler_arg) +{ + s->handler_arg = handler_arg; +} + + +/* Place SIZE random bytes into the buffer beginning at P, using + the stream in S. */ + +static void +readsource (struct randread_source *s, unsigned char *p, size_t size) +{ + for (;;) + { + size_t inbytes = fread (p, sizeof *p, size, s->source); + int fread_errno = errno; + p += inbytes; + size -= inbytes; + if (size == 0) + break; + errno = (ferror (s->source) ? fread_errno : 0); + s->handler (s->handler_arg); + } +} + + +/* Place SIZE pseudorandom bytes into the buffer beginning at P, using + the buffered ISAAC generator in ISAAC. */ + +static void +readisaac (struct isaac *isaac, unsigned char *p, size_t size) +{ + size_t inbytes = isaac->buffered; + + for (;;) + { + if (size <= inbytes) + { + memcpy (p, isaac->data.b + ISAAC_BYTES - inbytes, size); + isaac->buffered = inbytes - size; + return; + } + + memcpy (p, isaac->data.b + ISAAC_BYTES - inbytes, inbytes); + p += inbytes; + size -= inbytes; + + /* If P is aligned, write to *P directly to avoid the overhead + of copying from the buffer. */ + if (ALIGNED_POINTER (p, uint32_t)) + { + uint32_t *wp = (uint32_t *) p; + while (ISAAC_BYTES <= size) + { + isaac_refill (&isaac->state, wp); + wp += ISAAC_WORDS; + size -= ISAAC_BYTES; + if (size == 0) + { + isaac->buffered = 0; + return; + } + } + p = (unsigned char *) wp; + } + + isaac_refill (&isaac->state, isaac->data.w); + inbytes = ISAAC_BYTES; + } +} + + +/* Consume random data from *S to generate a random buffer BUF of size + SIZE. */ + +void +randread (struct randread_source *s, void *buf, size_t size) +{ + if (s->source) + readsource (s, buf, size); + else + readisaac (&s->buf.isaac, buf, size); +} + + +/* Clear *S so that it no longer contains undelivered random data, and + deallocate any system resources associated with *S. Return 0 if + successful, a negative number (setting errno) if not (this is rare, + but can occur in theory if there is an input error). */ + +int +randread_free (struct randread_source *s) +{ + FILE *source = s->source; + memset (s, 0, sizeof *s); + free (s); + return (source ? fclose (source) : 0); +} diff --git a/gl/lib/randread.h b/gl/lib/randread.h new file mode 100644 index 000000000..5f044bd30 --- /dev/null +++ b/gl/lib/randread.h @@ -0,0 +1,33 @@ +/* Generate buffers of random data. + + Copyright (C) 2006 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. */ + +#ifndef RANDREAD_H +# define RANDREAD_H 1 + +# include + +struct randread_source; + +struct randread_source *randread_new (char const *, size_t); +void randread (struct randread_source *, void *, size_t); +void randread_set_handler (struct randread_source *, void (*) (void const *)); +void randread_set_handler_arg (struct randread_source *, void const *); +int randread_free (struct randread_source *); + +#endif -- cgit v1.2.3-54-g00ecf