My Little Homegrown Simple Random Generator

Hello fellow programmers,

I am quite new with Rust, but (slowly) progressing...
For my program I need some random (u64) numbers without external dependencies.
(for hashing some chess board data).
If there are any 'random specialists' around: can you say something about the 'randomness'?
And for the code: comments on anything welcome.
(except the bracing. I am physically and mentally unable to read and write asymmetric code).

Best wishes,
Eric

pub struct Rnd
{
    Seed : u32,
}

impl Rnd
{
    const OFFSET : u32 = 0x5414d5f4;

    #[inline]
    pub fn new(seed: u32) -> Self
    {
        Self
        {
            Seed: seed ^ Rnd::OFFSET,
        }
    }

    #[inline]
    pub fn new_randomized() -> Self
    {
        Self
        {
            Seed: Rnd::OFFSET.wrapping_mul(Rnd::generate_time_seed())
        }
    }

    fn generate_time_seed() -> u32 
    {
        use std::time::{SystemTime, UNIX_EPOCH};
        let now = SystemTime::now();
        let since_epoch = now.duration_since(UNIX_EPOCH);
        match since_epoch
        {
            Ok(d) => 
            {
                let ms: u128 = d.as_micros();
                let a = (ms >> 96) as u32;
                let b = ((ms >> 64) & 0xffffffff) as u32;
                let c = ((ms >> 32) & 0xffffffff) as u32;
                let d = ms as u32;                
                a ^ b ^ c ^ d
            }
            _ => 
            {
                Rnd::OFFSET
            }
        }
    }

    #[inline]
    pub fn next_u32(&mut self) -> u32
    {
        let mut random : u32 = self.Seed;
        random ^= random << 13;
        random ^= random >> 17;
        random ^= random << 5;
        self.Seed ^= random;
        random
    }

    #[inline]
    pub fn next_u64(&mut self) -> u64
    {
        let a : u64 = self.next_u32() as u64;
        let b : u64 = self.next_u32() as u64;
        a | (b << 32)
    }

    #[inline]
    pub fn next_i64(&mut self) -> i64
    {
        self.next_u64() as i64
    }

    #[inline]
    pub fn next_i32(&mut self) -> i32
    {
        self.next_u32() as i32
    }

    #[inline]
    pub fn next_u64_range(&mut self, min: u64, max: u64) -> u64 
    {
        if max > min
        {
            let range = max - min;
            min + (self.next_u64() % range)
        }
        else
        {
            min
        }
    }

    #[inline]
    pub fn next_u32_range(&mut self, min: u32, max: u32) -> u32 
    {
        if max > min
        {
            let range = max - min;
            min + (self.next_u32() % range)
        }
        else
        {
            min
        }
    }

    #[inline]
    pub fn next_i64_range(&mut self, min: i64, max: i64) -> i64 
    {
        if max > min
        {
            let range = (max - min) as u64;
            let r = self.next_u64() % range;
            (r as i64) + min
        }
        else
        {
            min
        }
    }

    #[inline]
    pub fn next_i32_range(&mut self, min: i32, max: i32) -> i32 
    {
        if max > min
        {
            let range = (max - min) as u32;
            let r = self.next_u32() % range;
            (r as i32) + min
        }
        else
        {
            min
        }
    }
}

fn main()
{
     let mut rand: Rnd = Rnd::new_randomized();
     for _i in 0..43
     {

        let nr: u64 = rand.next_u64();
        println!("{}", nr);
    }
}
1 Like

Where did you get that random algorithm from? Did you concoct it yourself?

I would lean towards using well known algorithms that have had their properties analysed and tested. For example:
One of the PGC family: PCG
One of the xoroshoro https://prng.di.unimi.it/ They are small, simple and fast. Plenty of example codes for them in C, C++ etc.

4 Likes

I created it myself.
This one (from your link) looks interesting :slight_smile:

#include <stdint.h>

