fixed_bigint/fixeduint/
power_of_two_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//! Power-of-two operations for FixedUInt.
16
17use super::{FixedUInt, MachineWord};
18use crate::const_numtraits::{ConstOne, ConstPowerOfTwo, ConstPrimInt, ConstZero};
19use crate::machineword::ConstMachineWord;
20
21c0nst::c0nst! {
22    impl<T: [c0nst] ConstMachineWord + MachineWord, const N: usize> c0nst ConstPowerOfTwo for FixedUInt<T, N> {
23        fn is_power_of_two(&self) -> bool {
24            // Standard bitwise trick: n is power of two iff n != 0 && (n & (n-1)) == 0
25            // This works because a power of two has exactly one bit set,
26            // and subtracting 1 flips all lower bits, so AND gives zero.
27            !self.is_zero() && (*self & (*self - Self::one())).is_zero()
28        }
29
30        fn next_power_of_two(self) -> Self {
31            match self.checked_next_power_of_two() {
32                Some(v) => v,
33                None => panic!("FixedUInt::next_power_of_two overflow: result exceeds type capacity"),
34            }
35        }
36
37        fn checked_next_power_of_two(self) -> Option<Self> {
38            if self.is_zero() {
39                return Some(Self::one());
40            }
41            // Bit manipulation trick: (n-1).leading_zeros() gives the bit position
42            // needed for the next power of two, handling both power-of-two and
43            // non-power-of-two inputs correctly.
44            let m_one = self - Self::one();
45            let leading = ConstPrimInt::leading_zeros(m_one);
46            let bits = Self::BIT_SIZE as u32 - leading;
47
48            // Check for overflow
49            if bits >= Self::BIT_SIZE as u32 {
50                return None;
51            }
52            Some(Self::one() << (bits as usize))
53        }
54    }
55}
56
57#[cfg(test)]
58mod tests {
59    use super::*;
60
61    #[test]
62    fn test_is_power_of_two() {
63        type U16 = FixedUInt<u8, 2>;
64
65        assert!(!ConstPowerOfTwo::is_power_of_two(&U16::from(0u8)));
66        assert!(ConstPowerOfTwo::is_power_of_two(&U16::from(1u8)));
67        assert!(ConstPowerOfTwo::is_power_of_two(&U16::from(2u8)));
68        assert!(!ConstPowerOfTwo::is_power_of_two(&U16::from(3u8)));
69        assert!(ConstPowerOfTwo::is_power_of_two(&U16::from(4u8)));
70        assert!(!ConstPowerOfTwo::is_power_of_two(&U16::from(5u8)));
71        assert!(ConstPowerOfTwo::is_power_of_two(&U16::from(8u8)));
72        assert!(ConstPowerOfTwo::is_power_of_two(&U16::from(16u8)));
73        assert!(ConstPowerOfTwo::is_power_of_two(&U16::from(128u8)));
74        assert!(ConstPowerOfTwo::is_power_of_two(&U16::from(256u16)));
75        assert!(!ConstPowerOfTwo::is_power_of_two(&U16::from(255u8)));
76    }
77
78    #[test]
79    fn test_next_power_of_two() {
80        type U16 = FixedUInt<u8, 2>;
81
82        assert_eq!(
83            ConstPowerOfTwo::next_power_of_two(U16::from(0u8)),
84            U16::from(1u8)
85        );
86        assert_eq!(
87            ConstPowerOfTwo::next_power_of_two(U16::from(1u8)),
88            U16::from(1u8)
89        );
90        assert_eq!(
91            ConstPowerOfTwo::next_power_of_two(U16::from(2u8)),
92            U16::from(2u8)
93        );
94        assert_eq!(
95            ConstPowerOfTwo::next_power_of_two(U16::from(3u8)),
96            U16::from(4u8)
97        );
98        assert_eq!(
99            ConstPowerOfTwo::next_power_of_two(U16::from(4u8)),
100            U16::from(4u8)
101        );
102        assert_eq!(
103            ConstPowerOfTwo::next_power_of_two(U16::from(5u8)),
104            U16::from(8u8)
105        );
106        assert_eq!(
107            ConstPowerOfTwo::next_power_of_two(U16::from(7u8)),
108            U16::from(8u8)
109        );
110        assert_eq!(
111            ConstPowerOfTwo::next_power_of_two(U16::from(8u8)),
112            U16::from(8u8)
113        );
114        assert_eq!(
115            ConstPowerOfTwo::next_power_of_two(U16::from(9u8)),
116            U16::from(16u8)
117        );
118        assert_eq!(
119            ConstPowerOfTwo::next_power_of_two(U16::from(100u8)),
120            U16::from(128u8)
121        );
122        assert_eq!(
123            ConstPowerOfTwo::next_power_of_two(U16::from(128u8)),
124            U16::from(128u8)
125        );
126        assert_eq!(
127            ConstPowerOfTwo::next_power_of_two(U16::from(129u8)),
128            U16::from(256u16)
129        );
130    }
131
132    #[test]
133    fn test_checked_next_power_of_two() {
134        type U16 = FixedUInt<u8, 2>;
135
136        assert_eq!(
137            ConstPowerOfTwo::checked_next_power_of_two(U16::from(0u8)),
138            Some(U16::from(1u8))
139        );
140        assert_eq!(
141            ConstPowerOfTwo::checked_next_power_of_two(U16::from(1u8)),
142            Some(U16::from(1u8))
143        );
144        assert_eq!(
145            ConstPowerOfTwo::checked_next_power_of_two(U16::from(100u8)),
146            Some(U16::from(128u8))
147        );
148
149        // Test overflow case - 32769 needs next power of 2 = 65536 which overflows u16
150        let large = U16::from(32769u16);
151        assert_eq!(ConstPowerOfTwo::checked_next_power_of_two(large), None);
152
153        // But 32768 is already a power of two
154        let pow2 = U16::from(32768u16);
155        assert_eq!(ConstPowerOfTwo::checked_next_power_of_two(pow2), Some(pow2));
156    }
157
158    c0nst::c0nst! {
159        pub c0nst fn const_is_power_of_two<T: [c0nst] ConstMachineWord + MachineWord, const N: usize>(
160            v: &FixedUInt<T, N>,
161        ) -> bool {
162            ConstPowerOfTwo::is_power_of_two(v)
163        }
164
165        pub c0nst fn const_next_power_of_two<T: [c0nst] ConstMachineWord + MachineWord, const N: usize>(
166            v: FixedUInt<T, N>,
167        ) -> FixedUInt<T, N> {
168            ConstPowerOfTwo::next_power_of_two(v)
169        }
170    }
171
172    #[test]
173    fn test_const_power_of_two() {
174        type U16 = FixedUInt<u8, 2>;
175
176        assert!(const_is_power_of_two(&U16::from(4u8)));
177        assert!(!const_is_power_of_two(&U16::from(5u8)));
178        assert_eq!(const_next_power_of_two(U16::from(5u8)), U16::from(8u8));
179
180        #[cfg(feature = "nightly")]
181        {
182            const FOUR: U16 = FixedUInt { array: [4, 0] };
183            const FIVE: U16 = FixedUInt { array: [5, 0] };
184            const IS_POW2_TRUE: bool = const_is_power_of_two(&FOUR);
185            const IS_POW2_FALSE: bool = const_is_power_of_two(&FIVE);
186            const NEXT_POW2: U16 = const_next_power_of_two(FIVE);
187
188            assert!(IS_POW2_TRUE);
189            assert!(!IS_POW2_FALSE);
190            assert_eq!(NEXT_POW2, FixedUInt { array: [8, 0] });
191        }
192    }
193}
fixed_bigint/fixeduint/power_of_two_impl.rs

fixed_bigint/fixeduint/
power_of_two_impl.rs
