Hi On 2/16/22 12:04, Go Kudo wrote:
Thanks for the good idea. I changed the NumberGenerator to Engine and changed generate() to return a string as suggested.
Thanks, I've already seen the updated PR and played around with it. This feels much better now.
As a test I implemented xoshiro128++ in pure userland (it being a 32 Bit RNG avoids the signedness issues in PHP userland) and compared it against the reference implementation in C.
Find my implementations attached. Both versions give the same results (little endian encoding):
$ gcc xoshiro128pp.c ; ./a.out
fa3c872c
$ sapi/cli/php test_rng.php
string(8) "fa3c872c"
The main changes since last time are as follows: - The userland implementation can now specify the width of the random number sequence that can be generated - Random\Engine::nextByteSize() has been added
Is the nextByteSize() method actually required? PHP strings already know their own length.
- Random\Engine::generate() now returns a string
I've looked into your C implementation and it appears it still is affected by endianness issues. You can't simply memcpy the raw uintXX_t bytes into the char array. I believe the following should do the trick to for a consistent little endian encoding:
bytes[0] = (generated >> 0) & 0xff; bytes[1] = (generated >> 8) & 0xff; bytes[2] = (generated >> 16) & 0xff; bytes[3] = (generated >> 24) & 0xff;The choice of endianness is arbitrary, but it needs to be consistent for every platform.
Likewise when converting back to a number from bytes:number = (bytes[0] << 0) | (bytes[1] << 8) (bytes[2] << 16) | (bytes[3] << 24);
I believe the same issue exists when initializing the XorShift with a string.
I have not yet come to a final conclusion on whether XorShift128Plus should be switched to another RNG. For example, what about implementing XorShift128Plus, but adding Xoshiro256** as well?
That would be fine for me as well. But it might make it harder for the end user to choose an appropriate RNG.
Best regards Tim Düsterhus
<<attachment: test_rng.php>>
/* Written in 2019 by David Blackman and Sebastiano Vigna (vi...@acm.org) To the extent possible under law, the author has dedicated all copyright and related and neighboring rights to this software to the public domain worldwide. This software is distributed without any warranty. See <http://creativecommons.org/publicdomain/zero/1.0/>. */ #include <stdint.h> #include <stdio.h> /* This is xoshiro128++ 1.0, one of our 32-bit all-purpose, rock-solid generators. It has excellent speed, a state size (128 bits) that is large enough for mild parallelism, and it passes all tests we are aware of. For generating just single-precision (i.e., 32-bit) floating-point numbers, xoshiro128+ is even faster. The state must be seeded so that it is not everywhere zero. */ static inline uint32_t rotl(const uint32_t x, int k) { return (x << k) | (x >> (32 - k)); } static uint32_t s[4]; uint32_t next(void) { const uint32_t result = rotl(s[0] + s[3], 7) + s[0]; const uint32_t t = s[1] << 9; s[2] ^= s[0]; s[3] ^= s[1]; s[1] ^= s[2]; s[0] ^= s[3]; s[2] ^= t; s[3] = rotl(s[3], 11); return result; } /* This is the jump function for the generator. It is equivalent to 2^64 calls to next(); it can be used to generate 2^64 non-overlapping subsequences for parallel computations. */ void jump(void) { static const uint32_t JUMP[] = { 0x8764000b, 0xf542d2d3, 0x6fa035c3, 0x77f2db5b }; uint32_t s0 = 0; uint32_t s1 = 0; uint32_t s2 = 0; uint32_t s3 = 0; for(int i = 0; i < sizeof JUMP / sizeof *JUMP; i++) for(int b = 0; b < 32; b++) { if (JUMP[i] & UINT32_C(1) << b) { s0 ^= s[0]; s1 ^= s[1]; s2 ^= s[2]; s3 ^= s[3]; } next(); } s[0] = s0; s[1] = s1; s[2] = s2; s[3] = s3; } /* This is the long-jump function for the generator. It is equivalent to 2^96 calls to next(); it can be used to generate 2^32 starting points, from each of which jump() will generate 2^32 non-overlapping subsequences for parallel distributed computations. */ void long_jump(void) { static const uint32_t LONG_JUMP[] = { 0xb523952e, 0x0b6f099f, 0xccf5a0ef, 0x1c580662 }; uint32_t s0 = 0; uint32_t s1 = 0; uint32_t s2 = 0; uint32_t s3 = 0; for(int i = 0; i < sizeof LONG_JUMP / sizeof *LONG_JUMP; i++) for(int b = 0; b < 32; b++) { if (LONG_JUMP[i] & UINT32_C(1) << b) { s0 ^= s[0]; s1 ^= s[1]; s2 ^= s[2]; s3 ^= s[3]; } next(); } s[0] = s0; s[1] = s1; s[2] = s2; s[3] = s3; } int main(void) { s[0] = 1; s[1] = 2; s[2] = 3; s[3] = 4; for (size_t i = 0; i < 102400; i++) next(); int32_t result = next(); printf("%x%x%x%x\n", ((result >> 0) & 0xff), ((result >> 8) & 0xff), ((result >> 16) & 0xff), ((result >> 24) & 0xff)); }
-- PHP Internals - PHP Runtime Development Mailing List To unsubscribe, visit: https://www.php.net/unsub.php