/* This is a fixed-increment version of Java 8's SplittableRandom generator
   See http://dx.doi.org/10.1145/2714064.2660195 and 
   http://docs.oracle.com/javase/8/docs/api/java/util/SplittableRandom.html

   It is a very fast generator passing BigCrush, and it can be useful if
   for some reason you absolutely want 64 bits of state. */

static uint64_t x; /* The state can be seeded with any value. */

uint64_t next() {
	uint64_t z = (x += 0x9e3779b97f4a7c15);
	z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
	z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
	return z ^ (z >> 31);
}

Even if you might be used to other coding styles in other languages, I still strongly recommend you use rustfmt, for a few reasons.

  1. Most other code you'll be using like the standard library and third-party crates are written using rustfmt style. So when debugging and stepping through code, you will come across it. This is an inconsistency that can be avoided.

  2. When collaborating with other rust developers, many will want to use rustfmt, which may hinder collaboration. Even when just reviewing your code in this post, I'll need more mental effort to read and understand your code, because it subverts some expectations I have about rust code.


You say you can't use any external dependencies. Without any justification, it's hard to justify the added complexity to your whole codebase. rand is one of the most downloaded crates and written by the rust team, so the obvious recommendation would be to use that. It is of course a nice problem to implement for educational purposes. But definitely do not use it for anything cryptography-related.


The implementation of generate_time_seed fells a little uneasy to me, because you ignore the possible error case from duration_since. The resulting value may have less randomness than the caller expected, without any indication. You may want to bubble the error up. In any case this should be documented.


For next_u64_range and it's cousins, you should document whether the min and max are inclusive or exclusive. Or, even better, take a impl RangeBounds to make it self-documenting and be more flexible for the caller. As a next step, you can make it generic over RangeBounds<T>.

One thing I don't understand is the else { min } on those methods. To me, it's unclear why it's there and what it's supposed to do. I would consider a kind of "empty" range an invalid value for this purpose, so the methods should either panic or return a result. It would almost always be a bug in the calling code, and it shouldn't silently return a value that could be mistaken for a expected random value in the range.

2 Likes

Thanks.
I understand your comments. I already removed these 'else' statements.
About these 'range' things I am still not sure.
Comments were still not added. Work in progress... But true!
The reason I implemented it is because of the fact that maybe the keys will end up in some database or binary file and I need to be sure of the predictability.

I am not at all against using external crates. And no: I will not use my rnd for protection agains dos attacks etc.

About formatting: I will use formatting when posting something. In my own workspace, however, i will stick to my formatting. I really really tried, and I like symmetry too much.
I even can't use the rust formatter in vscode which is irritating because it messes up everything :slight_smile:
Leave my static arrays, oneliners and match statements alone!

For the rest: I will check out your other remarks. thanks.

1 Like

In Rust "without external dependencies" is not a virtue. The standard library is intentionally small, and Rust programs are expected to use crates.io a lot.

There are many good pseudorandom algorithms available for Rust. This is a very well researched area, and you'll likely find algorithms that are faster and more random than yours.

You've also mentioned hashing. These too have fast and good options, e.g. rustc-hash is an fnv function that is remarkably simple, and works very well. There's smhasher benchmark you can use to test hashing speed and quality.

2 Likes

I finally took a look at your code. I can't say anything about the quality of the pseudo random number sequences that produces but I do have to point out that your ..._range functions contain the classic "modulo bias" problem.

When you do % range on a uniform distribution of random numbers you end up with non-uniform distribution. There will be a bias in favour of a subrange.

You can read about it here: The definitive guide to “Modulo Bias and how to avoid it”! – Kudelski Security Research

Perhaps that bias does not matter much in your application but such things really upset my sense of symmetry :slight_smile:

1 Like

:smile:
thanks!! the randomrange is less important but i will have a look at that!

Take a look at the Mersenne Twister - it exists in both 32 & 64 bit versions. Also - has the advantage that it it is not patented.

