fixed_bigint/fixeduint/
div_ceil_impl.rs

1// Copyright 2021 Google LLC
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//      http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! Ceiling division for FixedUInt.
16
17use super::{FixedUInt, MachineWord, const_div, const_is_zero};
18use crate::machineword::ConstMachineWord;
19use const_num_traits::Nct;
20use const_num_traits::{CheckedAdd, DivCeil, One};
21
22c0nst::c0nst! {
23    c0nst impl<T: [c0nst] ConstMachineWord + MachineWord, const N: usize> DivCeil for FixedUInt<T, N, Nct> {
24        type Output = FixedUInt<T, N, Nct>;
25        fn div_ceil(self, rhs: Self) -> Self {
26            match checked_div_ceil_impl(self, rhs) {
27                Some(v) => v,
28                None => panic!("div_ceil: division by zero or overflow"),
29            }
30        }
31    }
32
33    c0nst impl<T: [c0nst] ConstMachineWord + MachineWord, const N: usize> DivCeil for &FixedUInt<T, N, Nct> {
34        type Output = FixedUInt<T, N, Nct>;
35        fn div_ceil(self, rhs: Self) -> FixedUInt<T, N, Nct> {
36            <FixedUInt<T, N, Nct> as DivCeil>::div_ceil(FixedUInt::from_array(self.array), FixedUInt::from_array(rhs.array))
37        }
38    }
39}
40
41c0nst::c0nst! {
42    /// Standalone const fn body for div_ceil's checked variant, used both
43    /// by the inherent `checked_div_ceil` shim and (transitively) by the
44    /// `DivCeil::div_ceil` trait impl above. Kept free-floating rather
45    /// than as an inherent method because the c0nst macro doesn't
46    /// translate `[c0nst]` bounds on inherent `impl` blocks (only on
47    /// `c0nst fn` items directly).
48    pub(crate) c0nst fn checked_div_ceil_impl<T: [c0nst] ConstMachineWord + MachineWord, const N: usize>(
49        a: FixedUInt<T, N, Nct>, rhs: FixedUInt<T, N, Nct>,
50    ) -> Option<FixedUInt<T, N, Nct>> {
51        if const_is_zero(&rhs.array) {
52            return None;
53        }
54        let mut quotient = a.array;
55        let remainder = const_div(&mut quotient, &rhs.array);
56        if const_is_zero(&remainder) {
57            Some(FixedUInt::from_array(quotient))
58        } else {
59            <FixedUInt<T, N, Nct> as CheckedAdd>::checked_add(
60                FixedUInt::from_array(quotient),
61                <FixedUInt<T, N, Nct> as One>::one(),
62            )
63        }
64    }
65}
66
67impl<T: ConstMachineWord + MachineWord, const N: usize> FixedUInt<T, N, Nct> {
68    /// `div_ceil` variant returning `None` on divide-by-zero or overflow.
69    ///
70    /// Not itself `const fn` — the `c0nst!` macro can't emit `[c0nst]`
71    /// bounds on inherent impls. Nightly callers wanting the const path
72    /// call `checked_div_ceil_impl` (the free `pub(crate) c0nst fn`
73    /// above) directly.
74    pub fn checked_div_ceil(self, rhs: Self) -> Option<Self> {
75        checked_div_ceil_impl(self, rhs)
76    }
77}
78
79#[cfg(test)]
80mod tests {
81    use super::*;
82
83    #[test]
84    fn test_div_ceil() {
85        type U16 = FixedUInt<u8, 2>;
86
87        // Exact division
88        assert_eq!(
89            DivCeil::div_ceil(U16::from(10u8), U16::from(5u8)),
90            U16::from(2u8)
91        );
92        assert_eq!(
93            DivCeil::div_ceil(U16::from(10u8), U16::from(2u8)),
94            U16::from(5u8)
95        );
96
97        // Rounds up
98        assert_eq!(
99            DivCeil::div_ceil(U16::from(10u8), U16::from(3u8)),
100            U16::from(4u8)
101        ); // 10/3 = 3.33... -> 4
102        assert_eq!(
103            DivCeil::div_ceil(U16::from(11u8), U16::from(3u8)),
104            U16::from(4u8)
105        ); // 11/3 = 3.66... -> 4
106        assert_eq!(
107            DivCeil::div_ceil(U16::from(12u8), U16::from(3u8)),
108            U16::from(4u8)
109        ); // 12/3 = 4 exact
110
111        // Edge cases
112        assert_eq!(
113            DivCeil::div_ceil(U16::from(0u8), U16::from(5u8)),
114            U16::from(0u8)
115        );
116        assert_eq!(
117            DivCeil::div_ceil(U16::from(1u8), U16::from(5u8)),
118            U16::from(1u8)
119        ); // 1/5 = 0.2 -> 1
120        assert_eq!(
121            DivCeil::div_ceil(U16::from(1u8), U16::from(1u8)),
122            U16::from(1u8)
123        );
124    }
125
126    #[test]
127    fn test_checked_div_ceil() {
128        type U16 = FixedUInt<u8, 2>;
129
130        assert_eq!(
131            FixedUInt::checked_div_ceil(U16::from(10u8), U16::from(3u8)),
132            Some(U16::from(4u8))
133        );
134
135        // Division by zero
136        assert_eq!(
137            FixedUInt::checked_div_ceil(U16::from(10u8), U16::from(0u8)),
138            None
139        );
140
141        // Edge case: MAX / 2 = 32767 remainder 1, ceil = 32768
142        assert_eq!(
143            FixedUInt::checked_div_ceil(U16::from(65535u16), U16::from(2u16)),
144            Some(U16::from(32768u16))
145        );
146
147        // Edge case: MAX / 1 = MAX exactly (no remainder, no +1 needed)
148        assert_eq!(
149            FixedUInt::checked_div_ceil(U16::from(65535u16), U16::from(1u16)),
150            Some(U16::from(65535u16))
151        );
152    }
153
154    c0nst::c0nst! {
155        pub c0nst fn const_div_ceil<T: [c0nst] ConstMachineWord + MachineWord, const N: usize>(
156            a: FixedUInt<T, N, Nct>,
157            b: FixedUInt<T, N, Nct>,
158        ) -> FixedUInt<T, N, Nct> {
159            DivCeil::div_ceil(a, b)
160        }
161        /// Const-callable parallel to `FixedUInt::checked_div_ceil`
162        /// (which can't itself be `const fn` on an inherent impl). Just
163        /// re-exposes the existing `checked_div_ceil_impl` helper above
164        /// under a `const_*` test-shim name for the empirical-proof
165        /// pattern other files use.
166        pub c0nst fn const_checked_div_ceil<T: [c0nst] ConstMachineWord + MachineWord, const N: usize>(
167            a: FixedUInt<T, N, Nct>,
168            b: FixedUInt<T, N, Nct>,
169        ) -> Option<FixedUInt<T, N, Nct>> {
170            super::checked_div_ceil_impl(a, b)
171        }
172    }
173
174    #[test]
175    fn test_const_div_ceil() {
176        type U16 = FixedUInt<u8, 2>;
177
178        assert_eq!(
179            const_div_ceil(U16::from(10u8), U16::from(3u8)),
180            U16::from(4u8)
181        );
182        assert_eq!(
183            const_checked_div_ceil(U16::from(10u8), U16::from(3u8)),
184            Some(U16::from(4u8))
185        );
186        assert_eq!(
187            const_checked_div_ceil(U16::from(10u8), U16::from(0u8)),
188            None
189        );
190
191        #[cfg(feature = "nightly")]
192        {
193            const TEN: U16 = FixedUInt::from_array([10, 0]);
194            const THREE: U16 = FixedUInt::from_array([3, 0]);
195            const ZERO: U16 = FixedUInt::from_array([0, 0]);
196            const RESULT: U16 = const_div_ceil(TEN, THREE);
197            const CHECKED_OK: Option<U16> = const_checked_div_ceil(TEN, THREE);
198            const CHECKED_ZERO: Option<U16> = const_checked_div_ceil(TEN, ZERO);
199            assert_eq!(RESULT, FixedUInt::from_array([4, 0]));
200            assert!(CHECKED_OK.is_some());
201            assert!(CHECKED_ZERO.is_none());
202        }
203    }
204}
fixed_bigint/fixeduint/div_ceil_impl.rs

fixed_bigint/fixeduint/
div_ceil_impl.rs
