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

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