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
33 #include "Zend/zend_exceptions.h"
34
35 /*
36 The following mt19937 algorithms are based on a C++ class MTRand by
37 Richard J. Wagner. For more information see the web page at
38 http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/C-LANG/MersenneTwister.h
39
40 Mersenne Twister random number generator -- a C++ class MTRand
41 Based on code by Makoto Matsumoto, Takuji Nishimura, and Shawn Cokus
42 Richard J. Wagner v1.0 15 May 2003 rjwagner@writeme.com
43
44 The Mersenne Twister is an algorithm for generating random numbers. It
45 was designed with consideration of the flaws in various other generators.
46 The period, 2^19937-1, and the order of equidistribution, 623 dimensions,
47 are far greater. The generator is also fast; it avoids multiplication and
48 division, and it benefits from caches and pipelines. For more information
49 see the inventors' web page at http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
50
51 Reference
52 M. Matsumoto and T. Nishimura, "Mersenne Twister: A 623-Dimensionally
53 Equidistributed Uniform Pseudo-Random Number Generator", ACM Transactions on
54 Modeling and Computer Simulation, Vol. 8, No. 1, January 1998, pp 3-30.
55
56 Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
57 Copyright (C) 2000 - 2003, Richard J. Wagner
58 All rights reserved.
59
60 Redistribution and use in source and binary forms, with or without
61 modification, are permitted provided that the following conditions
62 are met:
63
64 1. Redistributions of source code must retain the above copyright
65 notice, this list of conditions and the following disclaimer.
66
67 2. Redistributions in binary form must reproduce the above copyright
68 notice, this list of conditions and the following disclaimer in the
69 documentation and/or other materials provided with the distribution.
70
71 3. The names of its contributors may not be used to endorse or promote
72 products derived from this software without specific prior written
73 permission.
74
75 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
76 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
77 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
78 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
79 CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
80 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
81 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
82 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
83 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
84 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
85 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
86 */
87
88 #define N MT_N /* length of state vector */
89 #define M (397) /* a period parameter */
90 #define hiBit(u) ((u) & 0x80000000U) /* mask all but highest bit of u */
91 #define loBit(u) ((u) & 0x00000001U) /* mask all but lowest bit of u */
92 #define loBits(u) ((u) & 0x7FFFFFFFU) /* mask the highest bit of u */
93 #define mixBits(u, v) (hiBit(u) | loBits(v)) /* move hi bit of u to hi bit of v */
94
95 #define twist(m,u,v) (m ^ (mixBits(u,v) >> 1) ^ ((uint32_t)(-(int32_t)(loBit(v))) & 0x9908b0dfU))
96 #define twist_php(m,u,v) (m ^ (mixBits(u,v) >> 1) ^ ((uint32_t)(-(int32_t)(loBit(u))) & 0x9908b0dfU))
97
mt19937_reload(php_random_status_state_mt19937 * state)98 static inline void mt19937_reload(php_random_status_state_mt19937 *state)
99 {
100 uint32_t *p = state->state;
101
102 if (state->mode == MT_RAND_MT19937) {
103 for (uint32_t i = N - M; i--; ++p) {
104 *p = twist(p[M], p[0], p[1]);
105 }
106 for (uint32_t i = M; --i; ++p) {
107 *p = twist(p[M-N], p[0], p[1]);
108 }
109 *p = twist(p[M-N], p[0], state->state[0]);
110 } else {
111 for (uint32_t i = N - M; i--; ++p) {
112 *p = twist_php(p[M], p[0], p[1]);
113 }
114 for (uint32_t i = M; --i; ++p) {
115 *p = twist_php(p[M-N], p[0], p[1]);
116 }
117 *p = twist_php(p[M-N], p[0], state->state[0]);
118 }
119
120 state->count = 0;
121 }
122
mt19937_seed_state(php_random_status_state_mt19937 * state,uint64_t seed)123 static inline void mt19937_seed_state(php_random_status_state_mt19937 *state, uint64_t seed)
124 {
125 uint32_t i, prev_state;
126
127 /* Initialize generator state with seed
128 See Knuth TAOCP Vol 2, 3rd Ed, p.106 for multiplier.
129 In previous versions, most significant bits (MSBs) of the seed affect
130 only MSBs of the state array. Modified 9 Jan 2002 by Makoto Matsumoto. */
131 state->state[0] = seed & 0xffffffffU;
132 for (i = 1; i < MT_N; i++) {
133 prev_state = state->state[i - 1];
134 state->state[i] = (1812433253U * (prev_state ^ (prev_state >> 30)) + i) & 0xffffffffU;
135 }
136 state->count = i;
137
138 mt19937_reload(state);
139 }
140
seed(php_random_status * status,uint64_t seed)141 static void seed(php_random_status *status, uint64_t seed)
142 {
143 mt19937_seed_state(status->state, seed);
144 }
145
generate(php_random_status * status)146 static uint64_t generate(php_random_status *status)
147 {
148 php_random_status_state_mt19937 *s = status->state;
149 uint32_t s1;
150
151 if (s->count >= MT_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 (uint64_t) (s1 ^ (s1 >> 18));
161 }
162
range(php_random_status * status,zend_long min,zend_long max)163 static zend_long range(php_random_status *status, zend_long min, zend_long max)
164 {
165 return php_random_range(&php_random_algo_mt19937, status, min, max);
166 }
167
serialize(php_random_status * status,HashTable * data)168 static bool serialize(php_random_status *status, HashTable *data)
169 {
170 php_random_status_state_mt19937 *s = status->state;
171 zval t;
172
173 for (uint32_t i = 0; i < MT_N; i++) {
174 ZVAL_STR(&t, php_random_bin2hex_le(&s->state[i], sizeof(uint32_t)));
175 zend_hash_next_index_insert(data, &t);
176 }
177 ZVAL_LONG(&t, s->count);
178 zend_hash_next_index_insert(data, &t);
179 ZVAL_LONG(&t, s->mode);
180 zend_hash_next_index_insert(data, &t);
181
182 return true;
183 }
184
unserialize(php_random_status * status,HashTable * data)185 static bool unserialize(php_random_status *status, HashTable *data)
186 {
187 php_random_status_state_mt19937 *s = status->state;
188 zval *t;
189
190 /* Verify the expected number of elements, this implicitly ensures that no additional elements are present. */
191 if (zend_hash_num_elements(data) != (MT_N + 2)) {
192 return false;
193 }
194
195 for (uint32_t i = 0; i < MT_N; i++) {
196 t = zend_hash_index_find(data, i);
197 if (!t || Z_TYPE_P(t) != IS_STRING || Z_STRLEN_P(t) != (2 * sizeof(uint32_t))) {
198 return false;
199 }
200 if (!php_random_hex2bin_le(Z_STR_P(t), &s->state[i])) {
201 return false;
202 }
203 }
204 t = zend_hash_index_find(data, MT_N);
205 if (!t || Z_TYPE_P(t) != IS_LONG) {
206 return false;
207 }
208 s->count = Z_LVAL_P(t);
209 if (s->count > MT_N) {
210 return false;
211 }
212
213 t = zend_hash_index_find(data, MT_N + 1);
214 if (!t || Z_TYPE_P(t) != IS_LONG) {
215 return false;
216 }
217 s->mode = Z_LVAL_P(t);
218 if (s->mode != MT_RAND_MT19937 && s->mode != MT_RAND_PHP) {
219 return false;
220 }
221
222 return true;
223 }
224
225 const php_random_algo php_random_algo_mt19937 = {
226 sizeof(uint32_t),
227 sizeof(php_random_status_state_mt19937),
228 seed,
229 generate,
230 range,
231 serialize,
232 unserialize
233 };
234
235 /* {{{ php_random_mt19937_seed_default */
php_random_mt19937_seed_default(php_random_status_state_mt19937 * state)236 PHPAPI void php_random_mt19937_seed_default(php_random_status_state_mt19937 *state)
237 {
238 zend_long seed = 0;
239
240 if (php_random_bytes_silent(&seed, sizeof(zend_long)) == FAILURE) {
241 seed = GENERATE_SEED();
242 }
243
244 mt19937_seed_state(state, (uint64_t) seed);
245 }
246 /* }}} */
247
248 /* {{{ Random\Engine\Mt19937::__construct() */
PHP_METHOD(Random_Engine_Mt19937,__construct)249 PHP_METHOD(Random_Engine_Mt19937, __construct)
250 {
251 php_random_engine *engine = Z_RANDOM_ENGINE_P(ZEND_THIS);
252 php_random_status_state_mt19937 *state = engine->status->state;
253 zend_long seed, mode = MT_RAND_MT19937;
254 bool seed_is_null = true;
255
256 ZEND_PARSE_PARAMETERS_START(0, 2)
257 Z_PARAM_OPTIONAL;
258 Z_PARAM_LONG_OR_NULL(seed, seed_is_null);
259 Z_PARAM_LONG(mode);
260 ZEND_PARSE_PARAMETERS_END();
261
262 switch (mode) {
263 case MT_RAND_MT19937:
264 state->mode = MT_RAND_MT19937;
265 break;
266 case MT_RAND_PHP:
267 zend_error(E_DEPRECATED, "The MT_RAND_PHP variant of Mt19937 is deprecated");
268 state->mode = MT_RAND_PHP;
269 break;
270 default:
271 zend_argument_value_error(2, "must be either MT_RAND_MT19937 or MT_RAND_PHP");
272 RETURN_THROWS();
273 }
274
275 if (seed_is_null) {
276 /* MT19937 has a very large state, uses CSPRNG for seeding only */
277 if (php_random_bytes_throw(&seed, sizeof(zend_long)) == FAILURE) {
278 zend_throw_exception(random_ce_Random_RandomException, "Failed to generate a random seed", 0);
279 RETURN_THROWS();
280 }
281 }
282
283 engine->algo->seed(engine->status, seed);
284 }
285 /* }}} */
286
287 /* {{{ Random\Engine\Mt19937::generate() */
PHP_METHOD(Random_Engine_Mt19937,generate)288 PHP_METHOD(Random_Engine_Mt19937, generate)
289 {
290 php_random_engine *engine = Z_RANDOM_ENGINE_P(ZEND_THIS);
291 uint64_t generated;
292 size_t size;
293 zend_string *bytes;
294
295 ZEND_PARSE_PARAMETERS_NONE();
296
297 generated = engine->algo->generate(engine->status);
298 size = engine->status->last_generated_size;
299 if (EG(exception)) {
300 RETURN_THROWS();
301 }
302
303 bytes = zend_string_alloc(size, false);
304
305 /* Endianness safe copy */
306 for (size_t i = 0; i < size; i++) {
307 ZSTR_VAL(bytes)[i] = (generated >> (i * 8)) & 0xff;
308 }
309 ZSTR_VAL(bytes)[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
