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: u32 = 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: u32 = 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: u32 = 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: u32 = 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: fn u64(NonZero) -> u32 = u64;
129
130 // SAFETY: We have selected the correct `impl_fn`, so the converting `val` to the argument is
131 // safe.
132 impl_fn(val: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}
172