2
\$\begingroup\$

Background and motivation

I'm a C++ developer with a passion for modern, multi-threaded and functional code. I came across Rust not so long ago and it sounded like everything I wanted my C++ code to be. Naturally, I decided to try it out.

I was working on my own C++ project that had a need for some random numbers. I thought it would be a good opportunity to use some Rust and call into it from my C++ code. After some messing about, I thought I would convert some C/C++ code to Rust from the following pages:

Long story short, I ended up with the following code:

Code

#[macro_use]
extern crate lazy_static;

mod pointgen_random
{    
    const CMWC_CYCLE: u32 = 4096;
    const PHI: u32 = 0x9e3779b9;

    struct ComplementaryMultiplyWithCarryGen {
        q: [u32; CMWC_CYCLE as usize],
        c: u32,
        i: usize
    }

    impl ComplementaryMultiplyWithCarryGen {

        fn new(seed: u32) -> ComplementaryMultiplyWithCarryGen {
            let mut q_init = [0; CMWC_CYCLE as usize];

            q_init[0] = seed;
            q_init[1] = seed + PHI;
            q_init[2] = seed + PHI + PHI;

            for i in 3..CMWC_CYCLE as usize{
                q_init[i] = q_init[i - 3] ^ q_init[i - 2] ^ PHI ^ seed;
            }

            return ComplementaryMultiplyWithCarryGen{q: q_init, c: 362436, i: 4095}; 
        }

        fn reset(&mut self, seed: u32){
            let cmwc = ComplementaryMultiplyWithCarryGen::new(seed);
            self.q = cmwc.q;
            self.i = cmwc.i;
            self.c = cmwc.c;
    }

        fn random(&mut self) -> u32{
            const A: u64 = 18782;
            const R: u32 = 0xfffffffe;

            self.i = (self.i + 1) & (CMWC_CYCLE as usize - 1);
            let t = A * self.q[self.i] as u64 + self.c as u64;

            self.c = (t >> 32) as u32;
            let mut x = (t + self.c as u64) as u32;
            if x < self.c {
                x+=1;
                self.c+=1;
            }

            self.q[self.i] = R - x;
            return self.q[self.i];
        }
    }

    use std::sync::Mutex;

    // Lazy singleton random number generator
    lazy_static!{
            static ref GLOBAL_CMWC_GEN: Mutex<ComplementaryMultiplyWithCarryGen> = Mutex::new(ComplementaryMultiplyWithCarryGen::new(0));
    }

    pub fn get_random_cmwc() -> u32
    {
        GLOBAL_CMWC_GEN.lock().unwrap().random()
    }

    pub fn set_cmwc_seed(seed: u32)
    {
        GLOBAL_CMWC_GEN.lock().unwrap().reset(seed);
    }
}

// Public exports for PointGenLib
// All prefixed with pointgen_ to avoid name conflicts
#[no_mangle]
pub extern "C" fn pointgen_set_cmwc_seed(seed: u32)
{
    pointgen_random::set_cmwc_seed(seed);
}

#[no_mangle]
pub extern "C" fn pointgen_random_cmwc() -> u32
{
    return pointgen_random::get_random_cmwc();
}

It compiles on Windows without warning and appears to give some sensible pseudo-random numbers from 0 to 2^32, but there's just a lot of things in it that I don't like or don't feel right:

  • In fn new(), having q_init be mut seems like a hack, is there a more functional way to do this using slices?
  • Is this an appropriate struct to use the Default trait? I read that it's not recommended to use that.
  • There's a lot of as usize around, I don't quite have the feel for casting types as I would do in C++.
  • fn reset() seems ridiculous, is there a better way to reassign all values at once?

Any other help/suggestions/advice you can give would be very much appreciated.

\$\endgroup\$

1 Answer 1

