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

fixed_bigint/fixeduint/
checked_pow_impl.rs
