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

fixed_bigint/fixeduint/
div_ceil_impl.rs
