core/num/
int_log10.rs

1//! These functions compute the integer logarithm of their type, assuming
2//! that someone has already checked that the value is strictly positive.
3
4use crate::num::NonZero;
5
6// 0 < val <= u8::MAX
7#[inline]
8const fn u8_impl(val: u8) -> u32 {
9    let val = val as u32;
10
11    // For better performance, avoid branches by assembling the solution
12    // in the bits above the low 8 bits.
13
14    // Adding c1 to val gives 10 in the top bits for val < 10, 11 for val >= 10
15    const C1: u32 = 0b11_00000000 - 10; // 758
16    // Adding c2 to val gives 01 in the top bits for val < 100, 10 for val >= 100
17    const C2: u32 = 0b10_00000000 - 100; // 412
18
19    // Value of top bits:
20    //            +c1  +c2  1&2
21    //     0..=9   10   01   00 = 0
22    //   10..=99   11   01   01 = 1
23    // 100..=255   11   10   10 = 2
24    ((val + C1) & (val + C2)) >> 8
25}
26
27// 0 < val < 100_000
28#[inline]
29const fn less_than_5(val: u32) -> u32 {
30    // Similar to u8, when adding one of these constants to val,
31    // we get two possible bit patterns above the low 17 bits,
32    // depending on whether val is below or above the threshold.
33    const C1: u32 = 0b011_00000000000000000 - 10; // 393206
34    const C2: u32 = 0b100_00000000000000000 - 100; // 524188
35    const C3: u32 = 0b111_00000000000000000 - 1000; // 916504
36    const C4: u32 = 0b100_00000000000000000 - 10000; // 514288
37
38    // Value of top bits:
39    //                +c1  +c2  1&2  +c3  +c4  3&4   ^
40    //         0..=9  010  011  010  110  011  010  000 = 0
41    //       10..=99  011  011  011  110  011  010  001 = 1
42    //     100..=999  011  100  000  110  011  010  010 = 2
43    //   1000..=9999  011  100  000  111  011  011  011 = 3
44    // 10000..=99999  011  100  000  111  100  100  100 = 4
45    (((val + C1) & (val + C2)) ^ ((val + C3) & (val + C4))) >> 17
46}
47
48// 0 < val <= u16::MAX
49#[inline]
50const fn u16_impl(val: u16) -> u32 {
51    less_than_5(val as u32)
52}
53
54// 0 < val <= u32::MAX
55#[inline]
56const fn u32_impl(mut val: u32) -> u32 {
57    let mut log = 0;
58    if val >= 100_000 {
59        val /= 100_000;
60        log += 5;
61    }
62    log + less_than_5(val)
63}
64
65// 0 < val <= u64::MAX
66#[inline]
67const fn u64_impl(mut val: u64) -> u32 {
68    let mut log = 0;
69    if val >= 10_000_000_000 {
70        val /= 10_000_000_000;
71        log += 10;
72    }
73    if val >= 100_000 {
74        val /= 100_000;
75        log += 5;
76    }
77    log + less_than_5(val as u32)
78}
79
80// 0 < val <= u128::MAX
81#[inline]
82const fn u128_impl(mut val: u128) -> u32 {
83    let mut log = 0;
84    if val >= 100_000_000_000_000_000_000_000_000_000_000 {
85        val /= 100_000_000_000_000_000_000_000_000_000_000;
86        log += 32;
87        return log + u32_impl(val as u32);
88    }
89    if val >= 10_000_000_000_000_000 {
90        val /= 10_000_000_000_000_000;
91        log += 16;
92    }
93    log + u64_impl(val as u64)
94}
95
96macro_rules! define_unsigned_ilog10 {
97    ($($ty:ident => $impl_fn:ident,)*) => {$(
98        #[inline]
99        pub(super) const fn $ty(val: NonZero<$ty>) -> u32 {
100            let result = $impl_fn(val.get());
101
102            // SAFETY: Integer logarithm is monotonic non-decreasing, so the computed `result` cannot
103            // exceed the value produced for the maximum input.
104            unsafe { crate::hint::assert_unchecked(result <= const { $impl_fn($ty::MAX) }) };
105
106            result
107        }
108    )*};
109}
110
111define_unsigned_ilog10! {
112    u8 => u8_impl,
113    u16 => u16_impl,
114    u32 => u32_impl,
115    u64 => u64_impl,
116    u128 => u128_impl,
117}
118
119#[inline]
120pub(super) const fn usize(val: NonZero<usize>) -> u32 {
121    #[cfg(target_pointer_width = "16")]
122    let impl_fn = u16;
123
124    #[cfg(target_pointer_width = "32")]
125    let impl_fn = u32;
126
127    #[cfg(target_pointer_width = "64")]
128    let impl_fn = u64;
129
130    // SAFETY: We have selected the correct `impl_fn`, so the converting `val` to the argument is
131    // safe.
132    impl_fn(unsafe { NonZero::new_unchecked(val.get() as _) })
133}
134
135macro_rules! define_signed_ilog10 {
136    ($($ty:ident => $impl_fn:ident,)*) => {$(
137        // 0 < val <= $ty::MAX
138        #[inline]
139        pub(super) const fn $ty(val: $ty) -> Option<u32> {
140            if val > 0 {
141                let result = $impl_fn(val.cast_unsigned());
142
143                // SAFETY: Integer logarithm is monotonic non-decreasing, so the computed `result`
144                // cannot exceed the value produced for the maximum input.
145                unsafe {
146                    crate::hint::assert_unchecked(result <= const { $impl_fn($ty::MAX.cast_unsigned()) });
147                }
148
149                Some(result)
150            } else {
151                None
152            }
153        }
154    )*};
155}
156
157define_signed_ilog10! {
158    i8 => u8_impl,
159    i16 => u16_impl,
160    i32 => u32_impl,
161    i64 => u64_impl,
162    i128 => u128_impl,
163}
164
165/// Instantiate this panic logic once, rather than for all the ilog methods
166/// on every single primitive type.
167#[cold]
168#[track_caller]
169pub(super) const fn panic_for_nonpositive_argument() -> ! {
170    panic!("argument of integer logarithm must be positive")
171}
core/num/int_log10.rs

core/num/
int_log10.rs
