rfc:rng_extension

Differences

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

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
rfc:rng_extension [2021/05/25 15:40]
zeriyoshi str_shuffle has drop-in replacement API
rfc:rng_extension [2021/09/03 14:28] (current)
zeriyoshi
Line 1: Line 1:
-====== PHP RFC: Add Random class ====== +====== PHP RFC: Random Extension 3.0 ====== 
-  * Version: 0.+  * Version: 3.0 
-  * Date: 2021-05-18+  * Date: 2021-09-02
   * Author: Go Kudo <zeriyoshi@gmail.com>   * 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   * First Published at: http://wiki.php.net/rfc/object_scope_prng
  
 ===== Introduction ===== ===== Introduction =====
-PHP is currently having problems with RNG reproducibility. 
  
-PHP'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'random number implementation suffers from several problems.
  
-Butthese 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> <code php>
Line 26: Line 28:
 </code> </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. 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 ===== ===== Proposal =====
-Implements Random class. 
  
-This class implement to ext/standardalways bundled PHP core.+Clean up the implementationseparate 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 timethe 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
  
-Alsothe 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 methodsbut 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() 
 + 
 +This class can be used in the following way.
  
 <code php> <code php>
-// example 1 +// functions 
-echo foo(1234, function (): void {}) . PHP_EOL; // Result: 1480009472 +mt_srand(1234); 
-echo foo(1234function (): void { mt_rand(); }. PHP_EOL; // Result: 1480009472+mt_rand(); // generate random number 
 +mt_rand(110); // generate random number in range 
 +str_shuffle("foobar"); // shuffle string 
 +$arr = range(1, 10); 
 +shuffle($arr); // shuffle array items (pass by reference)
  
-function foo(int $seed, callable $bar): int { +// object 
-    $random = new Random(RANDOM_MT19937, $seed); +$mt = new Random\NumberGenerator\MT19937(1234); 
-    $max = Random::getNonBiasedMax(RANDOM_MT19937); +$mt->generate(); // generate random number  
-    $result = $random->getInt(0$max); +$random new Random($mt); 
-    $bar(); +$random->getInt(110); // generate random number in range 
-    $result += $random->getInt(0$max); +$random->shuffleString("foobar"); // shuffle string 
-    return $result; +$random->shuffleArray(range(110)); // shuffle array items (pass by value) 
-}+</code>
  
-// example 2 +The Random class accepts an instance that inherits from Random\NumberGenerator as a constructor argument.
-$random = new Random(RANDOM_MT19937, 1234); +
-$max = Random::getNonBiasedMax(RANDOM_MT19937); +
-echo $random->getInt(0, $max) PHP_EOL; // Result: 411284887+
  
-$random = new Random(RANDOM_MT199371234); +This class is final and cannot be clonedbut it can be serialized. 
-$max = Random::getNonBiasedMax(RANDOM_MT19937); +This is to prevent $rng from being copied by reference to a property and causing unintended behavior.
-str_shuffle('foobar'); +
-echo $random->getInt(0, $max) PHP_EOL; // Result: 411284887 +
-</code>+
  
-Similarly, several C APIs have been added to the PHP core. This can be used to add non-standard PRNGs.+The serializability depends on the serializability of the contained $rng.
  
-<code c+<code php
-// Note: The detailed implementation is tentative. +final class Random 
-typedef struct _php_random_class_algo +
-    int64_t max; +    private Random\NumberGenerator $randomNumberGenerator;
-    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 *identconst php_random_class_algo *algo); +    public function __construct(?Random\NumberGenerator $randomNumberGenerator = null) {} 
-void php_random_class_algo_unregister(const char *ident);+    public function getNumberGenerator(): Random\NumberGenerator {} 
 +    public function getInt(int $minint $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> </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 member of the structure, In that case, an exception will be thrown during serialization.+The Random\NumberGenerator abstract class has single abstract method called generate()
  
-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.+<code php> 
 +namespace Random;
  
-This class also supports the RNG implementation of userlandThis is useful for tests that want to fix the expected calculation cost.+abstract class NumberGenerator 
 +
 +        abstract public function generate(): int {} 
 +
 +</code> 
 + 
 +By defining a class that extends Random\NumberGenerator, the user can use their own random number generatorWith the introduction of JIT in PHP 8.0, this can generate random numbers at a realistic speed.
  
 <code php> <code php>
-class FixedNumberForTest extends Random+class UserDefinedRNG extends Random\NumberGenerator
 { {
     protected int $current = 0;     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> </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.
-8.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 nullwhat is used for the seed value? === +Alsoa 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-RequestIt'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'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 CSPRNG under any circumstances.+  * Changes random source to php_random_int() a 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 coreFor many users, this can be difficult.+  * ext/standard/lcg.
 +  * ext/standard/rand.
 +  * 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.+8.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 ===== ===== Vote =====
Line 247: Line 259:
  
 ===== Patches and Tests ===== ===== Patches and Tests =====
-TBD+  * https://github.com/php/php-src/pull/7453
rfc/rng_extension.1621957202.txt.gz · Last modified: 2021/05/25 15:40 by zeriyoshi