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::{
19    ConstBitPrimInt, ConstBounded, ConstOne, ConstPowerOfTwo, ConstWrappingSub, ConstZero,
20};
21use crate::machineword::ConstMachineWord;
22use crate::personality::{Personality, PersonalityTag};
23
24c0nst::c0nst! {
25    impl<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality> c0nst ConstPowerOfTwo for FixedUInt<T, N, P> {
26        fn is_power_of_two(&self) -> bool {
27            match P::TAG {
28                PersonalityTag::Nct => {
29                    !self.is_zero() && (*self & (*self - Self::one())).is_zero()
30                }
31                PersonalityTag::Ct => {
32                    let a = !self.is_zero();
33                    let b = (*self & self.wrapping_sub(&Self::one())).is_zero();
34                    a & b
35                }
36            }
37        }
38
39        fn next_power_of_two(self) -> Self {
40            match P::TAG {
41                PersonalityTag::Nct => {
42                    match self.checked_next_power_of_two() {
43                        Some(v) => v,
44                        None => panic!("FixedUInt::next_power_of_two overflow: result exceeds type capacity"),
45                    }
46                }
47                PersonalityTag::Ct => {
48                    // CT path: saturate to MAX on overflow (same convention
49                    // as SaturatingAdd/Sub/Mul). The Nct path's panic is
50                    // value-dependent and so unavailable here; silently
51                    // returning a wrong power of two would be worse than
52                    // a defined saturation sentinel.
53                    let m_one = <Self as ConstWrappingSub>::wrapping_sub(&self, &Self::one());
54                    let leading = ConstBitPrimInt::leading_zeros(m_one);
55                    let bits = Self::BIT_SIZE as u32 - leading;
56                    let shifted = Self::one() << (bits as usize);
57                    let is_zero = <Self as ConstZero>::is_zero(&self) as u8;
58                    // Overflow when bits >= BIT_SIZE (and self != 0).
59                    let overflow = ((bits >= Self::BIT_SIZE as u32) as u8) & (1u8 ^ is_zero);
60                    let saturated = crate::fixeduint::const_ct_select(
61                        shifted,
62                        <Self as ConstBounded>::max_value(),
63                        overflow,
64                    );
65                    crate::fixeduint::const_ct_select(saturated, Self::one(), is_zero)
66                }
67            }
68        }
69
70        fn checked_next_power_of_two(self) -> Option<Self> {
71            if self.is_zero() {
72                return Some(Self::one());
73            }
74            // Bit manipulation trick: (n-1).leading_zeros() gives the bit position
75            // needed for the next power of two, handling both power-of-two and
76            // non-power-of-two inputs correctly.
77            let m_one = self - Self::one();
78            let leading = ConstBitPrimInt::leading_zeros(m_one);
79            let bits = Self::BIT_SIZE as u32 - leading;
80
81            // Check for overflow
82            if bits >= Self::BIT_SIZE as u32 {
83                return None;
84            }
85            Some(Self::one() << (bits as usize))
86        }
87    }
88}
89
90#[cfg(test)]
91mod tests {
92    use super::*;
93
94    #[test]
95    fn test_is_power_of_two() {
96        type U16 = FixedUInt<u8, 2>;
97
98        assert!(!ConstPowerOfTwo::is_power_of_two(&U16::from(0u8)));
99        assert!(ConstPowerOfTwo::is_power_of_two(&U16::from(1u8)));
100        assert!(ConstPowerOfTwo::is_power_of_two(&U16::from(2u8)));
101        assert!(!ConstPowerOfTwo::is_power_of_two(&U16::from(3u8)));
102        assert!(ConstPowerOfTwo::is_power_of_two(&U16::from(4u8)));
103        assert!(!ConstPowerOfTwo::is_power_of_two(&U16::from(5u8)));
104        assert!(ConstPowerOfTwo::is_power_of_two(&U16::from(8u8)));
105        assert!(ConstPowerOfTwo::is_power_of_two(&U16::from(16u8)));
106        assert!(ConstPowerOfTwo::is_power_of_two(&U16::from(128u8)));
107        assert!(ConstPowerOfTwo::is_power_of_two(&U16::from(256u16)));
108        assert!(!ConstPowerOfTwo::is_power_of_two(&U16::from(255u8)));
109    }
110
111    #[test]
112    fn test_next_power_of_two() {
113        type U16 = FixedUInt<u8, 2>;
114
115        assert_eq!(
116            ConstPowerOfTwo::next_power_of_two(U16::from(0u8)),
117            U16::from(1u8)
118        );
119        assert_eq!(
120            ConstPowerOfTwo::next_power_of_two(U16::from(1u8)),
121            U16::from(1u8)
122        );
123        assert_eq!(
124            ConstPowerOfTwo::next_power_of_two(U16::from(2u8)),
125            U16::from(2u8)
126        );
127        assert_eq!(
128            ConstPowerOfTwo::next_power_of_two(U16::from(3u8)),
129            U16::from(4u8)
130        );
131        assert_eq!(
132            ConstPowerOfTwo::next_power_of_two(U16::from(4u8)),
133            U16::from(4u8)
134        );
135        assert_eq!(
136            ConstPowerOfTwo::next_power_of_two(U16::from(5u8)),
137            U16::from(8u8)
138        );
139        assert_eq!(
140            ConstPowerOfTwo::next_power_of_two(U16::from(7u8)),
141            U16::from(8u8)
142        );
143        assert_eq!(
144            ConstPowerOfTwo::next_power_of_two(U16::from(8u8)),
145            U16::from(8u8)
146        );
147        assert_eq!(
148            ConstPowerOfTwo::next_power_of_two(U16::from(9u8)),
149            U16::from(16u8)
150        );
151        assert_eq!(
152            ConstPowerOfTwo::next_power_of_two(U16::from(100u8)),
153            U16::from(128u8)
154        );
155        assert_eq!(
156            ConstPowerOfTwo::next_power_of_two(U16::from(128u8)),
157            U16::from(128u8)
158        );
159        assert_eq!(
160            ConstPowerOfTwo::next_power_of_two(U16::from(129u8)),
161            U16::from(256u16)
162        );
163    }
164
165    #[test]
166    fn test_checked_next_power_of_two() {
167        type U16 = FixedUInt<u8, 2>;
168
169        assert_eq!(
170            ConstPowerOfTwo::checked_next_power_of_two(U16::from(0u8)),
171            Some(U16::from(1u8))
172        );
173        assert_eq!(
174            ConstPowerOfTwo::checked_next_power_of_two(U16::from(1u8)),
175            Some(U16::from(1u8))
176        );
177        assert_eq!(
178            ConstPowerOfTwo::checked_next_power_of_two(U16::from(100u8)),
179            Some(U16::from(128u8))
180        );
181
182        // Test overflow case - 32769 needs next power of 2 = 65536 which overflows u16
183        let large = U16::from(32769u16);
184        assert_eq!(ConstPowerOfTwo::checked_next_power_of_two(large), None);
185
186        // But 32768 is already a power of two
187        let pow2 = U16::from(32768u16);
188        assert_eq!(ConstPowerOfTwo::checked_next_power_of_two(pow2), Some(pow2));
189    }
190
191    c0nst::c0nst! {
192        pub c0nst fn const_is_power_of_two<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(
193            v: &FixedUInt<T, N, P>,
194        ) -> bool {
195            ConstPowerOfTwo::is_power_of_two(v)
196        }
197
198        pub c0nst fn const_next_power_of_two<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(
199            v: FixedUInt<T, N, P>,
200        ) -> FixedUInt<T, N, P> {
201            ConstPowerOfTwo::next_power_of_two(v)
202        }
203    }
204
205    #[test]
206    fn test_const_power_of_two() {
207        type U16 = FixedUInt<u8, 2>;
208
209        assert!(const_is_power_of_two(&U16::from(4u8)));
210        assert!(!const_is_power_of_two(&U16::from(5u8)));
211        assert_eq!(const_next_power_of_two(U16::from(5u8)), U16::from(8u8));
212
213        #[cfg(feature = "nightly")]
214        {
215            const FOUR: U16 = FixedUInt::from_array([4, 0]);
216            const FIVE: U16 = FixedUInt::from_array([5, 0]);
217            const IS_POW2_TRUE: bool = const_is_power_of_two(&FOUR);
218            const IS_POW2_FALSE: bool = const_is_power_of_two(&FIVE);
219            const NEXT_POW2: U16 = const_next_power_of_two(FIVE);
220
221            assert!(IS_POW2_TRUE);
222            assert!(!IS_POW2_FALSE);
223            assert_eq!(NEXT_POW2, FixedUInt::from_array([8, 0]));
224        }
225    }
226}
fixed_bigint/fixeduint/power_of_two_impl.rs

fixed_bigint/fixeduint/
power_of_two_impl.rs
