From 07871354bfa8bbbacb6c6a1966f25b596119c146 Mon Sep 17 00:00:00 2001 From: mdw Date: Fri, 10 Dec 1999 23:15:28 +0000 Subject: [PATCH] Noncryptographic random number generator. --- fibrand.c | 257 +++++++++++++++++++++++++++++++++++++++++++++++++ fibrand.h | 147 ++++++++++++++++++++++++++++ lcrand.c | 307 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ lcrand.h | 126 ++++++++++++++++++++++++ tests/lcrand | 36 +++++++ 5 files changed, 873 insertions(+) create mode 100644 fibrand.c create mode 100644 fibrand.h create mode 100644 lcrand.c create mode 100644 lcrand.h create mode 100644 tests/lcrand diff --git a/fibrand.c b/fibrand.c new file mode 100644 index 0000000..44856e7 --- /dev/null +++ b/fibrand.c @@ -0,0 +1,257 @@ +/* -*-c-*- + * + * $Id: fibrand.c,v 1.1 1999/12/10 23:15:27 mdw Exp $ + * + * Fibonacci generator + * + * (c) 1999 Straylight/Edgeware + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Catacomb. + * + * Catacomb is free software; you can redistribute it and/or modify + * it under the terms of the GNU Library General Public License as + * published by the Free Software Foundation; either version 2 of the + * License, or (at your option) any later version. + * + * Catacomb 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 Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with Catacomb; if not, write to the Free + * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: fibrand.c,v $ + * Revision 1.1 1999/12/10 23:15:27 mdw + * Noncryptographic random number generator. + * + */ + +/*----- Header files ------------------------------------------------------*/ + +#include +#include +#include +#include + +#include +#include + +#include "fibrand.h" +#include "grand.h" +#include "lcrand.h" + +/*----- Main code ---------------------------------------------------------*/ + +/* --- @fibrand_step@ --- * + * + * Arguments: @fibrand *f@ = pointer to Fibonacci generator context + * + * Returns: Next output from generator. + * + * Use: Steps the generator. Returns + * %$x_{i - 24} + x_{i - 55} \bmod 2^{32}%$. + */ + +uint32 fibrand_step(fibrand *f) +{ + unsigned i = f->i; + unsigned j = i + (FIB_SZ - FIB_TAP); + uint32 x; + if (j >= FIB_SZ) + j -= FIB_SZ; + x = f->x[i] = U32(f->x[i] + f->x[j]); + i++; + if (i >= FIB_SZ) + i = 0; + f->i = i; + return (x); +} + +/* --- @fibrand_seed@ --- * + * + * Arguments: @fibrand *f@ = pointer to Fibonacci generator context + * @grand *r@ = random number generator to extract words from + * + * Returns: --- + * + * Use: Initializes a Fibonacci generator using word outputs from the + * given random number source @r@. + */ + +void fibrand_seed(fibrand *f, grand *r) +{ + int i; + unsigned p = 0; + + for (i = 0; i < FIB_SZ; i++) + p |= f->x[i] = r->ops->word(r); + if (!(p & 1)) { + i = r->ops->range(r, FIB_SZ); + f->x[i] |= 1; + } + f->i = 0; +} + +/* --- @fibrand_lcseed@ --- * + * + * Arguments: @fibrand *f@ = pointer to Fibonacci generator context + * @uint32 seed@ = seed value + * + * Returns: --- + * + * Use: Initializes a Fibonacci generator using outputs from the + * @lcrand@ generator seeded from @seed@. This is faster than + * using a generic @lcrand@-based generator and @fibrand_rseed@ + * because it uses raw outputs rather than uniformly distributed + * 32-bit words. + */ + +void fibrand_lcseed(fibrand *f, uint32 seed) +{ + int i; + unsigned p = 0; + + for (i = 0; i < FIB_SZ; i++) + p |= f->x[i] = seed = lcrand(seed); + if (!(p & 1)) { + i = lcrand_range(&seed, FIB_SZ); + f->x[i] |= 1; + } + f->i = 0; +} + +/* --- @fibrand_range@ --- * + * + * Arguments: @fibrand *f@ = pointer to Fibonacci generator context + * @uint32 m@ = limit + * + * Returns: A uniformly distributed pseudorandom integer in the interval + * %$[0, m)$%. + */ + +uint32 fibrand_range(fibrand *f, uint32 m) +{ + uint32 r = 0xffffffff - (0xffffffff % m); + uint x; + + /* --- Now generate numbers until a good one comes along --- */ + + do x = fibrand_step(f); while (x >= r); + return (x / (r / m)); +} + +/*----- Generic interface -------------------------------------------------*/ + +typedef struct gctx { + grand r; + fibrand f; +} gctx; + +static void gdestroy(grand *r) +{ + gctx *g = (gctx *)r; + DESTROY(g); +} + +static int gmisc(grand *r, unsigned op, ...) +{ + gctx *g = (gctx *)r; + va_list ap; + int rc = 0; + va_start(ap, op); + + switch (op) { + case GRAND_CHECK: + switch (va_arg(ap, unsigned)) { + case GRAND_CHECK: + case GRAND_SEEDINT: + case GRAND_SEEDUINT32: + case GRAND_SEEDRAND: + rc = 1; + break; + default: + rc = 0; + break; + } + break; + case GRAND_SEEDINT: + fibrand_lcseed(&g->f, va_arg(ap, unsigned)); + break; + case GRAND_SEEDUINT32: + fibrand_lcseed(&g->f, va_arg(ap, uint32)); + break; + case GRAND_SEEDRAND: + fibrand_seed(&g->f, va_arg(ap, grand *)); + break; + default: + GRAND_BADOP; + break; + } + + va_end(ap); + return (rc); +} + +static octet gbyte(grand *r) +{ + gctx *g = (gctx *)r; + return (U8(fibrand_step(&g->f))); +} + +static uint32 gword(grand *r) +{ + gctx *g = (gctx *)r; + return (fibrand_step(&g->f)); +} + +static uint32 grange(grand *r, uint32 l) +{ + gctx *g = (gctx *)r; + return (fibrand_range(&g->f, l)); +} + +static void gfill(grand *r, void *p, size_t sz) +{ + gctx *g = (gctx *)r; + octet *q = p; + while (sz) { + *q++ = U8(fibrand_step(&g->f)); + sz--; + } +} + +static const grand_ops gops = { + "fibrand", + 0, + gmisc, gdestroy, + gword, gbyte, gword, grange, gfill +}; + +/* --- @fibrand_create@ --- * + * + * Arguments: @uint32 seed@ = initial seed + * + * Returns: Pointer to a generic generator. + * + * Use: Constructs a generic generator interface over a Fibonacci + * generator. The generator is seeded using @fibrand_lcseed@. + */ + +grand *fibrand_create(uint32 seed) +{ + gctx *g = CREATE(gctx); + g->r.ops = &gops; + fibrand_lcseed(&g->f, seed); + return (&g->r); +} + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/fibrand.h b/fibrand.h new file mode 100644 index 0000000..27c39f3 --- /dev/null +++ b/fibrand.h @@ -0,0 +1,147 @@ +/* -*-c-*- + * + * $Id: fibrand.h,v 1.1 1999/12/10 23:15:27 mdw Exp $ + * + * Fibonacci generator + * + * (c) 1999 Straylight/Edgeware + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Catacomb. + * + * Catacomb is free software; you can redistribute it and/or modify + * it under the terms of the GNU Library General Public License as + * published by the Free Software Foundation; either version 2 of the + * License, or (at your option) any later version. + * + * Catacomb 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 Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with Catacomb; if not, write to the Free + * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: fibrand.h,v $ + * Revision 1.1 1999/12/10 23:15:27 mdw + * Noncryptographic random number generator. + * + */ + +/*----- Notes on the Fibonacci generator ----------------------------------* + * + * The generator was originally suggested by G. J. Mitchell and D. P. Moore + * in 1957, and publicized by D. E. Knuth as Algorithm 3.2.2A in volume 2 of + * his work `The Art of Computer Programming'. The generator is simple: at + * each stage it emits %$x_n = (x_{n - 55} + x_{n - 24}) \bmod 2^{32}$%. The + * period is proven to be greater than %$2^{55}$%, and statistical properties + * appear to be good. + */ + +#ifndef CATACOMB_FIBRAND_H +#define CATACOMB_FIBRAND_H + +#ifdef __cplusplus + extern "C" { +#endif + +/*----- Header files ------------------------------------------------------*/ + +#include + +#ifndef CATACOMB_GRAND_H +# include "grand.h" +#endif + +/*----- Magic constants ---------------------------------------------------*/ + +#define FIB_SZ 55 +#define FIB_TAP 24 + +/*----- Data structures ---------------------------------------------------*/ + +typedef struct fibrand { + unsigned i; + uint32 x[FIB_SZ]; +} fibrand; + +/*----- Functions provided ------------------------------------------------*/ + +/* --- @fibrand_step@ --- * + * + * Arguments: @fibrand *f@ = pointer to Fibonacci generator context + * + * Returns: Next output from generator. + * + * Use: Steps the generator. Returns + * %$x_{i - 24} + x_{i - 55} \bmod 2^{32}%$. + */ + +extern uint32 fibrand_step(fibrand */*f*/); + +/* --- @fibrand_seed@ --- * + * + * Arguments: @fibrand *f@ = pointer to Fibonacci generator context + * @grand *r@ = random number generator to extract words from + * + * Returns: --- + * + * Use: Initializes a Fibonacci generator using word outputs from the + * given random number source @r@. + */ + +extern void fibrand_seed(fibrand */*f*/, grand */*r*/); + +/* --- @fibrand_lcseed@ --- * + * + * Arguments: @fibrand *f@ = pointer to Fibonacci generator context + * @uint32 seed@ = seed value + * + * Returns: --- + * + * Use: Initializes a Fibonacci generator using outputs from the + * @lcrand@ generator seeded from @seed@. This is faster than + * using a generic @lcrand@-based generator and @fibrand_rseed@ + * because it uses raw outputs rather than uniformly distributed + * 32-bit words. + */ + +extern void fibrand_lcseed(fibrand */*f*/, uint32 /*seed*/); + +/* --- @fibrand_range@ --- * + * + * Arguments: @fibrand *f@ = pointer to Fibonacci generator context + * @uint32 m@ = limit + * + * Returns: A uniformly distributed pseudorandom integer in the interval + * %$[0, m)$%. + */ + +extern uint32 fibrand_range(fibrand */*f*/, uint32 /*m*/); + +/* --- @fibrand_create@ --- * + * + * Arguments: @uint32 seed@ = initial seed + * + * Returns: Pointer to a generic generator. + * + * Use: Constructs a generic generator interface over a Fibonacci + * generator. The generator is seeded using @fibrand_lcseed@. + */ + +extern grand *fibrand_create(uint32 /*seed*/); + +/*----- That's all, folks -------------------------------------------------*/ + +#ifdef __cplusplus + } +#endif + +#endif diff --git a/lcrand.c b/lcrand.c new file mode 100644 index 0000000..3686e17 --- /dev/null +++ b/lcrand.c @@ -0,0 +1,307 @@ +/* -*-c-*- + * + * $Id: lcrand.c,v 1.1 1999/12/10 23:15:27 mdw Exp $ + * + * Simple linear congruential generator + * + * (c) 1999 Straylight/Edgeware + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Catacomb. + * + * Catacomb is free software; you can redistribute it and/or modify + * it under the terms of the GNU Library General Public License as + * published by the Free Software Foundation; either version 2 of the + * License, or (at your option) any later version. + * + * Catacomb 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 Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with Catacomb; if not, write to the Free + * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: lcrand.c,v $ + * Revision 1.1 1999/12/10 23:15:27 mdw + * Noncryptographic random number generator. + * + */ + +/*----- Header files ------------------------------------------------------*/ + +#include +#include +#include +#include + +#include +#include + +#include "grand.h" +#include "lcrand.h" + +/*----- Magic numbers -----------------------------------------------------*/ + +/* --- The generator parameters --- */ + +#define P LCRAND_P /* Modulus */ +#define A LCRAND_A /* Multiplier (primitive mod @p@) */ +#define C LCRAND_C /* Additive constant */ + +/* --- Precomputed values for modular reduction --- */ + +#define D 5 /* %$p = 2^{32} - d$% */ + +/* --- Other useful bits --- */ + +#define P256 4294967040u /* Highest multiple of 256 < %$p$% */ + +/*----- Main code ---------------------------------------------------------*/ + +/* --- @lcrand@ --- * + * + * Arguments: @uint32 x@ = seed value + * + * Returns: New state of the generator. + * + * Use: Steps the generator. Returns %$ax + c \bmod p$%. + */ + +uint32 lcrand(uint32 x) +{ + uint32 a[2], xx[2]; + uint32 yy[2]; + + /* --- Unpack things into the arrays --- */ + + a[0] = U16(A); a[1] = U16(A >> 16); + xx[0] = U16(x); xx[1] = U16(x >> 16); + + /* --- Multiply everything together --- * + * + * This is plain old long multiplication, although it looks a bit strange. + * I set up the top and bottom partial products directly where they're + * supposed to be. The cross terms I add together, with the low 16 bits in + * @q@ and the high 32 bits in @p@. These I then add into the product. + */ + + { + uint32 p, q; + + yy[0] = a[0] * xx[0]; + yy[1] = a[1] * xx[1]; + + p = a[0] * xx[1]; + q = p + a[1] * xx[0]; + p = ((q < p) << 16) + (q >> 16); + q = U16(q) << 16; + + q += yy[0]; + if (q < yy[0]) + p++; + else + p += (q >> 16) >> 16; + yy[0] = q; + + yy[1] += p; + } + + /* --- Now reduce mod p --- * + * + * I'm using shifts and adds to do the multiply step here. This needs to + * be changed if @D@ ever becomes something other than 5. + */ + +#if D != 5 +# error "Change shift sequence!" +#endif + + { + uint32 q; + + q = yy[1]; + x = yy[0]; + + while (q) { + uint32 y, z; + y = q >> 30; + z = q << 2; + z += q; + if (z < q) + y++; + else + y += (q >> 16) >> 16; + q = y; + x += z; + if (x < z || x > P) + x -= P; + } + } + + /* --- Now add on the constant --- */ + + x += C; + if (x < C || x >= P) + x -= P; + + /* --- Done --- */ + + return (x); +} + +/* --- @lcrand_range@ --- * + * + * Arguments: @uint32 *x@ = pointer to seed value (updated) + * @uint32 m@ = limit allowable + * + * Returns: A uniformly distributed pseudorandom integer in the interval + * %$[0, m)$%. + */ + +uint32 lcrand_range(uint32 *x, uint32 m) +{ + uint32 xx = *x; + uint32 r = P - P % m; + do xx = lcrand(xx); while (xx >= r); + *x = xx; + return (xx / (r / m)); +} + +/*----- Generic interface -------------------------------------------------*/ + +typedef struct gctx { + grand r; + uint32 x; +} gctx; + +static void gdestroy(grand *r) +{ + gctx *g = (gctx *)r; + DESTROY(g); +} + +static int gmisc(grand *r, unsigned op, ...) +{ + gctx *g = (gctx *)r; + va_list ap; + int rc = 0; + va_start(ap, op); + + switch (op) { + case GRAND_CHECK: + switch (va_arg(ap, unsigned)) { + case GRAND_CHECK: + case GRAND_SEEDINT: + case GRAND_SEEDUINT32: + rc = 1; + break; + default: + rc = 0; + break; + } + break; + case GRAND_SEEDINT: + g->x = va_arg(ap, unsigned); + break; + case GRAND_SEEDUINT32: + g->x = va_arg(ap, uint32); + break; + default: + GRAND_BADOP; + break; + } + + va_end(ap); + return (rc); +} + +static uint32 graw(grand *r) +{ + gctx *g = (gctx *)r; + g->x = lcrand(g->x); + return (g->x); +} + +static octet gbyte(grand *r) +{ + gctx *g = (gctx *)r; + uint32 x = g->x; + do x = lcrand(x); while (x >= P256); + g->x = x; + return (x / (P256 / 256)); +} + +static uint32 grange(grand *r, uint32 l) +{ + gctx *g = (gctx *)r; + return (lcrand_range(&g->x, l)); +} + +static const grand_ops gops = { + "lcrand", + LCRAND_P, + gmisc, gdestroy, + graw, gbyte, grand_word, grange, grand_fill +}; + +/* --- @lcrand_create@ --- * + * + * Arguments: @uint32 x@ = initial seed + * + * Returns: Pointer to a generic generator. + * + * Use: Constructs a generic generator interface over a linear + * congruential generator. + */ + +grand *lcrand_create(uint32 x) +{ + gctx *g = CREATE(gctx); + g->r.ops = &gops; + g->x = x; + return (&g->r); +} + +/*----- Test rig ----------------------------------------------------------*/ + +#ifdef TEST_RIG + +#include + +static int verify(dstr *v) +{ + uint32 x = *(uint32 *)v[0].buf; + uint32 y = *(uint32 *)v[1].buf; + uint32 z = lcrand(x); + int ok = 1; + if (y != z) { + fprintf(stderr, + "\n*** lcrand failed. lcrand(%lu) = %lu, expected %lu\n", + (unsigned long)x, (unsigned long)z, (unsigned long)y); + ok = 0; + } + return (ok); +} + +static test_chunk tests[] = { + { "lcrand", verify, { &type_uint32, &type_uint32, 0 } }, + { 0, 0, { 0 } } +}; + +int main(int argc, char *argv[]) +{ + test_run(argc, argv, tests, SRCDIR"/tests/lcrand"); + return (0); +} + +#endif + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/lcrand.h b/lcrand.h new file mode 100644 index 0000000..24429c6 --- /dev/null +++ b/lcrand.h @@ -0,0 +1,126 @@ +/* -*-c-*- + * + * $Id: lcrand.h,v 1.1 1999/12/10 23:15:27 mdw Exp $ + * + * Simple linear congruential generator + * + * (c) 1999 Straylight/Edgeware + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Catacomb. + * + * Catacomb is free software; you can redistribute it and/or modify + * it under the terms of the GNU Library General Public License as + * published by the Free Software Foundation; either version 2 of the + * License, or (at your option) any later version. + * + * Catacomb 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 Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with Catacomb; if not, write to the Free + * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: lcrand.h,v $ + * Revision 1.1 1999/12/10 23:15:27 mdw + * Noncryptographic random number generator. + * + */ + +#ifndef CATACOMB_LCRAND_H +#define CATACOMB_LCRAND_H + +#ifdef __cplusplus + extern "C" { +#endif + +/*----- Notes on the linear congruential generator ------------------------* + * + * This pseudorandom number generator is simple, but has absolutely no + * cryptographic strength whatever. It may be used whenever random numbers + * are required but cryptographic strength is not, for example when + * generating numbers for use in primality tests. To be honest, it's not + * even particularly fast, although a certain amount of effort has been + * expended on making it better than awfully slow. + * + * There exists a fixed-point input @LCRAND_FIXEDPT@ -- when fed to the + * generator it comes straight back out again. All other inputs less than + * the modulus are part of the same sequence of period %$p - 1$%. + * + * The generator has been tested for its statistical properties. George + * Marsaglia's Diehard tests give it a reasonably clean bill of health. + * + * The modulus %$p$% is chosen as the largest prime number less than + * %$2^{32}$%. The multiplier %$a$% and additive constant %$c$% are based on + * the decimal expansions of %$\pi$% and %$e$%, with the additional + * restriction that the multiplier must be a primitive element modulo %$p$%. + * The fixed point value is determined as %$c / (1 - a) \bmod p$%. + */ + +/*----- Header files ------------------------------------------------------*/ + +#include + +#ifndef CATACOMB_GRAND_H +# include "grand.h" +#endif + +/*----- Constants ---------------------------------------------------------*/ + +#define LCRAND_P 4294967291u /* Modulus for the generator */ +#define LCRAND_A 314159265u /* Multiplier (primitive mod @p@) */ +#define LCRAND_C 271828183u /* Additive constant */ + +#define LCRAND_FIXEDPT 3223959250u /* Fixed point (only bad input) */ + +/*----- Functions provided ------------------------------------------------*/ + +/* --- @lcrand@ --- * + * + * Arguments: @uint32 x@ = seed value + * + * Returns: New state of the generator. + * + * Use: Steps the generator. Returns %$ax + c \bmod p$%. + */ + +extern uint32 lcrand(uint32 /*x*/); + +/* --- @lcrand_range@ --- * + * + * Arguments: @uint32 *x@ = pointer to seed value (updated) + * @uint32 m@ = limit allowable + * + * Returns: A uniformly distributed pseudorandom integer in the interval + * %$[0, m)$%. + */ + +extern uint32 lcrand_range(uint32 */*x*/, uint32 /*m*/); + +/* --- @lcrand_create@ --- * + * + * Arguments: @uint32 x@ = initial seed + * + * Returns: Pointer to a generic generator. + * + * Use: Constructs a generic generator interface over a linear + * congruential generator. + */ + +extern grand *lcrand_create(uint32 /*x*/); + +/*----- That's all, folks -------------------------------------------------*/ + +#ifdef __cplusplus + } +#endif + +#endif diff --git a/tests/lcrand b/tests/lcrand new file mode 100644 index 0000000..138632b --- /dev/null +++ b/tests/lcrand @@ -0,0 +1,36 @@ +# Test vectors for linear congruential generator +# +# $Id: lcrand,v 1.1 1999/12/10 23:15:28 mdw Exp $ + +lcrand { + + # --- Standard stuff --- + + 0 271828183; + 271828183 996300340; + 996300340 228306184; + 228306184 1171467301; + 1171467301 3265426054; + 3265426054 2636049353; + 2636049353 3799512036; + 3799512036 2414373801; + 2414373801 1059474234; + 1059474234 2734911993; + 2734911993 239668818; + 239668818 1752802481; + 1752802481 34386946; + 34386946 1344553049; + 1344553049 1121833700; + 1121833700 636134543; + + # --- Particular outputs --- + + 2282233179 4294967290; + 2624567577 0; + 2966901975 1; + + # --- Fixed point --- + + 3223959250 3223959250; +} + -- 2.11.0