spl_math/
checked_ceil_div.rs

1//! Defines performing checked ceiling division for different types
2
3use crate::uint::U256;
4
5/// Perform a division that does not truncate value from either side, returning
6/// the (quotient, divisor) as a tuple
7///
8/// When dividing integers, we are often left with a remainder, which can
9/// cause information to be lost.  By checking for a remainder, adjusting
10/// the quotient, and recalculating the divisor, this provides the most fair
11/// calculation.
12///
13/// For example, 400 / 32 = 12, with a remainder cutting off 0.5 of amount.
14/// If we simply ceiling the quotient to 13, then we're saying 400 / 32 = 13,
15/// which also cuts off value.  To improve this result, we calculate the other
16/// way around and again check for a remainder: 400 / 13 = 30, with a remainder
17/// of 0.77, and we ceiling that value again.  This gives us a final calculation
18/// of 400 / 31 = 13, which provides a ceiling calculation without cutting off
19/// more value than needed.
20///
21/// This calculation fails if the divisor is larger than the dividend, to avoid
22/// having a result like: 1 / 1000 = 1.
23pub trait CheckedCeilDiv: Sized {
24    /// Perform ceiling division
25    fn checked_ceil_div(&self, rhs: Self) -> Option<(Self, Self)>;
26}
27
28impl CheckedCeilDiv for u128 {
29    fn checked_ceil_div(&self, mut rhs: Self) -> Option<(Self, Self)> {
30        let mut quotient = self.checked_div(rhs)?;
31        // Avoid dividing a small number by a big one and returning 1, and instead
32        // fail.
33        if quotient == 0 {
34            return None;
35        }
36
37        // Ceiling the destination amount if there's any remainder, which will
38        // almost always be the case.
39        let remainder = self.checked_rem(rhs)?;
40        if remainder > 0 {
41            quotient = quotient.checked_add(1)?;
42            // calculate the minimum amount needed to get the dividend amount to
43            // avoid truncating too much
44            rhs = self.checked_div(quotient)?;
45            let remainder = self.checked_rem(quotient)?;
46            if remainder > 0 {
47                rhs = rhs.checked_add(1)?;
48            }
49        }
50        Some((quotient, rhs))
51    }
52}
53
54impl CheckedCeilDiv for U256 {
55    fn checked_ceil_div(&self, mut rhs: Self) -> Option<(Self, Self)> {
56        let mut quotient = self.checked_div(rhs)?;
57        let zero = U256::from(0);
58        let one = U256::from(1);
59        // Avoid dividing a small number by a big one and returning 1, and instead
60        // fail.
61        if quotient == zero {
62            return None;
63        }
64
65        // Ceiling the destination amount if there's any remainder, which will
66        // almost always be the case.
67        let remainder = self.checked_rem(rhs)?;
68        if remainder > zero {
69            quotient = quotient.checked_add(one)?;
70            // calculate the minimum amount needed to get the dividend amount to
71            // avoid truncating too much
72            rhs = self.checked_div(quotient)?;
73            let remainder = self.checked_rem(quotient)?;
74            if remainder > zero {
75                rhs = rhs.checked_add(one)?;
76            }
77        }
78        Some((quotient, rhs))
79    }
80}
spl_math/checked_ceil_div.rs

spl_math/
checked_ceil_div.rs
