chiark - git - mdw - catacomb/blob - fibrand.c

   1 /* -*-c-*-
   2  *
   3  * $Id: fibrand.c,v 1.4 2002/10/09 00:35:18 mdw Exp $
   4  *
   5  * Fibonacci generator
   6  *
   7  * (c) 1999 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of Catacomb.
  13  *
  14  * Catacomb is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU Library General Public License as
  16  * published by the Free Software Foundation; either version 2 of the
  17  * License, or (at your option) any later version.
  18  *
  19  * Catacomb is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU Library General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU Library General Public
  25  * License along with Catacomb; if not, write to the Free
  26  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  27  * MA 02111-1307, USA.
  28  */
  29
  30 /*----- Revision history --------------------------------------------------*
  31  *
  32  * $Log: fibrand.c,v $
  33  * Revision 1.4  2002/10/09 00:35:18  mdw
  34  * Fix bogus type name.
  35  *
  36  * Revision 1.3  2000/12/06 20:31:06  mdw
  37  * Simplify uniform range transformation.
  38  *
  39  * Revision 1.2  2000/06/17 10:55:24  mdw
  40  * Typesetting fixes.  Add flags word to generatic random generator.
  41  *
  42  * Revision 1.1  1999/12/10 23:15:27  mdw
  43  * Noncryptographic random number generator.
  44  *
  45  */
  46
  47 /*----- Header files ------------------------------------------------------*/
  48
  49 #include <stdarg.h>
  50 #include <stdio.h>
  51 #include <stdlib.h>
  52 #include <string.h>
  53
  54 #include <mLib/bits.h>
  55 #include <mLib/sub.h>
  56
  57 #include "fibrand.h"
  58 #include "grand.h"
  59 #include "lcrand.h"
  60
  61 /*----- Main code ---------------------------------------------------------*/
  62
  63 /* --- @fibrand_step@ --- *
  64  *
  65  * Arguments:   @fibrand *f@ = pointer to Fibonacci generator context
  66  *
  67  * Returns:     Next output from generator.
  68  *
  69  * Use:         Steps the generator.  Returns
  70  *              %$x_{i - 24} + x_{i - 55} \bmod 2^{32}$%.
  71  */
  72
  73 uint32 fibrand_step(fibrand *f)
  74 {
  75   unsigned i = f->i;
  76   unsigned j = i + (FIB_SZ - FIB_TAP);
  77   uint32 x;
  78   if (j >= FIB_SZ)
  79     j -= FIB_SZ;
  80   x = f->x[i] = U32(f->x[i] + f->x[j]);
  81   i++;
  82   if (i >= FIB_SZ)
  83     i = 0;
  84   f->i = i;
  85   return (x);
  86 }
  87
  88 /* --- @fibrand_seed@ --- *
  89  *
  90  * Arguments:   @fibrand *f@ = pointer to Fibonacci generator context
  91  *              @grand *r@ = random number generator to extract words from
  92  *
  93  * Returns:     ---
  94  *
  95  * Use:         Initializes a Fibonacci generator using word outputs from the
  96  *              given random number source @r@.
  97  */
  98
  99 void fibrand_seed(fibrand *f, grand *r)
 100 {
 101   int i;
 102   unsigned p = 0;
 103
 104   for (i = 0; i < FIB_SZ; i++)
 105     p |= f->x[i] = r->ops->word(r);
 106   if (!(p & 1)) {
 107     i = r->ops->range(r, FIB_SZ);
 108     f->x[i] |= 1;
 109   }
 110   f->i = 0;
 111 }
 112
 113 /* --- @fibrand_lcseed@ --- *
 114  *
 115  * Arguments:   @fibrand *f@ = pointer to Fibonacci generator context
 116  *              @uint32 seed@ = seed value
 117  *
 118  * Returns:     ---
 119  *
 120  * Use:         Initializes a Fibonacci generator using outputs from the
 121  *              @lcrand@ generator seeded from @seed@.  This is faster than
 122  *              using a generic @lcrand@-based generator and @fibrand_rseed@
 123  *              because it uses raw outputs rather than uniformly distributed
 124  *              32-bit words.
 125  */
 126
 127 void fibrand_lcseed(fibrand *f, uint32 seed)
 128 {
 129   int i;
 130   unsigned p = 0;
 131
 132   for (i = 0; i < FIB_SZ; i++)
 133     p |= f->x[i] = seed = lcrand(seed);
 134   if (!(p & 1)) {
 135     i = lcrand_range(&seed, FIB_SZ);
 136     f->x[i] |= 1;
 137   }
 138   f->i = 0;
 139 }
 140
 141 /* --- @fibrand_range@ --- *
 142  *
 143  * Arguments:   @fibrand *f@ = pointer to Fibonacci generator context
 144  *              @uint32 m@ = limit
 145  *
 146  * Returns:     A uniformly distributed pseudorandom integer in the interval
 147  *              %$[0, m)$%.
 148  */
 149
 150 uint32 fibrand_range(fibrand *f, uint32 m)
 151 {
 152   uint32 r = 0xffffffff - (0xffffffff % m);
 153   uint32 x;
 154
 155   /* --- Now generate numbers until a good one comes along --- */
 156
 157   do x = fibrand_step(f); while (x >= r);
 158   return (x % m);
 159 }
 160
 161 /*----- Generic interface -------------------------------------------------*/
 162
 163 typedef struct gctx {
 164   grand r;
 165   fibrand f;
 166 } gctx;
 167
 168 static void gdestroy(grand *r)
 169 {
 170   gctx *g = (gctx *)r;
 171   DESTROY(g);
 172 }
 173
 174 static int gmisc(grand *r, unsigned op, ...)
 175 {
 176   gctx *g = (gctx *)r;
 177   va_list ap;
 178   int rc = 0;
 179   va_start(ap, op);
 180
 181   switch (op) {
 182     case GRAND_CHECK:
 183       switch (va_arg(ap, unsigned)) {
 184         case GRAND_CHECK:
 185         case GRAND_SEEDINT:
 186         case GRAND_SEEDUINT32:
 187         case GRAND_SEEDRAND:
 188           rc = 1;
 189           break;
 190         default:
 191           rc = 0;
 192           break;
 193       }
 194       break;
 195     case GRAND_SEEDINT:
 196       fibrand_lcseed(&g->f, va_arg(ap, unsigned));
 197       break;
 198     case GRAND_SEEDUINT32:
 199       fibrand_lcseed(&g->f, va_arg(ap, uint32));
 200       break;
 201     case GRAND_SEEDRAND:
 202       fibrand_seed(&g->f, va_arg(ap, grand *));
 203       break;
 204     default:
 205       GRAND_BADOP;
 206       break;
 207   }
 208
 209   va_end(ap);
 210   return (rc);
 211 }
 212
 213 static octet gbyte(grand *r)
 214 {
 215   gctx *g = (gctx *)r;
 216   return (U8(fibrand_step(&g->f)));
 217 }
 218
 219 static uint32 gword(grand *r)
 220 {
 221   gctx *g = (gctx *)r;
 222   return (fibrand_step(&g->f));
 223 }
 224
 225 static uint32 grange(grand *r, uint32 l)
 226 {
 227   gctx *g = (gctx *)r;
 228   return (fibrand_range(&g->f, l));
 229 }
 230
 231 static void gfill(grand *r, void *p, size_t sz)
 232 {
 233   gctx *g = (gctx *)r;
 234   octet *q = p;
 235   while (sz) {
 236     *q++ = U8(fibrand_step(&g->f));
 237     sz--;
 238   }
 239 }
 240
 241 static const grand_ops gops = {
 242   "fibrand",
 243   0, 0,
 244   gmisc, gdestroy,
 245   gword, gbyte, gword, grange, gfill
 246 };
 247
 248 /* --- @fibrand_create@ --- *
 249  *
 250  * Arguments:   @uint32 seed@ = initial seed
 251  *
 252  * Returns:     Pointer to a generic generator.
 253  *
 254  * Use:         Constructs a generic generator interface over a Fibonacci
 255  *              generator.  The generator is seeded using @fibrand_lcseed@.
 256  */
 257
 258 grand *fibrand_create(uint32 seed)
 259 {
 260   gctx *g = CREATE(gctx);
 261   g->r.ops = &gops;
 262   fibrand_lcseed(&g->f, seed);
 263   return (&g->r);
 264 }
 265
 266 /*----- That's all, folks -------------------------------------------------*/