fixed_bigint/fixeduint/
midpoint_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//! Midpoint (average) implementation for FixedUInt.
16
17use super::{FixedUInt, MachineWord};
18use crate::machineword::ConstMachineWord;
19use const_num_traits::Midpoint;
20use const_num_traits::Personality;
21
22c0nst::c0nst! {
23    c0nst impl<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality> Midpoint for FixedUInt<T, N, P> {
24        type Output = Self;
25        fn midpoint(self, rhs: Self) -> Self {
26            // (a & b) + ((a ^ b) >> 1) avoids overflow
27            (self & rhs) + ((self ^ rhs) >> 1usize)
28        }
29    }
30
31    c0nst impl<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality> Midpoint for &FixedUInt<T, N, P> {
32        type Output = FixedUInt<T, N, P>;
33        fn midpoint(self, rhs: Self) -> FixedUInt<T, N, P> {
34            <FixedUInt<T, N, P> as Midpoint>::midpoint(*self, *rhs)
35        }
36    }
37}
38
39#[cfg(test)]
40mod tests {
41    use super::*;
42
43    #[test]
44    fn test_midpoint() {
45        type U16 = FixedUInt<u8, 2>;
46
47        // Simple midpoint
48        assert_eq!(
49            Midpoint::midpoint(U16::from(0u8), U16::from(10u8)),
50            U16::from(5u8)
51        );
52
53        // Order doesn't matter
54        assert_eq!(
55            Midpoint::midpoint(U16::from(10u8), U16::from(0u8)),
56            U16::from(5u8)
57        );
58
59        // Midpoint rounds down
60        assert_eq!(
61            Midpoint::midpoint(U16::from(0u8), U16::from(9u8)),
62            U16::from(4u8)
63        );
64
65        // Same values
66        assert_eq!(
67            Midpoint::midpoint(U16::from(42u8), U16::from(42u8)),
68            U16::from(42u8)
69        );
70
71        // Max values (no overflow)
72        let max = U16::from(0xFFFFu16);
73        assert_eq!(Midpoint::midpoint(max, max), max);
74
75        // 0 and max
76        assert_eq!(
77            Midpoint::midpoint(U16::from(0u8), max),
78            U16::from(0x7FFFu16)
79        );
80    }
81
82    c0nst::c0nst! {
83        pub c0nst fn const_midpoint<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(
84            a: FixedUInt<T, N, P>,
85            b: FixedUInt<T, N, P>,
86        ) -> FixedUInt<T, N, P> {
87            Midpoint::midpoint(a, b)
88        }
89    }
90
91    #[test]
92    fn test_const_midpoint() {
93        type U16 = FixedUInt<u8, 2>;
94
95        assert_eq!(
96            const_midpoint(U16::from(0u8), U16::from(10u8)),
97            U16::from(5u8)
98        );
99
100        #[cfg(feature = "nightly")]
101        {
102            const A: U16 = FixedUInt::from_array([0, 0]);
103            const B: U16 = FixedUInt::from_array([10, 0]);
104            const MID: U16 = const_midpoint(A, B);
105            assert_eq!(MID, FixedUInt::from_array([5, 0]));
106
107            // Test with max values
108            const MAX: U16 = FixedUInt::from_array([0xFF, 0xFF]);
109            const MID_MAX: U16 = const_midpoint(MAX, MAX);
110            assert_eq!(MID_MAX, MAX);
111        }
112    }
113
114    /// Polymorphic test: verify midpoint produces identical results across
115    /// different word layouts for the same values.
116    #[test]
117    fn test_midpoint_polymorphic() {
118        fn test_mid<T>(a: T, b: T, expected: T)
119        where
120            T: Midpoint<Output = T> + Eq + core::fmt::Debug + Copy,
121        {
122            assert_eq!(Midpoint::midpoint(a, b), expected);
123            assert_eq!(Midpoint::midpoint(b, a), expected); // order doesn't matter
124        }
125
126        // Test with different layouts
127        type U8x2 = FixedUInt<u8, 2>;
128        type U8x4 = FixedUInt<u8, 4>;
129        type U16x2 = FixedUInt<u16, 2>;
130
131        // 0 and 100
132        test_mid(U8x2::from(0u8), U8x2::from(100u8), U8x2::from(50u8));
133        test_mid(U8x4::from(0u8), U8x4::from(100u8), U8x4::from(50u8));
134        test_mid(U16x2::from(0u8), U16x2::from(100u8), U16x2::from(50u8));
135
136        // Same with primitives
137        test_mid(0u8, 100u8, 50u8);
138        test_mid(0u16, 100u16, 50u16);
139        test_mid(0u32, 100u32, 50u32);
140
141        // Rounding down: (0 + 99) / 2 = 49.5 -> 49
142        test_mid(U8x2::from(0u8), U8x2::from(99u8), U8x2::from(49u8));
143        test_mid(0u8, 99u8, 49u8);
144
145        // Large values that would overflow with naive (a+b)/2
146        let max_u16 = U8x2::from(0xFFFFu16);
147        test_mid(max_u16, max_u16, max_u16);
148        test_mid(u16::MAX, u16::MAX, u16::MAX);
149    }
150}
fixed_bigint/fixeduint/midpoint_impl.rs

fixed_bigint/fixeduint/
midpoint_impl.rs
