calyx_utils/
math_utilities.rs

1/// Returns the minimum bit width needed to represents n states with zero inclusive. Panics otherwise.
2/// Note: To represent the number `n`, you need to represent `n+1` states.
3///
4/// For example,
5/// `get_bit_width_from(3)` == 2 // 3 states requires a minimum of 2 bits.
6/// `get_bit_width_from(4)` == 2 // 4 states can be represented with exactly 2 bits.
7/// `get_bit_width_from(5)` == 3 // 5 states requires a minimum of 3 bits.
8#[inline(always)]
9pub fn get_bit_width_from(states: u64) -> u64 {
10    if states == 0_u64 || states == 1_u64 {
11        return states;
12    }
13    for index in 0u8..63 {
14        let x = (63 - index) as u64;
15        if states & (1u64 << x) != 0 {
16            // If n is a power of two, return x. Otherwise, x + 1.
17            return if (states & (states - 1)) == 0u64 {
18                x
19            } else {
20                x + 1
21            };
22        }
23    }
24    panic!();
25}
26
27/// To run the get_bit_width_from tests:
28/// ```bash
29/// cd calyx/src/passes && cargo test math_utilities
30/// ```
31#[cfg(test)]
32mod tests {
33    use super::*;
34
35    #[test]
36    fn get_bit_width_from_zero() {
37        assert_eq!(get_bit_width_from(0), 0);
38    }
39
40    #[test]
41    fn get_bit_width_from_one() {
42        assert_eq!(get_bit_width_from(1), 1);
43    }
44
45    #[test]
46    fn get_bit_width_from_three() {
47        assert_eq!(get_bit_width_from(3), 2);
48    }
49
50    #[test]
51    fn get_bit_width_from_four() {
52        assert_eq!(get_bit_width_from(4), 2);
53    }
54
55    #[test]
56    fn get_bit_width_from_in_between() {
57        assert_eq!(get_bit_width_from(9), 4);
58        assert_eq!(get_bit_width_from(10), 4);
59        assert_eq!(get_bit_width_from(11), 4);
60        assert_eq!(get_bit_width_from(12), 4);
61        assert_eq!(get_bit_width_from(13), 4);
62        assert_eq!(get_bit_width_from(14), 4);
63        assert_eq!(get_bit_width_from(15), 4);
64    }
65
66    #[test]
67    fn get_bit_width_near_multiples_of_two() {
68        let mut input: u64 = 2;
69        let mut expected: u64 = 1;
70        while input < (2 << 15) {
71            // 2^n - 1 bits should be represented by n bits.
72            assert_eq!(get_bit_width_from(input - 1), expected);
73            // 2^n bits should be represented by n bits.
74            assert_eq!(get_bit_width_from(input), expected);
75            // 2^n + 1 bits should be represented by n + 1 bits.
76            assert_eq!(get_bit_width_from(input + 1), expected + 1);
77
78            input <<= 1;
79            expected += 1;
80        }
81    }
82
83    #[test]
84    fn get_bit_width_from_large_numbers() {
85        assert_eq!(get_bit_width_from(2u64.pow(61)), 61);
86        assert_eq!(get_bit_width_from(2u64.pow(62)), 62);
87        assert_eq!(get_bit_width_from(2u64.pow(63)), 63);
88        assert_eq!(get_bit_width_from(18446744073709551614), 64); // 2^64 - 1
89    }
90}
calyx_utils/math_utilities.rs

calyx_utils/
math_utilities.rs
