sync_utils/
bithacks.rs

1/// bithacks functions.
2/// Implmented according to paper "Faster Remainder by Direct Computation Applications to Compilers and Software Libraries"
3
4/// Given a 32-bit number, find the highest bit number which is set 1.
5/// e.g:
6/// ```
7///   for 0011(3), returns 1.
8///   for 0100(4), returns 2.
9/// ```
10#[inline]
11pub fn highest_bit_set(n: u32) -> u32 {
12    let mut c: u32 = 0;
13    let mut _n = n;
14    if _n >= 65536 {
15        _n >>= 16;
16        c += 16;
17    }
18    if _n >= 256 {
19        _n >>= 8;
20        c += 8;
21    }
22    if _n >= 16 {
23        _n >>= 4;
24        c += 4;
25    }
26    if _n >= 4 {
27        _n >>= 2;
28        c += 2;
29    }
30    if _n >= 2 { c + 1 } else { c }
31}
32
33/// Given a 32-bit number, return the next highest power of 2, and the corresponding thift.
34/// e.g:
35/// ```
36///    if n is 7, then function will return (8, 3), which 8 = 1 << 3
37/// ```
38#[inline]
39pub fn round_up_to_power2(n: u32) -> (u32, u32) {
40    let mut _n = n;
41    _n -= 1;
42    _n |= _n >> 1;
43    _n |= _n >> 2;
44    _n |= _n >> 4;
45    _n |= _n >> 8;
46    _n |= _n >> 16;
47    _n += 1;
48    (_n, highest_bit_set(_n))
49}
50
51#[cfg(test)]
52mod tests {
53    use super::*;
54
55    #[test]
56    fn test_highest_bit_set() {
57        assert_eq!(highest_bit_set(1), 0);
58        assert_eq!(highest_bit_set(3), 1);
59        assert_eq!(highest_bit_set(4), 2);
60        assert_eq!(highest_bit_set(33554432), 25);
61        assert_eq!(highest_bit_set(1615855616), 30);
62    }
63
64    #[test]
65    fn test_round_up_to_power2() {
66        assert_eq!(round_up_to_power2(1), (1, 0));
67        assert_eq!(round_up_to_power2(3), (4, 2));
68        assert_eq!(round_up_to_power2(4), (4, 2));
69        assert_eq!(round_up_to_power2(5), (8, 3));
70        assert_eq!(round_up_to_power2(100), (128, 7));
71        assert_eq!(round_up_to_power2(16 * 1024 - 100), (16 * 1024, 14));
72    }
73}
sync_utils/bithacks.rs

sync_utils/
bithacks.rs
