|
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
using System.Diagnostics;
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
namespace System
{
public partial class Random
{
/// <summary>
/// Provides an implementation of the xoshiro256** algorithm. This implementation is used
/// on 64-bit when no seed is specified and an instance of the base Random class is constructed.
/// As such, we are free to implement however we see fit, without back compat concerns around
/// the sequence of numbers generated or what methods call what other methods.
/// </summary>
internal sealed class XoshiroImpl : ImplBase
{
// NextUInt64 is based on the algorithm from http://prng.di.unimi.it/xoshiro256starstar.c:
//
// Written in 2018 by David Blackman and Sebastiano Vigna (vigna@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/>.
private ulong _s0, _s1, _s2, _s3;
public unsafe XoshiroImpl()
{
ulong* ptr = stackalloc ulong[4];
do
{
Interop.GetRandomBytes((byte*)ptr, 4 * sizeof(ulong));
_s0 = ptr[0];
_s1 = ptr[1];
_s2 = ptr[2];
_s3 = ptr[3];
}
while ((_s0 | _s1 | _s2 | _s3) == 0); // at least one value must be non-zero
}
/// <summary>Produces a value in the range [0, uint.MaxValue].</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)] // small-ish hot path used by very few call sites
internal uint NextUInt32() => (uint)(NextUInt64() >> 32);
/// <summary>Produces a value in the range [0, ulong.MaxValue].</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)] // small-ish hot path used by a handful of "next" methods
internal ulong NextUInt64()
{
ulong s0 = _s0, s1 = _s1, s2 = _s2, s3 = _s3;
ulong result = BitOperations.RotateLeft(s1 * 5, 7) * 9;
ulong t = s1 << 17;
s2 ^= s0;
s3 ^= s1;
s1 ^= s2;
s0 ^= s3;
s2 ^= t;
s3 = BitOperations.RotateLeft(s3, 45);
_s0 = s0;
_s1 = s1;
_s2 = s2;
_s3 = s3;
return result;
}
public override int Next()
{
while (true)
{
// Get top 31 bits to get a value in the range [0, int.MaxValue], but try again
// if the value is actually int.MaxValue, as the method is defined to return a value
// in the range [0, int.MaxValue).
ulong result = NextUInt64() >> 33;
if (result != int.MaxValue)
{
return (int)result;
}
}
}
public override int Next(int maxValue)
{
Debug.Assert(maxValue >= 0);
return (int)NextUInt32((uint)maxValue, this);
}
public override int Next(int minValue, int maxValue)
{
Debug.Assert(minValue <= maxValue);
return (int)NextUInt32((uint)(maxValue - minValue), this) + minValue;
}
public override long NextInt64()
{
while (true)
{
// Get top 63 bits to get a value in the range [0, long.MaxValue], but try again
// if the value is actually long.MaxValue, as the method is defined to return a value
// in the range [0, long.MaxValue).
ulong result = NextUInt64() >> 1;
if (result != long.MaxValue)
{
return (long)result;
}
}
}
public override long NextInt64(long maxValue)
{
Debug.Assert(maxValue >= 0);
return (long)NextUInt64((ulong)maxValue, this);
}
public override long NextInt64(long minValue, long maxValue)
{
Debug.Assert(minValue <= maxValue);
return (long)NextUInt64((ulong)(maxValue - minValue), this) + minValue;
}
public override void NextBytes(byte[] buffer) => NextBytes((Span<byte>)buffer);
public override unsafe void NextBytes(Span<byte> buffer)
{
ulong s0 = _s0, s1 = _s1, s2 = _s2, s3 = _s3;
while (buffer.Length >= sizeof(ulong))
{
Unsafe.WriteUnaligned(
ref MemoryMarshal.GetReference(buffer),
BitOperations.RotateLeft(s1 * 5, 7) * 9);
// Update PRNG state.
ulong t = s1 << 17;
s2 ^= s0;
s3 ^= s1;
s1 ^= s2;
s0 ^= s3;
s2 ^= t;
s3 = BitOperations.RotateLeft(s3, 45);
buffer = buffer.Slice(sizeof(ulong));
}
if (!buffer.IsEmpty)
{
ulong next = BitOperations.RotateLeft(s1 * 5, 7) * 9;
byte* remainingBytes = (byte*)&next;
Debug.Assert(buffer.Length < sizeof(ulong));
for (int i = 0; i < buffer.Length; i++)
{
buffer[i] = remainingBytes[i];
}
// Update PRNG state.
ulong t = s1 << 17;
s2 ^= s0;
s3 ^= s1;
s1 ^= s2;
s0 ^= s3;
s2 ^= t;
s3 = BitOperations.RotateLeft(s3, 45);
}
_s0 = s0;
_s1 = s1;
_s2 = s2;
_s3 = s3;
}
public override double NextDouble() =>
// As described in http://prng.di.unimi.it/:
// "A standard double (64-bit) floating-point number in IEEE floating point format has 52 bits of significand,
// plus an implicit bit at the left of the significand. Thus, the representation can actually store numbers with
// 53 significant binary digits. Because of this fact, in C99 a 64-bit unsigned integer x should be converted to
// a 64-bit double using the expression
// (x >> 11) * 0x1.0p-53"
(NextUInt64() >> 11) * (1.0 / (1ul << 53));
public override float NextSingle() =>
// Same as above, but with 24 bits instead of 53.
(NextUInt64() >> 40) * (1.0f / (1u << 24));
public override double Sample()
{
Debug.Fail("Not used or called for this implementation.");
throw new NotSupportedException();
}
}
}
}
|