Differences

This shows you the differences between two versions of the page.

--- rfc:rng_extension [2021/05/25 15:40] – str_shuffle has drop-in replacement API zeriyoshi
+++ rfc:rng_extension [2021/09/03 13:53] – fix: missing CSPRNG functions. zeriyoshi
@@ Line 1: / Line 1: @@
-====== PHP RFC: Add Random class ======
+====== PHP RFC: Random Extension 3.0 ======
-  * Version: 0.3
+  * Version: 3.0
-  * Date: 2021-05-18
+  * Date: 2021-09-02
   * Author: Go Kudo <zeriyoshi@gmail.com>
-  * Status: Draft
+  * Status: Under Discussion
+  * Implementation: https://github.com/php/php-src/pull/7453
   * First Published at: http://wiki.php.net/rfc/object_scope_prng
 ===== Introduction =====
-PHP is currently having problems with RNG reproducibility.
-PHP's RNG has been unified into an implementation using the Mersenne twister, with the rand() and srand() functions becoming aliases for mt_rand() and mt_srand() respectively in PHP 7.1.
+Currently, PHP's random number implementation suffers from several problems.
-But, these functions still store the state in the global state of PHP and are not easily reproducible. Look at the following example.
+The first is that there are many different implementations. Historically, the random number implementations have been separated into lcg.c, rand.c, mt_rand.c random.c respectively, and the header file dependencies are complex.
+Second, the pseudo-random number generator makes use of global state. If a random number is consumed at an unexpected time, the reproducibility of the result may be lost. Look at the following example.
 <code php>
@@ Line 26: / Line 28: @@
 </code>
-As mentioned above, the reproducibility of random numbers can easily be lost if additional processing is added later.
+Reproducibility of random numbers can easily be lost if additional code is added later.
-In addition, the fiber extension was introduced in PHP 8.1. This makes it more difficult to keep track of the execution order. However, this problem has existed since the inception of Generator.
+In addition, the fiber extension was introduced in PHP 8.1. This makes it more difficult to keep track of the execution order. However, this problem has existed since the introduced of Generator.
 There is also the problem of functions that implicitly use the state stored in PHP's global state. shuffle(), str_shuffle(), and array_rand() functions implicitly advance the state of a random number. This means that the following code is not reproducible, but it is difficult for the user to notice this.
@@ Line 42: / Line 44: @@
 ===== Proposal =====
-Implements Random class.
-This class implement to ext/standard, always bundled PHP core.
+Clean up the implementation, separate out the random number related functions as Random extension, and add an object scoped API.
-The PHP code that represents the implementation is as follows:
+All of the following functions will be moved to the newly created Random extension.
-<code php>
+  * lcg_value()
-const RANDOM_XORSHIFT128PLUS = 'xorshift128plus'; // fast, lightweight, default
+  * srand()
-const RANDOM_MT19937 = 'mt19937'; // for compatibility
+  * rand()
-const RANDOM_SECURE = 'secure'; // required Cryptographically-Secure PRNG
+  * mt_srand()
-const RANDOM_USER = 'user'; // userland implementation
+  * mt_rand()
+  * random_int()
+  * random_bytes()
-class Random
+At the same time, the following internal APIs will also be relocated. If you want to use them, you can simply include ext/random/random.h.
-{
-    public function __construct(string $algo = RANDOM_XORSHIFT128PLUS, ?int $seed = null);
-    // For user.
+  * php_random_int_throw()
-    public static function getNonBiasedMax(string $algo): int;
+  * php_random_int_silent()
-    public function getInt(int $min = PHP_INT_MIN, int $max = PHP_INT_MAX): int;
+  * php_combined_lcg()
-    public function getBytes(int $length): string;
+  * php_mt_srand()
-    public function shuffleArray(array $array): array;
+  * php_mt_rand()
-    public function shuffleString(string $string): string;
+  * php_mt_rand_range()
+  * php_mt_rand_common()
+  * php_srand()
+  * php_rand()
+  * php_random_bytes()
+  * php_random_int()
-    // For serialize / unserialize. (but, NOT always available.)
+The following PHP constants will now be provided by the Random extension
-    public function __serialize(): array;
-    public function __unserialize(array $data): void;
-    // MUST override in RANDOM_USER.
+  * MT_RAND_MT19937
-    protected function next(): int;
+  * MT_RAND_PHP
-}
-</code>
-This single class is used to provide the processing using PRNG.
+To solve the scope problem, the following classes will be added
-This class switches the PRNG implementation to be used by the constructor argument $algo. It is just like the password_hash() function.
+  * Random class
+  * Random\NumberGenrator abstract class
+  * Random\NumberGenerator\XorShift128Plus class
+  * Random\NumberGenerator\MT19937 class
+  * Random\NumberGenerator\Secure class
-Also, the static method getNonBiasedMax() allows the user to get the non-biased RNG range.
+The Random class is a utility class that provides functionality using random numbers. It provides the following methods, but does not provide an alternative to array_rand because it is too complex.
-This allows us to rewrite the first example as follows:
+  * getInt()
+  * getBytes()
+  * shuffleArray()
+  * shuffleString()
-<code php>
+The Random class accepts an instance that inherits from Random\NumberGenerator as a constructor argument.
-// example 1
-echo foo(1234, function (): void {}) . PHP_EOL; // Result: 1480009472
-echo foo(1234, function (): void { mt_rand(); }) . PHP_EOL; // Result: 1480009472
-function foo(int $seed, callable $bar): int {
+This class is final and cannot be cloned, but it can be serialized.
-    $random = new Random(RANDOM_MT19937, $seed);
+This is to prevent $rng from being copied by reference to a property and causing unintended behavior.
-    $max = Random::getNonBiasedMax(RANDOM_MT19937);
-    $result = $random->getInt(0, $max);
-    $bar();
-    $result += $random->getInt(0, $max);
-    return $result;
-}
-// example 2
+The serializability depends on the serializability of the contained $rng.
-$random = new Random(RANDOM_MT19937, 1234);
-$max = Random::getNonBiasedMax(RANDOM_MT19937);
-echo $random->getInt(0, $max) . PHP_EOL; // Result: 411284887
-$random = new Random(RANDOM_MT19937, 1234);
+<code php>
-$max = Random::getNonBiasedMax(RANDOM_MT19937);
+final class Random
-str_shuffle('foobar');
+{
-echo $random->getInt(0, $max) . PHP_EOL; // Result: 411284887
+    private Random\NumberGenerator $randomNumberGenerator;
+    public function __construct(?Random\NumberGenerator $randomNumberGenerator = null) {}
+    public function getNumberGenerator(): Random\NumberGenerator {}
+    public function getInt(int $min, int $max): int {}
+    public function getBytes(int $length): string {}
+    public function shuffleArray(array $array): array {}
+    public function shuffleString(string $string): string {}
+    public function __serialize(): array {}
+    public function __unserialize(array $data): void {}
+}
 </code>
