fixed_bigint/fixeduint/
ilog_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//! Integer logarithm implementations for FixedUInt.
16
17use super::{FixedUInt, MachineWord};
18use crate::const_numtraits::{ConstBitPrimInt, ConstIlog, ConstZero};
19use crate::machineword::ConstMachineWord;
20use crate::personality::Nct;
21
22c0nst::c0nst! {
23    impl<T: [c0nst] ConstMachineWord + MachineWord, const N: usize> c0nst ConstIlog for FixedUInt<T, N, Nct> {
24        fn ilog2(self) -> u32 {
25            match self.checked_ilog2() {
26                Some(v) => v,
27                None => panic!("ilog2: argument is zero"),
28            }
29        }
30
31        fn ilog10(self) -> u32 {
32            match self.checked_ilog10() {
33                Some(v) => v,
34                None => panic!("ilog10: argument is zero"),
35            }
36        }
37
38        fn ilog(self, base: Self) -> u32 {
39            match self.checked_ilog(base) {
40                Some(v) => v,
41                None => panic!("ilog: argument is zero or base is less than 2"),
42            }
43        }
44
45        fn checked_ilog2(self) -> Option<u32> {
46            if self.is_zero() {
47                return None;
48            }
49            // ilog2 = position of highest set bit = BIT_SIZE - 1 - leading_zeros
50            let leading = ConstBitPrimInt::leading_zeros(self);
51            Some(Self::BIT_SIZE as u32 - 1 - leading)
52        }
53
54        fn checked_ilog10(self) -> Option<u32> {
55            if self.is_zero() {
56                return None;
57            }
58            // Count how many times we can divide by 10
59            let ten: Self = core::convert::From::from(10u8);
60            let mut n = self;
61            let mut count = 0u32;
62            while n >= ten {
63                n /= ten;
64                count += 1;
65            }
66            Some(count)
67        }
68
69        fn checked_ilog(self, base: Self) -> Option<u32> {
70            if self.is_zero() {
71                return None;
72            }
73            let two: Self = core::convert::From::from(2u8);
74            if base < two {
75                return None;
76            }
77            // Count how many times we can divide by base
78            let mut n = self;
79            let mut count = 0u32;
80            while n >= base {
81                n /= base;
82                count += 1;
83            }
84            Some(count)
85        }
86    }
87}
88
89#[cfg(test)]
90mod tests {
91    use super::*;
92
93    #[test]
94    fn test_ilog2() {
95        type U16 = FixedUInt<u8, 2>;
96
97        assert_eq!(ConstIlog::ilog2(U16::from(1u8)), 0);
98        assert_eq!(ConstIlog::ilog2(U16::from(2u8)), 1);
99        assert_eq!(ConstIlog::ilog2(U16::from(3u8)), 1);
100        assert_eq!(ConstIlog::ilog2(U16::from(4u8)), 2);
101        assert_eq!(ConstIlog::ilog2(U16::from(7u8)), 2);
102        assert_eq!(ConstIlog::ilog2(U16::from(8u8)), 3);
103        assert_eq!(ConstIlog::ilog2(U16::from(255u8)), 7);
104        assert_eq!(ConstIlog::ilog2(U16::from(256u16)), 8);
105        assert_eq!(ConstIlog::ilog2(U16::from(32768u16)), 15);
106    }
107
108    #[test]
109    fn test_ilog10() {
110        type U16 = FixedUInt<u8, 2>;
111
112        assert_eq!(ConstIlog::ilog10(U16::from(1u8)), 0);
113        assert_eq!(ConstIlog::ilog10(U16::from(9u8)), 0);
114        assert_eq!(ConstIlog::ilog10(U16::from(10u8)), 1);
115        assert_eq!(ConstIlog::ilog10(U16::from(99u8)), 1);
116        assert_eq!(ConstIlog::ilog10(U16::from(100u8)), 2);
117        assert_eq!(ConstIlog::ilog10(U16::from(999u16)), 2);
118        assert_eq!(ConstIlog::ilog10(U16::from(1000u16)), 3);
119        assert_eq!(ConstIlog::ilog10(U16::from(9999u16)), 3);
120        assert_eq!(ConstIlog::ilog10(U16::from(10000u16)), 4);
121    }
122
123    #[test]
124    fn test_ilog() {
125        type U16 = FixedUInt<u8, 2>;
126
127        // Base 2
128        assert_eq!(ConstIlog::ilog(U16::from(8u8), U16::from(2u8)), 3);
129        assert_eq!(ConstIlog::ilog(U16::from(9u8), U16::from(2u8)), 3);
130
131        // Base 3
132        assert_eq!(ConstIlog::ilog(U16::from(1u8), U16::from(3u8)), 0);
133        assert_eq!(ConstIlog::ilog(U16::from(3u8), U16::from(3u8)), 1);
134        assert_eq!(ConstIlog::ilog(U16::from(8u8), U16::from(3u8)), 1);
135        assert_eq!(ConstIlog::ilog(U16::from(9u8), U16::from(3u8)), 2);
136        assert_eq!(ConstIlog::ilog(U16::from(27u8), U16::from(3u8)), 3);
137
138        // Base 16
139        assert_eq!(ConstIlog::ilog(U16::from(255u8), U16::from(16u8)), 1);
140        assert_eq!(ConstIlog::ilog(U16::from(256u16), U16::from(16u8)), 2);
141    }
142
143    #[test]
144    fn test_checked_ilog2() {
145        type U16 = FixedUInt<u8, 2>;
146
147        assert_eq!(ConstIlog::checked_ilog2(U16::from(0u8)), None);
148        assert_eq!(ConstIlog::checked_ilog2(U16::from(1u8)), Some(0));
149        assert_eq!(ConstIlog::checked_ilog2(U16::from(8u8)), Some(3));
150    }
151
152    #[test]
153    fn test_checked_ilog10() {
154        type U16 = FixedUInt<u8, 2>;
155
156        assert_eq!(ConstIlog::checked_ilog10(U16::from(0u8)), None);
157        assert_eq!(ConstIlog::checked_ilog10(U16::from(1u8)), Some(0));
158        assert_eq!(ConstIlog::checked_ilog10(U16::from(100u8)), Some(2));
159    }
160
161    #[test]
162    fn test_checked_ilog() {
163        type U16 = FixedUInt<u8, 2>;
164
165        // Zero argument
166        assert_eq!(
167            ConstIlog::checked_ilog(U16::from(0u8), U16::from(2u8)),
168            None
169        );
170        // Invalid base
171        assert_eq!(
172            ConstIlog::checked_ilog(U16::from(10u8), U16::from(0u8)),
173            None
174        );
175        assert_eq!(
176            ConstIlog::checked_ilog(U16::from(10u8), U16::from(1u8)),
177            None
178        );
179        // Valid
180        assert_eq!(
181            ConstIlog::checked_ilog(U16::from(8u8), U16::from(2u8)),
182            Some(3)
183        );
184    }
185
186    c0nst::c0nst! {
187        pub c0nst fn const_ilog2<T: [c0nst] ConstMachineWord + MachineWord, const N: usize>(
188            v: FixedUInt<T, N, Nct>,
189        ) -> u32 {
190            ConstIlog::ilog2(v)
191        }
192
193        pub c0nst fn const_ilog10<T: [c0nst] ConstMachineWord + MachineWord, const N: usize>(
194            v: FixedUInt<T, N, Nct>,
195        ) -> u32 {
196            ConstIlog::ilog10(v)
197        }
198    }
199
200    #[test]
201    fn test_const_ilog() {
202        type U16 = FixedUInt<u8, 2>;
203
204        assert_eq!(const_ilog2(U16::from(8u8)), 3);
205        assert_eq!(const_ilog10(U16::from(100u8)), 2);
206
207        #[cfg(feature = "nightly")]
208        {
209            const EIGHT: U16 = FixedUInt::from_array([8, 0]);
210            const HUNDRED: U16 = FixedUInt::from_array([100, 0]);
211            const LOG2_RESULT: u32 = const_ilog2(EIGHT);
212            const LOG10_RESULT: u32 = const_ilog10(HUNDRED);
213            assert_eq!(LOG2_RESULT, 3);
214            assert_eq!(LOG10_RESULT, 2);
215        }
216    }
217}
fixed_bigint/fixeduint/ilog_impl.rs

fixed_bigint/fixeduint/
ilog_impl.rs
