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

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