ibig/
math.rs

1//! Mathematical functions.
2
3use crate::{arch::word::Word, assert::debug_assert_in_const_fn, primitive::PrimitiveUnsigned};
4
5/// The length of an integer in bits.
6/// 0 for 0.
7#[inline]
8pub(crate) fn bit_len<T: PrimitiveUnsigned>(x: T) -> u32 {
9    T::BIT_SIZE - x.leading_zeros()
10}
11
12/// The length of an integer in bits.
13/// 0 for 0.
14#[inline]
15pub(crate) const fn bit_len_word(x: Word) -> u32 {
16    Word::BIT_SIZE - x.leading_zeros()
17}
18
19/// Ceiling of log_2(x).
20/// x must be non-zero.
21#[inline]
22pub(crate) fn ceil_log_2<T: PrimitiveUnsigned>(x: T) -> u32 {
23    debug_assert!(x != T::from(0u8));
24    bit_len(x - T::from(1u8))
25}
26
27/// Ceiling of log_2(x).
28/// x must be non-zero.
29#[inline]
30pub(crate) const fn ceil_log_2_word(x: Word) -> u32 {
31    debug_assert_in_const_fn!(x != 0);
32    bit_len_word(x - 1)
33}
34
35/// Ceiling of a / b.
36#[inline]
37pub(crate) fn ceil_div<T: PrimitiveUnsigned>(a: T, b: T) -> T {
38    if a == T::from(0u8) {
39        T::from(0u8)
40    } else {
41        (a - T::from(1u8)) / b + T::from(1u8)
42    }
43}
44
45/// Ceiling of a / b.
46#[inline]
47pub(crate) const fn ceil_div_usize(a: usize, b: usize) -> usize {
48    if a == 0 {
49        0
50    } else {
51        (a - 1) / b + 1
52    }
53}
54
55/// Round up a to a multiple of b.
56#[inline]
57pub(crate) fn round_up<T: PrimitiveUnsigned>(a: T, b: T) -> T {
58    ceil_div(a, b) * b
59}
60
61/// Round up a to a multiple of b.
62#[inline]
63pub(crate) const fn round_up_usize(a: usize, b: usize) -> usize {
64    ceil_div_usize(a, b) * b
65}
66
67/// n ones: 2^n - 1
68#[inline]
69pub(crate) fn ones<T>(n: u32) -> T
70where
71    T: PrimitiveUnsigned,
72{
73    if n == 0 {
74        T::from(0u8)
75    } else {
76        T::MAX >> (T::BIT_SIZE - n)
77    }
78}
79
80/// n ones: 2^n - 1
81#[inline]
82pub(crate) const fn ones_word(n: u32) -> Word {
83    if n == 0 {
84        0
85    } else {
86        Word::MAX >> (Word::BIT_SIZE - n)
87    }
88}
89
90#[inline]
91pub(crate) const fn min_usize(a: usize, b: usize) -> usize {
92    if a < b {
93        a
94    } else {
95        b
96    }
97}
98
99#[cfg(test)]
100mod tests {
101    use super::*;
102
103    #[test]
104    fn test_bit_len() {
105        assert_eq!(bit_len(0u32), 0);
106        assert_eq!(bit_len(0b10011101u32), 8);
107        assert_eq!(bit_len(0b10000000u32), 8);
108        assert_eq!(bit_len(0b1111111u32), 7);
109    }
110
111    #[test]
112    fn test_ceil_log_2() {
113        assert_eq!(ceil_log_2(1u32), 0);
114        assert_eq!(ceil_log_2(7u32), 3);
115        assert_eq!(ceil_log_2(8u32), 3);
116        assert_eq!(ceil_log_2(9u32), 4);
117        assert_eq!(ceil_log_2(u32::MAX), 32);
118    }
119
120    #[test]
121    fn test_ceil_div() {
122        assert_eq!(ceil_div(0u32, 10u32), 0);
123        assert_eq!(ceil_div(9u32, 10u32), 1);
124        assert_eq!(ceil_div(10u32, 10u32), 1);
125        assert_eq!(ceil_div(11u32, 10u32), 2);
126    }
127
128    #[test]
129    fn test_round_up() {
130        assert_eq!(round_up(0u32, 10u32), 0);
131        assert_eq!(round_up(9u32, 10u32), 10);
132        assert_eq!(round_up(10u32, 10u32), 10);
133        assert_eq!(round_up(11u32, 10u32), 20);
134    }
135
136    #[test]
137    fn test_ones() {
138        assert_eq!(ones::<u32>(0), 0);
139        assert_eq!(ones::<u32>(5), 0b11111);
140        assert_eq!(ones::<u32>(32), u32::MAX);
141    }
142}
ibig/math.rs

ibig/
math.rs
