4
\$\begingroup\$

I require a PRNG which:

  1. Has repeatable results from a given state.
  2. Is both seeded from and has a state containing a sufficiently large amount of data (somewhere in the region of 700 bits or more) to cover every possible permutation of a fairly large Fisher-Yates shuffle.
  3. Can be run on .NET.

A few generators exist which satisfy the first two conditions, but finding one that also satisfies the third has proven more difficult, so I decided to port one myself. I chose to adapt xoroshiro1024**[Public Domain] and have (as far as I can tell) successfully converted the original C code (or at least as much of it as is required) to C#.

using System;
using System.Linq;
using System.Numerics;
using System.Security.Cryptography;

namespace CoreGamePlugin.Utilities.Random;

public class XoRoShiRo1024StarStar
{
    private byte position;
    private readonly ulong[] state;

    public XoRoShiRo1024StarStar()
    {
        state = new ulong[16];
        byte[] seedBytes;

        do { seedBytes = RandomNumberGenerator.GetBytes(129); }
        while (seedBytes[..^1].All(x => x == byte.MinValue));

        for (byte i = 0; i < 16; i++)
        {
            state[i] = BitConverter.ToUInt64(seedBytes, i * 8);
        }
        position = (byte)(seedBytes[128] % 16);
    }

    public ulong NextULong()
    {
        byte previousPosition = position;
        ulong activeSection = state[position = (byte)(++position % 16)];
        ulong newSection = state[previousPosition];

        newSection ^= activeSection;
        state[previousPosition] = BitOperations.RotateLeft(activeSection, 25) ^ newSection ^ (newSection << 27);
        state[position] = BitOperations.RotateLeft(newSection, 36);

        return BitOperations.RotateLeft(activeSection * 5, 7) * 9;
    }
    
    // Further methods utilising the result of NextULong()...
}

