Subject: Re: [PATCH 2/2] prandom/random32: switch to Xoshiro256++

From: Simon Horman <[email-masked]>
Date: Mon, 24 Mar 2025 17:32:19 +0000

On Sat, Mar 22, 2025 at 07:24:57PM +0100, Markus Theil wrote:
> On 2/17/25 12:18, Simon Horman wrote:
> > On Fri, Feb 14, 2025 at 09:18:40AM +0100, Markus Theil wrote:
> > > The current Linux PRNG is based on LFSR113, which means:
> > > - needs some warmup rounds to yield better statistical properties
> > > - seeds/initial states must be of certain structure
> > > - does not pass L’Ecuyer's BigCrush in TestU01
> > > 
> > > While of course, there is no clear "best" PRNG, replace with
> > > Xoshiro256++, which seams to be a sensible replacement, from
> > > todays point of view:
> > > - only needs one bit set to 1 in the seed, needs no warmup, when
> > >    seeded with splitmix64.
> > > - Also has statistical evaluation, like LFSR113.
> > > - Passes BigCrush in TestU01.
> > > 
> > > The code got smaller, because some edge cases are ruled out now.
> > > I kept the test vectors and adapted them to this RNG.
> > > 
> > > Signed-off-by: Markus Theil <[email-masked]>
> > ...
> > 
> > > diff --git a/lib/random32.c b/lib/random32.c
> > ...
> > 
> > > +/**
> > > + * prandom_seed_state - set seed for prandom_u32_state().
> > > + * @state: pointer to state structure to receive the seed.
> > > + * @seed: arbitrary 64-bit value to use as a seed.
> > > + *
> > > + * splitmix64 init as suggested for xoshiro256++
> > > + * See: https://prng.di.unimi.it/splitmix64.c
> > > + */
> > > +void prandom_seed_state(struct rnd_state *state, u64 seed)
> > >   {
> > > -	/* Calling RNG ten times to satisfy recurrence condition */
> > > -	prandom_u32_state(state);
> > > -	prandom_u32_state(state);
> > > -	prandom_u32_state(state);
> > > -	prandom_u32_state(state);
> > > -	prandom_u32_state(state);
> > > -	prandom_u32_state(state);
> > > -	prandom_u32_state(state);
> > > -	prandom_u32_state(state);
> > > -	prandom_u32_state(state);
> > > -	prandom_u32_state(state);
> > > +	int i;
> > > +
> > > +	for (i = 0; i < ARRAY_SIZE(state->s); ++i) {
> > > +		seed += 0x9e3779b97f4a7c15;
> > > +		u64 z = seed;
> > > +		z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
> > > +		z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
> > > +        state->s[i] = z ^ (z >> 31);
> > nit: The indentation seems off here.
> Shall I resend for this line?

The maintainer may think otherwise.
But in my opinion that would be a good idea.

> > > +	}
> > >   }
> > > +EXPORT_SYMBOL(prandom_seed_state);
> > ...