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 624 /* length of state vector */
90 ZEND_STATIC_ASSERT(
91 N == sizeof(((php_random_status_state_mt19937*)0)->state) / sizeof(((php_random_status_state_mt19937*)0)->state[0]),
92 "Assumed length of Mt19937 state vector does not match actual size."
93 );
94 #define M (397) /* a period parameter */
95 #define hiBit(u) ((u) & 0x80000000U) /* mask all but highest bit of u */
96 #define loBit(u) ((u) & 0x00000001U) /* mask all but lowest bit of u */
97 #define loBits(u) ((u) & 0x7FFFFFFFU) /* mask the highest bit of u */
98 #define mixBits(u, v) (hiBit(u) | loBits(v)) /* move hi bit of u to hi bit of v */
99
100 #define twist(m,u,v) (m ^ (mixBits(u,v) >> 1) ^ ((uint32_t)(-(int32_t)(loBit(v))) & 0x9908b0dfU))
101 #define twist_php(m,u,v) (m ^ (mixBits(u,v) >> 1) ^ ((uint32_t)(-(int32_t)(loBit(u))) & 0x9908b0dfU))
102
mt19937_reload(php_random_status_state_mt19937 * state)103 static inline void mt19937_reload(php_random_status_state_mt19937 *state)
104 {
105 uint32_t *p = state->state;
106
107 if (state->mode == MT_RAND_MT19937) {
108 for (uint32_t i = N - M; i--; ++p) {
109 *p = twist(p[M], p[0], p[1]);
110 }
111 for (uint32_t i = M; --i; ++p) {
112 *p = twist(p[M-N], p[0], p[1]);
113 }
114 *p = twist(p[M-N], p[0], state->state[0]);
115 } else {
116 for (uint32_t i = N - M; i--; ++p) {
117 *p = twist_php(p[M], p[0], p[1]);
118 }
119 for (uint32_t i = M; --i; ++p) {
120 *p = twist_php(p[M-N], p[0], p[1]);
121 }
122 *p = twist_php(p[M-N], p[0], state->state[0]);
123 }
124
125 state->count = 0;
126 }
127
php_random_mt19937_seed32(php_random_status_state_mt19937 * state,uint32_t seed)128 PHPAPI inline void php_random_mt19937_seed32(php_random_status_state_mt19937 *state, uint32_t seed)
129 {
130 uint32_t i, prev_state;
131
132 /* Initialize generator state with seed
133 See Knuth TAOCP Vol 2, 3rd Ed, p.106 for multiplier.
134 In previous versions, most significant bits (MSBs) of the seed affect
135 only MSBs of the state array. Modified 9 Jan 2002 by Makoto Matsumoto. */
136 state->state[0] = seed;
137 for (i = 1; i < N; i++) {
138 prev_state = state->state[i - 1];
139 state->state[i] = (1812433253U * (prev_state ^ (prev_state >> 30)) + i) & 0xffffffffU;
140 }
141 state->count = i;
142
143 mt19937_reload(state);
144 }
145
generate(void * state)146 static php_random_result generate(void *state)
147 {
148 php_random_status_state_mt19937 *s = state;
149 uint32_t s1;
150
151 if (s->count >= N) {
152 mt19937_reload(s);
153 }
154
155 s1 = s->state[s->count++];
156 s1 ^= (s1 >> 11);
157 s1 ^= (s1 << 7) & 0x9d2c5680U;
158 s1 ^= (s1 << 15) & 0xefc60000U;
159
160 return (php_random_result){
161 .size = sizeof(uint32_t),
162 .result = (uint64_t) (s1 ^ (s1 >> 18)),
163 };
164 }
165
range(void * state,zend_long min,zend_long max)166 static zend_long range(void *state, zend_long min, zend_long max)
167 {
168 return php_random_range((php_random_algo_with_state){
169 .algo = &php_random_algo_mt19937,
170 .state = state,
171 }, min, max);
172 }
173
serialize(void * state,HashTable * data)174 static bool serialize(void *state, HashTable *data)
175 {
176 php_random_status_state_mt19937 *s = state;
177 zval t;
178
179 for (uint32_t i = 0; i < N; i++) {
180 ZVAL_STR(&t, php_random_bin2hex_le(&s->state[i], sizeof(uint32_t)));
181 zend_hash_next_index_insert(data, &t);
182 }
183 ZVAL_LONG(&t, s->count);
184 zend_hash_next_index_insert(data, &t);
185 ZVAL_LONG(&t, s->mode);
186 zend_hash_next_index_insert(data, &t);
187
188 return true;
189 }
190
unserialize(void * state,HashTable * data)191 static bool unserialize(void *state, HashTable *data)
192 {
193 php_random_status_state_mt19937 *s = state;
194 zval *t;
195
196 /* Verify the expected number of elements, this implicitly ensures that no additional elements are present. */
197 if (zend_hash_num_elements(data) != (N + 2)) {
198 return false;
199 }
200
201 for (uint32_t i = 0; i < N; i++) {
202 t = zend_hash_index_find(data, i);
203 if (!t || Z_TYPE_P(t) != IS_STRING || Z_STRLEN_P(t) != (2 * sizeof(uint32_t))) {
204 return false;
205 }
206 if (!php_random_hex2bin_le(Z_STR_P(t), &s->state[i])) {
207 return false;
208 }
209 }
210 t = zend_hash_index_find(data, N);
211 if (!t || Z_TYPE_P(t) != IS_LONG) {
212 return false;
213 }
214 s->count = Z_LVAL_P(t);
215 if (s->count > N) {
216 return false;
217 }
218
219 t = zend_hash_index_find(data, N + 1);
220 if (!t || Z_TYPE_P(t) != IS_LONG) {
221 return false;
222 }
223 s->mode = Z_LVAL_P(t);
224 if (s->mode != MT_RAND_MT19937 && s->mode != MT_RAND_PHP) {
225 return false;
226 }
227
228 return true;
229 }
230
231 const php_random_algo php_random_algo_mt19937 = {
232 sizeof(php_random_status_state_mt19937),
233 generate,
234 range,
235 serialize,
236 unserialize
237 };
238
239 /* {{{ php_random_mt19937_seed_default */
php_random_mt19937_seed_default(php_random_status_state_mt19937 * state)240 PHPAPI void php_random_mt19937_seed_default(php_random_status_state_mt19937 *state)
241 {
242 uint32_t seed = 0;
243
244 if (php_random_bytes_silent(&seed, sizeof(seed)) == FAILURE) {
245 seed = (uint32_t)php_random_generate_fallback_seed();
246 }
247
248 php_random_mt19937_seed32(state, seed);
249 }
250 /* }}} */
251
252 /* {{{ Random\Engine\Mt19937::__construct() */
PHP_METHOD(Random_Engine_Mt19937,__construct)253 PHP_METHOD(Random_Engine_Mt19937, __construct)
254 {
255 php_random_algo_with_state engine = Z_RANDOM_ENGINE_P(ZEND_THIS)->engine;
256 php_random_status_state_mt19937 *state = engine.state;
257 zend_long seed, mode = MT_RAND_MT19937;
258 bool seed_is_null = true;
259
260 ZEND_PARSE_PARAMETERS_START(0, 2)
261 Z_PARAM_OPTIONAL;
262 Z_PARAM_LONG_OR_NULL(seed, seed_is_null);
263 Z_PARAM_LONG(mode);
264 ZEND_PARSE_PARAMETERS_END();
265
266 switch (mode) {
267 case MT_RAND_MT19937:
268 state->mode = MT_RAND_MT19937;
269 break;
270 case MT_RAND_PHP:
271 zend_error(E_DEPRECATED, "The MT_RAND_PHP variant of Mt19937 is deprecated");
272 state->mode = MT_RAND_PHP;
273 break;
274 default:
275 zend_argument_value_error(2, "must be either MT_RAND_MT19937 or MT_RAND_PHP");
276 RETURN_THROWS();
277 }
278
279 if (seed_is_null) {
280 /* MT19937 has a very large state, uses CSPRNG for seeding only */
281 if (php_random_bytes_throw(&seed, sizeof(seed)) == FAILURE) {
282 zend_throw_exception(random_ce_Random_RandomException, "Failed to generate a random seed", 0);
283 RETURN_THROWS();
284 }
285 }
286
287 php_random_mt19937_seed32(state, seed);
288 }
289 /* }}} */
290
291 /* {{{ Random\Engine\Mt19937::generate() */
PHP_METHOD(Random_Engine_Mt19937,generate)292 PHP_METHOD(Random_Engine_Mt19937, generate)
293 {
294 php_random_algo_with_state engine = Z_RANDOM_ENGINE_P(ZEND_THIS)->engine;
295 zend_string *bytes;
296
297 ZEND_PARSE_PARAMETERS_NONE();
298
299 php_random_result generated = engine.algo->generate(engine.state);
300 if (EG(exception)) {
301 RETURN_THROWS();
302 }
303
304 bytes = zend_string_alloc(generated.size, false);
305
306 /* Endianness safe copy */
307 for (size_t i = 0; i < generated.size; i++) {
308 ZSTR_VAL(bytes)[i] = (generated.result >> (i * 8)) & 0xff;
309 }
310 ZSTR_VAL(bytes)[generated.size] = '\0';
311
312 RETURN_STR(bytes);
313 }
314 /* }}} */
315
316 /* {{{ Random\Engine\Mt19937::__serialize() */
PHP_METHOD(Random_Engine_Mt19937,__serialize)317 PHP_METHOD(Random_Engine_Mt19937, __serialize)
318 {
319 php_random_engine *engine = Z_RANDOM_ENGINE_P(ZEND_THIS);
320 zval t;
321
322 ZEND_PARSE_PARAMETERS_NONE();
323
324 array_init(return_value);
325
326 /* members */
327 ZVAL_ARR(&t, zend_std_get_properties(&engine->std));
328 Z_TRY_ADDREF(t);
329 zend_hash_next_index_insert(Z_ARRVAL_P(return_value), &t);
330
331 /* state */
332 array_init(&t);
333 if (!engine->engine.algo->serialize(engine->engine.state, Z_ARRVAL(t))) {
334 zend_throw_exception(NULL, "Engine serialize failed", 0);
335 RETURN_THROWS();
336 }
337 zend_hash_next_index_insert(Z_ARRVAL_P(return_value), &t);
338 }
339 /* }}} */
340
341 /* {{{ Random\Engine\Mt19937::__unserialize() */
PHP_METHOD(Random_Engine_Mt19937,__unserialize)342 PHP_METHOD(Random_Engine_Mt19937, __unserialize)
343 {
344 php_random_engine *engine = Z_RANDOM_ENGINE_P(ZEND_THIS);
345 HashTable *d;
346 zval *t;
347
348 ZEND_PARSE_PARAMETERS_START(1, 1)
349 Z_PARAM_ARRAY_HT(d);
350 ZEND_PARSE_PARAMETERS_END();
351
352 /* Verify the expected number of elements, this implicitly ensures that no additional elements are present. */
353 if (zend_hash_num_elements(d) != 2) {
354 zend_throw_exception_ex(NULL, 0, "Invalid serialization data for %s object", ZSTR_VAL(engine->std.ce->name));
355 RETURN_THROWS();
356 }
357
358 /* members */
359 t = zend_hash_index_find(d, 0);
360 if (!t || Z_TYPE_P(t) != IS_ARRAY) {
361 zend_throw_exception_ex(NULL, 0, "Invalid serialization data for %s object", ZSTR_VAL(engine->std.ce->name));
362 RETURN_THROWS();
363 }
364 object_properties_load(&engine->std, Z_ARRVAL_P(t));
365 if (EG(exception)) {
366 zend_throw_exception_ex(NULL, 0, "Invalid serialization data for %s object", ZSTR_VAL(engine->std.ce->name));
367 RETURN_THROWS();
368 }
369
370 /* state */
371 t = zend_hash_index_find(d, 1);
372 if (!t || Z_TYPE_P(t) != IS_ARRAY) {
373 zend_throw_exception_ex(NULL, 0, "Invalid serialization data for %s object", ZSTR_VAL(engine->std.ce->name));
374 RETURN_THROWS();
375 }
376 if (!engine->engine.algo->unserialize(engine->engine.state, Z_ARRVAL_P(t))) {
377 zend_throw_exception_ex(NULL, 0, "Invalid serialization data for %s object", ZSTR_VAL(engine->std.ce->name));
378 RETURN_THROWS();
379 }
380 }
381 /* }}} */
382
383 /* {{{ Random\Engine\Mt19937::__debugInfo() */
PHP_METHOD(Random_Engine_Mt19937,__debugInfo)384 PHP_METHOD(Random_Engine_Mt19937, __debugInfo)
385 {
386 php_random_engine *engine = Z_RANDOM_ENGINE_P(ZEND_THIS);
387 zval t;
388
389 ZEND_PARSE_PARAMETERS_NONE();
390
391 if (!engine->std.properties) {
392 rebuild_object_properties(&engine->std);
393 }
394 ZVAL_ARR(return_value, zend_array_dup(engine->std.properties));
395
396 if (engine->engine.algo->serialize) {
397 array_init(&t);
398 if (!engine->engine.algo->serialize(engine->engine.state, Z_ARRVAL(t))) {
399 zend_throw_exception(NULL, "Engine serialize failed", 0);
400 RETURN_THROWS();
401 }
402 zend_hash_str_add(Z_ARR_P(return_value), "__states", strlen("__states"), &t);
403 }
404 }
405 /* }}} */
406
