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            // Count how many times we can divide by base
82            let mut n = self;
83            let mut count = 0u32;
84            while n >= base {
85                n /= base;
86                count += 1;
87            }
88            Some(count)
89        }
90    }
91
92    c0nst impl<T: [c0nst] ConstMachineWord + MachineWord, const N: usize> Ilog2 for &FixedUInt<T, N, Nct> {
93        fn ilog2(self) -> u32 {
94            <FixedUInt<T, N, Nct> as Ilog2>::ilog2(*self)
95        }
96        fn checked_ilog2(self) -> Option<u32> {
97            <FixedUInt<T, N, Nct> as Ilog2>::checked_ilog2(*self)
98        }
99    }
100
101    c0nst impl<T: [c0nst] ConstMachineWord + MachineWord, const N: usize> Ilog10 for &FixedUInt<T, N, Nct> {
102        fn ilog10(self) -> u32 {
103            <FixedUInt<T, N, Nct> as Ilog10>::ilog10(*self)
104        }
105        fn checked_ilog10(self) -> Option<u32> {
106            <FixedUInt<T, N, Nct> as Ilog10>::checked_ilog10(*self)
107        }
108    }
109
110    c0nst impl<T: [c0nst] ConstMachineWord + MachineWord, const N: usize> Ilog for &FixedUInt<T, N, Nct> {
111        fn ilog(self, base: Self) -> u32 {
112            <FixedUInt<T, N, Nct> as Ilog>::ilog(*self, *base)
113        }
114        fn checked_ilog(self, base: Self) -> Option<u32> {
115            <FixedUInt<T, N, Nct> as Ilog>::checked_ilog(*self, *base)
116        }
117    }
118}
119
120#[cfg(test)]
121mod tests {
122    use super::*;
123
124    #[test]
125    fn test_ilog2() {
126        type U16 = FixedUInt<u8, 2>;
127
128        assert_eq!(Ilog2::ilog2(U16::from(1u8)), 0);
129        assert_eq!(Ilog2::ilog2(U16::from(2u8)), 1);
130        assert_eq!(Ilog2::ilog2(U16::from(3u8)), 1);
131        assert_eq!(Ilog2::ilog2(U16::from(4u8)), 2);
132        assert_eq!(Ilog2::ilog2(U16::from(7u8)), 2);
133        assert_eq!(Ilog2::ilog2(U16::from(8u8)), 3);
134        assert_eq!(Ilog2::ilog2(U16::from(255u8)), 7);
135        assert_eq!(Ilog2::ilog2(U16::from(256u16)), 8);
136        assert_eq!(Ilog2::ilog2(U16::from(32768u16)), 15);
137    }
138
139    #[test]
140    fn test_ilog10() {
141        type U16 = FixedUInt<u8, 2>;
142
143        assert_eq!(Ilog10::ilog10(U16::from(1u8)), 0);
144        assert_eq!(Ilog10::ilog10(U16::from(9u8)), 0);
145        assert_eq!(Ilog10::ilog10(U16::from(10u8)), 1);
146        assert_eq!(Ilog10::ilog10(U16::from(99u8)), 1);
147        assert_eq!(Ilog10::ilog10(U16::from(100u8)), 2);
148        assert_eq!(Ilog10::ilog10(U16::from(999u16)), 2);
149        assert_eq!(Ilog10::ilog10(U16::from(1000u16)), 3);
150        assert_eq!(Ilog10::ilog10(U16::from(9999u16)), 3);
151        assert_eq!(Ilog10::ilog10(U16::from(10000u16)), 4);
152    }
153
154    #[test]
155    fn test_ilog() {
156        type U16 = FixedUInt<u8, 2>;
157
158        // Base 2
159        assert_eq!(Ilog::ilog(U16::from(8u8), U16::from(2u8)), 3);
160        assert_eq!(Ilog::ilog(U16::from(9u8), U16::from(2u8)), 3);
161
162        // Base 3
163        assert_eq!(Ilog::ilog(U16::from(1u8), U16::from(3u8)), 0);
164        assert_eq!(Ilog::ilog(U16::from(3u8), U16::from(3u8)), 1);
165        assert_eq!(Ilog::ilog(U16::from(8u8), U16::from(3u8)), 1);
166        assert_eq!(Ilog::ilog(U16::from(9u8), U16::from(3u8)), 2);
167        assert_eq!(Ilog::ilog(U16::from(27u8), U16::from(3u8)), 3);
168
169        // Base 16
170        assert_eq!(Ilog::ilog(U16::from(255u8), U16::from(16u8)), 1);
171        assert_eq!(Ilog::ilog(U16::from(256u16), U16::from(16u8)), 2);
172    }
173
174    #[test]
175    fn test_checked_ilog2() {
176        type U16 = FixedUInt<u8, 2>;
177
178        assert_eq!(Ilog2::checked_ilog2(U16::from(0u8)), None);
179        assert_eq!(Ilog2::checked_ilog2(U16::from(1u8)), Some(0));
180        assert_eq!(Ilog2::checked_ilog2(U16::from(8u8)), Some(3));
181    }
182
183    #[test]
184    fn test_checked_ilog10() {
185        type U16 = FixedUInt<u8, 2>;
186
187        assert_eq!(Ilog10::checked_ilog10(U16::from(0u8)), None);
188        assert_eq!(Ilog10::checked_ilog10(U16::from(1u8)), Some(0));
189        assert_eq!(Ilog10::checked_ilog10(U16::from(100u8)), Some(2));
190    }
191
192    #[test]
193    fn test_checked_ilog() {
194        type U16 = FixedUInt<u8, 2>;
195
196        // Zero argument
197        assert_eq!(Ilog::checked_ilog(U16::from(0u8), U16::from(2u8)), None);
198        // Invalid base
199        assert_eq!(Ilog::checked_ilog(U16::from(10u8), U16::from(0u8)), None);
200        assert_eq!(Ilog::checked_ilog(U16::from(10u8), U16::from(1u8)), None);
201        // Valid
202        assert_eq!(Ilog::checked_ilog(U16::from(8u8), U16::from(2u8)), Some(3));
203    }
204
205    c0nst::c0nst! {
206        pub c0nst fn const_ilog2<T: [c0nst] ConstMachineWord + MachineWord, const N: usize>(
207            v: FixedUInt<T, N, Nct>,
208        ) -> u32 {
209            Ilog2::ilog2(v)
210        }
211
212        pub c0nst fn const_ilog10<T: [c0nst] ConstMachineWord + MachineWord, const N: usize>(
213            v: FixedUInt<T, N, Nct>,
214        ) -> u32 {
215            Ilog10::ilog10(v)
216        }
217    }
218
219    #[test]
220    fn test_const_ilog() {
221        type U16 = FixedUInt<u8, 2>;
222
223        assert_eq!(const_ilog2(U16::from(8u8)), 3);
224        assert_eq!(const_ilog10(U16::from(100u8)), 2);
225
226        #[cfg(feature = "nightly")]
227        {
228            const EIGHT: U16 = FixedUInt::from_array([8, 0]);
229            const HUNDRED: U16 = FixedUInt::from_array([100, 0]);
230            const LOG2_RESULT: u32 = const_ilog2(EIGHT);
231            const LOG10_RESULT: u32 = const_ilog10(HUNDRED);
232            assert_eq!(LOG2_RESULT, 3);
233            assert_eq!(LOG10_RESULT, 2);
234        }
235    }
236}
fixed_bigint/fixeduint/ilog_impl.rs

fixed_bigint/fixeduint/
ilog_impl.rs
