1
/// Returns the number of bits needed to represent the given value.
2
43738679
pub fn bits_for_value(value: usize) -> u8 {
3
43738679
    if value == 0 {
4
1
        return 1;
5
43738678
    }
6

            
7
43738678
    value.ilog2() as u8 + 1
8
43738679
}
9

            
10
#[cfg(test)]
11
mod tests {
12
    use super::bits_for_value;
13

            
14
    #[test]
15
1
    fn test_bits_for_value() {
16
        // Zero is a special case that still needs a single bit.
17
1
        assert_eq!(bits_for_value(0), 1);
18

            
19
1
        assert_eq!(bits_for_value(1), 1);
20
1
        assert_eq!(bits_for_value(2), 2);
21
1
        assert_eq!(bits_for_value(3), 2);
22
1
        assert_eq!(bits_for_value(4), 3);
23
1
        assert_eq!(bits_for_value(255), 8);
24
1
        assert_eq!(bits_for_value(256), 9);
25
1
        assert_eq!(bits_for_value(usize::MAX), (usize::BITS) as u8);
26
1
    }
27
}
28

            
29
#[cfg(kani)]
30
mod verification {
31
    use super::bits_for_value;
32

            
33
    /// `bits_for_value` returns the minimal bit width: `2^(bits-1) <= value`
34
    /// and `value < 2^bits` (the upper bound where it fits), with zero mapping
35
    /// to a single bit. Verified for every `usize`.
36
    #[kani::proof]
37
    fn bits_for_value_is_minimal_width() {
38
        let value: usize = kani::any();
39
        let bits = bits_for_value(value);
40

            
41
        assert!(bits >= 1);
42

            
43
        if value == 0 {
44
            assert_eq!(bits, 1);
45
        } else {
46
            assert!((1usize << (bits - 1)) <= value);
47
            if (bits as u32) < usize::BITS {
48
                assert!(value < (1usize << bits));
49
            }
50
        }
51
    }
52
}