1
\$\begingroup\$
  1. Run rustfmt.

    • When the preceding thing fits on a single line, curly braces go on the same line:

      pub fn get_random_cmwc() -> u32 {
      
    • Binary operators have space on both sides:

      self.c += 1;
      
    • Curly braces always have whitespace around them:

      for i in 3..CMWC_CYCLE as usize {
      
  2. Run clippy:

    warning: unneeded return statement
      --> src/lib.rs:55:13
       |
    55 |             return self.q[self.i];
       |             ^^^^^^^^^^^^^^^^^^^^^^ help: remove `return` as shown: `self.q[self.i]`
       |
       = help: for further information visit https://github.com/Manishearth/rust-clippy/wiki#needless_return
    
    warning: the loop variable `i` is used to index `q_init`
      --> src/lib.rs:22:13
       |
    22 | /             for i in 3..CMWC_CYCLE as usize {
    23 | |                 q_init[i] = q_init[i - 3] ^ q_init[i - 2] ^ PHI ^ seed;
    24 | |             }
       | |_____________^
       |
       = note: #[warn(needless_range_loop)] on by default
       = help: for further information visit https://github.com/Manishearth/rust-clippy/wiki#needless_range_loop
    help: consider using an iterator
       |             for (i, <item>) in q_init.iter().enumerate().take(CMWC_CYCLE as usize).skip(3) {
    
  3. You really should have some tests. Without them, you cannot tell that refactoring hasn't changed anything, or that you are producing the same value as other implementations of the algorithm. Also, running even a single test would have shown..

  4. You need to think about integer overflow semantics! By default, Rust will panic if an integer overflows in debug mode. Setting q[2] in the initializer causes such an overflow!

  5. The module is providing no obvious benefit. Since you already have the namespace of the crate, just use that directly.

  6. use statements belong at the top of the file, unless they are scoped within a method.

  7. CMWC_CYCLE is always used as a usize, so just make the constant a usize.

  8. Many of the places that CMWC_CYCLE is used could be replaced with an equivalent call to .len().

  9. Your struct takes over 16K of space, which seems very large for the stack. You may wish to consider switching q to a vector.

  10. Instead of Clippy's suggestion, I might slice out a little mutable window of q. To me, this better expresses the initialization logic.

  11. The initial value of i really looks likes CMWC_CYCLE - 1

  12. (self.i + 1) & (CMWC_CYCLE - 1) looks to be a cutesy way of saying (self.i + 1) % CMWC_CYCLE. If so, I'd rely on the optimizer to do the right thing.

  13. Your reset is just replacing self with the result of new, so its usefulness seems low. See mem::swap.

  14. I really don't like global state. If your C code needs to have it, I'd only use the singleton in those two exported functions, inlining the Rust functions. If Rust code calling this needs to create a singleton, it should do so itself.

  15. If you really want to solidly avoid name conflicts, you should add the major and potentially the minor version of your library to any extern "C" functions in addition to the library name. Otherwise you cannot link in multiple conflicting major versions.

  16. Avoid usage of unwrap. Generally, you should favor handling the error. In terminal cases, prefer to use expect so that when the impossible case happens, you have a hint where the problem was.

  17. In general, you often want to split the Rust code and the exposed C shims into different crates. In this case, only the C shims need lazy-static.

#[macro_use]
extern crate lazy_static;

const CMWC_CYCLE: usize = 4096;
const PHI: u32 = 0x9e3779b9;

use std::sync::Mutex;

struct ComplementaryMultiplyWithCarryGen {
    q: [u32; CMWC_CYCLE],
    c: u32,
    i: usize,
}

impl ComplementaryMultiplyWithCarryGen {
    fn new(seed: u32) -> ComplementaryMultiplyWithCarryGen {
        let mut q = [0; CMWC_CYCLE];

        q[0] = seed;
        q[1] = seed.wrapping_add(PHI);
        q[2] = seed.wrapping_add(PHI).wrapping_add(PHI);

        for i in 3..CMWC_CYCLE {
            let window = &mut q[i - 3..i + 1];
            window[3] = window[0] ^ window[1] ^ PHI ^ seed;
        }

        ComplementaryMultiplyWithCarryGen {
            q: q,
            c: 362436,
            i: 4095,
        }
    }

    fn reset(&mut self, seed: u32) {
        *self = ComplementaryMultiplyWithCarryGen::new(seed);
    }

    fn random(&mut self) -> u32 {
        const A: u64 = 18782;
        const R: u32 = 0xfffffffe;

        self.i = (self.i + 1) & (CMWC_CYCLE - 1);
        let t = A * self.q[self.i] as u64 + self.c as u64;

        self.c = (t >> 32) as u32;
        let mut x = (t + self.c as u64) as u32;
        if x < self.c {
            x += 1;
            self.c += 1;
        }

        self.q[self.i] = R - x;
        self.q[self.i]
    }
}

// Lazy singleton random number generator
lazy_static!{
    static ref GLOBAL_CMWC_GEN: Mutex<ComplementaryMultiplyWithCarryGen> =
        Mutex::new(ComplementaryMultiplyWithCarryGen::new(0));
}

// Public exports for PointGenLib
// All prefixed with pointgen_ to avoid name conflicts
#[no_mangle]
pub extern "C" fn pointgen_set_cmwc_seed(seed: u32) {
    GLOBAL_CMWC_GEN.lock()
        .expect("Cannot lock to set seed")
        .reset(seed);
}

#[no_mangle]
pub extern "C" fn pointgen_random_cmwc() -> u32 {
    GLOBAL_CMWC_GEN.lock()
        .expect("Cannot lock to produce number")
        .random()
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn i_didnt_change_anything() {
        let mut rng = ComplementaryMultiplyWithCarryGen::new(0);
        let n: Vec<_> = (0..10).map(|_| rng.random()).collect();
        assert_eq!(n, [4294604858, 367747001, 735501178, 4294962861, 735512785, 3666536092, 3666528614, 4294955383, 367747001, 735501178]);
    }
}

having q_init be mut seems like a hack

It's not, really. The trick is that an entire array has to be guaranteed to be initialized. There's no way for the compiler to tell that some later code will finish initializing the array, especially in the presence of panics. Thus you need to initialize the array with something and then go back and fill in the real values. As mentioned above, you could also switch to using a Vec. Since a Vec has a dynamic size, you can construct it from an iterator, allowing you to avoid mutability at the call site.

Is this an appropriate struct to use the Default trait? I read that it's not recommended to use that.

Where did you read that? I'd like to check out to understand why it says so.

In general, Default is fine — so long as there's a reasonable default! Does a random number generator have a reasonable default? My gut feeling is "yes", but only if you have access to a true RNG that you can use to seed yourself. If you don't have access to a true source of entropy, then not implementing Default is a sign to the user that it's up to them.

There's a lot of as usize around, I don't quite have the feel for casting types as I would do in C++.

Rust generally requires you to be more explicit. After the previous change to CMWC_CYCLE's type, there are a lot fewer of these. The remaining ones deal with cases where you are adding values to a u32 that will exceed the capacity and thus you temporarily need a u64. This seems like nice indication that something "non traditional" is happening there.

\$\endgroup\$
4
  • \$\begingroup\$ Thanks for taking the time to do this review, this is all really helpful stuff. Regarding the Default thing, I can't find the reference now, so maybe I can forget about that. I think in this case it's sensible to not have a default, but then use an abitrary seed for the singleton access from the C shims. Putting the singleton alongside the C shims makes this feel more acceptable. \$\endgroup\$
    – valjean
    Jul 17, 2017 at 6:57
  • \$\begingroup\$ You mentioned using version numbers to extern "C" functions, do you have any reference for best practices when doing this? I've never seen it done before. \$\endgroup\$
    – valjean
    Jul 17, 2017 at 6:57
  • \$\begingroup\$ @valjean You are welcome. Remember that on the Stack Exchange network, the currency is upvotes and accepts. Many of us do it for that dopamine hit. an arbitrary seed for the singleton access — It all depends on what your random numbers are used for. If anything crypto-related, then that's a bad idea. I don't have a reference for the version numbers, it's just something I've learned by watching. Searching for "c link multiple version of library" shows some Q&A with nasty hacks to do it. Really, it's just an extension of the reason you added pointgen_ to each method - to namespace. \$\endgroup\$
    – Shepmaster
    Jul 17, 2017 at 12:16
  • 1
    \$\begingroup\$ I'm too basic for my upvote to show, but I've marked it as accepted :) thanks again \$\endgroup\$
    – valjean
    Jul 17, 2017 at 17:21

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.