The problem lies in the fact that I do not know C, and cannot claim to fully understand the nuances of C or what every keyword actually did in the original code. As such, while my version of the code runs, appears to pass the tests I have performed for distribution uniformity, and mirrors the behaviour of the original for a handful of seeds over a short period (but longer than two full cycles of the state's position, i.e. more than 32 calls to NextULong()), I am still concerned there may exist an edge case for which this may not hold true.

Additionally, I am unsure if my method for seeding the generator is appropriate, so any advice with regards to that would be very helpful. In particular, is there a risk of the RandomNumberGenerator "running out of entropy" and slowing/breaking the application if too many instances of the generator are created in quick succession, and how might this be addressed? In case it is relevant: this code will be running in various different environments/OS, including both locally on users' machines and on at least one server, with the latter being far more likely to require many instances of the generator at once.

Edit: Having thought more thoroughly about the cyclical nature of this PRNG's state while responding to a comment, I have come to the realisation—perhaps rather embarrassingly late—that seeding the position is entirely superfluous (as two instances of this generator would produce the same output if the second had both its state rotated by some number of places and the position accordingly increased or decreased by the same value [assuming correct adherance to the modulo operation] compared to the first), and so in my code it is now initialised outside of the constructor as so: private byte position = byte.MinValue;, along with the relevant modifications this would imply for the constructor itself. However, as per the rules of this site, I have left the code above as it was at the time of first answer.

\$\endgroup\$
12
  • \$\begingroup\$ "unable to verify if it actually mirrors the behaviour of the original for a given seed" I don't understand this remark. Surely we could print out the relevant variables of both implementations for each proposed seed? \$\endgroup\$
    – J_H
    Oct 17, 2023 at 5:06
  • 1
    \$\begingroup\$ I could try running the code to confirm the output, but in any case it would have been easier to visually inspect the code for potential differences if you hadn't renamed/moved a bunch of stuff unnecessarily. \$\endgroup\$
    – harold
    Oct 17, 2023 at 8:19
  • 1
    \$\begingroup\$ I don't mean using BitOperations.RotateLeft (or ulong instead of uint64_t), that is an obvious and necessary part of the translation. Some of the other changes make it harder to tell whether this code is a correct port or not, since there is no nice 1-to-1 correspondence between the original code and the port. \$\endgroup\$
    – harold
    Oct 17, 2023 at 12:26
  • 2
    \$\begingroup\$ @CommandMaster There is a trend on certain social media sites of people attacking projects similar to mine for perceived issues (whether spurious or not) with the PRNG used. It is simply better (from a business perspective) to have a PRNG for which some of these claims (specifically here the "not every deal is possible" claim) can have no theoretical validity, than to have to wade into arguments regarding the practical validity. \$\endgroup\$
    – Pikanchion
    Oct 18, 2023 at 10:24
  • 1
    \$\begingroup\$ @J_H That source is not by the original author, and I have no guarantee of its accuracy. Regardless, it uses a completely different method of seeding the generator, and I have not implemented SplitMix64 in my codebase as I am seeding the entire state from a cryptographic source rather than extrapolating from a given 64 bits (which would violate my second requirement). Also, the ten values given in this test is not even one full cycle of the state, which seems insufficient for verification purposes. I do have unit tests implemented for the values I myself have generated from the original C code \$\endgroup\$
    – Pikanchion
    Oct 18, 2023 at 23:45

1 Answer 1

1
\$\begingroup\$

I'm not commenting on the correctness of your port since I don't have the time to dig into the detail, so just some remarks on the code as presented:

Array handling

  1. The size of the state is represented as hard-coded magic numbers in several places. If it ever becomes useful to increase the size of the state then you need to find all the places that depend on this which has a good chance of forgetting one or 2 places. Plus introducing a named constant makes it clearer what it is used for.
  2. You seem to be aware of LINQ, however you still use a lot of direct array indexing which makes the code susceptible to off-by-one errors. For example your state init could be:
    state = Enumerable.Range(0, StateSize)
                      .Select(i => BitConverter.ToUInt64(seedBytes, i * 8))
                      .ToArray()
    

Design

It might be beneficial to derive your class from https://learn.microsoft.com/en-us/dotnet/api/system.security.cryptography.randomnumbergenerator?view=net-7.0 so that the consumers can easily swap different RNG implementations.

Seeding

I don't understand the rational behind this:

do { seedBytes = RandomNumberGenerator.GetBytes(129); }
while (seedBytes[..^1].All(x => x == byte.MinValue));

This obtains 129 random bytes values until at least one of them (except the last one) is not 0. Also - why exempt the last element from checking and did you mean to use Any instead of All (i.e. did you mean to write - generate a sequence of random bytes of which none are 0)?

As it stands - why would RandomNumberGenerator produce a sequence of all 0 bytes? I mean in theory it's possible but assuming that the class produces an equal distribution of values the chance of getting a 0 value is 1/256 and the chance of doing it 128 times in a row is (1/256)^128 = (1/2^8)^128 = 1/2^1024 which is ridiculously small. For comparison - the number of atoms in the universe is estimated to be ~10^80 which is somewhere around 2^267. So the chance of it is about the same as selecting a random atom in the universe, do it 4 times and hit 4 times the same atom.

It would probably be more useful to do something like:

    private static const int StateSize = 16;

    public XoRoShiRo1024StarStar()
    {
        var seedBytes = new byte[StateSize * 8 + 1];
        RandomNumberGenerator.GetNonZeroBytes(seedBytes);

        if (seedBytes.Any(b => b == 0))
            throw new Exception("RandomNumberGenerator is broken!");

        state = Enumerable.Range(0, StateSize)
                          .Select(i => BitConverter.ToUInt64(seedBytes, i * 8))
                          .ToArray()
        position = (byte)(seedBytes.Last() % StateSize);
    }

(This assumes that you want all your seed bytes to be guaranteed to be non-zero).

\$\endgroup\$
4
  • 1
    \$\begingroup\$ The choice of All is intentional: xoroshiro1024** requires that the state "must be seeded so that it is not everywhere zero", the position can safely be of any value (and the generator would fail to ever output a non-zero result if this were the only non-zero value). Though as you say this occuring is presumably infinitesimal. The choice of RandomNumberGenerator over RNGCryptoServiceProvider was simply as the latter is obsolete, with the former given explicitly as its replacement. I have no preconception of either's quality. \$\endgroup\$
    – Pikanchion
    Oct 18, 2023 at 22:48
  • \$\begingroup\$ @Pikanchion Ok, then the original logic is incorrect - All checks whether all elements fulfill the condition. So if you say do { ... } while (seedBytes.All()) this means "execute the loop as long as all seedBytes are 0". So as soon as one isn't then the condition fill be false. In other words - as originally coded it is sufficient for just one seed byte to b non-zero. You needed to use Any() instead. \$\endgroup\$
    – ChrisWue
    Oct 19, 2023 at 0:53
  • \$\begingroup\$ @Pikanchion Thanks for pointing out the RandomNumberGenerator class - didn't realize it's a dotnet standard thing now. Most of the answer still holds. \$\endgroup\$
    – ChrisWue
    Oct 19, 2023 at 0:56
  • 1
    \$\begingroup\$ "In other words - as originally coded it is sufficient for just one seed byte to be non-zero." Yes, this is the intended behaviour; the PRNG requires only one bit of state to be non-zero in order to be in a valid configuration. I think the confusion may be from misinterpreting the phrase "not everywhere zero" to be equivalent with "not zero everywhere"? This distinction is made clear elsewhere by the author's suggestion of SplitMix64 if only 64 bits are available, as he states that SM64—being equidistant—could generate no more than one 64-bit section of fully zero state. \$\endgroup\$
    – Pikanchion
    Oct 19, 2023 at 1:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.