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

fixed_bigint/fixeduint/
ilog_impl.rs
