git.pond.sub.org Git - empserver/blob - src/lib/gen/chance.c

   1 /*
   2  *  Empire - A multi-player, client/server Internet based war game.
   3  *  Copyright (C) 1986-2013, Dave Pare, Jeff Bailey, Thomas Ruschak,
   4  *                Ken Stevens, Steve McClure, Markus Armbruster
   5  *
   6  *  Empire is free software: you can redistribute it and/or modify
   7  *  it under the terms of the GNU General Public License as published by
   8  *  the Free Software Foundation, either version 3 of the License, or
   9  *  (at your option) any later version.
  10  *
  11  *  This program is distributed in the hope that it will be useful,
  12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  *  GNU General Public License for more details.
  15  *
  16  *  You should have received a copy of the GNU General Public License
  17  *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  18  *
  19  *  ---
  20  *
  21  *  See files README, COPYING and CREDITS in the root of the source
  22  *  tree for related information and legal notices.  It is expected
  23  *  that future projects/authors will amend these files as needed.
  24  *
  25  *  ---
  26  *
  27  *  chance.c: Roll dice
  28  *
  29  *  Known contributors to this file:
  30  *     Markus Armbruster, 2006-2012
  31  */
  32
  33 #include <config.h>
  34
  35 #include <fcntl.h>
  36 #include <math.h>
  37 #include <stdint.h>
  38 #include <stdlib.h>
  39 #include <sys/time.h>
  40 #include <unistd.h>
  41 #include "chance.h"
  42 #include "mt19937ar.h"
  43
  44 /*
  45  * Return non-zero with probability D.
  46  */
  47 int
  48 chance(double d)
  49 {
  50     return d > genrand_real2();
  51 }
  52
  53 /*
  54  * Return non-zero with probability PCT%.
  55  */
  56 int
  57 pct_chance(int pct)
  58 {
  59     return roll(100) <= pct;
  60 }
  61
  62 static unsigned
  63 round_up_to_pow2(unsigned val)
  64 {
  65     val--;
  66     val |= val >> 1;
  67     val |= val >> 2;
  68     val |= val >> 4;
  69     val |= val >> 8;
  70     val |= val >> 16;
  71     val++;
  72     return val;
  73 }
  74
  75 /*
  76  * Return a random number in [0..N-1].
  77  * N must be in [1..2^31-1].
  78  */
  79 int
  80 roll0(int n)
  81 {
  82     unsigned pow2 = round_up_to_pow2(n);
  83     int r;
  84
  85     do
  86         r = genrand_int32() & (pow2 - 1);
  87     while (r >= n);
  88     return r;
  89 }
  90
  91 /*
  92  * Return a random number in [1..N].
  93  * N must be in [0..2^31-1].
  94  */
  95 int
  96 roll(int n)
  97 {
  98     return 1 + roll0(n);
  99 }
 100
 101 /*
 102  * Round VAL to nearest integer (on the average).
 103  * VAL's fractional part is chance to round up.
 104  */
 105 int
 106 roundavg(double val)
 107 {
 108     double flr = floor(val);
 109     return (int)(flr + chance(val - flr));
 110 }
 111
 112 /*
 113  * Seed the pseudo-random number generator with SEED.
 114  * The sequence of pseudo-random numbers is repeatable by seeding it
 115  * with the same value.
 116  */
 117 void
 118 seed_prng(unsigned seed)
 119 {
 120     init_genrand(seed);
 121 }
 122
 123 static uint32_t
 124 djb_hash(uint32_t hash, void *buf, size_t sz)
 125 {
 126     unsigned char *bp;
 127
 128     for (bp = buf; bp < (unsigned char *)buf + sz; bp++)
 129         hash = hash * 33 ^ *bp;
 130
 131     return hash;
 132 }
 133
 134 /*
 135  * Pick a reasonably random seed for the pseudo-random number generator.
 136  */
 137 unsigned
 138 pick_seed(void)
 139 {
 140     int fd;
 141     uint32_t seed;
 142     int got_seed = 0;
 143     struct timeval tv;
 144     pid_t pid;
 145
 146     /*
 147      * Modern systems provide random number devices, but the details
 148      * vary.  On many systems, /dev/random blocks when the kernel
 149      * entropy pool has been depleted, while /dev/urandom doesn't.
 150      * The former should only be used for generating long-lived
 151      * cryptographic keys.  On other systems, both devices behave
 152      * exactly the same, or only /dev/random exists.
 153      *
 154      * Try /dev/urandom first, and if it can't be opened, blindly try
 155      * /dev/random.
 156      */
 157     fd = open("/dev/urandom", O_RDONLY | O_NONBLOCK);
 158     if (fd < 0)
 159         fd = open("/dev/random", O_RDONLY | O_NONBLOCK);
 160     if (fd >= 0) {
 161         got_seed = read(fd, &seed, sizeof(seed)) == sizeof(seed);
 162         close(fd);
 163     }
 164
 165     if (!got_seed) {
 166         /* Kernel didn't provide, fall back to hashing time and PID */
 167         gettimeofday(&tv, NULL);
 168         seed = djb_hash(5381, &tv, sizeof(tv));
 169         pid = getpid();
 170         seed = djb_hash(seed, &pid, sizeof(pid));
 171     }
 172
 173     return seed;
 174 }