ilog/
lib.rs

1// Copyright 2022 Redglyph
2//
3// Base 10 and 2 logarithm functions for integer types and their references:
4// u8, i8, u16, i16, u32, i32, u64, i64, u128, i128, usize, isize
5
6#![warn(clippy::pedantic)]
7#![allow(clippy::unreadable_literal)]
8#![no_std]
9
10mod tests;
11
12extern crate alloc;
13use alloc::boxed::Box;
14
15// =============================================================================================
16
17/// Trait that provides logarithms for integer types.
18///
19/// The [`log2`](IntLog::log2) and [`log10`](IntLog::log10) methods are optimized for the integer width and are
20/// `[inline]` since the code remains small enough. They typically use constant tables
21/// that are only stored once, even if the methods using them are inlined multiple times.
22///
23/// The **checked** versions of the methods, [`checked_log2`](IntLog::checked_log2) and [`checked_log10`](IntLog::checked_log10),
24/// return `None` if the logarithm is undefined for the parameter value, whereas the unchecked
25/// methods mentioned above simply panic or return a wrong value.
26pub trait IntLog {
27    /// Returns the largest integer less than or equal to the base 10 logarithm of the integer.
28    ///
29    /// Logarithms are only defined on positive values, calling `log10` with a null or a negative
30    /// argument may trigger a panic or return a wrong value.
31    /// See [`checked_log10`](Self::checked_log10) for a method that checks its argument first.
32    ///
33    /// # Examples
34    /// ```
35    /// # use ilog::IntLog;
36    /// let value: u64 = 100;
37    /// assert_eq!(value.log10(), 2);
38    /// assert_eq!(i32::log10(99), 1);
39    /// ```
40    fn log10(self) -> usize;
41
42    /// Returns the largest integer less than or equal to the base 2 logarithm of the integer.
43    ///
44    /// Logarithms are only defined on positive values, calling `log10` with a null or a negative
45    /// argument may trigger a panic or return a wrong value.
46    /// See [`checked_log2`](Self::checked_log2) for a method that checks its argument first.
47    ///
48    /// # Examples
49    /// ```
50    /// # use ilog::IntLog;
51    /// let value: u64 = 64;
52    /// assert_eq!(value.log2(), 6);
53    /// assert_eq!(i32::log2(63), 5);
54    /// ```
55    fn log2(self) -> usize;
56
57    /// Checked base 10 logarithm. Returns the largest integer less than or equal to the base 10
58    /// logarithm of the integer, or `None` if it doesn't exist.
59    ///
60    /// # Examples
61    /// ```
62    /// # use ilog::IntLog;
63    /// assert_eq!(100_u32.checked_log10(), Some(2));
64    /// assert_eq!(u64::checked_log10(99), Some(1));
65    /// assert_eq!(0_u32.checked_log10(), None);
66    /// ```
67    fn checked_log10(self) -> Option<usize>;
68
69    /// Checked base 10 logarithm. Returns the largest integer less than or equal to the base 10
70    /// logarithm of the integer, or `None` if it doesn't exist.
71    ///
72    /// # Examples
73    /// ```
74    /// # use ilog::IntLog;
75    /// assert_eq!(64_u32.checked_log2(), Some(6));
76    /// assert_eq!(u64::checked_log2(63), Some(5));
77    /// assert_eq!(0_u32.checked_log2(), None);
78    /// ```
79    fn checked_log2(self) -> Option<usize>;
80}
81
82// ---------------------------------------------------------------------------------------------
83
84/// Expands `IntLog` trait to references
85macro_rules! forward_ref_intlog {
86    ($imp:ident for $( $t:ty ),+) => {$(
87        impl $imp for $t {
88            #[inline]
89            fn log10(self) -> usize {
90                $imp::log10(*self)
91            }
92            #[inline]
93            fn log2(self) -> usize {
94                $imp::log2(*self)
95            }
96            #[inline]
97            fn checked_log10(self) -> Option<usize> {
98                $imp::checked_log10(*self)
99            }
100            #[inline]
101            fn checked_log2(self) -> Option<usize> {
102                $imp::checked_log2(*self)
103            }
104        }
105    )+}
106}
107
108/// Implements `IntLog` trait for unsigned integer type
109macro_rules! impl_unsigned_log {
110    ($SelfT: ty, $Msb: expr, $ApproxMul: expr, $ApproxShr: expr, $Table: ident) => {
111        impl IntLog for $SelfT {
112            #[inline]
113            fn log10(self) -> usize {
114                let y = ($ApproxMul * ($Msb - self.leading_zeros() as usize)) >> $ApproxShr;
115                y + (($Table[y + 1] as $SelfT).wrapping_sub(self) >> $Msb) as usize
116            }
117
118            #[inline]
119            fn log2(self) -> usize {
120                $Msb - self.leading_zeros() as usize
121            }
122
123            #[inline]
124            fn checked_log10(self) -> Option<usize> {
125                if self > 0 { Some(self.log10()) } else { None }
126            }
127
128            #[inline]
129            fn checked_log2(self) -> Option<usize> {
130                if self > 0 { Some(self.log2()) } else { None }
131            }
132        }
133
134        forward_ref_intlog!(IntLog for &$SelfT, &mut $SelfT, Box<$SelfT>);
135    }
136}
137
138/// Implements `IntLog` trait for signed integer type
139macro_rules! impl_signed_log {
140    ($SelfT: ty, $UnsignedT: ty) => {
141        impl IntLog for $SelfT {
142            #[inline]
143            fn log10(self) -> usize {
144                <$UnsignedT>::log10(self as $UnsignedT)
145            }
146
147            #[inline]
148            fn log2(self) -> usize {
149                <$UnsignedT>::log2(self as $UnsignedT)
150            }
151
152            #[inline]
153            fn checked_log10(self) -> Option<usize> {
154                if self > 0 { Some(<$UnsignedT>::log10(self as $UnsignedT)) } else { None }
155            }
156
157            #[inline]
158            fn checked_log2(self) -> Option<usize> {
159                if self > 0 { Some(<$UnsignedT>::log2(self as $UnsignedT)) } else { None }
160            }
161        }
162
163        forward_ref_intlog!(IntLog for &$SelfT, &mut $SelfT, Box<$SelfT>);
164    }
165}
166
167// ---------------------------------------------------------------------------------------------
168const LOG10_U8_TABLE: [u8; 4] = [0, 9, 99, u8::MAX];
169
170impl_unsigned_log! { u8, 7, 19, 6, LOG10_U8_TABLE }
171impl_signed_log! { i8, u8 }
172
173const LOG10_U16_TABLE: [u16; 6] = [0, 9, 99, 999, 9999, u16::MAX];
174
175impl_unsigned_log! { u16, 15, 18, 6, LOG10_U16_TABLE }
176impl_signed_log! { i16, u16 }
177#[cfg(target_pointer_width = "16")]
178impl_unsigned_log! { usize, 15, 18, 6, LOG10_U16_TABLE }
179#[cfg(target_pointer_width = "16")]
180impl_signed_log! { isize, u16 }
181
182const LOG10_U32_TABLE: [u32; 11] = [0, 9, 99, 999, 9999, 99999, 999999, 9999999, 99999999, 999999999, u32::MAX];
183
184impl_unsigned_log! { u32, 31, 19, 6, LOG10_U32_TABLE }
185impl_signed_log! { i32, u32 }
186#[cfg(target_pointer_width = "32")]
187impl_unsigned_log! { usize, 31, 19, 6, LOG10_U32_TABLE }
188#[cfg(target_pointer_width = "32")]
189impl_signed_log! { isize, u32 }
190
191const LOG10_U64_TABLE: [u64; 20] = [0, 9, 99, 999, 9999, 99999, 999999, 9999999, 99999999, 999999999,
192    9999999999, 99999999999, 999999999999, 9999999999999, 99999999999999, 999999999999999,
193    9999999999999999, 99999999999999999, 999999999999999999, 9999999999999999999];
194
195impl_unsigned_log! { u64, 63, 19, 6, LOG10_U64_TABLE }
196impl_signed_log! { i64, u64 }
197#[cfg(target_pointer_width = "64")]
198impl_unsigned_log! { usize, 63, 19, 6, LOG10_U64_TABLE }
199#[cfg(target_pointer_width = "64")]
200impl_signed_log! { isize, u64 }
201
202const LOG10_U128_TABLE: [u128; 40] = [0, 9, 99, 999, 9999, 99999, 999999, 9999999, 99999999, 999999999,
203    9999999999, 99999999999, 999999999999, 9999999999999, 99999999999999, 999999999999999,
204    9999999999999999, 99999999999999999, 999999999999999999, 9999999999999999999, 99999999999999999999,
205    999999999999999999999, 9999999999999999999999, 99999999999999999999999, 999999999999999999999999,
206    9999999999999999999999999, 99999999999999999999999999, 999999999999999999999999999, 9999999999999999999999999999,
207    99999999999999999999999999999, 999999999999999999999999999999, 9999999999999999999999999999999,
208    99999999999999999999999999999999, 999999999999999999999999999999999, 9999999999999999999999999999999999,
209    99999999999999999999999999999999999, 999999999999999999999999999999999999, 9999999999999999999999999999999999999,
210    99999999999999999999999999999999999999, u128::MAX];
211
212impl_unsigned_log! { u128, 127, 77, 8, LOG10_U128_TABLE }
213impl_signed_log! { i128, u128 }
214
215// ---------------------------------------------------------------------------------------------
ilog/lib.rs

ilog/
lib.rs
