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   assert(l);
 101   if (r->ops->max && r->ops->max >= l) {
 102     w = r->ops->raw;
 103     m = r->ops->max;
 104   } else {
 105     assert(!r->ops->max || r->ops->max >= 256);
 106     w = grand_word;
 107     m = 0xffffffff;
 108   }
 109
 110   /* --- Work out maximum acceptable return value --- *
 111    *
 112    * This will be the highest multiple of @l@ less than @m@.
 113    */
 114
 115   z = m - m%l;
 116
 117   /* --- Generate numbers until something acceptable is found --- *
 118    *
 119    * This will require an expected number of attempts less than 2.
 120    */
 121
 122   do x = w(r); while (x >= z);
 123   return (x%l);
 124 }
 125
 126 /* --- @grand_defaultfill@ --- *
 127  *
 128  * Arguments:   @grand *r@ = pointet to generic generator
 129  *              @void *p@ = pointer to a buffer
 130  *              @size_t sz@ = size of the buffer
 131  *
 132  * Returns:     ---
 133  *
 134  * Use:         Fills a buffer with uniformly distributed pseudorandom bytes.
 135  *              This calls the @byte@ method repeatedly to fill in the output
 136  *              buffer.
 137  */
 138
 139 void grand_defaultfill(grand *r, void *p, size_t sz)
 140   { octet *q = p; while (sz--) *q++ = r->ops->byte(r); }
 141
 142 /*----- Main code ---------------------------------------------------------*/
 143
 144 /* --- @grand_byte@ --- *
 145  *
 146  * Arguments:   @grand *r@ = pointet to generic generator
 147  *
 148  * Returns:     A uniformly-distributed pseudorandom integer in the interval
 149  *              %$[0, 256)$%.
 150  */
 151
 152 octet grand_byte(grand *r)
 153 {
 154   if (r->ops->byte == grand_byte) return (grand_defaultbyte(r));
 155   else return (r->ops->byte(r));
 156 }
 157
 158 /* --- @grand_word@ --- *
 159  *
 160  * Arguments:   @grand *r@ = pointet to generic generator
 161  *
 162  * Returns:     A uniformly-distributed pseudorandom integer in the interval
 163  *              %$[0, 2^{32})$%.
 164  */
 165
 166 uint32 grand_word(grand *r)
 167 {
 168   if (r->ops->word == grand_word) return (grand_defaultword(r));
 169   else return (r->ops->word(r));
 170 }
 171
 172 /* --- @grand_range@ --- *
 173  *
 174  * Arguments:   @grand *r@ = pointet to generic generator
 175  *              @uint32 l@ = limit for acceptable results
 176  *
 177  * Returns:     A uniformly-distributed pseudorandom integer in the interval
 178  *              %$[0, l)$%.
 179  */
 180
 181 uint32 grand_range(grand *r, uint32 l)
 182 {
 183   if (r->ops->range == grand_range) return (grand_defaultrange(r, l));
 184   else return (r->ops->range(r, l));
 185 }
 186
 187 /* --- @grand_fill@ --- *
 188  *
 189  * Arguments:   @grand *r@ = pointet to generic generator
 190  *              @void *p@ = pointer to a buffer
 191  *              @size_t sz@ = size of the buffer
 192  *
 193  * Returns:     ---
 194  *
 195  * Use:         Fills a buffer with uniformly distributed pseudorandom bytes
 196  *              (see @grand_byte@).
 197  */
 198
 199 void grand_fill(grand *r, void *p, size_t sz)
 200 {
 201   if (r->ops->fill == grand_fill) grand_defaultfill(r, p, sz);
 202   else r->ops->fill(r, p, sz);
 203 }
 204
 205 /*----- That's all, folks -------------------------------------------------*/