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

fixed_bigint/fixeduint/
checked_pow_impl.rs
