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

fixed_bigint/fixeduint/
ilog_impl.rs
