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

fixed_bigint/fixeduint/
checked_pow_impl.rs
