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

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