-Similarly, several C APIs have been added to the PHP core. This can be used to add non-standard PRNGs.
+The Random\NumberGenerator abstract class has a single abstract method called generate().
-<code c>
+<code php>
-// Note: The detailed implementation is tentative.
+namespace Random;
-typedef struct _php_random_class_algo {
-    int64_t max;
-    int64_t (*next)(void *state);
-    void (*seed)(void *state, const zend_long *seed); // allows NULL.
-    int (*serialize)(void *state, zval *data); // allows NULL.
-    int (*unserialize)(void *state, zval *data); // allows NULL.
-    void *state;
-} php_random_class_algo;
-int php_random_class_algo_register(const char *ident, const php_random_class_algo *algo);
+abstract class NumberGenerator
-void php_random_class_algo_unregister(const char *ident);
+{
+        abstract public function generate(): int {}
+}
 </code>
-In php_random_class_algo, the implementation of serialize / unserialize is optional. If the RNG you implement does not support it, you can specify NULL as a member of the structure, In that case, an exception will be thrown during serialization.
+By defining a class that extends Random\NumberGenerator, the user can use their own random number generator. With the introduction of JIT in PHP 8.0, this can generate random numbers at a realistic speed.
-Also, for RNGs that do not (or cannot) use seed values, the function pointer for seed is optional. If this is passed to a null RNG, an exception will be thrown if a seed value is passed.
-This class also supports the RNG implementation of userland. This is useful for tests that want to fix the expected calculation cost.
 <code php>
