chiark - git - mdw - catacomb/blob - rand/grand.c

   1 /* -*-c-*-
   2  *
   3  * Generic interface to random number generators
   4  *
   5  * (c) 1999 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of Catacomb.
  11  *
  12  * Catacomb is free software; you can redistribute it and/or modify
  13  * it under the terms of the GNU Library General Public License as
  14  * published by the Free Software Foundation; either version 2 of the
  15  * License, or (at your option) any later version.
  16  *
  17  * Catacomb is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20  * GNU Library General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU Library General Public
  23  * License along with Catacomb; if not, write to the Free
  24  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  25  * MA 02111-1307, USA.
  26  */
  27
  28 /*----- Header files ------------------------------------------------------*/
  29
  30 #include <stddef.h>
  31
  32 #include <mLib/bits.h>
  33
  34 #include "grand.h"
  35
  36 /*----- Default operations ------------------------------------------------*/
  37
  38 /* --- @grand_defaultbyte@ --- *
  39  *
  40  * Arguments:   @grand *r@ = pointet to generic generator
  41  *
  42  * Returns:     A uniformly-distributed pseudorandom integer in the interval
  43  *              %$[0, 256)$%.
  44  *
  45  * Use:         Default @byte@ output method.  This calls the @range@ method
  46  *              to return a uniform random value between 0 and 255.
  47  */
  48
  49 octet grand_defaultbyte(grand *r)
  50   { return (r->ops->range(r, 256)); }
  51
  52 /* --- @grand_defaultword@ --- *
  53  *
  54  * Arguments:   @grand *r@ = pointet to generic generator
  55  *
  56  * Returns:     A uniformly-distributed pseudorandom integer in the interval
  57  *              %$[0, 2^{32})$%.
  58  *
  59  * Use:         Default @word@ output method.  This calls the @fill@ method
  60  *              to fill a 4-octet buffer with uniform random bytes, and then
  61  *              converts them to an integer.
  62  */
  63
  64 uint32 grand_defaultword(grand *r)
  65   { octet buf[4]; r->ops->fill(r, buf, sizeof(buf)); return (LOAD32(buf)); }
  66
  67 /* --- @grand_defaultrange@ --- *
  68  *
  69  * Arguments:   @grand *r@ = pointet to generic generator
  70  *              @uint32 l@ = limit for acceptable results
  71  *
  72  * Returns:     A uniformly-distributed pseudorandom integer in the interval
  73  *              %$[0, l)$%.
  74  *
  75  * Use:         Default @range@ output method.  This falls back to either
  76  *              @word@ (if the generator's @max@ is zero, or if @max < l@) or
  77  *              @raw@ (otherwise).  This might recurse via @fill@ and @byte@,
  78  *              but this is safe because of the constraint on the @raw@
  79  *              method.
  80  */
  81
  82 uint32 grand_defaultrange(grand *r, uint32 l)
  83 {
  84   uint32 m, z;
  85   uint32 (*w)(grand */*r*/);
  86   uint32 x;
  87
  88   /* --- Decide where to get data from --- *
  89    *
  90    * The choice of %$2^{32} - 1$% as a limit when using @grand_word@ isn't
  91    * wonderful, but working with %$2^{32}$% is awkward and the loss of a few
  92    * return values isn't significant.  The algorithm below still successfully
  93    * returns uniformly distributed results.
  94    *
  95    * If there's a raw generator, and it can cope with the limit, then use it;
  96    * otherwise use the @word@ generator, which may recurse via @fill@ and
  97    * @byte@, but by that point it must be able to satisfy us.
  98    */
  99
 100   if (r->ops->max && r->ops->max >= l) {
 101     w = r->ops->raw;
 102     m = r->ops->max;
 103   } else {
 104     assert(!r->ops->max || r->ops->max >= 256);
 105     w = grand_word;
 106     m = 0xffffffff;
 107   }
 108
 109   /* --- Work out maximum acceptable return value --- *
 110    *
 111    * This will be the highest multiple of @l@ less than @m@.
 112    */
 113
 114   z = m - m%l;
 115
 116   /* --- Generate numbers until something acceptable is found --- *
 117    *
 118    * This will require an expected number of attempts less than 2.
 119    */
 120
 121   do x = w(r); while (x >= z);
 122   return (x%l);
 123 }
 124
 125 /* --- @grand_defaultfill@ --- *
 126  *
 127  * Arguments:   @grand *r@ = pointet to generic generator
 128  *              @void *p@ = pointer to a buffer
 129  *              @size_t sz@ = size of the buffer
 130  *
 131  * Returns:     ---
 132  *
 133  * Use:         Fills a buffer with uniformly distributed pseudorandom bytes.
 134  *              This calls the @byte@ method repeatedly to fill in the output
 135  *              buffer.
 136  */
 137
 138 void grand_defaultfill(grand *r, void *p, size_t sz)
 139   { octet *q = p; while (sz--) *q++ = r->ops->byte(r); }
 140
 141 /*----- Main code ---------------------------------------------------------*/
 142
 143 /* --- @grand_byte@ --- *
 144  *
 145  * Arguments:   @grand *r@ = pointet to generic generator
 146  *
 147  * Returns:     A uniformly-distributed pseudorandom integer in the interval
 148  *              %$[0, 256)$%.
 149  */
 150
 151 octet grand_byte(grand *r)
 152 {
 153   if (r->ops->byte == grand_byte) return (grand_defaultbyte(r));
 154   else return (r->ops->byte(r));
 155 }
 156
 157 /* --- @grand_word@ --- *
 158  *
 159  * Arguments:   @grand *r@ = pointet to generic generator
 160  *
 161  * Returns:     A uniformly-distributed pseudorandom integer in the interval
 162  *              %$[0, 2^{32})$%.
 163  */
 164
 165 uint32 grand_word(grand *r)
 166 {
 167   if (r->ops->word == grand_word) return (grand_defaultword(r));
 168   else return (r->ops->word(r));
 169 }
 170
 171 /* --- @grand_range@ --- *
 172  *
 173  * Arguments:   @grand *r@ = pointet to generic generator
 174  *              @uint32 l@ = limit for acceptable results
 175  *
 176  * Returns:     A uniformly-distributed pseudorandom integer in the interval
 177  *              %$[0, l)$%.
 178  */
 179
 180 uint32 grand_range(grand *r, uint32 l)
 181 {
 182   if (r->ops->range == grand_range) return (grand_defaultrange(r, l));
 183   else return (r->ops->range(r, l));
 184 }
 185
 186 /* --- @grand_fill@ --- *
 187  *
 188  * Arguments:   @grand *r@ = pointet to generic generator
 189  *              @void *p@ = pointer to a buffer
 190  *              @size_t sz@ = size of the buffer
 191  *
 192  * Returns:     ---
 193  *
 194  * Use:         Fills a buffer with uniformly distributed pseudorandom bytes
 195  *              (see @grand_byte@).
 196  */
 197
 198 void grand_fill(grand *r, void *p, size_t sz)
 199 {
 200   if (r->ops->fill == grand_fill) grand_defaultfill(r, p, sz);
 201   else r->ops->fill(r, p, sz);
 202 }
 203
 204 /*----- That's all, folks -------------------------------------------------*/