fixed_bigint/fixeduint/
checked_pow_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//! Checked power implementation for FixedUInt.
16
17use super::{FixedUInt, MachineWord};
18use crate::const_numtraits::{ConstCheckedMul, ConstCheckedPow, ConstOne};
19use crate::machineword::ConstMachineWord;
20
21c0nst::c0nst! {
22    impl<T: [c0nst] ConstMachineWord + MachineWord, const N: usize> c0nst ConstCheckedPow for FixedUInt<T, N> {
23        fn checked_pow(self, exp: u32) -> Option<Self> {
24            if exp == 0 {
25                return Some(Self::one());
26            }
27            // Exponentiation by squaring with overflow checking
28            let mut result = Self::one();
29            let mut base = self;
30            let mut e = exp;
31            while e > 0 {
32                if (e & 1) == 1 {
33                    result = match ConstCheckedMul::checked_mul(&result, &base) {
34                        Some(v) => v,
35                        None => return None,
36                    };
37                }
38                e >>= 1;
39                if e > 0 {
40                    base = match ConstCheckedMul::checked_mul(&base, &base) {
41                        Some(v) => v,
42                        None => return None,
43                    };
44                }
45            }
46            Some(result)
47        }
48    }
49}
50
51#[cfg(test)]
52mod tests {
53    use super::*;
54
55    #[test]
56    fn test_checked_pow() {
57        type U16 = FixedUInt<u8, 2>;
58
59        // Basic cases
60        assert_eq!(
61            ConstCheckedPow::checked_pow(U16::from(2u8), 0),
62            Some(U16::from(1u8))
63        );
64        assert_eq!(
65            ConstCheckedPow::checked_pow(U16::from(2u8), 1),
66            Some(U16::from(2u8))
67        );
68        assert_eq!(
69            ConstCheckedPow::checked_pow(U16::from(2u8), 2),
70            Some(U16::from(4u8))
71        );
72        assert_eq!(
73            ConstCheckedPow::checked_pow(U16::from(2u8), 8),
74            Some(U16::from(256u16))
75        );
76        assert_eq!(
77            ConstCheckedPow::checked_pow(U16::from(3u8), 3),
78            Some(U16::from(27u8))
79        );
80
81        // Edge cases
82        assert_eq!(
83            ConstCheckedPow::checked_pow(U16::from(0u8), 0),
84            Some(U16::from(1u8))
85        );
86        assert_eq!(
87            ConstCheckedPow::checked_pow(U16::from(0u8), 5),
88            Some(U16::from(0u8))
89        );
90        assert_eq!(
91            ConstCheckedPow::checked_pow(U16::from(1u8), 100),
92            Some(U16::from(1u8))
93        );
94
95        // Overflow cases
96        assert_eq!(ConstCheckedPow::checked_pow(U16::from(2u8), 16), None); // 2^16 = 65536 > 65535
97        assert_eq!(ConstCheckedPow::checked_pow(U16::from(256u16), 2), None); // 256^2 = 65536 > 65535
98
99        // Just fits
100        assert_eq!(
101            ConstCheckedPow::checked_pow(U16::from(2u8), 15),
102            Some(U16::from(32768u16))
103        );
104    }
105
106    c0nst::c0nst! {
107        pub c0nst fn const_checked_pow<T: [c0nst] ConstMachineWord + MachineWord, const N: usize>(
108            base: FixedUInt<T, N>,
109            exp: u32,
110        ) -> Option<FixedUInt<T, N>> {
111            ConstCheckedPow::checked_pow(base, exp)
112        }
113    }
114
115    #[test]
116    fn test_const_checked_pow() {
117        type U16 = FixedUInt<u8, 2>;
118
119        assert_eq!(
120            const_checked_pow(U16::from(2u8), 8),
121            Some(U16::from(256u16))
122        );
123
124        #[cfg(feature = "nightly")]
125        {
126            const BASE: U16 = FixedUInt { array: [2, 0] };
127            const POW_RESULT: Option<U16> = const_checked_pow(BASE, 8);
128            assert_eq!(POW_RESULT, Some(FixedUInt { array: [0, 1] })); // 256 = [0, 1] in little-endian
129        }
130    }
131}
fixed_bigint/fixeduint/checked_pow_impl.rs

fixed_bigint/fixeduint/
checked_pow_impl.rs