-class FixedNumberForTest extends Random
+class UserDefinedRNG extends Random\NumberGenerator
 {
     protected int $current = 0;
-    public function __construct()
+    public function generate(): int
     {
-        parent::__construct(RANDOM_USER, null);
+        return ++$this->current;
     }
+}
-    protected function next(): int
+function foobar(Random\NumberGenerator $numberGenerator): void {
-    {
+    for ($i = 0; $i < 9; $i++) {
-        return ++$this->current;
+        echo $numberGenerator->generate();
     }
 }
+foobar(new UserDefinedRNG()); // Results: 123456789
 </code>
-===== Backward Incompatible Changes =====
+It is also useful when you want to use a random number sequence with a fixed result, such as in testing.
-The class name Random is reserved and will not be available in userland.
-===== Proposed PHP Version(s) =====
+The Random class creates and uses an instance of the default random number generator, Random\NumberGenerator\XorShift128Plus, if the constructor argument is omitted.
-.1
-===== RFC Impact =====
+XorShift128Plus is an efficient, high-quality algorithm used in modern browsers and other applications. This algorithm is capable of generating a wider range of random numbers in a 64-bit environment. In a 32-bit environment, the range beyond zend_long will simply be truncated. This indicates incompatibility between environments, but is acceptable for real-world use.
-==== To SAPIs ====
-none
-==== To Existing Extensions ====
+The Random\NumberGenerator\MT19937 class, which implements the MT19937 Mersenne twister, is also provided for backward compatibility or when a higher period is required. However, a 1-bit right shift is required to obtain exactly the same result as mt_rand(), as shown below. This is due to historical reasons.
-none
-==== To Opcache ====
+<code php>
-none
+$seed = 1234;
-==== New Constants ====
+$mt = new Random\NumberGenerator\MT19937($seed);
-  * RANDOM_XORSHIFT128PLUS
+mt_srand($seed);
-  * RANDOM_MT19937
+var_dump(mt_rand() === ($mt->generate() >> 1)); // true
-  * RANDOM_SECURE
+</code>
-  * RANDOM_USER
-==== php.ini Defaults ====
+The following NumberGenerator class supports serialization. Secure is not serializable because it uses random_bytes internally and has no state.
-none
-===== Open Issues =====
+  * Random\NumberGenerator\XorShift128Plus
+  * Random\NumberGenerator\MT19937
+  * Random\NumberGenerator extends user-defined classes.
-=== When $seed is null, what is used for the seed value? ===
+Also, a new internal API will be implemented.
-Depends on the implementation of algo, but basically it is using internal php_random_int().
-It is similar to mt_srand() from PHP 8.1.
-- https://github.com/php/php-src/commit/53ee3f7f897f7ee33a4c45210014648043386e13
+  * php_random_ng_next()
+  * php_random_ng_range()
+  * php_random_ng_array_data_shuffle()
+  * php_random_ng_string_shuffle()
-=== Why cancelled RNG Extension? ===
+A Stub showing these implementations can be found on the Pull-Request. It's probably easier to understand if you look at it.
-As a result of discussions during the draft, the functions became a single class and no longer need to be separated.
-The functionality for random numbers is now included in ext/standard and will conform to this. (e.g. rand.c random.c)
-=== Why not take an object oriented approach? ===
+  * [[https://github.com/php/php-src/blob/7a4ef6ccfbf4a2cd48a4f261f2911ebb7b057d46/ext/random/random.stub.php|random.stub.php]]
-This is because it is overly complex and difficult to use, See my previous proposal and the discussion in the internals ML for more details.
-  * https://wiki.php.net/rfc/object_scope_prng
+===== Future Scope =====
-  * https://externals.io/message/114378
-  * https://externals.io/message/112819
-=== Why XorShift128+ as the default algorithm? ===
+This proposal is just a first step to improve the situation of PHP's random number implementation.
-This algorithm is capable of generating 64-bit random numbers, is used by major browsers, and is well validated. On the other hand, MT19937, currently used by PHP, can only generate 32-bit random numbers.
-=== Why keep the MT19937 implementation?　===
+If this proposal is approved, I will then propose the following changes
-This is for compatibility. It facilitates quick and easy migration.
-=== What algorithm does RANDOM_SECURE use exactly? ===
+  * Replace the state of the existing implementation with php_random_ng.
-It uses php_random_bytes() internally. This API is guaranteed to be a CSPRNG under any circumstances.
+  * Replace random_bytes() with random_bytes() for random numbers used in shuffle(), str_shuffle(), and array_rand().
+  * Deprecate srand() and mt_srand() (step by step)
-=== Why support CSPRNG? Isn't random_int() good enough? ===
+===== Backward Incompatible Changes =====
-The goal is to be able to migrate all RNG provided functions to this class in the future.
-In other words, to be able to write code without using any of the following functions:
-  * srand()
+The code that includes the following header file needs to be changed to ext/random/random.h
-  * rand()
-  * mt_srand()
-  * mt_rand()
-  * shuffle()
-  * str_shuffle()
-  * array_rand()
-  * random_int()
-  * random_bytes()
-In order to use these functions properly, you need to understand PHP core. For many users, this can be difficult.
+  * ext/standard/lcg.h
+  * ext/standard/rand.h
+  * ext/standard/mt_rand.h
+  * ext/standard/random.h
-=== Why isn't there a drop-in replacement API? ===
+The following class names have been reserved and will no longer be available
-There is no API that can simply replace the following functions:
-  * shuffle()
+  * "Random"
-  * array_rand()
+  * "Random\NumberGenerator"
+  * "Random\NumberGenerator\XorShift128Plus"
+  * "Random\NumberGenerator\MT19937"
+  * "Random\NumberGenerator\Secure"
-The approach of these functions is not compatible with recent implementations.
+===== Proposed PHP Version(s) =====
-shuffle() uses pass-by-reference, and array_rand() is too complex.
+.2
-=== Why stop deprecation for some functions? ===
+===== RFC Impact =====
-The following functions have been removed from deprecation:
+==== To SAPIs ====
+none
-  * srand()
+==== To Existing Extensions ====
-  * rand()
+none
-  * mt_srand()
-  * mt_rand()
-This is because it is still too early and inappropriate include it in one RFC.
+==== To Opcache ====
+none
-=== What will be the concrete C implementation? ===
+==== New Constants ====
-Please wait. If the discussion in ML is good, I' ll start the implementation.
+none
+==== php.ini Defaults ====
+none
+===== Open Issues =====
+none
 ===== Vote =====
@@ Line 247: / Line 239: @@
 ===== Patches and Tests =====
-TBD
+  * https://github.com/php/php-src/pull/7453

Differences

Page Tools