1 /*
2 +----------------------------------------------------------------------+
3 | Copyright (c) The PHP Group |
4 +----------------------------------------------------------------------+
5 | This source file is subject to version 3.01 of the PHP license, |
6 | that is bundled with this package in the file LICENSE, and is |
7 | available through the world-wide-web at the following url: |
8 | https://www.php.net/license/3_01.txt |
9 | If you did not receive a copy of the PHP license and are unable to |
10 | obtain it through the world-wide-web, please send a note to |
11 | license@php.net so we can mail you a copy immediately. |
12 +----------------------------------------------------------------------+
13 | Authors: Rasmus Lerdorf <rasmus@php.net> |
14 | Zeev Suraski <zeev@php.net> |
15 | Pedro Melo <melo@ip.pt> |
16 | Sterling Hughes <sterling@php.net> |
17 | Go Kudo <zeriyoshi@php.net> |
18 | |
19 | Based on code from: Richard J. Wagner <rjwagner@writeme.com> |
20 | Makoto Matsumoto <matumoto@math.keio.ac.jp> |
21 | Takuji Nishimura |
22 | Shawn Cokus <Cokus@math.washington.edu> |
23 +----------------------------------------------------------------------+
24 */
25
26 #ifdef HAVE_CONFIG_H
27 # include "config.h"
28 #endif
29
30 #include "php.h"
31 #include "php_random.h"
32 #include "php_random_csprng.h"
33
34 #include "Zend/zend_exceptions.h"
35
36 /*
37 The following mt19937 algorithms are based on a C++ class MTRand by
38 Richard J. Wagner. For more information see the web page at
39 http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/C-LANG/MersenneTwister.h
40
41 Mersenne Twister random number generator -- a C++ class MTRand
42 Based on code by Makoto Matsumoto, Takuji Nishimura, and Shawn Cokus
43 Richard J. Wagner v1.0 15 May 2003 rjwagner@writeme.com
44
45 The Mersenne Twister is an algorithm for generating random numbers. It
46 was designed with consideration of the flaws in various other generators.
47 The period, 2^19937-1, and the order of equidistribution, 623 dimensions,
48 are far greater. The generator is also fast; it avoids multiplication and
49 division, and it benefits from caches and pipelines. For more information
50 see the inventors' web page at http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
51
52 Reference
53 M. Matsumoto and T. Nishimura, "Mersenne Twister: A 623-Dimensionally
54 Equidistributed Uniform Pseudo-Random Number Generator", ACM Transactions on
55 Modeling and Computer Simulation, Vol. 8, No. 1, January 1998, pp 3-30.
56
57 Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
58 Copyright (C) 2000 - 2003, Richard J. Wagner
59 All rights reserved.
60
61 Redistribution and use in source and binary forms, with or without
62 modification, are permitted provided that the following conditions
63 are met:
64
65 1. Redistributions of source code must retain the above copyright
66 notice, this list of conditions and the following disclaimer.
67
68 2. Redistributions in binary form must reproduce the above copyright
69 notice, this list of conditions and the following disclaimer in the
70 documentation and/or other materials provided with the distribution.
71
72 3. The names of its contributors may not be used to endorse or promote
73 products derived from this software without specific prior written
74 permission.
75
76 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
77 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
78 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
79 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
80 CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
81 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
82 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
83 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
84 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
85 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
86 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
87 */
88
89 #define N MT_N /* length of state vector */
90 #define M (397) /* a period parameter */
91 #define hiBit(u) ((u) & 0x80000000U) /* mask all but highest bit of u */
92 #define loBit(u) ((u) & 0x00000001U) /* mask all but lowest bit of u */
93 #define loBits(u) ((u) & 0x7FFFFFFFU) /* mask the highest bit of u */
94 #define mixBits(u, v) (hiBit(u) | loBits(v)) /* move hi bit of u to hi bit of v */
95
96 #define twist(m,u,v) (m ^ (mixBits(u,v) >> 1) ^ ((uint32_t)(-(int32_t)(loBit(v))) & 0x9908b0dfU))
97 #define twist_php(m,u,v) (m ^ (mixBits(u,v) >> 1) ^ ((uint32_t)(-(int32_t)(loBit(u))) & 0x9908b0dfU))
98
mt19937_reload(php_random_status_state_mt19937 * state)99 static inline void mt19937_reload(php_random_status_state_mt19937 *state)
100 {
101 uint32_t *p = state->state;
102
103 if (state->mode == MT_RAND_MT19937) {
104 for (uint32_t i = N - M; i--; ++p) {
105 *p = twist(p[M], p[0], p[1]);
106 }
107 for (uint32_t i = M; --i; ++p) {
108 *p = twist(p[M-N], p[0], p[1]);
109 }
110 *p = twist(p[M-N], p[0], state->state[0]);
111 } else {
112 for (uint32_t i = N - M; i--; ++p) {
113 *p = twist_php(p[M], p[0], p[1]);
114 }
115 for (uint32_t i = M; --i; ++p) {
116 *p = twist_php(p[M-N], p[0], p[1]);
117 }
118 *p = twist_php(p[M-N], p[0], state->state[0]);
119 }
120
121 state->count = 0;
122 }
123
mt19937_seed_state(php_random_status_state_mt19937 * state,uint64_t seed)124 static inline void mt19937_seed_state(php_random_status_state_mt19937 *state, uint64_t seed)
125 {
126 uint32_t i, prev_state;
127
128 /* Initialize generator state with seed
129 See Knuth TAOCP Vol 2, 3rd Ed, p.106 for multiplier.
130 In previous versions, most significant bits (MSBs) of the seed affect
131 only MSBs of the state array. Modified 9 Jan 2002 by Makoto Matsumoto. */
132 state->state[0] = seed & 0xffffffffU;
133 for (i = 1; i < MT_N; i++) {
134 prev_state = state->state[i - 1];
135 state->state[i] = (1812433253U * (prev_state ^ (prev_state >> 30)) + i) & 0xffffffffU;
136 }
137 state->count = i;
138
139 mt19937_reload(state);
140 }
141
seed(php_random_status * status,uint64_t seed)142 static void seed(php_random_status *status, uint64_t seed)
143 {
144 mt19937_seed_state(status->state, seed);
145 }
146
generate(php_random_status * status)147 static php_random_result generate(php_random_status *status)
148 {
149 php_random_status_state_mt19937 *s = status->state;
150 uint32_t s1;
151
152 if (s->count >= MT_N) {
153 mt19937_reload(s);
154 }
155
156 s1 = s->state[s->count++];
157 s1 ^= (s1 >> 11);
158 s1 ^= (s1 << 7) & 0x9d2c5680U;
159 s1 ^= (s1 << 15) & 0xefc60000U;
160
161 return (php_random_result){
162 .size = sizeof(uint32_t),
163 .result = (uint64_t) (s1 ^ (s1 >> 18)),
164 };
165 }
166
range(php_random_status * status,zend_long min,zend_long max)167 static zend_long range(php_random_status *status, zend_long min, zend_long max)
168 {
169 return php_random_range(&php_random_algo_mt19937, status, min, max);
170 }
171
serialize(php_random_status * status,HashTable * data)172 static bool serialize(php_random_status *status, HashTable *data)
173 {
174 php_random_status_state_mt19937 *s = status->state;
175 zval t;
176
177 for (uint32_t i = 0; i < MT_N; i++) {
178 ZVAL_STR(&t, php_random_bin2hex_le(&s->state[i], sizeof(uint32_t)));
179 zend_hash_next_index_insert(data, &t);
180 }
181 ZVAL_LONG(&t, s->count);
182 zend_hash_next_index_insert(data, &t);
183 ZVAL_LONG(&t, s->mode);
184 zend_hash_next_index_insert(data, &t);
185
186 return true;
187 }
188
unserialize(php_random_status * status,HashTable * data)189 static bool unserialize(php_random_status *status, HashTable *data)
190 {
191 php_random_status_state_mt19937 *s = status->state;
192 zval *t;
193
194 /* Verify the expected number of elements, this implicitly ensures that no additional elements are present. */
195 if (zend_hash_num_elements(data) != (MT_N + 2)) {
196 return false;
197 }
198
199 for (uint32_t i = 0; i < MT_N; i++) {
200 t = zend_hash_index_find(data, i);
201 if (!t || Z_TYPE_P(t) != IS_STRING || Z_STRLEN_P(t) != (2 * sizeof(uint32_t))) {
202 return false;
203 }
204 if (!php_random_hex2bin_le(Z_STR_P(t), &s->state[i])) {
205 return false;
206 }
207 }
208 t = zend_hash_index_find(data, MT_N);
209 if (!t || Z_TYPE_P(t) != IS_LONG) {
210 return false;
211 }
212 s->count = Z_LVAL_P(t);
213 if (s->count > MT_N) {
214 return false;
215 }
216
217 t = zend_hash_index_find(data, MT_N + 1);
218 if (!t || Z_TYPE_P(t) != IS_LONG) {
219 return false;
220 }
221 s->mode = Z_LVAL_P(t);
222 if (s->mode != MT_RAND_MT19937 && s->mode != MT_RAND_PHP) {
223 return false;
224 }
225
226 return true;
227 }
228
229 const php_random_algo php_random_algo_mt19937 = {
230 sizeof(php_random_status_state_mt19937),
231 seed,
232 generate,
233 range,
234 serialize,
235 unserialize
236 };
237
238 /* {{{ php_random_mt19937_seed_default */
php_random_mt19937_seed_default(php_random_status_state_mt19937 * state)239 PHPAPI void php_random_mt19937_seed_default(php_random_status_state_mt19937 *state)
240 {
241 zend_long seed = 0;
242
243 if (php_random_bytes_silent(&seed, sizeof(seed)) == FAILURE) {
244 seed = GENERATE_SEED();
245 }
246
247 mt19937_seed_state(state, (uint64_t) seed);
248 }
249 /* }}} */
250
251 /* {{{ Random\Engine\Mt19937::__construct() */
PHP_METHOD(Random_Engine_Mt19937,__construct)252 PHP_METHOD(Random_Engine_Mt19937, __construct)
253 {
254 php_random_engine *engine = Z_RANDOM_ENGINE_P(ZEND_THIS);
255 php_random_status_state_mt19937 *state = engine->status->state;
256 zend_long seed, mode = MT_RAND_MT19937;
257 bool seed_is_null = true;
258
259 ZEND_PARSE_PARAMETERS_START(0, 2)
260 Z_PARAM_OPTIONAL;
261 Z_PARAM_LONG_OR_NULL(seed, seed_is_null);
262 Z_PARAM_LONG(mode);
263 ZEND_PARSE_PARAMETERS_END();
264
265 switch (mode) {
266 case MT_RAND_MT19937:
267 state->mode = MT_RAND_MT19937;
268 break;
269 case MT_RAND_PHP:
270 zend_error(E_DEPRECATED, "The MT_RAND_PHP variant of Mt19937 is deprecated");
271 state->mode = MT_RAND_PHP;
272 break;
273 default:
274 zend_argument_value_error(2, "must be either MT_RAND_MT19937 or MT_RAND_PHP");
275 RETURN_THROWS();
276 }
277
278 if (seed_is_null) {
279 /* MT19937 has a very large state, uses CSPRNG for seeding only */
280 if (php_random_bytes_throw(&seed, sizeof(seed)) == FAILURE) {
281 zend_throw_exception(random_ce_Random_RandomException, "Failed to generate a random seed", 0);
282 RETURN_THROWS();
283 }
284 }
285
286 mt19937_seed_state(state, seed);
287 }
288 /* }}} */
289
290 /* {{{ Random\Engine\Mt19937::generate() */
PHP_METHOD(Random_Engine_Mt19937,generate)291 PHP_METHOD(Random_Engine_Mt19937, generate)
292 {
293 php_random_engine *engine = Z_RANDOM_ENGINE_P(ZEND_THIS);
294 zend_string *bytes;
295
296 ZEND_PARSE_PARAMETERS_NONE();
297
298 php_random_result generated = engine->algo->generate(engine->status);
299 if (EG(exception)) {
300 RETURN_THROWS();
301 }
302
303 bytes = zend_string_alloc(generated.size, false);
304
305 /* Endianness safe copy */
306 for (size_t i = 0; i < generated.size; i++) {
307 ZSTR_VAL(bytes)[i] = (generated.result >> (i * 8)) & 0xff;
308 }
309 ZSTR_VAL(bytes)[generated.size] = '\0';
310
311 RETURN_STR(bytes);
312 }
313 /* }}} */
314
315 /* {{{ Random\Engine\Mt19937::__serialize() */
PHP_METHOD(Random_Engine_Mt19937,__serialize)316 PHP_METHOD(Random_Engine_Mt19937, __serialize)
317 {
318 php_random_engine *engine = Z_RANDOM_ENGINE_P(ZEND_THIS);
319 zval t;
320
321 ZEND_PARSE_PARAMETERS_NONE();
322
323 array_init(return_value);
324
325 /* members */
326 ZVAL_ARR(&t, zend_std_get_properties(&engine->std));
327 Z_TRY_ADDREF(t);
328 zend_hash_next_index_insert(Z_ARRVAL_P(return_value), &t);
329
330 /* state */
331 array_init(&t);
332 if (!engine->algo->serialize(engine->status, Z_ARRVAL(t))) {
333 zend_throw_exception(NULL, "Engine serialize failed", 0);
334 RETURN_THROWS();
335 }
336 zend_hash_next_index_insert(Z_ARRVAL_P(return_value), &t);
337 }
338 /* }}} */
339
340 /* {{{ Random\Engine\Mt19937::__unserialize() */
PHP_METHOD(Random_Engine_Mt19937,__unserialize)341 PHP_METHOD(Random_Engine_Mt19937, __unserialize)
342 {
343 php_random_engine *engine = Z_RANDOM_ENGINE_P(ZEND_THIS);
344 HashTable *d;
345 zval *t;
346
347 ZEND_PARSE_PARAMETERS_START(1, 1)
348 Z_PARAM_ARRAY_HT(d);
349 ZEND_PARSE_PARAMETERS_END();
350
351 /* Verify the expected number of elements, this implicitly ensures that no additional elements are present. */
352 if (zend_hash_num_elements(d) != 2) {
353 zend_throw_exception_ex(NULL, 0, "Invalid serialization data for %s object", ZSTR_VAL(engine->std.ce->name));
354 RETURN_THROWS();
355 }
356
357 /* members */
358 t = zend_hash_index_find(d, 0);
359 if (!t || Z_TYPE_P(t) != IS_ARRAY) {
360 zend_throw_exception_ex(NULL, 0, "Invalid serialization data for %s object", ZSTR_VAL(engine->std.ce->name));
361 RETURN_THROWS();
362 }
363 object_properties_load(&engine->std, Z_ARRVAL_P(t));
364 if (EG(exception)) {
365 zend_throw_exception_ex(NULL, 0, "Invalid serialization data for %s object", ZSTR_VAL(engine->std.ce->name));
366 RETURN_THROWS();
367 }
368
369 /* state */
370 t = zend_hash_index_find(d, 1);
371 if (!t || Z_TYPE_P(t) != IS_ARRAY) {
372 zend_throw_exception_ex(NULL, 0, "Invalid serialization data for %s object", ZSTR_VAL(engine->std.ce->name));
373 RETURN_THROWS();
374 }
375 if (!engine->algo->unserialize(engine->status, Z_ARRVAL_P(t))) {
376 zend_throw_exception_ex(NULL, 0, "Invalid serialization data for %s object", ZSTR_VAL(engine->std.ce->name));
377 RETURN_THROWS();
378 }
379 }
380 /* }}} */
381
382 /* {{{ Random\Engine\Mt19937::__debugInfo() */
PHP_METHOD(Random_Engine_Mt19937,__debugInfo)383 PHP_METHOD(Random_Engine_Mt19937, __debugInfo)
384 {
385 php_random_engine *engine = Z_RANDOM_ENGINE_P(ZEND_THIS);
386 zval t;
387
388 ZEND_PARSE_PARAMETERS_NONE();
389
390 if (!engine->std.properties) {
391 rebuild_object_properties(&engine->std);
392 }
393 ZVAL_ARR(return_value, zend_array_dup(engine->std.properties));
394
395 if (engine->algo->serialize) {
396 array_init(&t);
397 if (!engine->algo->serialize(engine->status, Z_ARRVAL(t))) {
398 zend_throw_exception(NULL, "Engine serialize failed", 0);
399 RETURN_THROWS();
400 }
401 zend_hash_str_add(Z_ARR_P(return_value), "__states", strlen("__states"), &t);
402 }
403 }
404 /* }}} */
405