I recently had a need similar to yours, so I made a rust version (64 bit). With this version you can generate random numbers at compile time (const) - with the normal rust random functions you have to define a proc macro if you want to do that (e.g. const-random crate).

Mersenne Twister is obsolete. It has needlessly large state that hurts performance, and has defects that can cause bias:

Instead, check out PCG:

5 Likes

Hey eric,

I just found out that rustfmt has configuration options, including the brace style. If you'd like, we can figure out a config that matches your preferred style, so that rustfmt can help you by applying your style automatically. For arrays, there's also a setting https://rust-lang.github.io/rustfmt/?version=v1.6.0&search=#array_width

If you care about randomness, you should use a standard, cryptographically strong, random number generator algorithm. Every other generator has known weaknesses, and there is almost never any real reason to expose yourself to that.

Even if you want to write all the code from scratch, I'd recommend ChaCha 20. It's a very simple algorithm to implement.

I have written a blog post about this:

1 Like

Hey eric,
I just found out that rustfmt has configuration options
For example this array which is very conciously aligned.

I started out a few weeks ago with vscode. And I think without the rustfmt. but not sure! Maybe it uses some other (language?) format settings as well.
I tend to get lost in the ocean of vscode options / json's. nothing worked out so far.
I seem to be not able to change a setting that has an effect.

There are only two settings for my personal needs.
-Brace always on newline except when i put the start and closing brace on one line myself.
-Don't do anything with arrays.

For example:

    [
        (   0,  90 ), (   0,  90 ), (   0,  90 ), (   0,  90 ), 
        (   0,  80 ), (   0,  80 ), (   0,  80 ), (   0,  80 ),  
        (   0,  60 ), (   2,  60 ), (   0,  60 ), (   0,  60 ),  
        (   6,  50 ), (   8,  50 ), (   4,  50 ), (  47,  50 ),  
        (   4,  40 ), (   6,  40 ), (  18,  40 ), (  35,  40 ),  
        (   2,  30 ), (  10,  30 ), (  14,  30 ), (  10,  30 ),  
        (   0,  20 ), (   0,  20 ), ( -10,  20 ), ( -12,  20 ),  
        (   0,   0 ), (   0,   0 ), (   0,   0 ), (   0,   0 ),  
    ]; 

So rustfmt is configured via a rustfmt.toml files that goes next to your Cargo.toml (or parent directories). The VSCode rust extension should by default use rustfmt (or cargo fmt) and thus pick up the config.

In there, you may want to set these options:

max_width = 9999
short_array_element_width_threshold = 9999
use_small_heuristics = "Off"
array_width = 9999

If you can provide me with a code sample that compiles, I'll be happy to test things myself. The code you shared for your RNG doesn't have any arrays.

You can also annotate something with #[rustfmt::skip], which will make rustfmt completely ignore that section.

Ok I will do that. but somehow the rustfmt is not findable in vscode.
I see Editor: Default Formatter rust-analyzer, but don't know if that is rustfmt!
I already created this rustfmt.toml. No effect.

I just created a rustfmt.toml file in my projects directory. next to its Cargo.toml file, with the content shown above and VSCode then formatted it as I would expect. As far as I know only my installing the rust-analyser extension to VSCode got this working. I never spend any time messing with editor configurations.

1 Like

Aha now i see: brace_style is ignored.
brace_style = "AlwaysNextLine"
Your array works. So it is working.

It's a modification of Marsaglia's xorshift32 algorithm.

I think I got this 'shift' idea from some rust core hashing operation yes.
By the way I changed it in my lib to some faster code directly producing a u64.
Using SplitMix64 as suggested above in a link.
Good enough for my (chess) hashing up until now.

This is not uniform. For instance, if min=0 and max=3000000000, the numbers in range 0..1294967296 will be twice as likely as the numbers in range 1294967296..3000000000.

1 Like