xref: /PHP-8.4/ext/random/engine_mt19937.c (revision 1fbb6665)
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 PHPAPI 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 	ZVAL_ARR(return_value, zend_array_dup(zend_std_get_properties_ex(&engine->std)));
392 
393 	if (engine->engine.algo->serialize) {
394 		array_init(&t);
395 		if (!engine->engine.algo->serialize(engine->engine.state, Z_ARRVAL(t))) {
396 			zend_throw_exception(NULL, "Engine serialize failed", 0);
397 			RETURN_THROWS();
398 		}
399 		zend_hash_str_add(Z_ARR_P(return_value), "__states", strlen("__states"), &t);
400 	}
401 }
402 /* }}} */
403