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

core/num/
int_log10.rs
