Coverage Report

Created: 2025-06-13 06:43

/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
/* }}} */