Fix PRNG seeding to resist guessing
[empserver] / 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 }