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