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

fixed_bigint/fixeduint/
midpoint_impl.rs
