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

   1 /* -*-c-*-
   2  *
   3  * $Id: fibrand.c,v 1.2 2000/06/17 10:55:24 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.2  2000/06/17 10:55:24  mdw
  34  * Typesetting fixes.  Add flags word to generatic random generator.
  35  *
  36  * Revision 1.1  1999/12/10 23:15:27  mdw
  37  * Noncryptographic random number generator.
  38  *
  39  */
  40
  41 /*----- Header files ------------------------------------------------------*/
  42
  43 #include <stdarg.h>
  44 #include <stdio.h>
  45 #include <stdlib.h>
  46 #include <string.h>
  47
  48 #include <mLib/bits.h>
  49 #include <mLib/sub.h>
  50
  51 #include "fibrand.h"
  52 #include "grand.h"
  53 #include "lcrand.h"
  54
  55 /*----- Main code ---------------------------------------------------------*/
  56
  57 /* --- @fibrand_step@ --- *
  58  *
  59  * Arguments:   @fibrand *f@ = pointer to Fibonacci generator context
  60  *
  61  * Returns:     Next output from generator.
  62  *
  63  * Use:         Steps the generator.  Returns
  64  *              %$x_{i - 24} + x_{i - 55} \bmod 2^{32}$%.
  65  */
  66
  67 uint32 fibrand_step(fibrand *f)
  68 {
  69   unsigned i = f->i;
  70   unsigned j = i + (FIB_SZ - FIB_TAP);
  71   uint32 x;
  72   if (j >= FIB_SZ)
  73     j -= FIB_SZ;
  74   x = f->x[i] = U32(f->x[i] + f->x[j]);
  75   i++;
  76   if (i >= FIB_SZ)
  77     i = 0;
  78   f->i = i;
  79   return (x);
  80 }
  81
  82 /* --- @fibrand_seed@ --- *
  83  *
  84  * Arguments:   @fibrand *f@ = pointer to Fibonacci generator context
  85  *              @grand *r@ = random number generator to extract words from
  86  *
  87  * Returns:     ---
  88  *
  89  * Use:         Initializes a Fibonacci generator using word outputs from the
  90  *              given random number source @r@.
  91  */
  92
  93 void fibrand_seed(fibrand *f, grand *r)
  94 {
  95   int i;
  96   unsigned p = 0;
  97
  98   for (i = 0; i < FIB_SZ; i++)
  99     p |= f->x[i] = r->ops->word(r);
 100   if (!(p & 1)) {
 101     i = r->ops->range(r, FIB_SZ);
 102     f->x[i] |= 1;
 103   }
 104   f->i = 0;
 105 }
 106
 107 /* --- @fibrand_lcseed@ --- *
 108  *
 109  * Arguments:   @fibrand *f@ = pointer to Fibonacci generator context
 110  *              @uint32 seed@ = seed value
 111  *
 112  * Returns:     ---
 113  *
 114  * Use:         Initializes a Fibonacci generator using outputs from the
 115  *              @lcrand@ generator seeded from @seed@.  This is faster than
 116  *              using a generic @lcrand@-based generator and @fibrand_rseed@
 117  *              because it uses raw outputs rather than uniformly distributed
 118  *              32-bit words.
 119  */
 120
 121 void fibrand_lcseed(fibrand *f, uint32 seed)
 122 {
 123   int i;
 124   unsigned p = 0;
 125
 126   for (i = 0; i < FIB_SZ; i++)
 127     p |= f->x[i] = seed = lcrand(seed);
 128   if (!(p & 1)) {
 129     i = lcrand_range(&seed, FIB_SZ);
 130     f->x[i] |= 1;
 131   }
 132   f->i = 0;
 133 }
 134
 135 /* --- @fibrand_range@ --- *
 136  *
 137  * Arguments:   @fibrand *f@ = pointer to Fibonacci generator context
 138  *              @uint32 m@ = limit
 139  *
 140  * Returns:     A uniformly distributed pseudorandom integer in the interval
 141  *              %$[0, m)$%.
 142  */
 143
 144 uint32 fibrand_range(fibrand *f, uint32 m)
 145 {
 146   uint32 r = 0xffffffff - (0xffffffff % m);
 147   uint x;
 148
 149   /* --- Now generate numbers until a good one comes along --- */
 150
 151   do x = fibrand_step(f); while (x >= r);
 152   return (x / (r / m));
 153 }
 154
 155 /*----- Generic interface -------------------------------------------------*/
 156
 157 typedef struct gctx {
 158   grand r;
 159   fibrand f;
 160 } gctx;
 161
 162 static void gdestroy(grand *r)
 163 {
 164   gctx *g = (gctx *)r;
 165   DESTROY(g);
 166 }
 167
 168 static int gmisc(grand *r, unsigned op, ...)
 169 {
 170   gctx *g = (gctx *)r;
 171   va_list ap;
 172   int rc = 0;
 173   va_start(ap, op);
 174
 175   switch (op) {
 176     case GRAND_CHECK:
 177       switch (va_arg(ap, unsigned)) {
 178         case GRAND_CHECK:
 179         case GRAND_SEEDINT:
 180         case GRAND_SEEDUINT32:
 181         case GRAND_SEEDRAND:
 182           rc = 1;
 183           break;
 184         default:
 185           rc = 0;
 186           break;
 187       }
 188       break;
 189     case GRAND_SEEDINT:
 190       fibrand_lcseed(&g->f, va_arg(ap, unsigned));
 191       break;
 192     case GRAND_SEEDUINT32:
 193       fibrand_lcseed(&g->f, va_arg(ap, uint32));
 194       break;
 195     case GRAND_SEEDRAND:
 196       fibrand_seed(&g->f, va_arg(ap, grand *));
 197       break;
 198     default:
 199       GRAND_BADOP;
 200       break;
 201   }
 202
 203   va_end(ap);
 204   return (rc);
 205 }
 206
 207 static octet gbyte(grand *r)
 208 {
 209   gctx *g = (gctx *)r;
 210   return (U8(fibrand_step(&g->f)));
 211 }
 212
 213 static uint32 gword(grand *r)
 214 {
 215   gctx *g = (gctx *)r;
 216   return (fibrand_step(&g->f));
 217 }
 218
 219 static uint32 grange(grand *r, uint32 l)
 220 {
 221   gctx *g = (gctx *)r;
 222   return (fibrand_range(&g->f, l));
 223 }
 224
 225 static void gfill(grand *r, void *p, size_t sz)
 226 {
 227   gctx *g = (gctx *)r;
 228   octet *q = p;
 229   while (sz) {
 230     *q++ = U8(fibrand_step(&g->f));
 231     sz--;
 232   }
 233 }
 234
 235 static const grand_ops gops = {
 236   "fibrand",
 237   0, 0,
 238   gmisc, gdestroy,
 239   gword, gbyte, gword, grange, gfill
 240 };
 241
 242 /* --- @fibrand_create@ --- *
 243  *
 244  * Arguments:   @uint32 seed@ = initial seed
 245  *
 246  * Returns:     Pointer to a generic generator.
 247  *
 248  * Use:         Constructs a generic generator interface over a Fibonacci
 249  *              generator.  The generator is seeded using @fibrand_lcseed@.
 250  */
 251
 252 grand *fibrand_create(uint32 seed)
 253 {
 254   gctx *g = CREATE(gctx);
 255   g->r.ops = &gops;
 256   fibrand_lcseed(&g->f, seed);
 257   return (&g->r);
 258 }
 259
 260 /*----- That's all, folks -------------------------------------------------*/