1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

// Given a value "word", produces an integer in [0,p) without division.
#[inline(always)]
pub fn fastrange_32(word: u32, p: u32) -> u32 {
    ((u64::from(word) * u64::from(p)) >> 32) as u32
}

// Given a value "word", produces an integer in [0,p) without division.
#[inline(always)]
pub fn fastrange_64(word: u64, p: u64) -> u64 {
    ((word as u128 * p as u128) >> 64) as u64
}

// Given a value "word", produces an integer in [0,p) without division.
#[inline(always)]
pub fn fastrange_usize(word: usize, p: usize) -> usize {
    #[cfg(target_pointer_width = "32")]
    {
        fastrange_32(word as u32, p as u32) as usize
    }

    #[cfg(target_pointer_width = "64")]
    {
        fastrange_64(word as u64, p as u64) as usize
    }

    #[cfg(all(not(target_pointer_width = "64"), not(target_pointer_width = "32")))]
    {
        word % p
    }
}

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

    #[test]
    fn test_32() {
        for x in 0..1_000_000 {
            assert!(fastrange_32(x, 5) < 5);
        }
    }

    #[test]
    fn test_64() {
        for x in 0..1_000_000 {
            assert!(fastrange_64(x, 5) < 5);
        }
    }
}